发布时间 : 星期日 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读f82c9d1e10a6f524ccbf85c8
山东师范大学硕士学位论文
联规则的挖掘中，提出了一些模糊关联规则的挖掘算法[42-44]。这些算法较好地解决了锐利临界的问题。
3.2.2.根据规则中涉及的数据维：
（1）如果规则中的项或属性每个维只涉及一个维，则它是单维关联规则。 （2）如果规则涉及两个或者多个维，则它是多维关联规则。
单维关联规则是基于Apriori算法的一种数据挖掘方法，其原理是通过逐层搜索的迭代方法来寻找频繁项集，即通过K项集获取（k+1）项集。然而，由于每次寻找一个频繁k-项集都需要扫描一次数据库，这种方法的计算效率比较低。为了克服这个缺点，人们对选区频繁项集的方法原理进行了改造，在此基础上，提出了不同的关联规则挖掘算法，如急雨散列的技术、事物压缩、划分法、选样法、动态项集计数法、频繁模式增长法等，各种方法在不同程度上提高了Apriori算法的性能（J.Han，2001）。
多维关联规则的挖据涉及多个属性，其挖掘方法可根据它们的属性性之来确定，通常，数据库中数据的属性可分为分类的和量化的两种，分类属性是指具有限个不同的值且这些值之间是无序的，如性别、颜色、品牌等；量化属性是指属性的各个值之间是有大小顺序的，如年龄、收入、价格等。对于量化属性的多维关联规则挖掘，一般可分为两类，即将量化属性表示为区间或具体数值。
多层关联规则的挖掘可以采用由顶向下的方法，即由较高的概念层到较低的概念层，挖掘过程中，对每个概念层的频繁项集累加技术 。就每一层而言，可以使用搜索频繁项集的算法，如Apriori法及其改进，支持度可采用一致支持度或者递减支持度。一致支持度是指所有层次使用的嘴下支持度是相同的，该法的优点是搜索过程较为简单，缺点是在较低概念层中有可能丢失有意义的关联规则或在较高概念层中产生无意义的关联规则：递减支持度是指概念层越低、支持度越小，其缺点是挖掘过程会找到一些无用的规则或者遗漏一些有意义的规则。因此，在多层关联规则的挖掘过程中，使用何种支持度需要视具体情况而定。
3.2.3.根据所涉及的抽象层
有些挖掘关联规则的方法可以在不同的抽象层发现规则，可分为单层的和多层的，在单
29
山东师范大学硕士学位论文
层的关联规则中，所有的变量都没有考虑到显示的数据是具有多个不同的层次：而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。
3.2.4.根据关联规则的各种扩充
关联规则可以扩充到相关分析，还可以扩充到挖掘最大的频繁模式（最大模式）和频繁闭项集。使用最大模式和频繁闭项集可以显著压缩挖掘所产生的频繁项集数。 基于以上关联规则的分类，我们就可以根据不同类别的规则使用不同的方法进行挖掘
3.3关联规则挖掘的基本原理及理论基础 3.3.1关联规则的基本原理
关联规则的挖掘是数据挖掘中的一个重要方面，它通过寻找在同一事件中出现的不同事项之间的相关性来实现，其优点是计算模式简单，结果易于理解，因而得到了广泛的应用，例如，A.Sava等（1995）从人口普查的大量数据中找出调查区域、选民、地方政府所在区域等对象之间的关系。J.Kleinberg等（1998）利用关联规则在银行和电信业等机构对顾客行为进行调查、分析和预测。J.Han（2001）探讨可关联规则如何通过“购物篮分析”帮助零售商有选择的经销和安排货架。
关联规则挖掘算法的模型如下图所示
最大项集搜索算法 关联规则搜索算法 关联规则集合 数据集合 minsupport Minconfudence 用 户
30
山东师范大学硕士学位论文
图2-1 关联规则挖掘的基本模型
3.4关联规则的定义及步骤 3.4.1关联规则的定义
设Ｉ={{i1，i2,?,im}是项的集合,设D={T1,T2,?,Tn}是与任务相关的数据库事务的集合,其中每个事务是项的集合,使得Ti?I。设A是一个项集,包含K个项的项集称为K-项集。事务Ti包含Ａ当且仅当A?Ii。事务集D中项集A的支持度sup(A)是D中包含A∪B的事务的百分比,即sup(A)=P(A∪B)。
支持度和置信度两个阐值是描述关联规则的两个重要概念，支持度反映关联规则在数据库中的重要性，表示规则的频度；置信度衡量关联规则的可信程度，表示规则的强度。同时满足最小支持度阈值和最小置信度阐值的规则称为强关联规则。为了方便，将
最小支持度阈值记为min_sup，最小置信度阐值记为min_conf。 最小支持度表示项目集在统计意义上的最低重要性，最小置信度表示规则的最低可靠性。一个项目集的出现频度是指整个交易数据集D中包含该项目集的交易记录数，也称为是该项目集的支持度。如果项目集的出现频度大于或等于min_ sup与D中事务总数的乘积，则称项目集满足最小支持度。如果一个项目集A满足最小支持度(support(A) ≥ min_sup)，则称它为频繁项目集，频繁k-项目集的集合记为Lk。反之，如果一个项目集A不满足最小支持度，则称为非频繁项目集。候选项目集是潜在的频繁项目集的集合，是频繁(k-1)-项目集的超集。含有k项的候选项目集记为Ck，由它构成频繁k-项目集Lk
因此,关联规则挖掘问题可以转为两个子问题:①找出所有频繁项集,这些项集满足预定义的最小支持度(min_sup)。②由频繁项集产生强关联规则,这些规则必须同时满足最小支持度(min_sup)和最小置信度(min_conf)。问题②实现简单容易。关联规则挖掘算法的性能主要集中在问题①上,大部分算法都集中在如何高效发现频繁项集。
目前，已经提出很多关联规则挖掘算法，其中由R.Agrawal等首先提出的Apriori算法是一种较有效的频繁项集挖掘算法。该算法的基本思想是利用一个层次顺序搜索的迭代方法来完成频繁项集的挖掘工作,即利用ｋ-项集来生成(ｋ+1)-项集,用候选项集Ck
31
山东师范大学硕士学位论文
找频繁项集Lk。首先,找出频繁1-项集的集合,记作L1, L1用于找频繁2-项集的集合L2,而L2用于找L3,如此下去,直到不能找到频繁ｋ-项集。找每个Lk需要一次数据库扫描。一旦从数据库的事务D中找出频繁项集,就可以根据最小置信度直接产生强关联规则。算法的缺陷是:可能需要产生大量的候选项集Apriori可能需要重复地扫描数据库,通过模式匹配检查一个很大的候选集合。
3.4.2关联规则挖掘的一般步骤
R.Agrawal等人在1993提出的Apriori算法,被认为是非常有效的挖掘算法,它将关联规则挖掘算法分解为两个子问题:
1.采用逐层搜索叠代的方法寻找所有支持度大于最小支持度的项集,称为频繁项集。Apriori算法首先用Apriori-gen(Lk-1)生成侯选ｋ-项集集合Cｋ,然后再扫描数据库D计算Cｋ中各候选项集出现的次数,再与最小支持度比较得到频繁ｋ-项集合LK。Apriori-gen函数以Lk-1 (所有频繁(k-1)-项集)作为输入参数,返回所有k-项集的候选项集集合CK,分为连接、剪枝两步实现:
第一步,连接 select p.item1,p.item2,?,p.itemk-1,q.itemk-1 Into Ck
From Lk-1 p, Lk-1 ,q
Where p.item1=q.item1,?,itemk-2=q.itemk-2,p.itemk-1 第二步,剪枝,如果存在(k-1)—项集c不包含于Lk-1之中,则删除项集c,c∈Ck。For each items c∈Ck For each (k-1)-subsets of c If (s?Lk-1)then Delete c from Ck; 2.利用频繁项集产生可信度不小于最小可信度的关联规则。 第二步较为简单,如果得到频繁项集,可以直接推出关联规则。因此挖掘的重点主要集中在如何快速、高效发现频繁项集。Apriori算法自身虽然进行了一定的优化,但在实际应用中还是存在一些问题: (1)需多次扫描交易数据库,由于挖掘的对象都是大型数据库或数据仓库,这样势必影响 32