基于文件指纹的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算法的初始聚类值,以两文本的相同指纹数作为文本的类似度做文本聚类.

　　参考文献

　　[1] 肖湘萍,高玉斌. Web文本发掘[J].电脑知识与技术. 2007.04

　　[2] 王建勇,谢正茂,雷鸣,李晓明. 近似镜像网页检测算法的研究与评测[J]. 电子学报. 2000.05

　　[3] 张明辉,王成耀,宋威. 一种基于段落的分段签名近似镜像新算法[J]. 情报技术. 2005.01

　　[4] 张志刚,陈静,李小明. 一种HTML网页净化办法[J]. 情报学报. 2004.07

　　[5] 旷华. 安全哈希算法SHA[J].华南金融电脑. 2003.06