一种基于向量空间模型的文档聚类算法研究

随着网络信息的迅速增长,文档聚类技术成为了人们研究的热点课题。探讨了典型的基于向量空间模型的文档聚类算法一k-means算法,针对它的不足提出了改进的BK-means算法。最后,根据一定的评价标准,得出BK-means算法是文档聚类算法中较好的算法。

处于知识爆炸的当今社会,纷繁复杂的信息资源仅仅依靠人来进行处理显然不能满足需要,利用计算机进行信息处理成为必然。

文本聚类是一种无指导的文本分类,它把一个文本集分成若干称为集簇的子集。

每个集簇中的文本之间具有较大的相识性,而集簇之间的文本具有较小的相识性。

中文文本聚类的一般过程是:首先把文本表示成为计算机能够处理的、体现文本本质特征的形式,然后对这些特征进行筛选,选出部分最重要的特征,最后用使某种评价函数值达到最优的聚类算法对文本进行聚类。

据统计,网络信息80%以上都是以文本的形式存在的。

为了对用户提供方便、快捷、准确的信息查询与检索,用于文本挖掘和信息检索等多个领域的聚类技术成为了人们研究的热点。聚类是一种应用很广的数据挖掘形式,它广泛应用于模式识别、图像处理、数据压缩等领域。

近年来,随着网络的发展,特别是国际互联网和基于http协议的WEB技术的飞速发展,网上文本信息的激增,搜索引擎、文本挖掘、信息过滤和信息检索等的研究出现了前所未有的高潮。

而聚类作为一种知识发现的重要方法,也日益广泛和中文信息处理技术相结合,应用于网络信息处理中以满足用户方便快捷地从互联网获得自己需要的信息资源。

文本聚类首先遇到的问题是如何将文本内容表示成在数学上可分析处理的形式。

由Salton教授提出的向量空间模型 (Vector Space Model, VSM)的基本思想是,对于文档集中的每一篇文章都将按照事先规定好的词序,表示成为高维空间中的一个向量。

规定好次序的词看成是向量空间的维,词的权重则看成是向量在高维向量空间中某一维的取值。

这样一篇文章就被表示成为高维空间中的一个向量了,便于利用各种数学工具对其进行处理。

聚类在本质上是一种通过对对象集合按照某种规则进行划分或覆盖从而发现隐含的潜在有用的信息的一种知识发现的方法。

聚类算法有许多种,通常有以下几类:

[list]
[] 以构建和评估各种分区的分割方法(Partitioning Method);
[
] 以创建层次分解的层次方法(Hierarchical Method);
[] 基于连通和密度的基于密度的方法(Density-Based Methods);
[
] 基于多层粒度的网络方法(Grid-Based Method);
[*] 以构建聚类假设模型的模型方法(Model-Based Clustering Method)。
[/list]

其中,文档聚类中最为常用的算法是分割算法中的k-means算法和层次算法中的凝聚层次算法(Agglomerative Hierarchical Clustering Algorithm)。

向量空间模型

由G . Salton等人提出的向量空间模型把文本简化为以项的权重为分量的向量表示,把文本处理过程简化为空间向量的运算,使问题的复杂性大大降低。

在向量空间模型中,过滤需求用向量表示为 Q= (T1 T2, …, T.),文本用向量表示为D= (Ti, T2,…Tm,)(Ti表示需求向量或文本向量中的第i个分量,即需求表达式或文本表示中所含的第i个关键词)。

关键词T、的权重取值一般在 [0, 1]区间,关键词及其权重构成一个向量空间,过滤中的文本和需求的匹配处理过程可转化为向量空间中文本向量与需求向量的相似度计算问题,通过向量对之间的相似度测定来判断文本与需求的相关程度。

计算相似度较常用的方法使用余弦函数,定义为:

其中:WDt为文本向量中第i个分量对应的权重, Wqi 为需求向量中第i个分量对应的权重。

这种方法的实质是计算m维空间中文本向量与需求向量之间的夹角余弦。当两个向量完全相同时,它们在该空间中相互重叠,即夹角为0,函数(相似度)达到最大值。
K- means算法的分析及其改进

分割聚类算法将数据集分成若干子集。

由于搜索全部可能子集空间在计算上是不可能的,因此往往采用一定迭代优化的启发式方法。

这就意味着反复在K类之间重定位每类的类别中心,以及重新分配每类中的对象。

与层次聚类不同的是这类算法反复调整聚类结果来进行聚类优化,典型的算法有K-means方法。

k-means 算法以k为参数,把n个对象分为k个簇,以使簇内具有较高的相似度,而簇间的相似度较低。

具体算法描述过程如下:

[list=1]
[] 在 n个对象中随机的选取k个对象作为初始的聚类种子;
[
] 根据聚类种子的值,将每个对象重新赋给最相似的簇;
[] 重新计算每个簇中对象的平均值,用此平均值作为新的聚类种子;(
[
] 重复(2), (3)步,直到每一聚类的中心不再改变。
[/list]

这种算法实质是一种多次迭代的方法,把每篇文档看成一个对象,利用文档与聚类中心之间的相似度来进行聚类, 在数据量较小时,具有较好的聚类效果,当处理大规模数据时,时间复杂度也是0 (n),但聚类效果较差,计算量大也会大增。

K-means方法有如下优点

[list]
[] 对数值属性有很好的几何和统计意义
[
] 对顺序不太敏感
[] 对凸型聚类有较好结果
[
] 可平行运行
[*] 可在任意范数下进行聚类
[/list]

K-means方法有如下缺点

[list]
[] 对初始聚类中心选取较敏感,往往得不到全局最优解,而常常得到的是次优解
[
] 关于K值的确定没有可行的依据
[] 该算法容易受到异常点的干扰
[
] 缺少可伸缩性
[*] 聚类结果有时会失衡
[/list]

全文检索理论与算法