基于分类修剪的关联分类算法改进①

秦晨普,张云华

(浙江理工大学 信息学院,杭州 310018)

1998 年,新加坡国立大学的Liu Bing 教授提出了一种将关联规则挖掘和分类技术结合在一起的分类算法——关联分类算法(Classification-Based Association,CBA)[1],因其较好的结合了关联规则挖掘和传统分类算法的优点,受到了研究者的广泛关注.实践证明,关联分类算法相较于决策树、朴素贝叶斯、SVM 支持向量机等传统的分类算法具有更优的分类性能且分类模型更易理解.另一方面,关联分类算法是基于传统Apriori 算法挖掘事务项之间的关联来产生分类规则,也因此也不可避免的继承了关联规则挖掘算法需要多次扫描数据库、I/O 负载较大的缺点,算法效率不是很理想.之后的研究者又先后提出了关联决策树(Association based Decision Tree,ADT)方法[2]、基于多关联规则的分类算法(Classification based on Mutiple Association Rules,CMAR)[3]、等,虽说在算法性能的提升上取得了一定的成果,但也或多或少的存在着算法鲁棒性差、冗余节点多的问题.

在现有CBA 关联分类算法的基础上,本文提出了一种基于分类修剪的关联分类算法改进方案ACCP,在分类关联规则的挖掘过程中基于分类标识对事务数据集进行分类修剪,并加入了基于最大频繁项集的事先剪枝,避免了无法生成规则的无效连接操作,有效提高了规则挖掘效率.同时,借鉴已有的研究成果在构造分类器的过程中利用改进后的数据覆盖法对分类规则进行修剪,提高分类准确率.

1 概念描述

关联分类实质上就是基于关联规则挖掘的分类技术,它既反映了知识的应用特点——分类或预测,又体现了知识内在的关联特性[4].设D是一个包含着n条记录的事务数据集,I={i1,i2,i3,···,im}是全体事务项的集合,I的子集一般称为项集,根据子集中事务项的个数依次可称为1-项集,2-项集,…,k-项集.数据库中每条事务记录ti(i=1,2,3,···,n)均对应着I的一个子集,且具有唯一标识符TID.║D║表示数据集D中包含的事务数量.

定义1.项集X的支持度：数据集中包含项集X 的事务出现的频率,记为

其中,| {T|X⊆T,T⊆D}|代表的是事务数据集D中包含项集X的事务总数,即项集的支持数.

定义2.频繁项集：若项集的支持度超过或等于人为设定的最小支持度阈值minSupp,则称此项集为频繁项集.

定义3.最大频繁项集：如果一个频繁项集的任一直接超集都是非频繁项集,那么就称这个频繁项集为最大频繁项集.

定义4.规则置信度：假设数据集中关联规则X⇒Y成立,则其置信度是指包含项集X的事务同时包含项集Y的概率,其表述的是规则的可靠性,表达式为：

定理1.项目集空间理论：频繁项集的子集仍是频繁项集,非频繁项集的超集是非频繁项集[5].

2 基于分类修剪的关联分类模型ACCP

2.1 基于分类标识的规则挖掘

之前的研究人员所运用的基于分类标识的规则后项约束,大多先由频繁k-1 项集的集合Lk-1自连接生成候选k项集的集合Ck,再对包含分类标识的候选k项集进行基于最小支持度阈值minSupp的剪枝操作.实际上,当频繁k-1 项集I1作为规则前项只出现在分类标识为Ci的事务中时,那么对分类标识不等于Ci的候选k项集{I1,Ci+1}进行支持度计数就显得没有必要,本文基于此思想对分类关联规则的挖掘过程进行了改进.

将事务数据集D根据分类属性值的不同,划分为多个事务子集{D1,D2,D3,…,Dn},其中n为分类属性值的个数,每个事务子集中挖掘得到的规则项集具有统一的分类标识.对每个子集进行单独的分类关联规则挖掘,在分类标识为Ci的事务子集中,项集{Ii}的支持数和事务总集中包含分类标识Ci的规则项集{Ii,Ci}支持数一致,只要根据项集Ii的支持数进行连接剪枝即可,从而大幅的降低了每次扫描数据库时的数据维度,避免了无法生成规则的项集的产生,减少了候选项集的数量.

2.2 基于最大频繁项集的事先剪枝

原始的关联规则挖掘过程有两次剪枝操作,第一次是在Lk-1自连接之后,根据Apriori 算法性质(项目集空间理论)剪除非频繁项集,第二次是由候选项集Ck生成Lk时,通过计算项集支持度剪除非频繁项集.本文将在此基础上加入一次基于最大频繁项集的事先剪枝,即在自连接之前利用项目集空间理论,提前判断出频繁k-1 项集的集合Lk-1中的某些最大频繁项集,将其进行剪除,从而省去了它们的连接操作,进一步减少了候选项集数,提高了分类关联规则的挖掘效率.

根据项目集空间理论,频繁k-项集的所有子集均为频繁项集.由此可得,每个频繁k-项集可抽取出k个频繁k-1 项子集,则包含这k个频繁k-1 项集的集合Lk-1当中每个事务项出现的次数必然大于等于k-1.下面用一个简单的例子说明这个原理.

已知4-项集{a,b,c,d}为频繁项集,其有4 个频繁3-项子集,分别为{a,b,c}、{a,b,d}、{a,c,d}、{b,c,d},则包含项集{a,b,c}、{a,b,d}、{a,c,d}、{b,c,d}的集合L3中,事务项a、b、c、d 出现的次数都至少为3.反之,若a、b、c、d 任意一个事务项在L3中出现次数小于3,则4 个3-项集中至少有一个不包含于L3即不是频繁项集,由此可得{a,b,c,d}亦不是频繁项集.推而广之,不难得出：

定理2.频繁k-1 项集中存在事务项在集合Lk-1中出现次数小于k-1 次是此频繁项集为最大频繁项集的充分条件.

对最大频繁项集事先剪枝的具体实现步骤如下：

(1)计算频繁k-1 项集的集合Lk-1中每个事务项出现的次数,用Lk-1(p)表示；

(2)记录下出现次数小于k-1 的事务项,记作P={p||Lk-1(p)|＜k-1}；

(3)将Lk-1中包含有P中任一元素的频繁项集删除,记为Lk-1'；

(4)Lk-1'自连接,生成候选k-项集的集合Ck.

2.3 实例分析

我们以表1所示的事务数据集为例,简单阐述一下改进后的关联分类算法的分类关联规则挖掘过程.

表1 数据库示例

由表1可得,事务数据集D有两个类别属性值A1,A2,可将事务数据集分为表2,表3所示的事务子集D1,D2.

表2 分类得到的事务子集D1

表3 分类得到的事务子集D2

Ck表示候选k-项集的集合,Lk表示频繁k-项集的集合,Ri表示事务子集Di中挖掘出的分类规则集,假定最小支持数minSupp为2,首先对事务子集D1进行规则挖掘.如图1所示,第一次扫描事务子集D1后得到候选1-项集的集合C1及其中各项集所对应的支持数,将C1中支持数小于最小支持数minSupp的项集剪除便得到频繁1-项集的集合L1,图1左上表便是C1到L1的剪枝过程,其中边框为虚线的项集即为被剪枝的非频繁项集.将L1自连接可得到候选2-项集的集合C2,基于最小支持数minSupp剪枝后得到频繁2-项集的集合L2= {{a,b},{a,c},{b,c},{b,d}}.

图1 分类关联规则挖掘过程示例

接着对集合L2进行遍历,记录L2中每个事务项出现的次数.不难发现,事务项a 同时包含于频繁2-项集{a,b}、{a,c},即事务项a 在L2中出现了2 次,同理可得事务项b 出现3 次,事务项c 出现2 次,事务项d 只出现了1 次.由于属性项目d 出现的次数小于L2中项集的项数,由定理2 可得L2中所有包含项目d 的项集均为最大频繁项集,将其剪除后即得到最终的L2'.由L2'自连接可得到候选3-项集C3={{a,b,c}}并最终确定L3={{a,b,c}},因其无法再进行自连接,频繁项集挖掘结束.将最终生成的集合L中所有频繁项集加入分类标识A1便得到分类关联规则集R1,循环挖掘所有事务子集并将最后得到的分类规则集合并便得到整个数据库的分类关联规则集R.

2.4 规则修剪

由于分类关联规则挖掘所得到的规则数量巨大,在构造分类器时会占用大量内存空间,并且会对分类准确率产生不利影响,本文基于改进后的数据库覆盖方法对规则集进行规则修剪.

首先基于置信度、支持度从大到小以及规则项集维度从小到大的方式对分类规则进行优先级排序.从优先级最高的规则依次进行考察,遍历事务数据集记录下正确分类的比例并将此规则所能覆盖的所有事务样本删除,直到没有剩余样本或已考察完所有规则.最后删除分类性能较差的规则并多次执行以上步骤不断提高规则集的分类准确率[6].规则修剪的算法一般性描述如下：

3 实验与结果分析

3.1 实验环境

本次实验的实验环境如下：Intel(R)Core(TM)i5-2450M CPU @2.50 GHz 处理器；8 G 内存；120 G SSD 固态硬盘；Windows 10 专业版操作系统.实验选取了UCI 标准数据库中的5 个常用数据集Pima Indians Diabetes、Lymphography、Wine、Car Evaluation、Iris[7]分别涵盖医疗卫生、食品检测、汽车评估、生物研究等领域,每个数据集的相关数据信息如表4所示.本实验算法程序使用Java 语言实现.

表4 实验所用数据集相关信息统计

3.2 实验结果分析

本实验使用了10 折交叉验证方法来避免过度拟合,从每个数据集中随机选取80%的样本作为训练数据集,其余20%作为测试数据集测试算法的分类性能.针对数据集中存在的数据缺失,根据缺失的属性值是离散还是连续,分别采用众数原理将其设定为该属性在数据集中出现次数最多的取值,或是设定为数据集中该属性其他非缺失值的平均数.本文选取了现有的CBA 算法以及传统分类算法中的C4.5 决策树算法进行对照试验,实验中最小支持度minSupp和最小置信度minConf分别设定为2%和60%,结果如表5所示.

本文采用正确分类的样本数占测试样本总数的比例即分类准确率来衡量分类器模型的优劣.从表5中可以看出,关联分类算法的准确率整体高于传统的C4.5 决策树算法.在部分数据集上CBA 算法的分类准确率等于或略小于C4.5 算法,而改进后的关联分类算法ACCP 则在全部数据集上都明显优于C4.5 和CBA,平均分类准确率分别提高了5.29 和3.37 个百分点.与此同时,基于分类修剪并加入了预先剪枝的ACCP 算法在实验所采用的所有数据集上的运行时间均较CBA 算法有所降低,在数据集属性较多、事务数较大更为明显.实验结果证明,ACCP 算法取得来了良好的应用效果.

表5 实验结果对比

4 结语

本文提出了一种基于分类修剪的新关联分类算法ACCP,通过将事务数据集根据分类标识分块挖掘,极大地节省了内存空间,提高了挖掘效率,同时在分类器构造过程中加大规则修剪力度,剪除了规则集中分类性能较差的冗余规则,进一步优化了分类模型.实验证明,本文提出的方法相比传统的C4.5 决策树和CBA分类模型具有更优的分类性能.

基于关联规则产生分类器的过程并不有助于人们对分类模型的理解,反而会影响分类器的性能.因此,如何有效减少构建分类器时所使用到的规则数量,提高单个规则的适用性,是接下来要研究解决的问题.

1 Liu B,Hsu W,Ma YM.Integrating classification and association rule mining.Proceedings of the 4th InternationalConference on Knowledge Discovery and Data Mining.New York,NY,USA.1998.80-86.