基于粗糙集的关联规则挖掘方法

摘 要:对粗糙集进行了相关研究,并提出一种以粗糙集理论为基础的关联规则挖掘方法,该方法首先利用粗糙集的特征属性约简算法进行属性约简,然后在构建约简决策表的基础上应用改进的Apriori算法进行关联规则挖掘。该方法的优势在于消除了不重要的属性,减少了属性数目和候选项集数量,同时只需一次扫描决策表就可产生决策规则。应用实例及实验结果分析表明该方法是一种有效而且快速的关联规则挖掘方法。

关键词:数据挖掘;关联规则;粗糙集;分辨矩阵;Apriori算法

中图分类号: TP392

文献标志码:A

Approach for mining association rules based on rough set

HE Chaobo1, CHEN Qimai2

1.College of Computer Science and Engineering, Zhongkai University of Agriculture and Engineering, Guangzhou Guangdong 510225, China;

2.School of Computer,South China Normal University, Guangzhou Guangdong 510631, China

)

Abstract: In this paper a novel approach for mining association rules based on rough set theory was presented. It firstly used the rough set’s feature attributes reduction algorithm to reduce attributes, and then applied the improved Apriori algorithm to mine association rules based on the reduction decision table. The advantages of this method were that it reduced the number of the attributes by reducing the unimportant attributes,also reduced the number of candidate item sets and could produce the association rules by scanning decision table only once. The results of application and experiments show that this method is fast and effective.

Key words: data mining;association rule;rough set;discernable matrix;Apriori algorithm

0 引言

关联规则的挖掘一直是数据挖掘领域研究热点之一,其目的是在大型事务数据库中发现项目之间的关联模式[1]。自1994年Agrawal等人提出传统的关联规则挖掘算法Apriori以来,针对该算法运行效率的不足,众多研究人员提出了许多新的改进算法。如Partition [2]、频繁闭项集法[3]、FPGrowth[4]以及TBAR[5]等算法。尽管这些算法各具优点且在性能和效率上均明显高于传统的Apriori算法,但当数据集属性数目较多时,这些算法的挖掘效率仍然较低。解决该问题的根本原则是进行数据预处理时进行属性的约简,从而减少数据挖掘规模,为此已有不少相关解决方法,大致可以分为三类:1)基于代数理论的[6];2)基于信息熵理论的[7-8];3)基于粗糙集分辨矩阵和分辨函数的[9]。

粗糙集(Rough Set)理论[10]主要用于处理和提取含糊性和不精确性的知识并在数据挖掘领域得到成功应用。利用粗糙集理论进行数据挖掘,其主要思想是在保持分类能力不变的前提下,利用基于粗糙集的属性约简方法减少属性的数目,进而可以归纳总结出适用于决策支持的规则。

针对以上关联规则挖掘相关问题,本文以粗糙集理论为基础,提出了一种新的关联规则挖掘方法。并从减少属性数目、减少候选项集数量以及决策表扫描次数等方面对Apriori算法进行了改进。文中给出了相关算法,并通过应用实例及实验结果分析验证了该方法的有效性。

1 粗糙集基本理论

1.1 粗糙集理论的基本定义以及性质

定义1 б桓鲋识表达系统S定义为一个五元组,S=〈U,C,D,V,f〉,其中U表示对象的集合,记为U={x1,x2,…,xn};R=C∪D,是属性的集合,其中C表示条件属性集,而D表示决策属性集;V= ∪r∈RVr是属性值的集合,即属性的值域集,其中Vr是属性r∈R的值域;f是信息函数,f:U×RV,即f(x,R)∈Vr,它指定了U中每一对象x的属性值。オ

定义2 б桓鼍霾弑矶ㄒ逦DT=(U,C∪D,V,f),其中U、C、D、V、 f等符号的意义均如定义1所述。オ

定义3 Ф杂谌我xi,xj∈U,如果C(xi)=C(xj),且D(xi)=D(xj),则DT被称为一致性决策表,否则被称为不一致决策表。オ

定义4 对于PR,我们可以定义一个P上的不可分辨关系:オ

ind(P)={(x,y)∈U×U|a∈P,f(x,a)=f(y,a)}オ

定义5 Ф杂x∈U,可用集合[x]p={y∈U|(x,y)∈ind(P)}来表示包含元素x的等价类。オ

定义6 ЯX是U中根据条件属性集C定义的分类,Y是U中根据决策属性D定义的分类,对于Xi∈X,Yi∈Y,定义一个函数Dx:Des(Xi)Des(Yi),函数Dx称为决策表DT中的决策规则。オ

定义7 Ф杂诿扛龉嬖Des(Xi)Des(Yi),度量规则的参数有支持度(Support)和置信度(Confidence),分别定义为:オ

Support=|Xi∧Yi| / |U|

Confidence=|Xi∧Yi| / |Xi|

性质1 由定义4和定义5推导可得出如下结论:假设ИX吉R,YR,a∈Vx,a∈Vy,г蛴歇[XY]a=[X]a∩[Y]a。オ

1.2 属性约简概念及其求解方法

属性约简是粗糙集用于数据分析的重要概念,可以减少属性数目,提高分析效率。属性约简定义为不含多余属性并保证分类正确的最小条件属性集。假设条件属性集C的约简是C的一个非空子集C′,C和C′必须满足以下两个性质:

1)ind(C,D)=ind(C′,D),不存在C″C′有ind(C″,D)=ind(C′,D)。

2)б桓鼍霾弑砜赡芡时存在几个约简,C的约简的集合记作Red(C)。这些约简的交集定义为决策表的核(Core),Core(C)=∩Red(C),核中的属性是影响分类的重要属性。

计算最小约简的复杂性随着决策表的增大呈指数增长,是一个典型的NP完全问题。文献[9]中提出一种基于分辨矩阵的条件属性约简有效方法,可以获的最优解或近似最优解。其主要思想是通过构造分辨矩阵,化简由分辨矩阵导出的分辨函数成标准式,该标准式所有的蕴含式包含的属性就是决策表所有的约简集合,最后选取包含核属性的最小约简集作为最终约简集。Ц梅椒ㄖ蟹直婢卣M是一个|U|×|U|矩阵,其中的每一个元素Mij都是C的一个子集,即Mij∈C。Mij的具体定义如下:オ

Mij={mij1,mij2,…,mijn};i, j=1,2,…,|U|

mijk=Φ, cik=cjkck, cik≠cjk ;k=1,2,…,|C|

Э芍M为主对角线为Φ的对称矩阵,在实际应用中只计算它的上三角阵。构造分辨函数可把Mij的每个属性值进行“或”运算,然后再“与”其所有的Mij (Mij≠Φ),其中i, j=1,…,|U|,结果用F表示。вτ梅直婢卣蠼行属性约简的优势在于可以利用该矩阵的对称性将计算量减半,并且可以对约简后的决策表直接提取规则。

┑1期 ┖爻波等:基于粗糙集的关联规则挖掘方法┆

┆扑慊应用 ┑30卷

2 基于粗糙集理论的关联规则挖掘方法

2.1 基本思想

该方法的基本思想是首先利用基于分辨矩阵的条件属性约简算法确定决策表K的一个约简集K_reduct,然后利用K_reduct将Kё化为适合Apriori算法分析的具有布尔属性的新决策表K′。г谛碌木霾弑砩隙蕴跫属性集运用Apriori算法首先生成频繁1项集,并删除其中支持度小于阈值的项,Ъ俏LC1;在LC1基础上继续生成频繁i项集,其中LCi=LCi-1×LC1,i大于1,小于或等于约简集的长度,并删除LCi中支持度小于阈值的项;同理对于决策属性集D,可在LD1基础上计算LDj=LDj-1×LD1,j大于1,小于或等于决策属性集的长度;接着LCi与LDj运用性质1进行两两连接运算生成长度为i+j的频繁项集,记为Li+j,Li+j中支持度与置信度大于或等于阈值的频繁项集可放入规则集RS中。每次计算LCi、LDj、Li+j都可以根据性质1利用之前的计算结果,避免了再次扫描决策表。最后对规则集RS中的规则进行合并优化后即为所需挖掘的关联规则。オ

该方法的实现步骤描述如下:

步骤1 数据概化形成决策表、确定条件属性以及决策属性。

步骤2 运用基于分辨矩阵的属性约简方法对条件属性进行约简和求核,当存在多个核值时,选择包含核值的最小约简集。

步骤3 将约简后的决策表转换为基于布尔属性的新决策表。

步骤4 根据支持度和置信度阈值,运用改进后的Apriori算法发现频繁K项集Lk,并生成规则集RS。オ

步骤5 в呕合并RS中的关联规则,由规则集RS生成形式为:Des(c1)∧Desc(c2)∧…∧Desc(cn)Des(d1)∧Desc(d2)∧…∧Desc(dn)У墓亓规则。

2.2 关键算法描述

该方法主要涉及到属性约简和求核、ё换生成新决策表以及关联规则集RS的生成3个关键算法。其中属性约简和求核算法在文献[9]已提到,下面给出本文设计的另外两个算法的描述。

算法1 Decisiontable _transform,使用约简集转换生成新决策表。

输入:K为具有完全属性的决策表;C为条件属性集合;D为决策属性集合;K_reduct为条件属性约简集。オ

输出:Ь哂胁级属性的新决策表K′。

程序前

1)For K_reduct中每一个条件属性Ci{

2) 计算Ci的值域集VCi;

3) 将VCi中每一个元素写入新决策表K′的条件属性集C′中;}

4) For D中每一个决策属性Di{

5) 计算Di的值域集VDi;

6) 将VDi中每一个元素写入新决策表K′的决策属性集D′中;}お

7) For K 中每一个元组 t{お

8) For K_reduct∪D 中每一个属性a{

9) Iff(t,a)=a(m),a(m)∈C′∪D′ Then

10) гK′中,f(t,a(m))=1;И

11) Else

12) гK′中,f(t,a(m))=0;}}

程序后

算法2 RS_generate,Ч亓规则集RS生成算法。

输入: K′为新决策表;C′为K′中的条件属性集;D′为K′中的决策属性集;minsup为最小支持度;minconf为最小置信度。オ

输出:Ч亓规则集RS。

程序前

1)For C′中每一元素ci {

2)ぜ扑闵成ciУ钠捣1项集Lci′И

3)If |Lci′|/|K′|≥minsup Then

4)おLC1=LC1∪ci //LC1为条件属性符合minsup的频繁1项集}お

5)For D′中每一元素di′{お

6)ぜ扑闵成di′У钠捣1项集Ldi′И

7)If |Ldi′|/|K′|≥minsup Then

8)おLD1=LD1∪d //LD1为决策属性符合minsup的频繁1项集}お

9)For(k=2 ;k≤|C′|;k++) {お

10)おLCk=LC(k-1)×LC1;И

11)そ岷闲灾1计算LCk中各元素的支持度并删除小于minsup的元素}お

12)For(k=2;k≤|D′|;k++){お

13)おLDk=LD(k-1)×LD1;И

14)そ岷闲灾1计算LDk中各元素的支持度并删除支持度小于minsup的元素;}お

15)For(i=1;i≤|C′|;i++){お

16)For(j=1;j≤|D′|;j++){お

17)おLi+j=Li+j∪(Lci×LDj)//Li+j为同时具有条件属性、决策属性的频繁集お

18)そ岷闲灾1计算Li+jе懈髟素的置信度conf′,如果conf′≥minconf,г蚣尤RS中;

19)}}

程序后

2.3 性能分析

该方法首先通过属性约简算法减少了条件属性数目,然后在算法RS_generate中只在生成频繁1项集时才需扫描决策表,往后寻找更大的频繁项集都可以根据粗糙集理论性质1利用前一次计算结果,避免了再次扫描决策表;同时通过支持度阈值过滤不符合要求的频繁集,减少了候选项集的数量,节省了存储空间。可见该方法可降低运算时间和空间复杂度,提高挖掘关联规则的效率。

3 应用实例

以某银行信用卡申请批准数据[11]为例挖掘其中的关联规则,对数据库的关系表进行数据预处理后得到表1所示的决策表。

表格(有表名)

表1 某银行信用卡申请批准数据

申请号账户余额职业月工资决策

1银行 中等有 低同意

2银行 低有 高 拒绝

3无 低 有 中等 拒绝

4其他金融机构高 有 高 同意

5其他金融机构中等 有 高 拒绝

6其他金融机构高 有 低 同意

7银行高 无 中等 同意

8无 低 无 低 拒绝

为方便用分辨矩阵对该决策表进行约简和求核,使用字母编号代替各属性值,概化表1得到表2。

表格(有表名)

表2 概化后的决策表

UABCDE

1A1B2C1D3E1

2A1B3C1D1E2

3A3B3C1D2E2

4A2B1C1D1E1

5A2B2C1D1E2

6A2B1C1D3E1

7A1B1C2D2E1

8A3B3C2D3E2

П2中U、A、B、C、D、E分别代表申请、账户、余额、职业、月工资、决策等属性;Ai、Bj、Ck、Dl、Em(i, j,k,l,m∈1,2,…,N)分别为各属性在表1中对应位置的取值。オ

确定A、B、C、D为条件属性,E为决策属性,接下来根据条件属性构建决策表的分辨矩阵,由分辨矩阵定义可得如下分辨矩阵:オ

0ACCCBCCDAD

0BCCDCDCAB

0CCCDAB

0ACDABCB0

0AC00

0BD

0C

в煞直婢卣罂杉扑惴直婧数F=(A∧B)∨(B∧C),即约简集为{A,B},{B,C},核为B,选取{A,B}为最小约简集K_reduct,删除多余属性,根据算法1将表2转化形成具有布尔属性的决策表(表3)。オ

表格(有表名)

表3 约简后决策表的布尔表

U

AA1A2A3

BB1B2B3

EE1E2

110001010

210000101

300100101

401010010

501001001

601010010

710010010

800100101

Ъ偕minsup=25%;minconf=75%,执行算法RS_generate进行关联规则挖掘。其中产生的满足minsup的频繁K项集有:LC1={A1,A2,A3,B1,B2,B3},LD1={E1,E2},LC2= LC1 А联LC1={(A2,B1),(A3,B3)},LD2= Й;L2=LC1×LD1={(A1,E1),(A2,E1),(A3,E2),(B1,E1),(B3,E2)},L3=LC2А联LD1={(A2,B1,E1),(A3,B3,E2)}。在L2中,B1E1,B3E2,置信度均为100%>minconf,放入规则集RS中;L3中A2,B1E1,A3,B3E2置信度均为100%>minconf,放入规则集RS中,则RS={(B1,E1),(B3,E2),(A2,B1,E1),(A3,B3,E2)},RS中的关联规则可进一步合并优化得到最小化关联规则B1E1与B3E2,最后由表1得到的关联规则为:Des(B1) Des(E1) 即余额=高决┎=同意(置信度为100%),Des(B3)Des(E2) 即余额=┑汀决策=不同意(置信度为100%)。オ

4 实验与结果分析

实验目的是对传统的Apriori算法与采用本文算法进行关联规则挖掘执行时间效率上的比较,实验环境部署在一台CPU为Intel Pentium Dual 2.0GHz,内存2GB,操作系统为Windows XP SP2的PC机上,开发语言采用VC++6.0,测试数据来自5个通用的UCI数据集:Zoo、breastcancer、TicTacToe、Solar Flare和mushroom。实验中首先采用属性约简算法进行属性约简,结果如表4所示。

表格(有表名)

表4 实验数据集及属性约简结果

数据集原属性数约简后属性数总记录数

Zoo1710101

breastcancer107286

TicTacToe108958

Solar Flare1081B389

mushroom2288B124

然后在选取不同数据集情况下分别执行Apriori算法与本文算法进行挖掘规则数和时间效率上的比较,同时对breastcancer以及mushroom数据集在分别选取不同记录数情况下观察Apriori算法与本文算法执行时间的变化,结果如表5,图1、2所示(设minsup=10%,minconf=50%)。

从表5可以看出,对于同一数据集,本文算法挖掘的关联规则数与Apriori相差不大,可以将置信度阈值设置较低便可与其接近。图1、图2表明随着记录数的增多,传统的Apriori算法随着频繁项集数量以及扫描数据集次数增多,执行时间有突变性的增加,而本文方法有效地应用了粗糙集的相关性质,减少了频繁项集数量以及数据集扫描次数,执行时间变化相对平稳而且平均约减少3~4倍时间。

表格(有表名)

表5 Apriori算法与本文算法挖掘规则数和用时

数据集

Apriori算法

规则数用时/s

本文算法

规则数用时/s

Zoo110.3390.12

breastcancer52.3430.45

TicTacToe324.46181.13

Solar Flare195.32121.98

mushroom3756.80289.30

图片

图1 breastcancer数据集测试结果

图片

图2 mushroom数据集测试结果

5 结语

本文给出的关联规则挖掘方法基于粗糙集理论,对传统的Apriori算法进行了改进,解决了该算法需多次扫描数据库

及产生庞大的候选项集的问题。理论及实验证明该方法可有效进行属性约简以及关联规则的挖掘,在运行时间复杂度、空

间复杂度上都有一定程度上的改善。但在实际应用中最终参与决策规则挖掘的条件属性及决策属性的选择仍然依靠人为判断,所以研究如何建立相关分析模型自动确定条件属性、决策属性有待进一步的工作。

参考文献:[1] HAN JIAWEI,KAMBER M.Data mining concepts and techniques[M]. San Francisco:Morgan Kaufmann Publishers,2005.

[2] SAVASERE A,OMIECINSKI E,NAVATHE S. An efficient algorithm for mining association rules in large database[C]// Proceedings of the 21th International Conference on Very Large DataBase.San Francisco:Morgan Kaufmann Publishers,1995:432-443.

[3] PASQUIER N,BASTIDE Y.Discovering frequent closed item sets for association rules[C]// Proceedings of the 7th International Conference on Database Theory. London: SpringerVerlag,1999:398-416.

[4] HAN JIAWEI,PEI JIAN.Mining frequent patterns without candidate generation[C]// Proceedings of the 20th ACM SIGMOD International Conference on Management of Data.New York:ACM,2000:1-12.

[5] BERZAL F,CUBERO J,MARIN N.TBAR: An efficient method for association rule mining in relational databases[J].Data and Knowledge Engineering,2001,37(1):47-64.

[6] 叶东毅.基于近似精度递归计算的一个属性约简算法[J].小型微型计算机系统,2003,24(12):2272-2274.

[7] 刘振华,刘三阳, 王珏.基于信息量的一种属性约简算法[J].西安电子科技大学学报,2003,30(6):835-838.

[8] 王国胤,于洪, 杨大春.基于条件信息熵的决策表约简[J].计算机学报, 2002,25(7):759-766.

[9] 唐建国,谭明术.粗糙集理论中的求核和约简[J].控制与决策,2003,7(4):449-452.

[10] PAWLAK Z.Rough sets[J].International Journal of Computer Information Science,1982,11(5):341-356.

[11] PAWLAK Z.Rough sets:Theoretical aspects of reasoning about data[M].Netherlands:Kluwer Academic Publishers,1991.