基于改进的K-means算法的关联规则数据挖掘研究

李 珺，刘 鹤，朱良宽

(东北林业大学，哈尔滨 150040)

1 引 言

数据挖掘是从随机的、不完全的大量数据中，找出隐藏在其中的有价值信息的过程[1，2].随着时代的发展，能获取到的信息越来越多，如何能利用有限的资源快速在大量的数据中找出有价值的信息是数据挖掘所面临的挑战[3].关联规则和聚类分析是数据挖掘中两个重要方法.

关联规则分析寻找给定数据集中数据项之间隐藏的关联关系，描述数据之间的密切程度，通过关联规则可以发现大量数据中项集之间有趣的关联规则或者相关关系[4-6].关联规则数据挖掘算法分为两个步骤：首先从事物数据库中挖掘出支持度不小于给定最小支持度的所有频繁项集，即产生频繁项集，然后从频繁项集中挖掘出置信度不小于给定最小置信度的强关联规则，即产生规则[7].

将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类[8].由聚类所产生的簇是一组数据对象的合集，这些对象与同一个簇中的对象彼此相似，却与其他簇中的对象相异[9].聚类分析是将对象分成多个子集的过程.聚类分析主要分为4个步骤：数据的预处理，衡量相似度的距离函数的定义，数据的聚类，输出结果的评估[10].K-means算法是基于划分的经典聚类算法，其基本思想是在空间设置K个初始聚类中心，分别计算K个中心点到数据集中点的距离，如果满足定义的距离最小阈值，则划分新的类别，通过迭代的方法逐次更新聚类的初始中心点，直到初始中心点不再发生变化或者变化范围很小，迭代结束[11，12].K-means算法中K值的选择和初始聚类中心的选择对聚类效果会产生很大影响.

为了能更迅速准确的找出有价值的规则，提高关联规则的理解性，本文提出一种方法将关联规则Apriori算法和聚类分析中K-means算法相结合使用.1)将数据预处理完成之后，用Apriori算法产生关联规则，利用本文建立的3个检验指标的方法对冗余的关联规则进行删除;2)聚类之前要先对初始点进行选择，将产生的关联规则利用最大三角形法通过迭代确定初始点;3)用K-means算法对产生的规则进行聚类.此方法能有效的删除大量的冗余规则，将相似的关联规则归为一簇，提高聚类性能，节省运行时间.

2 基于改进的K-means算法关联规则数据挖掘方法

K-means算法是一种迭代求解的聚类分析算法，是基于划分式方法的一种聚类方法，它有线性的时间复杂度和线性的空间复杂度[13].其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心.在算法中，k是需要用户提前设定的，它代表期望的种类数，但有时会不确定数据的种类数目，这种情况下会多次尝试用不同的k值进行聚类，选取其中最符合的K值.K-means算法对大数据集有比较高的效率，但对于K的定义和初始点的选择方面存在缺陷.

2.1 数据预处理

本文采用的数据是鸢尾花(iris)数据集，是一类多重变量分析的数据集.完整的鸢尾花(iris)数据集是一个150×5的矩阵.每一行代表一株鸢尾花，包含的属性有萼片长度(Sepal.Length)，萼片宽度(Sepal.Width)，花瓣长度(Petal.Length)，花瓣宽度(Petal.Width)和该鸢尾花的类型(Species)共计5种属性，其中前4种属性都是以厘米计数.鸢尾花类型属性里的数据都是文本格式，为了后续的数据分析更加方便，本文选择把种类中的字符型数据转化成数值型数据.由于本数据集中鸢尾花的种类只包含3种，所以在R软件中，将setosa类型替换为1，将versicolor类型替换成2，将virginica类型替换成3.替换后的数据集由R软件导出，用Excel显示部分数据如图1所示.本文所用的R软件为64位3.5.1版本，鸢尾花数据集可以在R软件自带的数据包中导入.

图1 数据预处理后的数据集部分数据Fig.1 Partial data of the data set after data preprocessing

2.2 冗余规则的删除

关联规则的产生是同时满足最小支持度和最小置信度的形如X→Y的蕴涵式，其中X称为关联规则的前项，Y称为关联规则的后项.当数据集较大时，会产生大量的关联规则，这些规则中包含的冗余规则是具有误导性的，不利于用户进行后续的分析和决策.本文将引入3个关联规则的检验指标增加删除冗余规则的条件，提高关联规则的实用效率.

2.2.1 相关性系数(Lift)

相关性系数(Lift)是观察到的X和Y的联合概率与期望联合概率的比值，前提是假设他们在统计上是独立的.相关性系数是用来度量一条规则出乎意料的程度.相关性系数的计算公式如下：

(1)

相关性系数接近1表示一条规则的支持度期望是由其两个分量的支撑的乘积决定的，即表示项集X和项集Y的出现是相互独立的，X和Y之间相互不受影响，X和Y同时出现没有意义；相关性系数小于1，则说明项集X和项集Y是互斥的，即X的出现降低了Y出现的概率；相关性系数大于1时，项集X的出现会带动另一个频繁项集Y的出现.

2.2.2 杠杆率(Leverage)

杠杆率(Leverage)是用来衡量XY的联合概率和期望联合概率之间的差异，杠杆率的计算公式如下：

leverage(X→Y)=P(XY)-P(X)·P(Y)=rsup(XY)-rsup(X)·rsup(Y)

(2)

杠杆率表示了规则出乎意料程度的“绝对”度量，它和相关性系数同时使用.

2.2.3 出错率(Conviction)

出错率衡量了规则的期望错误数，表示X出现的时候Y不在同一事务中的次数.因此，它是对关于后项的补集的规则强度的度量，出错率的定义如下：

(3)

以上考虑的所有规则度量都只使用了X和Y的联合分布.定义X′为X不出现在事务中的事，Y′也以此定义.表1中的列联表中给出了4种可能的事件，分别对应X和Y出现或者不出现的情况.从表1中可以观察到P(X)=P(XY)+P(XY′)，这表示P(XY′)=P(X)-P(XY)，以及P(Y′)=1-P(Y)也成立.由此可得出错率的计算公式如下：

(4)

出错率越大表明规则预测错误的概率越大，这样产生的规则有一定误导性，即使满足最小支持度和最小置信度也不能采用.

表1 X和Y的列联表Table 1 X and Y contingencyTable

2.2.4 检验指标的权重分析

本文利用R软件随机产生的数据集对以上检验指标进行权重分析.表2为样例数据集.

表2 样例数据集Table 2 Sample dataset

表3所示的3条规则及其支持度、置信度和相关性系数.比较前两条规则可以看出尽管前两条规则的相关性系数相同并且都大于1，但提供了不同的信息.因其置信度为0.4，所以E→AC是一条弱规则，而E→AB不仅置信度更高，支持度也更大.比较第2条和第3条规则，尽管B→E的相关性系数为1，但是它的置信度和支持度都较高.说明在分析关联规则的时候，必须要使用多个衡量指标进行评估.

表3 关联规则的支持度、置信度和相关性系数的比较Table 3 Comparison of support，confidence and correlation coefficients of association rules

表4中所示的4条规则及其支持度、相关性系数和杠杆率.从表中可以看出前两条规则的相关性系数相同，但第1条规则的杠杆率仅为第2条规则杠杆率的一半，主要是因为AC→E的支持度更大.因此仅考虑杠杆率很容易被误导，原因是即使在支持度不同的情况下规则的相关性系数也有可能相同.第2条规则和第3条规则虽然相关性系数不同，但杠杆率却相同.最后，通过比较第1、第2和第4条规则可知：他们的相关性系数相同，但杠杆率不同，实际上第4条规则A→E可能优于前两条规则，因为它更简洁，杠杆率也更高.

通过表3和表4可知在分析关联规则的时候不能只靠单一的支持度和置信度对规则进行评估，要多个检验指标对规则进行综合衡量，表4说明当相关性系数相同时，杠杆率更高的规则要优于其他的规则.因此，定义相关性系数、杠杆率和出错率的综合权重分析指标计算公式如下：

(5)

式中，conf(X→Y)代表的是当事务X发生时事务Y也发生的置信度，sup(Y)表示事务Y发生时的支持度，sup(XY)表示事务XY同时发生时的支持度.

2.3 初始点的选择

2.4 聚类过程及结果的显示

聚类的过程分为3个部分.第1部分，利用最大三角形方法选择初始点；第2部分，计算关联规则之间的距离并分类；第3部分，判断聚类是否收敛，重新分配关联规则.

将关联规则聚类后，会得到K个聚类簇，其中K为用户自定义.由海量数据产生的关联规则即使进行聚类后，结果依旧很庞大，很难从中快速找到符合用户需求的规则.为了减少聚类时间，提高聚类效率，在产生关联规则后按照用户需求设置检验指标，删除冗余的规则，并将删除冗余规则后的关联规则进行聚类分析.具体步骤如下：

1)先将得到的关联规则按照置信度从高到低降序排列，选择置信度高的前n条规则进行聚类(n可以根据产生的规则数目进行相应的调整)；

2)对n条规则进行聚类，在每类簇中各个关联规则到簇中心的距离分为K个类.那么这个聚类簇中就有n*K条关联规则被显示出来，这样能减少关联规则的数量，便于用户快速对规则进行分析，得到自己感兴趣的结论.

3 实验结果与分析

3.1 冗余关联规则的删除

由于引入了检验指标对关联规则进行删除，本文用鸢尾花数据集进行验证.图2为部分规则的支持度，置信度，3种检验指标及其权重指标.规则的出错率普遍数值较大，而出错率越大，表示规则进行预测时出错的机率越大，所以进行权重分析时，要降低出错率的影响，将比重放在相关性系数和杠杆率上.从图2中可以看出，rule29的出错率较大，但是综合权重分析没有受到出错率的影响而变大反而非常低，这说明rule29是冗余规则，会被识别出来并进行删除.rule19的出错率很低，相关性系数达到3，并且综合权重非常高，说明这条是一条强规则.

图2 部分规则的支持度，置信度，3种检验指标及其权重指标Fig.2 Support，confidence，three test indicators and their weight indicators of some rules

本文用鸢尾花数据集进行两组实验，第1组实验是保持最小支持度在0.2不变，改变最小置信度，对冗余关联规则的删除，结果如图3所示；第2组是在最小置信度保持在0.4不变，通过改变最小支持度对比冗余关联规则的删除情况，结果如图4所示.

从图3和图4中可以看出引入检验指标后能将冗余的关联规则有效的删除，并且当最小支持度和最小置信度的降低时，关联规则数增多的情况下，还能有效删除冗余的关联规则.

图3 最小置信度变化的实验结果(最小支持度为0.2)Fig.3 Experimental results of minimum confidence change (Minimum support is 0.2)

图4 最小支持度变化的实验结果(最小置信度为0.4)Fig.4 Experimental results of minimum support change (Minimum confidence is 0.4)

为了能更好的衡量对冗余关联规则删除的效果，本文定义了一种衡量指标Dr.计算公式如下：

(6)

式中Dr表示衡量指标，NumR表示删除的冗余规则数，TR表示总规则数.如果Dr的数值越大，表示删除的冗余规则数量越多，说明删除效果越好，反之，Dr的数值越小，冗余关联规则删除的效果越差.本文对鸢尾花数据集分别用两种方法进行了冗余关联规则的删除，本文利用韦素云文中所提的删除冗余关联规则的ADRR算法和本文的方法进行冗余关联规则的删除，并对两种方法的效果进行对比，对比结果如图5所示.

图5 两种方法删除效果的对比Fig.5 Comparison of the deletion effect of the two methods

由图5中Dr的数值比较可知，本文中删除冗余关联规则方法效果较好，因此本文的冗余关联规则删除方法是有效的.

3.2 关联规则的聚类

将鸢尾花数据集按照最小支持度为0.25，最小置信度为0.8挖掘关联规则，产生了40条规则，对冗余规则进行删除后剩下11条规则，如表5所示.利用表5所示的规则进行聚类分析，K值分别取K=2，K=3和K=4，结果如表6所示.

表5 关联规则Table 5 Association rules

聚类是将数据分类到不同的类或者簇的过程，所以同一个簇中的对象有很大的相似性而不同簇之间的差异性非常大.通过比较表6(a)，表6(b)和表6(c)，可以看出K值的变化对聚类的影响较小，每个簇内的趋势大致相同.当K=3的时候聚类效果最好，每个簇内的规则间前项都具有共同的特征，且后项相同，簇内的相似性高，不同簇之间的趋势不同.

因为聚类效果最好的是K=3，从分类上可以看出，聚类规则集1的规则都是通过鸢尾花的萼片或者花瓣的长度和宽度来预测鸢尾花的种类；聚类规则集2和3都是鸢尾花萼片和花瓣长宽度之间的关系，而这些规则对鸢尾花没有实际意义，用户可以直接将聚类规则集进行删除.用户在得到聚类规则集时，容易通过聚类规则集内的规则找出规则之间的共同点，快速得到有价值的结论，对无意义或者不感兴趣的规则直接进行删除.

表6(a) K=2时聚类分析结果Table 6(a) Cluster analysis results at K=2

表6(b) K=3时聚类分析结果Table 6(b) Cluster analysis results at K=3

表6(c) K=4时聚类分析结果Table 6(c) Cluster analysis results at K=4

相较于传统的K-means对比较大的数据集采用的随机选取初始点的方法，本文采用了在K条关联规则构建的三角形中迭代选择初始点的方法，在很大程度上减少了聚类运行时间.由图6可以综合看出本文方法能有效的删除冗余关联规则，并且本文方法的运行时间比ADRR算法的运行时间短，因此，本文方法能有效的减少运行时间，提高聚类效率.

3.3 运行效率的比较

在最小支持度不同的情况下，用鸢尾花数据集分别用本文方法和ADRR算法对数据挖掘关联规则并进行聚类分析，对两种方法删除冗余后规则数以及运行时间进行比较，比较结果如图6所示.

图6 两种方法运行效率的比较Fig.6 Comparison of operating efficiency of the two methods

4 结束语

当数据集比较庞大的时候，产生的关联规则数比较多，用户很难在短时间内在大量的规则中找出符合条件且感兴趣的规则，本文引入了3个检验指标，可以精确的将冗余的规则删除，并对删除后的关联规则进行聚类分析，将相似的规则归为同一簇，这样用户通过查看每一簇中的规则就能快速的找到自己感兴趣的规则并且针对簇内的规则得出规律.本文利用产生的关联规则构建三角形，进行迭代选择聚类的初始点，极大的减少了聚类的运行时间，提高了聚类的效率.通过对鸢尾花数据集进行的关联规则分析，证明本文对冗余关联规则的删除和对相似规则进行聚类方法的有效性和可行性.