Web文档聚类中k-means算法的改进

介绍了Web文档聚类中普遍使用的、基于分割的k-means算法,分析了k-means算法所使用的向量空间模型和基于距离的相似性度量的局限性,从而提出了一种改善向量空间模型以及相似性度量的方法。

　　关键词: 文档聚类 k-means算法 向量空间模型 相似性度量

　　Internet的快速发展使得Web上电子文档资源在几年间呈爆炸式增长,与数据库中结构化的信息相比,非结构化的Web文档信息更加丰富和繁杂。如何充分有效地利用Web上丰富的文档资源,使用户能够快速有效地找到需要的信息已经成为迫切需要解决的问题。

　　聚类能够在没有训练样本的条件下自动产生聚类模型。作为数据挖掘的一种重要手段,聚类在Web文档的信息挖掘中也起着非常重要的作用。文档聚类是将文档集合分成若干个簇,要求簇内文档内容的相似性尽可能大,而簇之间文档的相似性尽可能小。文档聚类可以揭示文档集合的内在结构,发现新的信息,因此广泛应用于文本挖掘与信息检索等方面。

　　文档聚类算法一般分为分层和分割二种,普遍采用的是基于分割的k-means算法。

　　k-means算法具有可伸缩性和效率极高的优点,从而被广泛地应用于大文档集的处理。针对k-means算法的缺点,许多文献提出了改进方法,但是这些改进大多以牺牲效率为代价,且只对算法的某一方面进行优化,从而使执行代价很高。

　　k-means算法中文档表示模型采用向量空间模型(VSM),其中的词条权重评价函数用TF*IDF表示。然而实际上这种表示方法只体现了该词条是否出现以及出现多少次的信息,而没有考虑对于该词条在文档中出现的位置及不同位置对文档内容的决定程度不同这一情况。另一方面,k-means算法使用基于距离的相似性度量,然而文档的特征向量一般超过万维,有时可达到数十万维,这种高维度使得这种度量方法不再有效。针对以上问题,本文提出相应的解决方法,即改进的k-means算法。实验表明改进后的k-means算法不仅保留了原算法效率高的优点,而且聚类的平均准确度有了较大提高。

1k-means算法简介

　　k-means算法是一种基于分割的聚类算法。基于分割的聚类算法可以简单描述为:对一个对象集合构造一个划分,形成k个簇,使得评价函数最优。不同的评价函数将产生不同的聚类结果,k-means算法通常使用的评价函数为:

　　k-means算法的具体过程如下:

　　(1)选取k个对象作为初始的聚类种子;

　　(2)根据聚类种子的值,将每个对象重新赋给最相似的簇;

　　(3)重新计算每个簇中对象的平均值,用此平均值作为新的聚类种子;

　　(4)重复执行(2)、(3)步,直到各个簇不再发生变化。

　　k-means算法的复杂度为:O(nkt)。其中:n为对象个数,k为聚类数,t为迭代次数。通常k、t n,所以k-means算法具有很高的效率。同时k-means算法具有较强的可伸缩性,除了生成k个聚类外,还生成每个聚类的中心,因此被广泛应用。