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 =\left\{ {i_1, i_2,i_3,\cdots,i_m }\right\}$ 是全体事务项的集合, I的子集一般称为项集, 根据子集中事务项的个数依次可称为1-项集, 2-项集, …, k-项集. 数据库中每条事务记录 $t_i (i=1, 2, 3,\cdots,n)$ 均对应着I的一个子集, 且具有唯一标识符TID. ║D║表示数据集D中包含的事务数量.

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

$ support(x) = \frac{{\left| {\{ T|X \subseteq T,T \subseteq D\} } \right|}}{{\left| D \right|}} \times 100\% $

(1)

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

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

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

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

$ conf(X \Rightarrow Y) = \frac{{\left| {\{ T|X \cup Y \subseteq T,T \subseteq D\} } \right|}}{{\left| {\{ T|X \subseteq T,T \subseteq D\} } \right|}} \times 100\% $

(2)

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

2 基于分类修剪的关联分类模型ACCP 2.1 基于分类标识的规则挖掘

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

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

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

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

根据项目集空间理论, 频繁k-项集的所有子集均为频繁项集. 由此可得, 每个频繁k-项集可抽取出k个频繁k–1项子集, 则包含这k个频繁k–1项集的集合L_k–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}的集合L₃中, 事务项a、b、c、d出现的次数都至少为3. 反之, 若a、b、c、d任意一个事务项在L₃中出现次数小于3, 则4个3-项集中至少有一个不包含于L₃即不是频繁项集, 由此可得{a, b, c, d}亦不是频繁项集. 推而广之, 不难得出:

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

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

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

(2) 记录下出现次数小于k–1的事务项, 记作 $P = \{ \left. p \right||{L_{k - 1}}(p)| < k - 1\} $ ；

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

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

2.3 实例分析

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

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

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

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

算法1.

输入: 数据库D, 最小支持度阈值minSupp;

输出: 分类规则项集的集合R;

Step 1. 根据分类标识的不同将事务数据集D分为事务子集D_k={D₁, D₂, D₃, ……, D_n}, 其中n为分类属性的值的数量;

Step 2. for(i=1; D_i≠Ø; i++) do

Step 2.1. 扫描事务子集D_i得到规则前项的频繁1-项集的集合L₁;

Step 2.2. for(k=2; L_k-1≠Ø; k++) do

Step 2.2.1 扫描L_k–1, 根据每个属性项目在其中出现的次数判断最大频繁项集并剪除, 得到L_k–1';

Step 2.2.2. L_k–1'自连接生成候选k-项集的集合C_k;

Step 2.2.3. 依次扫描D_i中所有事务记录, 若包含C_k中的候选集, 则此候选集的支持数加1;

Step 2.2.4. 对C_k进行基于最小支持数minSupp的剪枝得到L_k

Step 2.3. 得到事务子集D_i中的分类规则集R_i =∪L_k;

Step 3. 获得最终的分类关联规则集R=∪R_i;

2.4 规则修剪

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

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

算法2.

输入: 初始规则集R, 事务数据集D, 最小置信度minConf

输出: 改进后的关联分类器C

Step 1. 新建临时数据集X, 令其等于事务数据集D;

Step 2. 扫描数据集X, 计算R中每条未标记规则的置信度, 删除R中不满足最小置信度minConf要求的规则;

Step 3. 将分类规则集依次按照置信度、支持度从大到小以及规则项集维度从小到大的方式进行优先级排序;

Step 4. 选择最高优先级的规则进行考察, 记录下该规则在数据库X中正确分类的样本数与规则覆盖样本数之比, 并删除所有覆盖样本;

Step 5. 标记已遍历过的规则, 对剩余的样本循环执行Step 2~Step 4, 直到数据库中没有样本或所有规则均已被遍历. 如果存在未被遍历的的规则, 则将该规则剪除; 如果存在所有规则均不能对其分类的样本, 则将此样本归为数据库中样本数量最多的类别即默认类别;

Step 6. 按照正确分类的样本数占覆盖样本数的百分比对规则进行排序, 剪除正确分类比为0或正确分类比不为0但排名最后的规则. 计算当前规则集对数据库X的整体分类正确率;

Step 7. 循环执行Step 1~Step 6, 直到规则集对数据库的分类正确率不再提高为止, 得到最终的分类规则集R.

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语言实现.

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算法取得来了良好的应用效果.

4 结语

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

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