2019, Vol. 51
2. 计算智能与中文信息处理教育部重点实验室 山西 太原 030006
2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Taiyuan 030006, China
聚类分析是数据挖掘中的一个重要研究领域.它是针对给定的数据集，根据元素之间的相似性度量自动将相似的元素划分到同一组，使得组内元素的相似性达到最大而组间元素的相似性达到最小的过程.聚类分析已被广泛应用于图像处理、信息检索和生物信息学等研究领域[1].
目前，已有多种聚类算法被提出，例如基于层次的、基于划分的、基于密度的、基于网格的和基于模型的方法等.由于数据的复杂性与算法自身参数的影响，单一算法无法有效地完成聚类任务，所以将多个聚类结果进行融合是聚类分析的一个重要研究内容.集成学习通过集成多个不同的学习器来解决同一个问题，提高了系统的学习能力.聚类集成利用集成学习技术，通过将数据集的多个聚类结果融合，得到一个新的聚类结果.Fred[2]和Strehl等[3]分别于2001年和2002年提出了聚类集成的概念.聚类集成主要有两大任务：基聚类的产生和一致性函数的设计.为了得到更好的聚类集成效果，基聚类的成员应具有一定的差异性.目前生成基聚类成员[4-6]主要有以下方法：对同一数据集使用不同的聚类算法；在使用相同算法时设定不同的初始化参数；使用数据集不同的特征子集；将数据集投影到子空间以及添加人工噪声数据等.在得到具有差异性的基聚类成员后，需对其进行集成以得到最后的标签.集成即一致性函数[7]的设计有基于相似性度量的方法[8]、基于图论的方法[9]、基于标签对齐的方法[10-12]以及基于特征转换的方法[13]等.
虽然已有多种聚类集成算法被提出，但现有的聚类集成算法更多地追求最大基聚类的一致性，集成效果受到基聚类质量的影响.当基聚类结果很差时，最终的聚类集成效果会不理想.因此，本文在一致性函数设计时将原数据类结构纳入考虑中.将基聚类与原数据看作一个混合型数据，提出了一种基于混合型数据表示的聚类集成算法，该算法考虑了聚类集成结果对原数据类结构和基聚类的一致性.与MCLA、HGPA、CSPA、Voting、WCT、WTQ、CSM、LWGP聚类集成算法进行了比较, 结果表明，基于混合型数据表示的聚类集成算法具有较好的聚类结果.
1 基于混合型数据表示的聚类集成算法 1.1 基于混合型数据的表示数据可分为数值型数据、符号型数据和混合型数据.例如匿名统计学生信息S={身高，体重，班级}时，既统计身高、体重等数值型信息，也统计班级等符号型信息，这种类型的数据被称为混合型数据.
令X={X1, X2, …, Xn}表示具有n个样本的数据集，其中Xi={Xi1, Xi2, …, Xim}表示第i个样本的m个属性，数据集表示成n×m的矩阵.对数据集进行T次聚类，Ri={Ri1, Ri2, …, RiT}表示第i个样本在T次聚类下的结果，基聚类结果表示成n×T的矩阵.
定义1 将基聚类结果看作原数据的符号型属性，其和原数据合并成一个n×s的混合型数据.混合型数据中Xi={Xi1, …, Xim, Xi(m+1), …, Xis}表示第i个样本的s个属性，其中下标为1~m的属性为数值型属性，下标为m+1~s的属性为符号型属性，即基聚类.
1.2 基于混合型数据表示的聚类集成算法对数据集进行T次K-Means聚类得到基聚类结果，为了将原数据类结构考虑到集成过程中，在集成策略的选择上将基聚类结果作为原数据的符号型属性，将符号型数据与原数据结合，看作一个混合型数据来进行聚类.聚类方法采用K-Prototypes，对混合型数据进行T次K-Prototypes聚类, 得到T个聚类集成结果.将T个聚类集成结果看作新的符号型数据集，代替原先的符号型数据再进行聚类集成，循环Q次结束，通过不断迭代优化, 以得到更好的基聚类.在最后一次得到的T个集成结果中，将目标函数值最小的集成结果选为最后的类标签.算法具体步骤如下：
Step 1 对数据集进行T次K-Means聚类，将基聚类结果看作数据集的符号型属性，将原数据与其合并成一个混合型数据.
Step 2 在混合型数据中随机选取k个样本作为初始类原型.
Step 3 对数据集中的每个样本，根据式(1)~(3)计算其与每个类原型的相异性，并将样本分配到与其最近的类原型所代表的类中.
| $ D({X_i}, {X_j}) = \sum\limits_{l = 1}^s {d({X_{il}}, {X_{jl}})}, $ | (1) |
| $ d({X_{il}}, {X_{jl}}) = \left\{ \begin{array}{l} {({X_{il}} - {X_{jl}})^2}, {\text{若属性为数值型}}\\ \delta ({X_{il}}, {X_{jl}}), {\text{若属性为符号型}} \end{array} \ \ \ \ \ \ \ \ \ \ \ \right. , $ | (2) |
| $ \delta ({X_{il}}, {X_{jl}}) = \left\{ \begin{array}{l} 1, {X_{il}} \ne {X_{jl}}\\ 0, {X_{il}} = {X_{jl}} \end{array} \right.. $ | (3) |
Step 4 重新计算每个类的类原型.数值型属性部分取类内全部对象的均值，符号型属性部分取出现次数最多的属性组成类原型.
Step 5 循环Step 3、Step 4，直到每个类中的样本不再发生变化为止.
Step 6 将Step 2~Step 5循环T次，用每次得到的结果矩阵替换Step 1中的基聚类.
Step 7 将Step 6循环Q次结束，在最终的结果矩阵中选取结果类标签.
算法的最大优势在于在集成过程中既保证了最终结果对基聚类的一致性，也考虑了原数据类结构与结果的一致性.算法的时间复杂度为O(knstTQ)，空间复杂度为O(ns)，其中k为聚类的目标类数；n表示数据集中的对象数；s为混合型数据的属性个数；t为Step 5中的迭代次数；T为Step 6中的循环次数；Q为Step 7中的循环次数.
2 实验分析 2.1 实验数据为了验证所提出算法的有效性，从UCI真实数据集中选取了不同的数据集进行了测试.UCI数据集描述如表 1所示.
|
表 1 UCI数据集描述 Tab. 1 Description of UCI data sets |
使用调整兰德系数(ARI)以及标准互信息(NMI)来评价聚类质量.假设U={U1, U2, …, Uk}表示聚类结果标签，U′={U′1, U′2, …, U′k}表示真实类标签，k表示划分的类数，nij表示在真实标签中属于第i类且在聚类标签中属于第j类的对象个数，bi表示聚类标签是Ui的个数，b′j表示真实标签是U′j的个数.ARI和NMI的计算公式分别为
| $ ARI\left( {U, U'} \right) = \frac{{{r_0} - {r_3}}}{{({r_1} + {r_2})/2 - {r_3}}} $ |
其中：
| $ NMI\left( {U, U' } \right) = \frac{{\sum\limits_{i = 1}^k {\sum\limits_{j = 1}^k {{n_{ij}}{\rm{log}}\frac{{n{n_{ij}}}}{{{b_i}{{b'}_j}}}} } }}{{\sqrt {\left( {\sum\limits_{i = 1}^k {{b_i}{\rm{log}}\frac{{{b_i}}}{n}} } \right)\left( {\sum\limits_{j = 1}^k {{{b'}_j}{\rm{log}}\frac{{{{b'}_j}}}{n}} } \right)} }}. $ |
将本文算法与其他聚类集成算法进行了比较，选用的比较算法有MCLA[3]、HGPA[3]、CSPA[3]、Voting[10]、WCT[8]、WTQ[8]、CSM[8]、LWGP[14]，在UCI数据集中的7个真实数据集上进行测试.对本文算法进行30次K-Means聚类, 生成具有差异度的基聚类，对混合型数据进行30次K-Prototypes聚类，迭代10次得到最后的结果.实验结果是在每个数据集上运行多次, 得到结果的平均值，不同算法的ARI值比较如表 2所示，不同算法的NMI值比较如表 3所示.每个数据集上不同方法的最优值用黑色粗体进行标识.
|
|
表 2 不同算法的ARI值比较 Tab. 2 Comparison on different algorithms with respect to ARI |
|
|
表 3 不同算法的NMI值比较 Tab. 3 Comparison on different algorithms with respect to NMI |
通过表 2可知，在ARI指标上，本文算法在7个数据集中有6个数据集都得到了最优值，在未取得最优值的数据集上其结果与最优值也相差不大，均值在所有算法中是最优的.同样通过表 3可知，在NMI指标上，本文算法在7个数据集中也有6个数据集都得到了最优值，且均值在所有算法中是最优的.分析数据可知，本文设计的聚类集成算法相比其他算法有较好的聚类结果.
3 结束语提出了一种基于混合型数据表示的聚类集成算法.在聚类集成过程中，不断迭代优化基聚类结果，在一致性函数设计时将原数据类结构纳入考虑，保证了集成结果对原数据类结构与基聚类的一致性.在UCI数据集上与已有的聚类集成算法进行比较，实验结果表明，本文提出的算法可以获得较好的聚类集成结果.
| [1] |
HAN J W, KAMBER M, PEI J. Data mining: concepts and techniques[M]. 3rd ed. San Francisco: Morgan Kaufmann Publishers, 2011.
(  0) |
| [2] |
FRED A. Finding consistent clusters in data partitions[C]//International Workshop on Multiple Classifier Systems. Cambridge, 2001: 309-318. https://link.springer.com/chapter/10.1007%2F3-540-48219-9_31
( 0) |
| [3] |
STREHL A, GHOSH J. Cluster ensembles: a knowledge reuse framework for combining multiple partitions[J]. Journal of machine learning research, 2002, 3(12): 583-617. ( 0) |
| [4] |
罗会兰.聚类集成关键技术研究[D].杭州: 浙江大学, 2007. http://cdmd.cnki.com.cn/Article/CDMD-10335-2008045886.htm
( 0) |
| [5] |
YANG Y, KAMEL M. An aggregated clustering approach using multi-ant colonies algorithms[J]. Pattern recognition, 2006, 39(7): 1278-1289. DOI:10.1016/j.patcog.2006.02.012 ( 0) |
| [6] |
TOPCHY A, JAIN A K, PUNCH W. Clustering ensembles: models of consensus and weak partitions[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(12): 1866-1881. DOI:10.1109/TPAMI.2005.237 ( 0) |
| [7] |
ZHOU Z H. Ensemble methods: foundations and algorithms[M]. Boca Raton: CRC Press, 2012.
( 0) |
| [8] |
IAMON N, BOONGOEN T, GARRETT S, et al. A link-based approach to the cluster ensemble problem[J]. IEEE transactions on pattern analysis and machinie intelligence, 2011, 33(12): 2396-2409. DOI:10.1109/TPAMI.2011.84 ( 0) |
| [9] |
HUANG D, LAI J H, WANG C D. Robust ensemble clustering using probability trajectories[J]. IEEE transactions on knowledge and data engineering, 2016, 28(5): 1312-1326. DOI:10.1109/TKDE.2015.2503753 ( 0) |
| [10] |
ZHOU Z H, TANG W. Clusterer ensemble[J]. Knowledge-based systems, 2006, 19(1): 77-83. DOI:10.1016/j.knosys.2005.11.003 ( 0) |
| [11] |
GONZALEZ E, TURMO J. Unsupervised ensemble minority clustering[J]. Machine learning, 2015, 98(1/2): 217-268. ( 0) |
| [12] |
于洪, 陈云. 基于Spark的三支聚类集成方法[J]. 郑州大学学报(理学版), 2018, 50(1): 20-26. ( 0) |
| [13] |
LIU H F, WU J J, LIU T L, et al. Spectral ensemble clustering via weighted K-Means: theoretical and practical evidence[J]. IEEE transactions on knowledge and data engineering, 2017, 29(5): 1129-1143. DOI:10.1109/TKDE.2017.2650229 ( 0) |
| [14] |
HUANG D, WANG C D, LAI J H. Locally weighted ensemble clustering[J]. IEEE transactions on cybernetics, 2017, 48(5): 1460-1473. ( 0) |