一种基于Hartigan-Wong和Lloyd的定性平衡聚类算法  

Qualitative balanced clustering algorithm based on Hartigan-Wong and Lloyd

作　　者：周旺[1] 张晨麟 吴建鑫[1] 

机构地区：[1]南京大学计算机软件新技术国家重点试验室,江苏南京210046

出　　处：《山东大学学报（工学版）》2016年第5期37-44,共8页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金优秀青年科学基金资助项目(61422203);中央高校基本科研业务费专项资金资助项目(20620140498)

摘　　要：基于传统的Hartigan-Wong聚类算法会产生不平衡聚类结果的缺点,提出一种新的聚类算法Charl,这种算法会改进聚类结果的平衡性但不要求绝对平衡。结合Lloyd算法和Hartigan-Wong算法的思想,Charl算法采用一种自适应性的动态调整策略来调整平衡程度。跟Lloyd算法一样,Charl算法以批处理的方式更新中心,所以具有计算高效的性质。在13个数据集上进行的试验表明,Charl方法不仅产生了平衡的聚类结果,并且同时得到了比Lloyd算法更低的代价函数值和更好的聚类性能(聚类准确率、归一化互信息、聚类时间等)。这种定性平衡聚类算法也明显优于严格平衡的聚类算法。The traditional Hartigan-Wong clustering algorithm could cause the unbalanced clustering problem. To solve this problem,Charl which is a novel qualitative balanced clustering method was proposed to improve the balance level while the absolute balance was not required. Charl combined ideas from both the Lloyds method and the Hartigan-Wong method,Charl proposed an adaptive tuning strategy to tune the balance level. This algorithm was a batch processing method,which shared the efficiency benefits of the Lloyds method. Experiments on 13 benchmark datasets showed that Charl not only produced more balanced output groups,but also achieved lower cost values and higher clustering performances（ in terms of accuracy,normal mutual information and time cost） than the Lloyds method. This qualitative balancing method also outperformed the quantitative balanced clustering method by a large margin.

关 键 词：平衡聚类 定性平衡 Hartigan-Wong Lloyd 机器学习 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]