一種面向WEB頁面的標記聚類方法?

焦永強 王維揚 尚 穎

（1.中國航空綜合技術研究所 北京 100028）（2.北京化工大學 北京 100029）

1 引言

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

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

在Web應用測試過程中，由于一個Web應用中大量頁面具有類似的DOM樹結構［2～4］，而對這些相似Web頁面單獨生成測試用例進行測試降低了測試生成效率。為減少相似Web頁面對測試生成的影響，大多采用Web頁面聚類方法，即將相似頁面聚為同類，類內頁面作為一個頁面進行測試，以減少測試的時間開銷。

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

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

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

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

因此，本文提出一種新的頁面聚類方法，不僅考慮了DOM結構之間的相似性，而且考慮了頁面屬性之間的相似性，同時給出了一種新的頁面相似性度量方法。在此基礎上，改進了現(xiàn)有的頁面聚類算法，實現(xiàn)Web頁面聚類。該方法不僅能夠描述復雜的Web頁面，且具有較低的時間復雜度和較高的頁面聚類準確度。

2 Web頁面DOM結構與節(jié)點屬性

Web頁面是構成Web應用的基本元素，DOM將頁面表達為樹結構，稱為DOM樹，DOM樹上的節(jié)點類型包括元素節(jié)點、屬性節(jié)點和文本節(jié)點，分別表示頁面中的元素、文本和屬性。為了表述方便，下文將“元素節(jié)點”統(tǒng)稱為“節(jié)點”，“屬性節(jié)點”統(tǒng)稱為“屬性”，“文本節(jié)點”統(tǒng)稱為“文本”。所有DOM節(jié)點相互包含組成的樹形結構構成了Web頁面的基本結構，也被稱為DOM結構。

2.1 DOM

DOM將Web頁面表達為樹結構，定義了訪問和操作頁面節(jié)點、文本及屬性的標準方法。Web頁面以標簽（tag）來標識DOM節(jié)點，如圖1所示。圖1的樹形結構表示了一個簡單Web頁面的DOM樹，表示某教師管理系統(tǒng)的用戶管理頁面，該頁面實現(xiàn)對教師的增刪改等操作，其中淺灰線為屬性，點線為文本，其余為節(jié)點。

圖1DOM樹

2.2 節(jié)點屬性

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

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

圖2 與圖1具有相同DOM結構的DOM2

顯然，基于DOM結構的頁面聚類方法對此類頁面的聚類準確度較低。因此，為準確區(qū)分不同Web頁面，在進行頁面比較時，不僅需要考慮Web頁面中DOM結構之間的相似性，屬性之間的相似性比較在頁面聚類中也十分重要。

3 Web頁面相似性度量新方法

Web應用的頁面中，具有相同DOM結構的頁面可能表示不同的功能頁，而在Web應用功能測試時不能被劃分至同一類。因此，僅考慮DOM結構相似性的頁面聚類方法會產生大量誤報的情況。為提高頁面聚類的準確性，本文同時考慮Web頁面之間DOM結構和屬性的差異，提出了新的頁面相似度度量方法，并給出一種高效的改進樹匹配算法來計算頁面相似度。

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

3.1 相似性度量指標

頁面相似量用來度量兩個Web頁面，即兩棵DOM樹，之間的相似程度，由DOM樹上各個節(jié)點之間的節(jié)點相似量求和得出。由上述分析可知，僅通過DOM結構之間的相似程度進行頁面聚類是不充分的，頁面屬性也與Web應用功能密切相關，因此，本文同時考慮頁面結構和屬性之間的相似性，給出頁面相似性度量方法，以準確識別相似頁面。

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

兩棵DOM樹根節(jié)點標簽tag值相似基量為式（1）。

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

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

算法一：兩個Web頁面DOM樹T1和T2頁面相似量計算

輸入：兩個Web頁面DOM樹T1和T2

輸出：T1相對于 T2的相似量 F（T1，T2）

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

步驟2.通過式（2）～（4）計算各個屬性的相似基量值λid、λname、λclass；

步驟3.設T1的當前根節(jié)點為N1，T2的當前根節(jié)點為N2，當前樹的相似量為F（T1，T2）=0 ；

步驟6.轉步驟3進行遞歸計算得出T1i相對于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）），轉步驟6；

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

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

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

其中當id值、name值相同時，Cid=Cname值為“1”，不相同時值為“0”；Cclass計算公式如下：

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

式（1～7）定義了節(jié)點之間的節(jié)點相似量及DOM樹之間的頁面相似量度量公式。為計算兩棵DOM樹之間的頁面相似量，我們在現(xiàn)有樹匹配算法［12］的基礎上，增加了對頁面屬性信息的度量，提出了改進的樹匹配算法，如算法一所示。

3.2 相似度定義

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

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

4 標記聚類算法

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

4.1 MC聚類算法基本思想

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

4.2 算法描述

標記聚類MC主要有以下五個步驟，算法流程如圖3所示。

圖3 MC算法流程

1）初始化兩個集合A、B，其中A是所有Web頁面的集合，B=Ф；聚類標記k=0；

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

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

4）判斷是否遍歷A中所有元素，如果是進行下一步，否則轉3）；

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

最終得到B集合即為聚類結果，B中每個元素均為二元組，表示W(wǎng)eb頁面及其所屬的類簇的標號。

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

5 實驗

為了驗證本文方法的有效性，我們提出了兩個研究問題如下：

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

2）標記聚類算法MC是否能在不影響聚類結果的前提下提高聚類效率？

5.1 實驗對象與環(huán)境配置

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

實驗一：分別使用簡單樹匹配和本文提出的改進樹匹配算法完成頁面相似性度量，聚類方法均采用同一凝聚層次聚類方法進行頁面聚類。

實驗二：相似性度量采用本文提出的改進樹匹配的算法，聚類方法分別使用凝聚層次聚類和本文提出的標記聚類進行比較。

5.2 實驗結果

5.2.1 相似度算法結果

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

從圖4可以看出，本文提出的改進樹匹配算法對于屬于不同類的頁面計算得到的相似度明顯小于簡單樹匹配算法的結果，而且均小于0.9，這說明本文的改進樹匹配算法區(qū)分不同類頁面的能力強于簡單樹匹配算法。

圖4 兩種算法的頁面相似度計算比較結果

表1 e107

表2 wordpress

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

5.2.2 聚類算法結果

為比較兩種不同的聚類算法的效率，采用相同的頁面相似性度量方法，即改進樹匹配算法，不同的頁面聚類算法對上述兩個Web應用進行了頁面聚類實驗。其中凝聚層次聚類HAC算法中類之間的相似度采用如式（9）進行計算：

兩種聚類算法對Web頁面聚類的實驗結果如表3和表4所示。

表3 e107聚類算法比較

表4 wordpress聚類算法比較

觀察上表可以明顯看出本文提出的標記聚類算法MC并沒有影響聚類的結果，但是卻明顯減少了聚類時間，提高了頁面聚類效率。具體來說，對于e107效率提升了3.4倍，而對于wordpress效率提升了5.6倍。因此，本文提出的標記聚類算法效率更高。

6 結語

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