一种基于K-means的关联规则聚类算法

王 琢，荀亚玲，张继福

(太原科技大学计算机科学与技术学院，太原 030024)



一种基于K-means的关联规则聚类算法

王 琢，荀亚玲，张继福

(太原科技大学计算机科学与技术学院，太原 030024)

关联规则是数据挖掘领域中的主要研究内容之一。针对高维海量数据集，尤其当支持度和置信度阈值太低时，将生成大量冗余和相似的关联规则，从而对关联规则的理解和使用造成了困难。本文采用改进的K-means思想，给出了一种关联规则聚类算法：首先重新定义了冗余关联规则，并给出了删除的方法；然后定义了一种新的规则间相似性度量；最后利用K-means思想，采用最大三角形方法选取聚类的初始点，将相似的关联规则归为一类。实验验证该算法能够帮助用户快速有效地找到有用的关联规则，提高了关联规则的可理解性。

关联规则聚类算法；冗余关联规则；相似性度量；恒星光谱数据

关联规则挖掘[1]是寻找一个事物与其他事物之间的依赖性和关联性，使其中一个事物通过其他事物得到预测的过程，并已广泛应用在股票市场[2]、金融市场[3]、教学管理[4]、职业选择[5]、临床医学[6]等方面。聚类分析师数据挖掘领域的一个热门的研究分支[7]。聚类分析[8]，就是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程。

对于海量高维数据集，传统的关联规则挖掘方法，往往会生成包括冗余和相似规则在内的大量关联规则，造成了关联规则难以被理解的困境。删除冗余规则和将相似规则聚类于一簇是有利于用户分析和理解关联规则的有效手段之一。

目前，删除冗余关联规则的方法主要有：在文献[9]中，利用Galois连接提出了一种快速消除冗余的方法，并采用文献[10]中meta-rule减少冗余的方法作为基准来判断删除效果。但需多次访问闭规则集中出现的规则。在文献[11]中，通过属性前缀树来挖掘无冗余的顺序规则，但只适用于序列数据集。在文献[12]中对冗余关联规则进行定义：若一条规则包含其他规则，且置信度为100% ，那么这条规则就是冗余的。但是，置信度高的关联规则往往是用户所关心的，因此该定义存在问题。在文献[13]中，定义冗余规则为一条规则能够推出另一条规则，那么另一条规则是冗余的。并在此基础上提出了冗余关联规则删除算法ADRR.

现有关联规则的聚类方法主要采用的是：1)基于密度和网格的聚类方法：在文献[13]中，提出了关联规则聚类算法ACAR，同时结合基于密度的聚类算法DBSCAN的思想对关联规则进行聚类，但对于规则间的距离定义过于粗糙。在文献[14]中，通过将基于密度和基于网格的聚类方法结合，改善了基于密度聚类方法效率低的不足，但存在网格数量与内存不匹配的情况。2)K-means聚类方法：在文献[15]中提出了一种适用于关联规则聚类的K-means改进算法，但该方法没有考虑到关联规则之间的关系。在文献[16]中提出了基于最大三角形规则的K-means聚类算法，改善了K-means随机选择初始点的缺点。

综上所述，现有关联规则冗余删除和聚类方法难以有效地提高关联规则的可理解性。本文根据关联规则中重复、多余的关联规则特性(能被其他关联规则完全包含)，对冗余关联规则定义并删除，有效地减少了冗余规则；对前件与后件的关系重新定义关联规则间的相似性度量，结合K-means聚类的思想，对关联规则进行聚类，将聚类簇中的相似规则选择输出，大量地减少了呈现给用户的规则数目。两个方法的结合有效地减少了无用信息对用户的干扰，利于用户快速发现关联规则间的规律。

1 冗余关联规则的删除

1.1 冗余关联规则的定义

关联规则是满足最小支持度与最小置信度的形如X→Y的蕴含式。其中，X和Y分别称为关联规则的先导和后继。由于适用于海量关联规则集，且需在保留用户所关心的规则上对重复、多余的规则进行删除的情况下，本文重新对冗余规则进行定义并进行删除处理。定义如下：

定义1：设有两条关联规则R1：X1→Y1(sup1，conf1)，R2：X2→Y2(sup2，conf2)，若X2⊆X1，且Y2⊆Y1，即R2R1或R2=R1，则R1能够推出R2，那么R2是冗余的。

因为X2⊆X1，且Y2⊆Y1，则有sup1≤sup2、conf1≤conf2，那么R1必然能够推出R2，R2是冗余的规则。比如，最小支持度0.5，最小置信度0.3，有两条关联规则R1：A，C→B，D(0.6，0.3)，R2：A→B(0.7，0.4)，可知R2R1，R1能够推出R2，则R2是冗余的关联规则。

由定义1可知，冗余关联规则没有固定某种数据集的限制，同时也避免了将用户所需要的信息删除的可能，从而能够更有效地删除真正重复、多余的关联规则。

1.2 算法描述

在一个关联规则R1中截取部分前件与部分后件重新构成一个关联规则R2，如果R2存在，那么R2所表现的关联模式完全可以用R1表现出来，则R2是冗余的。依据定义1，删除冗余关联规则见算法1.

算法1：删除冗余的关联规则

Input:File(全部的关联规则)Output:File(无冗余的关联规则)ForeveryLine in File FortempLine in otherLines IfeveryLine⊆tempLine (一条规则若被其他规则包含) ThenDelete everyLine(删除这条规则) ElseiftempLine⊆everyLine Then Delete tempLine EndIf EndForEndFor

对关联规则间的前件与后件进行相等判断，若某条关联规则被其他关联规则完全包含，那么删除该条关联规则。该算法主要耗费时间部分为访问文件中的n条关联规则的两个for循环，因此时间复杂度是T(n)=O(n2).

2 关联规则的聚类

K-means方法是基于划分式方法的一种聚类方法。它有线性的时间复杂度和线性的空间复杂度[17]。对大数据集有较高的效率，适合挖掘大规模数据集。但存在用户定义K和随机选择初始点以及对于噪声和离群点敏感的欧式距离定义[17]的缺陷。

本文针对K-means存在的缺陷，主要从两个方面进行改进：初始点的选择、相似性度量的定义。

2.1 初始点的选择

传统的K-means方法第一步是随机选取任意的k个对象作为初始聚类的中心，对聚类结果具有较大的影响。在文献[16]中，利用最大三角形方法来选取初始聚类中心，改善了K-means随机选择初始点的缺点，提高了聚类性能。参照文献[16]，在关联规则聚类中，其初始聚类中心选择过程如下：从生成的一组关联规则中，均匀随机选择k条关联规则，选择其中三个构造一个三角形，那么总共有C3k个三角形；计算一个区域内的所有三角形的个数之和记作S，它们的周长之和记作L，最小边记作Lens；如果θ*L/C3k≤ Lens(θ作为判断因素，θ=0.133)，那么保留这组k条关联规则集，同时保留S。若不满足，则丢弃这组关联规则集，并抛弃S.第四步，重复上面的过程Ts次，最大的S对应的k条关联规则当作K-means的初始聚类中心。

2.2 相似性度量的定义

K-means算法是基于距离的聚类算法，根据距离大小衡量两个对象之间的相似性，即距离越近，其相似度就越大。因此，距离的定义是影响聚类结果的主要因素。为了表示具有关联规则性质的聚类距离，可根据关联规则中前件与后件之间的关系，来定义关联规则的相似性度量。首先，采用Jaccard相似性系数形式来比较规则之间的相似度。其次，考虑规则前件与后件的重要性因素，引进两个参数α和β来限定它们的重要程度。

定义2：设有两条关联规则R1：X1→Y1(sup1，conf1)，R2：X2→Y2(sup2，conf2)，设X1有m项，Y1有o项，X2有n项，Y2有p项，m，o，n，p≥0.R1和R2之间的相似性度量表示为：

(1)

在此定义中，规则间的距离由加权后的规则前件交集数与后件交集数的和与两个规则总共项目数的比来度量。一般情况下，限定两者权重之间的关系为α+β=1，考虑到规则前件对于规则间相似性度量影响更大，因此令α取值偏大，如=0.6，β=0.4或=0.7，β=0.3.

2.3 聚类结果的显示

聚类后，会得到k(k为用户自定义)个聚类簇。由海量数据生成的关联规则，聚类后的结果依然很大，对于用户仍旧很难去寻找有用信息。考虑到置信度高的关联规则往往是用户所关心的，本文选择对置信度高的规则部分输出，以便于用户分析规律。具体操作如下：第一步，在每个聚类簇中，按照该聚类簇中各关联规则到簇中心的距离分为k个小类，其中，每个小类里的关联规则条数不定。第二步，假设一个小类中有p条关联规则。将这些关联规则按照置信度从高到低排序，选择置信度高的关联规则q%条(q=[1，100]，q可以根据规则数目做相应的调整)进行显示，那么这个聚类簇将会有p*q%*k条关联规则显示，很大程度上减少了关联规则数量，同时将较重要的规则突出呈现给用户，利于用户快速地发现规律。

2.4 算法描述

本节对算法进行了详细描述。聚类过程大致分为三个子过程：1)利用最大三角形方法选择初始点：构造三角形，所构造的三角形个数和最大值对应的k条关联规则作为初始聚类中心；2)计算关联规则之间的距离并分类：定义关联规则之间的相似性度量，并计算关联规则与聚类中心的距离，再根据距离对关联规则进行分配；3)判断聚类是否收敛，重新分配关联规则。

算法2：关联规则的聚类

3 实验结果及分析

实验环境：Intel Core i5-4570，2GB内存，Windows 7 64位操作系统，Microsoft Visual Studio 2010.实验数据：(1)采用关联规则挖掘数据集——蘑菇数据集，该数据集有8124个记录，由蘑菇的颜色、气味、形状、生长环境、… 、类别等23个属性组成，包含了蘑菇的127种不同属性；(2)国家天文台提供的SDSS恒星光谱数据，包含206维的8315条数据，前件是200个波长，后件包括6个物理化学性质，参照文献[18]对其离散化处理。

3.1 冗余关联规则

为了检验冗余关联规则的删除效果，本文用蘑菇数据集做了两组实验。第一组实验：分别对不同支持度、置信度时生成的关联规则进行冗余删除，结果如图1、图2所示。第二组实验：设置最小支持度=0.5，最小置信度=0.7对蘑菇数据集生成的18条关联规则进行冗余删除，剩余12条关联规则。如表1所示。

从图1和图2可以看出，该方法在不同最小支持度和不同最小置信度时都能够对关联规则集中的冗余有效地删除，且随着支持度和置信度的降低，关联规则数增多的情况下，该方法依旧能够达到很好的冗余删除效果。

从表1中可以看出，按照定义1，冗余的关联规则(10)～(13)、(16)、(17)相对于包含它的关联规则(14)、(18)置信度更高，即这些规则可以被其他规则推出，那么将其删除。从表1右侧删除后的关联规则集中可以看出，该方法能够有效的将原关联规则中冗余的关联规则删除，减少无关信息对用户的干扰。

图1 支持度阈值变化的实验结果(最小置信度=0.2)

Fig.1 Experimental results of the support threshold change (minimum confidence = 0.2)

图2 置信度阈值变化的实验结果(最小支持度=0.5)

Fig.2 Experimental results of the confidence threshold change (minimum support = 0.2)

采用文献[11]中ratio，结合本文重新定义ratio=non-redundancy rules/rules(删除冗余后的最终关联规则数与总关联规则数的比值)来衡量冗余关联规则的删除效果。若ratio越大，说明最终的无冗余关联规则数越多，即删除的冗余规则数量少，那么删除效果差，反之，ratio越小，冗余规则的删除效果越理想。将文献[10]中的Meta-rule方法和文献[11]中的Prefix-tree方法与本文方法进行冗余关联规则的删除效果对比，如表2所示。

表1 冗余关联规则的删除结果(最小支持度=0.5，最小置信度=0.7)

Tab.1 The results of deleting redundant association rules minimum support = 0.5, minimum confidence = 0.7)

表2 删除冗余关联规则

Meta-rule方法在定义冗余关联规则中，假定后件一样，当前件出现包含情况，定义被包含的规则为冗余规则，缺少了后件不同时候的情况。Prefix-tree中只考虑有相同的支持度与置信度时出现包含现象，被包含的关联规则是冗余规则，却忽略支持度与置信度不同时存在的冗余规则。从表2 ratio数值对比中可知，本文的方法每组ratio数值低，即删除冗余规则的效果最理想，因此本文的删除冗余关联规则方法是有效的。

3.2 关联规则聚类

3.2.1 K值对聚类的影响

对蘑菇数据集采用最小支持度0.8、最小置信度0.2，生成76条关联规则，删除冗余规则后剩下14条关联规则，用这14条关联规则进行实验，如表3所示。分别选取K=3，K=4，K=5时进行聚类(=0.6，β=0.4)，结果如表4所示。

聚类的目标是使每个聚类内尽可能相似，聚类间尽可能区分。比较表4(a)、4(b)、4(c)，可以看出K值的变化对聚类的影响较小，每个聚类内的趋势大致相同。当K=4时的聚类结果最理想：每个聚类内的规则间的前件具有共同的特征，且后件都一样，聚类内相似度高。对于不同聚类间的趋势最大程度上不同。因此，K=4作为后续实验的前提假设。

表3 关联规则

表4(a) K=5的聚类结果

表4(b) K=4的聚类结果

表4(c)K=3的聚类结果

选取聚类个数K=4，针对、β不同情况：当=0.4，β=0.6；=0.5，β=0.5；=0.6，β=0.4；=0.7，β=0.3时，分别对删除冗余后的蘑菇数据集进行聚类，如表5所示。

表5 不同、β取值的聚类结果(K=4)

Tab.5 The clustering result on different and β(K=4)

表5 不同、β取值的聚类结果(K=4)

a、β聚类规则集1聚类规则集2聚类规则集3聚类规则集4a=0.4,β=0.6(2)(6)(13)(8)(14)(7)(10)(12)(9)(11)(1)(3)(4)(5)a=0.5,β=0.5(2)(6)(7)(8)(10)(12)(9)(11)(13)(14)(1)(3)(4)(5)a=0.6,β=0.4(2)(6)(13)(7)(8)(10)(12)(14)(9)(11)(1)(3)(4)(5)a=0.7,β=0.3(13)(14)(7)(3)(10)(12)(9)(11)(1)(4)(5)(8)(2)(6)

3.2.3 聚类效率

通过与基于K-means的关联规则算法和基于密度的聚类关联规则算法DBSCAN对相同蘑菇关联规则的聚类时间(ms)进行对比，如表6所示。

表6 聚类运行时间(ms)

对于传统K-means对于庞大关联规则集中随机选取初始点的方法，本文采用在K条关联规则构建的三角形中迭代选择初始点，大量减少计算时间。DBSCAN算法主要处理低维数据，且复杂性高，面对高维数据时往往回导致维度灾难，达到最差时间复杂度T(n)=O(n2)。从表6中可知在对相同数量的关联规则进行聚类时，本文的聚类方法运行时间最短，因此，本文方法能够有效地减少了聚类时间，提高了聚类效率。

3.3 恒星光谱数据

参照文献[18]，由8315条恒星光谱数据，生成关联规则74056条(最小支持度=1%，最小置信度=50%)，采用本文算法，删除冗余关联规则后，还剩有34774条；对其34774条关联规则进行聚类，得到4个聚类簇。其聚类结果由表7(a)-(d)所示。

根据文献[18]可知，恒星光谱数据前200个属性为关联规则前件，后6个属性为关联规则后件。从表7(a)可知：聚类1中当波4570、4970、5730、6290处窄、很强的时候往往伴随着化学丰度4、5、微湍流2；从表7(b)可知：当波4930、5410处窄、弱；波5910、7170处特宽、一般、波6610处窄、一般的时候往往能够得到温度1属性；从表7(c)得出：当波4390、4750、5110、7550处窄；波5910、7170特宽一般的时候推出温度1或mh值1；从表7(d)得出：当波4010、4330、4890、5830处宽、较强时可获得温度6属性。此聚类方法将海量关联规则以聚类簇的方式清晰地将部分相似的关联规则集显示出来，能够让用户快捷得获取庞大数据内所需的关联信息，利于用户理解并发现规律。

表7 (a) 恒星光谱数据聚类规则集1

表7 (b) 恒星光谱数据聚类规则集2

表7 (c) 恒星光谱数据聚类规则集3

表7 (d) 恒星光谱数据聚类规则集4

4 结束语

用户面对大量的关联规则，难以选择有用信息。本文，采用改进的K-means聚类思想，给出了一种关联规则聚类算法，有效地约简了大量冗余关联规则，并将相似的关联规则归为一簇。最后，采用SDSS恒星光谱数据以及人工数据集，实验验证了该算法的可行性和有效性。

[1] LIN J L, DUNHAM M H. Mining association rules: Anti-skew algorithms[C]//Data Engineering, 1998. Proceedings.14th International Conference on. IEEE, 1998: 486-493.

[2] KUO R J, CHAO C M, ChiuY T. Application of particle swarm optimization to association rule mining[J]. Applied Soft Computing, 2011, 11(1): 326-336.

[3] HO G T S, IP W H, WU C H, et al. Using a fuzzy association rule mining approach to identify the financial data association[J]. Expert Systems with Applications, 2012, 39(10): 9054-9063.

[4] WANG H, LIU P, LI H. Application of improved association rule algorithm in the courses management[C]//Software Engineering and Service Science (ICSESS), 2014 5th IEEE International Conference on. IEEE, 2014: 804-807.

[5] PERI H, KUMAR P. Application of association rule mining to help determine the process of career selection[J]. International Journal of Computer Application, 2014, 94(16): 15-19.

[6] SIMON G J, SCHROM J, CASTRO M R, et al. Survival association rule mining towards type 2 diabetes risk assessment[C]//AMIA Annual Symposium Proceedings. American Medical Informatics Association, 2013: 1293.

[7] 武霞,董增寿,孟晓燕. 基于大数据平台 hadoop 的聚类算法K值优化研究[J].太原科技大学学报,2015,36(2):92-96.

[8] HAN J, KAMBER M,数据挖掘概念与技术[M].范明,孟小峰,译.北京：机械工业出版社2004.

[9] LIU H, LIU L, ZHANG H. A fast pruning redundant rule method using Galois connection[J]. Applied Soft Computing, 2011, 11(1): 130-137.

[10] BERRADO A, RUNGER G C. Using metarules to organize and group discovered association rules[J]. Data Mining and Knowledge Discovery, 2007, 14(3): 409-431.

[11] PHAM T T, LUO J, HONG T P, et al. An efficient method for mining non-redundant sequential rules using attributed prefix-trees[J]. Engineering Applications of Artificial Intelligence, 2014，32: 88-99.

[12] NGUYEN L T T, VO B, HONG T P, et al. Classification based on association rules: A lattice-based approach[J]. Expert Systems with Applications, 2012, 39(13): 11357-11366.

[13] 韦素云,吉根林,曲维光.关联规则的冗余删除与聚类[J].小型微型计算机系统, 2006,27(1):110-113.

[14] 张爱芳.基于密度网格的关联规则开采及聚类算法[D].华中科技大学,2004.

[15] LIU G, HUANG S, LU C, et al. An improved K-means Algorithm Based on Association Rules[J]. International Journal of Computer Theory and Engineering, 2014, 6(2): 146-150.

[16] FENG J, LU Z, YANG P, et al. A K-means clustering algorithm based on the maximum triangle rule[C]// Mechatronics and Automation (ICMA),2012 International Conference on. IEEE, 2012: 1456-1461.

[17] CELEBI M E, KINGRAVI H A, Vela P A. A comparative study of efficient initialization methods for the K-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1): 200-210.

[18] 张继福,赵旭俊.一种基于约束 FP树的天体光谱数据相关性分析方法[J].模式识别与人工智能,2009(4): 639-646.

An Association Rule Clustering Algorithm Based on K-means

WANG Zhuo, XUN Ya-ling, ZHANG Ji-fu

(School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Association rule is one of the main research contents in the filed of data mining. For mining the association rule on massive and high-dimensional data set, a large number of redundant and similar association rules will be generated if the support or confidence threshold is low, so that it will cause difficulties to understand and use the rules. In this paper，an association rule clustering algorithm is presented by using improved K-means idea, which improves the understandability of association rules. First, the redundant association rules is redefined, and a method of deleting the rules is presented. Second，a new similarity measure of the rules is defined according to the structure characteristics between antecedent and consequent of association rules. Third，by using largest triangle method to select the initial cluster points and the idea of K-means, a clustering algorithm of association rules is presented to analyze association rules after deleting redundant rules, and put them into one cluster, and let users find useful association rules quickly and efficiently. In the end, the experiments on celestial spectra data and simulated datasets verified the feasibility and effectiveness of the algorithm.

an association rule clustering algorithm, redundant association rules, similarity measurement, celestial spectra data

1673-2057(2016)06-0429-09

2015-11-09

王琢(1990-)，女，硕士研究生，研究方向为数据挖掘与知识工程；通信作者：张继福教授，E-mail:jifuzh@sina.com

TP391

A

10.3969/j.issn.1673-2057.2016.06.003