基于修剪树的优化聚类中心算法  

Optimized clustering center based on trimmed tree

作　　者：周小亮 吴东洋[1] 曹磊 王玉鹏 业宁[1] Zhou Xiaoliang;Wu Dongyang;Cao Lei;Wang Yupeng;Ye Ning(School of Information Science and Technology,Nanjing Forestry University,Nanjing,210037,China)

机构地区：[1]南京林业大学信息科学技术学院,南京210037

出　　处：《南京大学学报（自然科学版）》2021年第2期167-176,共10页Journal of Nanjing University（Natural Science）

基　　金：国家重点研发计划(2016YFD0600101);江苏省住房和城乡建设厅计划(2016ZD44);江苏省研究生科研与实践创新计划(KYCX20_0894);汕尾市省级科技创新项目(2018D2002)。

摘　　要：针对传统聚类算法存在样本形状及孤立点敏感的问题,提出基于修剪树的优化聚类中心(Optimized Clustering Center Based on Trimmed Tree,OCT)算法.该算法自适应地寻找裁剪尺寸来修剪并分割最小生成树为森林,获取森林全部叶子结点并再次构造最小生成树,根据预设簇数n,修剪最小生成树的n-1条最长边,得到包含n棵树的森林,计算森林中每棵树的质心并将其置为初始类簇聚类中心.在仿真数据集和真实数据集上的测试结果表明,OTC算法的平均识别率分别为98.8%和95.7%,平均耗时为57 ms和10.53 ms.To solve the problem of sample shape and outlier sensitivity in traditional clustering algorithm,an optimized clustering center algorithm,OCT(Optimized Clustering Center Based on Trimmed Tree)based on pruning tree is proposed.This algorithm adaptively searches the cutting size to prune and divide the minimum spanning tree into a forest,obtains all the leaf nodes of the forest and constructs the minimum spanning tree again.According to the preset number of clusters n,the OCT algorithm trims the longest n-1 edge of the minimum spanning tree to get the forest containing n trees,then calculates centroid of each tree in the forest and sets it as the initial cluster center.The experimental results on the simulation dataset and the real dataset show that the average recognition rate of OCT algorithm is 98.8%and 95.7%,and the average time⁃consuming is 57 ms and 10.53 ms.

关 键 词：最小生成树 质心偏量 样本偏量 聚类分析 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]