多维关联规则数据挖掘在税务数据分析中的研究与应用(3)

第二章 关联规则概述

关联规则挖掘是数据挖掘领域中最活跃的研究方法之一。关联规则概念是有

Agrawal等最先提出（1993）[1]。关联规则最早提出是针对购物篮问题，目的是为通过发现顾客放入购物篮中不同商品之间的联系，分析顾客的购买习惯，从而来科学的指导进货、库存、货架设计等商务决策。关联规则的挖掘是一种无监督的学习过程。在这之后，众多的研究者对关联规则的挖掘问题进行了大量的研究。涉及关联规则理论的探索、原有算法的改进、新算法的设计、应用领域的开拓等。在提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面，许多学者进行了不懈的努力。

2.1 关联规则的基本概念和问题描述

? 基本概念

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

定义2.1[13] 设I={ i1,i2,… , im} 是一个项目集合，事务数据库D是数据库事务的集合，其中每个事务T是项的集合，T?I。每个事务有一个标志符，记为TID。

13]

定义2.2[ I中的任何子集称为项集（Itemset）。设X为一个项集，|X|=k，则称集合X为k-项集。 事务T包含X当且仅当X?T。

定义2.3[13]支持度。 数据集D中包含项集X的事务数称为项集X的频率或支持度，记为?x，项集X的支持度，记为：Support(X).

Support(X) =

?x|D|?100% (2.1)

其中|D|是数据集D中的事务数。若Support(X)不小于用户指定的最小支持度（记作：Min_Sup），则称X为频繁项目集，否则称X为非频繁项目集。

定理2.1[13]（向下封闭定理），设X，Y是数据集D中的项目集。

1.若X?Y，则Support(X) ?Support(Y)

2. 若X?Y，如果X是非频繁项集，则Y也是非频繁项集 3．若X?Y，如果X是频繁项集，则Y也是频繁项集

Y?I 一个关联规则是形如X=>Y的蕴涵式，这里X、Y都是项集，且X?I，

，并且X?Y??。X，Y分别称为关联规则X=>Y的前提或前件（LHS）和

11

结论或后件（RHS）。

以下我们给出关联规则相关的几个概念[14] 定义2.4 规则支持度（Support）。 规则X=>Y在数据库D中的支持度（Support）是数据集中同时包含X和Y的事务数和所有事务数之比，记为Support(X=>Y).设|D|为数据库中数据总数，即

Support(X=>Y) =|{T:X?Y?T,T?D}|/|D|= Support(X?Y)) (2.2) 支持度表出了X和Y这两个项集在所有事务中同时出现的概率。

通常用户根据挖掘需要指定的最小支持度记为Min_Sup。支持度是对关联规则重要性或适用范围的衡量，支持度越大则该规则越重要，应用范围越广。 定义2.5 规则可信度（Confidence）。 规则X=>Y在数据库D中的支持度是数据集中同时包含X和Y的事务数和包含X的事务数之比，它用来衡量关联规则的可信程度。记为Confidence(X=>Y)，既

Confidence(X=>Y)= |{T:X?Y?T,T?D}|/|T:X?T,T?D}| =

Support(X?Y) (2.3)

Support(X) 通常用户根据挖掘需要指定的最小置信度记为Min_Con。 定义2.6期望置信度（Expected Confindence）。规则X=>Ｙ的期望置信度是数据库D中的包含Y的事务数和所有事务数之比期，记为Exp_Con(X=>Y).设|D|为数据库中数据总数，即

(Y)) (2.4) Exp_Con(X=>Y)=|{T:Y?T,T?D}|/|D|= Support描述了在没有任何条件影响情况下，物品Ｙ在所有事务中出现的概率

定义2.7 强关联规则。如果Support(X=>Y) ?Min_Sup, 且Confidence(X=>Y) ?Min_Con,则称关联规则X=>Y为强关联规则。

这既是我们需要挖掘的关联规则。 ? 问题描述

一般的，关联规则挖掘问题可以划分成两个子问题： (1) 发现频繁项目集

通常由用户给定最小支持度（Min_sup），寻找所有频繁项目集（Frequent Itemset）。而这些频繁项目集可能具有包含关系。我们只关心那些不被其他频繁项目集所包含的所谓的频繁大项集（Frequent Large Itemset）的集合。这些频繁大项目集形成了关联规则的基础。 (2) 生成关联规则

通过用户给定的最小可信度Min_Con, 在每个最大频繁项目集中，寻找可信度不小于最小可信度的关联规则。 对于子问题（２），只需要在每个频繁大项目集中逐一匹配规则并进行Confidece(X=>Y) ?Min_Con 的测试就可以了，相对来说这部分的工作较简单、容易。所以关联规则挖掘的总体性能一般由第一步决定。

12

2.2 关联规则分类

关联规则按不同的标准可以有多种分类方法。

(1)按规则中所处理的值的类型，关联规则可以分为布尔关联规则和量化关

联规则。

? 布尔关联规则只是考虑项集中的值只涉及出现与不出现两种情况，

其运算规则可以采用布尔代数中的布尔运算。

? 量化关联规则既它描述的是量化的项或者属性之间的关联。在这种

规则中，一般对项或属性的量化值划分为区间，将其离散化。如下面是量化关联规则的一个例子。其中Ｘ代表顾客变量。其age和income已经被离散化。

Age(X,”30-38”) ∧ income(X,”5000以上”) => buys(X,”轿车”) (2.5) (2)按规则中涉及的数据维，可以分为单维和多维关联规则。

? 单维关联规则指关联规则中的项或属性只涉及一个维。它反映了同

一个属性内部不同实例之间的关系。挖掘对象一般都是面向某一个特定主题的数据项集。

例如，商场中顾客的购买物品项集{电视机、牛奶、面包、皮鞋?},

我们可能发现单维关联规则为:

buys(X,”牛奶”) => buys(X,”面包”) (2.6)

? 如果规则涉及的维有两个或者多于两个的都被认为是多维的关联规

则。

buys(X,”牛奶”) => age(X,”20…29”) (2.7) 规则(2.7)涉及了两个谓词，则是一个多维的关联规则。

(3) 按规则中数据涉及的抽象概念层次，可以分为单层关联规则和多层关联

规则

? 在单层关联规则中，所有的变量没有涉及不同的概念层的项或属性。

在规则（2.8）中的“牛奶”和“面包”是属于相同概念层的。 buys(X,”牛奶”) => buys(X,”面包”) (2.8) ? 在多层关联规则中，不同的项或属性涉及不同的概念层次。在规则

（2.9）中的“光明牌牛奶”的概念层次比“面包”的概念层次低，属于不同的概念层次的。

buys(X,”光明牌牛奶”) => buys(X,”面包”) (2.9)

2.3 经典的关联规则算法分析

自Agrawal等人于1994年提出了Apriori算法以来，这个算法已成为了最为经典的关联规则挖掘算法。它使用了一种称为逐层迭代的侯选产生测试的方法（candidate generation and test）的方法，从小到大的顺序来寻找频繁项集。其核心思想被其他许多算法引用。所以本文在这里对该算法先进行介绍和分析，作为我们后续研究的基础。

13

2.3.1 Apriori算法的理论基础

Apriori算法使用了定理2.1中的结论，既频繁项集的向下封闭性。如果项集X是频繁项集，则其所有的子集都是频繁项集；如果X是非频繁项集，则其所有的超集(Superset)都是非频繁项集。算法使用该性质来有效的修剪侯选项集，来提高挖掘的时间效率。这被称为Apriori性质。由此，可以采用迭代方式按项集从小到大的顺序寻找频繁项集，k-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合。该集合记为L1，L1用于找频繁2-项集的集合L2，如此下去，直到不能找到频繁K-项集Lk。其算法如下：

算法：Apriori 使用根据侯选生成的逐层迭代找出频繁项集 输入：事务数据库Ｄ；最小支持度阈值Min_Sup 输出：D中的频繁项集L

(1) L1=find_frequent_1-itemsets(D); (2) L=?;

(3) for(k=2;Lk-1 ≠?；k+1) {

(4) Ck=apriori_gen(Lk-1,Min_Sup);

(5) for each transaction t?D //scan D for counts

(6) Ct=subset(Ck,t); //get the subsets of t that are candidates (7) for rach candidate c?Ct (8) c.count++; (9) }

(10) Lk = {c?Ck|c.count/|D|≥Min_Sup; (11) }

(12) return L=?kLk

(13) R=generate_rule(L); (14) return(R);

从频繁(K-1)-项集中生成侯选K-项集的过程如下： procedure apriori_gen(Lk-1;Min_Sup) //侯选集产生 (1)Ck=?;

(1) for each itemset l1?lk?1 (2) for each itemset l2?lk?1

(3) if (l1[1]=l2[1] ∧l1[2]=l2[2]∧…∧ l1[k-2]=l2[k-2] ∧ l1[k-1]

(5) if has_infrequent_sunset(C,lk-1) then (6) delete C;

14

(7) else add C to Ck; (8) }

(9) return Ck

procedure has_infrequent_sunset(C,lk-1) –利用先验知识判断是否需要加入侯选集 (1) for each (k-1)-subset s of c (2) if s?Lk?1 then (3) return TRUE

(4) return FALSE

2.3.2 Apriori算法分析

虽然Apriori算法利用向下封闭性来获得较出色的性能，但是其仍然存在以下的缺陷：

? 多次扫描数据库。需要较大的I/O负载。对于每次K循环，侯选集Ck

中每个元素都必须扫描数据库一次，通过模式匹配计算项集的支持度，最后来验证其是否能加入Lk，这需要大量的I/O开销。例如要去发现一个长度为100的频繁项集，那么算法则至少需要扫描事务数据库100遍。

? 可能产生巨大的侯选集。由Lk-1产生k-侯选集Ck是按指数增长的。例

如如果1-频繁集集合包含104个侯选项集，则可能产生107个元素的2-侯选集。如此大量的侯选集的极大的存储空间和计算时间。

2.4 遗传算法

遗传算法（Genetic Algorithm-GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国的Michigan大学的J.Holland教授于1975年在发表的《自然系统和人工系统中的适应问题》（“Adaptation in Natural and

[15]

Artificial System”）一书中被首先提出的。随后遗传算法被广泛的应用于组合优化问题求解、自适应控制、规划设计、机器学习和人工生命等领域。

2.4.1 遗传算法的生物学理论

生命是进化的产物，是经过了漫长的生物进化历程，从低级、简单的生物类型逐渐发展成为高级、复杂的生物类型，生物进化的原因有各种不同的解释，其中达尔文的自然选择学说最具有代表性。

自然选择学说认为，（1）遗传。是指父代将自己的部分生物信息传给子代，而使在两代之间在性状上存在相似的现象。这使生物物种保存了该物种的特性，稳定繁衍。（2）变异。是指父代与子代之间、以及子代的个体之间，在性状上或多或少地存在差异的现象。变异使生物的性状发生改变，从而能适应不断变化的环境而向前不断发展。它是生物生命多样性的根源。遗传和变异是决定生物进化的内在因素。（3）适者生存。生物要生存下去就必须进行生存的斗争。而在生存

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库多维关联规则数据挖掘在税务数据分析中的研究与应用(3)在线全文阅读。