- 1 -
中国科技论文在线
基于半监督 K-means的主动学习聚类算法
#
孙凯1,2，孟祥武1,2**
（1. 北京邮电大学 智能通信软件与多媒体北京市重点实验室,北京 100876； 5
2. 北京邮电大学 计算机学院,北京 100876）
基金项目：基金项目：北京市教育委员会共建项目
作者简介：孙凯（1990-），男，硕士研究生，主要研究方向：智能信息处理与推荐系统
通信联系人：孟祥武（1966-），男，教授，博士生导师，主要研究方向：网络服务、智能信息处理、通信
软件
摘要：针对 K-means 算法对初始聚类中心敏感，针对不规则聚类簇效果较差的缺点，提出
了一种基于半监督 K-means 的主动学习算法。为了针对指定的 k 个类别进行聚类，首先通
过半监督聚类估算出每个类的中心，然后通过循环迭代过程中对特征值权重的反馈调节来适10
应指定聚类。对于 K-means 算法会对不规则类簇聚类效果差的问题，通过每次迭代时，影
响多个类簇中心来实现较为精确的中心调整。在 UCI 中的 20 Newsgroups 和真实数据集实验
表明，该算法在 F1-measure 指标上较其他几种算法，提升了分类精度。
关键词：K-means 算法;聚类算法;机器学习;噪声过滤
中图分类号：TP391 15
Active learning clustering algorithm based on
semi-supervised K–means
SUN Kai
1,2
, MENG Xiangwu
1,2
(1. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing 20
University of Posts and Telecommunications, Beijing 100876 China;
2. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing
100876 China)
Abstract: To solve the shortcomings of K-means algorithm, which is sensitive to initial clustering
center and vulnerable to noise, a Active learning clustering algorithm based on semi-supervised 25
K–means is proposed. In order to cluster fixed k classes, we first estimate the center of each class by
semi-supervised clustering and then adjust the clustering by feedback adjustment of eigenvalue weights
in the iterative process. During clustering process, adjusting the cluster centers can solve the problems
which the K-means algorithm is sensitive to the irregular clusters. Experiments on 20 Newsgroups in
UCI and real datasets show that the proposed algorithm improves the classification accuracy compared 30
with other algorithms in terms of F1-measure.
Key words: kK-means; classification algorithm; machine learning; Noise filtering
0 引言 35
数据挖掘技术（Data Mining）是从大量的、不完全的、有噪声的、模糊的、随机的实
际应用数据中，发现并提取隐含在其中未知的、可信的、有用的模式的过程[1]。在数据挖掘
任务中，由于大量标记数据的获取需要昂贵的代价，实际数据往往由大量无标记数据和少量
标记数据组成。半监督学习是处理此类数据的一种学习方法，近年来受到众多研究者的关注
- 2 -
中国科技论文在线
[2]。
半监督学习算法从学习方式上可以分为半监督分类算法和半监督聚类算法[3]。半监督分
类是在有监督分类的基础上，通过无标记数据指导分类过程，以提高分类的准确性；半监督
聚类是在无监督聚类的基础上，通过标记数据指导聚类过程，以提高聚类质量[4]。K-means
聚类作为聚类算法优质算法之一，近年来受到部分研究者的关注。半监督聚类可以在一定程5
度上改善 K-means 算法有聚类中心敏感且无法保证所得结果是用户指定分类的缺点，并实
际应用于管道检测[5]、SAR 图像[6]等众多领域中。
1 国内外研究现状
MacQueen
[7]最早提出 K-means 聚类的思想，并给出一个经典的算法，然而该算法的聚
类代价巨大，且聚类的质量较差。后来的半聚类研究中，孙雪[8]等人打破 K 值的限定，结合10
数据集自身的分布特点及聚类后各个簇内的监督信息，根据投票方法来指导簇中数据集的类
别标记。袁利永[9]等人改进了 K-means 方法的迭代流程，把已标签数据对未标签数据的引力
影响加入到类别分配决策中，提升了聚类中心的精确度。陈新泉[10]等人融合 K-means 方法
针对针对一些局部分布稀疏不均、聚类区域的形状及大小很不规整的数据点集，提出了一种
基于最小生成树结构的改进算法。 15
以上的半聚类算法中，主要针对数据集本身稀疏和不规则的问题进行了改进，对于用户
需要得到指定分类的情况难以得到满足，因此本文提出一种在用户偏好影响下的半监督
K-means 分类算法，通过不断的分类修正，最终可以达到良好的指定聚类效果。主要针对用
户对数据有指定的分类，但要求数据中小部分样本点已经标记所属类别，聚类后类别可控。
本文主要贡献为针对用户需求，考虑到自动聚类成果与用户所需类别不符的情况，通过20
反馈调节来调整特征权重，以生成符合用户需求的聚类模型。本文第3节详细阐述了K-means
算法的大致算法描述，再此基础上详细论述了基于半监督 K-means 的主动学习聚类算法具
体思想和算法流程。第 3 节提供详细的实验和数据以证明改进后的 K-means 算法的聚类质
量和执行效率。最后是本文得出的结论。
2 K-means 算法与用户学习聚类算法 25
针对 K-means 算法中，聚类效果依赖初始聚类中心的缺点，多数学者[11]通过半聚类方
式来解决。由相关领域专家对聚类样本中的小部分进行人工分类，借由这些有标签样本得出
初始聚类中心，然后继续进行 K-means 聚类。
半监督 K-means 算法虽然对初始聚类中心的选择进行了优化，但仍不能控制在循环迭
代部分聚类中心的偏移和无法适应不规则类群的问题。针对聚类中心的偏移的局限性，本文30
提出一种加权的距离计算方式，在半监督算法给出聚类中心的基础上，通过在每次迭代过程
后，针对错误聚类样本，对其在不同的特征维度上的类别距离进行权重的调整，使其最终的
聚类结果为正确类别，从而改善整体特征权重以适应用户的个性化分类。而针对无法适应不
- 3 -
中国科技论文在线
规则类群的缺点，本文采用类似于 Neural Gas 算法的策略，根据样本点与聚类中心的距离，
每次影响 Top N 个聚类中心的偏移，从而达到适应于不规则分类簇的情况。基于半监督
K-means 的用户学习聚类算法首先通过相关用户给出的少量有标签样本，通过计算每个类别
的特征均值以得到 k 个聚类中心，然后开始 K-means 聚类。设初始类别 i 中的有标签样本为
Si={si1,si2,…, sij,…,sin}，其中 sij为 n 为特征向量。则其聚类中心为： 5
1
,i ij ij ic s s S
n
(1)
然后依次计算每个样本点与所有聚类中心的距离，样本点 xj与聚类中心 ci的距离 di表
示为：
( ) ( )Ti j i i j id x c x c r (2)
其中，对角矩阵 ri是类别 i 的特征权重矩阵，初始为单位矩阵。每次聚类时，如果样本10
点距离最佳中心小于阀值，则对其他聚类中心影响较小；如果样本点聚类最佳中心大阀值，
则对其他聚类中心影响较大。根据每次的聚类结果，反馈调节该权重矩阵，该文章在特征维
度 p 上与类 i 之间的距离记为 dpi：
2( )
p p p ppi j i i
d x c r (3)
其中 ripp为类 i 在特征 p 上的聚类权重。在计算所有特征上的距离后，选择最小距离15
min{dip}作为样本点 xj在特征 p 上的分类结果，根据特征选择的结果若与反馈中的结果相同，
更新权重 ripp：
1
1 1
pp pp
pp pp
i i i i
i i
i i
r S r S
r r
S S
，反之 (4)
调整后判断该特征是否在各分类下权重值均小于φ （一般取 1/k），若是则在该分类中
过滤掉该特征。对于 K-means 算法自身存在的对离散点和孤立点敏感，易于陷入局部最优20
等特点，反馈调节过程可以良好的改善上述缺点。基于半监督 K-means 的主动学习聚类算
法描述如下：
表 1 基于半监督 K-means 的主动学习聚类算法
"Active learning clustering algorithm based on semi-supervised K–means"
基于半监督 K-means的主动学习聚类算法
输入：聚类数目 k和包含有 n个对象的数据集，数据集包含小部分的有标签数据和大部分的无标签数据
输出：满足目标函数最小的 k簇和筛选后的特征值以及对应权重
1 将数据集划分为训练集、验证集和测试集，其中训练集中应包含有标签数据
2 在训练集中，通过公式(1)使用有标签数据出 k个聚类中心
3 计算训练集中样本点与聚类中心距离(2)，将其划分至最近的类别中
4 重新计算每个类的聚类中心
5 若目标函数收敛，则聚类结束，否则转至步骤 3
- 4 -
中国科技论文在线
6 由用户对分类结果进行评判，针对分类错误的样本计算其在各个特征维度上的分类结果，根据公式(4)
对每个分类下特征权重进行调整
7 若分类结果满足用户需求，则针对验证集跳转至步骤 3；否则，跳转至步骤 2，继续使用训练集调整权重
8 最终使用测试集测试模型准确率
下面给出步骤 3 的理论解释。公式（4）中采用的是特征值的命中率。在特征维度 p 上，
假设已分类 p 篇文章，其中，分类正确的占 q 篇，则该特征维度分类的命中率为 p/q。本文
中将权重与命中率视为正相关，命中率越高，则其权重趋近于 1，反之，权重趋近于 0。针
对某分类不准确的特征维度上，趋近于 0 的权重会使该特征在计算距离时不产生影响。因其
命中率与权重的正相关性，当特征 p 在某分类下权重小于φ （一般取 1/k）时，显然已不具5
备分类参考价值，此时在该分类计算时滤掉该特征。
半监督 K-means 算法相较于 K-means 算法，通过精准的初始聚类中心选择，减少了
K-means 算法的迭代次数，从而减少 K-means 算法的递归收敛时间。而本文所述算法虽然基
于半监督 K-means 算法，但为了适应用户的个性化分类，增加了多次迭代，从而时间复杂
度较长。K-means 算法的时间复杂度为 O(lnkm)，其中 m 为特征方向数，n 为样本数，k 为10
聚类数，l 为迭代次数。Asghari Paeenroodposhti F 等[12]提出了一个基于过滤的策略，基于 kd
树索引结构来有效实施 K-means 聚类算法，综合提升了聚类中心选取准确度，与本文算法
相比，循环中的迭代时间更短，但聚类效果不如本算法，也不能有效的学习用户的指定分类。
本文算法在循环迭代时的反馈修正，能更加贴合用户给出的分类标准。在国内研究中，李洪
成等[13]结合 Map-Reduce 框架缩减了算法的时间复杂度，并且保证了算法的准确率，其基本15
理论与 K-means 算法无二。本文算法相较之下，算法的运行时间较其更长，但通过对特征
值的优化和迭代中的多中心调整使得在用户特定分类的情况下，适应性更好。具体对比见表
2：
表 2 聚类算法对比
"Clustering algorithm comparison" 20
算法 时间复杂
度
空间复杂度 适用场景
K-means O(lnkm) O((m+k)n) 精度要求不高，算法实现简单
半聚类 K-means O(lnkm) O((m+k)n) 一定的精度要求，迭代次数较少，有相关专家或用
户支持
Efficient K-means Based
on kd tree
O(lnkm) O((m+k)n) 对精度和时间要求较高，数据集为均匀的球形聚类
簇
Map-Reduce 框架下
K-means
O(lnkm/s) O((m+k)n+o) 要求运行时间短，在分布式环境下运行，规则聚类
簇
基于半监督 K-means 的
主动学习聚类算法
O(lnkmo) O((m+k)n) 精度要求高，特征维度极多，针对用户的指定分类，
对数据集的聚类簇形状无要求，但需要有小部分有
标签数据作为初始数据
- 5 -
中国科技论文在线
3 实验结果与分析
实验部分主要针对文本聚类，对语料库中的文本进行分词、去停用词、计算 TF/IDF 值、
向量化、标准化等预处理操作，得到文本集的文本向量矩阵，并从文本集中提取词典(文本
集中出现过的所有词的有序集合)。在这些预处理操作的基础上，将文本分类转化为以词汇
为特征维度的分类问题。 5
实验所采用的数据分为两部分，一部分是标准数据集 UCI 数据库中文本数据集 20
Newsgroups，另一部分为现实数据集，将指定 7 个癌症网站包含的特定的新闻通过有关专家
分为 7 个指定的分类。具体网站为医学论坛网、生物谷、丁香园、生物探索等，对应其 15
年 3~4月发布的新闻。实验环境为 Inter(R) Core(TM)2 Duo CPU T6600 @ GHz，内存 4 GB，
操作系统 Windows 7，编程语言 Python，实验软件为 PyCharm 。下表为数据集的具体10
细节。
表 3 实验数据集相关参数
"Experimental data set related parameters"
数据集 总数据量 大分类数目 小分类数目
20 Newsgroups 20000 7 20
真实数据集 1880 7 无
作为对比，通过 F-Measure 指标来评价聚类效果，计算公式(6)如下：
2
2
( 1)
, , i ii i i
i i
R Pacc accR P F
sum rel R P
(5) 15
其中，Ri表示第 i 个分类的召回率，Pi表示第 i 个分类的准确率，acc 表示准确分类的元
素数，sum 表示元素总数，rel 表示该分类下应有的元素数。此处我们取 F1-Measure 指标。
在 20 Newsgroups 数据集进行了 K-means 算法和本文算法的比较，共 10 次聚类，对其
评价指标求平均值。具体结果见表 4。
表 4 "对 20 Newsgroups 数据集的 10 次聚类试验结果平均值比较" 20
"Comparisons of the average of the 10 cluster test results for the 20 Newsgroups datasets"
算法 F1-measure 准确率 召回率
K-means 算法 947 83 249 42 428 07
本文算法 665 86 531 7 348 61
从表 4 中可以得出，本文算法所得 F1-measure 值、准确率和召回率较 K-means 算法有
显著提升。这 2 种算法对 20 Newsgroups 数据集取 10 次实验结果的平均值时，本文算法的
在准确率和召回率上比 K-means 算法提升了 %、%，F1-measure 值比 K-means 算
法提升了 ％。 25
针对实际数据集上，根据相关专家给出分类效果如下表所示：
表 5 对真实数据集上各个分类的 F-measure 指标
"The F-measure indicator for each cluster on the real data set"
分类 半监督 K-means 算法 本文算法
类 A
- 6 -
中国科技论文在线
类 B
类 C
类 D
类 E
类 F
类 G
平均 F-measure
0
类别
F
-
m
e
a
s
u
r
e 半监督K-
means算法
本文算法
图 1 真实数据集上 F-measure 指标
"The F-measure indicator on the real data set"
由 F1-measure 指数对可以综合评判算法的聚类效果，故而可以得出结论：本文算法相
对于半聚类 K-means 算法提升明显，半监督 K-means 算法针对个性化的分类时，聚类效果5
较差，在本文所用数据集中其 F-measure 指标不足 40%。经过本文算法对词汇进行进一步过
滤后，算法的精准度得到了极大地提升，提升比例达到 %。
4 结论
K-means 聚类是近年来数据挖掘学科中的一个改进的热点和重点[14-15]。然而，目前的半
监督 K-means 算法针对用户的特定分类研究较少，迭代效率不高的缺陷较为明显。本文给10
出了在 K-means 迭代循环过程中，动态调整适应分类下特征权重的算法，在半监督的部分
有标签数据的基础上，初始确定各个类的特征中心，引导算法在距离计算时，偏向于用户指
定的分类。理论分析和实验结果表明，本文算法在用户特定聚类时能显著地改善聚类质量，
并能够对特征值进行提取和过滤。目前的算法继续的改进方向有两个：一是现在的聚类算法
大多建立在均匀数据集基础之上，需要对不均匀或不规则的数据集聚类作进一步研究；二是15
针对过滤关键词的阀值进行进一步实验，给出其最有阀值。
[参考文献] (References)
[1] Han J, Kamber M.数据挖掘:概念与技术[M].范明,孟小峰等译.北京:机械工业出版社,2001.
- 7 -
中国科技论文在线
[2] Bouchachia A. Learning with paray labeled data[J]. Neural Computing and
Applications,2007,16(3):267-293.
[3] Zhu XJ. Semi-Supervised learning literature survey[J]. Technical Report, Computer Sciences
TR 1530, University of Wisconsin -42.
[4] 高滢 , 刘大有 , 齐红等 . 一种半监督 K 均值多关系数据聚类算法 [J]. 软件学5
报,2008,19(11):2814-2821.
[5] 王永雄 ,苏剑波 .基于禁忌搜索的管道状况集成检测方法 [J].模式识别与人工智
能,2013,26(1)::
[6] 田淞,宋建社,张雄美等.KM-SVM 法的 SAR 图像无监督变化检测[J].系统工程与电子技
术,2015,37(5):: 10
[7] MacQueen Methods for Classification and Analysis of Multivariate Observations//Proc
of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley. USA.
1967:28l-297.
[8] 孙雪,李昆仑,胡夕坤等.基于半监督 K-means 的 K 值全局寻优算法[J].北京交通大学学
报,2009,33(6):: 15
[9] 袁利永 , 王基一 . 一种改进的半监督 K-Means 聚类算法 [J]. 计算机工程与科
学,2011,33(6)::
[10] 陈新泉 ,苏锦钿 .基于半监督学习的 k 平均聚类框架[J].广西大学学报（自然科学
版）,2014,(5)::
[11] Idrissi H K, Kartit Z, Kartit A, et al. CKMSA: an Anomaly Detection Process Based on 20
K-Means and Simulated Annealing Algorithms[J]. International Review on Computers and
Software (IRECOS), 2016, 11(1): 42-48.
[12] Asghari Paeenroodposhti F, Nourian S, Yousefnezhad M. Wised Semi-Supervised Cluster
Ensemble Selection: A New Framework for Selecting and Combing Multiple Partitions Based On
Prior knowledge[J]. Journal of Advances in Computer Research, 2016. 25
[13] 李洪成,吴晓平,陈燕等.MapReduce 框架下支持差分隐私保护的 K-means 聚类方法[J].通
信学报,2016,37(2)::
[14] 刘文杰,伍之昂,曹杰等.基于成对约束 Info-Kmeans 聚类的图像索引方法[J].通信学
报,2013,(7):159-166,:
[15] 徐森 ,卢志茂 ,顾国昌等 .使用谱聚类算法解决文本聚类集成问题 [J].通信学30
报,2010,31(6)::
