数据结构与算法分析

数据结构与算法分析（通用7篇）

数据结构与算法分析 篇1

数据结构算法设计与分析、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；

网页制作、程序设计Java、JSP程序设计、Oracle、XML程序设计、计算机网络、SSH（Struts+Spring+Hibernate）框架、Java EE程序设计、Ajax程序设计、Linux+PHP+MySQL程序设计、Android手机开发、UML系统分析与设计、性能测试、自动化软件测试、软件质量保证、毕业设计及项目综合实训等。

数据结构、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、金融学概论、西方经济学等基础理论课程；

网页制作、程序设计Java、JSP程序设计、J2EE程序设计、SQL Server数据库、Oracle数据库、Linux操作系统、UML系统分析与设计、软件工程、XML程序设计、SSH框架、金融市场学、ERP财务管理、管理信息系统、投资银行学、商业银行学、国际金融管理、毕业设计及项目综合实训等专业课程。

数据结构、计算机网络、计算机组成原理、操作系统原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；

网页制作、程序设计Java、JSP程序设计、J2EE程序设计、XML程序设计、Ajax程序设计、SSH框架、Android手机开发、Linux+PHP+MySQL程序设计、SQL Server数据库、Linux操作系统、UML系统分析与设计、软件项目管理、行业标准与规范、IT服务管理、IT职业英语、毕业设计及项目综合实训等专业课程

数据结构与算法分析 篇2

目前, 公共交通是人们出行最常用的一种方式, 本文意在对公交数据结构算法与实现问题进行相关分析, 使人们出行可享受便利的公交服务。基于对具体公交实际情况的研究, 笔者对公交数据结构的算法进行了人性化的修改, 使其实用程度大大提高, 以不断满足大多数人的出行习惯和要求。

1 以GIS为基础的公交数据结构模型

GIS就是一种地理信息系统, 它主要是用于搜集、模拟、加工、检索、分析以及表达地理空间数据的计算机数据信息系统。它以点、线、面三种不同的基底数据模型表达为主。因此, 我们可以通过计算机建立起城市公交网络模型, 利用GIS点模型来显示公交车站的具体数据信息, 进而用这些数据结构来表示公交线路的路径信息。

经过比较, 我们发现一个城市的公交网络要比其道路网络复杂许多, 它不但包括公交站点与公交路线的数据结构, 而且还有许多其他的数据信息。我们可以从图1公交网络模型的结构图来了解部分相关数据结构。

首先, 公交站点数据。

这里的公交站点是指城市公交网络体系中的所有公交站点, 在这里, 我们可以借助于点模型来具体描述它们的地理位置, 最后把它们站点名称等信息储存在属性数据之中。

其次, 公交线路数据。

据调查, 每一条公交线路都有自己对应的唯一编号。这一编号包含多种信息, 主要有该公交线路的名称、起点、终点、上班、下班时间等具体信息, 这些信息都记录在属性数据中。

其三, 公交段数据。

公交段数据主要指城市公交线路的路径信息。我们可以利用线模型来描述其具体的地理位置。

其四, 线路与站点关联数据。

各个线路与站点的辨别以及相关信息都是通过关联数据来体现的, 这些数据都是按照顺序从始至终来记录的, 清楚并相互对应的描述了公交线路的每个站点。

其五, 站点与线路关联数据。

站点与线路关联数据是用来记录站点所经过的公交线路信息的, 并以此来记录站点与线路的关联信息。

公交网络模型, 它的数据结构不单单含有丰富的公交信息, 还明确了每一个公交实体相互间的关系具体是怎样。在公交段表中所介绍的公交站点和公交段之间的空间拓扑关系, 其实就是每个公交段记录一个前结点和后结点, 实际上也是这个公交段的起始站点和终止站点的一个记录。其次, 每张表中的数据前后要保持一致, 比如:站点-线路关联中的线路ID必须跟公交线路的Line ID保持一致, 而它们之间的数据结构关联关系见图2具体表述。

2 公交数据结构算法与实现的思路

在实际的生活中, 公交数据不是固定不变的, 它往往受到多种因素的影响, 因此在公交数据结构算法与实现的过程中我们要充分考虑这一问题, 努力合理实现公交数据结构的计算和应用。

2.1 影响公交数据结构算法与实现的因素

影响公交数据结构算法与实现的因素有多个, 主要有以下几个:首先, 出行距离。这主要包括两种, 即车上距离和车外距离。车外距离就是指乘车者为了乘坐公车而步行的那段距离;其次, 换乘次数。这是指乘车者为到达目的地在乘车的过程中所换乘公交车的次数;其三, 出行时间。这是指乘车者在一次出行过程中所需总的时间, 这既包括在车上的时间也包括为乘车花费的车外时间;其四, 出行费用。这是指乘车者在完成一次出行过程中所花的车费。由于不同的乘客对于这些因素的要求不一样, 他们优先考虑的因素不同, 这就导致公交数据及其结构的变化。本文笔者经过研究提出了全面的公交数据结构模型, 并给出了对应的计算方法。

2.2 人性化的公交数据结构算法与实现

而公交数据结构算法与实现在实际的运用中要本着人性化的要求, 因此在这一算法的过程中, 我们要着实考虑多种不同的优先策略, 例如尽量减少乘客的换乘次、费用最少化、时间和距离最短化、道路最优化等等。不同的人对公交乘坐路线的选择也是会有不同的, 因此乘车方案要结合具体的实际情况进行考虑, 有的人会把时间因素看的重要些, 有的人会率先考虑费用问题, 总而言之, 其实就是对公交网络模型中的权值的衡量。

本文经过实践和调查提出了一种基于换乘次数最少的公交数据结构算法, 这一计算方法相对其他方法来说比较符合人们出行时的心理状况。这一计算方法的思想我们可以描述如下:

根据大多数人的习惯我们可以得出, 在出行选择路线时, 2站之间首先考虑的是直达车, 如果只有一条则选择该方案, 若有多条则根据花费时间, 花费费用等因素进行选择。如果没有直达车, 则要考虑换乘, 换乘时首先考虑经过2站的车辆是否有共同的站点, 如果有, 则可以在此站进行换乘, 如果没有则要考虑进行2次换乘, 即在2站之间选择2个站点, 这2个站点的选择必须保证4个站点中有可直达的车, 在中间的站点换乘2次, 如果选择此出行方式还是没办法到达目的地, 则我们就需要考虑进行3次或者更多次的换乘。综上所述, 出行乘坐公交车时不仅仅有一种方案, 这就需要我们综合花费时间, 花费费用等多方面的因素优先选择。所以, 这一算法是对不同情况进行综合考虑的结果, 也就是用下面所述的权值来衡量最优的换乘方案:

σ=距离×权重%+费用×权重%+景观道路×权重%......

从以上公式我们可以看出, 依据不同情况对每种因素所占的权重进行调整, 来计算综合因素σ, 最后通过比较σ来就可判定多种乘车方案中的哪个是最优方案, 以选择最优的出行路线。

2.3 公交数据结构算法与实现的基本步骤

本文通过对最优公交途径的分析, 并结合城市公交网络的具体基本特点提出了城市公交数据结构算法与实现的具体步骤:首先, 依据城市公交网络建造公交数据结构模型;其次, 结合城市公交网络的具体特点把直达矩阵引入公交网络数据的计算, 并且可以根据这一直达矩阵把城市公交网络看成是一个“公交网络邻接图”。其三, 采用最短路径算法的同时, 结合城市公交抽象网络图进行计算, 即可得出最少换乘次数以及可能换乘的公交站点。最后, 在用建立起来的公交网络模型和所得换乘次数以及可能的换乘站点进行计算, 得到了综合考虑最小换乘和最短路径的最佳路径。这样, 就实现了人性化的公交乘坐计算方法, 给人们的出行也带来了便利。

3 公交数据结构算法与实现的意义

本文在以上分析的基础上, 从乘客的出行心理出发, 提出了“换乘次数最少”、“最短路径”等相结合的公交数据结构算法与实现的标准。这些算法在GIS地理信息系统中寻找接点的相邻接点, 打破了邻接关心的束缚, 使得换乘的搜索和计算成为可能, 为乘客提供了起点与终点之间的适合的便利路线。这不但满足了人们“换剩次数最少”的出行心理需求与实现公交出行的科学性, 也在一定程度上提高了人们公交出行的意识, 对解决城市交通压力过大与交通堵塞等城市交通问题有极大帮助。

4 结束语

总而言之, 论述以GIS为基础的城市公交数据结构模型, 并且在此基础上提出了公交数据结构算法与实现的思路, 这一思路是在分析实际的公交出行情况后得出的结论。文中笔者提到的具体公交数据结构算法其在具体的实用过程中有所提高。但是我们也应看到公交出行的实际情况要比我们看到的复杂的多, 还有许多方面都需要进一步研究, 相信在未来的公交数据结构算法与实现的过程中我们会取得更好的成绩, 最终实现公交的便捷化、快速化、实用化。

参考文献

[1]姚宝珍, 于艳弘, 于滨.公交IC卡收费系统与客流数据采集、处理[J].长春工业大学学报 (自然科学版) , 2005 (03) .

[2]张汝华, 杨晓光, 严海.智能交通信息特征分析与处理系统设计[J].交通运输系统工程与信息, 2003 (04) .

海量数据实时处理算法设计与分析 篇3

【关键词】海量数据 MapReduce算法 hash

一、背景以及现状

随着互联网的发展，在许多科学领域，信息数量呈指数型增长。截止到2011年全球信息总量为1.8ZB[1]。海量数据的时代已经来临，然而面对海量数据该如何存储，如何有效的处理，及时有效的处理了这些数据对于各行各业乃至整个社会的发展有着重要的意义。过去的几年里单机的性能得到发展，硬件也得到发展。但在理论上这些硬件技术的发展是有限的。现今的多核技术就是并行技术发展的一个实例[2]。

二、MapReduce的技术特征

1）横向扩展与纵向扩展。对于MapReduce集群的构建采用低廉且容易扩展的低端商用服务器，考虑到大量数据存储的需要，基于低端服务器的集群远比基于高端服务器的集群优越，所以基于低端服务器实现都会使用MapReduce并行计算集群。

2）失效与常态。相对低端的服务器适用于MapReduce集群，无论哪个节点失效，其他的节点要无缝接管着失效节点的计算任务；当该节点恢复以后将不需要人工配置而是能自动无缝加入集群。

3）处理向数据迁移。MapReduce采取数据与代码互定位的技术时，计算节点首先计算其本地存储的数据并对其负责使数据发挥本地化的特点。

三、对MapReduce改进

（一）预处理算法

大量事实证明，在数据挖掘中整个工作量的60%到80%都是数据预处理[3]。通过数据预处理工作可以使残缺的数据变得完整，能达到数据类型相同化、数据格式的一致化、数据存储集中化和数据信息精练化[4]。采用Hash算法，间接取余法。公式：f（x）：= x mod maxM ； maxM一般是不太接近 2^t 的一个质数。得余数x，根据x对源数据进行预处理分配，采用Hash取模进行等价映射。

（二）分布缓存

对由N台缓存服务器组成的集群缓存把集群依次编号为0 - （N-1）。

1）hash机器节点。首先求出机器节点处的hash值，然后把它分布到0～2^32的一个圆环上（顺时针分布）。如图3-1，集群中有ABCDE五台机器，通过hash算法把它们分布到如图3-1所示的环上。

2）访问方式。写入缓存的请求，Key值为K计算器hash值为hash（K），Hash（K）对应着图3-1环中的某一个点。若该点没有对应映射到具体的某个机器节点上，就进行顺时针查找直到找到确定的目标节点，也就是首次有映射机器的节点。Hash（K）的值介于A～B之间时，那么它命中的机器节点应当就是图3-1中的B节点。

3）增加节点的处理。如图3-1中如果在原有集群的基础上想再增加一台机器F，过程如下，首先要计算机器节点的Hash值，找到环中的一个节点，把机器映射上，如图3-2所示。在增加机器节点F以后访问策略不发生改变，按2）中的方式继续访问，那么此时仍然是不可避免的是缓存不命中的情况，hash（K）在增加节点之前不能命中的数据是落在C～F之间的数据。hash它使用了虚拟节点的思想，在圆上分配了100～200个点为其中的每一个物理节点，这样就能较好的抑制了分布的不均匀的情况，还能最大限度减小当服务器增减时缓存的重新分布。

{三}复用中间结果

在对海量数据进行了预处理和分布式缓存之后，采用简单随机取样[5]的方法对缓存好的数据进行随机取样具体实现该方法。

四、实验

本论文的实验可以对是某地区房价数据进行处理，简要的过程如下：

第一数据预处理阶段，首先让每一组数据分别自动编号，然后采用取余的方法。第二根据分组情况，分别把各组数据放置到不同的服务器上。第三采用简单随机取样的方法对缓存好的数据进行随机取样，选择出最适合的房产。

五、结束语

本文在算法方面也还有一些不足之处，有待深入的分析。目前海量数据的处理还有很多值得深入研究和挖掘的地方，还将会是热门的话题以及更多专家学者热衷研究的方向。

【参考文献】

[1] John Gantz， David Reinsel .The 2011 Digital Universe study： Extracting Value from Chaos [J]. International Data Corporation （IDC）， 2011

[2]陈康，郑纬民.云计算：系统实例与研究现状[J].软件学报，2009，20（5） ：1337 -1348.

[3]D. Romano， Data Mining Leading Edge： Insurance&Banking， InProceedings of Knowledge Discovery and Data Mining， Unicorn， BrunelUniversity， 1997.

[4]刘军强，高建民，李言等.基于逆向工程的点云数据预处理技术研究.现代制造工程.2005.7： 73-75.

《算法与数据结构》教学大纲 篇4

一、使用说明

（一）课程性质

《数据结构》是一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的先修课程为C程序设计或C++程序设计。

（二）教学目的

学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，要求学生会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。

（三）教学时数

课堂讲授每周4学时，18周，共72学时。

（四）教学方法

本课程将采用课堂讲授及课堂讨论相结合的交互式教学法，同时辅以必要的上机操作实践。

（五）面向专业

计算机科学与技术专业。

二、教学内容

第一章 绪论

（一）教学目的要求

介绍数据结构的一些基本概念，算法的时间复杂度和空间复杂度的分析方法，抽象数据类型的定义和使用以及算法的描述方法。掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。

（二）教学内容

主要内容：数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。抽象数据类型。算法时间复杂度和空间复杂度的分析。

教学重点：有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。

教学难点：算法时间复杂度和空间复杂度的分析。

第一节

一、非数值计算

二、数据结构课程内容的历史演变

三、数据结构研究范围

第二节

一、数据

二、数据结构

三、数据类型

四、抽象数据类型

五、多型数据类型

第三节

一、固有数据类型

抽象数据类型的表示与实现

基本概念和术语 什么是数据结构

二、数据抽象

三、抽象数据类型的描述语言

第四节

一、算法

二、算法设计的要求

三、算法效率的度量

四、算法的存储空间需求

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

第二章 线性表

（一）教学目的与要求

介绍线性表的基本概念和类型定义，对顺序表和单链表的常用操作方法及其程序实现，循环链表和双向链表的定义和它的插入、删除等操作方法。掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。

（二）教学内容

主要内容：线性表的基本概念和类型定义，线性表的顺序存储结构，线性表的链接存储结构：（1）单链表的查找、插入和删除；（2）循环链表；（3）双向链表。

教学重点：在顺序表和链表上各种基本算法的实现及相关的时间性能分析。

教学难点：用所学的基本知识设计有效算法解决与线性表相关的应用问题。链表要分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针以及循环链表、双向链表的特点等。

第一节

一、线性表的定义

二、线性表的基本操作

第二节

一、顺序表

二、顺序表上基本运算的实现

三、顺序表应用举例

第三节

一、线性链表

二、循环链表

三、双向链表

四、静态链表

第四节 一、一元多项式的数学表示 二、一元多项式的计算机表示

三、抽象数据类型：一元多项式的定义

四、抽象数据类型：一元多项式的存储结构

五、抽象数据类型：一元多项式的基本操作算法实现

（三）教学方法与形式

一元多项式的表示及相加 线性表的链式存储表示和实现 线性表的顺序存储表示和实现

线性表的类型定义 算法和算法分析 课堂讲授、多媒体课件。

（四）教学时数

8学时。

第三章 栈和队列

（一）教学目的与要求

介绍栈和队列的定义，顺序和链接存储的栈和队列的各种运算的方法及其程序实现。掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现。

（二）教学内容

主要内容：栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法，栈的应用举例，队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

教学重点：栈和队列在两种存储结构上实现的基本运算。教学难点：递归的实现、循环队列中对边界条件的处理。

第一节

一、抽象数据类型栈的定义

二、栈的表示和实现

第二节

一、数制转换

二、括号匹配的检验

三、表达式求值

第三节

一、函数调用与栈

二、递归调用栈的变化

第四节

一、抽象数据类型队列的定义

二、链队列--队列的链式表示和实现

三、循环队列--队列的顺序表示和实现

第五节

一、优先级队列的概念

二、优先级队列的存储表示和实现

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

第四章 串

（一）教学目的与要求

介绍串的基本概念和操作，串的存储结构以及基本操作的算法实现。掌握串的基本概念和操作，掌握串的存储结构以及基本操作的算法实现。

（二）教学内容

主要内容：串的类型定义，串的表示和实现，正文模式匹配，正文编辑——串操作应用举例串的类型定义。

教学重点：串类型定义中各基本操作的定义以及串的实现方法。教学难点：利用串的基本操作来实现串的其它操作。

优先级队列 队列 栈与递归的实现 栈的应用举例

栈

第一节

一、串的定义

二、串的基本操作

第二节

一、定长顺序存储表示

二、堆分配存储表示

三、串的块链存储表示

四、字符串操作的实现

第三节

二、模式匹配的一种改进算法

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

串的类型定义

串的表示和实现

字符串的模式匹配

一、求子串位置的定位函数Index（S，T，pos）

第五章 数组和广义表

（一）教学目的

介绍数组的基本概念和基本操作的算法实现；稀疏矩阵的定义和各种存储结构，稀疏矩阵的转置和相加的方法并了解其算法；广义表的定义、存储结构和求广义表的长度及深度的算法，建立广义表和输出广义表的方法并了解其算法。掌握数组的基本概念和基本操作的算法实现；掌握稀疏矩阵的定义和各种存储结构，掌握稀疏矩阵的转置和相加的方法并了解其算法；掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握建立广义表和输出广义表的方法并了解其算法。

（二）教学内容

主要内容：稀疏矩阵的定义、存储和运算，广义表的定义、存储和运算串的类型定义。教学重点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。教学难点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。

第一节 第二节

一、数组的存储方式

二、数组元素存储位置的计算

三、基本操作的实现

第三节

一、特殊矩阵

二、稀疏矩阵

第四节

一、广义表的基本概念

二、广义表的三个重要结论

第五节

一、头尾链表存储表示

二、扩展线性链表存储表示

第六节

广义表的递归算法 广义表的存储表示 广义表的定义 矩阵的压缩存储 数组类型 数组的顺序表示和实现

一、求广义表的深度

二、复制广义表

三、建立广义表的存储结构

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

6学时。

第六章 树和二叉树

（一）教学目的与要求

介绍树的定义、性质、存储结构及遍历算法，握二叉树的各种遍历方法及其实现，二叉树的其他操作方法及实现，树、森林和二叉树的转换方法，哈夫曼树的定义和构造哈夫曼树的方法，哈夫曼树编码的方法。掌握树的定义、性质、存储结构及遍历算法，熟练掌握二叉树的各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，掌握树、森林和二叉树的转换方法，掌握哈夫曼树的定义和构造哈夫曼树的方法，了解哈夫曼树编码的方法。

（二）教学内容

主要内容：树的定义、性质和表示方法，二叉树的定义、性质和存储结构，二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现，树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法，哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的方法。

教学重点：二叉树和树的遍历及其应用。

教学难点：实现二叉树和树的各种操作的递归算法。

第一节

一、树的定义

二、森林的定义

三、树的抽象数据类型定义

第二节 一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构

第三节

一、遍历二叉树

二、线索二叉树

第四节

一、树的存储结构

二、森林与二叉树的转换

三、树和森林的遍历

第五节

一、最优二叉树（赫夫曼树）

二、赫夫曼编码

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

10学时。

最优树和赫夫曼编码

树和森林

遍历二叉树和线索二叉树

二叉树

树的定义和基本术语

第七章 图

（一）教学目的与要求

介绍图的定义和术语；图的存储结构及深度和广度优先搜索方法及其实现；图的生成树的概念，求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；拓扑排序的方法并了解其实现算法；计算关键路径的方法及其实现算法。掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索方法及其实现；掌握图的生成树的概念，掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；掌握拓扑排序的方法并了解其实现算法；了解计算关键路径的方法并了解其实现算法。

（二）教学内容

主要内容：图的定义和术语，图的邻接矩阵、邻接表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，拓扑排序。

教学重点：图在邻接矩阵与邻接表上实现的遍历算法(DFS和BFS)。教学难点：基于遍历算法的应用。

第一节

一、图的定义

二、无向图

三、有向图

四、连通图

五、生成树

第二节

一、数组表示法

二、邻接表 三、十字链表

四、邻接多重表

第三节

一、深度优先搜索

二、广度优先搜索

三、连通分量

第四节

一、Kruskal算法

二、Prim算法

第五节

一、拓扑排序

二、关键路径

第六节

一、从某个源点到其余各项点的最短路径

二、每一对顶点之间的最短路径

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

12学时。

最短路径 有向无环图及其应用

最小生成树 图的遍历 图的存储表示 图的定义和术语

第八章 查找表

（一）教学目的与要求

介绍顺序表查找和有序表查找的方法及实现；二叉排序树和平衡二叉树的定义、对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；B树的定义，查找、插入和删除元素的方法。熟练掌握顺序表查找和有序表查找的方法及实现；掌握二叉排序树和平衡二叉树的定义、熟练掌握对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。掌握哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；了解B树的定义，查找、插入和删除元素的方法。

（二）教学内容

主要内容：顺序查找和二分查找，索引查找和分块查找，散列查找，动态查找树表。教学重点：顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。

教学难点：二叉排序树的删除算法。

第一节

一、顺序表的查找

二、有序表的查找

三、静态树表的查找

四、索引顺序表的查找

第二节 一、二叉排序树

二、平衡二叉树

三、动态的m路搜索树

四、B树和B+树基本概念

第三节

一、什么是哈希表

二、哈希函数的构造方法

三、处理冲突的方法

四、哈希表的查找及其分析

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

10学时。

第九章 内部排序

（一）教学目的与要求

介绍插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，快速排序、堆排序、二路归并排序的方法及其实现，各种排序方法的稳定性、时间复杂度和空间复杂度。掌握插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，熟练掌握快速排序、堆排序、二路归并排序的方法及其实现，掌握各种排序方法的稳定性、时间复杂度和空间复杂度。

（二）教学内容

主要内容：排序的概念，直接插入排序，冒泡排序和快排序，直接选择排序和堆排序，归并排序。

哈希表 动态查找表 静态查找表 教学重点：插入排序(直接插入、折半插入)、交换排序（冒泡、快速排序）、选择排序（直接选择、堆）、2-路归并排序。

教学难点：快速排序partition算法的应用和堆的调整。

第一节

一、稳定的排序方法

二、内部/外部排序

三、内部排序种类

四、排序中的基本操作

五、排序数据的存储方式

第二节

一、直接插入排序

二、其他插入排序

三、希尔排序

第三节

一、起泡排序算法

二、快速排序算法

第四节

一、简单选择排序

二、树形选择排序

三、堆排序

第五节 第六节

一、多关键字的排序

二、链式基数排序

第七节

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

10学时。

第十章 文件

（一）教学目的与要求

介绍文件和记录的基本概念以及基本操作。掌握文件和记录的基本概念以及基本操作。

（二）教学内容

主要内容：基本概念，顺序文件，索引文件，索引顺序文件，散列文件，多关键码文件。教学重点：各种文件的结构特点及其适用场合。教学难点：各种文件的结构特点及其适用场合。

第一节

一、文件及其类别

二、记录的逻辑结构和物理结构

三、文件的操作

四、文件的物理结构

第二节

一、顺序文件的定义

顺序文件 基本概念

各种排序方法的综合比较

归并排序法 基数排序 选择排序法 交换排序法 插入排序 排序的定义和方法

二、顺序文件的优缺点

第三节

一、索引文件的定义

二、索引文件的特点

第四节

一、ISAM文件

二、VSAM文件

第五节

一、散列文件的定义

二、散列文件的特点

第六节

一、多重表文件

二、倒排文件

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

三、考核方式

本课程的考核采用闭卷考试的方式，课程的总评成绩由平时成绩、实验成绩和期末考试成绩三部分组成，其中平时成绩占总评成绩的10%，实验成绩占总评成绩的30%，期末考试成绩占总评成绩的60%。

四、教材选用

1、殷人昆，陶永雷，谢若阳等：《数据结构（用面向对象方法与C++语言描述）》，清华大学出版社，2007.6年第二版。

2、严蔚敏，吴伟民：《数据结构（C语言版）》 及《数据结构题集（C语言版）》，清华大学出版社，2003年第一版。

多关键码文件 散列文件 ISAM文件和VSAM文件

数据结构与算法分析 篇5

1004012033 陈孝婕 10计本3 “数据结构与算法”这门课程对于计算机科学与技术系的学生来说是非常重要的课程。这门课程主要包括十个章节。

一．每章主要知识点总结和个人掌握情况

第一章主要要求学生掌握数据、数据类型、数据结构、算法及算法分析等基本概念和基础知识。另外，第一章结合课程学习要求，复习和掌握算法描述工具--C语言中的指针类型与指针变量、结构类型与结构变量、函数与参数、递归定义和递归函数、动态存储分配、文件操作、程序测试和测试集、测试数据的设计和程序调试等问题。

从这一章中我不仅学到了数据结构的基本概念和基础知识，了解到什么是数据结构，我们为什么要学习数据结构这门课程。而且复习了大一下学期所学的C语言程序课程设计中的算基本法语句。有利于数据结构与算法后面课程的学习。

第二章主要学习顺序表（包括顺序串）数据类型、数据结构、基本算法及相关应用。知识点包括顺序表的概念、数据结构定义、数据类型描述、基本算法的实现及其性能的分析等知识；还有“查找”和“排序”的概念，“查找”包括3种查找方式：简单顺序查找、二分查找、分块查找；“排序”包括直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序和归并排序（重点为二路归并排序）6种排序方式；掌握应用顺序表来进行查找和排序的各类算法以及不同的查找和排序算法间的性能差异。在此基础上，理解顺序串的相关应用。

从这一章中我学习到各种不同的查找方法和排序方式，其中二分查找作为重点查找方法我进行了重点学习，熟悉并熟练地运用二分查找并且了解到各种排序方法适合于不同的顺序表。对于顺序串的学习，我主要掌握了字符串的基本运算，包括：求串长strlen(S)、连接stract(ST1,ST2)、求子串substr(S,i,j)、比较串的大小strcmp(S,T)、插入insert(S1,i,S2)、删除delete(S,i,j)、子串定位index(S1,S2)、置换(replace(S1,i,j,S2)、replace(S,T,V)两种)。

第三章主要学习链表（单聊表、循环链表）的概念、数据结构、数据类型描述、基本算法以及链表相关应用。需要掌握各种链表的概念、数据结构定义、基本算法实现以及算法的性能分析等知识，掌握链表的相关应用方法，在此基础上掌握链串的相关知识。

通过这一章我学习了另一种数据结构——链表，在逻辑结构上，链表与顺序表一样，也是线性逻辑结构；单链表借助“地址”的概念，使用了链式存储结构，产生了一种新的数据结构——链表，链表的基本操作是地址运算，在此基础上构成的链表基本算法的特点也就不同，从链表算法的功能看，链表的基本运算与顺序表基本相同，但实现方法和过程与顺序表是不同的，链表可分为静态链表和动态链表两种。这一章我学习到的实际应用是链表的创建、插入和删除等基本操作。循环链表的建立和查询方法。

第四章主要知识点是在两种不同的存储结构下设计的堆栈，即顺序栈和链栈。主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。通过对本章的学习，要求掌握顺序栈及链栈的数据类型描述、数据结构、基本算法及其性能分析等知识。在此基础上，了解堆栈的相关应用，掌握应用堆栈解决实际问题的思想及方法。

通过对这一章的学习，我了解了堆栈的概念，堆栈的原理、创建方法以及使用方式。“后进先出”是其基本原则。利用堆栈可以轻松方便的解决对称问题以及括号匹配等问题。堆栈与顺序表、链表不同的是，堆栈只能对一端的数据元素进行操作，即只在栈顶进行元素的插入和删除。掌握顺序栈和链表的存储结构是学习堆栈的要素之一。堆栈是一类常用的数据结构，被广泛应用于各种程序设计中。

第五章的重点知识是在顺序存储和链接存储下的两种队列——顺序（循环）队列和链队

列的数据结构、基本运算及其性能分析以及应用。通过本章的学习，要求掌握顺序队列（重点是循环队列）及链队列的概念、数据类型描述、数据结构、基本算法及其性能分析等知识。在此基础上，了解队列的相关应用，掌握应用队列来解决实际问题的思想及方法。

通过这一章的学习，我掌握了队列的定义，概念，创建以及“对头删除”，“队尾插入”的原则。重点了解了判断循环队列空和满的判断条件。同堆栈一样，队列也是一种具有线性逻辑结构、运算受限制的数据结构。与堆栈只在一端（栈顶）进行元素的插入和删除运算不同的是，队列是在对头进行插入，而在队尾完成数据元素的删除，所以队列的算法和适用的应用问题与堆栈有很大的区别。队列作为一类常用的数据结构，被广泛应用于各种程序设计中。

第六章主要学习数组、系数矩阵和广义表的基本概念、集中特殊矩阵的存储结构及基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。通过本章的学习，要求掌握特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解稀疏矩阵的计算和广义表的存储结构及其基本运算。了解矩阵与广义表的相关应用。

通过这章的学习和前几章的比较，我了解到前几章的线性结构中的数据元素都是非结构的原子类型，即每一个元素都是不可再分解的。本章讨论的数组和广义表等数据结构可以看成是在前几章线性结构基础上的一个扩展：组成该数据结构的数据元素本身也是一个数据结构。矩阵计算应该数值计算方面的问题，由于矩阵和数组的关系以及特殊矩阵存储结构的复杂性，进而使得特殊矩阵的存储结构和算法也表现出其特殊性，所以数据机构课程应该解决其计算问题。

第七章的学习重点是二叉树的概念、数据类型、数据结构定义和各种基本算法，在此基础上介绍二叉树的一些应用问题。通过本章的学习，我掌握了二叉树概念及其性质、二叉树的逻辑结构和存储结构等知识，掌握二叉树的建立、遍历、线索化等基本概念和算法及性能分析，能熟练应用二叉树这章结构来解决一些实际问题，如哈夫曼树及哈夫曼编码、查找与排序（二叉树排序）等问题。了解堆栈排序及其算法等知识。二叉树是非线性数据结构，是树形结构的一种特殊形式。在现实生活有许多数据关系可抽象为树或二叉树的形式。本章中的二叉树的概念及其性质、二叉排序树、存储结构、遍线索（化）、基本算法为重点内容，二叉排序树的应用为难点内容。

第八章的学习重点是树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树间的转化算法等，在此基础上介绍树的应用——B-树。通过本章的学习，我掌握了树和森林的概念和性质、数据结构、树的基本算法及性能分析、树与二叉树间的转换及其算法，并能应用B-树来实现数据元素的动态查找。舒适一种非线性结构，它在二叉树的基础上做了更为一般化的扩展，而森林是树的集合。在树结构中，每一个元素最多只有一个前驱，但可能有多个后继。现实生活中的家族关系、单位的组成结构等，均可抽象为树的形式。

第九章学习重点是散列结构的相关知识，学习常用的散列函数和冲突处理方法，散列表的常用算法及其性能分析，通过本章的学习，我掌握了散列结构和散列函数的相关概念，掌握散列结构的存储（散列表）的相关概念，要求掌握散列冲突处理方法（散列法）的相关知识，并能灵活运用散列法解决应用问题。

散列结构是使用散列函数建立数据结点关键字与存储地址之间的对应关系并提供多种当数据节点存储地址发生“冲突”时的处理方法而建立的一种数据结构。散列结构的查找等运算效率是很高的，本章中的散列函数、散列结构、散列表、散列法的基本概念和基本算法是重点，线性探测散列算法、链地址法散列算法和散列法的应用是难点。

第十章的学习重点是图的定义及性质，图的四种存储结构，图的两种遍历算法以及图的典型应用，包括最小生成树、最短路径、拓扑排序和关键路径等。通过本章学习，我掌握了图的概念和基本性质，图的存储结构（邻接矩阵和邻接表）及其基本算法、图的遍历及算法、图的最小生成树普利姆算法或者克鲁斯卡尔算法、图的最短路径迪杰斯特拉算法和弗洛伊德算法、有向无环图拓扑排序算法。了解了图的逆邻接表、十字链表、邻接多重表存储结构及其基本算法、关键路径求解算法，并能灵活运用图的不同的数据结构和遍历算法解决复杂的应用问题。

二．课程学习体会

在学习开始的时候，老师就明确提出它不是一种计算机语言，不会介绍C语言的变成语言，而是通过学习可以设计出良好的算法，高效地组织数据。一个程序无论采用何种语言，其基本算法思想不会改变。联系到在大一和大二上学期学习的C和C++语言，我深刻认识到了这一点。“软件开发好比写作文，计算机语言提供了许多华丽的辞藻，而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中，要熟悉对算法思想的一些描述手段，包括文字描述、图形描述和计算机语言描述等。因此，计算机语言基础是必须的，因为它提供了一种重要的算法思想描述手段——机器可识别的描述。

这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。

三．对《数据结构与算法》课程教学的建议

1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生上课积极思考，不会开小差。

2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。

数据结构与算法分析 篇6

数据挖掘 (Data Mining, DM) , 又称为数据捕捞、知识挖掘、知识发现、模式分析等, 是从大量的、不完全、包含噪声数据的、模糊的、随机的数据中发现知识 (模式) 的非平凡过程。该定义包含以下几层含义:数据是指一个有关事实的集合, 记录了事务有关方面的原始信息, 数据源必须是真实的、大量的、包含噪声的;模式给出了数据的特性或数据之间的关系, 是对数据包含的信息的更抽象描述, 发现的知识是可理解的、新颖的、潜在有用的、可解释的:不是要发现所有的知识, 通常是针对特定的需求来发现满足需要的知识。数据挖掘系统具有以下主要成分:数据库、数据仓库或其它信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式评估模块和图形用户界面。

2 关联分析算法

关联规则挖掘技术用于发现数据库中属性之间的有趣关联, 和传统的产生式规则不同, 关联规则可以有一个或者多个关联属性。同时一个规则的输出属性可以是另外一个的输入属性。

定义1:关联规则挖掘的数据集记为D (一般为事务数据库) , D={t1, t2, …tk…, tm, }, tk={i1, i2, …im, …iP}, tk (k=1, 2, …n) 称为事务。im={1, 2, …p}, 称为项目。

定义2:设I={il, i2, …im}是D中全体项目的集合, I中的任何子集X称为D中的项目集, x=k称为集合X为K项目集。设tk和X分别为D中的事务和项目集, 如果x⊆tk, 称事务tk包含项目集X。每一个事务都由一个唯一的标识符, 称为TID。

定义3:数据集D中包含项目集X的事务数称为项目集X的支持数, 记为σx。项目集X的支持度记为support (x) :

其中|D|是数据集D的事务数, 若support (x) 不小于用户支持的最小度 (minspport) , 则称X为频繁项目集, 简称频集, 否则称X为非频繁项目集, 简称非频集。

3 序列分析算法

序列模式与关联模式相仿, 不同的是它处理不同记录之间属性集的关联关系, 把数据之间的关联性与时间联系起来。为了发现序列模式, 不仅需要知道事件是否发生, 而且需要确定事件发生的时间。序列模式分析的侧重点在于分析数据间的前后序列关系。序列分析描述的问题是:在给定交易序列数据库中, 每个序列按照交易时间排列成一组交易集, 挖掘序列函数作用在这个交易序列数据库上, 返回出现的高频序列。将序列模式发现的问题分解成以下几个阶段:

⑴排序阶段。利用客户标识字作为主关键字及事务发生的时间做为次关键字将数据库进行排序, 该步骤也将原始的事务数据库转换成客户序列的数据库。

⑵大项目集阶段。在该阶段发现所有的大项目集L, 同时发现了所有的大1序列的集合, 并把大数据项集映射为一组相邻的整数, 每个大数据项对应一个整数。

⑶转换阶段。需要重复确定哪一个给定的大序列集被包含于顾客序列中, 要快速完成这种测试, 需要将每一个顾客序列转换成一个替换的代表。在一个已转换的客户序列中, 每一个事务被包含于该事务中的所有大项目集来替换。如果一个事务不包含任何大项目集, 在已转换的序列中就不应保留该事务。如果一个客户序列不包含任何大项目集, 则从已转换的数据库中去掉该序列, 但是, 总客户数的计数仍要对它计数。这个已转换的数据库称为Dt, 根据磁盘空间的大小, 可以生成这个己转换的数据库, 或者当在一个遍历期间读每一个客户序列时通过快速查找完成这个转换。

⑷序列阶段。利用大项目集, 发现所期望的序列。

⑸最大阶段。在大序列中发现最大的序列。

4 在入侵检测中应用数据挖掘技术的优点

数据挖掘技术能够从大量的审计数据和网络数据中抽取出能充分描述网络连接和主机会话特征的属性, 利用数据挖掘技术产生能够精确描述入侵行为和系统正常行为模式的规则, 并自动产生精确适用的检测模型。同时应用数据挖掘方法的检测系统不是基于预定义的检测模型, 自适应能力强, 可以有效地检测新型攻击以及己知攻击的变种, 也可以有效地剔除重复的攻击数据, 因而具有较低的虚警率, 减少漏报的发生。

参考文献

[1]李志云, 周国祥, 张丽萍.一种挖掘大型数据库的关联规则新算法[J].合肥工业大学学报 (自然科学版) .2010 (02) .

[2]Armananzas R, IInza, R.Santana, et al.A review of estimation of distribution algorithms in bioinformatics.Bio Data Min.2008.

数据结构与算法分析 篇7

【关键词】Apriori算法；关联规则；weka；数据挖掘

1.关联规则

关联规则是数据中蕴含的一类重要规律，对关联规则进行挖掘是数据挖掘中的一项根本任务，甚至可以说是数据库和数据挖掘领域中所发明并被广泛研究的最为重要的模型[1]。简言之，关联规则挖掘是发现大量数据中项集之间的关系或相关联系[2]。这些关系往往是隐藏的，从大量商务数据中发些这些有趣的关系对交叉销售、配送服务、贱卖分析等是有价值的，这样也有利于商务决策的制定。

关联规则挖掘的经典应用是购物篮数据分析，该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯，得出哪些商品频繁的被顾客同时购买，可以优化商品的分类陈列、改善商店的布局。以下是一个关联规则的简单例子：

计算机=>财务管理软件

[支持度=12%，置信度=60%]

这个规则表明12%的顾客同时购买电脑和财务管理软件，而在所有购买了电脑的顾客中有60%顾客也购买了财务管理软件。

2.关联规则相关概念

项目集合：I={i1，i2，i3，…，im}。

k-项集：项集中项目个数为k的项集。

事务集合：T=(t1，t2，t3，...，tm)。

关联规则表达模型：

XàY，其中X∈I，Y∈I，且X∩Y=ø。

这是一个蕴涵关系表达式，X称前件，Y称后件。

X覆盖ti：项集X是事务ti∈T的一个子集，则称ti包含X，也称X覆盖ti。

支持计数：是T中包含X的事务的数目，记做X.count。

支持度：规则XàY的支持度是T中包含X∪Y的事务的百分比，也可以看做是概率P(XUY)。支持度表示规则在事务集合T中使用的频繁程度。如果支持度的值太小，则表明这个规则可能是偶然发生的，研究它可能没什么价值。

置信度：规则XàY的置信度是既包含了X又包含了Y的事务的数量占所有包含了X的事务的百分比，也可看做是条件概率P(Y|X)。置信度决定了规则的可预测度，如果一条规则的置信度太低，那么从X就很难可靠地推断出Y。研究置信度太低的规则在实际应用中也不会有太大价值。

目标：关联规则挖掘就是要找出一个给定的事务T中所有满足用户指定的最小支持度(minsup)和最小置信度(mincof)的关联规则。如果一个关联规则满足最小支持度和最小置信度，那么就认为该关联规则是有意义的。

频繁项目集：一个支持度高于minsup的项集。

可信关联规则：置信度大于minconf的规则。

3.Apriori算法思想

Apriori算法是基于关联规则的经典挖掘算法，是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori算法分两步进行：

（1）生成所有频繁项目集。

（2）从频繁项目集中生成所有可信关联规则。

3.1 频繁项目集生成部分的算法

Apriori算法基于演绎原理（向下封闭属性）来高校的产生所有频繁项目集，其中向下封闭属性是指如果一个项集满足某个最小支持度要求，那么这个项集的任何非空子集必须都满足这个最小支持度。

Apriori使用一种逐层搜索的思想来生成频繁项目集。它采用多轮搜索的方法，每一轮搜索一遍整个数据集，并最终生成所有的频繁项目集。在第一轮搜索中，算法计算出所有只包含一个项目集的项集在事务集合中的支持度，并据此得到初始的单项目集（即1-频繁项目集）F1。随后的每一轮所搜都分为三步：

(1)将算法第(k-1)轮搜索生成的频繁项目集集合Fk-1作为种子集合产生候选的项集集合Ck，而Ck中的这些候选项集都是可能的频繁项目集，这个过程由candidate-gen()函数完成。

(2)随后算法对整个事务数据库进行扫描，计算Ck中的每个候选项集c的支持度，注意，在整个计算过程中并不需要将整个数据集加载入内存，事实上，在任何时候我们都只要在内存中保留一条事务记录，因此Apriori算法可以用于处理非常巨大的数据集。

(3)在本论搜索的最后，算法计算Ck中每个候选项集的支持度，并将符合最小支持度要求的候选项集加入Fk中。

算法最后输出的是所有频繁项目集的集合F。

3.2 候选项集集合Ck的生成函数

该函数分为两部分：合并和剪枝。

合并：将两个(k-1)-频繁项目集合并来产生一个可能的k-候选项集c。两个频繁项目集f1和f2的前k-2个项目都是相同的，只有最一个项目是不同的，随后，c被加入到候选项集集合Ck中。

剪枝：从合并步中得到的候选项集并不是最终的Ck。有一部分候选项集可以被剪枝。这一步判断c的所有(k-1)-子集是否都在Fk-1中。如果其中任何一个子集不在Fk-1中，则根据向下封闭原理，c必然不可能是频繁项目集，于是可将c从候选项集Ck中删除。

3.3 关联规则生成算法

给定一个频繁项目集f，如果一条关联规则的后件为a，那么所有以a的任意一个非空子集为后件的候选规则都是关联规则。基于此，得出了一个类似于频繁项目集生成的关联规则生成算法。首先，从频繁项目集f中生成只有一项的关联规则，然后利用所得到的关联规则和candidate-gen函数生成所有2-后件候选关联规则，依此类推。

3.4 缺点

在实践中，关联规则可能不像人们期望的那么有用。一个主要缺点是支持度、置信度框架常常产生过多的规则。另一个缺点是其中大部分规则是显而易见的。关联分析需要技巧，用严格的统计学知识处理规则增值将是有益的[4]。

3.5 提高Apriori的有效性

为提高Apriori算法的有效性，我们可以从以下几个方面考虑：

基于散列的方法：通过实验可以发现寻找频繁项集主要的计算是在生成频繁2-项集上，一种基于散列的技术可以用于压缩候选k-项集Ck(k>1)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，可以对每个事务产生所有的2-项集，将它们散列（即映射）到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阈值的2-项集不可能是频繁2-项集，因而应当由候选集中删除。这种基于散列的技术可以大大压缩要考察的k-项集，特别是利用这一技术来改进产生频繁2-项集。

事务压缩：减少用于未来扫描的事务集的大小。一个基本的原理就是不包含任何k-项集的事务不可能包含任何（k+1）-项集。从而就可以将这些事务在其后的考虑时加上标记或删除，因为为产生j-项集（j>k），扫描数据库时不再需要它们，这样在下一遍的扫描中就可以减少要进行扫描的事务集的个数。

基于划分的方法：为了降低算法对内存的需求同时提高并行性，基于划分的方法把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些频繁项集的支持度，这里每一个部分的大小和划分的数目确定，使得每一部分能够放入内存，这样每个阶段只需要被扫描一次，而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。此算法可以使高度并行的，可以把每一部分分配给某一个处理器生成频繁项集。

基于选样的方法：在给定数据的一个子集挖掘。选样的方法的基本思想是：选取给定数据库D的随机样本S，然后，在S而不是在D中搜索频繁项集，得到一些在整个数据库中可能成立的规则，然后对数据库剩余部分验证这个结果。用这种方法，牺牲了一些精度换取了有效性。样本S的大小这样选取，使得可以在内存搜索S中频繁项集；这样，总共只需要扫描一次S中的事务。由于搜索S中而不是D中的频繁项集，可能丢失一些全局频繁项集。为减少这种可能性，使用比最小支持度低的支持度阈值来找出局部于S的频繁项集（记作LS）。然后，数据库的其余部分用于计算LS中每个项集的实际频繁度。采用下列方法来确定是否所有的频繁项集都包含在LS中：如果LS实际包含了D中的所有频繁项集，只需要扫描一次D；否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须在频繁度不同的数据上运行时，选择方法特别合适。

动态项集计数：动态项集计数技术将数据库划分为标记开始点的块在扫描的不同点添加候选项集，不像Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种方法中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。

4.weka实现数据挖掘

Weka是一个功能全面的机器学习和数据挖掘应用程序平台[4]。Weka用Java编程，其中提供了优秀的学习算法，现在我们使用上面已经分析了的Apriori算法做一些机器学习工作。本文中，我们在windows xp下，使用的是weka3.6版以及Mysql5.0版本数据库，对深海油气田的数据库中的oilField表中的FieldLife和Total用Apriori进行分析。

4.1 weka连接数据库

在连接数据库之前我们需要下载安装了mysql-connector-java-3.1.14和Java的jdk，并将mysql-connector-java-3.1.14-bin.jar的路径配置到环境变量classpath中。接着打开weka的安装路径，例如：我的路径为：G:Program FilesWeka-3-6，找到weka.jar文件，将其解压到当前文件夹下。在解压后的文件夹中找到wekaexperiment这个目录下的DatabaseUtils.props与DatabaseUtils.props.mysql。然后使用UltraEdit打开这两个文件。在DatabaseUtils.props.mysql文件中，我们能看到以下配置项：

（1）驱动加载项

将jdbcDriver=后的内容mysql-connector-java-3.1.14-bin.jar里面的驱动，配置如下：

# JDBC driver(comma-separated list)

jdbcDriver=com.mysql.jdbc.Driver

数据库的URL，因为数据库装载在本地，所以配置为localhost# database URL

jdbcURL=jdbc:mysql://localhost:3306/database_name

（2）类型转换

找到# specific data types部分，在其下配置mysql中各种类型对应转换成weka的数据类型，我们使用从DatabaseUtils.props中的#mysql-conversion下的配置项。其余部分的配置不需要更改，保存文件。此时我们再将DatabaseUtils.props重命名为任意名字，将DatabaseUtils.props.mysql改成DatabaseUtils.props。

（3）将weka重新打包

在命令提示符下我们进入到刚解压的文件夹下，运行jar –cvf weka.jar *.*，此命令将当前目录下的任意文件压缩到weka.jar里，并且weka.jar文件就生成在当前目录下。

（4）覆盖原文件，运行weka

我们将重新打包的weka.jar拷贝到安装目录下（建议将原文件重命名），然后运行weka。

（5）点击Explorer-Open DB

在url栏的最后面修改要连接的数据库名，点击user输入用户名与密码，点击connect连接数据库。

4.2 weka进行关联规则挖掘

（1）导入数据

在Query栏输入sql语句，点execute执行，点ok将结果集导入weka。本文导入了深海油气田数据库中的oilField表中的FieldLife和Total：

FieldLife：油田寿命

Total：油田储量

（2）数据离散化

在weka的preprocess的filter中选择unsupervised/attribute/discretize。在choose右侧点击显示输入参数界面，将bin改成5。然后点击apply，这样就将fieldlife和total离散成了5类数据。

（3）度量标准

Weka中有几个类似的度量代替置信度来衡量规则的关联程度，它们分别是：

Lift：P(L，R)/(P(L)P(R))。Lift=1时表示L和R独立。这个数越大，越表明L和R存在在一个购物篮中不是偶然现象。

Leverage：P(L,R)-P(L)P(R)。它和Lift的含义相近。Leverage=0时L和R独立，Leverage越大L和R的关系越密切。

Conviction：P(L)P(!R)/P(L,!R)（!R表示R没有发生）。Conviction也是用来衡量L和R的独立性。从它和lift的关系（对R取反，代入Lift公式后求倒数）可以看出，我们也希望这个值越大越好。

值得注意的是，用Lift和Leverage作标准时，L和R是对称的，Confidence和Conviction则不然。

（4）参数设置

现在计划挖掘出支持度在10%到100%之间，并且lift值超过1.5且lift值排在前10位的那些关联规则。我们把"lowerBoundMinSupport"和"upperBoundMinSupport"分别设为0.1和1，"metricType"设为lift，"minMetric"设为1.5，"numRules"设为10。其他选项保持默认即可。"OK"之后在"Explorer"中点击"Start"开始运行算法，在右边窗口显示数据集摘要和挖掘结果。

（5）结果及分析

Apriori

=======

Minimum support:0.1(5 instances)

Minimum metric :1.5

Number of cycles performed:18

Generated sets of large itemsets:

Size of set of large itemsets L(1): 10

Size of set of large itemsets L(2):2

Best rules found:

1. FieldLife='(5.797968868E17-7.693786214E17]' 11 ==>

Total(TOE)='(7.87367106E17-inf)' 6 conf:(0.55) <

lift:(2.03)> lev:(0.06) [3] conv:(1.34)

2. Total(TOE)='(7.87367106E17-inf)' 14 ==>

FieldLife='(5.797968868E17-7.693786214E17]' 6 conf:(0.43) < lift:(2.03)> lev:(0.06) [3] conv:(1.23)

3. FieldLife='(3.902151522E17-5.797968868E17]' 13 ==>

Total(TOE)='(2.10176475E17-4.02573352E17]' 5 conf:(0.38) <

lift:(1.82)> lev:(0.04) [2] conv:(1.14)

4. Total(TOE)='(2.10176475E17-4.02573352E17]' 11 ==>

FieldLife='(3.902151522E17-5.797968868E17]' 5 conf:(0.45) <

lift:(1.82)> lev:(0.04) [2] conv:(1.18)

虽然设置的numRules为10，但是相关的关联项只有四项。对于挖掘出的每条规则，WEKA列出了它们关联程度的四项指标。第一条规则的意思是油田寿命在5.797968868E17-7.693786214E17范围内的油田的储量大于7.87367106E17的可信度为55%。第二条规则是说油田储量大于7.87367106E17的油田的寿命在5.797968868E17-7.693786214E17范围内的可信度为43%，依此类推。所以，总的来说油田寿命较长的油田，其储量最高的可能性最大。

参考文献

[1]Bing Lin.Web数据挖掘俞勇[M].薛贵荣,韩定一,译.北京:清华大学出版社.

[2]韩家炜.数据挖掘:概念与技术[M].机械工业出版社.

[3]Data Minng:Concepts and Techniques J.Han and M.Kamber Morgan Kaufman 2006 China Machine Press.

[4][印]K.P. Soman Shyam Diwakar V.Ajay.数据挖掘基础教程[M].范明,牛常勇,译.机械工业出版社.