一種面向WEB頁(yè)面的標(biāo)記聚類(lèi)方法?

焦永強(qiáng) 王維揚(yáng) 尚 穎

（1.中國(guó)航空綜合技術(shù)研究所 北京 100028）（2.北京化工大學(xué) 北京 100029）

1 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，Web應(yīng)用以其易于開(kāi)發(fā)與升級(jí)、擴(kuò)展性好、系統(tǒng)靈活性強(qiáng)等優(yōu)點(diǎn)，獲得了越來(lái)越多企業(yè)的青睞。但Web應(yīng)用程序相較于傳統(tǒng)應(yīng)用程序，擁有更獨(dú)特的結(jié)構(gòu)和功能，傳統(tǒng)軟件測(cè)試技術(shù)難以對(duì)Web應(yīng)用進(jìn)行有效的測(cè)試。

Web頁(yè)面是構(gòu)成Web應(yīng)用的基本元素，是用戶(hù)與Web應(yīng)用交互的媒介。傳統(tǒng)的Web應(yīng)用為每個(gè)頁(yè)面綁定了一個(gè)唯一的URL，因此，頁(yè)面可以用URL表示。然而，在Web 2.0中，為豐富交互及響應(yīng)，提升用戶(hù)體驗(yàn)，JavaScript（JS）和 DOM（Docu?ment Object Model）廣泛使用。因此，Web頁(yè)面的改變不再由URL決定，而是由DOM的動(dòng)態(tài)改變決定。即Web頁(yè)面表示為DOM樹(shù)，JS代碼執(zhí)行過(guò)程中動(dòng)態(tài)改變DOM樹(shù)，從而使得頁(yè)面發(fā)生變化。A.Nederlof等的研究表明，在Web 2.0應(yīng)用中，平均每個(gè)URL對(duì)應(yīng)16個(gè)DOM頁(yè)面［1］。由此可以看出，DOM微小變化可使Web頁(yè)面急劇擴(kuò)充，導(dǎo)致頁(yè)面集合十分復(fù)雜與龐大，增大了Web應(yīng)用測(cè)試的難度。

在Web應(yīng)用測(cè)試過(guò)程中，由于一個(gè)Web應(yīng)用中大量頁(yè)面具有類(lèi)似的DOM樹(shù)結(jié)構(gòu)［2～4］，而對(duì)這些相似Web頁(yè)面單獨(dú)生成測(cè)試用例進(jìn)行測(cè)試降低了測(cè)試生成效率。為減少相似Web頁(yè)面對(duì)測(cè)試生成的影響，大多采用Web頁(yè)面聚類(lèi)方法，即將相似頁(yè)面聚為同類(lèi)，類(lèi)內(nèi)頁(yè)面作為一個(gè)頁(yè)面進(jìn)行測(cè)試，以減少測(cè)試的時(shí)間開(kāi)銷(xiāo)。

目前，Web頁(yè)面聚類(lèi)方法主要有三類(lèi)：面向URL的頁(yè)面聚類(lèi)［5］、基于頁(yè)面超鏈接的頁(yè)面聚類(lèi)［6］和基于DOM結(jié)構(gòu)的頁(yè)面聚類(lèi)方法［7～11］。由于JS和Ajax技術(shù)的使用，頁(yè)面超鏈接和URL不能很好地表示W(wǎng)eb頁(yè)面，因此，其對(duì)應(yīng)的頁(yè)面聚類(lèi)方法應(yīng)用領(lǐng)域有限。當(dāng)前的研究主要集中在基于DOM的頁(yè)面聚類(lèi)方法。文獻(xiàn)［7］最早提出基于DOM樹(shù)的頁(yè)面聚類(lèi)方法，該方法利用樹(shù)編輯距離來(lái)度量?jī)身?yè)面之間的相似度，并基于此對(duì)頁(yè)面進(jìn)行聚類(lèi)，然而樹(shù)編輯距離的計(jì)算復(fù)雜度高，且該方法未考慮由于頁(yè)面內(nèi)容不同導(dǎo)致的相似Web頁(yè)面，因此，聚類(lèi)準(zhǔn)確度不高。文獻(xiàn)［8］提出了一種基于DOM結(jié)構(gòu)和樣式相結(jié)合的頁(yè)面聚類(lèi)方法，采用樹(shù)編輯距離作為結(jié)構(gòu)相似度的度量準(zhǔn)則，同時(shí)考慮頁(yè)面樣式，如布局/顏色/字體等的相似度對(duì)頁(yè)面進(jìn)行聚類(lèi)。該方法聚類(lèi)準(zhǔn)確度有所提升，但其計(jì)算復(fù)雜度很高。

文獻(xiàn)［9］提出了Bag of Xpath模型，把頁(yè)面表示為包含當(dāng)前頁(yè)面元素位置索引的Xpath集合，通過(guò)計(jì)算兩個(gè)頁(yè)面Xpath集合元素之間的差異來(lái)度量二者之間的相似度，進(jìn)而實(shí)現(xiàn)頁(yè)面聚類(lèi)，該方法雖然降低了計(jì)算復(fù)雜度，但其聚類(lèi)準(zhǔn)確度不高。文獻(xiàn)［10］通過(guò)深度遍歷將兩個(gè)頁(yè)面的DOM結(jié)構(gòu)轉(zhuǎn)換成一個(gè)元素節(jié)點(diǎn)標(biāo)簽序列，比較兩個(gè)頁(yè)面的節(jié)點(diǎn)標(biāo)簽序列來(lái)計(jì)算頁(yè)面之間的相似度，同樣地，該方法的頁(yè)面聚類(lèi)準(zhǔn)確度不太理想。

綜上，目前Web頁(yè)面聚類(lèi)準(zhǔn)確率較低而時(shí)間復(fù)雜度較高。分析其原因，是由于1）上述方法大多僅考慮DOM樹(shù)結(jié)構(gòu)之間的相似性。具有相同DOM結(jié)構(gòu)的頁(yè)面可能表征的功能不同，在Web應(yīng)用功能測(cè)試時(shí)不應(yīng)被劃分至同一類(lèi)；2）現(xiàn)有的頁(yè)面之間相似性度量方法不能準(zhǔn)確區(qū)分不同頁(yè)面，且其相似性計(jì)算及聚類(lèi)算法的時(shí)間復(fù)雜度較高。

此外，Web頁(yè)面屬性為頁(yè)面元素定義屬性（如id、name和class），實(shí)現(xiàn)頁(yè)面元素樣式渲染以及事件綁定，為Web應(yīng)用程序提供了多種定制化服務(wù)。可以看出，頁(yè)面屬性與Web頁(yè)面功能密切相關(guān)。換言之，為區(qū)分表征不同功能的頁(yè)面，頁(yè)面元素的屬性必不可少。

因此，本文提出一種新的頁(yè)面聚類(lèi)方法，不僅考慮了DOM結(jié)構(gòu)之間的相似性，而且考慮了頁(yè)面屬性之間的相似性，同時(shí)給出了一種新的頁(yè)面相似性度量方法。在此基礎(chǔ)上，改進(jìn)了現(xiàn)有的頁(yè)面聚類(lèi)算法，實(shí)現(xiàn)Web頁(yè)面聚類(lèi)。該方法不僅能夠描述復(fù)雜的Web頁(yè)面，且具有較低的時(shí)間復(fù)雜度和較高的頁(yè)面聚類(lèi)準(zhǔn)確度。

2 Web頁(yè)面DOM結(jié)構(gòu)與節(jié)點(diǎn)屬性

Web頁(yè)面是構(gòu)成Web應(yīng)用的基本元素，DOM將頁(yè)面表達(dá)為樹(shù)結(jié)構(gòu)，稱(chēng)為DOM樹(shù)，DOM樹(shù)上的節(jié)點(diǎn)類(lèi)型包括元素節(jié)點(diǎn)、屬性節(jié)點(diǎn)和文本節(jié)點(diǎn)，分別表示頁(yè)面中的元素、文本和屬性。為了表述方便，下文將“元素節(jié)點(diǎn)”統(tǒng)稱(chēng)為“節(jié)點(diǎn)”，“屬性節(jié)點(diǎn)”統(tǒng)稱(chēng)為“屬性”，“文本節(jié)點(diǎn)”統(tǒng)稱(chēng)為“文本”。所有DOM節(jié)點(diǎn)相互包含組成的樹(shù)形結(jié)構(gòu)構(gòu)成了Web頁(yè)面的基本結(jié)構(gòu)，也被稱(chēng)為DOM結(jié)構(gòu)。

2.1 DOM

DOM將Web頁(yè)面表達(dá)為樹(shù)結(jié)構(gòu)，定義了訪問(wèn)和操作頁(yè)面節(jié)點(diǎn)、文本及屬性的標(biāo)準(zhǔn)方法。Web頁(yè)面以標(biāo)簽（tag）來(lái)標(biāo)識(shí)DOM節(jié)點(diǎn)，如圖1所示。圖1的樹(shù)形結(jié)構(gòu)表示了一個(gè)簡(jiǎn)單Web頁(yè)面的DOM樹(shù)，表示某教師管理系統(tǒng)的用戶(hù)管理頁(yè)面，該頁(yè)面實(shí)現(xiàn)對(duì)教師的增刪改等操作，其中淺灰線為屬性，點(diǎn)線為文本，其余為節(jié)點(diǎn)。

圖1DOM樹(shù)

2.2 節(jié)點(diǎn)屬性

Web頁(yè)面的每一個(gè)節(jié)點(diǎn)都擁有若干屬性，在構(gòu)建網(wǎng)頁(yè)時(shí)，節(jié)點(diǎn)屬性必不可少，且每個(gè)屬性都具有其作用。根據(jù)W3C標(biāo)準(zhǔn)，id屬性用來(lái)唯一標(biāo)識(shí)網(wǎng)頁(yè)中的元素，如果兩個(gè)Web頁(yè)面中的兩個(gè)節(jié)點(diǎn)具有相同的id，則它們有極大的概率是相同的節(jié)點(diǎn)。class屬性用來(lái)標(biāo)識(shí)一類(lèi)元素，這一類(lèi)元素往往具有相同的樣式，因?yàn)镃SS通常采用class（類(lèi)）名來(lái)為節(jié)點(diǎn)定制樣式。Id和class屬性都有一個(gè)最重要的特性，即能夠綁定事件，因此，二者與Web應(yīng)用的行為密切相關(guān)。name屬性比較特殊，表示一個(gè)節(jié)點(diǎn)的名字，常常用于form節(jié)點(diǎn)中。在Web應(yīng)用中form節(jié)點(diǎn)被大量的使用，而在Web測(cè)試中不同的form往往意味著與后臺(tái)數(shù)據(jù)交互的不同，表示不同的功能，這對(duì)功能測(cè)試有很大的影響。

圖2為某圖書(shū)管理系統(tǒng)的書(shū)籍管理頁(yè)面，實(shí)現(xiàn)對(duì)書(shū)籍借閱、查找、歸還等操作。圖1和2所示的兩個(gè)DOM具有相同結(jié)構(gòu)，但其div標(biāo)簽具有不同的id及name，且為不同的id綁定不同的事件。因此，即使這兩個(gè)Web頁(yè)面的DOM結(jié)構(gòu)完全相同，也應(yīng)被識(shí)別為不同的頁(yè)面。

圖2 與圖1具有相同DOM結(jié)構(gòu)的DOM2

顯然，基于DOM結(jié)構(gòu)的頁(yè)面聚類(lèi)方法對(duì)此類(lèi)頁(yè)面的聚類(lèi)準(zhǔn)確度較低。因此，為準(zhǔn)確區(qū)分不同Web頁(yè)面，在進(jìn)行頁(yè)面比較時(shí)，不僅需要考慮Web頁(yè)面中DOM結(jié)構(gòu)之間的相似性，屬性之間的相似性比較在頁(yè)面聚類(lèi)中也十分重要。

3 Web頁(yè)面相似性度量新方法

Web應(yīng)用的頁(yè)面中，具有相同DOM結(jié)構(gòu)的頁(yè)面可能表示不同的功能頁(yè)，而在Web應(yīng)用功能測(cè)試時(shí)不能被劃分至同一類(lèi)。因此，僅考慮DOM結(jié)構(gòu)相似性的頁(yè)面聚類(lèi)方法會(huì)產(chǎn)生大量誤報(bào)的情況。為提高頁(yè)面聚類(lèi)的準(zhǔn)確性，本文同時(shí)考慮Web頁(yè)面之間DOM結(jié)構(gòu)和屬性的差異，提出了新的頁(yè)面相似度度量方法，并給出一種高效的改進(jìn)樹(shù)匹配算法來(lái)計(jì)算頁(yè)面相似度。

本節(jié)首先定義頁(yè)面之間的頁(yè)面相似量定義；然后，給出改進(jìn)樹(shù)匹配算法計(jì)算頁(yè)面相似量；最后，為比較多個(gè)Web頁(yè)面之間的相似程度，基于頁(yè)面相似量，給出頁(yè)面之間相似度計(jì)算方法。

3.1 相似性度量指標(biāo)

頁(yè)面相似量用來(lái)度量?jī)蓚€(gè)Web頁(yè)面，即兩棵DOM樹(shù)，之間的相似程度，由DOM樹(shù)上各個(gè)節(jié)點(diǎn)之間的節(jié)點(diǎn)相似量求和得出。由上述分析可知，僅通過(guò)DOM結(jié)構(gòu)之間的相似程度進(jìn)行頁(yè)面聚類(lèi)是不充分的，頁(yè)面屬性也與Web應(yīng)用功能密切相關(guān)，因此，本文同時(shí)考慮頁(yè)面結(jié)構(gòu)和屬性之間的相似性，給出頁(yè)面相似性度量方法，以準(zhǔn)確識(shí)別相似頁(yè)面。

為度量節(jié)點(diǎn)及屬性之間的相似量，我們針對(duì)DOM樹(shù)定義四種相似基量：Tag相似基量λtag、ID相似基量λid、Name相似基量λname和Class相似基量λclass，相似基量表示節(jié)點(diǎn)相似量度量時(shí)節(jié)點(diǎn)及屬性的相似量權(quán)重。

兩棵DOM樹(shù)根節(jié)點(diǎn)標(biāo)簽tag值相似基量為式（1）。

節(jié)點(diǎn)各屬性（id、name、class）的相似基量如式（2～4）。

其中 ||ID1和 ||ID2分別表示兩個(gè)DOM樹(shù)中具有id屬性的節(jié)點(diǎn)個(gè)數(shù)，name和class同理， ||T1和 ||T2分別表示兩個(gè)DOM樹(shù)的節(jié)點(diǎn)總數(shù)。

算法一：兩個(gè)Web頁(yè)面DOM樹(shù)T1和T2頁(yè)面相似量計(jì)算

輸入：兩個(gè)Web頁(yè)面DOM樹(shù)T1和T2

輸出：T1相對(duì)于 T2的相似量 F（T1，T2）

步驟1.分別對(duì)T1和T2進(jìn)行深度遍歷得到它們的總結(jié)點(diǎn)個(gè)數(shù)|T1|和|T2|，分別具有 id、name、class屬性的節(jié)點(diǎn)個(gè)數(shù)|ID1|、|NAME1|、|CLASS1|、|ID2|、|NAME2|、|CLASS2|；

步驟2.通過(guò)式（2）～（4）計(jì)算各個(gè)屬性的相似基量值λid、λname、λclass；

步驟3.設(shè)T1的當(dāng)前根節(jié)點(diǎn)為N1，T2的當(dāng)前根節(jié)點(diǎn)為N2，當(dāng)前樹(shù)的相似量為F（T1，T2）=0 ；

步驟6.轉(zhuǎn)步驟3進(jìn)行遞歸計(jì)算得出T1i相對(duì)于T2j的相似量為 F（T1i，T2j）；

步驟 7.j=j+1，判斷如果 j>m，F(xiàn)（T1，T2）=F（T1，T2）+F（T1i，B），i=i+1，j=0 ；否則 F（T1i，B）=MAX（F（T1i，B），F(xiàn)（T1i，T2j）），轉(zhuǎn)步驟6；

步驟8.判斷如果i>n，算法停止，輸出F（T1，T2）；否則轉(zhuǎn)步驟6；

根據(jù)DOM特性，定義兩個(gè)節(jié)點(diǎn)N1和N2之間的節(jié)點(diǎn)相似量：當(dāng)tag值不同時(shí)，他們之間的節(jié)點(diǎn)相似量f（N1，N2）=0，相同時(shí)相似量如式（5）。

眾所周知，沙特阿拉伯是美國(guó)在中東地區(qū)的重要盟友和戰(zhàn)略支點(diǎn)。美沙之間不斷發(fā)展的緊密聯(lián)系，成為了美國(guó)在中東地區(qū)發(fā)揮影響力的重要支點(diǎn)。

其中當(dāng)id值、name值相同時(shí)，Cid=Cname值為“1”，不相同時(shí)值為“0”；Cclass計(jì)算公式如下：

在節(jié)點(diǎn)相似量的基礎(chǔ)上，給出頁(yè)面相似量計(jì)算公式如下：假設(shè)兩頁(yè)面對(duì)應(yīng)的兩棵DOM樹(shù)為T(mén)1和T2，其根節(jié)點(diǎn)分別為 N1和 N2，T1和 T2子樹(shù)的集合為A=［T11，T12，T13，…，T1n］，B=［T21，T22，T23，…，T2m］，則定義T1相對(duì)于T2的頁(yè)面相似量為式（7）：

式（1～7）定義了節(jié)點(diǎn)之間的節(jié)點(diǎn)相似量及DOM樹(shù)之間的頁(yè)面相似量度量公式。為計(jì)算兩棵DOM樹(shù)之間的頁(yè)面相似量，我們?cè)诂F(xiàn)有樹(shù)匹配算法［12］的基礎(chǔ)上，增加了對(duì)頁(yè)面屬性信息的度量，提出了改進(jìn)的樹(shù)匹配算法，如算法一所示。

3.2 相似度定義

頁(yè)面相似量是一個(gè)絕對(duì)值，它在一定程度上能反映兩個(gè)頁(yè)面的相似程度，但是在多個(gè)網(wǎng)頁(yè)之間并沒(méi)有可比性，因此，本文將頁(yè)面相似量進(jìn)行歸一化，記為頁(yè)面相似度，并用相似度來(lái)進(jìn)行Web頁(yè)面間的差異性比較。對(duì)于給定的兩個(gè)Web頁(yè)面，它們對(duì)應(yīng)的DOM樹(shù)分別為T(mén)1和T2，|T1|和|T2|分別表示兩者的節(jié)點(diǎn)個(gè)數(shù)，假設(shè)二者包含id屬性的節(jié)點(diǎn)總個(gè)數(shù)為M，包含name屬性的節(jié)點(diǎn)總個(gè)數(shù)為N，包含class數(shù)屬性的節(jié)點(diǎn)總個(gè)數(shù)為K，則它們之間的相似度定義為式（8）：

其中 F（T1，T2），F(xiàn)（T2，T1）分別表示 T1相對(duì)于 T2的相似量及T2相對(duì)于T1的相似量，λid、λname和λclass的計(jì)算如式（2～4）。

4 標(biāo)記聚類(lèi)算法

Web頁(yè)面集合龐大，頁(yè)面多種多樣且結(jié)構(gòu)復(fù)雜，因此，無(wú)法預(yù)先判斷最終聚類(lèi)的個(gè)數(shù)，這使得一些傳統(tǒng)的聚類(lèi)算法如k-means不再適用于Web頁(yè)面聚類(lèi)［13］。凝聚層次聚類(lèi)（Hierarchical Agglomera?tive Clustering，HAC）方法是一種常用的層次聚類(lèi)算法，該方法無(wú)需預(yù)先設(shè)定類(lèi)簇個(gè)數(shù)，常被應(yīng)用于Web頁(yè)面聚類(lèi)中［14～15］。基礎(chǔ)凝聚層次聚類(lèi)HAC算法具有o（n3）的時(shí)間復(fù)雜度，改進(jìn)的凝聚層次聚類(lèi)算法［16］，能達(dá)到的最好的時(shí)間復(fù)雜度是o（n2）。本文在改進(jìn)的HAC基礎(chǔ)上，提出了標(biāo)記聚類(lèi)算法（Marked Clustering，MC），即在聚類(lèi)的同時(shí)進(jìn)行頁(yè)面標(biāo)記，在理想的情況下最低能達(dá)到o（n）的時(shí)間復(fù)雜度。

4.1 MC聚類(lèi)算法基本思想

為了在保證聚類(lèi)準(zhǔn)確性的同時(shí)減少聚類(lèi)所用的時(shí)間，本文基于Web頁(yè)面的特性提出標(biāo)記聚類(lèi)算法。該算法的核心思想是在計(jì)算Web頁(yè)面間相似度之后，對(duì)頁(yè)面進(jìn)行聚類(lèi)標(biāo)記，即當(dāng)Web頁(yè)面之間的相似度超過(guò)設(shè)定閾值，則將兩個(gè)Web頁(yè)面標(biāo)記為同一類(lèi)；針對(duì)已經(jīng)標(biāo)記的Web頁(yè)面不再進(jìn)行后續(xù)的Web頁(yè)面比較；且各類(lèi)僅取任一頁(yè)面作為當(dāng)前類(lèi)中所有頁(yè)面的代表，當(dāng)判斷其他Web頁(yè)面是否歸屬于此類(lèi)時(shí)，僅與類(lèi)中的代表頁(yè)面進(jìn)行相似度比較即可。

4.2 算法描述

標(biāo)記聚類(lèi)MC主要有以下五個(gè)步驟，算法流程如圖3所示。

圖3 MC算法流程

1）初始化兩個(gè)集合A、B，其中A是所有Web頁(yè)面的集合，B=Ф；聚類(lèi)標(biāo)記k=0；

2）從A中選擇一個(gè)元素a，將［a，k］添加到B中，然后從A中刪除a；

3）從A中順序選擇一個(gè)元素b，通過(guò)改進(jìn)樹(shù)匹配算法計(jì)算a與b之間的頁(yè)面相似度，如果相似度大于閾值則將［b，k］添加到B中，然后從A中刪除b；否則進(jìn)行下一步；

4）判斷是否遍歷A中所有元素，如果是進(jìn)行下一步，否則轉(zhuǎn)3）；

5）判斷A是否為空，如果不為空則令k=k+1，轉(zhuǎn)2）。

最終得到B集合即為聚類(lèi)結(jié)果，B中每個(gè)元素均為二元組，表示W(wǎng)eb頁(yè)面及其所屬的類(lèi)簇的標(biāo)號(hào)。

標(biāo)記聚類(lèi)MC算法的時(shí)間復(fù)雜度是o（n2），但是由于每一次循環(huán)都會(huì)減少下一次需要比較的頁(yè)面數(shù)量，事實(shí)上程序運(yùn)行時(shí)間會(huì)大大降低。且最終聚類(lèi)的數(shù)量越少，該方法的時(shí)間復(fù)雜度越小。在理想的情況下最少能達(dá)到o（n）的時(shí)間復(fù)雜度。

5 實(shí)驗(yàn)

為了驗(yàn)證本文方法的有效性，我們提出了兩個(gè)研究問(wèn)題如下：

1）Web頁(yè)面相似性度量方法的有效性如何？改進(jìn)樹(shù)匹配算法是否優(yōu)于其他樹(shù)匹配算法？

2）標(biāo)記聚類(lèi)算法MC是否能在不影響聚類(lèi)結(jié)果的前提下提高聚類(lèi)效率？

5.1 實(shí)驗(yàn)對(duì)象與環(huán)境配置

實(shí)驗(yàn)采用兩個(gè)開(kāi)源的Web應(yīng)用e107和word?press作為被測(cè)程序。實(shí)驗(yàn)在Intel酷睿i5（3470 3.4GHZ）4核CPU、內(nèi)存8GB、Win10操作系統(tǒng)、Py?thon 3.6.4和htmlParser環(huán)境下進(jìn)行。本文選用常用的簡(jiǎn)單樹(shù)匹配算法作為相似性對(duì)比算法，HAC作為聚類(lèi)對(duì)比算法，設(shè)計(jì)了以下兩個(gè)實(shí)驗(yàn)。

實(shí)驗(yàn)一：分別使用簡(jiǎn)單樹(shù)匹配和本文提出的改進(jìn)樹(shù)匹配算法完成頁(yè)面相似性度量，聚類(lèi)方法均采用同一凝聚層次聚類(lèi)方法進(jìn)行頁(yè)面聚類(lèi)。

實(shí)驗(yàn)二：相似性度量采用本文提出的改進(jìn)樹(shù)匹配的算法，聚類(lèi)方法分別使用凝聚層次聚類(lèi)和本文提出的標(biāo)記聚類(lèi)進(jìn)行比較。

5.2 實(shí)驗(yàn)結(jié)果

5.2.1 相似度算法結(jié)果

為了比較兩種相似度算法（改進(jìn)樹(shù)匹配和簡(jiǎn)單樹(shù)匹配）的優(yōu)劣，本實(shí)驗(yàn)收集了兩個(gè)開(kāi)源Web應(yīng)用的100張Web頁(yè)面，并對(duì)其進(jìn)行人工聚類(lèi)，然后將每一類(lèi)的頁(yè)面與同一類(lèi)的頁(yè)面以及其他類(lèi)的頁(yè)面進(jìn)行相似度計(jì)算，比較他們的相似度值。對(duì)于同類(lèi)頁(yè)面，兩種算法均得到了大于0.9的相似度值，這說(shuō)明對(duì)于相似頁(yè)面，兩種算法都能很好的比較其相似度。但對(duì)于不同類(lèi)的頁(yè)面，實(shí)驗(yàn)結(jié)果如圖4所示。

從圖4可以看出，本文提出的改進(jìn)樹(shù)匹配算法對(duì)于屬于不同類(lèi)的頁(yè)面計(jì)算得到的相似度明顯小于簡(jiǎn)單樹(shù)匹配算法的結(jié)果，而且均小于0.9，這說(shuō)明本文的改進(jìn)樹(shù)匹配算法區(qū)分不同類(lèi)頁(yè)面的能力強(qiáng)于簡(jiǎn)單樹(shù)匹配算法。

圖4 兩種算法的頁(yè)面相似度計(jì)算比較結(jié)果

表1 e107

表2 wordpress

為了直觀展示兩種相似度算法對(duì)聚類(lèi)結(jié)果的影響，本部分還給出了分別使用兩種相似度度量算法結(jié)合同一層次聚類(lèi)算法得到的聚類(lèi)結(jié)果，如表1，2所示，本文提出的改進(jìn)樹(shù)匹配算法準(zhǔn)確率和召回率都明顯優(yōu)于簡(jiǎn)單樹(shù)匹配算法。這是由于簡(jiǎn)單樹(shù)匹配將大量的不屬于同一類(lèi)但是卻有相似DOM結(jié)構(gòu)的網(wǎng)頁(yè)聚為一類(lèi)，使得該算法的召回率極低。經(jīng)過(guò)進(jìn)一步的分析發(fā)現(xiàn)，由于Web應(yīng)用中大量使用同一框架和form表單，這使得簡(jiǎn)單樹(shù)匹配算法聚類(lèi)失誤，但本文提出的改進(jìn)樹(shù)匹配算法考慮了更多的屬性信息，從而得到了更好的聚類(lèi)效果。

5.2.2 聚類(lèi)算法結(jié)果

為比較兩種不同的聚類(lèi)算法的效率，采用相同的頁(yè)面相似性度量方法，即改進(jìn)樹(shù)匹配算法，不同的頁(yè)面聚類(lèi)算法對(duì)上述兩個(gè)Web應(yīng)用進(jìn)行了頁(yè)面聚類(lèi)實(shí)驗(yàn)。其中凝聚層次聚類(lèi)HAC算法中類(lèi)之間的相似度采用如式（9）進(jìn)行計(jì)算：

兩種聚類(lèi)算法對(duì)Web頁(yè)面聚類(lèi)的實(shí)驗(yàn)結(jié)果如表3和表4所示。

表3 e107聚類(lèi)算法比較

表4 wordpress聚類(lèi)算法比較

觀察上表可以明顯看出本文提出的標(biāo)記聚類(lèi)算法MC并沒(méi)有影響聚類(lèi)的結(jié)果，但是卻明顯減少了聚類(lèi)時(shí)間，提高了頁(yè)面聚類(lèi)效率。具體來(lái)說(shuō)，對(duì)于e107效率提升了3.4倍，而對(duì)于wordpress效率提升了5.6倍。因此，本文提出的標(biāo)記聚類(lèi)算法效率更高。

6 結(jié)語(yǔ)

在Web測(cè)試中，為解決現(xiàn)有方法在頁(yè)面聚類(lèi)時(shí)準(zhǔn)確率低及效率不高的問(wèn)題，本文提出了一種改進(jìn)樹(shù)匹配算法，不僅考慮Web頁(yè)面結(jié)構(gòu)信息還考慮部分屬性信息，通過(guò)該算法來(lái)計(jì)算Web頁(yè)面之間的相似度顯著提高了聚類(lèi)的準(zhǔn)確性。同時(shí)為了解決傳統(tǒng)聚類(lèi)算法耗時(shí)長(zhǎng)的問(wèn)題，提出一種更為簡(jiǎn)單有效的標(biāo)記聚類(lèi)算法MC。實(shí)驗(yàn)證明，本文的聚類(lèi)算法在不影響聚類(lèi)的準(zhǔn)確性的前提下顯著地降低了聚類(lèi)所用的時(shí)間。