关键字 |
| 关联规则,先验的算法,频繁项 |
介绍 |
| 数据挖掘是一种决策支持过程。Itgets的潜在有用的信息和承认实际应用数据很大,不完整的,嘈杂的、模糊的、随机的。数据挖掘与从数据库中提取大量的数据,转换,处理这些数据分析和建模,撤回援助决策的关键数据。关联规则挖掘是数据挖掘中一个重要的问题[1]。 |
| r . Agrawal等人在1993年提出了著名的先验的算法基于频繁项集[2、3],然后大部分算法都是基于改进的基本算法或导数算法的变体(4、5)。本文提出了一种改进的关联规则,它使用交叉操作产生频繁项集,这奠定了基础提高基于关联规则挖掘算法的性能。该算法只需扫描数据库一次,而且大大减少了候选频繁项集的数量。 |
关联规则 |
| 关联规则可以de照本宣科正式如下[6], |
| 假设我= (i1、i2…, im)是一家集m不同属性,在给定的数据库D, T是每个记录acollection 1的一组属性。那是T⊆;我,TID T能标识符。如果X⊆我和X⊆T, T包括X Anassociation规则公式为X⊆Y, X⊆Y⊆我和Xn Y = < D。它表明,如果X出现在一个事务,Y会导致出现在相同的事务中不可避免的。X被称为规则的前提,和Y规则的结果。 |
| 项集支持 |
| 时候itemset出现在事务数据集被称为支持数字或支持计数。支持是除以总数量的事务,叫做项集的支持。它可以由符号定义如下: |
| 支持(X⇒Y) = P U (X, Y) |
| 支持(X⇒。X和Y Y)的概率是指同时出现在D time.P X (X)的概率是指在数据集D,一样的P (Y)。 |
| 频繁项集 |
| 如果支持itemset大于或等于预处理,定义的最小支持度阈值设置的项集称为频繁项集[7]。 |
| 有两个重要的关联规则的基本措施,支持(s)和(c)的信心。由于大型数据库和用户只关心那些经常购买物品,通常由用户的支持和信心是预定义的阈值下降那些不是很有趣或有用的规则。这两个阈值分别被称为最小支持和最小的信心。关联规则的支持(s)被定义为/百分比分数的记录包含X∪Y在数据库中记录的总数。假设一个项目的支持是0.1%,这意味着只有0.1%的事务包含这个项目的采购。信心的关联规则的定义是交易数量的百分比/分数包含X∪Y记录的总数,包含X。自信是一种衡量关联规则的力量,假设关联规则的信心X⇒Y是80%,这意味着80%的交易包含X也包含在一起。总的来说,一组物品(如规则的前提或结论)叫做itemset。物品的数量itemset叫做itemset的长度。项集的长度称为k-itemsets k。 |
| •生成的组候选人k-itemsets 1-extensions大型(k - 1) -项集生成在前面的迭代。 |
| •支持的候选人k-itemsets是由经过数据库生成的。 |
| •项目集,没有最低支持被丢弃,剩下的项集被称为大k-itemset |
APRIORY算法 |
| 一般过程 |
| 关联规则生成通常分成两个独立的步骤: |
| 1。首先,最小支持应用于数据库中找出所有的频繁项集。 |
| 2。第二,使用这些频繁项集和最小信心约束形成的规则。 |
| 第二步是直接时,第一步需要更多的关注。 |
| 数据库中找出所有的频繁项集是困难的,因为它涉及到搜索所有可能的项集(项目组合)。一组可能的项集是设置在我和大小2 n−1(不包括空集不是一个有效的项目集)。虽然powerset的规模呈指数级增长数量的物品我n,有效的搜索可能使用downward-closure属性的支持(也称为anti-monotonicity)保证频繁项目集,其所有子集也频繁项目集的频繁,因此,所有的超集也必须是罕见的。利用这个性质,高效的算法(如先天和辉煌的成就)可以找到所有的频繁项集。 |
| 先验的使用广度优先搜索和树结构计算候选项集效率。它生成候选项集的长度k项集长度k−1。然后梅干的候选人有一个罕见的子模式。根据下行关闭引理,候选集包含所有k-length频繁项集。之后,它会扫描事务数据库确定候选人之间的频繁项集。 |
| 先天,而具有历史意义的、患有许多效率低下或取舍,这引发了其他算法。候选人代生成大量的子集(算法尝试加载候选集之前尽可能多的每个扫描)。自下而上探索子集(本质上是一个子集的宽度优先遍历晶格)发现任何最大子集S毕竟只有2 | |−1的适当的子集。 |
分析的问题 |
| 发现强关联规则库和minsupport minconfidence由用户指定,它可以分为两个问题: |
| 1)找出频繁项集:使用minsupport找出所有的频繁项集不少于minsupport。事实上,他们互相包含。 |
| 2)产生关联规则:发现关联规则的信心不少于minconfidence最大频繁项集。所以,如何发现频繁项集快速,是关联规则挖掘的重点。 |
| 有两个重要性质的关联规则挖掘[8][9]: |
| 1:如果X是一个频繁项集的项集,那么所有的非空的子集 |
| 2:如果项集X不是一个频繁项集,那么它的所有超集并不频繁项集。 |
APRIORY基于矩阵 |
| 算法基于矩阵使用矩阵来描述数据库中的每一个事件,所以我们只处理矩阵计算频繁项集的支持的候选人,而不需要再次扫描数据库。 |
| 这里计算支持快速使用“和操作[10] |
| “经营”和行根据物品的候选频繁项集的矩阵,然后添加的结果,结果都是支持的。例如,我们只是和行“一”,行“c”矩阵当我们想计算项集{a, c}的支持,并添加结果,我们可以得到的支持。 |
| 过程描述: |
| 1。将事务数据库包含我项目和t事务矩阵,我+ 1 + 1行1列,第一列指出项目和第一行记录事务。 |
| 然后根据minsupport简化矩阵。当一个项目的总和小于minsupport,项目将不会在任何频繁项集,包含项目,删除行。通过一步是标记为初始矩阵的矩阵 |
| 2。最大频繁项集是一个频繁项集,包含最比其他的物品。根据性质1,它会更容易发现频繁项集包含更少的物品如果我们知道最大频繁项集 |
| 3所示。发现矩阵的事件的大部分商品和数量的物品被标记为K .如果事务的数量物品的数量不少于minsupport K不到,这意味着最大频繁项集不能包含K物品,所以我们应该考虑的事情K - 1项并使用K K - 1。我们使用这种方法直到我们找出K事务的数量不小于minsupport。 |
| 使用递归算法简化矩阵 |
| 删除的列条目的数量少于k .删除的行事务的数量小于minsupport。如果它没有改变矩阵矩阵标记为NewMattix和步骤。如果矩阵是空,这意味着没有K-frequent项集。 |
| b)选择一个事件“t”NewMatrix并选择K项t形成一个项集,然后利用和操作数项集的支持。如果不小于minsupport的支持,项目集是K-frequent项集。否则它不是。然后我们再次选择K t的物品不一样的前任和法官的支持。使用这种方法,直到没有不同的K项t。现在,我们可以删除的列包含NewMatrix t和简化。然后,使用相同的方式来处理其他事务NewMatrix和项集已数不应被视为一次。使用这种方式,直到NewMatrix是空的。如果没有K-frequent项集,我们应该去一步)和考虑的事情k - 1项。 |
| 3所示。使用矩阵找出所有的频繁项集2-frequent项集K-1-frequent项集,和方法类似于先验的算法。但应该简化矩阵使计算更容易的支持。 |
的结果分析 |
| 在我们的实验中我们选择超市数据研究对象。超市数据库7个不同的项目,包含4000个事务。发现新算法的效率,首先我们使用普通先天算法,然后使用改进的先验的算法。 |
算法的比较: |
| 图1显示了执行时间的先验的算法和改进的先验的算法,如果我们比较算法在不同支持所需的执行时间正常先天算法多是对基于矩阵的改进算法。 |
| 基于矩阵的算法经常不扫描数据库,减少I / O的开销。因此,新算法在时间复杂度比先天。 |
| 如图表所示当我们增加数据库的大小时间生成规则apriory算法比改进的先验的方法。 |
结论 |
| 经典的先验的算法会由于对加入实现复杂性和修剪。基于矩阵的算法在时间和空间都比先天。矩阵有效显示数据库中的事务,并使用“经营”处理矩阵生成最大频繁项集和其他人。它不必扫描数据库一次又一次地查找事务,并大大减少候选频繁项集的数量。新算法在时间复杂度比先天。通过这个算法是善于支持很小的频繁项集。改进算法获得奖金的计算时间和促进效率的计算。 |
|
数据乍一看 |
 |
 |
| 图1 |
图2 |
|
|
引用 |
- 大卫的手,海基Mannila, Padhraic史密斯。数据挖掘原理[M]。翻译员Yinkun张。北京:机械工业出版社。2003:272 - 284。
- R Agrawal。挖掘关联规则集之间的物品在数据库[C] .Washington: ACMSIGMOD国际会议管理学报》的数据,1993:207 - 216。
- Agrawal R, Srikant R .快速算法挖掘关联rulesin大型数据库.Proc。20国际Conf非常LargeData基地。[c]。圣地亚哥:摩根考夫曼,1994:478 ~ 499
- Z.Xu, S。张。挖掘关联规则的优化Apriorialgorithm计算机Engineering.2003 [J], 29 (19): 83 - 85。
- g . Grahne J。朱、高效使用prefix-trees挖掘频繁项集。Proc。ICDM 03 Int。研讨会频繁项集挖掘实现(FIMI ' 03),墨尔本,FL, 2003年11月
- 林小博,徐Qian-Fang Zhi-Qing,郭小君,李Chun-Guang。可信关联规则及其挖掘算法基于最大小团体[J]。软件学报,2008,(10):2597 - 2610。
- 夏,张军,王Guo-yin。时空关联规则挖掘算法及其在智能交通系统中的应用[J]。38岁的计算机科学,2011 (9):173 - 176。
- 陈Wenwei。数据仓库和数据挖掘教程[M]。北京:清华大学出版社。2006年
- 朱Yixia,姚明梨纹,黄黄Shuiyuan,为了。基于矩阵的关联规则挖掘算法和树木[J]。计算机科学。2006年,33 (7):196 - 198
- 羌族,周Yuanchun吴Kaichao,燕Baoping。Aquantitative关联规则挖掘算法[J]。计算机工程。2007年,33 (10):34-35
|
菜单
