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

楊金花

（西安鐵路職業(yè)技術(shù)學(xué) 陜西 西安 710014）

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

1 Web數(shù)據(jù)挖掘的特點

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

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

2Web文本挖掘

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

3 傳統(tǒng)的層次凝聚算法

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

傳統(tǒng)的層次凝聚類算法思想是：對于給定的文檔集合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的特征矢量，從而要構(gòu)成了 D的一個新的聚類集合 C=｛c1，…，ck，…，cn-1｝；

4）重復(fù)上述步驟，根據(jù)所要產(chǎn)生聚類的數(shù)目，得到最終聚類結(jié)果。

用偽語言來表述

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

4 改進的層次凝聚算法

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

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

4.1 改進后算法

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

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

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

4.2 算法分析

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

4.3 參數(shù)分析

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

4.4 改進后的算法驗證

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

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

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

5 結(jié)束語

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

[1]曹聰聰，康耀紅.Web數(shù)據(jù)挖掘研究[J].現(xiàn)代電子技術(shù)，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數(shù)據(jù)挖掘分析[J].電腦知識與技術(shù)，2006（6）：18-19.GONG Gu，ZHANG Hong.AnalysisofWebMining[J].Computer Knowledge and Technology，2006（6）：18-19.

[3]陳曉紅，秦楊.基于Web數(shù)據(jù)挖掘高效關(guān)聯(lián)規(guī)則研究[J].計算機工程與科學(xué)，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].計算機應(yīng)用研究，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].科技和產(chǎn)業(yè)，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]姜亞莉，關(guān)澤群.用于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.