引用本文

徐森, 皋军, 花小朋, 李先锋, 徐静. 一种改进的自适应聚类集成选择方法. 自动化学报, 2018, 44(11): 2103-2112. doi: 10.16383/j.aas.2018.c170376

XU Sen, GAO Jun, HUA Xiao-Peng, LI Xian-Feng, XU Jing. An Improved Adaptive Cluster Ensemble Selection Approach. ACTA AUTOMATICA SINICA, 2018, 44(11): 2103-2112. doi: 10.16383/j.aas.2018.c170376

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170376

关键词

机器学习，聚类分析，聚类集成，聚类集成选择 

摘要

针对自适应聚类集成选择方法（Adaptive cluster ensemble selection，ACES）存在聚类集体稳定性判定方法不客观和聚类成员选择方法不够合理的问题，提出了一种改进的自适应聚类集成选择方法（Improved ACES，IACES）.IACES依据聚类集体的整体平均归一化互信息值判定聚类集体稳定性，若稳定则选择具有较高质量和适中差异性的聚类成员，否则选择质量较高的聚类成员.在多组基准数据集上的实验结果验证了IACES方法的有效性：1）IACES能够准确判定聚类集体的稳定性，而ACES会将某些不稳定的聚类集体误判为稳定；2）与其他聚类成员选择方法相比，根据IACES选择聚类成员进行集成在绝大部分情况下都获得了更佳的聚类结果，在所有数据集上都获得了更优的平均聚类结果.

文章导读

聚类分析的目标是依据对象之间的相似度对其自动分组/簇, 使得簇内对象彼此相似度尽量高, 而簇间对象彼此相似度尽量低[1-2].虽然已有上千种聚类算法, 但没有一种能有效识别不同大小, 不同形状, 不同密度甚至可能包含噪声的簇[1].已有聚类方法主要分为: 1)基于划分的方法, 将聚类问题转化为优化问题, 并采用不同的优化策略, 例如, K均值算法(K-means, KM)[3]、非负矩阵分解(Non-negative matrix factorization, NMF)[4]、近邻传播算法(Affinity propagation, AP)[5]、子空间聚类算法[6]以及基于深度学习[7]的聚类算法[8]; 2)层次聚类[2], 例如单连接(Single linkage, SL)、全连接(Complete linkage, CL)、组平均(Average linkage, AL); 3)基于模型的方法[1], 将聚类问题转化为模型的充分统计量估计问题; 4)基于密度的方法, 通过寻找被低密度区域分离的高密度区域来进行聚类, 例如密度峰值(Density peaks, DP)算法[9]、谱聚类方法[10]; 5)基于谱图理论将聚类问题转化为图划分问题.

2002年, 文献[11]正式提出聚类集成(Cluster ensemble), 通过组合多个不同的聚类结果能够获得更加优越的最终结果, 具有传统聚类算法无可比拟的优势[12].早期的聚类集成研究主要围绕聚类成员生成和共识函数设计问题展开, 目前已有较多聚类成员生成方法及共识函数设计方法[13-26].受"选择性集成学习"研究启发, 文献[27]于2008年开启了选择性聚类集成研究, 其关键问题为聚类成员选择问题, 即如何从所有聚类成员集合(称为聚类集体)中选出部分聚类成员用于后续集成, 获得比对所有聚类成员进行集成更加优越的结果.文献[27]提出了质量和多样性综合准则(Joint criterion, JC)、聚类并选择(Cluster and select, CAS)和凸包(Convex hull, CH)三种方法.文献[28]提出了自适应聚类集成选择(Adaptive cluster ensemble selection, ACES), 依据聚类成员与初始一致划分π∗的归一化互信息(Normalized mutual information, NMI)将聚类集体分为稳定和不稳定两类, 并选择不同的聚类成员子集. ACES方法存在两个问题: 1)判定聚类集体稳定性的方法不客观, 稳定性与初始一致划分π∗有关, 在某些情况下容易将不稳定的聚类集体误判为稳定.当聚类成员之间差异性较低时, NMI值较大, 且NMI值大于0.5的比例较高, 聚类成员与π∗的NMI值也较大, 此时聚类集体稳定; 当聚类成员之间差异性较高时, NMI值较低, 平均NMI值低于0.5, 且NMI值大于0.5的比例低于50%, 但仍然有绝大多数的聚类成员与π∗的NMI值大于0.5, 此时虽然聚类集体不稳定, 但ACES方法却判定聚类集体是稳定的. 2)聚类成员子集的选择方法不够合理.当聚类集体稳定时, ACES简单地选择Full集并输出π∗, 而没有进一步选择差异性较高的聚类成员来提高集成效果; 当聚类集体不稳定时, ACES简单地选择High集, 可能会选出少量聚类质量较差的聚类成员.

本文针对ACES存在的问题, 提出了一种改进的自适应聚类集成选择方法(Improved adaptive cluster ensemble selection, IACES).本文把所有聚类成员的整体平均NMI值(Total average NMI, TANMI)作为判定聚类集体是否稳定的依据, 若TANMI大于0.5, 则聚类集体稳定; 否则, 不稳定.有效解决了上述第一个问题.当聚类集体稳定时, 聚类成员提供相似的聚类结构, 差异可能由聚类算法陷入局部最优值引起, π∗能够在一定程度上减小聚类成员之间差异引起的方差, 可能比聚类成员更加接近于真实分类结果.与ACES选择Full集不同, 本文首先选择与π∗的差异性最低(NMI值最大)的1/4的聚类成员, 降低平均误差; 然后选择与π∗的差异性最高(NMI值最小)的1/4的聚类成员, 增加平均差异性; 另外, 为了避免选出离群点, 通过约束聚类成员的平均NMI值(Average NMI, ANMI)排名高于某一阈值.此时, 选出的聚类成员既具有较高质量, 又具有适中的差异性, 往往能够获得比π∗更加优越的结果.当聚类集体不稳定时, 聚类成员提供了不同的聚类结构, 差异可能由聚类算法本身的偏置或数据集的复杂结构引起, 此时π∗偏离真实分类结果的可能性较大, 因此应该尽量降低聚类成员的平均误差, 选择与π∗差异性大的聚类成员(High集)往往会得到更好的结果.但High集里会存在一些质量较差的聚类成员, 此时通过约束聚类成员ANMI值排名高于某一阈值, 能够在很大程度上避免选出质量较差的聚类成员.有效解决了上述第二个问题.

图 1  选择性聚类集成系统框架

图 2  采用聚类集体P1时获得的聚类结果(NMI值和F值)

图 3  采用聚类集体P2时获得的聚类结果(NMI值和F值)

本文提出了一种改进的自适应聚类集成选择方法(IACES), 有效解决了ACES存在的聚类集体稳定性判定方法不客观和聚类成员选择方法不够合理的问题.在多组基准数据集上进行了实验, 实验结果表明: 1) IACES能够准确判定聚类集体的稳定性, 而ACES会将某些不稳定的聚类集体误判为稳定; 2)与其他聚类成员选择方法相比, 根据IACES选择聚类成员进行集成在绝大部分情况下都获得了更佳的聚类结果, 在所有数据集上都获得了更优的平均聚类结果.

作者简介

皋军

盐城工学院信息工程学院教授.主要研究方向为机器学习, 人工智能.E-mail:gaoj@ycit.cn

花小朋  

盐城工学院信息工程学院副教授.主要研究方向为机器学习, 人工智能.E-mail:huaxp@ycit.cn

李先锋  

盐城工学院信息工程学院副教授.主要研究方向为机器学习, 人工智能.E-mail:lxf@ycit.cn

徐静  

盐城工学院信息工程学院副教授.主要研究方向为机器学习, 人工智能.E-mail:xujingycit@163.com

徐森  

盐城工学院信息工程学院副教授.主要研究方向为机器学习, 人工智能, 文本挖掘.本文通信作者.E-mail:xusen@ycit.cn