网页自动聚类的方法总结

网页的自动聚类普通包括四个步骤：

(1)网页表示:包括特征抽取和特征选择。特征选择是选择那些最具有区分性的特征,也就是最能把不同类别区分开来的特征,而不是大少数对象都具有的特征。

(2)相似度计算。主要依据网页表示的距离函数来定义。

(3)聚类:依据网页表示和相似度计算的结果,依照一定的规则将聚类网页分红不同的类。

(4)给出聚类的标识。在最后构成的每一类中抽取一定具有代表性的特征,作为该类的标识。

常用的聚类方法有单遍聚类法、逆中心距聚类法、密度测试法、图聚类法等。下面对以上方法做一简明引见。

单遍聚类法是依照一定的顺序从待分类的网页集合中取出一篇网页,恣意赋予它一个新的类别,其标引向量作为该新类的聚类中心向量,尔后取出的各篇网页与该类中心向量停止运算失掉相似系数,当相似系数大于给定的一个预定值的时分,就将该网页归入此类,同时调整类中心向量。假设相似系数不在给定的预定值范围内,则该网页就另立新类并且创立该类中心向量。要处置的每一篇网页依次与已有的类中心向量停止比拟,将其归入相似度最大(且在预定值范围之内)的类中,并且及时调整该类的中心向量。

逆中心聚类法与单遍聚类法比拟相似,详细进程如下:任取一篇网页作为第一个聚类中心,计算剩下的网页到该网页的距离,距离最大的作为第二个聚类中心。计算一切非聚类中心的网页到每个聚类中心的距离,将每一篇网页到每个中心距的最小距离求出,选择出最大的最小中心距者作为新的聚类中心。当然,这个还要结合所定义的中心距离制约机制等其它条件。

密度测试法的原理是假设某个网页的左近集聚有较多的网页,并且在其周围较广的范围内也散布有一定的网页,那么该网页可作为一个聚类中心。在密度测试中,网页被划分为三种类型:未聚类网页,即还没有被集聚就任何一类中的网页;松懈型网页,它们与己经存在的类中心相似度比拟小,尚不具有被聚于某类的条件;己被聚类的网页。在聚类末尾时,一切的网页都可以看作未聚类网页。用Di表示某篇网页,假设它同时满足以下两个条件,则可以将Di作为类别中心:至少有nl篇网页,它们与Di的相似系数都超越Tl;至少有n2篇网页,它们与Di的相似系数都超越T2,其中TI≥T2且nl≤n2。TI、T2、nl、n2都是事前给定的参数。聚类的进程如下:在未聚类网页中任取一篇,把它作为聚类中心并对其停止密度测试,测试范围为尚未聚类和松懈型的网页。假设测试失败,即被测试的网页周围不具有指定数量的网页,则该网页被作为松懈型网页。然后在未聚类网页中重新选取网页测试聚类中心;假设测试成功,即被测试网页周围集聚一定预定值范围内的相似网页,则该网页被作为一个聚类中心,并将其中相似度超越Tl的网页视为已聚类网页,关于相似度小于Tl又大于T2的网页,视为松懈型网页,其他网页不改动原有类型。聚类进程不时继续下去到没有未聚类网页为止。最后将剩下的松懈型网页就近聚集到己存在的类别中。