韓 海

（江漢大學(xué) 人工智能學(xué)院，湖北 武漢 430056）

人工智能在20 世紀(jì)90 年代進(jìn)入了低谷期，新世紀(jì)以來，隨著計(jì)算能力的提高和算法研究的深入，人工智能重新成為科學(xué)研究的熱門領(lǐng)域。聚類是一種無監(jiān)督的機(jī)器學(xué)習(xí)方法，是人工智能的基礎(chǔ)之一，在統(tǒng)計(jì)、圖像處理、自然語言理解、經(jīng)營決策等方面都有廣泛應(yīng)用。聚類是把樣本劃分成若干個(gè)互不相交的子集，每一個(gè)子集稱為一個(gè)“簇”（cluster），使得同一簇內(nèi)的個(gè)體相似度盡可能高，而不同簇內(nèi)的個(gè)體相似度盡可能低。

1 確定簇?cái)?shù)的聚類

從實(shí)際問題中采集信息，經(jīng)預(yù)處理、規(guī)范化之后得到m維空間的測量樣本X。設(shè)X中共有n個(gè)個(gè)體，記作每個(gè)個(gè)體包含m個(gè)屬性，是一個(gè)m維向量，記作對于其中任意兩個(gè)個(gè)體之間的距離表示兩者的相似度，通常用歐氏距離表示：

記P是對X進(jìn)行一次聚類的結(jié)果，P把X劃分成k個(gè)簇，定義每個(gè)簇的中心、簇內(nèi)距離di如下（該定義目前被廣泛采用［1?3］）：

式中，Ni表示第i個(gè)簇的容量，x表示第i個(gè)簇中的各個(gè)個(gè)體，1 ≤i≤k。

目前常用的聚類算法有基于均值的K?means 算法、基于密度的DBSCAN 算法等，這些算法在其適用場合都能夠?qū)颖具M(jìn)行劃分。如K?means 算法就是在預(yù)先確定簇?cái)?shù)的前提下搜索最佳劃分。對于給定的整數(shù)k，K?means 算法試圖把X聚類成k個(gè)簇，使得以下目標(biāo)函數(shù)F(P)的值最?。?/p>

文獻(xiàn)［2?3］主要是在搜索的覆蓋面上進(jìn)行改進(jìn)，調(diào)整了選擇初始簇心的策略，使得算法能夠更好地搜索解空間。對于給定的整數(shù)k，K?means 算法及K?means++算法給出的結(jié)果往往已接近甚至就是最優(yōu)解。但是，不論是相關(guān)問題的研究［4?7］還是MATLAB、R 語言等提供各類聚類運(yùn)算工具的平臺(tái)，都需要以預(yù)先確定簇?cái)?shù)為前提。在尋找全局最優(yōu)解時(shí)需要人工干預(yù)，通常是先人為確定幾種可能的k值，對每一種取值進(jìn)行聚類，將聚類結(jié)果進(jìn)行可視化處理，再人工判定哪一種更好。

2 全局聚類函數(shù)

為了進(jìn)行全自主的聚類，需要設(shè)計(jì)一種目標(biāo)函數(shù)比較不同k值下的聚類結(jié)果。聚類不僅要求同一簇內(nèi)的個(gè)體相似度盡量高，還要求不同簇中的個(gè)體相似度盡量低。一個(gè)簇中的個(gè)體與非該簇的個(gè)體相似度通常用簇間距離Di衡量［1，5，8］：

除了針對特定樣本的聚類之外，目前還沒有能夠廣泛適用的全局目標(biāo)函數(shù)，僅有較少人對此做過試探［9］。究其原因在于聚類成多少個(gè)簇為最優(yōu)與人的觀察有關(guān)，針對實(shí)際問題的聚類通常沒有公認(rèn)的最優(yōu)解，比如要把圖1 的星云圖像劃分成若干個(gè)星系，不同的人會(huì)有不同的看法。本文試圖以簡單的方式體現(xiàn)人的觀察，并把它作為目標(biāo)函數(shù)的一個(gè)參數(shù)。

綜合考慮簇內(nèi)距離和簇間距離后，設(shè)計(jì)初始的目標(biāo)函數(shù)G（P）為簇間距離減簇內(nèi)距離的平均值：

全自主的聚類就是要針對各種可能的k值，找出使得G（P）值最大的劃分。實(shí)驗(yàn)表明，多數(shù)情況下，G（P）的值會(huì)隨著簇?cái)?shù)k的增加而逐漸減小。比如，對圖1 所示574 × 329 像點(diǎn)的圖像進(jìn)行采樣，按照像點(diǎn)灰度值達(dá)到128 為有效點(diǎn)，灰度值每增加16 則重復(fù)次數(shù)加1（相當(dāng)于該亮點(diǎn)的權(quán)重），得到含2 667 個(gè)亮點(diǎn)的數(shù)據(jù)集，如圖2 所示，顏色越深代表重復(fù)次數(shù)越高，即原圖中該像點(diǎn)亮度越高。

圖1 星云圖像Fig.1 Nebula image

圖2 對圖1 采樣得到的樣本Fig.2 The sample obtained by figure 1

用K?means 聚類方法反復(fù)實(shí)驗(yàn)，得到聚類成2 ～ 13 個(gè)簇時(shí)目標(biāo)函數(shù)G（P）的最大值見表1第一行。

表1 目標(biāo)函數(shù)在簇?cái)?shù)k 為2～13 時(shí)的最大值Tab.1 The maximum value of the objective function when the number of clusters k is 2～13

G（P）在k=2 時(shí)取得最大值，并且隨著簇?cái)?shù)k的增加而逐漸減小，如圖3 中的實(shí)線所示。用其他樣本進(jìn)行實(shí)驗(yàn)可以獲得類似的結(jié)果，表明G（P）總體上呈現(xiàn)出遞減的特點(diǎn)，文獻(xiàn)［1，8］設(shè)計(jì)的目標(biāo)函數(shù)也有類似的現(xiàn)象，在不添加限制條件時(shí)目標(biāo)函數(shù)總體上表現(xiàn)為單調(diào)函數(shù)。簡單地用G（P）作為目標(biāo)函數(shù)不能合理地表現(xiàn)不同簇?cái)?shù)聚類結(jié)果的優(yōu)劣。圖3 中的虛線表現(xiàn)的是預(yù)期的目標(biāo)函數(shù)的特征(由表1 中第二行數(shù)據(jù)得到，即加入視野參數(shù)后目標(biāo)函數(shù)在簇?cái)?shù)k為2 ～13 時(shí)變化曲線)，好的目標(biāo)函數(shù)能夠在中間適當(dāng)位置取得最大值而不是單調(diào)的。

圖3 G（P）函數(shù)及預(yù)期的目標(biāo)函數(shù)Fig.3 G（P）function and expected objective function

3 聚類函數(shù)中的視野參數(shù)

對于同一個(gè)樣本，目前尚無成熟的方法用于比較兩個(gè)簇?cái)?shù)不同的聚類的優(yōu)劣，通常是把簇?cái)?shù)不同的聚類結(jié)果進(jìn)行可視化處理之后再由人通過觀察來確定。人們通常傾向于把圖1 劃分成5 ～7 個(gè)簇，而把圖4 劃分成2 ～ 4 個(gè)簇。圖4 不過是把圖1 縮小并在四周添加背景顏色的邊框得到，針對兩圖的不同聚類意向主要來自于視野范圍不同?？梢?，劃分成幾個(gè)簇與人的觀察有關(guān)，視野是描述觀察情況的一種簡單方法，在目標(biāo)函數(shù)中加入視野參數(shù)是一種可以考慮的設(shè)計(jì)。

圖4 加上廣闊背景的星云圖Fig.4 Nebula image with a broad background

視野表示人觀察事物的粗細(xì)程度。定義視野參數(shù)是一個(gè)數(shù)值T，T值越大越趨于大范圍宏觀觀察，T值越小越趨于微觀觀察。為了使得T能夠自適應(yīng)于不同的樣本，可以把該值設(shè)計(jì)為與樣本特征有關(guān)的函數(shù)。本文把T設(shè)計(jì)為樣本各分量最大差值的線性函數(shù)。對于m維樣本，記R(1)，R(2)，…，R(m)是各分量的最大差值，Rmin是各個(gè)R(t)的最小值：

則T可設(shè)置為Rmin的線性函數(shù)：

式中，K是定值，針對不同的樣本，根據(jù)經(jīng)驗(yàn)，K取值0.3 ～ 0.5 較好。在計(jì)算簇間距離時(shí)，用T限定Di的上限。先針對某一劃分計(jì)算出第i號(hào)簇與其他簇的簇心之間的距離，令Di取其最小值但不得超過T：

比如，對于圖2 所示樣本，每個(gè)個(gè)體有兩個(gè)屬性，x坐標(biāo)值和y坐標(biāo)值，其中x坐標(biāo)的最大差值為原圖像的寬度574，y坐標(biāo)的最大差值為原圖像的高度329，取K= 0.4，則T= 131.6。記對簇間距離Di設(shè)置上限之后的目標(biāo)函數(shù)為GK(P)，在K取值為0.4 時(shí)記作GK=0.4(P)。對圖2 的樣本進(jìn)行聚類的結(jié)果見表1 的第2 行。GK=0.4(P)在k=5 時(shí)取得最大值，此時(shí)的聚類結(jié)果如圖5所示。

圖5 用GK=0.4（P）找到的最優(yōu)劃分(k=5)Fig.5 The optimal partition with GK=0.4（P）(k=5)

圖5 中的“o”表示各個(gè)中心的初始位置，然后根據(jù)每個(gè)個(gè)體到各個(gè)“o”的距離指派到離它最近的一個(gè)“o”所代表的簇，得到對樣本的一個(gè)劃分。計(jì)算當(dāng)前劃分下各個(gè)簇的中心，圖中用“+”表示。觀察圖1 可以發(fā)現(xiàn)圖5 是對原始圖像很好的劃分。特別的是，如果以圖5 中的“+”作為新的初始中心再重新做一次指派，計(jì)算得到的目標(biāo)函數(shù)值略小于圖5 情況下的結(jié)果。

另外，根據(jù)添加視野參數(shù)后的GK=0.4(P)尋找最優(yōu)解時(shí)，表1 表示的k的各種取值情況下的局部最優(yōu)解都可以把圖1 中明顯的兩團(tuán)星云的主要部分劃分在同一個(gè)簇中。

如果視野參數(shù)T取比較小的值，對應(yīng)于人的主觀意愿是把樣本劃分成更小、更多的簇。表1的第3 行給出了GK=0.2(P)的實(shí)驗(yàn)數(shù)據(jù)，此時(shí)T= 65.8。GK=0.2(P)在k= 11 時(shí)取得最大值，對應(yīng)的聚類結(jié)果如圖6 所示。對樣本進(jìn)行劃分時(shí)各個(gè)初始中心較好地散布在相互距離適中的位置，不足之處是沒有突顯出兩大團(tuán)星云。

圖6 用GK=0.2（P）找到的最優(yōu)劃分(k=11)Fig.6 The optimal partition with GK=0.2（P）(k=11)

針對綜合簇內(nèi)距離和簇間距離的聚類目標(biāo)函數(shù)GK(P)，K?means 算法是用隨機(jī)的方式尋找最優(yōu)解的一種方法，但最優(yōu)解可能出現(xiàn)在算法的某一次循環(huán)中，而不一定是算法收斂時(shí)的劃分。表1 的數(shù)據(jù)都是通過記載并比較每一輪的劃分情況，保留GK(P)最大值而獲得。

4 改進(jìn)的方向

加入視野參數(shù)的目標(biāo)函數(shù)GK(P)可以從一定程度上反映人類對于聚類問題的主觀意愿，可以比較簇?cái)?shù)不同時(shí)哪一種聚類結(jié)果更好，并具有一定的普適性。極端情況下，目標(biāo)函數(shù)GK=0(P)退化成只考慮簇內(nèi)距離平均值，GK=+∞(P)就是不考慮視野參數(shù)的G(P)。

針對圖2 的樣本，在實(shí)驗(yàn)過程中曾經(jīng)獲得過一個(gè)GK=0.4(P)值略低于表1 最大值的劃分，如圖7 所示，該劃分的GK=0.4(P)值為100.7，即表1 中k= 6 的情況。一般來說，人們會(huì)傾向于圖7 是更好的聚類結(jié)果。

圖 7 用GK=0.4（P）在 k=6 時(shí)的最優(yōu)劃分Fig.7 The optimal partition with GK=0.4（P）(k=6)

造成圖5 的GK=0.4(P)值最大的原因在于該劃分中位于左上角的那個(gè)簇只有很少的個(gè)體，從而導(dǎo)致其簇內(nèi)距離di很?。欢J(rèn)為圖7 更好是因?yàn)楦鱾€(gè)簇比較均衡，簇內(nèi)距離di相差不大。因此，作為對設(shè)計(jì)全局目標(biāo)函數(shù)GK(P)的進(jìn)一步改進(jìn)，還可以考慮添加表示各簇均衡程度的參數(shù)。圖5 的劃分把圖像中部少量本該屬于左側(cè)星系的亮點(diǎn)劃歸到右側(cè)，這是由于按照個(gè)體到初始中心點(diǎn)的歐式距離劃分它歸屬于哪一個(gè)簇而造成的，改進(jìn)的另一個(gè)方向是尋找更好的劃分標(biāo)準(zhǔn)。