FPC: 大規(guī)模網(wǎng)頁(yè)的快速增量聚類

余 鈞，郭 巖，張 凱，劉 林，劉 悅，俞曉明，程學(xué)旗

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190; 2. 中國(guó)科學(xué)院大學(xué)，北京 100190; 3. 中國(guó)信息安全評(píng)測(cè)中心，北京 100085)

FPC: 大規(guī)模網(wǎng)頁(yè)的快速增量聚類

余 鈞1,2，郭 巖1，張 凱1，劉 林3，劉 悅1，俞曉明1，程學(xué)旗1

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190; 2. 中國(guó)科學(xué)院大學(xué)，北京 100190; 3. 中國(guó)信息安全評(píng)測(cè)中心，北京 100085)

面向結(jié)構(gòu)相似的網(wǎng)頁(yè)聚類是網(wǎng)絡(luò)數(shù)據(jù)挖掘的一項(xiàng)重要技術(shù)。傳統(tǒng)的網(wǎng)頁(yè)聚類沒有給出網(wǎng)頁(yè)簇中心的表示方式，在計(jì)算點(diǎn)簇間和簇簇間相似度時(shí)需要計(jì)算多個(gè)點(diǎn)對(duì)的相似度，這種聚類算法一般比使用簇中心的聚類算法慢，難以滿足大規(guī)模快速增量聚類的需求。針對(duì)此問題，該文提出一種快速增量網(wǎng)頁(yè)聚類方法FPC(Fast Page Clustering)。在該方法中，先提出一種新的計(jì)算網(wǎng)頁(yè)相似度的方法，其計(jì)算速度是簡(jiǎn)單樹匹配算法的500倍；給出一種網(wǎng)頁(yè)簇中心的表示方式，在此基礎(chǔ)上使用Kmeans算法的一個(gè)變種MKmeans(Merge-Kmeans)進(jìn)行聚類，在聚類算法層面上提高效率；使用局部敏感哈希技術(shù)，從數(shù)量龐大的網(wǎng)頁(yè)類集中快速找出最相似的類，在增量合并層面上提高效率。

DOM樹分層向量；網(wǎng)頁(yè)簇中心；局部敏感哈希；快速增量聚類

1 引言

Web抽取是網(wǎng)絡(luò)數(shù)據(jù)挖掘中的重要應(yīng)用。針對(duì)海量網(wǎng)頁(yè)的抽取，可以把結(jié)構(gòu)相似的網(wǎng)頁(yè)自動(dòng)聚成一類，對(duì)聚類后的網(wǎng)頁(yè)簇歸納出高效精確的抽取規(guī)則，從而提高抽取的準(zhǔn)確率。傳統(tǒng)的面向結(jié)構(gòu)的網(wǎng)頁(yè)聚類算法中，通常沒有給出網(wǎng)頁(yè)簇中心的表示方式。它們一般使用代表點(diǎn)的聚類算法，在計(jì)算點(diǎn)簇間距離和簇簇間距離時(shí)需要計(jì)算多個(gè)點(diǎn)對(duì)的距離，難以應(yīng)用到大規(guī)模網(wǎng)頁(yè)增量聚類中。

為了解決面向結(jié)構(gòu)的大規(guī)模網(wǎng)頁(yè)聚類問題，本文提出一種快速網(wǎng)頁(yè)增量聚類方法FPC(Fast Page Clustering)。在該方法中，先提出DOM樹分層向量，用多個(gè)DOM樹分層向量的中心來(lái)近似反映多棵DOM樹的中心。在此基礎(chǔ)上，采用基于向量、集合相似度的方式來(lái)計(jì)算兩個(gè)網(wǎng)頁(yè)的相似度，其計(jì)算效率比傳統(tǒng)的樹編輯距離高；給出一種網(wǎng)頁(yè)簇中心的表示方式，進(jìn)而提出使用Kmeans算法的一個(gè)變種MKmeans(Merge-Kmeans)，實(shí)現(xiàn)網(wǎng)頁(yè)的快速聚類；使用局部敏感哈希技術(shù)，從數(shù)量龐大的網(wǎng)頁(yè)類集合中可以快速找出和給定類最相似的類，從而實(shí)現(xiàn)快速增量聚類。實(shí)驗(yàn)表明：(1)選用的網(wǎng)頁(yè)特征確實(shí)有效合理，網(wǎng)頁(yè)簇中心確實(shí)可以代表網(wǎng)頁(yè)簇的一些公共結(jié)構(gòu)中心，在網(wǎng)頁(yè)聚類中很有效；(2)相似的網(wǎng)頁(yè)類，使用局部敏感哈希技術(shù)計(jì)算得到的指紋也相似，可以用于快速查找近似最相似類；(3)FPC的速度遠(yuǎn)高于傳統(tǒng)的網(wǎng)頁(yè)聚類方法，且其準(zhǔn)確率和回收率都非常高。

本文余下章節(jié)安排如下: 第二節(jié)介紹相關(guān)工作；第三節(jié)介紹快速網(wǎng)頁(yè)增量聚類方法FPC；第四節(jié)是實(shí)驗(yàn)結(jié)果和分析；第五節(jié)是對(duì)本文的總結(jié)并討論下一步的研究方向。

2 相關(guān)工作

計(jì)算兩個(gè)網(wǎng)頁(yè)的相似度有很多辦法。文獻(xiàn)[1]使用DOM樹編輯距離來(lái)表示兩個(gè)網(wǎng)頁(yè)的相似度，這種方法計(jì)算代價(jià)較高。文獻(xiàn)[2]使用局部標(biāo)簽樹匹配的方法來(lái)進(jìn)行聚類，將DOM 樹的每一層節(jié)點(diǎn)的HTML標(biāo)簽連接成串，計(jì)算對(duì)應(yīng)層字符串的編輯距離的加權(quán)和作為兩個(gè)網(wǎng)頁(yè)的距離，這種方法要求每層節(jié)點(diǎn)個(gè)數(shù)相差不大,對(duì)記錄型網(wǎng)頁(yè)效果不太好。文獻(xiàn)[3]使用鏈路壓縮樹來(lái)定義網(wǎng)頁(yè)的相似度，這種方法對(duì)高層節(jié)點(diǎn)很敏感。文獻(xiàn)[4]使用自頂向下的樹編輯距離來(lái)計(jì)算網(wǎng)頁(yè)的相似度，這種方法對(duì)高層節(jié)點(diǎn)也很敏感，高層節(jié)點(diǎn)不匹配，則相似度非常小。

傳統(tǒng)的網(wǎng)頁(yè)聚類使用點(diǎn)代表的聚類方法，這些算法的執(zhí)行效率較低，難以應(yīng)用到大規(guī)模網(wǎng)頁(yè)增量聚類中。文獻(xiàn)[5]用的是自底向上的CURE算法，兩個(gè)簇間的距離由這兩個(gè)簇中距離最近的數(shù)據(jù)點(diǎn)的距離來(lái)確定。文獻(xiàn)[6]用的是類CURE算法，兩個(gè)簇間的距離由來(lái)自兩簇的所有點(diǎn)對(duì)的距離的平均值來(lái)確定。

局部敏感哈希技術(shù)(Locality Sensitive Hash)主要用來(lái)解決高維空間中點(diǎn)的近似最近鄰搜索問題。LSH將原始空間中的點(diǎn)嵌入到漢明(Hamming)空間中，原始空間中的度量變成Hamming空間中的度量。文獻(xiàn)[7]使用局部哈希技術(shù)將一個(gè)網(wǎng)頁(yè)映射到一個(gè)64位的二進(jìn)制指紋上，通過(guò)查找相似的指紋可以快速檢測(cè)出內(nèi)容近似的網(wǎng)頁(yè)。

3 快速增量聚類方法FPC

本文的FPC方法使用基于向量、集合的相似度來(lái)計(jì)算兩個(gè)網(wǎng)頁(yè)的相似度，比傳統(tǒng)的基于樹編輯距離和鏈路方法快得多；給出一種網(wǎng)頁(yè)簇結(jié)構(gòu)中心的表示方式，在這個(gè)基礎(chǔ)上提出使用一種類似Kmeans的算法MKmeans(Merge Kmeans)實(shí)現(xiàn)網(wǎng)頁(yè)的快速聚類；并使用局部敏感哈希技術(shù)從大規(guī)模的網(wǎng)頁(yè)簇中快速找出近似最相似簇，實(shí)現(xiàn)快速增量聚類。

3.1 網(wǎng)頁(yè)特征

網(wǎng)頁(yè)是一種半結(jié)構(gòu)化數(shù)據(jù)，同模板生成的網(wǎng)頁(yè)，在結(jié)構(gòu)上較相似，在內(nèi)容上也相似，如廣告鏈接、導(dǎo)航欄和版權(quán)信息等可能也會(huì)相似。FPC從網(wǎng)頁(yè)中提取若干結(jié)構(gòu)特征和內(nèi)容特征，用來(lái)表示一個(gè)網(wǎng)頁(yè)。

3.1.1 DOM樹分層向量

DOM樹是一個(gè)重要的網(wǎng)頁(yè)結(jié)構(gòu)特征，但是計(jì)算DOM樹的編輯距離的代價(jià)太高。在HTML標(biāo)記語(yǔ)言中，大部分標(biāo)簽是不能隨意插入和刪除的，標(biāo)簽的嵌套關(guān)系相對(duì)比較固定，同模板網(wǎng)頁(yè)，語(yǔ)義相同的節(jié)點(diǎn)鏈路一般也會(huì)相同。

基于這個(gè)事實(shí)，給出下面的假設(shè)：

(1) 兩個(gè)同模板網(wǎng)頁(yè)，它們匹配上的節(jié)點(diǎn)大多處在樹中同一層位置上；

(2) 在一個(gè)網(wǎng)頁(yè)內(nèi)，相同語(yǔ)義的迭代型節(jié)點(diǎn)(如帖子根節(jié)點(diǎn))一般處在同一層位置上；

(3) 相同語(yǔ)義的迭代型節(jié)點(diǎn)，它們子樹中每一層的節(jié)點(diǎn)分布相似，于是對(duì)同模板的網(wǎng)頁(yè)，它們?cè)诘訕渖蠘?biāo)簽的頻率分布也相似。

由這些假設(shè)可以推出，同模板網(wǎng)頁(yè)，它們?cè)诿繉拥臉?biāo)簽分布向量也會(huì)相似。本文為此引入DOM樹分層向量，該向量組是一個(gè)有序向量組，它的第i個(gè)向量表示樹的第i層節(jié)點(diǎn)按標(biāo)簽名的頻率分布。

定義1 DOM樹分層向量，如式(1)所示。

(1)

圖1的兩個(gè)網(wǎng)頁(yè)中，網(wǎng)頁(yè)1的DOM樹分層向量是： (html: 1), (head: 0.5,body: 0.5), (meta: 0.5,div: 0.25,a: 0.25) (p: 1)。網(wǎng)頁(yè)2的DOM樹分層向量是：(html:1), (head: 0.5,body: 0.5), (meta: 0.4,div: 0.4,a: 0.2)。

圖1 樣例頁(yè)面

多個(gè)DOM樹分層向量的中心也是一個(gè)分層向量，它的第i個(gè)向量是所有這些分層向量的第i個(gè)向量的中心。對(duì)DOM樹，很難找出多棵DOM樹的中心骨干。但對(duì)于多個(gè)DOM樹分層向量，可以快速地計(jì)算出它們的中心。

定義2 DOM樹分層向量的中心，如式(2)所示。

(2)

結(jié)構(gòu)相似的網(wǎng)頁(yè)，其DOM樹分層向量相似，且它們的中心也和它們相似。對(duì)多個(gè)網(wǎng)頁(yè)的中心向量，在相似層，它和各網(wǎng)頁(yè)對(duì)應(yīng)層向量的平均相似度較大；在不相似層，它和各網(wǎng)頁(yè)對(duì)應(yīng)層向量的平均相似度會(huì)較小。設(shè)置閾值，當(dāng)中心的某層向量到各網(wǎng)頁(yè)層的平均相似度較小時(shí)，則從中心去掉該層的向量，這樣得到的中心分層向量將會(huì)保存這些網(wǎng)頁(yè)中相似層部分，不相似層將會(huì)去掉。

如圖1，網(wǎng)頁(yè)1和網(wǎng)頁(yè)2較相似，它們的DOM樹分層向量的中心是：(html: 1), (head: 0.5,body: 0.5), (meta: 0.45,div: 0.325,a: 0.225) (p: 0.5)。

3.1.2 其他特征

同模板網(wǎng)頁(yè)有一些屬性值比較特殊的標(biāo)簽，如Discuz論壇軟件生成的帖子頁(yè)面中，會(huì)經(jīng)常出現(xiàn)這種標(biāo)簽。本文用標(biāo)簽-屬性特征來(lái)保存具有特定屬性的標(biāo)簽的標(biāo)識(shí)串，標(biāo)識(shí)串的格式是“標(biāo)簽名+屬性名+屬性值”。

FPC選取部分內(nèi)容作為網(wǎng)頁(yè)的特征。這些內(nèi)容特征包括：鏈接地址、CSS文件名、JS文件名、JS中出現(xiàn)的函數(shù)名、錨文本、短文本、圖片名。

這些特征都是集合型的，每個(gè)特征包含多個(gè)字符串。多個(gè)網(wǎng)頁(yè)，它們對(duì)應(yīng)特征會(huì)有若干共同元素，這些共同元素是這些網(wǎng)頁(yè)的公共固定部分?？梢杂眉现行膩?lái)表示多個(gè)網(wǎng)頁(yè)的集合型特征的公共固定部分。

定義3 多個(gè)集合的中心

多個(gè)集合的中心是一個(gè)集合，該中心集合中的元素是在這些集合中出現(xiàn)比例超過(guò)某個(gè)閾值的元素。

3.2 網(wǎng)頁(yè)表示和網(wǎng)頁(yè)簇中心表示

FPC選取九個(gè)網(wǎng)頁(yè)特征，在這些基礎(chǔ)上給出網(wǎng)頁(yè)和網(wǎng)頁(yè)簇的中心的表示方式，并給出相似度的計(jì)算方法。

3.2.1 網(wǎng)頁(yè)表示

我們使用DOM樹分層向量，以及3.1.2節(jié)中的八個(gè)特征來(lái)表示一個(gè)網(wǎng)頁(yè)。從網(wǎng)頁(yè)中計(jì)算出DOM樹分層向量，找出標(biāo)簽-屬性值、鏈接地址等內(nèi)容特征，可以將網(wǎng)頁(yè)映射到一個(gè)特征向量上。

定義 4 網(wǎng)頁(yè)表示為式(3)。

(3)

其中，fi是網(wǎng)頁(yè)的第i個(gè)特征，除了DOM樹分層向量外，其他特征都是集合型的。

3.2.2 網(wǎng)頁(yè)簇中心表示

許多聚類算法要求給出簇中心的表示方法。FPC將網(wǎng)頁(yè)簇中心定義為一個(gè)隱藏網(wǎng)頁(yè)，它包含網(wǎng)頁(yè)的九個(gè)特征，其所反映的是簇中網(wǎng)頁(yè)的公共固定部分。它的各個(gè)特征是簇中所有網(wǎng)頁(yè)相應(yīng)特征的中心。

定義5 網(wǎng)頁(yè)簇中心，如式(4)所示。

(4)

其中P1,…,Pn表示n個(gè)網(wǎng)頁(yè)，fi,Pk是網(wǎng)頁(yè)P(yáng)k的第i個(gè)特征，i=1,..9,k=1,…,n。對(duì)DOM分層向量，按定義2的方式給出其中心，對(duì)其余八個(gè)集合型特征，按定義3的方式給出其中心。網(wǎng)頁(yè)簇中心可以很好地反映簇中網(wǎng)頁(yè)的共同穩(wěn)定部分。如果簇中網(wǎng)頁(yè)相似，則簇中心和它們也相似。

3.2.3 相似度計(jì)算

網(wǎng)頁(yè)與網(wǎng)頁(yè)、網(wǎng)頁(yè)與網(wǎng)頁(yè)簇的相似度，是各個(gè)特征相似度的加權(quán)和，計(jì)算公式如式(5)所示。

(5)

其中S1,S2是網(wǎng)頁(yè)或網(wǎng)頁(yè)簇中心，weightfi是特征fi的權(quán)重，Simfi是特征fi的相似度。

對(duì)兩個(gè)DOM樹分層向量，它們的相似度是各對(duì)應(yīng)層向量的余弦相似度之和除以兩者向量層數(shù)和的一半，計(jì)算公式如式(6)所示。

(6)

對(duì)集合型的特征，相似度計(jì)算采用不同的計(jì)算方式。

1. 兩個(gè)網(wǎng)頁(yè)，或者兩個(gè)簇中心，它們的集合型特征的相似度使用Jaccard相似性度量，平滑后的公式為式(7)。

(7)

其中S1,S2都是網(wǎng)頁(yè)或者都是簇中心的集合型特征，α是FPC中MKmeans算法合并簇的相似度閾值。

2. 網(wǎng)頁(yè)和簇中心，它們的集合型特征的相似度稍有不同，平滑后的公式為式(8)。

(8)

其中S是網(wǎng)頁(yè)的集合型特征，T是簇中心的集合型特征。

3.3 增量聚類

FPC使用Leader-Follower策略進(jìn)行網(wǎng)頁(yè)增量聚類，即將網(wǎng)頁(yè)分批聚類，對(duì)每批聚類后的類，從已有類集中查找最相似的類，如果它們的相似度大于給定閾值，則將它們合并在一起，否則將該類作為新類并添加到類集中。

3.3.1 單批網(wǎng)頁(yè)聚類算法MKmeans

Kmeans算法需要提前指定類別個(gè)數(shù)，但是網(wǎng)頁(yè)類別的個(gè)數(shù)通常難以提前確定。為此，F(xiàn)PC提出使用一種類似Kmeans的算法MKmeans(Merge-Kmeans)，該算法不需要提前指定K值，聚類結(jié)果中類個(gè)數(shù)是由合并類的閾值間接決定。通過(guò)修改類合并閾值，可以使得聚類后每類網(wǎng)頁(yè)的類內(nèi)平均相似度都較高。MKmeans算法如下。

算法1 聚類算法MKmeans(Merge-Kmeans)

輸入：網(wǎng)頁(yè)集合S，初始類相異閾值d，類合并閾值α，類內(nèi)平均相似度變化閾值e，最大迭代次數(shù)T

輸出：網(wǎng)頁(yè)類

1. 初始類中心：對(duì)S中的網(wǎng)頁(yè)，逐個(gè)計(jì)算其與已有類中心的相似度，如果最大相似度小于閾值d，則該網(wǎng)頁(yè)成為一個(gè)新的類中心；

2. 歸入最近類：將S中的網(wǎng)頁(yè)逐個(gè)歸入最相近的類；

3. 更新類中心：計(jì)算每個(gè)類中心，它是類中所有網(wǎng)頁(yè)的中心；

4. 合并相似類：計(jì)算各對(duì)類的相似度，不斷合并最相似的類，直到所有類之間的相似度都小于閾值α；

5. 迭代步驟2,3,4，直到迭代次數(shù)超過(guò)T或類內(nèi)平均相似度的變化已經(jīng)小于閾值e。

3.3.2 增量合并

在增量聚類的過(guò)程中，如果類集中類的個(gè)數(shù)太多，則從中查找最相似類的時(shí)間開銷將很大。FPC使用局部敏感哈希技術(shù)計(jì)算出類的指紋信息，用其來(lái)篩選出小部分備選類，再?gòu)膫溥x類中找最相似類。FPC對(duì)一個(gè)網(wǎng)頁(yè)類，可以計(jì)算得到一個(gè)指紋組，一個(gè)指紋組包含32個(gè)16位的二進(jìn)制指紋。計(jì)算指紋組算法如下。

算法2 計(jì)算指紋組算法FingerPrints

輸入： 一個(gè)網(wǎng)頁(yè)類C，四個(gè)哈希函數(shù)Hi，i=1,2,3,4

輸出：指紋組(32個(gè)16位的二進(jìn)制指紋)

1. 對(duì)哈希函數(shù)Hi(i=1,2,3,4)，依次

1.1使用一個(gè)128位的二進(jìn)制數(shù)X，將其清零；

1.2對(duì)網(wǎng)頁(yè)類C的中心的標(biāo)簽-屬性特征中的每個(gè)元素，分別用Hi計(jì)算其哈希結(jié)果hashvalue，將X的第hashvalue%128位置1；

1.3將X切分成八個(gè)16位的二進(jìn)制數(shù)，得到八個(gè)指紋；

2. 每個(gè)哈希函數(shù)得到八個(gè)指紋，四個(gè)哈希函數(shù)共得到32個(gè)指紋，返回指紋組。

指紋組中的指紋是有序的，兩個(gè)指紋組相似度等于兩組對(duì)應(yīng)序號(hào)且相等的指紋的個(gè)數(shù)除以指紋組長(zhǎng)度32。計(jì)算公式如式(9)所示。

(9)

其中，F(xiàn)1,i是指紋組FS1的第i個(gè)指紋，F(xiàn)2,i是指紋組FS2的第i個(gè)指紋，

相似的網(wǎng)頁(yè)類，它們的指紋組很可能也相似，利用指紋組，可以快速地找出近似最相似的類，從而實(shí)現(xiàn)快速增量聚類。FPC在增量聚類的過(guò)程中，保存已有類集中每個(gè)類的中心及其指紋組信息，同時(shí)保存32個(gè)指紋的倒排索引表，索引內(nèi)容是類的標(biāo)識(shí)。子類合并算法如下。

算法 3 子類合并到類集中算法 Merge-Cluster

輸入：子類C，類庫(kù)(S,F, IDX)，S是已有類集，F(xiàn)是類的指紋組表，IDX=(index1,…,index32)是32個(gè)指紋索引表，指紋相似閾值β

輸出：合并C后的類庫(kù)(S,F, IDX)

1. 計(jì)算C的指紋信息F1,…,F32；

2. 分別從index1,…,index32中找到F1,…,F32對(duì)應(yīng)的索引列l(wèi)1,…,l32；

3. 在索引列l(wèi)1，…,l32中找出出現(xiàn)次數(shù)超過(guò)32*β的類，記這些類為備選類；

4. 從備選類中找出和子類C最近的類，如果相似度大于給定閾值，則將子類C和最相似的類進(jìn)行合并；否則，子類C成為一個(gè)新的類，添其加到類集中。

5. 更新發(fā)生變化的類的指紋組表F和索引表IDX。

4 實(shí)驗(yàn)與分析

4.1 聚類實(shí)驗(yàn)

本實(shí)驗(yàn)是為了評(píng)測(cè)FPC中聚類方法的效果。對(duì)比實(shí)驗(yàn)使用STM計(jì)算相似度，用文獻(xiàn)[6]中用于網(wǎng)頁(yè)聚類的類CURE算法進(jìn)行聚類，該類CURE算法用兩個(gè)類之間所有的點(diǎn)對(duì)的平均相似度作為兩個(gè)類的相似度，不斷合并最相似的類，直到所有的類的相似度小于給定閾值。本文將該對(duì)比實(shí)驗(yàn)方法稱為STM+CURE。

4.1.1 實(shí)驗(yàn)數(shù)據(jù)

數(shù)據(jù)集1：采集15個(gè)新聞網(wǎng)站，每個(gè)網(wǎng)站采集20個(gè)網(wǎng)頁(yè)，共300個(gè)網(wǎng)頁(yè)。我們認(rèn)為，由相同軟件生成的網(wǎng)頁(yè)屬于同一模板，于是將這300個(gè)網(wǎng)頁(yè)分為15個(gè)模板類。

數(shù)據(jù)集2：采集100個(gè)論壇網(wǎng)站，每個(gè)網(wǎng)站采集10個(gè)網(wǎng)頁(yè)，共1 000個(gè)網(wǎng)頁(yè)，分為23個(gè)模板類。

4.1.2 評(píng)價(jià)指標(biāo)

我們使用以下三種指標(biāo)進(jìn)行評(píng)價(jià)：

1. 準(zhǔn)確率 Precision, 回收率Recall， F值。

2. 時(shí)間開銷，評(píng)測(cè)兩者的效率。

4.1.3 結(jié)果分析

考慮到對(duì)比實(shí)驗(yàn)中的類CURE算法時(shí)間復(fù)雜度較高，我們?cè)趯?shí)現(xiàn)類CURE算法時(shí)，做了很多優(yōu)化。實(shí)驗(yàn)結(jié)果如表1所示。

表1 聚類測(cè)試結(jié)果

注：APS-Time(Average Page Similarity Time)：計(jì)算兩個(gè)網(wǎng)頁(yè)相似度的平均時(shí)間開銷。

另外，在數(shù)據(jù)集2上，前者的回收率比后者高出62.5%。這是因?yàn)镾TM算法太過(guò)敏感，在計(jì)算樹的相似度時(shí)，如果兩棵子樹的根節(jié)點(diǎn)不一樣，則認(rèn)為這兩棵子樹的匹配數(shù)為0，于是若兩棵子樹高層節(jié)點(diǎn)偏差稍大，則可能導(dǎo)致計(jì)算得到的相似度很小，從而使得同類網(wǎng)頁(yè)被錯(cuò)誤分開。而FPC是把各層的相似度類加起來(lái)，高層結(jié)點(diǎn)差異不影響計(jì)算低層的相似度。因此，F(xiàn)PC算法健壯性更好，適用范圍更廣，回收率也更高。

同時(shí)，F(xiàn)PC的準(zhǔn)確率也很高。這表明FPC中所選用的網(wǎng)頁(yè)特征確實(shí)很有效，網(wǎng)頁(yè)簇中心能很好地反應(yīng)多個(gè)網(wǎng)頁(yè)的一些公共固定部分，將其用在簇中心代表的聚類算法中很有效。

4.2 指紋實(shí)驗(yàn)

本實(shí)驗(yàn)是為了驗(yàn)證兩方面內(nèi)容：(1)指紋相似，則類也較相似；(2)利用指紋可以有效篩選出類集中一小部分備選類，最相似的類落在備選集中的概率會(huì)很大。

4.2.1 實(shí)驗(yàn)數(shù)據(jù)

數(shù)據(jù)集3：采集1160個(gè)網(wǎng)站網(wǎng)頁(yè)，每個(gè)網(wǎng)站采集5個(gè)網(wǎng)頁(yè)，共5 800個(gè)網(wǎng)頁(yè)。聚成302個(gè)類，記為類集3。

數(shù)據(jù)集4：采集855個(gè)網(wǎng)站網(wǎng)頁(yè)，每個(gè)網(wǎng)站采集5個(gè)網(wǎng)頁(yè)，共4 275個(gè)網(wǎng)頁(yè)。聚成149個(gè)類，記為類集4。

數(shù)據(jù)集4所選的網(wǎng)站絕大部分是來(lái)自數(shù)據(jù)集3中所選的網(wǎng)站，但這兩個(gè)數(shù)據(jù)集所用網(wǎng)頁(yè)完全不一樣。因此，類集3和類集4間雖然有許多類是相似的，但它們不會(huì)完全一樣(這里指類中心的特征不會(huì)完全相同)。

4.2.2 結(jié)果分析

計(jì)算類集3和類集4之間所有類對(duì)的類相似度和指紋相似度，得到指紋相似度—類相似度曲線，如圖2所示。

對(duì)類集4中的每一個(gè)類，計(jì)算其指紋，從類集3中篩選出和其指紋相似度超過(guò)閾值β的備選類，檢測(cè)和其最相似的類是否落在備選類集中。表2給出不同指紋相似閾值β下的備選集大小，同時(shí)還給出最相似的類落在其中的概率。

圖2 指紋相似度-類相似度曲線

表2 備選集測(cè)試結(jié)果

注：備選集大小是指，備選集在整個(gè)類集3中所占的比例。

從圖2可以看出，指紋相似度和類相似度存在一種很好的正相關(guān)關(guān)系，兩個(gè)類的指紋越相似，則這兩個(gè)類也越可能相似。從表2可以看出，利用指紋可以篩選出一個(gè)很小的備選類集，而最相似類落在備選集中的概率會(huì)非常大。例如，當(dāng)指紋相似閾值取0.05時(shí)，就可以篩選出一個(gè)6.9%大小的備選集，而最相似類落在該備選集中的概率是90.6%。

因此，在增量合并類的過(guò)程中，可以篩選出一小部分備選集，最相似的類落在備選集中的概率很大，即使最相似類沒有落在備選集中，從備選集中仍然可以找出和其很相似的類。例如，從圖2中可以看出，當(dāng)指紋相似閾值取0.45時(shí)，備選集中的類和需合并的子類的平均相似度達(dá)到0.3。因此，利用局部敏感哈希，確實(shí)可以從很小的備選集中近似找到最相似的類，從而大大提高FPC在增量合并類的效率。

5 結(jié)論

本文先提出DOM樹分層向量概念，給出一種新的計(jì)算網(wǎng)頁(yè)相似度的方法，其速度是簡(jiǎn)單樹匹配算法的500倍，并且適用范圍更廣。本文還提出一種網(wǎng)頁(yè)簇中心的表示方式。在這些基礎(chǔ)上用類Kmeans算法MKmeans實(shí)現(xiàn)網(wǎng)頁(yè)的快速聚類，其正確率回收率都很高，這表明所選的網(wǎng)頁(yè)特征和網(wǎng)頁(yè)簇中心表示方式確實(shí)非常有效。最后，本文使用局部敏感哈希技術(shù)，可以在龐大的網(wǎng)頁(yè)類集中快速找出近似最相似的類，從而提高增量合并中查找相似類的效率。

本文在使用公式(1)計(jì)算網(wǎng)頁(yè)相似度時(shí)，各個(gè)特征權(quán)重是預(yù)先設(shè)定的，在接下來(lái)的工作中準(zhǔn)備通過(guò)一些機(jī)器學(xué)習(xí)方法訓(xùn)練出更好的參數(shù)。另外，網(wǎng)頁(yè)簇中心除了用在聚類上，還可以用在分類上。如何使用網(wǎng)頁(yè)簇中心以用于分類當(dāng)中，這是一個(gè)有待繼續(xù)研究的問題。

[1] Reis D C,Golgher P B, Silva A S, et al. Automatic Web news extraction using tree edit distance[C]//Proceedings of the 13th International Conference on World Wide Web. New York: ACM.

[2] 李 睿, 曾俊瑀, 周四望. 基于局部標(biāo)簽樹匹配的改進(jìn)網(wǎng)頁(yè)聚類算法[J]. 計(jì)算機(jī)應(yīng)用, 2010，30(3)：818-820.

[3] 宋明秋, 張瑞雪. 基于鏈路壓縮樹的網(wǎng)頁(yè)相似度研究[J]. 情報(bào)學(xué)報(bào), 2012，31(1)：40-46.

[4] 何昕,謝志鵬. 基于簡(jiǎn)單樹匹配算法的Web頁(yè)面結(jié)構(gòu)相似性度量[J]. 計(jì)算機(jī)研究與發(fā)展, 2007，44(23)：1-6.

[5] 邱韜奮,楊天奇,曾洪波. 基于網(wǎng)頁(yè)聚類的Web 信息自動(dòng)抽取[J]. 微型機(jī)與應(yīng)用, 2011，31(4)：71-74.

[6] 賴春波. Web信息自動(dòng)抽取技術(shù)研究[D]. 浙江:浙江大學(xué), 2008.

[7] Gurmeet Singh Manku, Arvind Jain, Anish Das Sarma. Detecting near-duplicates for web crawling[C]//Proceedings of the 16th International Conference on World Wide Web, Banff, Alberta, Canada, 2007: 141-150.

FPC: Fast Incremental Clustering for Large Scale Web Pages

YU Jun1,2, GUO Yan1,ZHANG Kai1, LIU Lin3, LIU Yue1, YU Xiaoming1, CHENG Xueqi1

(1. CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China； 2. University of Chinese Academy of Sciences, Beijing 100190, China；3. China Information Technology Security Evaluation Center, Beijing 100085, China)

Structure-oriented web page clustering is one of the most important technique in web data mining. Previous traditional methods haven’t given a formal definition of the web page cluster center and have to calculate several point-wise similarities for the purpose of getting the similarity between a point and a cluster or the similarity between two clusters. The efficiency of these methods is much slower than the clustering algorithms using cluster center, especially they can’t satisfy the need of large scale clustering in fast incremental web pages clustering. To solve these issues, this paper proposes a fast incremental clustering method FPC (Fast Page Clustering). In our method, a new approach is given to calculat the similarity between two web pages which is 500 times faster than the Simple Tree Matching algorithm; then a formal representation of web page cluster center is described and a Kmeans-like MKmeans(Merge-Kmeans) clustering algorithm for fast clustering is applied; Moreover, we use local sensitive hashing technique to quickly find the most similar cluster in a large scale cluster set and improve the efficiency in terms of the incremental clustering.

DOM tree layered vectors; web page cluster center; local sensitive hashing; fast incremental clustering

余鈞(1988—)，碩士，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)信息處理。E?mail：yu．jun．reach@gmail．com郭巖(1974—)，博士，高級(jí)工程師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)信息處理。E?mail：guoy@ict．a(chǎn)c．cn張凱(1976—)，碩士，助理研究員，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)采集。E?mail：zk@ict．a(chǎn)c．cn

1003-0077(2016)02-0182-07

2013-08-25 定稿日期： 2014-06-01

國(guó)家973計(jì)劃(2012CB316303，2013CB329602)；國(guó)家863計(jì)劃(2014AA015204)；國(guó)家自然科學(xué)基金(61232010，61425016，61572473，61572467)

TP391

A