一种基于主属性判定的关联规则挖掘约简算法*

熊中敏，汪 博，陶 然，郑宗生，陈 明，2

(1.上海海洋大学信息学院，上海 201306；2.农业部渔业信息重点实验室，上海 201306)

1 引言

关联规则挖掘虽然已经得到大量的应用，但在实践中仍然存在令人不满意的地方，比较典型的问题是在数据库的挖掘过程中会得到大量的规则，导致用户无所适从[1]。如何约简规则集的大小，使得到的规则数量减少且是用户想要的，是影响到关联规则挖掘项目能否有效实施的问题。

关联规则挖掘算法基本上是以Apriori算法为基础的一系列改进算法。算法的核心思想是计算频繁项集，即统计数据项出现的概率是否大于事先设定好的最小支持度，由于每次都要扫描整个数据库，这个计算过程非常耗时。很多国外研究者提出了改进的措施，对事务数据库不进行多次扫描就能产生同样的候选集[2 - 5]。这些算法虽然计算效率有所提高，但需要同时提高Apriori算法框架中的参数设定值，即比较大的最小置信度和最小支持度，或者设置一些数据约束，算法的效率才能有明显改善。

国内学者也展开了相关的技术研究[6 - 13]，主要是算法的理论研究，注重采用新的技术方法提高算法的效率；另外则是应用研究，将关联规则分析方法引入到一些行业，得到原来不能得到的分析结果。这2类研究大多数没有考虑规则集的约简问题，另外一类理论研究和规则集的化简有关[11]，主要是找到最小置信度之外的一种新的评价关联规则的测度，然后通过测度值重新进行关联规则的选择。而本文从Apriori算法挖掘出的关联规则的结构分析出发(即利用数据库模式规范化中“局部函数依赖”这种依赖结构分析出冗余信息的频繁出现会导致没有实际价值的冗余信息被基于Apriori算法的关联规则挖掘处理为频繁项和相应的关联规则)，没有引入新的评价测度，分别基于数据库模式设计中的主属性和频繁(K+1)项集中新增属性对生成的关联规则的影响，提出约简关联规则集的算法。所以，本文的研究角度有别于上述文献的算法，而且利用本文提出的算法约简关联规则后，还可以进一步利用上述新的规则评价测度重新评估并选择关联规则。

关联规则挖掘已经获得巨大的发展，但面临着新的挑战:现有的挖掘方法不仅得到的规则过多，而且还包含了没有什么关系的规则[1]。本文提出的化简关联规则集的算法，正是针对上述关联规则急需解决的问题，但本文的研究方向不是如何改善算法在计算频繁项集的执行效率，而是在不改变基于Apriori算法的关联规则挖掘中的最小支持度和最小置信度的条件下，通过对关联规则进行结构化分析，简化挖掘到的关联规则集。

2 相关知识

2.1 规则分析方法

从海量的数据中挖掘隐含的知识，这是数据挖掘发展的目标和动力，也是很多大型企业或公司越来越关注并应用数据挖掘技术的原因。关联规则最初是用来研究顾客在超市中购买的商品有无关联性的问题，这就是广为传颂的关联规则挖掘故事“啤酒和尿布”，这种隐藏在数据中的联系可带来巨大的商业价值。现在随着联机分析处理OLAP(OnLine Analytical Process)技术的日趋成熟与广泛运用，OLAP技术与关联规则同时使用的方法已经成为非常受关注的研究方向。

关联规则常用表达为：(X⟹Y，支持度=s，置信度=c)，在表达式中X是规则的前提条件，Y是规则的结论，s是包含了规则的前提条件的数据项在数据库事务集中出现的次数占整个事务集中数据项个数的百分比，c是在数据库事务集中规则前提条件和结论同时出现的次数占规则前提出现次数的百分比。显然，支持度表示规则的频度，置信度表示规则的强度。

关联规则挖掘的理论基础是Apriori算法[7]。基于Apriori算法的关联规则挖掘过程以频繁项集的计算为基础，统计超出支持度阈值的项集，统计过程包括以下2个步骤：

(1)首先利用递推公式设计一个增量计算方法由“K-项集”计算“K+1-项集”，然后在“K+1-项集”中采用剪枝策略即Apriori性质(如果一个候选项是频繁的，那么它的任一个非空子集也是频繁的)过滤其中的元素，直到计算的候选项集为空，则终止计算。

(2)通过设置的置信度阈值利用转换规则，由计算得到的频繁项集简单地推导出对应的关联规则。即对每个计算出的频繁项L产生它的所有非空子集，然后对L的每个非空子集S，如果L在数据库事务集中出现的次数与S在数据库事务集中出现的次数的比值不小于置信度阈值，则产生一个关联规则“S→L-S”。

2.2 关系模式规范化中的关键字及主属性

选取一个比较优化的关系模式是关系数据库在规范化设计中需要考虑的现实问题。数据依赖、范式和模式设计方法是规范化设计的理论所包含的内容。数据依赖是规范化设计的核心，它研究数据之间的联系，范式是数据库模式设计要达到的标准，模式设计方法是为自动化设计服务的。关系数据库是否具有完整性和一致性，模式规范化理论起着决定性的作用。在数据库中，属性值之间会产生联系，例如每个学生只有一个姓名，每门课程只有一个任课教师，每个学生学一门课只能有一个成绩等。我们将这类联系称为函数依赖FD(Functio- nal Dependency)。

定义1[14]设有关系模式R，X和Y是属性集U的子集，函数依赖是形为X→Y的一个命题，只要r是R的当前关系，对r中任意2个元组t和s，都有t[X]=s[X]蕴涵t[Y]=s[Y]，那么称FDX→Y在关系模式R中成立。

函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。数据库设计者可以对现实世界作强制的规定，例如，规定不允许同名人出现，函数依赖“姓名→年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组。

定义2[14]设关系模式R的属性集是U，X是U的一个子集。如果X→U在R上成立，那么称X是R的一个超关键字。如果X→U在R上成立，但对于X的任一真子集X1都有X1→U不成立，那么称X是R上的一个候选关键字。

在实际使用中，经常要判断能否从已知的FD集F中推导出X→Y，即从FD集F推导出的所有函数依赖形成的集合F+是否包含X→Y，从F求F+是一个指数级问题，而求属性集闭包则是一个多项式级时间问题[14]。

定义3[14]设F是属性集U上的FD集，X是U的子集，那么(相对于F)属性集X的闭包用X+表示，它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合：X+={属性A|X→A在F+中}。

定理1[14]X→Y能用FD推理规则推出的充分必要条件是Y⊆X+。

设属性集X的闭包为X+，其计算过程如算法1所示[14]。

算法1求属性X相对于FD集F的闭包X+

输入：属性X,FD集F。

输出：X相对于F的闭包X+。

{X+=X;

do{ifF中有某个FDU→V满足U⊆X+then

X+=X+∪V;}

while(X+有所改变);

}

定义4[14]如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是第一范式1NF(First Normal Form)的模式。

1NF是关系模式应具备的最起码的条件。

定义5[14]如果A是关系模式R的候选键中属性，那么称A是R的主属性；否则称A是R的非主属性。

定义6[14]对于FDW→A，如果存在X⊂W有X→A成立，那么称W→A是局部依赖(A局部依赖于W)；否则称W→A是完全依赖。

定义7[14]如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式2NF(Second Normal Form)的模式。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。

3 基于主属性判定的关联规则分析

3.1 数据模式中冗余信息的频繁出现

例如，关于选课信息数据库的规范化关系模式(带下划线的字段为关键字)为：

学生(学号，姓名，年龄，性别)；课程(课程号，课程名，教师名)；选课(学号，课程号，成绩)。

在查询选课信息时，通常会采用如下的数据视图：

Create view course-view as

Select 选课.学号,选课.课程号,学生.姓名,学生.年龄,学生.性别,课程.课程名,课程.教师名,选课.成绩

From 学生，课程，选课

Where选课.学号=学生.学号 and选课.课程号=课程.课程号

虽然在规范化的设计中教师“张三”主讲课程“线性代数”在数据库中存储的是一条记录，但在综合查询信息时假设有25个同学选了这门课，那么“张三主讲线性代数”冗余出现25次，即达到了关联规则挖掘的频繁度而成为频繁项。但是，显然我们只关注学生自主选课的频繁性，即“线性代数”课程被多少学生选择，而不是“张三主讲线性代数”这样频繁出现的冗余信息，也就是说，通过频繁项计算后的关联规则挖掘可以得到“张三⟹线性代数”这样的关联规则。但是，实际上在数据库概念设计实体关系ER(Entity Relationship)建模时就可以确定“张三主讲线性代数”这样的实体关系，即这种模型可以确定的关系已经没有必要再经过关联规则挖掘算法得到，否则只会增加挖掘到的规则集的规模，使得用户理解并使用规则的难度更大。

同样地，如果一个学生选了10门课，则他的姓名、年龄和性别这样的冗余信息也会频繁出现10次，显然关联规则挖掘出的频繁项不应该是这样频繁出现的冗余信息。

根据定义6可知，在上述视图中存在局部依赖，虽然上述关系模式符合2NF范式，即消除了局部依赖，但这些规范化的表通过连接操作形成完全的信息后出现了局部依赖，同时出现了冗余信息，而这些频繁出现的冗余信息并不是我们想关注的数据中隐藏的具有一定关联的频繁项。事实上我们在数据存储时是通过模式规范化分解避免这些冗余信息的频繁出现，只不过是在用户查询的外模式即视图级别的信息展示时通过规范化表之间的连接使得这些冗余信息频繁出现了(冗余信息的频繁出现并没有数据上的挖掘价值，只是一种完全信息的展示)。

3.2 基于属性闭包求一个候选关键字

由3.1节的分析可知，冗余信息频繁出现的原因是FD集中出现的局部依赖，而根据定义6判断是否有局部依赖存在，其实就是判断是否存在一个候选关键字中包含的主属性为左部的函数依赖，所以判定主属性是个关键问题，现有教材[14]中只有主属性的定义(见本文定义5)，并没有提供如何判定主属性的方法。由文献[15，16]可知，求全部主属性如同求所有候选关键字问题都是NP难题，为此，本文提出了一种基于一个候选关键字进行验证的算法来判定主属性，从而完成基于主属性判定的关联规则挖掘算法的设计与实现。

算法2求关系R的一个候选关键字X

输入：关系R的属性集U，FD集F。

输出：候选关键字X。

{X:=U;

调用算法1求X的闭包X+；//X一个超关键字

Old_X+:= X+;

Foreachx∈X并按出现在X中的先后次序do

{X:=X-x;

调用算法1求X的闭包X+；

ifOld_X+≠X+thendo/*推导的闭包发生变化即变小了，说明删除的属性为主属性，即当前X不再是关键字*/

{X:=X∪{x};}/*主属性不能删除*/

}

return(X)}

定理2算法2正确地求出了关系R的一个候选关键字X。

证明很显然关系R的所有属性形成的集合U满足U→U，由定义2 可知,U就是R的一个超关键字，由于算法2 删除了超关键字中的所有非主属性，根据定义2可知最后求得的X即为候选关键字。

□

3.3 频繁项为主属性的识别方法

由于关联规则挖掘算法Apriori的关键步骤是计算出频繁项集，然后根据转换规则和置信度自动生成关联规则，所以如果能判断频繁项是否来自于局部依赖导致的冗余信息的频繁出现，就能避免生成不必要的关联规则，从而达到约简关联规则集的效果。

根据定义2可知，候选关键字能唯一决定一条记录，即不同的关键字和所决定的属性值只能频繁出现1次，故而可以认为通过关联规则挖掘算法Apriori计算出的频繁项不会包含候选关键字，除非设置频繁度为1，即只出现1次，而这种频繁度设置失去了频繁的意义。故而，只要检测到频繁项中属性为主属性就认为该主属性为某个候选关键字的子集，然后通过计算其属性闭包识别该频繁项是否源于一个局部依赖。

算法3判定频繁项中元素x是否为主属性

输入：某个频繁项中元素x，一个候选关键字K。

输出：x为主属性返回True，否则返回False。

{X:=K∪{x};//根据定义2，X是一个超关键字

将x置为属性集X的最后元素并调用算法2求X包含的候选关键字M；

ifM≠KthenreturnTrue;

elsereturnFalse}

定理3算法3可正确地判定某个频繁项中元素x是否为主属性。

证明算法3中X为候选关键字K添加了一个元素x后形成的超关键字，并且将x置为属性集X的最后元素并调用算法2求X包含的候选关键字M，如果x为非主属性，即x为超关键字X中唯一的冗余属性，则x肯定被算法2从X中删除，从而得到的候选关键字仍然为K；反之，如果x为主属性，根据定义2，将x置为属性集X的最后元素并调用算法2求X包含的候选关键字M时必然将x前面的某个元素删除。这是因为调用算法2时尝试删除这个元素后，因为x可等价替换这个主属性，导致算法2中此时属性闭包不会发生变化；否则如果没有前面某个等价的主属性删除，而此时x为主属性不会被作为冗余属性删除，则M=K∪{x}。根据定义2可知，因为K是候选关键字导致M是超关键字，这与M是候选关键字相矛盾。故而，算法3是正确的。

□

3.4 基于主属性识别的约简关联规则挖掘

关系R的一个候选关键字中的主属性可分为3种：(1)只包含在FD集中函数依赖的左部的R的属性；(2)在FD集中没有出现过的关系R的属性；(3)在FD集中函数依赖的左部和右部都出现过的R的属性。

定理4[15]在FD集中没有出现过的关系R的属性必为主属性。

定理5[15]只包含在FD集中函数依赖的左部的关系R的属性必为主属性。

由文献[15]可知,在FD集中函数依赖的左部和右部都出现过的关系R的属性不一定为主属性，需要进行判定。为了描述方便，本文记只包含在FD集中函数依赖的左部的R的属性构成集合为K1={FD集中所有依赖的左部}-{FD集中所有依赖的右部}，在FD集中没有出现过的关系R的属性构成集合为K2=关系R的属性集U-{FD集包含的所有属性}，在FD集中函数依赖的左部和右部都出现过的R的属性构成集合为K3=关系R的属性集U-K1-K2。

算法4基于主属性判定的约简关联规则挖掘 Apriori-KAD(Apriori based on Key Attributes Decision)

输入：事务集I，minsupp，minconf。

输出：关联规则集Associate-ruleset。

begin

(1) 利用最小支持度minsupp和“Apriori性质”找到事务集I中所有频繁项集Item-set；

for每个频繁项集X∈Item-setdo

{for每个元素x∈Xdo

{ifx∈K1then

{FD集中左部包含x的所有依赖的左部构成属性集X1并求其闭包X1+；

ifX∈X1+then

Item-set:=Item-set-{X};}

ifx∈K3then

{调用算法3判定x是否为主属性；

ifx为主属性then

{FD集中左部包含x的所有依赖的左部构成属性集X1并求其闭包X1+；

ifX∈X1+then

Item-set:=Item-set-{X};}}}}

(2) 利用最小置信度minconf将第(1)步找到的频繁项集转换为关联规则集Associate-ruleset；

returnAssociate-ruleset；

end

定理6算法4是正确的。

证明由定理2、定理3和定理4可知，算法4正确地判定了关联规则挖掘算法Apriori计算得到的频繁项中是否包含主属性。由定义6可知，当x∈K2时，由于x是在FD集中没有出现过的关系R的属性，即不存在关于x的函数依赖，也就不会存在关于x的局部依赖，即本文考虑的冗余信息的频繁出现问题不会出现，所以算法只考虑x∈K1和x∈K32种情况下会出现的局部依赖。由定理4可知，x∈K1时x必为主属性，由定理2可知,x∈K3时算法3可以正确判定x是否为主属性。

根据前文的描述，我们认为最小支持度应该大于1，即只频繁出现1次的现实意义不大，所以关联规则挖掘算法Apriori计算得到的频繁项中不会包含候选关键字。因为根据定义2可知，一个候选关键字能唯一标识数据库中一条记录，即候选关键字和数据库中属性字段的值是一一对应的，由此可以断定算法Apriori计算得到的频繁项中若包含了主属性且该频繁项属于这个主属性相关的属性闭包，则由定义6可知，该频繁项中属性构成了一个局部依赖。这正是导致规范化表通过连接形成综合信息时会频繁出现冗余信息的原因，即算法4正确地找到了挖掘算法Apriori计算得到的频繁项中包含的局部依赖。故算法4达到了约简算法Apriori计算得到频繁项集的目的，即算法4是正确的。

□

4 实验设计及分析

本文利用微软公司的SQL SERVER 2008 R2提供的SSMS(SQL Server Management Studio)部件建立实验环境中的数据库和SQL Server BIDS(Business Intelligence Development Studio)部件建立一个关联规则挖掘分析项目。实验中使用的数据来源于网络提供的一个用于测试的肾癌数据库(http://www.wsbookshow.com/bookshow/jc/yjs/qtl/11269.html下载案例文件，见sql范例资料.xsl中肾癌数据)。肾癌数据库的表结构如下所示(带下划线字段为关键字)：

肾癌(标本编号，患者编号，患者的年龄(岁)，患者姓名，检测日期，肾癌细胞核组织学分级，肾细胞癌分级，肾细胞癌血管内皮生长因子(VEGF)，肾细胞癌转移情况，肾细胞癌组织内微血管数(MVC)，主治医师)。

在这个数据表中，关键字为“标本编号”，候选关键字还有(患者编号，检测日期)，存在如下的FD集：{ 患者编号→患者姓名，患者编号→主治医师}。由于{患者编号}⊂{患者编号，检测日期}，根据定义6可知上述2个依赖是局部依赖。

4.1 现有关联规则挖掘方法分析结果

本节设置最小支持度为40%，利用现有关联规则挖掘方法得到频繁项集 93项，但其中包含了大量冗余信息，比如患者姓名、主治医师等，运行结果如图1所示。

Figure 1 Associate rule set by the existing mining method with mini-support=40% and mini-conf=30%图1 现有关联规则挖掘方法得到的规则集(最小支持度为40%，置信度为30%)

从图1可以看到“主治医师=王强4⟹肾细胞癌转移情况=有转移”“〈患者姓名= 张六，患者编号≥6〉⟹肾细胞癌转移情况=有转移”这样的规则正是由于数据库中存在如下的FD函数依赖{患者编号→患者姓名，患者编号→主治医师}，这些局部依赖使得冗余信息频繁出现，而这样的规则是我们不关注的、没有实际价值的关联规则。

4.2 基于主属性判定的约简关联规则挖掘

如前所述，在这个肾癌数据表上，关键字为“标本编号”，候选关键字还有(患者编号，检测日期)，存在如下的FD集：{患者编号→患者姓名，患者编号→主治医师}。由于{患者编号}⊂{患者编号，检测日期}，根据定义6,这个表中存在2个局部依赖，且“患者编号”是出现在频繁项集中的主属性，因为“患者编号”存在于候选关键字(患者编号，检测日期)上，算法4将消除(患者编号，患者姓名)，(患者编号，主治医师)这些由于局部依赖导致的频繁项。

消除局部依赖即冗余信息比如患者姓名、主治医师后，在最小支持度为40%时，基于主属性判定的约简关联规则挖掘算法得到的频繁项集有49项，运行结果如图2所示。从图2可以看出，本文所提算法在消除了局部依赖带来的冗余信息后，在最小支持度为40%时挖掘到的频繁项集从93项约简为49项，设置最小置信度也为30%得到规则集的大小为27，比图1中常规挖掘方法在同样的设置参数下挖掘到关联规则集为101个大大减少，而且因为消除了冗余信息带来的频繁出现，图1中展示的冗余信息导致的关联规则在图2中没有出现。

Figure 2 Associate rule set by the proposed algorithm with mini-support=40% and mini-conf=30%图2 本文所提算法得到的规则集(最小支持度为40%，置信度为30%)

5 结束语

现有的基于Apriori算法的关联规则挖掘会产生很多规则，用户难以准确地理解这些规则，更难以挑选合适的规则。针对当前关联规则挖掘方法得到的关联规则数量过多的现象，本文提出了基于频繁项中包含主属性的判定算法，并消除了因为局部依赖导致的冗余信息的频繁出现，从而使挖掘出的关联规则针对性强，也利于用户的理解。实验结果也验证了本文算法的正确性和有效性。