基于Web挖掘的層次凝聚類算法研究

楊金花

（西安鐵路職業技術學 陜西 西安 710014）

隨著網絡資源越來越豐富，它容納了海量的各種類型的原始數據，激增的數據背后隱藏著許多重要的信息，人們越來越多地關注如何從海量數據中提取有價值的信息。數據挖掘（Data Mining）是從大型數據庫或數據倉庫中提取人們感興趣的、隱含的、尚未被認識到的有用知識。由于Web本身的特性，使得Web上的信息查找比傳統的信息查找表現出更大的挑戰性。解決從Web上查找信息的一個途徑，就是將傳統的數據挖掘技術和Web結合起來，進行Web數據挖掘[1]。

1 Web數據挖掘的特點

數據挖掘是通過對大量數據的分析，尋找每個數據規律的技術，它挖掘的是數據庫中有模型的數據，更注重的是數據的精確性。Web數據挖掘不同于數據挖掘，它是指利用數據挖掘技術在Web數據中發現潛在的、有用的模式或信息，它更注重數據的模糊性，需要挖掘出來的是同一類的信息。傳統的數據庫都有一定的數據模型，或以此模型來具體描述。Web上的數據與傳統的數據庫中的數據不同[2]。Web是由文本，多媒體元素、超鏈接等內容組成。Web上的數據非常復雜，沒有特定的模型描述，每一站點的數據都各自獨立設計，并且數據本身具有自述性和動態可變性，從而是一種非完全結構化的數據。半結構化是形成了Web文本挖掘的特色。

Web上的大量數據是非結構化的、層次化的[3]，而其中80%以上的信息都是以文本的形式存在的、蘊含著巨大潛在價值的知識。人們迫切需要能夠從Web上快速、有效地發現這些有價值的知識。正是這些問題推動了Web文本挖掘技術的產生和發展。

2Web文本挖掘

Web文本挖掘是從Web文本和Web活動中發現、抽取用戶感興趣的、潛在的、有用模式和隱藏的信息的過程。Web文本挖掘為Web用戶深入使用Web資源開辟了新的渠道。Web文檔中的標記給文檔提供了額外的信息。借此可以提高Web文本挖掘的性能。Web文本挖掘可以使Web用戶較準確地找到所需要的資料，縮短搜索時間，提高Web文檔利用價值等。

3 傳統的層次凝聚算法

目前，在Web文本挖掘上常用的方法大致可分為層次凝聚法[4]和平面劃分法2種類型。文中主要研究層次凝聚類法。

傳統的層次凝聚類算法思想是：對于給定的文檔集合D=｛d1，…，di，…，dn｝，層次聚類的過程如下：

1）將D中的每一文檔di作為一個聚類中心ci=｛di｝，形成D 的一個聚類集合 C=｛c1，…，ci，…，cn｝；

2）計算 C 中的每個聚類對（ci，cj）之間的相似度 sim（ci， cj），

3）選取具有最大相似度的 2 個聚類（ci，cj）|max sim（ci，cj），將合并成一個新的聚類ck=ci∪cj，同時合并ci和cj的特征矢量，從而要構成了 D的一個新的聚類集合 C=｛c1，…，ck，…，cn-1｝；

4）重復上述步驟，根據所要產生聚類的數目，得到最終聚類結果。

用偽語言來表述

傳統的層次凝聚法[5]，每次需要計算兩兩類之間的相似度。假設有n個類，需要計算2個類之間的相似度，獲得n！/（2×（n-1）！）個相似度，接著比較這些相似度大小，將最大相似度的兩個類合并，計算合并后類的值，同時將刪除合并的一個類，類的個數變為n-1，第1次的聚類完成。接下來在n-1個類中再計算兩兩類的相似度， 需要計算 （n-1）！/（2×（n-3）！次， 獲得（n-1）！）/（2×（n-3）！個相似度，接著比較這些相似度，將相似度較大的兩個類合并，刪除一個合并類，類的個數變為n-2，第2次的聚類完成。按照前面所述如此執行下去，直到滿足條件—聚類的個數等于給定的個數為止。傳統的層次凝聚法，實現的是最大相似度的兩個類合并，雖然能夠比較精確地刻畫樣本點之間一些細微差別，但運算速度緩慢、時間復雜性較高，占用存儲空間大，不能承擔較大數據規模的樣本。由于Web文本的挖掘，需要挖掘的是某一方面的信息，也就是挖掘的是某個類。更進一步指出，就是Web文本的挖掘需要的是模糊挖掘，只要包含關鍵字就可以了。假設，在低層循環中，我們最初按照給定的相似度合并類，此時的相似度值比較小，進行粗略的合并。到高層循環時，使相似度為動態變化的，此時相似值逐漸變大，進行的是更精細的合并。如果兩兩類的相似度大于或等于給定的相似度就合并這兩個類，這樣就可以實現一次合并若干個類，從而提高合并速度，減小計算時所占有的存儲空間。

4 改進的層次凝聚算法

根據日常知識可以知道，對于Web數據挖掘，就是要求將某一類的文檔內容挖掘出來，對于挖掘出來的內容完全一樣的文檔，是沒有實際意義的。在實際Web數據挖掘中，如果相似度過大，挖掘出來的類就少，如果相似度過小，挖掘出來的類就多。所以需要設置一個合理的相似度，我們就可以挖掘出來若干個類。

目前，對于基于相似度的聚類算法的研究也不少，大多數是基于EM（Expectation-Maximization）算法，這種算法是一種含參數的潛在的概率模型，該模型描述了一個對象物體歸屬于某個聚類的可能性，但是這些聚類算法在時間和空間上花費太大了。文中提出一個相似度函數sim，且0≤sim≤1[6]。該算法與其他的一些聚類算法相似。算法開始精選出初始的簇，并對簇進行循環步驟以提高聚類效果。這種算法事先定義好了相似度值，減少了迭代次數，提高了運算速度，減少了占有的空間。

4.1 改進后算法

由于考慮Web數據挖掘是在海量級的數據中進行的，要求挖掘的是類數據。在最初的合并中，可以將相似度設計為sim，而在較高層次循環時的聚類算法改為一種可變的相似度的層次凝聚類算法，這樣做，可以加快合并的速度，而且能挖掘出大量的同一類數據。設計公式 sim=sim+a（minsim+maxsim）。

基本思想如下：每一個對象仍單獨成為一類，按給定的相似度合并。重復此操作，待循環進行到指定的次數后，重新計算相似度sim=sim+a（minsim+maxsim），進行下一層次的合并，重復以上步驟，直至滿足結束條件。

假設給定包含 n 個對象的數據集合 D=｛d1，…，di，…，dn｝

4.2 算法分析

在傳統的層次凝聚類法中，將n個對象最終合并為一個類中需要迭代n次，時間復雜性為O（n2），在改進的算法中，假定平均每次合并t個對象，則構迭代次數為n/t，其時間復雜性為 O（n2/t），當 t>1 時，O（n2/t）<

4.3 參數分析

在改進的算法中，最大相似度sim的選取直接影響到聚類結果的好壞。相似度值sim過大，就會出現所產生的聚類中的數據過少，有可能將有用信息丟掉；相似度值sim過小，就會出現所產生的聚類中的數據過多，同時產生了有可能是無關的信息。同時又存在相似度值越小，聚類的速度則越慢。從理論上來說要求0≤sim≤1，因此，試給出一個計算sim公式：sim=sim+a （minsim+maxsim），maxsim 為 最大相似 度 ，minsim為最小相似度，其中a為比例系數，其取值范圍在0～0.1之間，sim為上次聚類的相似值。有關a的計算公式，還有待于更進一步的研究。

4.4 改進后的算法驗證

對3組樣本集合D1，D2，D3分別使用傳統的層次凝聚算法和改進后的層次凝聚算法進行聚類，其結果比較如表1所示。

實驗結果證明改進的層次凝聚類算法與傳統的層次凝聚類算法的結果是基本相同的，而改進的層次凝聚類算法的速度卻遠遠高于傳統的算法，這表明改進的算法是可行而且高效的。

表1 傳統的層次凝聚類算法與改進的層次凝聚類算法各項指標對照表Tab.1 Traditional agglomerative hierarchical clustering algorithm and the improved hierarchical agglomerative algorithms each index table

5 結束語

由于Web數據挖掘是從海量級數據進行挖掘的，它完成的是從大量的數據中挖掘用戶感興趣的信息類，使用傳統的層次凝聚類算法，實現起來存在運算速度慢，占用的存儲空間大等問題。為了提高挖掘的速度，減少計算時所占用的空間，本文提出了改進后的層次凝聚類算法，并對相似度值的取法進行了探索，給出了動態改變相似度值參考公式。但該算法仍有許多不足之處，需進一步完善改進，有關參數a的取值以及相似度的初始值、循環多少次后相似值采用公式來計算等問題，也有待于進一步的研究，希望找出更合適的取值。

[1]曹聰聰，康耀紅.Web數據挖掘研究[J].現代電子技術，2007（4）：92-97.CAO Cong-cong，KANG Yao-hong.Research on Web data mining[J].Modern Electronic Technique，2007（4）：92-97.

[2]鞏固，張虹.Web數據挖掘分析[J].電腦知識與技術，2006（6）：18-19.GONG Gu，ZHANG Hong.AnalysisofWebMining[J].Computer Knowledge and Technology，2006（6）：18-19.

[3]陳曉紅，秦楊.基于Web數據挖掘高效關聯規則研究[J].計算機工程與科學，2005，27（11）：48-51.CHEN Xiao-hong，QIN Yang.Research on the effective association rules for Web-based data mining[J].Computer Engineering&Science，2005，27（11）：48-51.

[4]郝洪星，朱玉全，陳耿，等.基于劃分和層次的混合聚類算法[J].計算機應用研究，2011，1（28）：51-53.HAO Hong-xing，ZHU Yu-quan，CHEN Geng，et al.Hybrid dynamin clustering algorithm based on partition and hierarchical clustering[J]Application Research of Computers，2011， 1（28）：51-53.

[5]魏桂英，鄭玄軒.層次聚類方法的CURE算法研究[J].科技和產業，2005，5（11）：22-24.WEI Gui-ying，ZHEN Xuan-xuan.Hierarchical clustering method CURE algorithm[J].Science Technology and Industry，2005，5（11）：22-24.

[6]姜亞莉，關澤群.用于Web文檔聚類的基于相似度的軟聚類算法[J].計算機工程，2006（2）：202-207.JIANG Ya-li，GUAN Ze-qun.A similarity-based Soft clustering algorithm for Web documents[J].Computer Engineering，2006（2）：202-207.

[7]劉興波.凝聚型層次聚類算法的研究 [J].科技信息，2008（11）：202.LIU Xing-bo.Condensed type hierarchical clustering algorithm[J].Science and Technology Information，2008（11）：202.