《基于集合运算的频繁集挖掘优化算法》由会员分享，可在线阅读，更多相关《基于集合运算的频繁集挖掘优化算法（8页珍藏版）》请在金锄头文库上搜索。
1、基于集合运算的频繁集挖掘优化算法摘要 挖掘关联规则是数据挖掘中一个重要的课题，产生频繁项目集是其中的一个关键步 骤。本文提出了一种基于集合运算的数据挖掘算法，并将该算法与经典算法进行比较。该算 法只需要对数据库扫描一遍。实验表明该算法的效率较好。关键词数据挖掘，关联规则，频繁项目集A Improved Algorithm Based on Sets Operation for Mining Large Item Sets Abstract Mining association rules is an important topic in data mining. Generating larg
2、e item sets is one of its keys. This paper presents a data mining algorithm based on sets operation and compares it with traditional algorithms. The improved algorithm only needs to scan the database once. Experiment results indicate that the new algorithm has good efficiency.Keywords: data mining,
3、association rules, large itern sets1. 引言数据挖掘也叫数据库中的知识发现。是从大型的数据库中发现潜在的、有价值的、能 被用户理解的概念和信息的过程。在数据挖掘研究中关联规则挖掘是一个非常重要的研究领 域关联规则挖掘起源于对超级市场“购物篮”问题的研究，主要是发现交易数据库 中项与项之间的关联关系。关联规则挖掘研究起初主要应用于诸如山场分析、决策制定、商 业管理等领域，但随着研究的不断深入，关联规则挖掘研究的应用越来越广泛，L1扩展到了 网络分析、天文学和生物学等领域。传统的关联规则挖掘算法采用的是通过多次扫描数据库来生成频繁项集的策略。这类算 法最有代表性
4、的就是R-Agrawal在1994年提出的Apriori算法3。本文利用集合运算来发 现频繁项集，只须扫描原事务数据库一次，并且不会产生大量的候选集，试验表明该算法是 有效的。2 .问题描述2. 1关联规则的挖掘关联规则的形式化描述4如下。定义1集合I=ii, i2,，im为标识符的集合，其中m为整数，ik(k=l,2, ni)称为 项目。顾客的一次购物可以用该顾客所购买的所有商品的名称来表示，称为事务，用符号T 来表示，很显然TWT(T是的子集)。一条事务仅包含其涉及到的项目，而不包含项目的具 体信息。所有事务的集合就构成了关联规则挖掘的数据集，称为事务数据库，用符号D来表.示，事务数据库的
5、记录数用D来表示。定义2项目集是由I中项目构成的集合。若项目集包含的项目数为k,则称此项目集 为k项目集。定义3对任意项目集X,若数据库D中s%的事务包含项目集X,则项目集X的支持率 为，记为support(X)=s%,其中包含项目集X的事务数称为项日集X的频度，记为count(X)=ca若项1=1集X的支持率大于或等于用户指定的最小支持率，则项目集X称为频繁 项目集或大项日集，否则项H集X称为非频繁项H集或小项日集。定义4关联规则是形如X=Y的规则，其中X、Y为项目集且XCY二如定义5在数据库D中，若s%的事务包含XU Y,则关联规则X二Y的支持度为s%；在数据库D中,若c%的包含项目X的事
6、务也包含项目Y,则关联规则X=Y的置信度为c%o定义6若关联规则X=Y的支持度和置信度分别大于或等于用户指定的最小支持度和最小置信度，则关联规则X二Y为强关联规则；否则称为弱关联规则。2. 2 Apriori 算法Apriori算法经过逐层迭代来计算出数据库中的频繁项集。第1次迭代计算出所有I- 项频繁集。它的每次迭代均经过三个步骤：1) 联结产生候选集，利用(k-1)项频繁数据项集Fz中产生k-项候选数据项集Ck。2) 剪枝。如果候选集中至少有一个子集不是频繁数据项集，则删除该数据项集合。3) 计算支持数。2. 3集合论(1) 集合的基本概念集合5是不能被精确定义的基本的数学概念。-般认为一
7、个集合指的是一些可确定的 可分辨的事务构成的整体。对于给定的集合和事物，成该可以断定这个特定的事物是否属于 这个集合。如果属于，就称它为这个集合的元素。集合可以有各种类型的事物构成。-般说来，集合的元素可以是任意类型的事物,一-个集合也可以作为另一个集合的元素。(2) 集合的基本运算集合的基本运算包括并、交、补、差等运算。下面就给出这些运算的定义。设A, B为集合，E是全集。AUB的并集定义为：AUB= (x I xeA 或 xcBAAB的交集定义为：AAB= (x I xeA 且 xeB人的补集定义为：A = x I xeE且xWBA-B的差集定义为：AB= (x I xwA 且 xWB性质
8、1频繁数据项集的所有子集是频繁的。性质1是频繁数据项集上交运算封闭性的结果。这条性质为在日底向上搜索频繁数据项 集的过程中，采用删除策略提供了理论基础。在挖掘2-项集及k-项集(k2)时，所有频繁项集的非空子集也一定是频繁的，即频繁 项集的任何非空子集都有可能有最小支持度。所以Apriori算法使用了一种联结规则来产生 候选集，通常我们可以这样定义这种规则运算：Lk*Lk=(pUq 其中，p, qe Lk , p. itemi = q. itenii，p. itenvi = q. item support (Y) o 如果数据项集X是数据项集Y的子集，那么Y的支持数一定等于或小于X的支持数。3
9、. 改进的算法及其描述3. 1改进算法改进算法主要是针对发现频繁集这一阶段进行改进的。改进算法思想主要是基于集合论 的。下而给出改进算法的形式化描述：Li = large 1-sets ;/此处 Li 由 Itemset 集、Tset 集和支持数 support 组成。For ( k = 2; Lk-i H 0; k+) do beginCk = gen ( Lk-j) :/产生k-项频繁集endAnswer = Uk Lk;其中gen函数是以L-作为输入的，其结果可直接生成k-项频繁集。gen函数实现如 下：gen ( Lk-i) (Ck =( Lk-i. Itemset * Lk-i. I
10、temset / 根据定义(1.1)产生候选集Tk =Lk-!.Tset nU-i.Tset)/事务支持集合作交运算 For all candidates c e Ck doc. support二Count (c. Tk)；计算每一项的支持数If c. support minsup then delete c endend3. 2应用实例我们以表1中的事务数据库为例进行阐释说明。表1 一个简单的事务数据库A simple transaction database事务TID项集 ItemsetTi1,3,4t21,2,3,4,5t32,3,4t41,2,3,6t54,5,6t62,346(1)扫
11、描一遍事务数据库，建立如卜-数据摩表2。之所以要生成这样的表，最大的优势在于 方便计算候选集项目的支持数。表2新建立的数据库表Xcvv creation database项集 Itemset事务支持集Tset12(T2, T3, Ti, Te)3(Ti, T2, T3, Ti, To)4(Ti, T2, T3, Ts, Td5(t2, t5)6L, T5, T6)(2)根据库表2,计算事务支持集Tsct中各行元素的个数(即事务支持数)，然后删除 那些支持数小于给定阈值的项集.这样就可得到1-项频繁集。表2中因为计算项日集5的 支持数为2达不到阈值，故将其删除。结果见表3。表3 1-项频繁集On
12、e length of large item sets项集 Itemset事务支持集Tset支持数Support1, T.J32Tz, T3, Ti, To)43(Ti, T2, T3, Ti, To)54( Tl, ?2, T3, T5, Tg )56(Ti, E, L3(3) 根据得到的1-项频繁集，项目集两两作并运算，其对应的事务支持集Tset两两作交运 算求出交集，然后计算每项事务支持集元素的个数，删除那些支持数小于给定阈值的项集, 这样我们就得到2-项频繁集。最终得到表4。表4 2-项频繁集项集Ttemset事务支持集Tset支持数Support1,3L, T2, TJ3(2,3T2
13、, T3, T4, Tg)42,4(T2, T3, K)33,4Ti, T2, Ts, Tg)4Two length of large item setsApriori算法中 算L2*L2,可得到 对应的事务支持 质上，这时L2*L2 根据 的定义(1.1)计 3-项候选集，其 集作交运算。实就是项集作集合的交与并的运算。在本例中，仅有2, 3与2, 4符合定义(3. 1), 2, 3)与2, 4作并运算可得3一项候选集2, 3, 4)；其对应的事物支持集为T2, L, L, Tc A T2, T3, = 1、2, T3, Tg,计算支持数为3,等于给定最小支持数阈值，故应保 存该项集；最终得
14、到3-项频繁集如表5所示。表5 3-项频繁集Three length of large item sets项集 Itemset事务支持集Tset支持数Support2, 3,4(T L, Tg)3(5)到此我们看到项集3-项频繁集已无法产生4项频繁集，频繁集挖掘算法至此结束。4. 算法实现和性能分析下面给出了论文改进算法在超市系统中定义的两个结构体。Public Type Spswrsspidset () As String商品项目集saleidset () As String销售事务集Encl TypePublic Type Spsetsupsupport As Integer 支持数spidset （） As String商品项目集End Type图1示意了数据在内存中的存储。系统定义一个结构体数组和I, J两个变量作为指示指 针。通过对指针I, J进行循环操作即可模拟表的联结。spidset saleidI 11, Ti)J 22(T?, T3, Ti, To)33(Ti, T2, T3, T, To)44(Ti, T2, T3, T5, Tg)55作,Ts)66(t
