基于一維數(shù)據(jù)逐段均勻條件下的參考分布研究*

張乃今， 張正軍， 趙慧秀

(南京理工大學(xué) 理學(xué)院，南京 210094)

0 引 言

聚類分析是對(duì)樣本觀測(cè)值聚集分類的一種探索性分析，其基本思想是通過(guò)在研究對(duì)象在特征空間上的差異等方面依據(jù)相應(yīng)指標(biāo)對(duì)對(duì)象進(jìn)行分類。雖然無(wú)法解釋樣本觀測(cè)值分類的合理性，但可以解決很多實(shí)際問(wèn)題，因此仍被廣泛應(yīng)用[1-3]?，F(xiàn)如今已經(jīng)產(chǎn)生很多種估計(jì)最佳聚類數(shù)的方法[4-7]， 2000年Hastie等提出了Gap Statistic(GS)方法，方法在k-means算法的基礎(chǔ)上解決了其他聚類方法無(wú)法將數(shù)據(jù)分成一類的問(wèn)題。隨后幾年，學(xué)者們?cè)陬悆?nèi)離散度的表示、參考分布的選取等方面對(duì)GS 方法進(jìn)行了改進(jìn)，或?qū)⑵渌椒ńY(jié)合起來(lái)處理問(wèn)題[8-11]。

GS方法引入了一個(gè)參考分布，用Gap統(tǒng)計(jì)量刻畫參考分布下樣本觀察值與期望值之間的差異，從統(tǒng)計(jì)角度解釋了樣本數(shù)據(jù)分類的合理性。由此可以看出，選擇合適的參考分布對(duì)于GS方法十分重要。目前已經(jīng)理論證明出在一維情況且成員(類)的分布函數(shù)形式(退化分布除外)為對(duì)數(shù)凹的情況下[12]，應(yīng)選取均勻分布作為參考分布，但對(duì)于其他條件下的分布沒(méi)有相關(guān)理論證明。

對(duì)此，提出在非對(duì)數(shù)凹及一維逐段均勻的條件下研究GS方法的參考分布。應(yīng)用k-means算法對(duì)數(shù)據(jù)進(jìn)行聚類，假設(shè)聚類后的數(shù)據(jù)是逐段均勻分布，計(jì)算不同聚類數(shù)下的類內(nèi)平方和，在給定條件下通過(guò)理論證明在這種情況下，總體均勻分布仍是使得類內(nèi)平方和最大的情況。

1 逐段均勻條件下參考分布研究

在樣本容量為p的情況下，對(duì)不同分布的數(shù)據(jù)空間，采用k-means聚類算法分別對(duì)其進(jìn)行聚類，假設(shè)每一簇?cái)?shù)據(jù)都是均勻分布。對(duì)于一維數(shù)據(jù)，總體均勻分布是類內(nèi)平方和最大的情況。

因此，在[0,1]區(qū)間上，

(2) 當(dāng)k=n,n=2,3,…,p時(shí)，

設(shè)在[0,a1]區(qū)間上P(X∈I1)=α1，

在[a1,a1+a2]區(qū)間上P(X∈I2)=α2,

?

在[a1+a2+…+an-1,1]區(qū)間上P(X∈In)=1-α1-α2-…-αn-1=αn。令an=1-a1-a2-…-an-1，如圖1所示。

圖1 一維情況Fig.1 One-dimensional situation

則有

(1)

用Lagrange乘數(shù)法對(duì)其求極值，設(shè)

(2)

解方程組：

(3)

可以看出，當(dāng)α1a1=α2a2=…=αnan=-6λ時(shí),Dn(α1,α2,…,αn,a1,a2,…,an)取極值。此時(shí)

(4)

已知

α1+α2+…+αn-1=1,a1+a2+…+an-1=1

故

(5)

由均值不等式可知

(6)

所以

(7)

則

(8)

即

(9)

2 實(shí)證分析

應(yīng)用k-means算法，選擇了不同的數(shù)據(jù)集進(jìn)行聚類，并計(jì)算分成各類后的類內(nèi)平方和。從圖2-圖7中可以看出，不管各數(shù)據(jù)集聚類后的類內(nèi)平方和logWk隨著k值怎樣變化，這6種數(shù)據(jù)集的類內(nèi)平方和均小于總體均勻分布時(shí)的類內(nèi)平方和。說(shuō)明假設(shè)是合理的。

圖2 iris數(shù)據(jù)集 圖3 glass數(shù)據(jù)集 圖4 seeds數(shù)據(jù)集
Fig.2 irisdata set Fig.3 glass data set Fig.4 seeds data set

圖5 balance數(shù)據(jù)集 圖6 haberman數(shù)據(jù)集 圖7 wine數(shù)據(jù)集
Fig.5 balance data set Fig.6 haberman data set Fig.7 wine data set

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

聚類分析能夠獲得數(shù)據(jù)的分布狀況，觀察每一簇?cái)?shù)據(jù)的特征，集中對(duì)具有相似特征的數(shù)據(jù)做進(jìn)一步處理，還可以作為其他算法的預(yù)處理步驟。GS方法從統(tǒng)計(jì)角度解釋了樣本數(shù)據(jù)分類的合理性，補(bǔ)充了聚類分析在分類準(zhǔn)確性方面的不足。對(duì)于GS方法來(lái)說(shuō)，選擇合適的參考分布至關(guān)重要。