面向FAQ文档轻量级聚类算法.docVIP

面向FAQ文档的轻量级聚类算法 　　[摘要]文档聚类分析是组织文档的一种有效方法，在信息处理中被广泛应用于未知话题的自动发现并取得不错的效果。提出一个轻量级聚类算法，该算法利用减小原始文档的索引数来处理大量小文档，并把它们分组到几千个簇，或者通过更改特定参数，将聚类簇的数量减小到几十个。理论分析和实际应用表明，该算法改善了对高维数据和大量小文档的处理效率。 　　[关键词]数据挖掘　Web文档聚类　k均值算法　自动化信息表示 　　[分类号]TP311 　　 　　1 引 言 　　 　　文档聚类是将一个文档集合的模式根据相似度划分为多个簇的过程，其中模式一般表示为一个向量或者一个多维空间的点。Web信息的急速膨胀急切需要有效的信息检索工具，因此聚类分析重新引起研究者的重视。文本聚类在文本总结、标签赋值、维度缩减和消除冗余等领域比实时信息检索具有更大的价值。 ???　 　　WEB留言簿是公司产品使用者之间实现信息交流、产品使用回馈和讨论的环境。随着时间的增长和用户的增加，留言文档的数量会呈指数级增长。用户提出问题或意见，所积累的大量小文档，本身就构成了关于产品特定主题的知识库。通过对这些文档进行聚类分析，产品供应商就会拥有产品使用者所有问题或建议的一个全局视图，如果生成的簇形成一个自然的问题类型，那么这些聚簇将被赋予一个标签或者主题。新的用户问题将被组织到合适的标签，同时被发送到合适的问题回复队列。一旦合适的簇被识别出来，可以使用任意一个文档分类方法对文档分类。然而很多问题往往是重复出现的，根据使用者提交的相同问题，就会创建一个FAQ(Frequently Asked Questions)报告。为了减少数据库中的产品重复文档数量，必须降低文档的冗余度。因为许多问题表面很相似但实际上有本质区别，所以用来消除问题文档的簇数要远小于问题文档的数量，但要比人工总结的问题类型的数量大得多。 　　 　　由于小文档具有不同于普通静态文档的特性，传统的聚类算法不能很好的应用于大量小文档分析。本文针对小文档这种特定语料的内在特性，在分析现有聚类算法不足的基础上，描述了一个新的面向FAQ小文档的轻量级聚类算法。该算法用于处理大量的小文档，并把文档集合聚类为适用于文档总结、组织标签和消除重复的聚簇。 　　 　　2　文档聚类技术 　　 　　聚类算法中的K均值算法是比较经典的一个基于划分的聚类算法，是将n个数据对象划分为k个聚类，以使所获得聚簇满足以下要求：同一聚簇中的对象相似度较高，而不同聚簇中的对象相似度较小。k均值算法比较简单，结果簇是密集的，并且聚簇与聚簇区别明显时，显示出很好的效果，时间复杂度是0(k*n*t)(其中n是所有对象的数目，k是聚簇的数目，t是算法迭代次数)，有相对的可伸缩性和高效率；但是该算法聚类前要求事先给出生成聚簇的数目k，而且该算法不适用于发现非凸面形状的或者大小差别很大的簇。 　　 　　层次聚类算法递归对对象进行合并或者分裂，直到满足某一终止条件。层次聚类的结果可以用一个谱系图表示，树中的每个节点都是一个簇，下层的簇是上层簇的嵌套，每一层节点构成一组划分。根据谱系图的生成顺序，层次聚类分为凝聚的和分裂的。最常用的是凝聚的层次聚类算法。单链接算法(Single-linkage)是将文档与文档之间的距离定义为两个文档中样本之间的最小距离值，d(ci，q)=mind(x，y)，其中x∈ci，y∈q。单联接算法的特点是算法简单，容易构造和理解，但是算法的时间和空间复杂度都是O(n2)(n为样本的个数)。 　　对大量文本聚类，很可能会产生大量的簇，作为折中方案必需减少索引词的个数和进行比较的次数。每个文档的索引词是25个在TF-IDF(term frequency and inverse documentfrequency)公式中得分最高的词，应用K均值算法(k=9)进行迭代。尽管这种方法有效，但同样有经典k-means算法的缺点。 　　本文描述一个有效处理高维数据和直接产生具有高相似度的聚簇的轻量级过程。同k均值算法相比，聚簇数量是动态决定的，采用最近邻距离计算相似度。因此，新的文档聚类算法保持了层次聚类的主要优势，并且同信息检索方法相兼容，但性能不会随着文档数量的增加而降低。 　　 　　3　面向FAQ文档轻量级聚类算法 　　 　　3.1　数据准备 　　每个小文档由一个特征词条集合代表，用向量表示每一个特征词条，向量的每一个元素代表一个特征词的存在与否。为获得文档的特征词条，需要对文档进行分词处理，利用停用词表将停用词从文档特征矢量中删除，然后运用倒排文档频率(IDF)约简特征词条，保留文档集中倒排文档频率在一定范围内的特征词条作为文档特征集合。相同的过程用于降低索引，通过比较代表文档向