基于文件指纹的Web文本挖掘

在迅猛增加的海量异构的Web信息资源中，蕴含着巨大潜在价值的数据。如何从浩如烟海的Web资源中发现潜在有价值的知识成为迫在眉睫的问题。人们迫切需要能从Web上快速、有效地发现资源和数据的工具，以提高在Web上检索信息、利用信息的效率。

目前Web文本挖掘大部分研究都是建立在词汇袋(bag of words)或称向量表示法(Vector Representation)的基础上，这种方法将单个的词汇看成文档集合中的属性，只从统计的角度将词汇孤立地看待而忽略该词汇出现的位置和上下文环境。词汇袋方法的一个弊端是自由文本中的数据丰富，词汇量非常大，处理起来很困难，为解决这个问题人们做了相应的研究，采取了不同技术，如信息增益，交叉熵、差异比等，其目的都是为了减少属性。一个比较有意义的方法是潜在语义索引(Latent Semantic Indexing)，它通过分析不同文档中相同主题的共享词汇，找到它们共同的根，用这个公共的根代替所有词汇，以此来减少维空间。其它的属性表示法还有词汇在文档中的出现位置、层次关系、使用短语、使用术语、命名实体等，目前还没有研究表明一种表示法明显优于另一种。

图1 文本聚类模型

本文所提出的挖掘技术，不是基于词汇属性，而是文本块。在利用网页的标签树结构的基础上，提取标题和文本块生成SHA-1指纹序列，如果两个页面具有的相同的指纹块在我们所设定的范围内，那么就把这两个页面归为一类，类值就是所要聚类的准确数目k，接下来用k-means进行文本聚类，达到文本挖掘的目的[2][3]。图1是文本聚类模型。

文本预处理

◆网页净化

由于Web文本上存在大量的广告、html标签、相关链接等无用信息，所以首先要对所收集到的网页进行净化处理，也称为网页去噪，以提高聚类效果。我们把网页设计者为了辅助网站组织而增加的文字定义为“噪声”，把原本要表达的文字素材称为“主题内容”。 这些噪音是与页面主题无关(即浏览者不关心)的区域及项，包括广告栏、导航条、修饰成分等。

这样，我们对HTML源码进行分析，根据起分隔作用的标记去掉噪音部分，提取出网页正文[4]。

◆生成SHA-1指纹

SHA的全称是Secure Hash Algorithm，即安全哈希算法。它是由美国国家标准和技术协会(NIST)开发，于1993年作为联邦信息处理标准(FIPS PUB 180)公布。1995年又发布了一个修订版FIPS PUB 180-1，通常称之为SHA-1。现在已成为公认的最安全的散列算法之一，并被广泛使用。该算法的思想是接收一段明文，然后以一种不可逆的方式将它转换成一段(通常更小)密文，也可以简单的理解为取一串输入码(称为预映射或信息)，并把它们转化为长度较短、位数固定的输出序列即散列值(也称为信息摘要或信息认证代码)的过程[5]。

由于sha-1算法的雪崩效应，对文本块作信息摘要时，要消除文本块中的不可见字符，而文本块排序是为了降低算法的复杂度。对于净化后的文本块，通过格式分析生成M个文本块B1，B2，…BM(文本块按重要性排序)，取前m(≤ M)个文本块生成sha-1指纹sha-11，sha-12，…sha-1m。对于网页对(pi，pj)，定义STm (pi，pj)= m0/m，其中m0为pi，pj的相同sha-1指纹的个数。易得，给定范围t，如果STm (pi，pj)∈t，则把两个页面归为某一类。

文本聚类

目前，有多种文本聚类算法，常见的聚类方法有层次凝聚类方法和以k-means为代表的平面划分法。

层次聚类方法能够生成层次化的嵌套簇，且准确度较高。但是在每次合并时需要全局地比较所有簇之间的相似度，并选择出最佳的两个簇，因此运行速度较慢，不适合于大量文档的集合。

近年来各种研究显示，平面划分法比层次凝聚法更适合对大规模文档进行聚类，这是因为平面划分法的计算量相对较小。如：层次凝聚法中的Single-link和group-average方法的时间复杂度为O(n2)，complete-link法的时间复杂度为(n3)，n为文档数。而平面划分法中的k-means法的时间复杂度为O(nKT)，single-pass法的时间复杂度为O(nK)，其中n为文档数，k是最终聚类数目，T是迭代次数。

所以本文选取k-means算法进行文本聚类，k-means 算法接受输入量 k;然后将n个数据对象划分为 k个聚类以便使所获得的聚类满足，同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。

k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。

虽然k-means算法对初始聚类中心选取较敏感，但在本文中，文本分成了多少个类，就有多少个k对象。以两个文本块相同的指纹数作为它们的相似度做聚类得到最终聚类结果。

总结

本文舍弃了常用的提取特征值，计算文本相似度的方法，而是对净化的文本块作分块的信息摘要(即文件指纹)，在比较相同指纹的基础上对文本进行分类，以类值为k-means算法的初始聚类值，以两文本的相同指纹数作为文本的相似度做文本聚类。