第 27 卷 第 4 期
Vol. 27 No. 4
控 制 与 决 策
Control and Decision
2012 年 4 月
Apr. 2012
基于模糊 𝑲-调和均值的单词-文档谱聚类方法
文章编号: 1001-0920 (2012) 04-0501-06
刘 娜
1,2
, 肖智博
1
, 鲁明羽
1
(1. 大连海事大学 信息科学技术学院,辽宁 大连 116026;
2. 大连工业大学 信息科学与工程学院,辽宁 大连 116034)
摘 要: 在分析单词-文档谱聚类方法的基本步骤, 找出其对初始值敏感的根本原因的基础上, 提出一种基于模
糊 𝐾 -调和均值的单词-文档谱聚类方法. 首先从矩阵相似的角度对谱聚类中的 Laplacian 矩阵进行处理, 使其满足对
初始值不敏感的条件; 然后通过加入模糊的概念, 用模糊 𝐾-调和均值算法代替 𝐾-均值算法, 使聚类结果对初始值不
敏感. 实验结果表明, 所提出的方法不仅使聚类结果对初始值不敏感, 而且在一定程度上提高了数据的鲁棒性.
关键词: 谱聚类;𝐾-均值;𝐾 -调和均值;模糊𝐾 -调和均值
中图分类号: TP181 文献标识码: A
Spectral co-clustering documents and words based on fuzzy 𝑲-harmonic
means
LIU Na
1,2
, XIAO Zhi-bo
1
, LU Ming-yu
1
(1. College of Information Science & Technology,Dalian Maritime University,Dalian 116026,China;2. College of
Information Science & Engineering,Dalian Polytechnic University,Dalian 116034,China.Correspondent:LU Ming-
yu,E-mail:lumingyu@dlmu.edu.cn)
Abstract:::Based on analysising the main step of spectral clustering and finding out its cause of sensitive to the initialization,
a method of spectral co-clustering documents and words based on fuzzy 𝐾-harmonic means is proposed. Firstly, the matrix
which is insensitive to the initialization is constructed. Then fuzzy 𝐾-harmonic means algorithm is used instead of 𝐾 -means
algorithm. The experiment result shows that the proposed method not only is initialization insensitive, but also can improve
the accuracy and robustness of clustering results.
Key words:::spectral clustering;𝐾 -means;𝐾 -harmonic means;fuzzy 𝐾 -harmonic means
1 引引引 言言言
聚类分析是数据挖掘中一个非常活跃的研究领
域, 而单词聚类和文档聚类是聚类分析中的热点问题.
近年来, 人们已经提出了许多聚类算法, 其中谱聚类
方法具有不受簇空间形状限制、不会陷入局部最优
解
[1]
及其有效性可从多个方面进行解释等特点
[2-3]
,
越来越受到人们的关注.
谱聚类算法最初用于计算机视觉
[4]
和 VLSI 设
计
[5]
等领域, 最近已开始用于机器学习
[3]
, 并迅速成为
国际上机器学习领域的研究热点. 典型的算法有: 2 -
way 划分的 Normailized - Cut (Ncut) 算法
[4]
, 𝑘 - way 划
分的 Normailized - Cut (Ncut) 算法
[2]
, 针对大规模数据
集的谱聚类方法
[6]
, 混合二部图模型
[7]
, 自动确定聚类
数目的谱聚类方法
[8]
, 基于背景的相似性度量方法和
尺度参数问题
[9]
, Nystrom 逼近方法 (用以减少求解特
征问题时的计算复杂度)
[10]
, 利用谱聚类解决文本集
成聚类问题
[11]
以及 MDS 方法
[12]
和用图理论对话语
者进行识别的方法
[13]
等. 虽然这些谱聚类方法与其
他聚类方法相比易于理解和实现, 具有识别非凸分布
的能力等优势, 但仍存在对初始值敏感等缺陷.
针对以上谱聚类方法存在对初始值敏感、聚类
效率不高等问题, 本文提出一种基于模糊 𝐾-调和均
值的单词-文档谱聚类方法. 首先对谱聚类方法中的
Laplacian 矩阵进行处理, 使其满足对初始值不敏感的
条件, 并加以证明; 然后用模糊 𝐾-调和均值聚类方法
代替谱聚类中的 𝐾-均值聚类方法, 并采用模糊加权
收稿日期: 2010-11-08;修回日期: 2011-01-14.
基金项目: 国 家 自 然 科 学 基 金 项 目(61175053, 61073133, 60973067); 教 育 部 创 新 团 队 及 重 点 科 研 培 育 项 目
(2011ZD010).
作者简介: 刘娜(1978−), 女, 博士生, 从事数据挖掘、文本摘要等研究;鲁明羽(1963−), 男, 教授, 博士生导师, 从事机
器学习、数据挖掘等研究.