高效数据挖掘算法

高效数据挖掘算法（共7篇）

高效数据挖掘算法 篇1

ASP是一种服务器端脚本编写环境, 可以用来创建和运行动态网页或Web应用程序。ASP网页可以包含HTML标记、普通文本、脚本命令以及COM组件等。利用ASP可以向网页中添加交互式内容 (如在线表单) , 也可以创建使用HTML网页作为用户界面的Web应用程序。结合ASP与各类数据库的链接, 可以使得资源在互联网上得到最大限度的共享。

随着数据量的增大, 传统的ASP显示数据技术已经逐渐略显疲态。速度慢, 浏览器停止响应等让用户访问效率大打折扣。ASP.NET的新算法可以很好的解决这一问题。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列, 并且这样的步骤和序列可以解决一类问题。

在Web端浏览数据的时候一般习惯使用的有两种分页算法, 一是传统的ado分页算法, 二是select top分页算法。对于小型数据表, 比如一两万的数据量的表, 本人倾向使用ado分页算法, 对于大型的数据表, 则建议采用select top分页算法了。

先来说说传统的ado分页算法。

这种算法, 使用起来简单容易, 很容易上手, 对于小心数据库来说是首选, 其执行效率很高, 数据库自带的游标功能进行翻页的时候也很方便。

这种ado游标的分页算法, 由于每次加载页面都要重新读取数据表的全部数据, 虽然游标的使用非常简单, 当数据表容量不大的情况下, 也是可以使用的;但当数据量非常大的情况下, 使用这种分页方法的效率无疑是极低的。

所以, 需要引入另外一种高效的select top分页算法。代码如下:

这是一种非常高效的分页算法。当数据表中的数据量成百上千万的时候, 上面的这种分页算法的响应时间是非常短的, 通常在几十毫秒之内。原理很简单, 就是每次分页, 我只取需要的几十条记录而已, 使用select top也正是基于这样的考虑。

上面的两个分页算法的例子中, flymorn都使用了时间字段time来进行order by排序, 因为在我接触的绝大多数系统中, 我们都需要把用户最近更新 (包括新添加的记录以及新修改过的老记录) 的内容展示在前面, 如果仅仅使用自动编号的id作为排序字段的话, 用户编辑过的老信息将无法展示在前面。这就是flymorn使用时间字段的原因了。

这里又涉及到聚合索引的问题了。默认情况下, 我们是以自动编号id作为主键, 并且用作聚合索引列, 如果上面的算法中, 使用这样的id列来排序的话, 效率会更高, 数据库响应的时间会更少;然而, 我提到了最近更新的内容需要展示在前面的问题, 所以, 我们必须使用时间字段来排序。因此, 为了更高的分页效率, 我们可以在数据库设计的时候, 把这个时间字段设计为聚合索引列。

通过这样的设计后, 整个分页效率就会得到非常高的提高了。

然而, 把这个时间字段作为聚合索引列, 存在又一个小问题。因为数据表在排列数据的时候, 是按照聚合索引列来进行物理排序的, 当用户添加数据的时候, 没有什么问题, 在数据表的末尾添加就行了;当用户编辑信息的时候, 数据库需要根据这个聚合索引列, 把刚编辑过的信息也提到表的末尾, 这里就需要耗费一定的时间了。就是说, 当我们以时间字段为聚合索引列的时候, 我们就需要在update数据的时候多耗费一点的时间。

然而, 综合比较而言, 本人认为, select top的高效分页算法的关键是要避免全表扫描, 尽量只获取需要的字段, 排序的字段最好是聚合索引列, 实践表明, 以聚合索引列来排序的sql语句的响应时间是最快的。这样处理之后, 对于sql server数据库来说, 即使上千万的数据量, 也不用怕分页算法失去响应了。

上面是以asp语言为例写的算法, 当然同样可以改造成其他的如ASP.NET, PHP语言所使用。为了更好地使用这样的分页代码, 也可以把上面的算法改写成存储过程

结束语

综上所述, ASP程序中的所采用的传统的ado分页算法以及select top分页算法各有特点, 关键在于数据库的大小而选择不同的分页算法。通过长期的运行时间证明, 这两种算法会有效的解决了高效浏览数据的难题。H

参考文献

[1]翟仲毅, 王雪松, 赵岭忠.基于ASP的程序切片[J].桂林电子科技大学学报, 2012, 32 (1) .

[2]崔海波.基于ASP.NET架构Web应用的安全性研究及应用[D].湖北大学, 2009.

[3]陈媛, 刘洁.在线算法验证系统的设计与实现[J].计算机工程与设计, 2008, 29 (5) .

[4]梁小利, 曹明刚, 程伟明.基于ASP.NET技术的数据处理研究[J].农业网络信息, 2008 (5) .

[5]原佳丽.网络多媒体教育资源数据库检索研究[D].山东师范大学, 2009.

高效数据挖掘算法 篇2

近年来,一些数据密集的应用已经广为人知,这些应用中数据的到达非常快速,并且会随时间而变,甚至可能是无法预测的,数据量看起来也是无界的,这样的应用例子有:金融应用、网络监测、安全、通讯数据管理、Web应用和制造和传感网络等。这些应用中,数据源会不断地产生出大量的数据,比如股票交易中,股票的交易数据会不断涌入,这种类型的数据应该被视为易逝的数据流[1]。

在数据流模型中,不支持对部分或全部数据的随机访问,而是以持续数据流的形式到达。概括地说,与传统存储关系模型不同,数据流主要有如下几个方面的特征:

实时性数据流中的数据元素是在线到达的,并要求对它的处理也是近乎实时的;

无序性系统无法控制将要处理的新到达的数据元素的顺序,不论是对一个数据流还是在多个数据流之间;

无穷性流式数据本身就意味着数据量的无限大,而系统存储的数据相对数据流大小则是非常有限的;

瞬时性流中的数据一旦经过处理,要么被丢弃,要么被归档存储。但被丢弃的数据元素可能需要再次被访问。

时序性数据流模型中查询是相对静止不变的,而数据是时刻变化的。

对持续数据流的查询和对传统数据库的查询类似,但数据流模型下的查询具有两个一般数据库系统所没有的特点:

第一个特点是存在一次性查询和持续查询的区别。一次性查询是根据某个时间点数据集的状态计算查询结果,再把结果返回给用户。传统的数据库管理系统(DBMS)查询通常都属于一次性查询。相反,持续查询是在数据流持续到达情况下的持续计算。在数据流模型下,持续查询比一次性查询更普遍,持续查询的答案是基于时间的,它反映了到目前为止已到达的数据流的情况。当新的数据到达时,持续查询的结果可以被存储或更新。有时候查询结果本身也可表现为持续的数据流。数据流模型下一次采用一次性查询还是持续查询,得根据具体应用环境确定。例如,需要多次执行,但每次执行只产生少量的查询结果的聚集查询适合存储数据库模型下的一次性查询;而连接查询往往只需执行一次,但执行一次需要很长时间,并且产生持续的、海量的查询结果,更适合使用数据流模型下的持续查询。

第二个特点是存在预定义查询和特定查询的区别。预定义查询是指在任何相关数据到达前就已经提交给数据流管理系统的一种查询。虽然一次性查询也可以被预先定义,但预定义查询通常是持续查询。与此相反,特定查询是指在数据流已经到达后的在线查询。由于特定查询不能提前预知,因此无法找出不同查询间的公共子表达式从而对查询进行优化;计算特定查询有时需要引用数据流中历史的数据元素,而这些数据很可能已经丢弃了。

此外,传统数据库查询的数据对象是相对稳定的,至少在查询进行的过程中被认为是不变的;而数据流查询的数据对象则不断的变化,持续增长。传统查询执行的过程中可以利用索引、排序或分类等技术对数据对象进行随机存取,查询执行的次数完全取决于应用系统;而数据流查询对于持续输入的数据流只能采取线性扫描算法,在数据对象过期之前进行有限次数的查询[2]。

由于数据流在容量上可能是无限的,为了计算数据流查询的精确结果,所需的存储器容量也会无限制地增长。传统的处理数据集的算法不适合于数据流应用系统,因为它不支持持续查询。由于存储器的容量是有限的,对无限的数据流查询就不可能总是产生精确的结果,用高质量的近似结果来替代准确结果往往是可以接受的。数据流问题的近似算法在近年来已成为一个富有成效的研究领域,这其中高效查询的优化处理就成为其中的一个热点。

1 优化处理算法模块设计

当前数据流系统中存在如下几个显著的特征[3]:

(1)DS系统中存在着大量的查询,系统应该尽快地找到关心该数据的查询。

(2)对单个查询而言最优的查询计划未必对全局来说是最优的。

(3)大量查询中存在着的共同特征,查询分组技术已经在传统DBMS和一些DSMS中被证明为一种非常有效的技术。

(4)数据流系统的执行效率不仅和输入数据的速率有关,还和系统中算子的数量有关,和实际引发的查询的数量有关。如何尽量减少系统中存在的活动算子的数量也是优化需要考虑的一个问题。

基于此,设计优化模块时提出的基本目标就是:充分利用查询之间的共同特征,尽可能在查询之间实现共享;另外,调度器采用高效的调度算法使得运行时的开销最小;追求系统整体性能的提高[4]。

优化处理算法模块的组成结构如图1所示。

图1中查询优化的输入是解析后的查询树。DSMS以访问内存数据为主,且查询的数量非常庞大,因此DSMS系统的主要优化方向是减少DSMS系统中实际引发的查询的数量。连接运算代价非常大,因此DSMS将连接运算向下压,先进行连接运算,多个查询共享一个连接运算,减少了实际引发的连接操作的数量。因此,优化处理模型中的优化首先对连接进行分组,以便较大程度地在不同的连接之间共享中间结果,节约了DSMS系统中最为宝贵的主存资源。完成连接分组后,再对谓词进行分组,将相同结构的谓词组织在一个表结构中,这样实际引发的查询的数量就会大大减少[5]。

2 基于连接谓词约束的等值连接分组算法

目前为止,虽然对连接查询提出了大量的优化算法,但是针对多查询优化的连接分组优化算法却未见应用于数据流系统中,这里实现的是基于连接谓词约束的等值连接分组算法。

2.1 连接分组算法设计

连接分组的输入条件是Get Table Link中的表列和Get Where中的等值连接条件。输出结果是网络节点。如果一个节点表示一个用户查询的话,则就称该节点为终端节点,在用户明确地将查询删除以前,终端节点是不能删除的,与之相对应的是非终端节点,非终端节点没有对应的用户查询,只是保存连接的中间结果,当连接计划改变后非终端节点可能会被删除。我们的连接分组连接结果都只是增加一个基本表(流),采用类似System R优化器的结构,也特别适合流水线处理,而对于数据流来说,所需的处理方式正是流水处理方式。

基于连接谓词约束的等值连接分组算法中,连接运算的优化分为两个阶段;第一阶段为增量分组阶段;每当一个新的查询提交后,系统查找当前存在的分组,检测是否存在一个分组与新提交的查询对应,如果存在则不用创建任何分组,只需要把这个分组的引用次数加一即可;如果不存在则需要创建新的分组与这个查询对应,新的分组可以利用已经存在的分组作为自己实现的一部分。

连接运算查询优化的第二阶段为动态重分组阶段;增量分组对新加入的查询进行分组而不对存在的查询进行重分组,尽管这种查询也是有效的,可扩展的,但是它可能导致只是局部的优化,已经存在的查询没有在新查询加入时为了适应新的全局优化要求而获得重新分组的机会。

随着增量分组的进行,系统中创建了很多分组,但是对当前存在的所有查询来说,有一些分组是不必要的,或者说是冗余的,冗余分组的计算消耗了系统很多资源,因此应该动态地把这些冗余分组删除,重新创建系统的分组图,使系统尽可能地达到全局最优。

2.2 连接分组算法实现

2.2.1 基本数据结构

所有的连接节点在逻辑上是一个有向无环图,图中的每个节点都代表一个分组计划中的一个连接表达式,该节点的结构为:

2.2.2算法表示

1)增量分组Increment Group

输入:int tableids,连接约束A(目前实现的是等值连接),inttime＿t。

输出:目的节点。

示意代码实现如下所示:

该算法的过程是:

Find MaxGroup:用于找到输入的连接对应的最大连接分组,输入是表列tableids和连接约束条件,以及时间窗口。连接的中间结果都是通过索引结构记录下来,因此,Find Max只需按照哈希表的长度由大到小地遍历哈希表即可,一旦找到就停止。由于,目前为止我们规定表的最大长度为10,因此这一步的开销并不是很大。另外,目前的连接约束条件只包含等值连接,只有符合约束的连接才会被用到。

Get Constraint:得到节点B的连接约束条件,B是A的一个子集。

Get Left Table Id:得到剩余表的列表。

Ramdom Join:利用约束条件Left Constraint在node和剩下的表列随机生成连接结果(也可以按照刷新频率由小到大的次序选择基本表)。

2)动态重分组Re Group

当系统经过一段时间时,查询有的是新加入的,有的则运行一段时间后便从系统中注销,因此这时候系统的状态不一定是最优的。因此,运行一段时间后就需要对系统进行重新分组。

输入:不同长度的哈希表。

输出:重新分组优化后的查询网络。

动态重分组中,首先按照长度从大到小的规律遍历哈希表,因为终端节点是不能删除的,因此首先检查每个终端节点,如果该终端节点的父母节点的孩子节点不是此终端节点,就用子节点代替这个孩子节点,代替的过程同时检查约束条件,只有符合约束条件才能替代。检查完终端节点后,再检查非终端节点,如果发现非终端节点的引用计数等于零,就将其删除,因为已经没有父母节点引用该节点的结果了。

由于动态重分组每次都遍历哈希表,因此代价很高,可以在系统空闲的时候进行这个操作。

3 谓词分组算法

谓词分组技术在很多系统中都有应用[5],将具有相同结构的过滤条件组织在一起(通常采用索引),当数据到来时,对该分组进行过滤操作,使用高效的组织手段,因此分组过滤操作执行效率可能会比较高(相对于单独执行时)。

Argus系统中谓词分组的输入是连接分组的结果网络节点和查询解析器解析的Wheres子句的内容,它将结构相似的谓词组织在一个称为常数表的结构中,当数据到来时查找该常数表,然后找到其目的节点。

下面我们讨论一下谓词的标记以及常数表的结构和基于常数表的连接算子。

3.1 谓词的标记

为了更简便,我们以下面的两个查询为例子来说明谓词的标记:

查询1:

我们比较一下这两个查询,两者的其它部分都相同,唯一不同的就是选择常数一个是pku,另外一个是nju。我们称这两个查询的标记相同。谓词的标记由下面几个部分生成:数据源,关系操作符。

3.2 常数表结构

常数表就是存放相同查询标记的查询常数值的一个结构。常数表的结构如表1所示。

常数表的第一列是常数值,第二列是引用次数,比如可能有两个查询的常数值是“云计算”,这个“云计算”的引用次数是3,第三列是目的算子的地址。

3.3 算法实现

在对数据流管理系统模型进行多查询优化时,预先对数据流进行连接,其实现如图2所示。

图2中每条数据流都有多个谓词分组,一个谓词分组对应一条或多条(有部分重复的)查询。再通过这些谓词分组生成查询计划,使整体代价较小,并且记录或删除查询不需要更改其它查询的谓词分组[6]。

算法的实现包括查询的更新和撤销两部分。算法的更新查询部分复杂度为O(n×m3),其中n为两流之间最大的不同连接因子数,m为数据流的查询连接数。而算法的撤销部分复杂度为O(m)。由于参与连接的数据流一般不会太多(少于10条),所以记录和撤消查询的算法复杂度是可接受的。

谓词分组算法的过程是:首先根据pre＿node和pre＿node的谓词找到对应的常数表,用哈希表保存常数表的地址,因此查找的速度通常会很快。如果没有对应的常数表,则创建一个常数表Create Table。然后在该表中查找是否具有取值等于过滤常数的一行,如果没有,则新生成一行,直接插入,并返回插入新行的目的网络节点的地址。如果找到对应的行,则将该行的引用计数值增1,然后返回改行对应的网络节点的地址。

3.4 常数表连接算子

由于有了常数表将所有结构相同的查询组织在一起,这样每次流A中的数据到来的时候,不用分别每次调用Filter算子,只要根据元组的相应列在常数表中查找就是了,将该查找工作用一个特定的算子Join Const实现。元组是以队列的形式存放的,和常数表的结构类似,该查找操作和连接操作很相似,我们称之为常数表连接算子Join Const。

4 实验及结果分析

查询优化的输出是查询网络,底层的调度器调度该网络上的算子节点。查询用测试用例如下所示:

4.1 实验参数说明

1)查询的总数N系统中注册的连续查询的总数量,是系统扩展性的一个重要量度。

2)算子的数量系统中存在的算子的数量。由于大量的查询可能会共享相同的算子,因此如果优化器能够实现这些计算之间的共享,算子的数量并不会和查询数量成正比。

3)数据源生成数据的速度当数据源的速度过高时可能会超出系统的处理能力,使得元组积累,内存消耗增加,从而性能急剧降低。因此采用了模拟的数据源,使数据生成速度随时可调。

4.2 优化前的算子数量对比优化后算子的数量

优化算法分别对连接和过滤操作进行分组,图3所示表示了改进前后算子数量的变化情况。

图3中由于结构相似,每个查询都会分解为数目相同的算子,因此未优化时算子的增长为直线。在采用优化方案后,由于大量的过滤算子共享同一个常数表连接算子,因此算子的数量增加很缓慢,当查询的数量足够多时(例如大于400),则算子呈直线上升,斜率约等于1,即只是增加每个查询的Map算子(投影共享),其他算子增加幅度相对减少。

另外,在很多的连接查询条件下,一条查询的优化可能会牵涉到其它许多的查询,迫使它们修正正在执行的查询计划。而查询计划的调整是非常复杂和耗资源的。这种情况在记录大量查询并频繁更新的数据流管理系统是不愿看到的[6]。如果记录查询的数量是n,本优化算法复杂度为O(lnn),而且对一条查询的优化对一条查询的优化基本不会牵涉到其它查询,性能也在可接受的范围内。

本文提出的高效查询优化处理算法的优化很简单,对一条查询的优化基本不会牵涉到其它查询。为考察该算法的性能,设计了一个实验模拟数据流的连接查询,实验结果与预期的基本吻合,有效地验证了算法的性能。本算法同样适用于硬件处理的查询计划生成,因硬件希望查询计划相对稳定。当然,它更适合应用于查询的更新频率很高的系统。

5 结语

详细讨论了用于高效查询的优化处理模型的算法。该算法的追求目标是尽量在查询之间的共享计算,优化算法采用的主要方法是分组,包括连接分组和谓词分组,分组方法是基于索引的。连接分组在大量的连接之间共享中间结果,一方面减少了内存需求,另一方面减少了连接的计算量。谓词分组将标记相同的谓词组织在一起,采用常数表将其存储起来,这样,多个过滤操作转化为数据源和常数表之间的连接操作,大大减少了系统引发的数量,并减少了系统的存储空间。

实验结果表明,本查询子系统在效率和资源节约上都取得了比较好的效果,初步可以应对网络环境中海量用户查询的挑战。

数据流产生的数据是有始无终的,而且很多环境下查询的数量是海量的,从而对硬件的资源要求很高,这就和我们有限的硬件资源产生了冲突,因此,数据化简技术也成为人们关注的焦点,数据化简技术的目标就是在查询准确性和硬件资源之间取得权衡,如果能够高效地将这些技术应用到DSMS中,会给DSMS提供更强大的效率和功能。

摘要：提出一种新颖的优化方案。方案采用了查询谓词分组和连接分组技术,在众多的查询之间实现了计算共享,较大地节约了系统中存在的算子的数量并提高了处理速度。连接分组首先检查系统当前有无可以利用的中间结果,在这个基础上进行后续连接操作。谓词分组将相同结构的谓词组织在一起,通过引入常数表的这个数据结构将这些查询组织在一起,并将多个过滤操作转化为连接操作,减少了过滤算子的数量。实验结果表明,该方法不仅节约了内存空间,而且还较好地提高了系统的运行效率。

关键词：数据流,滑动窗口,连接分组,常数表,谓词分组

参考文献

[1]左利云,马英杰.基于数据流处理模型的多查询优化算法[J].计算机工程与科学,2009,31(3):71-74

[2]陈磊松.面向高速网络的数据流处理模型研究[J].漳州师范学院学报:自然科学版,2006(2):31-33.

[3]谭博阅,刘宁.数据流中的近似查询技术[J].世界科技研究与发展,2006(4):57-60.

[4]Silberschatz A,等.数据库系统概念[M].杨冬青,唐世渭,等译.北京:机械工业出版社,2000.

[5]游凤荷,黄樟灿,李亮,等.具有物理模型数据处理的多目标优化及其算法[J].武汉大学学报:理学版,2001,47(1):57-60.

高效数据挖掘算法 篇3

目前, 无线数据传输中的压缩算法正朝着更高的压缩比, 更小的失真度, 更快的编解码速度, 更小的花费和资源浪费的方向不断努力。因此, 本文将通过提出一种高效的压缩算法进行无线传输策略设计, 并利用此策略进行航空发动机的试车数据压缩与无线传输测试。

1 基于压缩感知的无线传感网络压缩算法

与传统压缩基本理论不同, 压缩感知对信号的采样和压缩编码发生在同一步骤。具体压缩采样过程包括信号稀疏表示、编码测量和信息重构。

1.1 信号的稀疏表示

应用压缩感知的前提是被采样信号的稀疏性, 首先需要将信号在稀疏基中稀疏表示。小波变换不仅可以处理非平稳信号, 而且其变换系数能够反映块间相关信息。所以, 将选择小波基做为稀疏基。

1.2 测量矩阵的选取

测量矩阵满足约束等距性, 是保证信号精确重构的基本条件。因此, 可通过选择高斯随机矩阵作为测量矩阵φ来高概率保证Ψ和φ的不相干。

1.3 信号重构

本文将围绕贝叶斯压缩感知模型的求取参数后验概率的核心思想, 对贝叶斯算法进行改进。利用贝叶斯估计方法作为理论基础, 结合最大似然估计的方法进行压缩感知重构的研究。

在实际环境中, 噪声无处不在, 观测向量变成y=Φz+n。研究发现, 噪声的方差可当作常量, 而观测数据可看作高斯随机向量。对信号模型采用带有反馈的贝叶斯模型, 信号服从拉氏先验分布。利用最简单的先验分布, 设向量z服从独立同分布、均值为0的高斯分布, 该先验分布自身的超参数α=[α1, α2, …, αN]T服从超参数为a, b的伽马分布。为了简化模型, 令a=1, 2b=λ, 则根据概率论中的恒等式, 可以得到z的后验概率:

因此, 该后验概率分布服从均值为u, 方差∑为高斯分布N (u, Σ) 。基于以上分析, 因此可利用增广思想, 转换为完全数据的后验。

由贝叶斯公式可知,

因为

去掉与α无关的项可得:

利用最大似然估计思想, 对αi更新可得, 当qi2-pi>λ时,

否则αi=0。为方便计算pi和qi, 更新pi和qi,

2 基于压缩感知技术的航空发动机试车数据压缩与无线传输仿真测试

航空发动机试车过程中研究的参数主要包括发动机高低压转子转速、振动速度、滑油压力、滑油温度、燃油压力和燃气温度等。利用Matlab/Simulink的无线网络系统仿真工具Truetime, 进行基于压缩感知技术的航空发动机试车数据压缩与无线传输仿真测试。为确保无线网络传输效率, 经过实验对比, 设置丢包率为0.1, 传输速率为800kb/s不变, 网络时延为2ms, 并选择IEEE802.15.4 (Zig Bee) 协议。

以进气口总温传感器节点为例 (节点模型如图1所示) , 对无线数据传输进行测试分析。该节点通过仿真K型热电偶温度传感器感应进气道进气口总温, 输出前后的温度变化如图2所示。

经过观察对比, 传输前后的信号基本没有误差。因此, 本文提出的无线传感器网络无线传输策略中, 添加压缩感知技术是一种高效的网络传输策略, 网络传输效率高, 信号重构精度高, 可应用于实际的数据监测中。

3 结语

无线传感器网络中节点能量消耗快, 数据传输量往往也很大。本文针对无线传感器网络的网络传输特点提出了一种基于压缩感知的数据压缩方法, 并利用Matlab的无线网络系统仿真工具Truetime进行基于压缩感知的航空发动机试车数据压缩与无线传输仿真测试。经过测试, 本文提出的无线传输策略传输效率高, 网络节点能量消耗低, 信号重构精度高, 可应用于实际的大量数据传输和实时监测等应用中。

摘要：无线传感器网络已经成为数据传输的重要渠道。为了保证传输的高效性, 降低传感器节点能量的损耗, 通过结合无线传感器网络的传输性能, 实现了基于高效压缩算法的无线传输策略设计。根据此策略, 利用Matlab的无线网络系统仿真工具Truetime, 进行航空发动机的试车数据压缩与无线传输测试, 并取得了理想效果。

关键词：高效,压缩算法,无线传感器网络,航空发动机,试车数据

参考文献

[1]吴景志.对当今无线数据传输技术的研究[J].电子测试, 2013 (6) :153-154.

[2]冀晓骥, 杨钊.无线数据传输技术的思考与探讨[J].计算机光盘软件与应, 2012 (8) :90-96.

[3]林蔚, 韩红丽.无线传感器网络的数据压缩算法综述[J].小型微型计算机系统, 2012 (9) :2043-2048.

高效数据挖掘算法 篇4

省级教育考试部门是全省各类教育考试的主管部门, 具体负责普通高校招生考试、研究生招生考试、自学考试、成人高考、高中学业水平测试、各类证书考试的组织管理工作。多年来, 我省教育考试部门负责的考试类型、服务对象、考试模式、管理模式、录取模式以及服务模式日益复杂, 已经积累了海量的历史数据。如何从这些数据中找出其中隐藏的知识和规律, 有针对性地修改完善现有的政策和规定, 使成绩能够真实地反映学生的学习水平和学校的教学水平, 是一个迫切需要解决的问题。

本文针对教育考试的特点, 应用一种改进的关联规则挖掘算法, 对我省历年高考数据进行挖掘, 得到一些关联规则。分析发现, 挖掘得到的规则符合实际情形, 对后续考试政策或是规定的指定具有积极的意义。

1 关联规则简介

如何从海量的历史数据中获取有价值的知识是一项艰巨但非常有意义的任务。为了解决这一任务, 知识发现[1]、数据挖掘[2,3]成为研究的热点问题。数据挖掘是指从大量数据中, 使用某种技术手段, 提取出隐含的、先前未知的、对决策有潜在价值的知识[2,3]。通常, 知识可以用规则进行有效地表达。随着各种数据的海量累积, 数据挖掘已经逐步成为当前的研究热点问题, 起了学术界和工业界的广泛关注。各种面向数据挖掘的理论、方法和工具不断呈现, 以支持从大量数据中提取有价化的知识和模式。在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题, 它是由R.Agrawal等人于1993年提出的。关联规则的一个典型例子就是:“90%的客户在购买面包的同时也会购买牛奶”, 其直观意义为顾客在购买某些商品的时候有多大的倾向会购买另外一些商品[4]。关联规则挖掘用来发现大量数据中项之间有趣的关联或相关联系。Apriori算法是数据挖掘中被频繁使用的一个挖掘算法。然而, 传统的关联规则提取算法Apriori存在不足之处[5]:

首先, 在算法的初期所使用的候选数据项集过于庞大。会导致算法在初期的计算量太大, 效率降低。这一点在待挖掘数据量大时尤其成为突触问题, 甚至会导致算法无法运行, 成为Apriori算法进行实用化的一个重要瓶颈。

其次, 在Apriori算法频繁数据项集生成的过程中, 由于没有考虑到对原始数据的缩减, 为了判断某一候选数据项集是否频繁, 无论该事务是否含有该数据项集, 都必须遍历数据库中的所有事务, 阻碍了Apriori算法效率的提升。

再者, 在Apriori算法中仅采用唯一支持度, 而未考虑各个属性之间的差异性。

上述几个问题, 使得直接应用Apriori在海量数据集上提取关联规则成为困难。为此, 本文中将应用一种改进的Apriori算法来进行关联规则挖掘。

2 关联规则挖掘算法Apriori的改进

针对上述经典Apriori算法的不足, 颜雪松等[4]提出了一种改进的关联规则挖掘算法Apriori Tid。在Apriori Tid算法中, 寻找最大项目集的基本思路是:算法需要对数据集进行多步处理。第一步, 简单统计所有含一个元素项目集出现的频率, 并找出那些不小于最小支持度的项目集, 即一维频繁项目集。从第二步开始循环处理直到再没有频繁项目集生成。

从Apriori Tid算法寻找频繁项目集的思路中, 可以知道该算法的优点:即仅在第一次扫描时用事务数据库D计算候选频繁项目集的支持度, 其它各次扫描用其上一次扫描生成的候选事务数据库D'来计算候选频繁项目集的支持度。在最后的几次扫描中, D'的大小要远远小于D, 减少了I/0操作时间, 提高了算法的效率[4]。

算法简述如下[4]:

其中, D表示数据库;minsup表示给定的最小支持度;Answer表示所有频繁项目集。

3 实验结果与分析

高考作为一种选拔性考试, 旨在选拔适合高等学校培养要求的优秀新生。高考是一种导向性考试, 高考是中学教学的指挥棒, 起着对中学教学的引导作用, 这是高考的引导性质。高考成绩也是评价教育教学质量的科学依据。通过对近十年来高考数据进行数据挖掘, 找出其中隐藏的知识和规律, 有针对性地修改完善现有的政策和规定, 使高考成绩能够真实地反映学生的学习水平和学校的教学水平。

图1给出了本文使用上述改进的关联规则挖掘算法进行挖掘的流程图。

首先, 为了便于挖掘算法的运行, 我们需要对原始的数据进行预处理。数据预处理包含三个基本步骤:数据清理、数据归纳以及数据转换。

数据清理主要是对原始数据进行清理, 去掉异常数据, 如空值、不合理的值;还需要对原始数据进行简化, 删除与挖掘主题无关的数据信息。

数据归纳就是以数据库中关系表为基础, 查询收集任务相关数据, 形成任务相关基础表, 然后在基础表的基础上, 对各属性进行分析和泛化, 找出与决策规则有关联的属性, 构造出分类样本模型。此时的数据样本模型就是一个有效的、通过压缩或泛化了的数据集合。这样做的目的是设法减小数据规模, 使之只与属性值有关系, 而与原始的数据量无关, 为更有效地产生决策树提供方便。

数据转换是将数据变成统一的格式, 以适合数据挖掘的需要。

其次, 在完成上述的数据预处理后, 使用文[4]所述的该进关联规则挖掘算法进行挖掘。

完成挖掘后, 得到如下几条置信度较高的关联规则:

(1) 女生==>英语 (A)

(2) 男生==>数学or物理 (B)

(3) 农村and男生==>英语 (B)

(4) 城市and男生==>数学 (A)

(5) 边远地区==>英语 (C)

显然, 上述得到的规则是符合客观实际的。

4 结论

本文基于改进的Apriori关联规则挖掘算法, 对高考数据挖掘进行了初步尝试, 得到了一些有意义的关联规则。后续, 我们将在本文的基础上, 针对教育考试系统, 进一步研发出实用的关联规则挖掘应用系统, 从历史考试数据中找出隐藏的知识和规律, 以有助于修改完善现有的政策和规定。

摘要：从历史考试数据中提出有用的信息具有重要的意义。使用关联规则挖掘是有效的手段之一。然而, 传统的Apriori关联规则挖掘算法存在不足之处。为此, 本文应用一种改进的、基于Apriori的关联规则挖掘算法, 在高考考试数据上进行了尝试, 得出了有益的结果。为进一步构建针对教育考试的实际数据挖掘应用系统奠定了基础。

关键词：教育考试信息,关联规则,数据挖掘

参考文献

[1]杨炳儒, “知识发现系统框架及其理论体系的构造方法论, ”中国工程科学vol.13, pp.83-90, 2011.

[2]王光宏, 蒋平, “数据挖掘综述, ”同济大学学报 (自然科学版) , vol.32, pp.246-262, 2004.

[3]王爱平, 王占凤, 陶嗣干, 等, “数据挖掘中常用关联规则挖掘算法, ”计算机技术与发展, vol.20, pp.105-108, 2010.

[4]颜雪松, 蔡之华, “一种基于Apriori的高效关联规则挖掘算法的研究, ”计算机工程与应用, vol.38, pp.209-211, 2002.

数据挖掘算法综述 篇5

数据挖掘的任务是发现隐藏在数据中的模式,可以发现的模式分为两大类:描述型模式和预测型模式[2]。描述型模式是对当前数据中存在的事实做规范描述,刻画当前数据的一般特性;而预测型模式则是以时间为关键参数,对于时间序列型数据,根据其历史和当前的值预测未来的值。

关联模式是反映一个事件和其他事件之间依赖或关联的知识,其目的是为了生成部分数据的概要,寻找数据子集之间关联关系与数据之间的派生关系,即在同一事件中出现的不同项之间的相关性。如果两项或多项属性之间存在关联,那么就可以依据已知的属性值预测某一项的属性值。关联规则的挖掘可分为两步,首先是通过迭代识别所有的频繁项目集,然后再从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别和挖掘所有频繁项目集是关联规则挖掘算法的核心,也是计算量最大的部分[3]。

关联规则中最典型的是购物篮分析,在关联规则的分析中有助于发现交易数据库中不同商品之间的联系,找出顾客购买的行为模式。

分类就是通过构造一个分类函数,把具有某些特征的数据项划分到某个给定的类别上。分类由模型创建和模型使用两步组成,模型创建是指通过对训练数据集的学习来建立分类模型;模型使用是指使用分类模型对测试数据和新的数据进行分类。训练数据集中的数据带有类标号,通过训练集的训练,使得使用分类函数可以把标号未知的数据正确的分类到其相应的标号中[4]。

聚类就是将数据项分组成多个类或簇,类之间的数据差别应尽可能大,类内的数据差别应尽可能小,即为“最小化类间的相似性,最大化类内的相似性”原则。与分类模式不同的是,聚类中要划分的类别是未知的,是一种不依赖于预先定义的类和带类标号的训练数据集的非监督学习,无需背景知识,其中类的数量由系统按照某种性能指标自动确定。聚类分析作为数据挖掘中的一个模块,既可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息,概括出每一类的特点,又可以把注意力放在某一个特定的类上以作进一步的分析,还可以作为数据挖掘算法中其他分析算法的一个预处理步骤。

2 关联分析算法

常用的经典频繁项集挖掘算法有下面几种[5]。

2.1 Apriori算法

在关联分析中经典算法是R.Agrawal等人提出的Apriori算法,这是一种很有影响力的挖掘关联规则频繁项集的算法,探查逐级挖掘Apriori性质:频繁项集的所有非空子集都必须是频繁的。根据频繁k-项集,形成频繁(k+1)-项集候选,并扫描数据库1次,完成第k次迭代(k>1),找出完整的频繁(k+1)-项集Lk+1。

Apriori算法是最早用于解决关联规则问题的算法,也是目前数据挖掘领域里应用最广泛的算法之一。该算法的优点是简单易懂并且能够有效地产生所有关联规则,在频繁项目不多时表现出了明显优势;但是,当最小支持度低时,该算法会生成大量的候选频繁项集,可能会遇到组合爆炸的问题,另外,在判定每个候选项集支持度的时候,Apriori算法需要反复多次的遍历事务数据库,导致系统的输入输出代价过高。

2.2 Apriori-Tid算法

为了提高Apriori算法的有效性,目前已经提出了许多Apriori变形,旨在提高原算法的效率,Apriori-Tid算法就是一种Apriori变形算法。

Apriori-Tid算法仅在第1次扫描时用事务数据库D计算候选频繁项集的支持度,其它各次扫描用其上一次扫描生成的候选事务数据库D'来计算候选频繁项集的支持度。该做法可以减少对数据库的扫描次数,在一定情况下能迅速削减候选频繁项集。虽然Apriori-Tid算法进行了改进,但是仍然无法克服Apriori算法的固有缺陷,仍然存在下面的问题:可能产生大量的候选集;可能需要重复扫描数据库,通过模式匹配检查一个很大的候选集;无法对稀有信息进行分析。

3 分类算法

常用的分类算法有下面的几种[6]。

3.1 决策树方法

决策树是一种以实例为基础的归纳学习算法,在其树型结构中,每个结点表示对一个属性值的测试,其分支表示测试的结果,而树的叶结点表示类别,从决策树的根结点到叶结点的一条路径对应着一条合取规则,整个决策树对应着一组析取表达式规则。

决策树算法中最著名的是ID3和C4.5两个算法。ID3算法用信息论的知识作为基础,来计算具有最大信息增益的属性字段,然后建立一个决策树结点,再根据该属性字段的不同取值来建立分支。该方法描述简单且分类速度快,但是只对较小的数据集有效,而且抗噪性差。C4.5算法在继承ID3算法的优点的基础上对其进行了改进,用信息增益率代替信息增益来选择属性,同时在树的构造过程中对树进行剪枝避免了过拟合问题,还能够处理属性值缺少的样本,提高了抗噪能力。C4.5算法产生的分类规则仍然易于理解,准确率较高,但是在构造树的过程中,对数据集进行多次的顺序扫描和排序,导致算法的效率降低,而且C4.5仍然不适合大训练集数据。

3.2 人工神经网络

人工神经网络是多个神经元按一定规则连接构成的网络系统,通过模拟人类大脑的结构和功能完成对外部输入信息的动态响应,并将获取的知识存储在网络单元之间的连接权系数中,使网络具有很强的容错性和鲁棒性。

反向传播算法是人工神经网络中采用最多的训练方法。该算法通过对训练样本集的学习,将每次的处理结果与该样本已知类别进行比较,用所得的误差帮助完成学习,并且对每个训练样本动态的修改权值从而让网络的输出值与实际的类别的均方差最小。

神经网络的优点就是并行分布处理能力强,分类的准确度高,对噪声数据有较强的鲁棒性和容错能力,具备联想记忆的功能等。但是该方法获取的模式隐含在网络结构中,导致分类结果较难理解,网络的训练时间较长,不适于大数据量的学习。

3.3 贝叶斯分类

贝叶斯分类以统计学中的贝叶斯定理为理论基础,通过贝叶斯定理得到的后验概率来预测类成员关系的可能性,是一种具有最小错误率的概率分类方法。在计算过程中,如果假设所有变量都是条件独立的,则可以使用朴素贝叶斯分类方法,但所有变量都是条件独立的情况非常少。贝叶斯网络可以综合先验信息和样本信息,减少了定义全联合概率分布的概率数目,又避免了朴素贝叶斯分类器要求所有变量都是条件独立的不足,成为近年的主要研究方向。

4 结束语

数据挖掘是当今计算机学领域研究的一个主要热门课题,在各个领域都有广泛的应用,数据挖掘的算法对数据挖掘技术的实现起到关键的作用,也直接影响到能否把数据挖掘应用到具体的实践中。本文综合研究了数据挖掘的各种算法的优劣,为算法的改进和创新提供了基础。

参考文献

[1]王光宏,蒋平.数据挖掘综述[J].上海.同济大学学报,2004,32(2):246-252.

[2]Fayyad U.Knowledge Discovery and Data Mining towards a U-inifying Framework.KDD'96Proc.2nd Intl.Conf.on Knowled-ge Discovery&Data Mining,1996.

[3]邹志文,朱金伟.数据挖掘算法研究与综述[J].北京.计算机工程与设计,2005,26(9):2304-2307.

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

[5]R.Agrawal,T.Imielinski,A.N.Swamy.Mining association rules between sets of items in large databases[A].Proceedings of1993ACM SIGMOD International Conference on Managem-ent of Data,Washington D.C.USA,1993:207-216.

数据挖掘算法研究 篇6

1 关联规则挖掘算法

关联规则是通过用户给定支持度和置信度来寻找规则的过程[1]。基本思想包含2个过程:

(1)发现最大频繁项目集。通过用户给定的支持度,寻找数据集中支持度大于或等于给定支持度的所有项目集,即频繁项目集,再从频繁项目集中选出所有不被其他项目包含的频繁项目集,即最大频繁项目集。

(2)生成关联规则。通过用户给定的置信度,在发现最大频繁的项目集中生成置信度大于或等于给定置信度的关联规则。

思想中支持度是数据集D中包含项目集i1的事务在数据集D上的百分比,公式如下:

式中:t是数据集D上的一个事务。置信度是指包含i1和i2的事务数与包含i1的事务数的支持度比值,公式如下:

2 分类算法

分类是根据数据集的特点构造一个分类器,利用该分类器将数据集中的数据映射到给定类别中某一类的过程。主要分类算法有k-最邻近算法、决策树分类算法和贝叶斯分类算法。

2.1 k-最邻近算法

k-最邻近算法(kNN)是一种基于距离的分类算法,距离越近,相似性越大,距离越远,相似性越小[2]。算法的基本思想是为:计算每个分类样本到待分类元组的距离,即计算相似度,选取与待分类数据相似度最大的k个数据,将待分类元组划分到这k个数据分类属性最集中的类别中。

2.2 决策树算法

决策树算法采用自上而下的方法递归构造决策树,分两个步骤:决策树生成和决策树剪枝。典型的决策树算法有ID3算法、C4.5算法等[3]。

2.2.1 决策树生成算法

决策树生成算法采用信息增益来选择能使样本最好分类的属性,信息增益的计算如下:

有n个消息,概率分布为p=(p1,p2,…,pn),则该样本S的期望信息为:

对于给定的样本si∈S,其样本总数为Si,根据类别属性值将si划分为m个子集,每个子集中所包含的样本数分别为sij(1≤j≤m),其概率分布为p=(Si1/Si,Si2/Si,…,Sim/Si)。根据公式得样本si的期望信息为I(si)=I(p)。

样本集S的熵为:

样本S的信息增益为:

算法的基本思想:

(1)以代表训练样本的单个结点开始建树。

(2)如果样本S都属于同一个分类,则将该结点作为叶子结点。

(3)否则,利用公式计算各个属性的信息增益,比较计算所得的信息增益值,选取信息增益最大的属性作为根结点。

(4)递归划分选取的根结点,直到下面3个条件之一满足时结束:给定结点的所有样本属于同一分类;没有多余的属性可以用来进一步划分样本,此时采用多数表决法来创建叶节点;分支属性样本为空。

2.2.2 决策树剪枝算法

理想的决策树分为3种:叶结点数最少;叶子结点深度最小;叶结点数最少,且叶子结点的深度最小[4]。在决策树生成算法中没有考虑噪声等影响的因素,因此可能出现过度拟合现象,使分类预测性能降低,导致生成的决策树不尽理想。为了避免过度拟合,提出了决策树剪枝算法,该方法有预先剪枝和后剪枝2种。预先剪枝指在生成决策树的同时,决定是继续划分还是停止划分。预先剪枝的最大缺点是可能使树的生长过早停止,导致生成的决策树不完整,因此应用较少。后剪枝是一种先拟合后化简的方法,首先采用决策树生成算法对训练样本生成决策树,然后从树的叶子结点开始逐步向根的方向进行剪枝,具体的剪枝算法在本文不予以讨论。

2.3 贝叶斯分类

贝叶斯分类以贝叶斯定理为基础[5],贝叶斯定理是:H为某种假定,P(H)为先验概率,P(X|H)为H成立条件下X的概率,则后验概率P(H|X)为:

贝叶斯分类的原理是通过某对象的先验概率,利用贝叶斯定理计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。

算法的基本思想:

(1)根据训练样本计算分类属性的先验概率P(ci)。

(2)计算待分类数据每个非分类属性的条件概率P(x|ci)。

(3)由于各非分类属性可视为条件独立,故。

(4)利用式(6)计算ci的后验概率。

因为P(x)和P(ci)是常数,所以P(x|ci)最大,则后验概率最大,故将待分类数据划分到P(x|ci)最大的ci所在类别中。

3 聚类方法

聚类就是将数据对象分成多个簇,簇内有较高的相似性,而簇间差异很大。典型的聚类分析方法有划分方法和层次方法。

3.1 划分方法

划分方法依据数据点在几何空间的距离来判断个体间的相似度,距离越近就越相似,就越容易划分为一类。划分的原则是在同一个簇中的对象间有较高的相似性,而不同簇间差异很大。

3.1.1 k-平均算法

k-平均算法(k-means)是一种以簇内对象的均值为中心点的划分方法[6]。算法用欧氏距离来表示点到簇的距离:

算法的准则函数定义为:

算法基本思想:

(1)随机地选取k个对象,每个对象代表一个簇的初始中心。

(2)根据式(7)计算剩余对象到中心点的欧氏距离,将每个对象赋给与其欧氏距离最小的簇,即最相似的簇。

(3)重新选取每个簇的中心点,即重新计算簇内各点的平均值。

(4)计算平方误差和E,循环(1),(2),(3)直到准则函数E变化不明显为止。

3.1.2 PAM算法

PAM算法是一种以簇中位置最中心的对象为中心点的划分方法[7]。中心点被称为代表对象,其他对象被称为非代表对象。算法基本思想:

(1)随机地选取k个对象,每个对象代表一个簇的初始中心点。

(2)根据中心点计算每个非中心点y到中心点x的绝对距离|y-x|,将每个对象赋给与其绝对距离最小的簇,即最相似的簇。

(3)选择一个未被选过的中心点oi及oi所在簇中的一个未被选过的非中心点oh,计算oh代替oi的总代价Tcih,并记录在S中。

(4)如果S中有小于0的记录,则找出S最小,记录的非中心点,并用该非中心点代替被选择的中心点,重新组建k个划分的簇。

(5)如果S中所有的记录都大于等于0,则不再划分新的簇。

总代价为:。其中n为所有节点数;cjhi表示oj在oi被oh代替后所产生的代价。每一个oi被oh代替后,对于非中心点oj,有四种情况需要考虑(如图1~图4所示)。

(1)oj当前在oi所在簇内,但oh代替oi后,oj被划分到了中心点om所在的簇。此时。

(2)oj当前在oi所在簇内,但oh代替oi后,oj被重新划分到了中心点oh所在簇,此时cjhi=d(j,h)-d(j,i)。

(3)oj当前在中心点om所在簇内,但oh代替oi后,oj被重新划分到了中心点oh所在簇,此时cjhi=d(j,h)-d(j,m)。

(4)oj当前在中心点om所在簇内,但oh代替oi后,oj仍在中心点om所在簇,此时cjhi=0。

图中实线为oh代替oi前oj的所属关系,虚线为代替后oj的所属关系。

3.2 层次方法

层次方法是根据某种给定的条件对数据集进行层次的分解,有凝聚和分裂2种方式[8]。

凝聚采用自底向上的策略,先将每个对象作为独立的簇,然后合并各个簇,满足用户指定的终止条件时停止。凝聚方法有AGNES算法等。

分裂采用自顶向下的分类策略,先将所有对象作为一个簇,然后将该簇细分为越来越小的簇,满足用户指定的终止条件时停止。分裂方法有DIANA算法等。

3.2.1 AGNES算法

AGNES算法采用对象间的欧氏距离作为评价2个簇间距离的标准[9]。算法基本思想:

(1)将每个对象作为独立的初始簇。

(2)将欧氏距离最小的2个对象所在簇进行合并,组成一个新的簇。

(3)达到用户指定的簇的数目时终止。

3.2.2 DIANA算法

DIANA算法以簇的直径和平均相异度为划分层次的标准[10]。其中,簇的直径是指簇中任意两对象间的最大欧氏距离,平均相异度指平均距离:

式中:ni是Cj中包含属性的个数;nj是Cj中包含属性的个数。算法基本思想:

(1)将所有对象作为一个整体划分到同一个簇。

(2)在所有簇中挑选出簇直径最大的簇,并在该簇中选取一个与其他点平均相异度最大的点作为一个新簇,然后选取原簇中到新簇距离小于等于到原簇距离的点放入新簇中。

(3)循环(2)直到满足用户指定簇的数目为止。

4 几种算法的比较

关联规则方法主要用于对事物数据库进行数据挖掘,在商业领域使用得相对频繁一些。分类和聚类方法则用于对关系数据库进行数据挖掘,通过分析有属性描述的数据库元组来构造模型。

在实际应用过程中,不同方法有不同的优点和缺点。下面对本文提出几种算法的时间复杂度、使用范围、依赖条件、误差估计进行比较,如表1所示。

从表1可以看出,不同算法在不同应用上有各自的优缺点。如kNN算法时间复杂度最小,然而仅限于小数据集,对于数据集较大的情况,则可选用决策树和贝叶斯分类;k-平均算法对簇密集型数据有很高的效率。在实际应用中可以根据需要将几种算法结合,以达到更高的效率。

5 结 语

数据挖掘使信息处理技术从简单的数据存储转入更为高级的知识发现阶段,它正以一种全新的理念改变着人类信息管理方式。本文分析了3种数据挖掘算法的基本思想,并对不同算法进行了比较,指出了各算法的优缺点及使用范围,并展望了各算法对不同特征数据集的应用前景。

参考文献

[1]毕建新,张岐山.关联规则挖掘算法综述[J].中国工程科学,2005(15):77-79.

[2]潘丽芳,杨炳儒.基于簇的k最邻近(kNN)分类算法研究[J].计算机工程与设计,2009,30(18):52-54.

[3]刘佳,王新伟.一种改进的C4.5算法及实验分析[J].计算机应用与软件,2008,25(12):51-53.

[4]魏红宁.决策树剪枝方法比较[J].西南交通大学学报,2005(1):36-39.

[5]王国才.朴素贝叶斯分类器的研究与应用[D].重庆:重庆交通大学,2010.

[6]金薇,陈慧萍.基于分层聚类的k-means算法[J].河海大学常州分校学报,2007,21(1):25-27.

[7]TAN Pang-ning,STEINBACH M,KUMAR V.Introduc-tionto Data Mining[M].[S.l.]:Posts&TelecomPress,2006.

[8]刘坤朋.数据挖掘中聚类算法的研究[D].长沙:长沙理工大学,2010.

[9]刘畅,戴勃.基于AGNES算法的网格资源分析[J].辽宁工业大学学报,2009,29(1):62-63.

数据挖掘技术与关联规则挖掘算法 篇7

1 数据挖掘技术介绍

1.1 数据挖掘技术的概念

数据挖掘技术是一门包容性以及开放性较强的跨领域数据信息揭示学科, 这项技术能从大量含有噪声, 且模糊不确定的实际业务数据中进行计算, 在这些数据中对当前尚未发现, 或者没有被明确认知的具有一定价值的知识信息进行揭示。在进行数据挖掘中的业务数据形式不是单一固定的, 是复杂多样的, 所以数据挖掘得出的分析结果形式能以多种形式表现出来, 可以是具有较强逻辑性的数学表达式, 也可以是容易被一般用户理解的结果。且数据挖掘技术在科学研究、市场分析等领域均得到了广泛的应用。

1.2 数据挖掘技术分类

数据挖掘功能的分类主要是根据数据挖掘功能的不同进行的, 当前的数据挖掘技术主要有关联规则挖掘技术、分类挖掘技术、孤立点挖掘技术以及聚类挖掘技术等。本研究主要对关联规则挖掘算法进行详细探讨。

2 关联规则挖掘算法

2.1 关联规则种类介绍

关联规则按照不同的标准, 能用各种不同的方法分成不同类型。将关联规则分为挖掘频繁项集、闭频繁项集、被约束频繁项集、极大频繁项集, 是根据挖掘模式的完全性分类的;将关联规则分为多层和单层关联规则, 以及单位和多维关联规则是根据规则所涉及的数据进行分类的;将关联规则分为量化关联规则和挖掘布尔型规则是根据规则处理值类型分类的;将关联规则分为序列模式挖掘、频繁项集挖掘以及结构模式挖掘是根据俄关联规则挖掘模式进行分类的;将关联规则分为兴趣度约束、知识类型约束、数据约束, 是根据规则所挖掘的约束类型分类的。

2.2 关联规则挖掘算法分析

2.2.1 Apriori算法分析

关联规则算法中的挖掘完全频繁项集中, Apriori算法该类型中最具有应用价值, 影响力最大的算法。Apriori算法主要有两个步骤:

(1) 发现所有的频繁集;

(2) 生成强关联规则。

在Apriori算法中的第一步是最为重要的步骤, 该算法的核心思路是, 给定一个数据库, 在第一次数据库扫描中找出所有支持度大于等于最小支持度的项目组成频繁1—项集, 也就是L1, 1—项集C1, 由L1进行连接得到;接着进行第二次数据库扫描, 将C1中所有支持度大于等于最小支持度的项集组成频繁2—项集, 也就是L2, 候选2—项集C2由L2连接得到。以此类推, 直到找出最大项频繁集。即在进行第N次数据库扫描时, 找出CN-1中所有支持度大于等于最小支持度的项集组成频繁N—项集, 即是LN, N—项集CN要由LN连接得出, 一直到找不出新的选集为止。在这里还要用到Apriori算法性质, 即是频繁项集是频繁项集的子集, 非频繁项集是非频繁项集的超集。在Apriori算法中对数据库的扫描次数需要大于最大频繁项集的项数。

Apriori算法的操作具有两个明显的缺点。 (1) 该算法的使用需要对数据库进行多次扫描, 因此在读写操作上会花费很多的时间, 从而增加挖掘算法的时间成本, 这种成本的增加不可小觑, 因为它是有数据库存储数据的增加, 以几何级数上升的成本;

(2) Apriori算法会出现众多的候选频繁集, 频发集的产生量在每一步都很大, 这会使算法在广泛度和深入度上的适应性较差。

2.2.2 FP—growth算法分析

FP—growth算法是关联规则算法中属于深度优化的一种算法, 这种算法是深度优化算法中较新且具有较高成效的, 不同于Apriori算法本质的常用算法。FP¬—growth算法的基本基本步骤有两个:

(1) 先将频繁模式树FP—tree生成;

(2) 在生成的FP—tree频繁模式树中搜索频繁项集。

(1) 需要将项集关联信息保留住, 并采用一棵频繁模式树 (FP—tree) 用来容纳压缩后的数据库;

(2) 再将压缩后的FP—tree再分散为几个小的条件数据库, 再分别对这些数据库进行信息挖掘。FP—growth算法相较于Apriori算法, 只需要对数据库进行两次扫描, 不需要多次扫描, 大幅度减少了挖掘算法的时间成本;也不会出现大量的候选项集, 大幅度减少了频繁集的搜索空间。也就是说FP—growth算法能明显提高时间和空间效率。但是该算法也有缺点, 在对庞大且松散的数据库进行挖掘处理过程中, 不管是递归计算还是信息挖掘都需要占据大量的空间。

3 总结

综上所述, 本研究对对数据挖掘技术概念和分类进行了简单的介绍, 并对关联规则的种类进行了详细的分析, 对关联规则中常用的两种算法FP—growth算法和Apriori算法进行了详细的分析。两种算法都还存在各自需要改进缺点, 怎样在挖掘过程中提高挖掘效率, 满足人们对挖掘系统的需求, 这将是数据研究工作者仍然需要突破的重难点。

参考文献

[1]毛国君.数据挖掘技术与关联规则挖掘算法研究[D].北京:北京工业大学, 2015.

[2]张弛, 王本德, 李伟等.数据挖掘技术在水文预报中的应用及水文预报发展趋势研究[J].水文, 2015, 27 (02) :74-77, 85.

[3]魏陵博, 付先军.基于Aprio关联规则挖掘技术分析归心经中药与抗心律失常药理作用的相关因素[J].中西医结合心脑血管病杂志, 2014 (05) :517-518.

[4]付先军, 周永红, 王中琳等.基于频繁项集与关联规则挖掘技术探索王新陆临床用药及处方配伍规律的初步研究[J].中国中医药信息杂志, 2015, 17 (09) :92-94.