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

楊金花

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

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

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

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

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

2Web文本挖掘

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

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

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

傳統(tǒng)的層次凝聚類算法思想是：對(duì)于給定的文檔集合D=｛d1，…，di，…，dn｝，層次聚類的過(guò)程如下：

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

2）計(jì)算 C 中的每個(gè)聚類對(duì)（ci，cj）之間的相似度 sim（ci， cj），

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

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

用偽語(yǔ)言來(lái)表述

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

4 改進(jìn)的層次凝聚算法

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

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

4.1 改進(jìn)后算法

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

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

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

4.2 算法分析

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

4.3 參數(shù)分析

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

4.4 改進(jìn)后的算法驗(yàn)證

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

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

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

5 結(jié)束語(yǔ)

由于Web數(shù)據(jù)挖掘是從海量級(jí)數(shù)據(jù)進(jìn)行挖掘的，它完成的是從大量的數(shù)據(jù)中挖掘用戶感興趣的信息類，使用傳統(tǒng)的層次凝聚類算法，實(shí)現(xiàn)起來(lái)存在運(yùn)算速度慢，占用的存儲(chǔ)空間大等問(wèn)題。為了提高挖掘的速度，減少計(jì)算時(shí)所占用的空間，本文提出了改進(jìn)后的層次凝聚類算法，并對(duì)相似度值的取法進(jìn)行了探索，給出了動(dòng)態(tài)改變相似度值參考公式。但該算法仍有許多不足之處，需進(jìn)一步完善改進(jìn)，有關(guān)參數(shù)a的取值以及相似度的初始值、循環(huán)多少次后相似值采用公式來(lái)計(jì)算等問(wèn)題，也有待于進(jì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í)與技術(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].計(jì)算機(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].計(jì)算機(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].計(jì)算機(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.