关联规则算法优化研究（共8篇）
关联规则算法优化研究 篇1
引言
在数据挖掘的知识模式中, 关联规则模式是比较重要的一种, 也是最活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。采用关联模型比较典型的例子是“啤酒和尿布”的故事。关联规则经典算法Aprior是由美国学者R.Agrawa1等人于1993年首先提出, 随即引起了广泛的关注。目前的大多数关联规则挖掘算法在这些情况下效率较低, 必须对关联规则挖掘算法作进一步的研究, 设计高效的算法。所以, 如何设计高效的更新、维护算法也是非常重要的研究课题。
1 关联规则算法简介
关联规则挖掘主要分为两个问题:a.找出事务数据库D中所有大于等于用户指定最小支持度的项目集 (itemset) 。具有最小支持度的项目集称为最大项目集, 简称大项集。项目集的支持度指包含该项目集的数目。b.利用最大项目集生成所需要的关联规则。对每一最大项目集A找到A的所有非空子集a, 如果比率support (A) /support (a) ≥minconfidence, 就生成关联规则a: (A-a) .support (A) /support (a) 即规则aÞ (A-a) 的置信度。
事实上, 由于第2步比较简单, 所以挖掘关联规则的关键就是寻找频繁集。
Apriori算法的中心思想是首先通过对事务数据库进行扫描, 找出支持度不小于最小支持度的所有项目, 即频繁I项集。接下来的工作是循环的, 每次循环分3步进行:a.连接, 对频繁k项集中的项进行连接, 前提条件是前k-1项必须相同。b.减枝, 在减枝这一步主要根据一个频繁项目集的任何一个子集都应该是频繁的这一思想对连接后的项目集进行筛选, 删除那些子集不是频繁集的项目集, 得出候选 (k+1项集。c.对数据库进行扫描, 计算候选项的支持度, 从候选集中删除支持度小于最小支持度的候选项, 进而得出频繁 (k+1) 项集。循环的终止条件是频繁k项集为空, 也就是说再也找不出相关联的项目了。
2 关联规则挖掘算法存在的缺陷
Apriori算法的频繁项集方法已被证明是在大型数据库中挖掘关联规则的有效工具, 但在实际应用中, 还存在不足之处。
2.1 关联规则有较大的冗余性。
2.2 由于该算法只用支持度和置信度这两
个标准来衡量关联规则, 在实际应用中常会产生一些没有价值的规则, 甚至是错误的结果。
2.3 关联规则挖掘算法的挖掘效率有待进一步提高。
通过前面算法的介绍, 我们知道Apriori算法在进行相应计算和操作时总是要对整个数据库进行扫描, 数据库有时候可达GB甚至TB数量级, 而数据库中有的事务是可以在扫描中略去的, 这样效率就会比较低。
3 关联规则算法优化
如何提高关联规则挖掘算法的效率一直是关联规则挖掘问题研究的热点。对关联规则问题的研究主要集中在以下几个方面:减少候选项目集的数量;减少对数据库的扫描次数;减少所需扫描的数据库的大小;为此, 特提出如下优化方案:
3.1 增加衡量标准
目前, 衡量和生成关联规则的标准主要有最小支持度和最小置信度两个。但仅用这两个标准来衡量关联规则显然是不够的, 由此提出增加如下标准:
3.1.1 兴趣度
一般来说, 如果挖掘出的关联规则具有新颖性———与人们以前的认识和观点不同, 或具有实用性———用户根据所挖掘出的关联规则可以辅助决策, 那么这样的关联规则就是用户感兴趣的规则, 或称关联规则是兴趣的。
兴趣度度量一条规则给用户带来的信息的多少, 不同的兴趣度的计算将具有不同的修剪效果。
在数值关联规则的挖掘中, 通过比较一条规则的预测支持率与实际支持率之间的差距来确定该规则的兴趣度。例如:对如下两条规则
(1)
(2)
如果己经得到了第一条规则, 则可以预测第二条规则具有2%左右的支持率和70%左右的置信度。因此第二条规则并没有带给用户更多的信息而可以被删除掉。
3.1.2 有效度
考虑数据库中X不出现而Y出现的可能性, 能较全面地描述X对Y的影响程度。将在数据库中X和Y同时出现的概率P (XY) 减去X不出现而Y出现时的概率P (XY) 定义为有效度, 取值在[0, 1]区间, 记为Validity。如果Validity<0, 则XÞY规则是无意义的。
如果在挖掘关联规则时, XÞY的有效度小于或等于零, 即使支持度和置信度均满足要求, 该规则仍是无用的。
所以, 将类似兴趣度、有效度这样的标准加入到关联规则的定义之中, 能够减少关联规则挖掘的盲目性, 从而提高算法的效率。
3.2 运用领域知识
领域知识就是在数据库中未明确表达, 而在该领域内达成共识的信息知识。
在数据准备与预处理阶段, 可以利用领域知识排除与关联规则发现无关的数据库中的记录或数据项, 有效地降低问题的维数, 缩减数据库的大小, 使设计出的挖掘算法更加有效。
在数据挖掘的产生假设阶段, 用领域知识排除假设中不必要的条件以优化假设, 减少从数据库发现有用信息的搜索时间。
在发现新模式阶段, 利用领域知识及对规则的关注程度或兴趣度无意义的候选关联规则进行修剪, 以提高挖掘效率。
但领域知识也应该认真使用以防阻碍一些有用规则的发现。
3.3 改进挖掘方式
关联规则挖掘的基本模型在数据集更新 (事务数的少量增减) 时, 需要对整个数据集重新进行挖掘。关联规则挖掘的增量算法对数据集中的事务增加时的关联规则挖掘进行了优化, 算法只需要找出新增数据集中的频繁项目集并对原数据集扫描一次就可以确定更新后的整个数据集中的新的频繁项目集。
Online关联规则挖掘是针对关联规则挖掘的基本模型的封闭性而作的改进。关联规则挖掘的基本模型的封闭性是指在寻找频繁项目集的过程中, 用户难以与挖掘算法交互。Online关联规则挖掘使用户在第一次扫描数据集的任何时候都可以根据需要调整最小支持率和最小置信度, 以挖掘出所需的关联规则, 该算法只需对数据集扫描两次。
4 结论
本文通过对Apriori算法的分析, 找到该算法存在的缺陷, 并提出算法改进的可能方向和途径。
参考文献
[1]Vipin Kumar, Mahesh V.Joshi, Eui-Hong Sam Han, etal.High Performance Data Mining[M].Lecture Notes in Computer Science.2003, 8:63-88页
[2]陈辉, 向伟忠, 单健.关联规则挖掘在教师教学评价系统中的应用[J].南华大学学报 (自然科学版) Vol.19.No.1
[3]王铁军.数据挖掘技术在教学评价系统中的应用[J].MODERN COMPUTER.2005, 3.
关联规则算法探讨 篇2
摘要:文章对关联规则的发展进行了简单的介绍,分析了关联规则的经典算法,介绍进了一种新的关联规则算法,并对这三种算法在挖掘关联规则的特点进行了对比分析,最后对关联规则以后的发展进行了总结。
关键词:数据挖掘;关联规则;算法;探讨
中图分类号:TP311.13 文献标识码:A文章编号:1006-8937(2009)20-0091-02
1发展历史
随着信息技术的迅猛发展,许多领域搜集、积累了大量的数据,迫切需要一种新技术从海量的数据中自动、高效地提取所需的有用知识。对这些海量数据进行研究的过程中,数据挖掘技术受到越来越多的关注。我们可以使用数据挖掘技术从海量数据中发掘其中存在的潜在规律。并将这些规律进行总结,用于今后的决策。采用关联规则在大型事务数据库中进行数据挖掘是数据挖掘领域的一个重要研究内容。从大量数据中发现项之间有趣的、隐藏的关联和相关联系正是关联规则目的。
关联规则技术在不断成熟和发展,应用范围不断扩大,由最初的购物篮分析发展到计算机入侵检测、搜索引擎、警务预警、交通事故、保险业、金融业、农业专家系统、教学评估、股票分析等领域。在理论研究方面,由最简单的单维、单层、布尔关联规则逐渐向复杂形式扩展,由频繁模式挖掘不断扩展到闭合模式挖掘、扩展型关联规则、最大模式挖掘、衍生型关联规则、关联规则隐私保护、挖掘后处理、增量挖掘、规则主观兴趣度度量、相关模式、数据流等多种类型数据上的关联规则挖掘等。
2相关概念
设项的集合I = { i l ,i 2 ,…,i m },D为数据库事务集合,每个事务T是一个项目子集,似的TI。每个事务由事务标识符TID标识。若有XI, XT,则称T包含X;如果X有k个元素,称X为k-项集。
关联规则的逻辑蕴含式为:X Y[s,c] ,其中XI ,YI 且 XY=。规则XY在事务集D中成立,并且具有支s和置信度c。支持s是指事务集XY含的百分比:support(XY)=P(XY),置信度c是指D中包含X的事务同时也包含Y的百分比confidence(XY)=P(Y|X)。
对于一个事务集D,挖掘关联规则的问题就是找出支持度和可信度分别大于用户给定的最小支持度阀值(minsupp)和最小置信度(minconf)阀值的关联规则,这种规则成为强关联规则。
3经典算法
基于频繁集的方法是关联规则挖掘的主要方法,Aproiri算法是基于频繁集的算法最主要算法之一,在数据挖掘中具有里程碑的作用,但是Apriori算法本身存在着一些固有的无法克服的缺陷,而后出现的基于频繁集的另外一种算法FP-gorwth算法能较好地解决APriori算法存在的一些问题。下面分别介绍两种经典的算法。
3.1产生候选频繁项集
Apriori算法是Rabesh Agrawal等人在1994年提出的,该算法采用了一种宽度优先、逐层搜索的迭代方法:首先产生所有的频繁1-项集,然后在此基础上依次产生频繁2-项集、频繁3-项集……,直到频繁k-项集为空集。在此过程中,产生每个频繁项集都需要扫描一次数据库,通过对数据库D的多趟扫描来发现所有的频繁项目集。
设Ck表示候选k-项集,Lk表示Ck中出现频率大于或等于最小支持数的k-项集,即k-频繁集或者是k-大项集。该算法的基本过程如下。
①首先计算所有的C1;
②扫描数据库,删除其中的非频繁子集,生成L1(1-频繁项集);
③将L1与自己连接生成C2(候选2-项集);
④扫描数据库,删除C2中的非频繁子集,生成L2(2-频繁项集);
⑤依此类推,通过Lk-1((k-1)-频繁项集)与自己连接生成Ck(候选k-项集),然后扫描数据库,生成Lk(频繁k-项集),直到不再有产生频繁项集为止。
Apriori算法虽然能较有效地产生关联规则,同时也存在着不少缺点:
①数据库太大时对候选项集的支持度计算非常繁琐,当支持度、置信度阀值设置太低会产生过多的规则,致使用户难易人为地对这些规则进行出区分和判断。
②要对数据进行多次扫描,需要很大的I/O负载,算法的效率不高。
③当数据库D很大时,会产生庞大的候选集,导致算法的耗时太大。
3.2不产生候选频繁项集
FP-Tree算法由 Jiawei Han提出。它的基本思路是将数据集中的重要信息压缩在一个称为频繁模式树(FP-Tree)的数据结构中, 然后基于FP-Tree生成数据集中所有的频繁项集。该算法对所有频繁项集的挖掘分为以下两步:构造频繁模式树FP-Tree。在 FP-Tree中,每个结点有4个域组成结点名称、结点计数、结点链及父结点指针。另外,为方便树遍历,创建一个频繁项头表,它由两个域组成:项目名称及结点链头,其中结点链头指向 FP-Tree中与之名称相同的第一个结点;调用FP-Growth挖掘出所有频繁项集,具体算法描述如下。
①生成频繁模式树,首先,扫描事务数据库 D一次,产生频繁1-项集,并把它们按降序排列,放入L表中。其次,创建 FP-Tree的根结点,以“null”标记。再一次扫描D,对于D中的每个事务按 L中的次序排序,并对每个事务创建一个分枝。
②挖掘频繁项集,首先,从FP-tree的头表开始, 按照每个频繁项集的链接遍历,列出能够到达此项的所有前缀路径,得到条件模式基。其次,用条件模式基构造对应的条件FP-tree。第三,递归挖掘条件FP-tree,直到结果FP-tree为空,或者只含有唯一的一个路径(此路径上的每个子路径对应的项集都是频繁项集)。
FP-Growth算法是一种基于模式增长的频繁模式挖掘算法,采用了“分而治之”策略,它能够在不产生候选频繁项集的情况下挖掘全部频繁项集,直接将数据库压缩成一个频繁模式树FP-tree,只需要两次扫描数据库,相对于Apriori算法效率快一个数量级。该算法虽然可以避免产生候选项目集,但在挖掘过程,当存在大量大项集,并且如果得到的频繁模式树FP-tree分支很多、分支长度很长时,该算法将需要构造出太多的条件FP-tree,这不仅费时且要占用大量存储空间,导致挖掘效率不高。另外构造FP-tree是自顶而下构造的,而生成条件模式基是自底而上生成的,在挖掘时需要反复地进行搜索FP-tree,存储结构采用双向链表,则会进一步增加内存的开销。
4一种新的关联规则算法
目前有许多新的关联规则算法出现,但大都是根据Apriori算法的框架结构来改进的。文章将介绍一种新的基于幂集的挖掘算法PS (Power Set),该算法将完全脱离Apriori算法的框架结构。
4.1算法的相关概念
①幂集合PS(A)定义:对于任意一个非空集合A,它的幂集合PS( A) 就是由A的全部子集组成的集合。例如非空集合A:{a,b,c},则它的幂集合PS(A)={{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。
②对事务数据库D,I={il,i2……im},XI,在D中包含X的事务数就称为D中的频度,也可简称为X的频度。
③集合A={a1,a2,a3,……,ai}中元素的个数称为该集合A的长度Length(A)。
4.2算法描述
PS算法的主要步骤为:
①首先扫描事务数据库D,并对每一条事务记录本身进行拆解,例如,XYZ为一事务记录,可以拆分为XY、XZ、YZ、X、Y、Z、XYZ七个子集。
②接着得到子集依据集合长度Length(A)存放在不同的结果表中,并做频度计数,如果结果表已存在对应的子集,则将该集合的计数值加1,如果不存在,则将该集合加入其中,并设置初始值为1。这样此事务记录的拆解才算结束。当事务数据库被扫描一次以后,所有的事务记录都拆解完毕。
③最后根据用户输入的最小支持度和最小置信度阀值来产生频繁项目集和关联规则。
该算法通过对数据库的一次扫描就能挖掘所有的频繁集,大大降低了I/O存取的时间;而且算法运算简单且速度较快,用户可以任意改变最小支持度阀值使算法弹性增大,执行的效率稳定,不受支持度的变动的影响,在增量式挖掘中可以运用该算法而不需要对数据库进行前期的处理。算法在新增记录时比Apriori算法节省许多重复搜索记录的时间,但是该算法在存储的空间上会花费比Apriori算法大上数倍的存储空间,所以PS算法是一种以存储空间换取挖掘时间的方式。
5结 语
文章对关联规则的发展做了简单的介绍,对关联规则的两个经典算法进行了分析并介绍了一种完全脱离Apriori算法的框架结构的新算法。重点分析了三种算法的特点,得出对于将来的挖掘关联规则的改进和研究重点仍会在减少I/O操作、减少存储空间、产生更少的候选项集和如何更有效地挖掘数据中更实用的关联规则上。
参考文献:
[1] 王琳莎,林国龙,杨斌.新的关联规则算法在物流行业中的应用[J].物流工程与管理,2009,(3):41-43.
[2] 方风波.关联规则挖掘技术发展及应用[J].中小企业科技,2007,(6):108-109.
[3] 朱绍文,王泉德等.关联规则挖掘技术及发展动向[J].计算机工程,2000,(9):4-6.
[4] 白利果,乔钢柱,曾建潮.关联规则挖掘在农业产值分析中的应用[J].太原科技大学学报,2008,(10):335-338.
一种优化的关联规则增量更新算法 篇3
在数据挖掘中, 关联规则的挖掘是一个重要的研究课题。关联规则是R.Agrawal等人于1993年提出的。它最典型的应用是在销售事务数据库中发现新的有用信息。例如:90%的顾客在购买商品A和B的同时也购买了商品C和D。因此找出类似的规则, 就可以制定出更好的销售策略。此外, 关联规则也应用到金融、保险等行业。由于这些应用数据库中的数据都是极其庞大的, 而且是经常更新变化的, 因此迫切需要高效的算法来更新、维护已经挖掘出的规则。
目前大多数的关联规则增量式更新算法都是以Apriori算法为核心进行的改进和优化。如FUP[1]、UWEP[2]、PFUP[3]算法等。本文主要考虑在最小支持度和最小置信度不变的情况下, 数据库D被添加时, 关联规则的更新、维护问题。在借鉴上述算法思想的基础上提出了一种改进的关联规则更新算法MIFUP。
1关联规则的增量更新算法
给定事务数据库D和新的事务数据集d。本文考虑的主要问题是假定在最小支持度不变化的情况下, 事务数据库D中增加了新的事务数据集d后, 最新事务数据库D∪d中关联规则的高效更新问题。针对这个问题, D.W.Cheng等人提出了经典的FUP算法。
FUP的基本思想是:对于任何一个k项集, 若它在D和d中都是频繁项集, 那么它在D∪d中同样是频繁项集;若它在D和d中都是非频繁项集, 那么它在D∪d中同样是非频繁项集;若它仅在D (d) 中是频繁项集, 则其支持计数应该加上d (D) 中的支持计数来决定它在D∪d中是否为频繁项集。由于FUP算法产生了大量的候选项集, 扫描数据库次数多, 因此它具有很高的时间复杂度。
1999年, N F Ayan等人提出了UWEP算法。UWEP算法利用非频繁项集的父集一定是非频繁项集这个定理的性质, 对于候选k项集不必等到第k次遍历, 就尽可能早地剪切掉非频繁k项集, 有效地减少了候选项集的数量, 但是该算法对于预剪切的策略考虑得还不是很完善。
后来有人在FUP和UWEP算法的基础上提出了PFUP算法, 该算法借鉴强频繁项集概念, 利用强频繁项集连接生成小数量的候选项集, 采用了预剪枝策略减少了对数据库的扫描次数。它将候选项集数量减到最小, 通过预剪枝策略减少扫描数据库的次数, 但是当数据库规模大时, PFUP算法仍然耗费大量的时间。
除了以上算法, 还有许多新的算法, 如SFUA[4]、HIUP[5]、EFUP[6]、IFUP[7]等, 在减少扫描数据库次数和候选项集数量上做出了改进。
针对现有的关联规则增量更新算法上存在的缺陷, 本文提出了一种优化的关联规则更新MIFUP算法, 采取了优化策略, 更大程度地减少扫描数据库的次数, 不仅从理论上提高了算法执行的效率, 而且将以实验的形式来加以验证。
2关联规则的更新MIFUP算法
2.1优化策略
针对现有算法的不足, 采取如下两个优化策略。
优化策略1 在关联规则优化中, 事务压缩原理[8]是一个重要的方面, 它减少了扫描数据库的次数。因此MIFUP算法借鉴了事务压缩的思想。事务压缩算法是Agrawal等提出的压缩进一步迭代扫描事务数的方法。因为不包含任何k项集的事务, 不可能包含任何 (k+1) 项集, 所以可对这些事务加上删除标志, 扫描数据库时不再考虑。若一个事务不包含任何k项集, 则该事务包含的项集必定小于k, 同时必小于k+1, 则该事务不会包含在任何 (k+2) 项集中。因此在下一次扫描事务数据库, 先把该事务删除以提高扫描效率。
本文中引入数组来存放事务中项集的个数。FlagD存放原数据库D的每条事务项集个数, Flagd存放新数据库d的每条事务项集个数。由于不包含k-项集的事务不可能包含任何 (k+1) -项集。则计算频繁k-项集在原数据库中的支持度, 如果相对应的FlagD中的数据小于k, 则不需要扫描该对应下标的事务, 直接扫描下一条事务。如果相对应的FlagD中的数据大于k, 则扫描对应下标的事务, 进行模式匹配, 得到该项集的支持度。扫描频繁k-项集在新数据库d中的支持度也是一样的情况。
优化策略2 用numD1数组保存D的1-非频繁项集在D中出现的次数, 如果X∈Ld1且XLD1, 扫描numD1数组可以得到X的出现次数。因此只需要扫描一次数据库D。在得到数据库d的频繁项集时, 同时用numd1数组保存d中的1-非频繁项集在d中出现的次数。如果X∈LD1且XLd1, 扫描numd1数组可以得到X的出现次数。那么在生成D的1-强频繁项集时, 不需要扫描数据库d。
2.2 算法思想
新增数据库d中k-项集X的频繁性主要有以下3种情况:
(1) X在d和D中均频繁;
(2) X在d中频繁但在D中非频繁;
(3) X在d中非频繁但在D中频繁。
当X属于⑴情况, 则X是D∪d的频繁项集。但是当X属于⑵或⑶时, X需要扫描D或d来判断X在D∪d是否频繁。在PFUP算法, 必须扫描整个数据库D或d。但是在MIFUP算法中, 如果FlagD或Flagd中的数据小于k, 则不需要扫描该对应下标的事务。因此减少了扫描的事务数, 减少了扫描数据库的时间。
在生成D∪d中的1-频繁项集时, 如果X属于⑵情况, PFUP算法扫描数据库D的次数是项集X的个数, 但是MIFUP算法只需要扫描numD1, 可以得到X在数据库D的出现次数;如果X属于⑶情况, PFUP算法扫描数据库d的次数也是项集X的个数, 而MIFUP算法只需要扫描numd1, 可以得到X在数据库d的出现次数。
2.3算法描述
算法:关联规则增量式更新算法MIFUP。
输入:设原数据库为D, 新增数据库为d, 最小支持度为s, LD为原数据库D的频繁项目集合, Ld为新数据库d的频繁项目集合, LDk为原数据库D的k-频繁项目集合, Ldk为新数据库d的k-频繁项目集合, FLd为d的强频繁项目的集合, FLD为D的强频繁项目的集合, FLDd为D∪d的强频繁项目的集合。
输出:D∪d中的强频繁项集FLDd。
首先求出数据库D、d的1-阶强频繁项集FLD1 、FLd1
3算法实现和比较
通过优化策略1, MIFUP算法减少了数据库的事务数;通过优化策略2, 在生成1-频繁项集时, MIFUP算法只需要扫描一次数据库D或d。因此从理论上来说, MIFUP的效率远大于FUP和PFUP算法。为了进一步比较这两个算法, 下面给出了实际运算比较, 实际运行的硬件环境:CPU是intel-p4-2.4G, 内存是DDR-1.0G;软件环境:操作系统为Windows 2000 Server, 编程语言是Matlab 7.1。原数据集D是以布尔矩阵的形式存放, 有9个项目的10000条记录的, 新数据集是500 (约8.5k) 条记录。算法FUP、PFUP、MIFUP执行结果比较如图1所示。
由图1可知, 总体而言MIFUP算法的执行时间小于PFUP算法和FUP算法。当支持度小于或等于0.2时, MIFUP和PFUP算法执行时间相差比较大, 因此当频繁项集数量较大的时候, MIFUP算法的效果更加明显, 且MIFUP算法更适用于稀疏数据库。当支持度在[0.2, 0.4]变化时, 由于满足该支持度的频繁项集数量不大, 因此MIFUP算法与PFUP算法执行速度大致相同。在数据库的关联规则增量更新方面, MIFUP算法具有更小的时间复杂度。
4结束语
本文在借鉴其他算法的基础上, 提出了一种优化的关联规则更新算法MIFUP。与其他算法相比, MIFUP算法减少了扫描数据库D或d的次数, 极大地减小了时间复杂度。本文不仅在理论上证明算法的正确性, 而且还通过实验加以验证。但MIFUP算法只适用于数据库增加的情况, 将来研究重点是拓展MIFUP算法, 使之能面向增加和删除数据库的情况。
摘要：针对PFUP算法存在扫描多次数据库这个瓶颈问题, 提出一种优化的关联规则增量更新算法MIFUP (Mixed Improve Fast Updating) 。该算法提出了两种优化策略:借鉴事务压缩原理和用数组存放一阶非频繁项集个数。实验仿真说明, MIFUP算法效率明显优于PFUP算法。
关键词：FUP算法,UWEP算法,PFUP算法,MIFUP算法
参考文献
[1]Cheung D W, Han J, Ng VT, et al.Maintenance of discovered association rules in large databases:An incremental updating technique[C]//New Orleans, Louisiana:The12th Int l Conf on Data Engineering, 1996.
[2]Ayan N F, et al.An Efficient Algorithm To Updating Large Itemsets with Early Pruning[C]//San Diego, California, USA:proc of the5th Int.Conf.on Knowledge Discovery and Data Mining (KDD’99) , 1999.
[3]黄德才, 张良燕, 龚卫华, 等.一种改进的关联规则增量式更新算法[J].计算机工程.
[4]陈劲松, 施小英.一种关联规则增量更新算法[J].计算机工程, 2002, 27 (7) :106-107.
[5]孙士潮, 刘寒冰, 吉立新.一种高效的关联规则增量式更新算法[J].计算机应用与软件, 2007, 24 (10) :169-183.
[6]徐文拴, 辛运帏.一种改进的关联规则维护算法[J].计算机工程与应用, 2006, 18 (3) :178-180.
[7]朱红蕾, 李明.一种高效维护关联规则的增量算法[J].计算机应用研究, 2004, 21 (9) :107-109.
数据挖掘关联规则算法研究 篇4
Web服务器的日志文件通常都是简单的文本文件, 在长期的历史时期只是作为服务器管理员的参考使用, 利用率很低。但其中的信息涵盖丰富, 包含了了用户的上网时间、运行的程序、访问的页面等互联网的有用信息, 通过对这些海量信息的梳理, 只要运用的关联规则分析研究, 即可清晰地记录用户的程序使用习惯和网站访问偏好, 预测用户的喜好, 从而进行个性化推荐, 这在互联网+ 经济时代蕴藏着巨大的商业价值, 是还未充分挖掘的宝藏。
用户的对于兴趣内容的访问习惯和偏好, 下一步的行为可能就是购买等商业行为。因此, 利用Web日志挖掘的个性化推荐关联规则算法对用户关于兴趣内容的访问习惯和偏好挖掘是非常重要的。高效的Web日志挖掘[1], 可以很好地发掘出用户感兴趣的关键字和内容, 很好的预测商机, 为定向的个性化推荐服务打下良好的基础。Web日志挖掘的个性化推荐关联规则算法主要流程是从Web日志中筛选用户访问路径, 然后从梳理好的事务集中使用Apriori算法挖掘出高频访问集, 以此为依据进行个性化推荐服务。
一、Web日志挖掘中个性化推荐关联规则算法
个性化推荐关联规则算法可以分为两个主要步骤: 数据预处理步骤和高频访问模式发现步骤。其中数据预处理是从日志当中杂乱的结构化和非结构化数据进行分析和提取, 梳理出干净的数据, 作为实验中有效的备用访问事务集。通过高频访问模式和基于关联规则的改进Apriori算法挖掘用户的潜在访问路径, 通过从干净的事务集发掘高频访问集得到合适的个性化推荐关联规则算法。
1.1 Hadoop平台搭建。为了模拟云平台集群运行模式, 通过在局域网多台电脑上安装不同操作系统的方式组建计算机集群。在局域网中构建了8 个节点, 其中, 三台电脑为WIN7, 三台电脑为MAC, 两台电脑为Linux。包括三个Name Node节点和五个Data Node节点, 节点间通过局域网通信协议方式进行数据交换。
1.2 Web日志挖掘预处理。Web日志数据预处理本文数据来自某计算机图书在线网站, 选取网站2015 年4 月份的后台日志作为挖掘对象, 日志大小为12.6GB, 保存方式为log文本。
数据清理、用户识别、会话识别、路径补充和事务识别是Web日志数据预处理的主要步骤。
数据清理的主要工作是删除与访问兴趣无关的用户痕迹, 主要通过后缀名去除图片文件, 过滤掉由网络爬虫采集的页面记录, 本文实验过程中选取了htm、html、asp、aspx四种文件格式来保留页面访问记录。数据清理留存了有效数据, 数据存放在User Data表, 存放在Mysql数据库中。数据字段包括访问时间、访问IP地址、访问页面时间等, 为用户识别做好铺垫。
经过数据清理后的数据总共有100 多万条记录, 记录存入User Data数据表中, 再陆续经过用户识别、会话识别、路径补充和事务识别后, 数据预处理完毕, 干净的数据可以为关联规则的发现做好准备。
1.3 高频访问模式发现[2]。本文使用改进的Map Reduce化的Apriori算法发掘高频访问集, 通过给单独网页项目赋予权重值, 较好的衡量了网页的重要程度, 方便高效地挖掘出了关联访问路径, 共发掘出2943 条有效关联规则。置信度、支持度是评价关联规则的重要指标。最小置信度反映了算法挖掘关联规则的效率, 同时满足最小支持度阈值和最小置信度阈值的关联规是强规则。
二、结论
本文通过经典Apriori算法相关思想和理论介绍, 分析和研究了经典Apriori算法的缺陷。提出了改进的基于加权的多支持度的Map Reduce化的Apriori算法, 通过在高频访问模式发现阶段使用改进的Map Reduce化的Apriori算法挖掘频繁访问集, 用实例详细描述了改进的Map Reduce化的Apriori算法流程和手段。个性化推荐关联规则算法实现了通过从服务器日志中提取互联网用户频繁访问集, 然后把频繁访问集通过梳理、存储进本地的MYSQL数据库, 通过对数据库的操作、梳理和分析实现了个性化推荐关联规则算法。
参考文献
[1]陈文.基丁-Fp树的加权频繁模式挖掘算法[J].计算机工程, 2012, 38 (06) :63-65.
并行关联规则挖掘算法比较研究 篇5
1 计算模型
SO算法实在SMP上设计完成的, 这种并行算法有许多的模型。如平行随机存取器和非对称并行随机存取器, 着这里采用平行随机存取器计算模型。传统使用的顺序执行的单机处理计算机模型被称为随机存储器。平行随机存取器是随机存储器的并行版本, 它构成一个类的全局内存并行处理器的抽象模型。这种抽象模型由忽略处理器内存细节的互联网络和每个处理器可以访问每台机器的内存位置周期而独立于其它运作的处理器的视图组成。简单的说就是处理器里的每一个字段都可以读取公用存储器里的字段, 并且同时进行。
2 SO 算法
算法的主要思想是:首先扫描数据库, 获得最初的0-1矩阵, 然后生成频繁项集。1) 算法设计。算法的主要描述如下面的流程图:
在算法的第一步, 数据库中的所有事物被随机分配给处理器, 每个处理器扫描分配给他的任务并得到相应的值。当所有的事物在数据库里被扫描以后将生成初始矩阵。在原始的0-1矩阵的生成过程中, 计算每一行的第一个数将生成每一个项集的子集。因此就得到了一阶频繁项。第二步中, 单一的不属于Bk的项集将会从0-1矩阵中被删除且SO算法满足频繁项集的反单调性约束。第三步中, 候选项集Ck由Bk-1内部产生。令y, z为Bk-1的项集, 其中yj表示y的第j项。在这个算法中, 通常假设项集里的每一个事务都按名称排序, 这样是为了节约得到候选项集的时间。第四步中, 生成最大项集的元在执行过程中生成K阶频繁项集。以上的所有过程中, 处理器都是并行执行任务的。下面我们将定义矢量操作:设向量如果向量Ai, Aj…, Ak进行矢量操作, 得到如下的结果:
Get Large Itemets (k) 的生成过程如下面流程图:
在第一步中, Ck项集将会平均随机分配到每个处理器中, 每个处理器读取磁盘分配给它的候选项集。因此所有的Ck不需要在同一时间占用内存。在并行运算过程中, 每一个处理器在0-1矩阵中读取相应的向量。进行矢量与操作以后将会生成c的支持集。例如, 假设项集, 处理器i读取 (10111) 与 (11101) 两个向量。这两个向量在0-1矩阵里相对于项集A与B。进行矢量操作后将得到一个新的向量 (10101) 。如果, , 将会输出c与Bk的并集且保存。前面这三个步骤将会一直重复进行直到没有项集需要处理。整个算法就结束了。2) 算法的正确性。首先在内部加入Bk-1与Bk-1且内部的规则保证得到所有可能的k- 项集。然后对于任意的k- 项集C, 都会进行矢量与操作。在这个操作之后, 我们可以得到在这个k- 项集里同步出现的所有项集的正确数量, 这就是k- 项集C的支持集。接下来将会与最小支持度做比较, 如果, 就讲C添加到Bk中。因此在这个算法中得到的频繁k-项集是正确的。
3 SO 算法与 CD 算法的比较
1) 时间复杂度。SO算法只需要扫描数据库一次, 耗费O (其中表示数据库D里面的事务的个数, p表示处理器的个数) , 且在得到初始的0-1矩阵后数据库将不会再被使用。
然后此算法再耗费O 来生成候选k- 项集。最后, 它会耗费O 得到频繁k- 项集 (其中c代表一个常数, Ck代表候选k-项集的个数) 。2) 空间复杂度。CD算法产生大量的候选项集且相同长度的候选项集也需要储存。但是SO算法不需要存储所有的候选项集。这些候选项集将被储存到磁盘里。与CD算法相比较, SO算法空出候选项集所需的存储空间, 极大提高了算法的效率。3) 总体评价。与CD算法相比, SO算法采用矩阵来处理数据。矩阵就是用来判断项集是否为频繁项集。这样就大大的提升了得到频繁项集的效率。总而言之, 基于矩阵的SO算法更容易被实现与理解。
4 结论
许多已有的并行关联规则算法采用分层搜索的方法, 这些算法结构复杂, 所需要的时间比较长。而SO算法只需要扫描数据库一次, 时间消耗短且空间占用率低, 可以提高关联规则挖掘的效率。在以后的研究中, 一些问题应该集中于:1) 如果数据库的规模继续增大我们应该怎么做?2) 当前并行方法主要在于发现频繁项集。而对大规模的数据集, 则需要更有效更强大的关联规则。
参考文献
[1]荣冈, 刘进锋, 顾海杰.数据库中动态关联规则的挖掘[J].控制理论与应用, 2007.
挖掘空间关联规则算法的应用研究 篇6
1 GIS数据库中SDMKD可以使用的方法
笔者认为，在现阶段，至少有以下方法适用于GIS数据库中的SDMKD。
1.1 归纳与演绎的方法
这是从数据库中获取知识的最基本的方法，即从多个已存在的事实中归纳出规则。在GIS中，无论是属性数据还是空间拓扑关系，若进行抽象和概括时，均可用到此方法。
1.2 空间分析的方法
空间分析是指分析对象的位置和对象的属性。空间分析的主要目的是从空间关系中开发数据，以得到空间的内部关系并加以理解。GIS数据库中的空间数据提供了空间分析所需要的位置，非空间数据提供了对象的属性数据，因此GIS数据库提供了空间分析所需要的各种数据，利用GIS数据库中的数据可以进行空间分析。
1.3 统计的方法
统计的方法一直是SDMKD中最主要的方法。如在遥感影像分析中，对影像进行监督分类和非监督分类，都是利用统计的方法得出影像模式后，再按此模式对影像分类。实际上，遥感影像的计算机自动分类也可算是较简单的数据挖掘过程，只是其数据为一些以栅格方式存储的影像数据，而不是像关系数据库中的数据那样以关系元组的方式存储。
1.4 Rough集方法
Rough集理论(Rough Sets Theory)是波兰华沙大学Z.Pawlak教授在1982年提出的一种智能数据决策分析工具，被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知识获取。Rough集理论可用于GIS数据库属性表的一致性分析、属性的重要性、属性依赖、属性表简化、最小决策和分类算法生成等。Rouxh集方法与其它知识发现方法相结合，可以在GIS数据库中数据不确定情况下获取多种知识。
2 基于空间关联规则挖掘算法的数据挖掘软件的体系结构
数据挖掘软件的体示结构如图1所示，各部件的功能如下:
(1)数据库管理模块：主要贮存、管理和提取GIS空间数据库中的数据;
(2)方法库管理模块：主要存放、管理和提取挖掘方法库中的各种算法构件;
(3)知识库管理模块：主要贮存、管理和提取基础知识库中的知识，如概念树;
(4)工作空间：为空间数据挖掘进程运行提供场所;
(5)衍生知识库;临时存放数据挖掘结果。
3 空间关联规则算法
空间关联规则是空间数据库中普遍存在的一种重要的知识类型，将事务数据库中常用的关联规则挖掘算法与空间数据访问方法以及表达背景知识的概念树相结合，可有效地挖掘高频发生和获得多数案例支持的多层强空间关联规则，其算法描述如下。
输入:空间数据库、挖掘查询和一组阀值。
(1)数据库由3部分组成： (1) 包含一组空间对象的空间数据库，SDB; (2) 一个描述空间对象的非空间属性的关系数据库，RDB; (3) 一组概念树集合。
(2)查询由以下几部分组成: (1) 被描述对象的参照集S; (2) 用于描述S中对象的与任务相关的空间对象C1，…，C2的集合; (3) 与任务相关的空间关系的集合。
(3)概念树的每一层描述中有两个阀值:最小支持度(minsup[L])和最小可信度(minconf[L])。
输出:与对象集和关系集相关的强多层空间关联规则。
方法:挖掘空间关联规则过程如下:
第一步通过执行空间查询，将所有与任务相关的对象收集到数据库Task_relevant_DB中;
第二步计算所有对象的最小边界矩形(MBR)的交，抽取MBRS间距离落在预设阀值之内的对象，并将描述对象间空间关系的渭词存贮在数据库Coarse_predicate_DB中;
第三步为Coarse_predicate_DB中的谓词计算支持度，并过滤掉支持度低于最小支持度阀值的对象，从而形成数据库Fre quent_coarse_DB;
第四步在Frequent_coarse_DB上执行精确空间计算形成数据库Fine_predicate_DB;
第五步采用常规关联规则挖掘算法在Fine_predicate_DB上抽取强空间关联规则。
上述算法的第二步到第五步的最坏时间复杂度为O (n*logn+m+Cf*m+Cnon-spatial)，其中n为数据库中的空间对象数目，m为参与精确空间计算的空间对象数目，Cf为每个空间对象执行精确空间计算的成本，Cnon-spatial是从Fine_predicate_DB中抽取的关联规则的成本。
4 应用
基于SDMKD的数据挖掘软件从湖北农产品市场信息系统中挖掘油菜籽价格与铁路、国道和河流位置之间的关联规则。湖北农产品与市场信息系统由交易(包括品种名、价格、地理位置等，共210条记录)、铁路(包括铁路名、地理位置等)、国道(包括国道名、地理位置等)和河流(包括河流名、地理位置等)等表格组成。
利用该软件的空间规则挖掘方法，并设定不同空间对象间符合接近关系的距离阀值为25公里，最小值支持度阀值为0.3，最小可信度阀值为0.85，则可在概念树顶层发现如下所示的关联规则。
is_a (X，交易市场)^high(价格)→g_close_to (X，铁路)^g_close (X，国道)(25.5%，100%)
此规则意味着：油菜籽价格高的交易市场100%接近铁路和国道，它覆盖数据库中的28.5%的纪录。
调整最小支持度阀值为0.15，在概念树第二层可发现如下的关联规则:
is_a (X，交易市场)^g_close_to (X，京广线)→high(价格) (18%, 100%)
此规则意味着：接近京广线的交易市场100%油菜籽价格高，它覆盖数据库中的18%的纪录。上述规则对预测和指导农产品交易具有重要的实用价值。
5 结束语
从GIS数据库中挖掘空间关联规则是数据挖掘也是空间数据挖掘研究的一个特例，存在于计算机世界到现实世界的反馈过程中，需要充分理解GIS的有关知识，并涉及到地理空间认知的相关理论和内容。研究空间数据的处理方法，特别是从数据库技术角度探讨空间数据挖掘对空间数据的处理方法具有非常重要的理论和现实意义。
参考文献
[1]李德仁, 王树良, 史文中.论空间数据挖掘和知识发现[J].武汉大学学报 (信息科学版) , 2001 (6) .
[2]马荣华, 黄杏元, 朱传耿.用ESDA技术从GIS数据库中发现知识[J].遥感学报, 2002 (3) .
[3]马荣华, 马晓冬, 蒲英霞.从GIS数据库中挖掘空间关联规则研究[J].遥感学报, 2005 (6) .
关联规则算法优化研究 篇7
1.1 数据挖掘体系结构
数据挖掘(Data Mining)从定义上可以将其界定为从大量的、不完全的、有噪声的、模糊的、随机的数据中识别有效的、新颖的、潜在有用的,以及最终可理解的模式的过程[1]。通过对数据挖掘的定义的分析可以看出,数据挖掘是一个高级的处理过程,其最终要达到的目的就是能够实现从数据集中识别出以模式来表示的知识。由此可以看出,数据挖掘作为一门学科,涉及的学科知识十分广发,最主要的是涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化等多个领域。借助数据挖掘这一工具和方法,其最终的分析结果和成果可以用在信息管理、过程控制、科学研究、决策支持等许多方面。一般来说,一个完整的数据挖掘过程由以下七个步骤组成:数据清理、数据集成、数据选择、数据变换、数据挖掘、模型评估和知识表示。
1.2 关联规则
关联规则的挖掘(ARM)是数据挖掘的一项重要的任务。关联规则挖掘最根本的目的就是能够快速有效地发现大量数据中项集之间有趣的关联或相关联系。其目的就是从事务数据库、关系数据库中发现项目集或属性之间的相关性、关联性以及因果性。随着数据挖掘相关研究的不断深入,许多研究学者更多地将研究的目光集中在了挖掘关联规则方面。从数据挖掘的本质特征来分析可以看出,关联规则更多地反映一个事件和其他事件之间依赖或关联的知识。通过关联规则的定义可以发现,如果两项或多项属性之间存在关联,那么其中一项的属性值就可以依据其他属性值进行预测。
2 一种基于矩阵的Apriori改进算法
挖掘关联规则的对象是含有大量事务的事务数据库,所以如何设计一个高效的算法,以提高挖掘的计算效率,降低数据库的扫描次数,是研究关联规则挖掘的重要课题。虽然现在对于挖掘算法Apriori相关的改进和发展不断涌现,但是仍然有着自身的一些缺陷,最具有代表性的就是对数据库进行多次扫描而造成的精确度的降低,以及显著地存在由候选集C K产生频繁集LK等不足。正是由于这些缺陷的存在,本节提出一种基于矩阵的改进算法来产生频繁集L K,这种算法只对数据库扫描一次,并且无需候选集C K,即可得到频繁集L K。
2.1 与算法相关的几个概念
I={I1,I2,···,Im}是项的集合,D={T1,T2,···,Tp}是数据库事务的集合,其中TiСI(i=1,2,...,p)。
定义1项Ij的向量定义为:
Dj={d1j,d2j,...,dpj},其中,dij=1,当Ij∈Ti,这样support_count(Ij)=∑dij。
定义2项集I的矩阵定义为:
定义3 2-项集{Ii,Ij}表示Rij,Rij的向量定义为:
定义4 K-项集{I1,I2,I3,...,Ik}表示为R12...K,即R12...K={R12...K-1,Ik},R12...K的向量定义为:D12...K=D1∧D2∧...∧DK=(D1∧D2∧...∧DK-1)∧DK.
定义5非频繁项集下标集L’定义为:由支持度小于最小支持度的项集(非频繁项集)中的项集的下标组成的集合,如Support(R12)
定义6项集下标集W定义为:由项集的集合中每个项集的下标所组成的集合如:若项集集合为{R12,R13,R23},则W={12,13,23}。
定义7下标w的下近似集L'(w)定义为:L'(w)={y|y∈L'且y∈w}。
2.2 基于矩阵的算法描述
3 Apriori算法在商务中的应用
3.1 问题提出
假如一家大型超市的管理人员想要知道每天超市的销售情况,顾客的购买模式,通过顾客特征,采取相应的货价摆放以增加顾客满意度和销售额。如果仅仅靠传统人工技术,从巨大的购买信息中找出相应的答案就像大海里捞针,非常困难。
本章利用数据挖掘技术针对这一问题进行研究。研究对象是顾客在一次购物的过程中,购买的不同商品之间联系,进而借助数据挖掘来进一步深入地分析顾客的购买习惯。在对不同商品种类和数量进行充分分析的基础上,进一步地分析出哪些商品最受顾客欢迎,从而购买频率很高,进而借助这种关联的发现可以帮助零售商制定营销策略。问题归结为分析当前销售情况,找出商品统计信息之间的关系。
3.2 数据来源
对于一个实际的数据挖掘应用来说,数据是进行数据挖掘的基础和根本,同时数据挖掘技术的应用对数据量也有一定的要求,只有这样数据挖掘才能有实际意义。数据的获取确实是这次研究数据挖掘面临的很大的问题。通过仔细的搜索和分析,我最终选择了Belgium的一家的超市的销售数据。整个数据源是在三个非连续的时期收集的,在每一个间隔期,没有可获的数据。数据收集期跨时近5个月,总共收集到的数据记录有88163条。在整个数据收集期间里,该超市总共出售了16470种商品,共有5133位顾客在该超市购买了至少一种商品。
但是与我们期望的数据还是有许多不同之处,数据表结构与我们需求的也存在很大的差别,这里可以采用等同和类比的方法,从而实现了对表结构的修改和数据的替换,这样以来就有效地实现了对大量的数据替换和表结构重组,解决了数据来源问题。
3.2.1 数据处理
由于数据仓库中各个主题中的数据是按照前端应用需求存放的,因此在数据应用前必然存在一个数据处理和转换的过程,这一过程需要对数据进行变形,使之适应前端应用需要。为了能够提高关联规则的效率,充分实现数据挖掘需要达到的既定目标,在进行数据挖掘之前,需要对交易数据库中的销售数据进行一定的预处理才能有效地应用数据挖掘技术和方法。这里采用超市销售表中的相关信息来进行数据挖掘,具体的每一条记录包括以下信息:
顾客编号发票编号购买日期商品1名称商品1总价商品2名称商品2总价⋯商品n名称商品n总价总计
通过分析可以发现,这种数据结构的特点是数据库的每一条记录能够对每一位顾客在一次进入商店进行购物的详细信息进行充分的记录,一次完整的交易记录通常由多种商品的名称和支付的价钱组成,这种数据结构提供的信息比较详细,但是不利于关联规则挖掘的。因为关联规则所描述的只是不同项目之间的关系,它只关注一次交易中有哪些商品被同时购买。我们不用去考虑顾客在一次交易中所购买物品的数量、价格等信息,每种商品(也就是物品)都由一个二进制变量代替,而不管它是否在交易中被购买与否。由于我们挖掘的交易数据库中关联规则最根本要实现的目的是反映出各种物品之间的关联关系,因而,我们需要从综合数据库中取出当前主题需要的数据,将上述的交易记录的数据结构转换成如下结构形式:
顾客编号发票编号购买日期商品1名称商品2名称⋯商品n名称
这样我们通过每一条的交易记录就能够清晰地看出每一名顾客在进入超市后的每一次购物情况,同时,经过变换也可以有效实现对数据的压缩和精简,一方面可以减少工作量,提升运算速度和效率,同时还能够有效筛除冗余信息,这样以来将会使算法搜索数据库的时间缩短,大大提高了Apriori算法的效率。
3.2.2 数据转换
当对数据进行有效的压缩,并过滤了一些不需要的信息后,都会形成二维表形式的数据源模式。
但是这些数据都是描述业务事实的信息,在进行数据挖掘过程中,这些数据是不能直接拿来使用的,因此就需要把事实数据变换成算法能够识别的数据类型。一般来说,最常用的变换有两种:离散变换和值变换。
1)离散变换。离散变换的运算原理可以解释为通过将属性域划分为区间,减少连续属性值的个数,以区间的标号代替实际的数据值。概念分层就是其中常用的一种,在搜集会员数据的过程中,我们已经自然的进行了初步的概念分层。虽然绝大多数的商品都是用唯一的条形码标识予以区别,但是在超市中的某些商品分类比较细,而且种类繁多。这个时候如果按照每一条单独列出,就会比较繁琐,所以我们可以用某一种商品名称来代表一组商品,而不是某一单独的某一个商品。
2)值变换。在数据库中,由于许多属性值都是字符型数据,这样产生的最不利的影响会对数据的挖掘和统计分析造成不良的结果,我们采用值变换可以将字符型数值映射成为数值型数据。例如:
音像制品==>I1,书籍==>I2,文具==>I3,...,灯具==>I100,...
4 总结
该文回顾了数据挖掘及关联规则中的相关概念,并着重研究了一个关联规则的Apriori的算法实现,针对Apriori算法存在的对数据库进行多次扫描,精确度不高,由候选集C K产生频繁集L K等的问题,提出了一种改进的算法,它解决了一些原有Apriori算法可能遇到的一些难题。
参考文献
[1]Agrawal R,Imielinski T,Swami A.Mining association rules between sets of items in large databases[C].Proceedings of the ACM SIG MOD Conference on Management of data,1993:207-216,
[2]Jiawei Han,Sonny H S.Chee,Jenny Y Chiang.Issues for On-Line Analytical Mining of Data Warehouses[C].
[3]Information Discovery,Inc.OLAP and Data Mining,Bridging the Gap[C].
[4]Park J S,Chen M S,Yu P S.An effective hash-based algorithm for mining association rules[C].Proceedings of ACM SIGMOD Interna tional Conference on Management of Data,1995:175-186.
[5]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002:100-128.
[6]朱扬勇.数据挖掘入门[EB/OL].http://datamining.126.com.
[7]琚敏敏.基于Apriori算法的改进——TSAprioriTid算法[J].科技信息,2010(12):106-106.
关联规则算法优化研究 篇8
随着社会经济的迅猛发展和工业化程度的不断提高,污染物的排放已使环境日趋恶化,直接或间接给生物的生存带来威胁,并危及人类健康。重金属污染与其他有机化合物的污染不同,具有富集性,很难在环境中降解。近年来,工矿业废水、生活污水等未经适当处理即向外排放,污染土壤和废弃物堆置场受流水作用,以及富含重金属的大气沉降物输入, 城市生活污水、工业废水和矿山开采、金属冶炼等所产生的污染物通过不同方式进入水中, 使水体中的重金属含量急剧升高,如随废水排出的重金属汞(Hg)、铜(Cu)、铬(Cr),导致水体受到重金属污染 [1]。我国各大江河湖库普遍受到不同程度的重金属污染,其底质的污染率高达80.11% [2],而且已经开始影响到水体的质量,严重影响着人类及其它生物的健康与生存。
数据挖掘是从大量的数据中提取隐含在其中的、人们事先不知道的、但又潜在的有用信息和知识的过程。数据挖掘得到的信息和知识的表现形式为规则、概念和模式等,它可以帮助决策者分析历史数据以及当前数据的特征和规律,以便进一步预测未来。 [3]关联挖掘作为数据挖掘的一个重要研究分支,其主要研究目的就是从大型数据集中发现隐藏的、有趣的、属性间的规律,即关联规则。 [4]本文采用数据挖掘的关联规则技术从现有的生活、工业两方面的废水排放量、化学需氧量排放量、氨氮排放量以及水体中汞、镉、铅的含量数据进行处理,并用关联规则中的Apriori算法获取相应的关联规则,形成水体污染预警知识,便于水体重金属污染的预防和治理。
2 材料与方法
2.1 数据来源
本文数据来源于2011年环境统计年报 [5]。选取六个对于水体重金属污染有一定作用的影响因子:工业废水排放量、生活废水排放量、工业化学需氧量排放量、生活化学需氧量排放量、工业氨氮排放量、生活氨氮排放量,并选取了汞、镉、铅三种最具重金属代表性的元素作为分析因子,具体数据如表1所示。
2.2 关联规则及Apriori算法描述
1994年由R.Agrawal等人提出来的Apriori算法是关联规则挖掘的一个经典算法 [6],关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。关联规则侧重于确定数据中不同领域之间的联系,找出满足给定支持度和置信度阈值的多个域之间的依赖关系 [7]。关联规则能够从大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。为了在数据挖掘任务中得到有用的和可靠的规则,需要通过支持度和置信度两个阈值来保证。关联规则X=>Y在D中的支持度是D中事务包含XUY的百分比,即概率P(XUY),它是对关联规则重要度的衡量,表示关联规则的频度。关联规则X=>Y在D中的置信度是包含X的事务中同时包含Y的百分比,即条件概率P(X=>Y),它是对关联规则准确度的衡量,表示关联规则的强度 [8]。Apriori算法的核心思想是把发现关联规则的工作分为两步:第一步通过迭代检索出事务数据库中的所有频繁项集,即频繁项集的支持度不低于用户设定的阈值;第二步从频繁项集中构造出满足用户最低信任度的规则 [9]。对于满足最小支持度和最小置信度要求的关联规则称为强规则 [10]。
2.3 数据处理
利用Weka软件,采用关联规则中的Apriori算法,对表1的数据进行处理,得到的关联规则如所示:Apriori
相应的规则解释如下:
规则1:工业氨氮排放量<29.82万吨时,则汞排放量<1.505吨,置信度为100%;
规则2.3:工业化学需氧量排放量<452.07万吨时,则铅排放量<183.57吨,置信度为100%;
规则4:工业废水排放量为233.43-237.82亿吨时,则工业氨氮排放量<29.82万吨,置信度为100%;
规则5:工业废水排放量为233.43-237.82亿吨时,则汞排放量<1.505吨 ,置信度为100%;
规则6.7:工业废水排放量为233.43-237.82亿吨时,则镉排放量<38.14吨,置信度为100%;
规则8.9:工业废水排放量为233.43-237.82亿吨时,则铅排放量<183.57吨,置信度为100%;
规则10:生活废水排放量<245.25亿吨,则工业氨氮排放量为39.9-42.42万吨置信度为100%;
规则11.12:生活废水排放量>245.25亿吨时, 则镉排放量>102.46吨置信度为100%;
规则13.14:生活废水排放量<245.25亿吨时,则铅排放量为482.96-525.73吨置信度为100%;
规则15:工业化学需氧量排放量<452.07万吨时,则汞排放量<1.505吨置信度为100%;
3 结果分析
由关联规则Apriori算法得出的15条规则结果分析,可以得到如下结论:
1) 重金属与氨氮排放量关系。当工业氨氮排放量<29.82万吨时,则汞排放量<1.505吨,说明工业氨氮排放量较低时,重金属元素汞的排放量低;
2) 重金属与废水排放量关系。当工业废水排放量为233.43-237.82亿吨时,则汞排放量<1.505吨,镉排放量<38.14吨,铅排放量<183.57吨,说明工业废水排放量较低时,重金属汞、镉、铅的排放量较少;当生活废水排放量>245.25亿吨时, 则镉排放量>102.46吨,说明生活废水排放量比较高时,重金属镉的含量比较高。生活废水排放量<245.25亿吨时,则铅排放量为482.96-525.73吨,说明当生活废水排放量比较高时,重金属铅的含量比较高。
3) 重金属与化学需氧量排放量关系。工业化学需氧量排放量<452.07万吨时,则汞排放量<1.505吨,说明当工业化学需氧量排放量比较少时,重金属汞的含量比较低。工业化学需氧量排放量<452.07万吨时,则铅排放量<183.57吨,说明化学需氧量排放量较少时,铅的排放量较少。
4 结论
水体中金属污染具有富集性、不可降解性等特点,已经对我国各大江河湖库造成了严重污染,影响人类和其他生物的健康和生存,因此,提高对水体中重金属污染的成因认识,了解水体污染物排放对几大重金属的影响,加强对水体重金属污染排放的控制,显得尤为重要。采用数据挖掘关联规则Apriori算法,对近十年来的全国污染物和重金属排放量数据利用weka进行离散化处理后,获取相关的关联规则知识,分析了工业、生活两方面的废水排放量、氨氮排放量、化学需氧量与水体重金属汞、镉、铅含量之间的关系 ,从而对水体重金属污染进行预警,对水体重金属污染的预防和治理的决策上起到了一定的指导作用,帮助控制环境污染。
摘要：关联规则是一种重要的数据挖掘技术,结合水体污染的特点,应用关联挖掘中的Apriori算法,分析水体污染排放量和水体中重金属含量之间的关系,同时分析工业、生活分别与水体重金属含量之间的关系,对水体重金属污染物有一定的预警作用。