文档聚类算法改进及效果测试文档聚类研究

摘 要：本文提出一种利用文本间相似度进行主题的语义合并，对文本进行语义抽象聚类的算法。该模型充分利用现状网上一些开源工具，并对已有的聚类算法进行改进，最后给出了该算法与其他算法的测试比较效果。

关键词：文档聚类；算法改进；测试

中图分类号：TP391.1 文献标识码：A 文章编号：1674-7712 （2013） 14-0000-02

一、研究背景

在日常生产和生活中，人们面对非常复杂的事物，往往希望能够把相似的东西归为一类，有明显区别的事物分属在不同的类别中，这样处理起来就大为简便。随着人类对自然和社会的认识不断深入，要处理的数据量规模越来越大，相互关系也越来越复杂，分类越来越细，对分类的要求也越来越高，这时仅仅依靠定性分析就不能满足要求。

聚类分析是一种数学工具引入后，形成的基于数值分类学的一种多元统计方法，也是文献计量研究中经常用到的数据结构挖掘技术。

聚类是对无标签的数据进行分类，优势是无标签，就是不需要在训练前对训练集集中的数据点进行人为的事先分类，缺点是聚类得到的模型不一定反映数据的真实模型。

聚类相当于将一大群人按照他们的距离（这里的距离可能是他们的相似程度或者其他，越相似距离越短）进行分类，聚类分析可以获得数据的分类，但是这个分类不一定反映数据的真实模型。适用于目标分类。聚类是对数据样例进行划分，形成若干个簇。

随着科技文献检索能力的加强，人们能够直接从网上和众多英文数据库中获取的科技文献越来越多。如何从海量的英文资料中发现更多隐含的信息，这也是国内外众多学者研究的一个热点问题之一。例如，做文献综述时需要从检索到的科技文献中分析本课题的主要研究方向，在以前文献量较少的情况下可以人工提炼和总结，但面对大量的文献时则已超过了人的阅读和分析能力，往往耗费大量的时间和精力也不能找到学科的主要研究领域。

二、聚类模型

收集文档资料，对这些文档中的文本信息进行分词和统计词频，为下一步进行主题词提取做准备。

单个网页文本信息抽取与统计的详细步骤如下：

将经过 Crunch 过滤后的网页解析成 DOM Tree，然后根据该 DOM Tree，取得文本；

利用Charniak's parser对网页的文本进行分词；

利用Lucene的snowball组件对分词后的各个单词取词根；

统计词根的词频；

对所有的keyword进行基于语义相似度的聚类，当聚类结果中的keywords之间的语义相似度大于某个阈值的时候，对这些keywords进行语义层次的合并，词频数相加；

按词频从大到小排序，每个页面取前N个词根；

将处理以后的N个词作为输入，参与下一小节的主题词提取的运算。经过过滤后网页中的文本内容需要进行分词与词频统计，我们这里采用的是共指消解系统所采用的预处理系统：Charniak's parser（英语语法分析器）。作为一种应用系统的数据预处理工具，它的功能有：（1）划分出一个句子以及一个词的起始位置与结束位置；（2）区分出词或者短语的词性；（3）检测出名词短语，如人名；（4）检测出专有名词，如the Summer Palace这样的短语。这个工具改进了我们原本采用的简单利用Lucene组件的进行分词的技术，使得许多名词短语和专有名词的分词更加的准确。另外，经过Charniak's parser处理以后的文本的词性也已经知道，因此，我们直接忽略了介词以及副词等无关主题的词过滤掉，对实验结果的效率也改进不少。

在使用Charniak's parser分完词之后，如果直接进行词频统计，同一名个词可能会因为单复数形式的不同，或者是同一个动词因为时态的不同，被统计成为两个不同的词。因此，需要再对得到词或者词组进行取词根的操作。这里本文使用的是Snowball算法。Snowball是Lucene SandBox里的一个组件，它是信息检索中用于处理字符串的处理的一个算法，可以将一个句子进行分词运算，并取其词根的操作。

我们对根据分词，取词根，利用共指消解工具后得到的指代关系处理以及原始的词频统计这系列的步骤处理之后，得到的词或词组的统计信息，接下来再进行语义相似度的计算：如果两个经过分词处理得到的文本都是是单个词，并且在WordNet中可以查询到它们的语义信息，我们就应用WordNet进行语义相似度计算；否则，则利用Wiki进行相应的语义相似度计算。

当两个概念之间的语义相似度大于某个域值的时候，对两个概念进行合并，词频数相加。这样，我们就在主题抽取的步骤中引入了语义。对于单个网页内 的keyword进行语义合并的算法，本文采用了层次聚类的方法。两个聚类之间的 距离，我们用了两个类中任意两个元素的距离的平均。每一个聚类Ci为一个 keyword的集合，即Ci={ki，1 ki，2 ki，3 ...ki，n }， 两个聚类Ci Cj的距离记为davg（Ci， Cj），

1.每一个keyword作为一个初始类，设定一个类之间的距离阈值d0；

2.计算任意两个类之间的距离；

3.将所有两两之间的距离大于阈值d0的类合并；

4.重复2，3步，直到第 3步不再有类合并为止，算法结束。通过语义相似的文本的聚类处理以后，我们得到了一些Keyword的聚类。接下来进行语义合并的处理。通过检索WordNet，判断聚类里的Keyword，如果ki kj是同义词的话，用ki kj里词频大的Keyword作为代表，词频数为两者之和；如果ki kj有共同的上位词（深度小于 4），则用它们的上位词作为代表，词频数为两者之和。

由于通过链接分析得到的网页集，它们只是因为互相有着紧密的链接相互指向，而被挖掘出来，分到同一个网页集当中，其结果可能并不只是一个社区，因此我们需要再进行一次网页集的聚类。

通过无关内容块的过滤之后，抽取出文本信息的网页集，与平常的文档集有着比较多的相似之处，因此，在网页集的聚类方面，本文借鉴了文档集的聚类方法。文本聚类在本质上是一种通过对对象集合按照某种规则进行划分或覆盖从而发现隐含的潜在有用的信息的一种知识发现的方法。聚类算法通常有以下几类：（1）通过构建类别层次或者构造一棵类别树进行聚类的层次聚类算法；（2）将数据集进行划分的分割聚类算法；（3）按其连接分量的密度定义类别的基于密度的聚类方法；（4）通过对属性空间进行单元划分，然后对单元进行聚类的网络聚类算法；（5）其他聚类算法还有基于“核”的聚类算法以及利用进化算法，梯度下降法等的聚类算法。各种不同的应用对聚类质量、效率以及结果可视化程度等方面往往都有特定的要求，因此要根据应用场合和目的选用适合的聚类算法。

由于一个网页集中主题的个数是不确定的，因此本文选用层次聚类作为网页集聚类的算法。因为层次聚类算法首先假设所有文档自成一类，然后将最相似的两类合并，并继续这一过程，直到最后将所有文档合并为一类，因而可以形成一棵聚类树。层次聚类的优点在于可以适用于任意形状的类别并且适用于任意形式的相似度或距离形式。另外，聚类粒度比较灵活性，聚类质量比较高，在信息检索的应用背景下，层次聚合聚类在检索相关文档方面要比基于划分的算法要好。

从网页集中获取主题词，许多方法是将单个网页页面主题词提取技术用于网页集主题词的提取。目前，网页集主题词的提取常见的方法有：

1.先建立特定领域的模板，再从文档中提取信息填充模板，通过比较模板的内容，获取共同部分生成主题词；

2.建立文档中的实体名对，通过分析实体名的出现频率确定网页集中各网页的相关程度；

3.先建立词的活动网络，再从中提取文本的中心内容。另外，当前网页集主题词提取研究的主要方向是基于统计的机械式文摘方法。但是，越来越多的现象表明，统计并不能完全取代语义分析。不考虑句子的含义和句子间的关系机械抽取，必然导致主题词的准确率低，连贯性差，产生一系列问题。因此，理想的网页集主题词提取模型应当将两种方法相结合。

三、试验设计与结果分析

为了测试我们的算法，我们选择了两组不同的数据。

第一组数据是体育方面的文章，是通过spider从fm365网站上搜集的，包含485篇文章。经过切词处理，去掉停用词（stop words）后保留了2719个特征词。通过人类专家手工分类，将文档分为六类，如下：

第二组数据是文艺类的文章，也是通过spider从互联网上获取的，包含了1199篇文章。在去掉停用词后保留了15171个特征词。通过预处理，将在文章中出现频率少于0.1%或多于90%的词过滤后（见第四章），保留了7542个特征词。通过人类专家手工分类，这1199篇文章被分到六个不同的类别中：

值得注意的是，文艺类数据中各个类别的区分不像体育类中那么明显，特别是某些类别涵盖面非常广泛，比如时尚、笑话、其他的范围非常大，因而在几百篇文章中并不能使其统计规律得到充分的体现，由此会带来较大的误差。如果没有对语义的理解，可以想象即使是人类专家要对他进行合理的分类也有相当的困难。

对这两组数据，我们用K-means，Ward’s method，HBC，以及本文提出的聚类算法分别作了测试（K-means，Ward’s method使用SPSSv10.0 进行的测试）。

使用K-means算法聚类，对于文艺类数据，聚类目标为6个类别时，最大的类别包括了974篇文章，并且准确率只有54.13%。对于体育类数据，当聚类目标为6时，最大的类别包括了446篇文章，准确率为53.28%。使用Ward’s method进行聚类，进行聚类，对文艺类数据达到的最高的准确率为62.41%，对体育类的准确率为61.41%。

这两种算法的准确率均远低于HBC算法和本文介绍的其他算法，因而下面的讨论中不再考虑它们，而只与HBC算法进行对比。

对于文艺类数据：

三种算法在恰好分为六个类别时每个类别的文章数量，如下表所示：

总体来看三个算法产生的结果都没有明显的失衡，MED与HBC算法的分类都非常均匀，这两个算法的第一个类别出现了较大的偏差，经对比，此类别中的文档主要来自“其他”类。各种聚类方法的准确率如下：

从总体结果来看，MED算法取得了最佳的效果，相对MEI有了一定的改进。与HBC算法相比准确率也有明显的提高。

四、结论

本文所采用的分词技术，并不是简单的按照空格，标点来进行英文单词的分词，而是采用了Brown大学的Charniak's parser。这个工具可以将输入的文本的句子结构解析出来，同时可以把句中的名词短语，动词，以及介词，副词划分出来，标上词性。因此，这样很多名词短语，如人名、专有名词都可以很好的解释出来，对比普通的分词工具，对主题的抽取的准确性有了很大的改进。并且我们引入了共指消解，利用了著名的共指消解系统GuiTAR进行了文本的共指消解的处理，使得我们可以知道文本中的代词所指代的名词，因此在词频统计时，将代词所指代的名词的词频加上相应的代词出现的次数。这样就既解决了主题抽取的结果中会出现无谓的高词频的代词的现象，同时还增加了主题抽取的准确性。另外，本文在进行网页集的主题抽取之前，利用单个网页本身的主题词进行了基于语义相似度的网页的聚类，使得拥有不同主题的网页聚集到不同的类中，从而减少了不同主题的网页产生的噪声。而且，利用主题词之间的语义相似度，而不是单纯的计算关键字的内积，使得网页之间的语义信息得以保留，也提高了主题抽取的准确性。

参考文献：

[1]Georgios Paliouras. Discovery ofWeb user communities and their role in personalization[J].Springer Science+Business Media B.V.10 March 2012.

[2]唐焕玲.文本分类系统SECTSCS中若干技术问题的探讨[J].计算机工程与应用，2003（11）.

[3]陈克利.基于大规模真实文本的平衡语料分析与文本分类方法[C].Advances in Computation of Oriental Languages.北京：清华大学出版社，2003.

[4]Nazir，A.，Raza，S，Chuah， C.N.： Unveiling facebook：ameasurement study of social network based applications.In： Papagiannaki，K.，Zhang，Z.L.（eds.）Proceedings of the Eighth ACM SIGCOMM Conference on Internet Measurement， Vouliagmeni，43-56（2008）.

[5]Chris Fraley and Adrian E.Raftery， Model-Based Clustering， Discriminate Analysis， and Density Estimation，Technical Report NO.380，Department of Statistics， University of Washington，October 2000

[作者简介]朱一（1964-），女，河南开封人，硕士，高级讲师，研究方向：研究方向为数据库等。