基于模糊集的Web文本最大支撐樹聚類算法

〔摘 要〕當今信息社會，Internet上的信息資源雜亂繁多，用戶很難準確地獲得所需的信息。對此，本文提出根據特征詞在html網頁中的title、keywords、description標簽的位置來計算各Web文本內容之間的相關度，對Web文檔進行模糊聚類的算法，這種基于模糊集的Web文本最大支撐樹聚類算法改善了文本聚類的時間和空間的復雜度，減少了文本處理的維度，提高了聚類的速度和精度，從而提高了用戶對信息資源獲取的方便性。

〔關鍵詞〕模糊聚類；Web文本；html標簽；最大支撐樹

ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００８－０８２１．２０１１．１１．００５

〔中圖分類號〕ＴＰ２７４ 〔文獻標識碼〕Ａ 〔文章編號〕１００８－０８２１（２０１１）１１－００２１－０５

Maximum Support Tree Clustering Algorithm of Web Text Based on Fuzzy SetsMao Taitian１ Zou Kai１ Mao Jing１ Zhou Jun２

（１．Public Administration School，Xiangtan University，Xiangtan 411105，China；

２．The Limited Liability Company of Machinery Manufacturing of Xikuangshan Lengshuijiang，

Lengshuijian 417500，China）

〔Ａｂｓｔｒａｃｔ〕In the information society，the information resource in the Internet is variety and disorderly and the user is difficult to acquire information accurately.So this paper analyzed the web text based on the method of fuzzy cluster by calculating the correlation among the content of the web text，according to the placement of the check tags which“title”，“keywords”and“description”contained in HTML pages.The Maximum Support Tree Clustering Algorithm of Web Text based on Fuzzy Sets improved the time-space complexity in text clustering，reduced the text processing dimensions，sped up the clustering，and improved the precision.Consequently，it increased user’s accessibility to information resources.

〔Ｋｅｙ ｗｏｒｄｓ〕the fuzzy clustering;web text;html label;the maximum support tree

信息時代，信息資源在經濟社會發展中扮演著愈益重要的角色。網絡的迅猛發展，使得WWW(World Wide Web)已經成為一個巨大的、蘊含著具有潛在價值知識的分布式信息空間。Internet是信息資源的一個巨大的承載體，Web迅猛發展的同時，信息爆炸，將成為我們面臨的新問題。在這龐大的信息庫中，用戶從搜索引擎上得到的信息雜亂無章，用戶檢索到自己需要的信息也將越來越困難［１］。對網絡信息資源進行更好的分類，使用戶快速簡單的從Internet上檢索到自己所需要的信息，將成為信息時代的一個重要的研究方向［２］。

Web文本聚類就是將Web文本集分成若干稱為聚類簇的子集，聚類簇內的文本間具有較大的相似性，而聚類簇間的文本的相似性較小，從而使我們能夠將觀察到文本的內容組織成不同的類［３］。文本聚類的一般方法有單遍聚類、逆中心距聚類、自上而下精分法、密度 測試法、圖論分析法。但這些方法不能完全套用Internet網頁上的文本，對此本文將通過We b文本的一些特殊結構，突出重點特征詞，來改善算法實現的時間和空間的復雜度，減少文 本處理的維度，提高聚類的速度和精度［４］。

１ Web文本特殊結構說明

Web文本的信息內容大部分是以網頁的形式存于Internet之上，本文將通過html網頁的特殊結構對Web文本進行模糊聚類。

一般而言，html的主體結構如下［５］：

∥為方便書寫簡稱為title標簽

∥為方便書寫簡稱為keywords標簽

∥為方便書寫簡稱為description標簽

HTML結構包括頭部、主體兩大部分，其中頭部描述瀏覽器所需的信息，而主體則包含所要說明的具體內容。在Web文本的最外層，Web文本中的所有文本和html標簽都包含在其中；是HTML文本的頭部標簽，標簽中的信息內容顯示在瀏覽器窗口中；是嵌套在頭部標簽中的，標簽之間的文本是Web文本標題，它被顯示在瀏覽器窗口的標題欄，該部分是反映文章主題的一個最重要部分；語句，網頁文檔中是直接反映文本內容的一個重要標簽，往往在title標簽的下面，本文為方便書寫簡稱為keywords標簽；語句，也是對文本的概要描述，簡稱為description標簽；標簽之間的文本是正文，是在瀏覽器要顯示的頁面內容。

２ Web文本的最大支撐樹聚類算法

本文借助于傳統的文本表示法，采用基于特征詞的多維向量空間模型VSM［６］來對Web文本進行模糊表示：

設有集合Ｔ＝｛Ｔ１，Ｔ２，…，Ｔｎ｝，其中Ｔ是待聚類的Web文本的集合，Ｔｉ＝｛Ｘｉ１，…，Ｘｉｍ｝是文本ｉ的ｍ維特征向量，１ｉｎ，特征向量Ｘｉｊ是從文本中抽取的、能反映文本主題內容的一組特征詞。在Internet的Web網頁上，我們可以通過獲得Web文本的title、keywords、description標簽中的一些信息來確定文本的主旨和大意，而不一定需要查看網頁上繁多的正文。所以本文從title、keywords、description標簽中的特征詞著手，來對Web文本進行聚類。

２.１ 提取詞庫

將所有對象里的特征詞抽出，組成一個詞庫Ｘ，如下表示：

Ｘ＝｛Ｘ１１，Ｘ１２，…｝Ｕ…Ｕ｛Ｘｉ１，Ｘｉ２，…｝Ｕ…＝｛Ｘ′１，Ｘ′２，…，Ｘ′ｍ｝（1）

Ｘｉｊ是Web文本ｉ第ｊ個的特征詞，詞庫X共有m個特征詞。

２.２ 抽取特征詞

根據詞庫Ｘ，從Web文本的title、keywords、description標簽中抽取特征詞ｋ∈Ｘ：

ｋｉ＝｛｛Ｔｉ的ｔｉｔｌｅ｝ＩＸ｝Ｕ｛｛Ｔｉ的ｋｅｙｗｏｒｄｓ｝ＩＸ｝Ｕ｛｛Ｔｉ的ｄｅｓｃｒｉｐｔｉｏｎ｝ＩＸ｝（2）

２.３ 特征詞權重計算

在向量空間模型中，針對關鍵詞所在的位置我們不能一味的套用只考慮了Web文本的長度、數量、詞頻等因素的布爾權重(Boolean weighting)、TFIDF［７］型權重、基于熵概念的權重(Entropy weighting)、Okapi權重等計算方法［８］。不同位置的詞在分類中所起的作用是有差別的，特別在本文的算法中差別尤為明顯。我們對上述的權重計算方法進行改動，對于特征詞在title、keywords、description三類標簽中的權重的計算，我們用到下列公式：

ｋｉｊ＝∑３ｋ＝１ａｉｋ（3）

其中，ｋｉｊ為特征詞ｉ的權重，ａｉｋ為特征詞ｉ在第ｋ個標簽中的權重，ｃｋ為三類標簽的重要程度系數。

再求解ａｉｋ，利用公式［９］

ａｉｋ＝ｌｎ（ｃｋｔｆｋｉ）（4）

ｔｆｋｉ為特征詞出現在各類標簽的頻數，根據本文在不考慮正文的前提下，求解單個特征詞在title、keywords、description三類標簽中的局部權重，所以ｔｆｋｉ值為1。

最終對特征詞在三類不同標簽中的權重計算公式可表示如下：

ｋｉｊ＝∑３ｋ＝１ｌｎｃｋ（6）

為了區分這三類標簽的重要程度，根據網絡上搜集的相關信息和對SEO（搜索引擎優化）的調查數據分析，對于title、keyword、description標簽的重要程度系數如下［１０］：

ｃｋ＝１０ ｋ＝１（ｔｉｌｔｅ）

５ ? ｋ＝２（ｋｅｙｗｏｒｄ）

２ ? ｋ＝３（ｄｅｓｃｒｉｐｔｉｏｎ）（7）

２.４ 構造Web文本權重矩陣

根據(6)和（7）我們可以得到如下結果：

當第ｉ個Web文本中的第ｊ個特征詞都沒有出現在title、keywords、description標簽中時，ｋｉｊ＝０；

當第ｉ個Web文本中的第ｊ個特征詞出現在description標簽中，沒有出現在title、keywords標簽中時，ｋｉｊ=0.693；

當第ｉ個Web文本中的第ｊ特征詞出現在keywords標簽中，沒有出現在title、description標簽中時，ｋｉｊ=1.386；

當第ｉ個Web文本中的第ｊ個特征詞出現在keywords標簽中和標description吧簽中，沒出現在title標簽中時，ｋｉｊ=2.079；

當第ｉ個Web文本中的第ｊ個特征詞出現在title標簽中，沒有出現在description、keywords標簽中時，ｋｉｊ=2.303；

當第ｉ個Web文本中的第ｊ個特征詞出現在title標簽中和description標簽中，沒有出現在keywords標簽中時，ｋｉｊ=2.996；

當第ｉ個Web文本中的第ｊ個特征詞出現在title標簽中和keywords標簽中，沒有出現在description標簽中時，ｋｉｊ=3.689；

當第ｉ個Web文本中的第ｊ個特征詞出現在title、keywords和description標簽中時，ｋｉｊ=4.382。

從而得到Web文本權重矩陣：

Ｔ＝［ｋｉｊ］ｎ×ｍ， １ｉｎ， １ｊｍ（8）

ｎ是文本數，ｍ是詞條數，由于詞條和Web文本的數量都很大，而單個文本中出現的詞條非常有限，再加上在兩篇Web文本出現相同的特征詞的概率很小，因此Ｔ一般為稀疏矩陣。

２.５ 構造模糊相似矩陣

模糊相似矩陣Ｒ是描述各個待聚類Web文本對象之間的相似性的統計量，根據Ｔ＝［Ｘｉｊ］生成模糊相似關系：

Ｒ＝［ｒｉｊ］ｎ×ｎ， ０ｒｉｊ１， ｉ、ｊ＝１，２，…，ｎ（9）

ｒｉｊ表示待聚類Web文本ｉ和Ｔｊ之間的相似程度。在計算模糊相似矩陣時，常用夾角余弦法、數量積法、相關系數法、指數相似系數法、最大最小法、算術平均最小法、幾何平均最小值法、絕對值指數法、絕對值減數法等方法來計算，因模糊矩陣Ｒ為稀疏矩陣，本文采用比較簡單的最大最小值法計算模糊相似矩陣的值：

ｒｉｊ＝∑ｓｈ＝１ｍｉｎ（ｋｉｈ，ｋｊｈ）∑ｓｈ＝１ｍａｘ（ｘｉｈ，ｘｊｈ）（10）

２.６ 構建模糊最大支撐樹并進行聚類分析

第一步，建立待聚類對象集上的模糊相似關系，構造模糊圖。

（1）先按上述計算方法建立待聚類對象的模糊相似矩陣Ｒ，并計算各個分類對象之間的相似性統計量ｒｉｊ，ｉ，ｊ＝１，２，…，ｎ。

（2）將Ｒ表示成無向圖Ｇ＝｛Ｔ，Ｄ｝，Ｔ為圖的各個頂點，Ｄ為連接兩頂點ｉ、ｊ的邊，權值為ｒｉｊ。

第二步，構造模糊圖Ｇ上的最大模糊支撐樹［１１］：

（1）找出圖Ｇ中最大權值的邊ｒｉｊ；

（2）將權值為ｒｉｊ所連接的新結點放入集合Ｔ中，并保留權值ｒｉｊ所在的邊，若Ｔ中已含有所有ｎ個結點時，轉（4）；

（3）檢查已有的Ｔ的每一個結點與Ｔ外的結點組成的邊的權值，找出其中最大權值ｒｉｊ，轉（2）；

（4）結束，此時Ｔ中的所有的頂點和所保留的邊連成我們所需要的最大樹Ｔｍａｘ。

２.７ 聚類分析

選擇一個閾值ｒ做截集，將最大樹中小于ｒ的邊斷開，使相連的各結點構成一類，單個結點也作為一類，當ｒ由0上升到1時，所得的分類數目由少變多，分類由粗變細，各結點所代表的聚類對象歸并，形成一個動態聚類譜系圖。

３ 應用實例

３.１ 選取樣本

從Internet上面保存6個Web文本網頁，在百度所搜引擎里輸入“房價”關鍵詞，在所搜索到得結果中，隨機選取6個網頁：“重慶出臺多項樓市新政 業內人士熱議新政影響”（Ｔ１）、“大興線二手房回到原點 業主囤房一年沒賺多少”（Ｔ２）、“國務院關于堅決遏制部分城市房價過快上漲的通知”（Ｔ３）、“滬樓市房價‘漲’聲再起帶看上升 買還是等？”（Ｔ４）、“高房價下近半數80后購房置業選擇50～60平米的小戶型”（Ｔ５）、“北京村民因拆遷一夜暴富，專家稱高補償催漲房價”（Ｔ６），并從6個網頁中的title、keywords、description標簽中挑選出特征詞如表１所示：

表１ 各標簽中的特征詞

titlekeywordsdescriptionT1樓市新政（Ｘ１）、新政影響（Ｘ２）房價（Ｘ３）、計價（Ｘ４）、新政（Ｘ５）樓市新政（Ｘ１）、新政影響（Ｘ２）T2二手房（Ｘ６）、業主囤房（Ｘ７）二手房（Ｘ６）、業主囤房（Ｘ７）二手房（Ｘ６）、業主囤房（Ｘ７）T3國務院（Ｘ８）、房價（Ｘ３）、上漲（Ｘ９）國務院（Ｘ８）、房價（Ｘ３）、上漲（Ｘ９）國務院（Ｘ８）、房價（Ｘ３）、二手房（Ｘ６）、房貸（Ｘ１０）T4滬樓市房（Ｘ１１）、上漲（Ｘ９）房價（Ｘ３）、上漲（Ｘ９）房價下跌（Ｘ１２）、房價（Ｘ３）T5房價（Ｘ３）、小戶型（Ｘ１３）房價（Ｘ３）、小戶型（Ｘ１３）置業問題（Ｘ１４）、購房主力（Ｘ１５）T6拆遷暴富（Ｘ１６）、高補償（Ｘ１７）、房價（Ｘ３）拆遷暴富（Ｘ１６）、房價會（Ｘ１８）、樓面價（Ｘ１９）Φ

Ｔ＝｛Ｔ１，Ｔ２，Ｔ３，Ｔ４，Ｔ５，Ｔ６｝，Ｔｉ為第ｉ個Web文本，對這6個Web文本的title，keywords，description標簽中的特征詞進行聚類分析：

Ｔ１中的特征詞：｛Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５｝；

Ｔ２中的特征詞：｛Ｘ６，Ｘ７｝；

Ｔ３中的特征詞：｛Ｘ３，Ｘ６，Ｘ８，Ｘ９，Ｘ１０｝；

Ｔ４中的特征詞：｛Ｘ３，Ｘ９，Ｘ１１，Ｘ１２｝；

Ｔ５中的特征詞：｛Ｘ３，Ｘ１３，Ｘ１４，Ｘ１５｝；

Ｔ６中的特征詞：｛Ｘ３，Ｘ１６，Ｘ１７，Ｘ１８，Ｘ１９｝。

３.２ 提取樣本詞庫

提取樣本詞庫，根據公式（1）得到如下詞庫：

Ｘ＝｛Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５，Ｘ６，…，Ｘ１８，Ｘ１９｝

根據詞庫X，從各Web文本的title，keywords，description標簽中抽出特征詞：

Ｔ１：title標簽中的特征詞｛Ｘ１，Ｘ２｝，keywords標簽中的特征詞｛Ｘ３，Ｘ４，Ｘ５｝，description標簽中的特征詞｛Ｘ１，Ｘ２｝；

Ｔ２：title標簽中的特征詞｛Ｘ６，Ｘ７｝，keywords標簽中的特征詞｛Ｘ６，Ｘ７｝，description標簽中的特征詞｛Ｘ６，Ｘ７｝。

Ｔ３：title標簽中的特征詞｛Ｘ３，Ｘ８，Ｘ９｝，keywords標簽中的特征詞｛Ｘ３，Ｘ８，Ｘ９｝，description標簽中的特征詞｛Ｘ３，Ｘ６，Ｘ８，Ｘ１０｝。

Ｔ４：title標簽中的特征詞｛Ｘ９，Ｘ１１｝，keywords標簽中的特征詞｛Ｘ３，Ｘ９｝，description標簽中的特征詞｛Ｘ３，Ｘ１２｝。

Ｔ５：title標簽中的特征詞｛Ｘ３，Ｘ１３｝，keywords標簽中的特征詞｛Ｘ３，Ｘ１３｝，description標簽中的特征詞｛Ｘ１４，Ｘ１５｝。

Ｔ６：title標簽中的特征詞｛Ｘ３，Ｘ１６，Ｘ１７｝，keywords標簽中的特征詞｛Ｘ１６，Ｘ１８，Ｘ１９｝，description標簽中的特征詞｛Φ｝。

３.３ 構造模糊矩陣

依據各個特征詞在各個Web文本中出現的位置求出其位置加權值，構造Web文本的特征向量矩陣：Ｔ＝2.9962.9961.3861.3861.38600000000000000

000004.3824.382000000000000

004.382000.69304.3822.3030.693000000000

003.689000003.68902.3030.6930000000

003.6890000000003.6890.6930.6930000

002.3030000000000003.6892.3031.3861.286

使用公式（10）計算Ｔ的模糊相似矩陣Ｒ：

Ｒ＝100.070.070.080.07

010.03000

0.070.0310.360.210.12

0.0700.3610.240.12

0.0800.210.2410.13

0.07000.120.131

３.４ 繪制模糊圖

在建立待聚類對象集上的模糊相似關系矩陣Ｒ后，將Ｒ表示成模糊圖Ｇ＝｛Ｔ，Ｄ｝如圖１所示。

圖１ 模糊圖Ｇ

３.５ 構造最大支撐樹

根據做最大支撐樹的方法，做模糊圖Ｇ的一個最大支撐樹如圖２所示。

３.６ 劃分截集

分別選擇ｒ的值為：0、0.03、0.07、0.13、0.24、0.36、1對最大支撐樹做截集，將最大樹中小于ｒ的邊斷開，使相連的各結點構成一類。

圖２ 最大支撐樹

ｒ=0；分成一類｛Ｔ１，Ｔ２，Ｔ３，Ｔ４，Ｔ５，Ｔ６｝；

ｒ=0.03；分成一類｛Ｔ１，Ｔ２，Ｔ３，Ｔ４，Ｔ５，Ｔ６｝；

ｒ=0.07；分成兩類｛Ｔ１，Ｔ３，Ｔ４，Ｔ５，Ｔ６｝、｛Ｔ２｝；

ｒ=0.13；分成三類｛Ｔ１｝、｛Ｔ２｝、｛Ｔ３，Ｔ４，Ｔ５，Ｔ６｝；

ｒ=0.24；分成四類｛Ｔ１｝、｛Ｔ２｝、｛Ｔ３，Ｔ４，Ｔ５｝、｛Ｔ６｝；

ｒ=0.36；分成五類｛Ｔ１｝、｛Ｔ２｝、｛Ｔ３，Ｔ４｝、｛Ｔ５｝、｛Ｔ６｝；

ｒ=1；分成六類｛Ｔ１｝、｛Ｔ２｝、｛Ｔ３｝、｛Ｔ４｝、｛Ｔ５｝、｛Ｔ６｝。

３.７ 分 析

由上述模糊聚類可已看出，當ｒ由1下降到0時，對于上面6個網頁的分類由細變粗，ｒ=0.36時，Ｔ３，Ｔ４聚為一類，其他各自成一類，而Ｔ３，Ｔ４都涉及到“房價上漲”問題，比較體現文本內容主題，當ｒ=0.24；Ｔ１，Ｔ２，Ｔ６各自分別聚為一類，其他Web文檔聚為一類，Ｔ３，Ｔ４，Ｔ５聚為一類，總體而言這4個Web文本都談到了“房價”問題，而Ｔ１，Ｔ２，Ｔ６基本上沒有涉及的“房價”的信息，并不是文本內容所要反映的主題，即“房價”在反應內容主題所占的權重非常小，由此可見，在對Web文本進行聚時，可以根據具體ｒ的值來進行模糊聚類。

４ 不同算法的性能對比

我們從百度搜索引擎中輸入“經濟”，搜索引擎找到的相關搜索結果約100 000 000個，我們抽取前10個頁面的網頁（每個頁面均有12條結果），得到約1 200個關于經濟的網頁，再對這1 200個網頁進行篩選，去除視頻，圖片及網站類信息的網頁，得到1 025個文本網頁，對這1 025個Web文本的聚類。我們將本文所采用的算法與TFIDF、TFC的計算方法進行對比， 時間性能如表２所示：

表２ 算法的時間性能

算 法特征詞總數

（個）分詞所用時間

（ms）計算特征詞時間

（ms）總計用時

（ms）平均每個特征詞所用時間

（ms）本文算法2 97440 080108 222148 30249TFIDF26 502501 2042 347 1542 848 358107TFC27 024410 2082 800 9623 211 170119

從表２我們可以看出，在對Web文本網頁模糊聚類時，本文所采用的通過特殊標簽抽取特征詞的方法，在時間性能上明顯優于TFIDF和TFC算法。

在聚類精度上，通過確定不同的閾值ｒ確定Web文本的聚類種數，本文算法和TFIDF、TFC算法聚類情況對比如圖３所示，從圖中我們可以看到，本文算法的聚類種數要略多于TFIDF和TFC的聚類種數，即本文算法比原來的聚類算法在聚類的精度上有一定的提高。

圖３ 本文算法和TFIDF、TFC算法聚類情況

５ 結束語

本文提出的Web文檔的特征詞提取方法，不需要對文檔進行分詞，充分利用了網頁Web文本中的title、keywords、description等標簽中的特征詞對整個Web文本進行歸納。該Web文本聚類算法，充分利用html網頁文本的特殊結構，避免對文本聚類的時間和空間的高復雜度，文本處理的高維度，減少了文本特征維數；在Web文本的title、keywords、description標簽中抽取特征詞，通過調查分析，計算特征詞的權重，從而確定具體的閾值來對Web文本進行模糊分類，而不需要通過閱讀文本的全文后來對Web文本進行分類，在一定程度上提高了聚類的速度；準確定位到title、keywords、description標簽中詞，提高聚類精度，一般網頁文本上的內容雜亂繁多，在體現文本主題內容時，往往穿插一些與文本無關聯的內容，增加了文本分類難度，該聚類算法抽取html中的三類標簽進行分析，有效的避免了網頁內容雜亂的問題，提高聚類的精度。

但是該算法在某些地方也存在著一些不足，比如說對Web文本的聚類限定在了包含有title、keywords、description標簽的網頁文本中，對于Internet上的信息資源絕不僅僅限于此，它還包含有基于圖片、視頻等方面的信息資源；另一方面，對于標簽title、keywords、description中的特征詞進行查閱時，需要查看Web文本的源碼。

參考文獻

［１］Linghui Gong，Jianping Zeng，Shiyong Zhang.Text stream clustering algorithm based on adaptive feature selection［Ｊ］.Expert Systems with Applications，2011，(38):1393-1399.

［２］孟海濤.基于模糊聚類的學術期刊數據挖掘算法［Ｊ］.鹽城商學院學報，2006，19(4):68-70.

［３］彭曙蓉，王耀南.針對小文本的Web數據挖掘技術及其應用［Ｊ］.微計算機信息，2006，22(7-3):203-205.

［４］Trotman，Andrew.Choosing document structure weights［Ｊ］.Information Processing and Management，2005，(2):243-264.

［５］隋麗萍，徐承韜，李瑞芳.基于HTML結構的Web文本主題挖掘研究［Ｊ］.算法研究，2007，(1):47-50.

［６］孟海濤.基于模糊聚類的學術期刊數據挖掘算法［Ｊ］.鹽城商學院學報，2006，19(4):68-70.

［７］譚穎.文本挖掘中的聚類算法研究［Ｄ］：［碩士學位論文］.吉林大學，2009.

［８］李清峰，周偉林，何靜，等.一種基于模糊聚類的文本挖掘新方法［Ｊ］.計算機應用研究，2009，26(12):4453-4456.

［９］孫雙，賀睴等.一種改進的Web文檔關鍵詞權重計算方法［Ｊ］.上海大學學報：英文版，2008，12(3):235-239.

［１０］許建潮，胡明.中文Web文本的特征獲取與分類［Ｊ］.計算機工程，2005，(8)：24-25.

［１１］高新波．模糊聚類分析及其應用［Ｍ］.西安:西安電子科技大學出版社，2004．1.