新方法基于改进先验的算法和频繁模式挖掘关联规则的算法

穆罕默德Shahnawaz纳西尔¹博士R B S亚达夫²

研究学者、数学系、Magadh大学,印度的菩提伽耶
教授和头部,数学系,Magadh大学,印度的菩提伽耶

文摘

关联规则挖掘的效率是一个重要的领域,在数据库知识发现(KDD)。先验的算法是一种经典关联规则挖掘算法。本文提出一种改进方法,先天和频繁模式的算法来提高生成关联规则的效率。该算法采用一种新的方法来减少冗余代sub-itemsets在修剪候选项集,可以直接形成频繁项集的集合和删除候选人子集不是频繁的同时。该算法可以提高扫描数据库中获取信息的概率,减少潜在的项集的规模

关键字

关联规则,先验的算法,频繁模式的算法,频繁项目集

我的介绍。

最近的技术进步提供了一个机会来构建和存储大量的数据从许多领域如商业,政府和银行、社会和医疗服务的交付,环境安全,安全和政治。通常,这些数据集非常大,经常生长和包含一个巨大数量的复合功能,这是很难管理的。因此,矿业或从大量的数据中提取关联规则在数据库中是许多行业感兴趣可以帮助在许多业务决策流程,如交叉销售、篮子数据研究和推广分类。频繁项集挖掘(鳍)是最广为人知的技术之一是关心从数据库中提取的信息基于事件经常发生,也就是说。,an event, or a set of events, is interesting if it occurs frequently in the data, according to a user given minimum frequency threshold or in other terms it is a non-supervised process which concerns in finding frequent patterns (or itemsets) hidden in large volumes of data in order to produce compressed summaries or models of the database. It is the fundamental operation behind several common data-mining tasks including association rule [1] and sequential pattern mining [2].

挖掘关联规则是数据挖掘研究的主要内容之一,目前,和压力特别寻找不同的关系数据库中的条目。对提高挖掘算法是一个重要方面,如何减少候选项集为了有效地生成频繁项集。在经典先验的算法,当候选人代生成时,算法需要测试他们的出现频率。冗余导致高频查询的操作,所以将消耗大量的资源是否在时间或空间。

本文中提取关联规则的一种改进算法,考虑了时间,许多数据库扫描,内存利用率和规则的兴趣度。该方案是结合目前最大的先天(改善先天)和频繁Pattern-tree技术(FP树)比古典先验的算法保证了更好的性能。提出技术的目的,分析挖掘频繁项集和评估新技术的性能和比较与现有的古典先验的和频繁的Pattern-tree算法支持下计数。

二世。相关工作

频繁模式挖掘频繁项集的分类从庞大的数据库中。的主要目标是识别所有频繁项集挖掘频繁项集,也就是说,项目集至少有一个特定的最低支持;事务包含itemset的百分比[3]。使用支持背后的基本原理是,只有项集高频感兴趣的用户,”的实际用途限制频繁项集挖掘发现项集”的意义。提出的AIS算法Agrawal等。[1]只有一项顺向生成关联规则,这意味着这些规则的顺向只包含一个条目。使该算法更有效,评估方法引入一个意图减少那些没有希望的候选项集大,因此可以避免不必要的努力计算这些项集。因为所有的候选项集和频繁项集被认为是存储在内存中,内存管理也提出了AIS当内存是不够的。SETM算法由Houtsma和偶像等。[4]出于希望使用SQL来计算项集。像AIS, SETM算法动态生成候选项集作为数据库扫描,但最终通过计算。因此生成和计算每个候选项目集AIS算法生成。 J. S. Park, M. Chen, P.S. Yu.et al. [5] described DHP algorithm in which author utilizes the extra data structure i.e., Hash Bucket for candidate itemset generation. The algorithm is an effective hash-based algorithm for the candidate set generation. Han et al. [6] devised an FP-growth method that mines the complete set of frequent itemsets without candidate generation. The algorithm does not subscribe to the generate-and-test paradigms of Aprori. Instead, it encodes the data set using a compact data structure called FP-tree and extracts frequent itemsets directly from this structure. The algorithm adopts divide and conquer strategy. A memory-based, efficient patterngrowth algorithm, H-mine (Mem), is for mining frequent patterns for the datasets that can fit in (main) memory. H-mine [7] algorithm is the enhancement over FP-tree algorithm as in H-mine projected database is shaped using in-memory pointers. H-mine uses an H-struct new data structure for mining purpose known as hyperlinked structure. It has polynomial space complexity therefore more space efficient then FP-growth and also designed for fast mining purpose. Mining quantitative association rules based on a statistical theory to present only those that deviate substantially from normal data was studied by Aumann and Lindell et al. [8]. Zhang et al. [9] considered mining statistical quantitative rules. Statistical quantitative rules are quantitative rules in which the right hand side of a rule can be any statistic that is computed for the segment satisfying the left hand side of the rule.

三世。关联规则描述

首次提出了关联规则挖掘Agrawal和et al [10]。它可以被正式定义为:给定一个事务数据库DB, I = {il、i2 i3,…}是一组物品与n不同数据库中项集,每个事务在DB是一组T条目(即项集)。

定义1:让我= {il、i2 i3,…}是一组项目,然后D = {< Tid T > | T⊆我}是一个事务数据库,Tid在哪一个与每个事务标识符。T⊆我。

经典的先验的算法:

(1)Cl ={候选人I-itemsets};

(2)L1 = {c∈C1 | c.countKminsup};

(3)对(k = 2; Lk-1LM; k + +)开始

(4)Ck = apriori-gen (L k - 1);

(5)对所有事务t∈D开始

(6)Ct =子集(Ck, t);

(7)所有候选人c∈Ct

(8)c.count + +;

(9)结束

(10)路= {c∈Ck | c.countKminsup}

(11)结束

(12)回答=∪路;

关联规则挖掘是一个两步的过程:

1。找到事务数据库中的所有频繁项集。如果项集的支持X,支持(X) Kminsup,那么X是一个频繁项集。否则,X不是频繁项目集。

2。从频繁项集产生强关联规则。对于每一个频繁项集,如果B⊂, BLM,和支持(A) (B) Kminconf /支持,然后我们有关联规则B⇒(A - B)。第二步是相对容易,其生成算法可以找到的参考。目前集中在研究中找到高效算法的第一步。

四、问题描述

在先验的算法,从Ck路有两个步骤:(1)根据Lk-1修剪项集。(2)根据minsupport修剪项集。

首先,频繁1-itemsets发现的集合。这组来标示L1。L1用于查找L2,频繁2 -项集的集合,用于发现L3,等等,直到不再频繁k-itemsets可以找到,然后算法停止。周期的k,一组候选人k-itemsets生成。这组候选人Ck来标示。每个itemset Ck是由连接两个属于Lk-1频繁项集和只有一个不同的项目。在Ck的候选项集生成频繁集,和最终的频繁项集路必须Ck的子集。Ck应该在业务数据库中每一个元素来决定枯萎加入路。

先天的问题算法,生成候选项集的集合Ck Lk-1。每项集在Ck检测是否所有k-l子集构成大k - 1 itemset与否,如果一个k - 1项集Lk-1项集,这个k-l itemset的超级项目集可以被删除。即每次构成k itemset的,先天必须扫描所有Lk-1项集。由于许多以这种方式扫描多次大型数据库,识别过程的瓶颈是先验的算法。

先验的算法可能需要生成大量的候选人。每次当候选人代生成算法需要判断这些候选人频繁项集。冗余导致高频查询的操作,所以将消耗大量的资源是否在时间或空间。

FP-Growth算法

FP-growth算法被认为是最有效和高效的方法挖掘所有频繁项集没有候选人„年代一代。FP-growth综合使用了垂直和水平将数据库存储在主存数据库布局。而不是覆盖每项存储在数据库中,它存储从数据库中实际的交易在一个树结构,每个项目都有一个链表经历的所有事务,包括项目。这个新的数据结构用FP-tree [10]。另外每个节点存储一个计数器,它跟踪交易的数量通过该节点共享分支。也链接存储,指向下一个出现的FP-tree各自的项目,这样出现的所有项FP-tree相连。尽管如此,使用头表包含每个单独的项目支持和链接项FP树的第一次出现。FP-tree,所有项目设置在支持降序排列,因为通过这种方式,它是可预测的,这表示数据库保持尽可能小,因为所有更经常发生的商品排列接近FP-tree的根源,从而更容易被分享。

算法采用分而治之的策略挖掘频繁项集,如下:FP-growth首先压缩数据库代表频繁项目集的频繁模式树,或FP-tree itemset协会保留信息。下一步是把压缩数据库分成组条件数据库(一种特殊的投影数据库),每个与一个频繁项。最后,我的每一个单独的数据库。特别是FP-tree建设和矿业FP-tree FP-growth算法的主要步骤。

先验的和FP-Growth之间的比较研究

下面的表显示了先天和FP-growth之间的差异。

诉改进算法

该算法是基于改进的先天和频繁Pattern-tree结构支持计数。在一个巨大的事务性数据库就像零售商数据库是很常见,一些项目已出售或购买同时因此数据库必须包含各种事务包括相同的物品。因此通过这种类型的交易的好处,它必须是发现,频繁项集和删除数据库初始没有生成候选项集和许多数据库扫描,从而有效地利用内存和加强计算。

该算法是基于先天属性即。,all non empty subsets of the frequent itemsets are frequent. It has two procedures. In first procedure, locate those transactions which are frequently appearing in the database equal to or greater than min user defined support which is known as maximal frequent itemset. Then get all nonempty subsets of those maximal frequent itemset as frequent according to Apriori property. Examine the database to find 1-itemset frequent elements. Then it has to be found out as a lot of items which are 1-itemset frequent but not contain in maximal frequent transactions. Therefore trim the database by considering only those transactions which contain 1-itemset frequent elements from the database, but not include in the maximal frequent itemsets. Obviously the size of the trimmed or pruned database is smaller as compared to actual database in the average cases and no item left in best case.

第二步骤,将数据库作为输入,然后再次检查了数据库一旦为了找到1-itemset频繁和消除这些物品从事务不1-itemset频繁。然后创建频繁模式树只是削减了交易。以这种方式减少了内存问题频繁Pattern-tree因为数据库的大小是紧凑的在大多数情况下。在最好的情况下,不需要构造频繁Pattern-tree因为所有元素搜索在第一个程序。在最坏的情况下如果没有最大频繁交易存在,那么也只有第二个程序运行和计算性能是一样频繁Pattern-tree [11]。这个概念背后的基本目标是削减后的数据库搜索和寻找最大频繁项集和构造频繁Pattern-tree修剪FP-tree数据库从而降低内存的问题,使采矿过程快。详细的步骤如下:

详细算法

步骤1:

输入:数据库D,最小的支持

步骤1:2 -维数组;地方事务为2-dimmension数组与他们的重复计数。

步骤2:位置在订单的基础上增加每笔交易的模式长度。

步骤3:搜索的最大交易(k-itemset)从数组中数大于或等于最低支持称为最大频繁项集或事务。如果k-itemsets计数小于最小支持然后寻找k-itemsets (k - 1)下(k - 1)项集共同最大项目集等等,直到没有发现项集计数大于最小的支持。如果没有这样的交易然后去发现过程2。

步骤4:一旦发现最大频繁交易,比根据先天属性考虑所有的非空的子集是频繁。

步骤5:有剩余项集不包含在最大频繁项目集但他们频繁。因此发现所有频繁1-itemset并删除数据库只考虑那些事务包含频繁1-itemset元素,但不包括在最大频繁交易。

输出:部分或所有频繁项集,修剪数据库D1。

Procedure2:

输入:删除数据库D1,最低的支持

步骤1:从数据库搜索频繁1-itemset修剪;删除所有这些物品不1-itemset频繁。

步骤2:为我剩下的频繁项目集构建FP-tree遵循FP-tree算法的过程。

输出:剩余的频繁项集

六。实验结果

这是一个基于事务数据库,D,表2。有十个交易数据库,也就是说,| | = 10。我们用改进的先验的算法寻找频繁项集是2 d .假设最低支持。

步骤3:根据最大频繁项目集的先天属性子集也视为频繁,即。最大频繁项目集:{I1、I2 I3、I5}。即所有子集频繁(先天属性)。,{I1, I2, and I3}, {I1, I2, I5}, {I2, I3, I5}, {I2, I3}, {I2, I5}, {I1, I2}, {I1, I3}, {I1, I5}, {I3, I5}, {I1}, {I2}, {I3}.

步骤4:检查数据库搜索上述开采的支持。

步骤5:从数据库中找到1-itemset频繁,发现当频繁但不包括最大频繁项集。(可能有很多项目仍是不包括在最大频繁项集,在我们的案例中只有1项)。修剪的数据库通过只考虑事务包含预告itemset。

输出:一些频繁项集({I1、I2 I5}, {I2 I3、I5}, {I2, I3}, {I2, I5}, {I1、I2}, {I1, I3}, {I1, I5}, {I3、I5}, {I1}, {I2}, {I3}),删除数据库表13所示。

Procedure2:

输入:删除数据库,最小支持= 2

步骤1:找到频繁1-itemset从修剪或删除数据库支持= 2,发现I1不是频繁因此删除它。

交易成为:T2: I2预告和T4: I2,预告。

步骤2:构建FP-tree剩余修剪数据库中事务。

1。在这种情况下I2和我拥有相同的频率,因此它不需要放入L(降序排列的频率)。

2。为每个事务构造一个新分支。在这种情况下创建单独的分支,因为相同的事务。

3所示。构造条件模式基本只和FP -树项目预告。

项目- >预告;模式基础- > I2: 2;- > I2:2频繁模式树,频繁项目集- >预告,I2: 2

因此通过应用上述过程可以很容易地发现,unmin频繁项目集即。{预告,I2},一些早期的算法不能够找到[12]。现在所有的频繁项集在一个特定的数据库。

输出:剩下的项集({预告,I2})

因此剩下的频繁项集,不是由只挖掘最大频繁项集挖掘的FP增长过程还没有生成候选项集和有效利用内存,因为后修剪整个数据库很容易融入到内存。

在下一节中,我们将演示实验,我们已经检查执行新程序的效率。评估我们进行了几个实验通过使用现有的数据集。这些实验进行计算机酷睿2双核2.00 GHZ CPU、2.00 GB内存和80 GB硬盘。所有的算法都是在c++语言开发,测量的时间和内存的单位分别是第二和兆字节。

比较分析

时间比较

作为一个研究的结果,显示我们与先天的新技术的性能和FPGrowth算法。运行时间是时间去挖掘频繁项集。实验结果如图2所示。它表明,投影方案优于FP-growth和先验的方法。

为合成数据集包含大量的最大频繁项目集显示与新方法更好的结果如图3所示然后FP-tree先验的算法。在合成数据集有不同的事务考虑数据库和一些事务中发生多次发生大于最小的支持。挖掘频繁项目集的项目集仍然是开采的帮助第二过程的复杂性= FP-Growth算法,但是由于程序1整体复杂性降低,成为高效。

记忆比较

从图4很明显,推测的算法的内存消耗是先进的水平,因为它产生候选项集的支持。FP-tree内存消耗的支持先进水平附近的新方法,因为是一样的支持增加搜索重复的最大项目集的可能性大于最小支持少因此其工作大约是一样FP-Growth算法。

由于商店和先验的算法流程只非零项,需要修剪的大多数常见物品的报酬在最初几个传球。因此在更高层次支持新计划的表演和先验的接近。下级但它表明新方法表现良好支持水平利用内存。在这种情况下先天比FP-Tree消耗更多的内存和新方法由于其候选人生成问题。FP-tree方法执行比先天的但不是比的新方法。

七世。结论

在本文中,我们考虑时间和内存利用率作为创建算法的因素。几个实验来评估方案的性能对FP-growth和先天生成关联规则。据观察,算法的性能强烈依赖于支持水平和数据集的特性(性质和数据集的大小)和保证节约时间和内存的稀疏和稠密数据集。因此该算法产生完全频繁项集。这种方法不会产生候选项集和建筑FP-tree只修剪数据库容易融入主内存。因此节省了时间和空间,认为是一种有效的算法。

数据集运行时间和内存利用率的算法进行推测的。而该算法运行时间超过FP-growth执行较低的收集到的数据集的支持水平,判决最大频繁项集的概率是大型和高杠杆运行时间大约是FP-Tree一样。内存利用率也大约一样FP-Tree支持和较低表现良好支持更高。由于改进算法矿山没有候选频繁项集生成,查询频率下降约一半水平与先验的算法进行比较。数据库的大小减少;与此同时,存储空间和计算时间保存。

引用

Agrawal, R。,T. Imielinski and A. Swami, “Mining association rules between sets of items in large databases”, Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, pp. 207-216, May 25-28, 1993.
拉克什Agrawal Ramakrishnan Srikant。“快速算法挖掘关联规则”,20学报》国际会议上非常大的数据基地,圣地亚哥,智利,页。487 - 499年,1994年9月12 - 15。
h .姚明,H.J.汉密尔顿,矿业项目集实用程序从事务数据库,数据与知识工程、爱思唯尔科学出版社,59卷,第626 - 603页,2006年12月。
莫里斯·托Houtsma,阿伦•n .哲人“种面向集合的矿业在关系数据库中关联规则”,ICDEA¢95,第十一届国际会议的程序数据工程,页。男性,IEEE计算机协会,华盛顿特区,1995年美国。
j·s·公园,注:m . Chen Yu。,“An effective hash-based algorithm for mining association rules”, SIGMOD Ã¢ÂÂ95 Proceedings of 1995 ACM SIGMOD international conference on Management of Data, pp. 175-186, May 1995.
汉J,裴J,阴Y,没有候选人一代”“挖掘频繁模式,进行2000年ACM-SIGMOD国际会议管理的数据(SIGMODA¢00),达拉斯,得克萨斯州,1 - 12,2000页。
Pei.J。,Han.J., Lu.H., Nishio.S., Tang. S.,Yang. D. “H-mine: Hyper-structure mining of frequent patterns in large databases”, In Proceedings of International Conference in Data Mining, (ICDM), November 2001.
Aumann Y, Lindell Y”,统计理论量化关联规则”,在1999年国际会议上进行知识发现和数据挖掘(KDDA¢99),圣地亚哥,261 - 270年,1999页。
张H, Padmanabhan B, Tuzhilin,“发现的重大统计量化规则”,在2004年国际会议上进行知识发现和数据挖掘(KDDA¢04),西雅图,佤邦,374 - 383年,2004页。
A . Savasere大肠Omiecinski, s . Navathe”一个高效的算法在大型数据库中挖掘关联规则”,1995年国际研讨会论文集超大型数据基地(VLDB¢95),苏黎世瑞士,国立中央- 443,1995年9月。
盛Chai1,杨贾,杨成,“改善先天挖掘关联规则算法的研究”,2007年IEEE国际会议。