计 算 机 工 程 第 34 卷 第11期
Vol.34 No.11 Computer Engineering ·博士论文·
文章编号：1000—3428(2008)11—0015—03
文献标识码：A
2008年6月
June2008
中图分类号：TP311
基于局部搜索机制的K-Means聚类算法
孙越恒，李志圣，何丕廉
(天津大学计算机学院，天津 300072)
摘 要：K-Means聚类算法的结果质量依赖于初始聚类中心的选择。该文将局部搜索的思想引入K-Means算法，提出一种改进的KMLS算法。该算法对K-Means收敛后的结果使用局部搜索来使其跳出局部极值点，进而再次迭代求优。同时对局部搜索的结果使用K-Means算法使其尽快到达一个局部极值点。理论分析证明了算法的可行性和有效性，而在标准文本集上的文本聚类实验表明，相对于传统的K-Means算法，该算法改进了聚类结果的质量。
关键词：K-Means聚类算法；局部搜索机制；KMLS算法；文本聚类
K-Means Clustering Algorithm Based on Local Search Mechanism
SUN Yue-heng, LI Zhi-sheng, HE Pi-lian
(School of Computer Science and Technology, Tianjin University, Tianjin 300072)
【Abstract】The quality of K-Means clustering algorithm depends on the choice of cluster center. This paper introduces the idea of local searchmechanism into K-Means and presents a KMLS algorithm. This algorithm uses the local search mechanism to jump out one local critical pointobtained by K-Means, and uses K-Means to quickly find another local critical point. Experiments of text clustering in standard document sets showthat this algorithm achieves a better clustering result than the traditional K-Means algorithm does. 【Key words】K-Means clustering algorithm; local search mechanism; KMLS algorithm; text clustering
1 概述
K-Means[1]是一种基于划分的聚类方法，可看作一个组合优化问题，即如何生成使某一目标函数达到最优的划分P的问题。虽然K-Means算法以较快的聚类速度、较好的可伸缩性而被广泛采用，但是它的聚类结果依赖于由初始聚类中心出发所遇到的第1个局部极值点，因而不同的初始聚类中心对于聚类质量有着较大影响。为此对于K-Means算法的研究主要集中在对初始聚类中心的选择优化上，如文献[2]提出的Buckshot和Fractionation方法，文献[3]提出的RA算法以及文献[4]提出的聚类中心初始化算法。这些算法在一定程度上提高了聚类结果的质量，但是它们仍依赖于K-Means算法的简单启发机制。
本文将局部搜索的思想引入K-Means算法，提出了一个基于局部搜索的KMLS(K-Means based on Local Search)算法。它将局部搜索机制同K-Means算法相结合，使用局部搜索的迭代策略来不断改进K-Means算法的聚类结果，同时使用K-Means来加速局部搜索的收敛。可以证明KMLS算法能得到一个比K-Means更优的聚类结果。
降方向的梯度策略；3)确定对局部极值点的处理策略。如果一个点的邻域中的所有点都不比这个点更好，那么这个点就是一个局部最优解。
局部搜索虽然简单，但却十分有效，究其原因在于它的重复搜索操作——虽然从某个初始点出发成功的可能性很小，但多次重复之后，却能以很大概率求得问题的解。 2.2 基于局部搜索的文本聚类算法
文本聚类实际上是为了寻找一个使目标函数最优的划分，可以使用局部搜索来进行文本聚类。
为说明方便，作以下定义：
(1)S={d1,d2,",dN}：包含N个文本的文本集。
(2)P=(S1,S2,",SK)：文本集S的一个K划分(即一个聚类结果)，其中，S=∪i=1,2,",KSi，Si∩Sj=∅，当i≠j时。
(3)ni=Si：文本集Si中的文本数，i=1,2,",K。 (4)D=∑d∈Sd：文本集S中所有文本向量之和。 (5)c=D/D：文本集S的中心向量。
2.2.1 问题的定义
文本聚类问题可转化为：在给定文本集S的K划分集P={P=(S1,S2,",SK)|S=∪i=1,",KSi∧Si∩Sj=∅,i≠j}中，搜索使目标函数最优的一个K划分。文本聚类中一般采用如下函数作为聚类过程的目标函数：
基金项目：国家自然科学基金资助项目“基于信息几何方法的维数约减和信息抽象模型研究”(60603027)
作者简介：孙越恒(1974－)，男，讲师、博士，主研方向：自然语言处理，网络信息检索与挖掘；李志圣，博士研究生；何丕廉，教授、博士生导师
收稿日期：2007-06-20 E-mail：[email protected]
2 局部搜索机制及其在文本聚类中的应用
2.1 局部搜索机制
局部搜索[5]是解决优化问题的常用技术。它基于贪婪思想，利用邻域函数进行搜索，包括以下步骤：(1)把原问题转化成一个优化问题，即在一个可行域上寻求一个目标函数的最优值。(2)要在可行域中定义邻域结构，即事先指明可行域中每个点的邻域包含哪些点。在定义了邻域关系之后，进行迭代操作，具体可分为3步：1)在可行域中选择一个初始点，常用的策略是随机选取；2)确定如何在一点的局部邻域中寻找更优的点，可采用“见好就走”的贪心策略或沿着最大下
—15—
E(P)=∑∑d∈Sd⋅ci (1)
i=1
i
K
2.2.2 邻域的定义
对任意“点”P=(S1,S2,"Sk)∈P，任意文本d∈S，P的一个邻域点可以定义如下：将一个文本从Si移动到Sj时得到的新划分P'，即如果d∈Si，那么P关于文本d的邻域为
1'
Nd(P)={P}∪{P'=(S1',S2,",SK)|Si'=Si−{d},
20Newsgroups和WAP数据集。在进行聚类实验之前，对所
有的数据集都进行了预处理。经过预处理后，各个数据集的统计信息如表1所示。
表1 文本数据集的属性统计表
数据集 Reutes-21578
类数81 20 20
文本数10 37718 8281 560
单词数 18 921 97 820 8 460
平均每个文本单词数
44.8 82.6 138.9
平均每个单词的文本频数
24.6 15.9 26.6
S'j=Sj∪{d}, Sk'=Sk当k≠i,j}
(2)
20Newsgroups
WAP
2.2.3 搜索策略
本文使用最速下降作为局部搜索策略。它对一个解P邻域内的所有解分别做出评估，然后选择那个使目标函数有最大增加的解作为新解。
设P的邻域为Neighbour(P)，最速下降搜索策略就是要在Neighbour(P)搜索一个满足P'=argmax(E(P')−E(P))
P,P′∈Neighbor(P)
本文使用熵作为聚类质量的评价指标。设C={C1,C2,",Cm}表示聚成类的集合；K={K1,K2,",Kn}是文本集中真实类的集合，它是由专家手工建立的，作为评价聚类结果的标准答案。C的熵定义为
Entropy(C)=−∑
Cj
njN
的P’。即对于任意P∈Neighbour(P)都存在：
E(P')≥E(P) (3) 基于上述定义，在此提出了一种基于局部搜索的文本聚类算法(Local Search Algorithm, LSA)，描述如下：
(1)对一个聚类划分P=(S1,S2,",SK)；
(2)设置max∆=0,movedDoc=null,target=null(其中，
movedDoc指要移动的文本，target指要移动到的类)；
pijln(pij) (4)
i
其中，nj是聚成类Cj中的文本数；pij是类别Cj中实际属于真实类Ki的概率；N表示文本集中的文本总数。熵值越小，表示聚类质量越好。
4.2 实验结果与分析
对上述数据集进行预处理后，进行特征选择并生成文本的特征向量，接着以随机方式生成10个不同的初始点，然后针对这些初始点分别运行KMLS和K-Means算法10次，并比较这10组结果及其平均值。图1~图3分别是在3个数据集上运行2种算法后的熵值比较。
1.21.1熵
值
对S中的每个文本d∈Si； 对所有的j，j=1,2,",K∧j≠i， 计算∆jE(P)=E(P')−E(P)；
b=max{∆jE(P)>0|j≠i}；
max∆=max(max∆,b),movedDoc=d,target=Sj；
(3)如果movedDoc≠null(已经找到一个最好解)，则将文本d从Si移到target，并重新计算Di及Dtarget；
(4)如果得到P'=argmax(E(P')−E(P))，则退出；否
P,P′∈Neighbor(P)
1.00.90.8
1
2
3
4
5
6次数
7
8
9
10avg.
则，返回(2)和(3)。
3 基于局部搜索的K-Means算法
LSA算法可确切地计算出目标函数的变化，但是在每次迭代过程中，目标函数只会增加一个极小的值；而K-Means算法则以高效的迭代而著称。本文结合这2种算法的优点，提出了一个基于局部搜索的KMLS算法。首先，执行一次K-Means操作，当K-Means收敛后，执行LSA算法来跳出K-Means所得到的局部极值点，并再次迭代。
KMLS算法描述如下：
(1)生成一个初始聚类划分P=(S1,S2,",SK)； (2)K-Means(P)； (3)执行LSA；
(4)如果类P没有变化，退出；否则，执行(2)。 该算法结合了LSA和K-Means的优点。一方面，在每一次局部搜索迭代得到一个解后，K-Means的迭代优化可以很快得到由这个解出发遇到的第1个局部极值点；另一方面，当K-Means收敛得到一个局部极值点后，局部搜索的搜索策略又会使K-Means从这个局部极值中跳出，以期得到一个更优的解。
1.51.41.3熵
值
图1 KMLS和K-Means在Reuters上的熵值比较
1.21.11.00.90.8
1
2
3
4
5
6次数
7
8
9
10avg.
图2 KMLS和K-Means在20Newsgroups上的熵值比较
1.31.21.1熵
值
1.00.90.8
1
2
3
4
5
6次数
7
8
9
10avg.
4 实验设计与结果分析
4.1 实验设计
本文使用了3个标准的文本数据集：Reuters-21578, 16——
图3 KMLS和K-Means在WAP上的熵值比较
可以看出，KMLS几乎总是取得比K-Means算法更好的结果。注意到在Reuters的第8次实验和在20Newsgroups上的第6次实验中，KMLS所得结果的熵值比K-Means要高，为此比较了它们各自的目标函数值，发现KMLS所得到结果的目标函数值比K-Means要高。之所以会出现这种目标函数值同熵值相矛盾的情况，是因为熵值这个评价标准是以人工分类结果为依据，而向量空间模型在表示文本时，并不能完全地将文本的真实主题表示在余弦相似度的度量之中，因而在某次实验中出现这样的情况是可以接受的。
那么，局部搜索和K-Means算法结合的合理性是什么？假定P=(S1,S2,",SK),P'=(S,S,",S)∈Neighbour(P)，笔
'1
12
'K
2个类的中心概念向量，那么∆P'E(P)−∆k也会有一个较大的改变。当文本集足够大时，由于每个类内文本数较多，因此去除或是加入一个文本对于它的中心概念向量的改变并不显著；然而对于小数据集来说这个改变就非常明显了。
2.62.21.81.41.0
50
100类
200
熵值
者的目标是确定是否可以将一个文本d0∈Si移动到Sj。
对于K-Means算法要检验下面的不等式：
∆k=d0⋅(cj−ci)>0 (5) 如果∆k>0，那么K-Means把d0从类Si移动到Sj，否则依然把d0留在类Si中。
不同于K-Means算法，本文所介绍的LSA算法计算： ∆P′E(P)=E(P')−E(P) (6) 对式(6)进一步推导，由Si′=Si−{d0}和Sj′=Sj∪{d0}可以得到：
∆P′E(P)=∑∑d∈Sd⋅ci'−∑∑d∈Sd⋅ci=
i=1
i
图4 在20Newsgroups小数据集上的熵值比较
与之不同的是，K-Means算法在面对小数据集时，考虑一个文本d∈Si，对于任意一个类Sj≠Si，由于文本集的文本数很小，而且文本间余弦相似度的均值很小，这就造成了d⋅cj对于任意的初始类而言都只有很小的数量级。但是对于
d及它所属的类Si而言，由d⋅d=1，有
d⋅ci=
1d⋅x+∑ Dix∈S−{d}Di
i
上式的第1项可以解释为文本d对类Si的中心向量的贡献。对于一个小而且高维稀疏的文本数据而言，上面的第一项远大于d⋅cj，因而，K-Means几乎不会在初始类之间移动
KK
i=1
i
'
∑d∈Sd⋅c−∑d∈Sd⋅ci)+(∑d∈Sd⋅cj−∑d∈Sd⋅cj)=
i
i
j
j'i'i
∑∑
d∈Sij
d⋅c−∑d∈Sd⋅ci−d0⋅ci)+(∑d∈Sd⋅c−
i
j'j
文本。
∑d∈Sd⋅cj+d0⋅cj)=
d∈Si5 结束语
本文分析了K-Means算法在处理文本数据上的不足，将局部搜索的思想引入文本聚类，提出了一种新的KMLS文本聚类算法。
实验结果表明，相对于较大的数据集，KMLS算法可以更显著地改进小数据集的聚类质量。笔者认为，除了文本表示模型的问题外，另一个原因可能是定义的领域对于目标函数的扰动并不敏感。如何使该算法更好地应用于真实情况下的大规模数据集，有待于进一步研究。
参考文献
[1] Garcia-Escudero L A, Gordaliza A. Robustness Properties of
K-Means and Trimmed K-Means[J]. Journal of the American Statistical Association, 1999, 94(8): 956-969.
[2] Cutting D, Karger D, Pedersen J, et al. Scatter-gather: A Cluster-
Based Approach to Browsing Large Document Collections[C]//Proc. of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Copenhagen, Denmark: [s. n.], 1992: 318-329.
[3] Larsen B, Aone C. Fast and Effective Text Mining Using Linear-time
Document Clustering[C]//Proc. of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, CA, USA: [s. n.], 1999: 16-22.
[4] Khan S S, Ahmad A. Cluster Center Initialization Algorithm for
K-Means Clustering[J]. Pattern Recognition Letters, 2004, 25(12): 1293-1302.
[5] Gill P E, Murray W, Wright M H. Practical Optimization[M]. [S. l.]:
Academic Press, 1997.
d⋅(ci'−ci)+∑d∈Sd⋅(c'j−cj)+d0⋅(cj−ci)
j
因而：
∆P'E(P)=∑d∈Sd⋅(ci'−ci)+∑d∈Sd⋅(c'j−cj)+∆k (7)
i
j
由Cauchy-Schwarz不等式，有∑d∈Sd⋅ci'≥∑d∈Sd⋅ci，因
i
i
而有：
'
∑d∈Sd⋅(ci−ci)≥0 (8)
i
同样：
'
∑d∈Sd⋅(cj−cj)≥0 (9)
j
由上面2个不等式及式(7)可推出：
∆P'E(P)≥∆k (10) 式(8)说明，即使当∆k
≤0
时K-Means算法不会改变d0在
聚类结果内的从属，KMLS的目标函数∆P'E(P)仍然可能是正的。因此，虽然E(P')>E(P)，K-Means算法会错过划分P'。而2种算法的结合，则可以避免这种情况的出现，由此改善了聚类结果的质量。
另外，笔者也发现虽然KMLS对聚类结果的改善是显著的，但是在大数据集上其改进幅度比在小数据集上要小，如在Reuters数据集上，熵值最大的改进是第1次运行结果，KMLS比K-Means有4.46%的改进，而在WAP数据集中，最小的改进是第7次运行结果，为11.81%。为进一步验证该结论，手工从20Newsgroups数据集中生成了一个每个类包含50, 100, 200的小数据集来重复上述实验，结果如图4所示。它们的熵值改进分别为：33.93%, 27.12%和22.88%。
为从理论上说明这个问题，回到式(7)。可以认为，如果把一个文本从一个类移到另一个类时，可以显著地改变这
—17—
计 算 机 工 程 第 34 卷 第11期
Vol.34 No.11 Computer Engineering ·博士论文·
文章编号：1000—3428(2008)11—0015—03
文献标识码：A
2008年6月
June2008
中图分类号：TP311
基于局部搜索机制的K-Means聚类算法
孙越恒，李志圣，何丕廉
(天津大学计算机学院，天津 300072)
摘 要：K-Means聚类算法的结果质量依赖于初始聚类中心的选择。该文将局部搜索的思想引入K-Means算法，提出一种改进的KMLS算法。该算法对K-Means收敛后的结果使用局部搜索来使其跳出局部极值点，进而再次迭代求优。同时对局部搜索的结果使用K-Means算法使其尽快到达一个局部极值点。理论分析证明了算法的可行性和有效性，而在标准文本集上的文本聚类实验表明，相对于传统的K-Means算法，该算法改进了聚类结果的质量。
关键词：K-Means聚类算法；局部搜索机制；KMLS算法；文本聚类
K-Means Clustering Algorithm Based on Local Search Mechanism
SUN Yue-heng, LI Zhi-sheng, HE Pi-lian
(School of Computer Science and Technology, Tianjin University, Tianjin 300072)
【Abstract】The quality of K-Means clustering algorithm depends on the choice of cluster center. This paper introduces the idea of local searchmechanism into K-Means and presents a KMLS algorithm. This algorithm uses the local search mechanism to jump out one local critical pointobtained by K-Means, and uses K-Means to quickly find another local critical point. Experiments of text clustering in standard document sets showthat this algorithm achieves a better clustering result than the traditional K-Means algorithm does. 【Key words】K-Means clustering algorithm; local search mechanism; KMLS algorithm; text clustering
1 概述
K-Means[1]是一种基于划分的聚类方法，可看作一个组合优化问题，即如何生成使某一目标函数达到最优的划分P的问题。虽然K-Means算法以较快的聚类速度、较好的可伸缩性而被广泛采用，但是它的聚类结果依赖于由初始聚类中心出发所遇到的第1个局部极值点，因而不同的初始聚类中心对于聚类质量有着较大影响。为此对于K-Means算法的研究主要集中在对初始聚类中心的选择优化上，如文献[2]提出的Buckshot和Fractionation方法，文献[3]提出的RA算法以及文献[4]提出的聚类中心初始化算法。这些算法在一定程度上提高了聚类结果的质量，但是它们仍依赖于K-Means算法的简单启发机制。
本文将局部搜索的思想引入K-Means算法，提出了一个基于局部搜索的KMLS(K-Means based on Local Search)算法。它将局部搜索机制同K-Means算法相结合，使用局部搜索的迭代策略来不断改进K-Means算法的聚类结果，同时使用K-Means来加速局部搜索的收敛。可以证明KMLS算法能得到一个比K-Means更优的聚类结果。
降方向的梯度策略；3)确定对局部极值点的处理策略。如果一个点的邻域中的所有点都不比这个点更好，那么这个点就是一个局部最优解。
局部搜索虽然简单，但却十分有效，究其原因在于它的重复搜索操作——虽然从某个初始点出发成功的可能性很小，但多次重复之后，却能以很大概率求得问题的解。 2.2 基于局部搜索的文本聚类算法
文本聚类实际上是为了寻找一个使目标函数最优的划分，可以使用局部搜索来进行文本聚类。
为说明方便，作以下定义：
(1)S={d1,d2,",dN}：包含N个文本的文本集。
(2)P=(S1,S2,",SK)：文本集S的一个K划分(即一个聚类结果)，其中，S=∪i=1,2,",KSi，Si∩Sj=∅，当i≠j时。
(3)ni=Si：文本集Si中的文本数，i=1,2,",K。 (4)D=∑d∈Sd：文本集S中所有文本向量之和。 (5)c=D/D：文本集S的中心向量。
2.2.1 问题的定义
文本聚类问题可转化为：在给定文本集S的K划分集P={P=(S1,S2,",SK)|S=∪i=1,",KSi∧Si∩Sj=∅,i≠j}中，搜索使目标函数最优的一个K划分。文本聚类中一般采用如下函数作为聚类过程的目标函数：
基金项目：国家自然科学基金资助项目“基于信息几何方法的维数约减和信息抽象模型研究”(60603027)
作者简介：孙越恒(1974－)，男，讲师、博士，主研方向：自然语言处理，网络信息检索与挖掘；李志圣，博士研究生；何丕廉，教授、博士生导师
收稿日期：2007-06-20 E-mail：[email protected]
2 局部搜索机制及其在文本聚类中的应用
2.1 局部搜索机制
局部搜索[5]是解决优化问题的常用技术。它基于贪婪思想，利用邻域函数进行搜索，包括以下步骤：(1)把原问题转化成一个优化问题，即在一个可行域上寻求一个目标函数的最优值。(2)要在可行域中定义邻域结构，即事先指明可行域中每个点的邻域包含哪些点。在定义了邻域关系之后，进行迭代操作，具体可分为3步：1)在可行域中选择一个初始点，常用的策略是随机选取；2)确定如何在一点的局部邻域中寻找更优的点，可采用“见好就走”的贪心策略或沿着最大下
—15—
E(P)=∑∑d∈Sd⋅ci (1)
i=1
i
K
2.2.2 邻域的定义
对任意“点”P=(S1,S2,"Sk)∈P，任意文本d∈S，P的一个邻域点可以定义如下：将一个文本从Si移动到Sj时得到的新划分P'，即如果d∈Si，那么P关于文本d的邻域为
1'
Nd(P)={P}∪{P'=(S1',S2,",SK)|Si'=Si−{d},
20Newsgroups和WAP数据集。在进行聚类实验之前，对所
有的数据集都进行了预处理。经过预处理后，各个数据集的统计信息如表1所示。
表1 文本数据集的属性统计表
数据集 Reutes-21578
类数81 20 20
文本数10 37718 8281 560
单词数 18 921 97 820 8 460
平均每个文本单词数
44.8 82.6 138.9
平均每个单词的文本频数
24.6 15.9 26.6
S'j=Sj∪{d}, Sk'=Sk当k≠i,j}
(2)
20Newsgroups
WAP
2.2.3 搜索策略
本文使用最速下降作为局部搜索策略。它对一个解P邻域内的所有解分别做出评估，然后选择那个使目标函数有最大增加的解作为新解。
设P的邻域为Neighbour(P)，最速下降搜索策略就是要在Neighbour(P)搜索一个满足P'=argmax(E(P')−E(P))
P,P′∈Neighbor(P)
本文使用熵作为聚类质量的评价指标。设C={C1,C2,",Cm}表示聚成类的集合；K={K1,K2,",Kn}是文本集中真实类的集合，它是由专家手工建立的，作为评价聚类结果的标准答案。C的熵定义为
Entropy(C)=−∑
Cj
njN
的P’。即对于任意P∈Neighbour(P)都存在：
E(P')≥E(P) (3) 基于上述定义，在此提出了一种基于局部搜索的文本聚类算法(Local Search Algorithm, LSA)，描述如下：
(1)对一个聚类划分P=(S1,S2,",SK)；
(2)设置max∆=0,movedDoc=null,target=null(其中，
movedDoc指要移动的文本，target指要移动到的类)；
pijln(pij) (4)
i
其中，nj是聚成类Cj中的文本数；pij是类别Cj中实际属于真实类Ki的概率；N表示文本集中的文本总数。熵值越小，表示聚类质量越好。
4.2 实验结果与分析
对上述数据集进行预处理后，进行特征选择并生成文本的特征向量，接着以随机方式生成10个不同的初始点，然后针对这些初始点分别运行KMLS和K-Means算法10次，并比较这10组结果及其平均值。图1~图3分别是在3个数据集上运行2种算法后的熵值比较。
1.21.1熵
值
对S中的每个文本d∈Si； 对所有的j，j=1,2,",K∧j≠i， 计算∆jE(P)=E(P')−E(P)；
b=max{∆jE(P)>0|j≠i}；
max∆=max(max∆,b),movedDoc=d,target=Sj；
(3)如果movedDoc≠null(已经找到一个最好解)，则将文本d从Si移到target，并重新计算Di及Dtarget；
(4)如果得到P'=argmax(E(P')−E(P))，则退出；否
P,P′∈Neighbor(P)
1.00.90.8
1
2
3
4
5
6次数
7
8
9
10avg.
则，返回(2)和(3)。
3 基于局部搜索的K-Means算法
LSA算法可确切地计算出目标函数的变化，但是在每次迭代过程中，目标函数只会增加一个极小的值；而K-Means算法则以高效的迭代而著称。本文结合这2种算法的优点，提出了一个基于局部搜索的KMLS算法。首先，执行一次K-Means操作，当K-Means收敛后，执行LSA算法来跳出K-Means所得到的局部极值点，并再次迭代。
KMLS算法描述如下：
(1)生成一个初始聚类划分P=(S1,S2,",SK)； (2)K-Means(P)； (3)执行LSA；
(4)如果类P没有变化，退出；否则，执行(2)。 该算法结合了LSA和K-Means的优点。一方面，在每一次局部搜索迭代得到一个解后，K-Means的迭代优化可以很快得到由这个解出发遇到的第1个局部极值点；另一方面，当K-Means收敛得到一个局部极值点后，局部搜索的搜索策略又会使K-Means从这个局部极值中跳出，以期得到一个更优的解。
1.51.41.3熵
值
图1 KMLS和K-Means在Reuters上的熵值比较
1.21.11.00.90.8
1
2
3
4
5
6次数
7
8
9
10avg.
图2 KMLS和K-Means在20Newsgroups上的熵值比较
1.31.21.1熵
值
1.00.90.8
1
2
3
4
5
6次数
7
8
9
10avg.
4 实验设计与结果分析
4.1 实验设计
本文使用了3个标准的文本数据集：Reuters-21578, 16——
图3 KMLS和K-Means在WAP上的熵值比较
可以看出，KMLS几乎总是取得比K-Means算法更好的结果。注意到在Reuters的第8次实验和在20Newsgroups上的第6次实验中，KMLS所得结果的熵值比K-Means要高，为此比较了它们各自的目标函数值，发现KMLS所得到结果的目标函数值比K-Means要高。之所以会出现这种目标函数值同熵值相矛盾的情况，是因为熵值这个评价标准是以人工分类结果为依据，而向量空间模型在表示文本时，并不能完全地将文本的真实主题表示在余弦相似度的度量之中，因而在某次实验中出现这样的情况是可以接受的。
那么，局部搜索和K-Means算法结合的合理性是什么？假定P=(S1,S2,",SK),P'=(S,S,",S)∈Neighbour(P)，笔
'1
12
'K
2个类的中心概念向量，那么∆P'E(P)−∆k也会有一个较大的改变。当文本集足够大时，由于每个类内文本数较多，因此去除或是加入一个文本对于它的中心概念向量的改变并不显著；然而对于小数据集来说这个改变就非常明显了。
2.62.21.81.41.0
50
100类
200
熵值
者的目标是确定是否可以将一个文本d0∈Si移动到Sj。
对于K-Means算法要检验下面的不等式：
∆k=d0⋅(cj−ci)>0 (5) 如果∆k>0，那么K-Means把d0从类Si移动到Sj，否则依然把d0留在类Si中。
不同于K-Means算法，本文所介绍的LSA算法计算： ∆P′E(P)=E(P')−E(P) (6) 对式(6)进一步推导，由Si′=Si−{d0}和Sj′=Sj∪{d0}可以得到：
∆P′E(P)=∑∑d∈Sd⋅ci'−∑∑d∈Sd⋅ci=
i=1
i
图4 在20Newsgroups小数据集上的熵值比较
与之不同的是，K-Means算法在面对小数据集时，考虑一个文本d∈Si，对于任意一个类Sj≠Si，由于文本集的文本数很小，而且文本间余弦相似度的均值很小，这就造成了d⋅cj对于任意的初始类而言都只有很小的数量级。但是对于
d及它所属的类Si而言，由d⋅d=1，有
d⋅ci=
1d⋅x+∑ Dix∈S−{d}Di
i
上式的第1项可以解释为文本d对类Si的中心向量的贡献。对于一个小而且高维稀疏的文本数据而言，上面的第一项远大于d⋅cj，因而，K-Means几乎不会在初始类之间移动
KK
i=1
i
'
∑d∈Sd⋅c−∑d∈Sd⋅ci)+(∑d∈Sd⋅cj−∑d∈Sd⋅cj)=
i
i
j
j'i'i
∑∑
d∈Sij
d⋅c−∑d∈Sd⋅ci−d0⋅ci)+(∑d∈Sd⋅c−
i
j'j
文本。
∑d∈Sd⋅cj+d0⋅cj)=
d∈Si5 结束语
本文分析了K-Means算法在处理文本数据上的不足，将局部搜索的思想引入文本聚类，提出了一种新的KMLS文本聚类算法。
实验结果表明，相对于较大的数据集，KMLS算法可以更显著地改进小数据集的聚类质量。笔者认为，除了文本表示模型的问题外，另一个原因可能是定义的领域对于目标函数的扰动并不敏感。如何使该算法更好地应用于真实情况下的大规模数据集，有待于进一步研究。
参考文献
[1] Garcia-Escudero L A, Gordaliza A. Robustness Properties of
K-Means and Trimmed K-Means[J]. Journal of the American Statistical Association, 1999, 94(8): 956-969.
[2] Cutting D, Karger D, Pedersen J, et al. Scatter-gather: A Cluster-
Based Approach to Browsing Large Document Collections[C]//Proc. of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Copenhagen, Denmark: [s. n.], 1992: 318-329.
[3] Larsen B, Aone C. Fast and Effective Text Mining Using Linear-time
Document Clustering[C]//Proc. of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, CA, USA: [s. n.], 1999: 16-22.
[4] Khan S S, Ahmad A. Cluster Center Initialization Algorithm for
K-Means Clustering[J]. Pattern Recognition Letters, 2004, 25(12): 1293-1302.
[5] Gill P E, Murray W, Wright M H. Practical Optimization[M]. [S. l.]:
Academic Press, 1997.
d⋅(ci'−ci)+∑d∈Sd⋅(c'j−cj)+d0⋅(cj−ci)
j
因而：
∆P'E(P)=∑d∈Sd⋅(ci'−ci)+∑d∈Sd⋅(c'j−cj)+∆k (7)
i
j
由Cauchy-Schwarz不等式，有∑d∈Sd⋅ci'≥∑d∈Sd⋅ci，因
i
i
而有：
'
∑d∈Sd⋅(ci−ci)≥0 (8)
i
同样：
'
∑d∈Sd⋅(cj−cj)≥0 (9)
j
由上面2个不等式及式(7)可推出：
∆P'E(P)≥∆k (10) 式(8)说明，即使当∆k
≤0
时K-Means算法不会改变d0在
聚类结果内的从属，KMLS的目标函数∆P'E(P)仍然可能是正的。因此，虽然E(P')>E(P)，K-Means算法会错过划分P'。而2种算法的结合，则可以避免这种情况的出现，由此改善了聚类结果的质量。
另外，笔者也发现虽然KMLS对聚类结果的改善是显著的，但是在大数据集上其改进幅度比在小数据集上要小，如在Reuters数据集上，熵值最大的改进是第1次运行结果，KMLS比K-Means有4.46%的改进，而在WAP数据集中，最小的改进是第7次运行结果，为11.81%。为进一步验证该结论，手工从20Newsgroups数据集中生成了一个每个类包含50, 100, 200的小数据集来重复上述实验，结果如图4所示。它们的熵值改进分别为：33.93%, 27.12%和22.88%。
为从理论上说明这个问题，回到式(7)。可以认为，如果把一个文本从一个类移到另一个类时，可以显著地改变这
—17—