第 28 卷 第 6 期
Vol. 28 No. 6
控 制 与 决 策
Control and Decision
2013 年 6 月
Jun. 2013
基于谱图和成对约束的主动半监督聚类算法
文章编号: 1001-0920 (2013) 06-0904-05
蒋伟进
1,2
, 许宇晖
1
, 王 欣
3
(1. 湖南商学院 计算机与信息工程学院，长沙 410205；2. 武汉理工大学 计算机科学与
技术学院，武汉 430070；3. 湖南工业大学 电气自动化学院，湖南 株洲 412008)
摘 要: 针对半监督聚类学习算法中缺乏主动学习的缺陷, 提出一种纠错式主动学习成对约束方法. 算法通过寻找
一般聚类算法自身难以发现的成对约束信息, 同时避免这部分约束信息之间本身的关系, 将其引入谱聚类算法, 利用
该监督信息调整谱聚类中点与点之间的距离矩阵对两点间距离进行排序, 采用双向寻找的方法, 使得学习器即使接
收到没有标记的数据也能进行主动学习. 实验分析表明, 所提出算法能够获得较为满意的聚类效果.
关键词: 半监督聚类；主动式学习；成对约束；谱聚类
中图分类号: TP273 文献标志码: A
Active semi-supervised clustering algorithm based-on pair-wise
constraints
JIANG Wei-jin
1,2
, XU Yu-hui
1
, WANG Xin
3
(1. School of Computer and Information，Hu’nan University of Commerce，Changsha 410205，China；2. School of
Computer Science and Technology，Wuhan University of Technology，Wuhan 430070，China；3. School of Electric
Automatization，Hu’nan University of Technology，Zhuzhou 412008，China. Correspondent：JIANG Wei-jin，E-mail:
nudtjwj@163.com)
Abstract: An active learning algorithm based on pair-wise constraints with error correction is proposed in this paper. The
algorithm searches the pair-wise constraints information that the clustering algorithm cann’t find, and tries its best to reduce
the connections between these constraint informations, which is used in the spectral clustering. The suppervised information
is used to adjust the distance matrix in the spectral clustering, and the distances are sorted. The learninger can study actively
when the learinger receives the data without flags by using the two-way search method. Experiment analysis shows that
better clustering result can be obtained by using the proposed method.
Key words: semi-supervised clustering；active learning；pairwise constraint；spectral clustering
0 引引引 言言言
信息技术的迅猛发展极大地帮助人们提高了数
据收集、数据存储的能力, 在科学研究和社会生活的
各个方面都积累了海量的数据, 对这些数据进行分析
和发掘其中蕴含的有价值信息, 已经是各个领域的共
同需求. 以往的机器学习算法一般只考虑有标记数
据, 或者只考虑未标记数据, 但在现实环境中一般两
者兼有, 因此, 如何更有效地利用这些数据成为一个
亟待解决的问题. 近年发展起来的半监督学习是解决
这一问题的有效方法, 它通过广泛利用无标号数据样
本的先验知识来完成对样本数据的分类或聚类. 目
前, 应用样本的先验信息解决聚类问题已成为智能信
息处理的重要途径和研究热点
[1-6]
.
半监督聚类一般通过两种先验信息引导聚类过
程, 即标号点信息和成对约束信息. 由于标号点信息
可以转化为成对约束信息, 通常用成对约束信息作为
半监督聚类先验信息来监督聚类过程
[1]
. 作如下规定:
1) must-link, 若两样本为 must-link 约束, 则它们在聚
类时必须被分配到同一类中 (即 Must-link 约束要求
两个数据点必须在同一个聚类中); 2) cannot-link, 若
两样本是 cannot-link 约束, 则它们在聚类时必须被分
配到不同类中 (即 cannot-link 约束要求两个点不能在
收稿日期: 2012-02-22；修回日期: 2012-11-05.
基金项目: 国家自然科学基金项目(61074067, 21106036)；湖南省自然科学基金项目(10JJ5064, 11JJ6051)；教育部人文
社科研究一般规划基金项目(11YJAZH039)；湖南省重点学科建设项目.
作者简介: 蒋伟进(1964−), 男, 教授, 博士, 从事机器学习、智能计算等研究；许宇晖(1969−), 女, 讲师, 从事计算机控
制与应用的研究.
资源评论
