注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

瘋人院

lunatic asylum

 
 
 

日志

 
 

数据挖掘原理与算法(第三章)  

2010-01-19 12:59:36|  分类: 數據挖掘 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

第三章:关联规则挖掘理论和算法

关联规则挖掘是数据挖掘中最活跃的研究方法之一,最早是由Agrawal等人提出的(1993)。

当前对关联规则挖掘问题的研究主要有:关联规则挖掘理论的探索;原有算法的改进和新算法的设计;并行关联规则挖掘(Parallel Association Rule Mining);数量关联规则挖掘(Quantitive Association Rule Mining)等。

3.1、基本概念与解决办法

一个事务数据库中的关联规则挖掘可以描述如下:

I={i1i2... im}是一个项目集合,事务数据库D={t1t2tn}是由一系列具有唯一标识TID的事务组成,每个事务tii=12n)都对应I上的一个子集。

定义1:设项目集I1íII1在数据集D上的支持度是包含I1的事务在D中所占的百分比,即

supportI1= || {tD | I1ít } || / || D ||

定义2:对项目集I和事务数据库DT中所有满足用户指定的最小支持度(Minsupport)的项目集,成为频繁项目集(Frequent Itemsets)或大项目集(Large Itemsets)。在所有频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集(Maximum Frequent Itemsets)或最大项目集(Maximum Large Itemsets)。 

定义3:一个定义在ID上的形如I1TI2 的关联规则通过满足一定的可信度(Confidence)来给出。所谓规则的可信度是指包含I1 I2的事务数与包含I1的事务数之比,即

confidenceI1TI2= supportI1I2/ support( I1 )

其中I1I2  í II1I2 = F

定义4DI上满足最小支持度和最小信任度(Minconfidence)的关联规则称为强关联规则。通常我们所说的关联规则一般是指强关联规则。

关联规则挖掘问题可以划分为两个子问题:

<!--[if !supportLists]-->1  <!--[endif]-->发现频繁项目集(近年来的研究重点);

<!--[if !supportLists]-->2  <!--[endif]-->生成关联规则;

3.2、经典的频繁项目集生成算法分析

3.2.1、项目集空间理论(Agrawal

定理1:如果项目集X是频繁项目集,那么它的所有非空子集都是频繁项目集。

定理2:如果项目集X是非频繁项目集,那么它的所有超级都是非频繁项目集。

 

3.2.2、经典的发现频繁项目集算法

Agrawal等提出的Apriori算法,通过项目集元素数目的不断增长来逐步完成频繁项目集的发现。

 

算法1Apriori(发现频繁项目集)

输入:数据集D;最小支持数minsup_count

输出:频繁项目集L

<!--[if !supportLists]-->1       <!--[endif]-->L1 = { large1–itemsets };  //所有支持度不小于minsupport1-项目集

<!--[if !supportLists]-->2       <!--[endif]-->FOR k = 2Lk-1Fk++ DO  BEGIN

<!--[if !supportLists]-->3       <!--[endif]-->    Ck = apriori–genLk-1;   //Ckk个元素的候选集

<!--[if !supportLists]-->4       <!--[endif]-->    FOR  all transactions  tD  DO  BEGIN

<!--[if !supportLists]-->5       <!--[endif]-->        Ct = subsetCkt;   // Ct是所有t包含的候选集元素

<!--[if !supportLists]-->6       <!--[endif]-->        FOR  all transactions  cCt  DO  c.count++;

<!--[if !supportLists]-->7       <!--[endif]-->    END

<!--[if !supportLists]-->8       <!--[endif]-->Lk = { cCk | c.count minsup_count }

<!--[if !supportLists]-->9       <!--[endif]-->END

<!--[if !supportLists]-->10   <!--[endif]-->L = Lk;

 

算法1中调用了apriori–genLk-1),它是通过(k-1)-频繁项目集产生k-候选集。

算法2apriori–genLk-1  (候选集产生)

输入:(k-1)-频繁项目集Lk-1

输出:k-候选集Ck

<!--[if !supportLists]-->1       <!--[endif]-->FOR  all itemset p Lk-1  DO

<!--[if !supportLists]-->2       <!--[endif]-->    FOR all itemset q Lk-1  DO

<!--[if !supportLists]-->3       <!--[endif]-->        IF p.item1 = q. item1, p.item2 = q. item2, … , p.itemk-2 = q. itemk-2, p.itemk-1 < q. itemk-1  THEN  BEGIN

<!--[if !supportLists]-->4       <!--[endif]-->              c = pq;  //q的第k-1个元素连到p

<!--[if !supportLists]-->5       <!--[endif]-->              IF  has_infrequent_subset (c, Lk-1)  THEN

<!--[if !supportLists]-->6       <!--[endif]-->                  delete  c;  //删除含有非频繁项目子集的候选元素

<!--[if !supportLists]-->7       <!--[endif]-->              ELSE  add  c  to  Ck

<!--[if !supportLists]-->8       <!--[endif]-->         END

<!--[if !supportLists]-->9       <!--[endif]-->Return  Ck

 

算法2中调用了has_infrequent_subset (c, Lk-1),作用是判断c是否需要加入到k-候选集中。

算法3has_infrequent_subset (c, Lk-1) (判断候选集的元素)

输入:一个k-候选项目集c,(k-1)频繁项目集Lk-1

输出:c是否从候选集中删除的布尔判断

<!--[if !supportLists]-->1       <!--[endif]-->FOR  all (k-1)-subsets of c  DO

<!--[if !supportLists]-->2       <!--[endif]-->    IF  S?Lk-1  THEN  return TRUE

<!--[if !supportLists]-->3       <!--[endif]-->Return  FALSE

 

3.2.3、关联规则生成算法

在得到了所有的频繁项目集之后,可以按照下面的步骤生成关联规则:

<!--[if !supportLists]-->1       <!--[endif]-->对于每个频繁项目集l,生成其所有其所有的非空子集;

<!--[if !supportLists]-->2       <!--[endif]-->对于l的每个非空子集x,计算confidencex),如果configdencex)≥minconfidence,那么xTl-x)成立。

 

算法4:从给定的频繁项目集中生成强关联规则

输入:频繁项目集;最小信任度minconf

输出:强关联规则。

Rule-generate (L, minconf )

<!--[if !supportLists]-->1       <!--[endif]-->FOR  each frequent itemset lk in L

<!--[if !supportLists]-->2       <!--[endif]-->genruleslk , lk;

 

算法4的核心是genrules递归过程,它实现一个频繁项目集中所有强关联规则的生成。

算法5:递归测试一个频繁项目集中的关联规则

genruleslk: frequent k-itemset,  xm: frequent m-itemset

1X = { (m-1)-itemsets xm-1 | xm-1 in xm };

2FOR  each xm-1 in X  BEGIN

3    conf = supportlk/ supportxm-1;

4    IFconfminconfTHEN  BEGIN

5        print the rule “xm-1T( lk -xm-1), with support = support (lk), confidence = conf”;

6    IF m-1>1 THEN  //generate rules with subsets of xm-1 as antecedents

7    END

8END

 

关联规则生成算法的优化问题主要集中在减少不必要的规则生成方面;

定理3:设项目集XX1X的一个子集,如果规则XTl-X)不是强规则,那么X1Tl-X1)一定不是强规则。

这个定理告诉我们,在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定不是强规则的尝试。

定理4:设项目集XX1X的一个子集,如果规则YTX是强规则,那么规则YT X1一定是强规则。

这个定理告诉我们,在生成关联规则尝试中可以利用已知的结果来有效避免测试一些肯定是强规则的尝试。

 

3.3Apriori算法的性能瓶颈问题

Apriori算法有两个致命的性能瓶颈:

<!--[if !supportLists]-->1       <!--[endif]-->多次扫描事务数据库,需要很大的I/O负载;

<!--[if !supportLists]-->2       <!--[endif]-->可能产生庞大的候选集。

 

3.4Apriori算法的改进算法

为了提高Apriori算法的效率,出现了一系列改进算法,这些算法都是引入了相关技术,如数据分割、抽样等,在一定程度上改善了Apriori算法的适应性和效率。

 

3.4.1、基于数据分割(Partition)的方法

它的基本思想是,首先把大容量数据库从逻辑上分成几个互不相交的块,对每块应用挖掘算法生成局部的频繁项目集,然后把这些局部的频繁项目集作为候选的全局频繁项目集,通过测试它们的支持度来得到最终的全局频繁项目集。

 

该方法至少在两个方面有所提高:

<!--[if !supportLists]-->1       <!--[endif]-->合理利用主存空间;

<!--[if !supportLists]-->2       <!--[endif]-->支持并行挖掘算法。

 

该方法的理论基础可以通过下面的定理来保证:

定理5:设数据集D被分割成分块D1D2Dn,全局最小支持度为minsupport,假设对应的最小支持数为minsup_count。如果一个数据分块Di的局部最小支持数为minsup_conuti的话,那么局部最小支持数minsup_conuti应按如下方法生成:

minsup_conuti = minsup_count *|| Di || / || D ||

可以保证所有的局部频繁项目集成为全局频繁项目集的候选(即所有的局部频繁项目集涵盖全局频繁项目集)。

 

3.4.2、基于散列(hash)的方法

1995年,Park等提出了一个基于散列(hash)技术的产生频繁项目集的算法。由于寻找频繁项目集的主要计算是在生成2-频繁项目集L2上,因此,Park等引入散列技术来改进产生2-频繁项目集的方法。但是,理论上说,这种方法可以扩展到产生k-项目集(k>2)中。

 

算法思想是,把扫描的项目放在不同的Hash桶中,每队项目最多只能在一个特定的桶中,这样可以对每个桶中的项目子集进行测试,减少了候选集生成的代价。

 

3.4.3、基于采样(sampling)的方法

1996年,Toivonen提出了一个基于采样技术产生频繁项目集的算法。

 

算法思想是:先使用数据库的抽样数据得到一些可能成立的规则,然后利用数据库的剩余部分验证这些关联规则是否正确。

 

从本质上说,使用一个抽样样本而不是使用整个数据集的原因是效率问题。但是,它的最大问题是抽样数据的选取以及由此而产生的结果偏差过大,即存在所谓的数据扭曲(Data Skew)问题。

 

3.5、对项目集空间理论的发展

随着数据库容量的增大,重复访问数据库将导致性能下降。因此目前的研究集中在一下几个方面:

<!--[if !supportLists]-->1       <!--[endif]-->探索新的关联规则挖掘理论:突破Apriori算法,利用新的理论生成新的算法。

<!--[if !supportLists]-->2       <!--[endif]-->提高裁减项目集格空间的效率:如Close算法。

<!--[if !supportLists]-->3       <!--[endif]-->分布和并行环境下的关联规则挖掘问题。

 

3.5.1Close算法

1999年,Pasquier等提出了闭合项目集挖掘理论,并给出了基于这种理论的Close算法。实验证明,它对特殊数据是可以减少数据库扫描次数的。

 

Close算法基于这样的原理:一个频繁闭合项目集的所有闭合子集一定是频繁的;一个非频繁闭合项目集的所有闭合超集一定是非频繁的。

 

算法6Close算法

<!--[if !supportLists]-->1       <!--[endif]-->generators in FCC1 = { 1-itemsets }  //候选频繁闭合1-项目集

<!--[if !supportLists]-->2       <!--[endif]-->FOR i=1;  FCCi.grnerators = F;  i++ DO BEGIN

<!--[if !supportLists]-->3       <!--[endif]-->    closures in FCCi = F;

<!--[if !supportLists]-->4       <!--[endif]-->    supports in FCCi = 0;

<!--[if !supportLists]-->5       <!--[endif]-->    FCCi = Gen_Closure (FCCi)  //计算FCC的闭合

<!--[if !supportLists]-->6       <!--[endif]-->    FOR all candidate closed itermsets c ? FCCi  DO  BEGIN

<!--[if !supportLists]-->7       <!--[endif]-->        IF(c.support minsupport)  THEN FCi= FCi{c}; 

         //修剪小于最小支持度的项

<!--[if !supportLists]-->8       <!--[endif]-->    END

<!--[if !supportLists]-->9       <!--[endif]-->    FCCi+1 = Gen_Generator(FCi);  //生成FCCi+1

<!--[if !supportLists]-->10   <!--[endif]-->END

<!--[if !supportLists]-->11   <!--[endif]-->FC = iFCi(FCi.closure, FCi.support);  //返回FC

<!--[if !supportLists]-->12   <!--[endif]-->Deriving frequent itemsets(FC, L);

 

函数Gen_Closure (FCCi)产生候选的闭合项目集,用于频繁项目集的生成。

算法7Gen_Closure函数

<!--[if !supportLists]-->1       <!--[endif]-->FOR  all transactions t?D  DO  BEGIN

<!--[if !supportLists]-->2       <!--[endif]-->    Go = Subset (FCCi.generator, t );

<!--[if !supportLists]-->3       <!--[endif]-->    FOR  all generators p?Go  DO  BEGIN

<!--[if !supportLists]-->4       <!--[endif]-->        IF (p.closure = F)  THEN  p.closure=t;

<!--[if !supportLists]-->5       <!--[endif]-->        ELSE  p.closure = p.closure t;

<!--[if !supportLists]-->6       <!--[endif]-->        p.support++;

<!--[if !supportLists]-->7       <!--[endif]-->    END

<!--[if !supportLists]-->8       <!--[endif]-->END

<!--[if !supportLists]-->9       <!--[endif]-->Answer = {c? FCC| c.closure F};

 

函数Gen_Generator(FCi)实现Apriori算法的两个重要步骤:连接和修剪。

算法8Gen_Generator函数

<!--[if !supportLists]-->1       <!--[endif]-->FOR  all generators p? FCCi+1  DO BEGIN

<!--[if !supportLists]-->2       <!--[endif]-->    Sp = Subset(FCi.generator, p);  //取得p的所有i-项目子集

<!--[if !supportLists]-->3       <!--[endif]-->    FOR  all s?Sp  DO  BEGIN

<!--[if !supportLists]-->4       <!--[endif]-->        IF(p?s.closure)  THEN  //如果p是它的i-项子集闭合的子集

<!--[if !supportLists]-->5       <!--[endif]-->            Delete p from FCCi+1.generator;  //将它删除

<!--[if !supportLists]-->6       <!--[endif]-->    END

<!--[if !supportLists]-->7       <!--[endif]-->END

<!--[if !supportLists]-->8       <!--[endif]-->Answer = {c? FCCi+1}

 

函数Deriving frequent itemsets(FC, L)通过频繁闭合项目集得到频繁项目集

算法9Deriving frequent itemsets(FC, L)

<!--[if !supportLists]-->1       <!--[endif]-->k=0

<!--[if !supportLists]-->2       <!--[endif]-->FOR  all frequent closed itemsets c? FC  DO  BEGIN

<!--[if !supportLists]-->3       <!--[endif]-->    L||c|| = L||c||{c}  //按项的个数归类

<!--[if !supportLists]-->4       <!--[endif]-->    IFk<||c|| THEN  k=||c||;  //记下项目集包含的最多的个数

<!--[if !supportLists]-->5       <!--[endif]-->END

<!--[if !supportLists]-->6       <!--[endif]-->FOR (i=k; i>1; i--)  DO  BEGIN

<!--[if !supportLists]-->7       <!--[endif]-->    FOR  all itemsets  c? L DO

<!--[if !supportLists]-->8       <!--[endif]-->        FOR  all (i-1)-subsets of c  DO  //分解所有(i-1-项目集

<!--[if !supportLists]-->9       <!--[endif]-->            IFs! ?Li-1 THEN  BEGIN  //不包含在Li-1

<!--[if !supportLists]-->10   <!--[endif]-->                S.support = c.support;  //支持度不变

<!--[if !supportLists]-->11   <!--[endif]-->                Li-1 =Li-1 {s};  //添加到Li-1

<!--[if !supportLists]-->12   <!--[endif]-->            END

<!--[if !supportLists]-->13   <!--[endif]-->L = Li

 

3.5.2FP-tree算法

2000年,Han等提出了FP-tree算法,这个算法只进行2次数据库扫描,不使用候选集,直接压缩数据库成一个频繁模式树,最后通过这棵树生成关联规则。

 

FP-tree算法由两个步骤完成:

<!--[if !supportLists]-->1  <!--[endif]-->利用事务数据库中的数据构造FP-tree

FP-tree的构造过程中,将出现频度高的项目放在靠近根节点。

算法10FP-tree构造算法

输入:事务数据库DB;最小支持度阀值Minsup

输出:FP-tree,简称T

Build_FP-tree (DB, Minsup, T)

<!--[if !supportLists]-->1       <!--[endif]-->扫描事务数据库DB一次,形成1-频繁项表L(按照支持度降序排列);

<!--[if !supportLists]-->2       <!--[endif]-->创建T的根节点,以“root”标记。对于DB中的每个事务执行如下操作:对事务中的频繁项按照L中的顺序进行排序,排序后的频繁项表记为[p|P],其中p是第一个元素,P是剩余元素的表。调用insert_tree([p|P], T)将此元组对应的信息加入到T中。

 

insert_tree是对数据库的一个元组对应的项目集的处理,它对排序后的一个项目集的所有项目进行递归式处理直到项目表为空。

算法11insert_tree([p|P], T)

<!--[if !supportLists]-->1       <!--[endif]-->IFT有子女N使得N.项名 = p.项名 THEN  N的计数加1

<!--[if !supportLists]-->2       <!--[endif]-->ELSE 创建一个新结点N将其计数设置为1链接到它的父结点T并且通过结点链结构将其链接到具有相同项名的结点

<!--[if !supportLists]-->3       <!--[endif]-->如果p非空递归地调用insert_tree( P, N )

 

<!--[if !supportLists]-->2  <!--[endif]-->FP-tree中挖掘频繁模式的方法

FP-tree挖掘频繁集的基本思想是分而治之大致过程如下

<!--[if !supportLists]-->1       <!--[endif]-->对每个项生成它的条件模式基一个子数据库”,FP-tree中与后缀模式一起出现的前缀路径集组成),然后是它的条件FP-tree

<!--[if !supportLists]-->2       <!--[endif]-->对每个新生成的条件FP-tree重复这个步骤

<!--[if !supportLists]-->3       <!--[endif]-->直到FP-tree为空或者只含有唯一的一个路径此路径的每个子路径对应的项目集都是频繁集

 

算法12:在FP-tree中挖掘频繁模式

输入:构造好的FP-tree;事务数据库DB;最小支持度阀值Minsup

输出:频繁模式的完全集

方法:Call FP-growthFP-tree, null.

 

FP-growth通过递归调用方式实现频繁模式

算法13FP-growthTree, a

1IFTree只含单位路径P THEN  FOR路径P中结点的每个组合(记为b DO

     产生模式ba,其支持度support = b中结点的最小支持度;

2ELSE FOR each aiFP-tree的项头表(倒序) DO  BEGIN

2-1)产生一个模式b=aia,其支持度support = aisupport;

2-2)构造b的条件模式基,然后构造b的条件FP-tree Tree b;

2-3if Tree bF  THEN  call FP-growth(Tree b, b);

 

3.6、项目集格空间和它的操作

3.63.7是本书作者提出的一种关联规则挖掘的新理论,原始文献为:

毛国君,刘椿年。基于项目集格操作的关联规则挖掘算法。计算机学报,第25卷,第4期。2002

 

为了重复利用对数据库的扫描信息,把来自数据库的信息组织成项目集格(Set of Itemsets)形式,并且对项目集格及其操作代数化。

 

定义5:(项目集格)一个项目集格空间可以用三元组(ISp)来刻画,其含义如下:

项目定义域II = {i1, i2, , im}为所涉及项目的定义范围;

项目集变量集SS中的每个项目集变量形式为ISS = {IS1, IS2, … , ISn},其中ISi是定义在I上的项目集;

操作p:关于S中的项目集变量的操作集。

 

定义6:(项目集格上的集合操作)项目集间(上)的属于(?)、包含(í)、并(U)、交(∩)、差(-)等操作和普通的集合操作相同。

 

定义7:(项目集上的亚操作)设ISS1ISS2是定义在I上的来两个项目集的集合,IS是定义在I上的一个项目集,定义如下操作:

亚属于(?sub):ISI ?subSS1当且仅当$IS1?ISS1,使得ISíIS1

亚包含(í sub):ISS1 í sub ISS2 当且仅当"IS1? ISS1T IS1?sub ISS2

亚交(∩sub):ISS1sub ISS2 = {IS | IS?sub ISS1IS?sub ISS2}

亚并(U sub):ISS1 U sub ISS2 = {IS | IS?sub ISS1IS?sub ISS2}

 

亚操作的性质:类似集合间的性质,不难理解。

 

3.7、基于项目集操作的关联规则挖掘算法

3.7.1、关联规则挖掘空间

定义8:(关联规则挖掘空间)关联规则挖掘空间定义为一个五元组W=IDOUR),其含义如下:

I = {i1, i2, , im},为W所涉及的全体项目;

D = {t1, t2, , tn},W所基于的事务数据库;

O = {o1, o2, , ok},W上关于D的元素的操作集合;

U = {u1, u2, , up},W上用户给定的限制参数及约束条件;

R = {r1, r2, , rq},D中所蕴含的关联规则集。

 

3.7.2、三个实用算子

定义9:(考虑支持度下的项目集加入项目集格的操作)一个项目集IS加入项目集格ISS的操作算子joinISISS)描述为:

<!--[if !supportLists]-->1       <!--[endif]-->项目集格为ISS = ISSU {IS};

<!--[if !supportLists]-->2       <!--[endif]-->ISISS中的支持度按如下方法给出:

如果IS?ISS,则sup_conut(IS) = 1;

如果IS?ISS,则sup_conut(IS)++

算法14join(IS, ISS)

<!--[if !supportLists]-->1       <!--[endif]-->sup_count(IS) = 1; flog = 0;

<!--[if !supportLists]-->2       <!--[endif]-->FOR  all  IS1?ISS  DO

<!--[if !supportLists]-->3       <!--[endif]-->    IF  IS = IS1  THEN BEGIN

<!--[if !supportLists]-->4       <!--[endif]-->        sup_count(IS1)++;

<!--[if !supportLists]-->5       <!--[endif]-->        Flag = 1;

<!--[if !supportLists]-->6       <!--[endif]-->    END

<!--[if !supportLists]-->7       <!--[endif]-->IF flag = 0 THEN ISS = ISS U {IS}

 

定义10(频繁项目集格生成操作)利用ISISS中挑选频繁项目集并加入到频繁项目集格ISS*的操作算子make_fre(IS, ISS, ISS*)描述为:

" ISS*?sub {IS},如果IS*的支持数≧minsup_count,则IS*可能作为频繁项目集加入ISS*中。

算法15make_fre(IS, ISS, ISS*)

<!--[if !supportLists]-->1       <!--[endif]-->FOR  all IS*?sub{IS}  DO  BEGIN

<!--[if !supportLists]-->2       <!--[endif]-->    sup_count(IS*) = 0;

<!--[if !supportLists]-->3       <!--[endif]-->    FOR  all IS**?ISS  DO

<!--[if !supportLists]-->4       <!--[endif]-->        IF IS* íIS**  THEN

<!--[if !supportLists]-->5       <!--[endif]-->            sup_count(IS*) += sup_count(IS**);

<!--[if !supportLists]-->6       <!--[endif]-->    IF sup_count(IS*) minsup_count  THEN

<!--[if !supportLists]-->7       <!--[endif]-->        IF IS*?sub ISS*  THEN BEGIN

<!--[if !supportLists]-->8       <!--[endif]-->            prune (IS*, ISS*);   //把不需要的项目集从ISS*中裁减掉

<!--[if !supportLists]-->9       <!--[endif]-->            ISS* = ISS* U {IS*}

<!--[if !supportLists]-->10   <!--[endif]-->        END

<!--[if !supportLists]-->11   <!--[endif]-->    prune(IS*, ISS);  //把不需要的项目集从ISS中裁减掉

<!--[if !supportLists]-->12   <!--[endif]-->END

 

定义11:(频繁项目集格的裁减操作)利用项目集IS1裁减项目集格ISS1的操作算子pruneIS1ISS1)描述为:

"IS?ISS1,如果IS?sub{IS1},把ISISS1中剔除。

算法16pruneIS1ISS1

<!--[if !supportLists]-->1       <!--[endif]-->FOR  all IS?ISSDO

<!--[if !supportLists]-->2       <!--[endif]-->    IF IS?sub{IS1} THEN  ISS1 = ISS1 - {IS}

 

3.7.3、最大频繁项目集格的生成算法

算法17ISS-DM  Algorithm(最大频繁项目集生成算法)

输入:数据库D

输出:最大频繁项目集格ISS*

<!--[if !supportLists]-->1       <!--[endif]-->Input(minsup_count);

<!--[if !supportLists]-->2       <!--[endif]-->ISS?F; ISS*?F;

<!--[if !supportLists]-->3       <!--[endif]-->FOR  all IS?D  DO  BEGIN  //D的一个项目集IS

<!--[if !supportLists]-->4       <!--[endif]-->    joinISISS);

<!--[if !supportLists]-->5       <!--[endif]-->    make_fre(IS, ISS, ISS*);

<!--[if !supportLists]-->6       <!--[endif]-->END

<!--[if !supportLists]-->7       <!--[endif]-->Answer = ISS*;

 

3.8、改善关联规则挖掘质量问题

衡量关联规则挖掘结果的有效性应该从多种综合角度来考虑:

<!--[if !supportLists]-->1       <!--[endif]-->准确性;

<!--[if !supportLists]-->2       <!--[endif]-->实用性;

<!--[if !supportLists]-->3       <!--[endif]-->新颖性;

可以在用户主观和系统客观两个层面上考虑关联规则挖掘的质量问题。

 

在用户主观层面上,约束数据挖掘可以为用户参与知识发现工作提供一种有效的机制。

在系统客观层面上,除了使用“支持度-可信度”的关联规则挖掘度量框架外,还需要研究引入新的度量机制。

 

3.9、约束数据挖掘问题

3.9.1、约束在数据挖掘中的作用

1)聚焦挖掘任务,提高挖掘效率;

2)保证挖掘的精确性;

3)控制系统的使用规模。

 

3.9.2、约束的类型

1、单调性约束(Monotone Constraint

定义15:所谓一个约束Cm是单调性约束是指满足Cm的任何项目集S的超集也能满足Cm

 

2、反单调性约束(Anti-monotone Constraint

定义16:约束Ca是反单调约束是指对于任意给定的不满足Ca的项目集S,不存在S的超集能够满足Ca

 

<!--[if !supportLists]-->3  <!--[endif]-->可转变的约束(Convertible Constraint

定义17:如果一个约束C满足下面的条件,那么称它为反单调可转变的:

<!--[if !supportLists]-->1       <!--[endif]-->CS)既不是单调性约束,也不是反单调性约束;

<!--[if !supportLists]-->2       <!--[endif]-->若存在顺序R,使得经R排序后的I满足:任给S*?{suffix_S},有CSTC(S*)

 

定义18:如果一个约束C满足下面的条件,那么称它为单调可转变的:

<!--[if !supportLists]-->1       <!--[endif]-->CS)既不是单调性约束,也不是反单调性约束;

<!--[if !supportLists]-->2       <!--[endif]-->若存在顺序R,使得经R排序后的I满足:任给S*?{suffix_S},有CS*TC(S)

 

<!--[if !supportLists]-->4  <!--[endif]-->简洁性约束(Succinct Constraint

没看懂。

 

3.10、时态约束关联规则挖掘

参考资料:

毛国君,刘椿年。时态约束下的数据挖掘问题与算法。电子学报,2003Vol.31No.11:16901694

欧阳为民,蔡庆生。在数据库中发现具有时态约束的关联规则。软件学报,1999Vol.10NO.5

 

时态约束可以起到过滤过时数据、聚焦用户目标以及加速形成关联规则生成等作用。

 

3.11、关联规则挖掘中的一些更深入的问题

3.11.1、多层次关联规则挖掘

根据规则中涉及的层次,多层次关联规则可以分为同层次关联规则和层间关联规则:

如果一个关联规则对应的项目是在同一个粒度层次上,那么它是同层关联规则;

如果一个关联规则对应的项目是在不同的粒度层次上,那么它是层间关联规则。

 

目前,多层次关联规则挖掘的度量方法基本沿用了“支持度-可信度”的框架,对支持度的设置一般有两种:

<!--[if !supportLists]-->1       <!--[endif]-->统一的最小支持度;

<!--[if !supportLists]-->2       <!--[endif]-->不同层次使用不同的最小支持度。

 

多层次关联规则挖掘方法有以下几种:

<!--[if !supportLists]-->1       <!--[endif]-->自上而下方法:先找高层规则,再找它的下一层规则;

<!--[if !supportLists]-->2       <!--[endif]-->自下而上方法:

<!--[if !supportLists]-->3       <!--[endif]-->在一个固定层次上挖掘:

 

3.11.2、多维关联规则挖掘

OLAP中挖掘多维、多层关联规则是一个很自然的过程。

有两种常见形式:

<!--[if !supportLists]-->1       <!--[endif]-->维内的关联规则;

<!--[if !supportLists]-->2       <!--[endif]-->混合维关联规则。

 

3.11.3、数量关联规则挖掘

对于数值型的数据而言,在处理方法、技术和难度上都和布尔关联规则有差距,因此需要针对相关问题进行专门讨论。

目前数量关联规则挖掘问题重要集中在以下三个方面:

<!--[if !supportLists]-->1       <!--[endif]-->连续数值属性的处理:

两种基本方法:离散化方法;统计或模糊方法。

<!--[if !supportLists]-->2       <!--[endif]-->规则的优化:

对产生的大量冗余规则进行优化,找出用户真正感兴趣的规则集。

<!--[if !supportLists]-->3       <!--[endif]-->提高挖掘效率:

 

3.12、数量关联规则挖掘方法

目前对数量关联规则挖掘的研究主要基于两条技术路线:

<!--[if !supportLists]-->1       <!--[endif]-->通过对比较成熟的布尔关联规则算法的改进来解决数量关联规则问题;

<!--[if !supportLists]-->2       <!--[endif]-->用一种全新的思路和算法来解决数量关联规则挖掘问题。

讨论比较多和比较成熟的是第一种方法。

  评论这张
 
阅读(1480)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017