聚類算法的改進的研究

薄文彥 付文蘭 張鳳英

1山西大同大學教育科學與技術學院 山西 037009 2內(nèi)蒙古工業(yè)大學信息工程學院 內(nèi)蒙古 010051

0 引言

Web文本挖掘作為 Web數(shù)據(jù)挖掘的一個重要分支，可以對文檔集合的內(nèi)容進行分類、聚類、關聯(lián)分析等。聚類是知識發(fā)現(xiàn)的重要工具，它是一種無指導的學習，能夠從海量的數(shù)據(jù)中分析并挖掘出人們需要的東西，已經(jīng)被廣泛應用到信息管理、搜索引擎、推薦系統(tǒng)等多個領域。

1 類間距離

聚類就是按照對象的類間距離將距離近的放在一類，距離遠的放在一類。聚類時常用的類間距離公式如下：

Single linkage(單連通)：

Complete linkage(完全連通)：

Average group(平均連通)：

Centroid distance(質(zhì)心距離)：

2 層次聚類算法

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

根據(jù)結(jié)果的生成順序，層次聚類可以分為兩類：分裂的層次聚類、凝聚的層次聚類。大部分層次聚類都屬于后者，它先把每個對象看做一個類，然后將距離最近的兩個類合并，直到所有對象都在一個類中，或者達到預定的停止條件。

下面舉個例子來理解一下層次聚類算法的執(zhí)行過程。假設有8個對象，每個對象有兩個(也可以是多個)屬性1x、2x：A(1,1)、B(3,4)、C(1.5,1.5)、D(2,3)、E(4,4)、F(3,3.5)、G(5，5)、H(5,3.5)。我們選用歐幾里得距離計算對象之間的初始化距離矩陣，結(jié)果如表1所示。

表1 初始化距離矩陣

我們選用公式1，找到距離的最小值dB→F= 0 .50，然后將 B 、F歸為一類(B,F) ，重新計算距離矩陣。經(jīng)過一系列地合并、計算距離矩陣，最后我們得到聚類的層次為((((((B,F),E),D),H),G) ,(A,C) ) ，如圖1所示。

圖1 凝聚層次聚類算法結(jié)果

分析上面的計算過程，第一次合并的是距離最小的兩個類，重新計算該類與其他類之間的距離時我們選擇的是公式1，例如：d((B,F),E)→D= m in(dBD,dFD,dED)，其中dBD、dFD和dED都是從初始距離矩陣中得到的，即新的距離矩陣的值都來源于初始距離矩陣。第二次迭代時是從新的距離矩陣中取的最小值，那么這個最小值應該是初始距離矩陣中的次小值。依此類推，直到所有的對象合并完為止。

2.2 改進后的層次聚類算法

在上面的例子中可以看出，合并過程中每次迭代都要重新計算類間距離，比較浪費時間，我們發(fā)現(xiàn)合并是按照初始距離矩陣從小到大的順序進行的，如果我們把初始距離矩陣中的元素用線性結(jié)構(gòu)存儲起來，對其進行從小到大的排序，那么合并類時只要順序遍歷線性結(jié)構(gòu)就行了，這樣就提高了層次聚類的速度。具體描述如下：

(1) 將給定數(shù)據(jù)中的每個對象看做一類，計算各個類之間的距離dij，將距離存儲在一維數(shù)組中。

(2) 對一維數(shù)組進行升序排列。

(3) 對于數(shù)組中的當前元素dij(即對象xi與xj之間的距離)，可以分為三種情況：①如果xi∈Cm，xj∈Cn，則Ck=Cm∪Cn。②如果xi∈Cm，xj沒有合并到類中，則Cm=Cm∪xj。 ③ 如 果xi、xj都 沒 有 合 并到類中，則Ck=Ci∪xj。

(4) 重復步驟(3)，直到數(shù)組中所有的元素處理完畢。

文獻證明了改進后的層次聚類算法的運行速度提高了近3倍，而聚類的結(jié)果不受影響。

3 k-means算法

3.1 傳統(tǒng)k-means聚類算法

k-means算法是一種應用最廣泛的劃分算法，它的聚類結(jié)果是平面的，一般用不相交的集合來表示。k-means聚類算法的基本思想：給定n個數(shù)據(jù)，隨機地選擇k個對象作為初始聚類中心，計算各個對象到聚類中心的聚類，將剩下的對象分配到聚類最近的類中，然后重新計算聚類中心，不斷重復這個過程，直到所有的聚類不再發(fā)生變化為止。

下面舉個例子來理解一下k-means算法的執(zhí)行過程。假設有6個對象，每個對象有兩個(也可以是多個)屬性x1、x2：A(1,1)、B(2,1)、C(3,4)、D(4,3)、E(2,2)、F(5,4)，我們的目標是將它們歸為兩類即K=2。選用A、B作為初始聚類中心，則C1 = ( 1 ,1)，C2 = ( 2 ,1)，選用歐幾里得距離計算距離矩陣，如表2所示。

表2 第一次迭代時的距離矩陣

我們根據(jù)公式 1，將對象劃分到距離最近的那個類中，即C1 = (A)，C2 =(B,C,D,E,F)，然后重新計算聚類中心，采用各個對象的平均值作為新的聚類中心，則C1 = ( 1 ,1)，再計算各個對象到新的聚類中心的距離。經(jīng)過一系列地劃分、計算聚類中心，最后得到的聚類結(jié)果為：C1 = (A,B,E)，C2 = (C,D,F)，如圖2所示。

圖2 k-means聚類算法結(jié)果

在k-means算法執(zhí)行過程中，每次迭代都把數(shù)據(jù)分配到距離最近的類中，新的分類產(chǎn)生后，需要計算新的聚類中心，這個過程的時間復雜度為 ( )Ond，則該算法總的時間復雜度為 ( )Onkd，其中d是對象的維數(shù)，k是指定的聚類個數(shù)，n是數(shù)據(jù)對象的總個數(shù)。當數(shù)據(jù)量比較大時，算法的時間開銷是非常大的。

3.2 改進后的k-means算法

在計算對象到聚類中心的距離時，我們采用的是歐幾里得距離，該種計算方法具有4種性質(zhì)(文檔與自身的距離為0、非負性、對稱性、三角不等式)，其中三角不等式即從對象i到對象j的直接距離小于等于途徑其他對象的距離。k-means算法每次迭代都要計算對象到每個聚類中心的距離，通過比較將對象分配到距離最近的聚類中，這些不必要的比較和距離計算比較浪費時間，我們可以利用三角不等式來減少每次迭代的計算次數(shù)，這樣就可以處理大數(shù)據(jù)量時的時間開支問題。

具體流程為：

(1) 任意選擇k個對象作為初始聚類中心。

(2) 計算每兩個聚類中心的距離d(Ci,Cj) ，其中i,j= 1 , 2,…k。

(3) 對于每個對象xi，設它當前屬于類ξi，ξi類的中心為Ci，計算xi與Ci的 距離d(xi,Ci) 。如果d(Ci,Cj) ≥ 2d(xi,Ci)，則xi所在的類不變，否則，計算d(xi,Cj) ；如果d(xi,Cj) ＜d(xi,Ci)，則暫時將xi分配到ξi中，否則，xi所在的類不變。重復步驟(3)，直到所有i d處理完。

(4) 重復(2)、(3)步，直到所有聚類都不變化。

文獻證明了該改進算法獲得了很好的聚類效果，提高了算法的效率。

4 混合文本聚類算法

凝聚型層次聚類算法能夠生成層次化的嵌套簇，準確度較高，但時間復雜性較高，運行速度較慢，在進行合并之后無法回溯。k-means聚類算法的運行速度較快，但是必須事先確定k的取值，對初始聚類中心的依賴性比較強，不適合發(fā)現(xiàn)非凸形狀的聚類，雖然可以保證局部最小，但不能保證全局最小。

如果將凝聚型層次聚類算法與k-means算法結(jié)合起來，利用凝聚型層次聚類算法來產(chǎn)生k-means算法所需要的k值和初始聚類中心，可以有效的克服k-means算法的不足。

為了能更準確的發(fā)現(xiàn)用戶的興趣所在，本算法將2.2節(jié)改進的凝聚型層次聚類算法和3.2節(jié)改進的k-means聚類算法結(jié)合起來。

具體流程如下：

(1) 計算給定的文檔集合D= {d1, …di, …dn} 中各個數(shù)據(jù)間的距離dij，將距離存放在一維數(shù)組中。

(2) 對一維數(shù)組進行升序排列。

(3) 將文檔集合 D 看成是一個聚類C= {c1, …ci, …cn} ，其中ci= {di}。

(4) 設定一閾值ξm，如果數(shù)組中的當前元素dij≤ξm，則分為三種情況：①如果di∈cm，dj∈cn，則ck=cm∪cn。②如果di∈cm，dj沒有合并到類中，則cm=cm∪dj。③如果di、dj都沒有合并到類中，則ck=di∪dj。重復步驟(4)，直到數(shù)組中所有元素處理完。否則如果dij＞ξm，凝聚算法結(jié)束，得到含有k個子類的聚類C= {c1, …ci, …ck} 。

(5) 將C= {c1, …ci, …ck} 作為k-means算法的初始聚類中心。

(6) 計算每兩個聚類中心的距離d(ci,cj) 。

(7) 對于D中的每個文檔di，設它當前屬于類ξi，ξi類的中 心為ci，計 算di與ci的 距離d(di,ci) 。如果d(ci,cj) ≥ 2d(di,ci)，則di所 在的類不變，否則，計算d(di,cj) ；如果d(di,cj) ＜d(di,ci)，則暫時將di分配到ξj中，否則，di所在的類不變。重復執(zhí)行步驟(7)，直到所有di處理完。

(8) 重復步驟(6)、(7)，直到所有聚類都不再變化。

5 結(jié)論

本文提出的混合文本聚類算法的難點就是閾值的確定，要通過相關領域知識來選定閾值，才能得到滿意的聚類結(jié)果。筆者將該算法用到了一個小型的個性化搜索引擎中，通過試驗將閾值定義為 5.0，對用戶的瀏覽記錄進行聚類，較好的挖掘出了用戶感興趣的內(nèi)容。

隨著 Web技術的發(fā)展以及用戶的需求和行為日益多元化，如何從海量的數(shù)據(jù)中分析并挖掘出人們需要的內(nèi)容，個性化的搜索引擎已經(jīng)成為人們研究的熱點，聚類的研究也將成為人們研究的熱點。

[1]段明秀,楊路明.對層次聚類算法的改進[J].湖南理工學院學報(自然科學版).2008.

[2]王會芬.基于 Web的網(wǎng)頁聚類系統(tǒng)的研究與實現(xiàn)[D].天津大學碩士學位論文.2005.

[3]嚴華.一種改進的k-means算法[J].計算機與現(xiàn)代化.2009.

[4]易珺.改進的 k-means算法在客戶細分中的應用研究[J].微型機與應用.2005.

[5]段小斌,陳基漓,張沫等.個性化推薦服務中用戶興趣模型研究[J].計算機與信息技術.2006.