未確知均值聚類

龐彥軍,劉立民,劉開第

(河北工程大學(xué) 理學(xué)院,河北 邯鄲056038)

聚類分析[1-2]是多元統(tǒng)計分析的重要方法,是模式識別的重要工具,在自動控制、系統(tǒng)辨識、人工智能、故障診斷等領(lǐng)域有重要的應(yīng)用?；诘膭討B(tài)聚類是最常用的聚類方法。C-均值聚類[3-4]是一種確定性聚類,是誤差平方和最小意義下的最優(yōu)聚類,當(dāng)存在病態(tài)數(shù)據(jù)和分類不清數(shù)據(jù)時,聚類效果不能令人滿意。模糊C均值聚類[5-6]則將隸屬函數(shù)引入均值聚類,能很好的處理分類不清數(shù)據(jù),但當(dāng)樣本存在“野值”時,效果不是很好。改進的模糊C均值聚類[7]等雖解決了“野值”問題,但迭代算法失去了可解釋性。更重要的是,上述聚類算法沒有充分利用輸入數(shù)據(jù)提供的分類信息,沒有體現(xiàn)出不同分類特征對分類作出的“不同貢獻”。樣本點之所以能被劃分為不同類別,是由于不同樣本的同一特征觀測值不同。不同樣本的某個特征觀測值越接近,則該特征對區(qū)分開樣本類別做出的貢獻越小。樣本集關(guān)于同一特征取值集中與發(fā)散的程度反映了該特征對分類貢獻的大小,這是與分類“同時存在”的客觀事實。本文分析特征對樣本分類所作貢獻,定義特征分類權(quán)重,給出計算樣本關(guān)于各類隸屬度的迭代算法,建立一種新的聚類方法—未確知均值聚類。

1 未確知系統(tǒng)理論[8]

未確知性是指由于條件限制,決策者無法確定事物的真實狀態(tài)或真實的數(shù)量關(guān)系,因而產(chǎn)生的一種主觀的、認(rèn)識上的不確定性。對未確知性的定量描述和處理,是對人類主觀事物范疇的一種探索。

定義1 設(shè)論域U={x1,x2,…,xn},F是U上的性質(zhì)空間,E是F上的σ-代數(shù),稱(F,E)為U上的可測空間。

定義2 如果{F1,F2,…,Fk}滿足

定義3 設(shè)(F,E)為U上的可測空間,μA(x)為元素x具有性質(zhì)A的程度,如果對?A,Al∈E,x∈U,有

則稱 μA(x)為可測空間(F,E)上的測度函數(shù),(U,E,μA(x))為未確知測度空間。

定義4 設(shè)(U,E,μA(x))是未確知測度空間,則以(x)為隸屬函數(shù)確定了論域U上關(guān)于σ代數(shù)E的一個未確知子集G

當(dāng)A∈E固定時,以 μA(x)為隸屬函數(shù)確定了論域U上的一個未確知子集;當(dāng)x∈U固定時,以μA(x)為隸屬函數(shù)確定了 σ代數(shù)E上的一個未確知子集。所以,μA(x)是U×E上的二元函數(shù)。

2 未確知均值聚類算法

2.1 問題描述

已知d維特征空間的N個訓(xùn)練樣本xi=(xi1,xi2,…,xid)(i=1,2,…,N),欲將 N個樣本劃分為C 類:Γ1,Γ2,…,ΓC。確定出 Γi類的類中心mi,則可用最小距離準(zhǔn)則確定各樣本點及待識樣本點的類別。

2.2 基本假設(shè)

假設(shè)同一類中的樣本點在特征空間中彼此應(yīng)該更“接近”,并且這種“接近”是歐氏距離或加權(quán)歐氏距離意義下的接近[9],即認(rèn)為同類樣本點在空間呈現(xiàn)超球體分布。如果這種“接近”是指在某個方向上的接近,將對應(yīng)“距離”的不同表達方法。

2.3 啟發(fā)性知識獲取

設(shè)xi=(xi1,xi2,…,xid)的分量是標(biāo)稱化數(shù)據(jù)。為了定量描述d個特征對初始分類做出的貢獻,令

令

稱ωj為特征j關(guān)于給定分類的分類權(quán)重。特征分類權(quán)重是在給定某種分類下,特征對“區(qū)分開”各類所做“貢獻”在所有特征中所占的比例。

2.4 隸屬度計算

初始分類給出C個聚類中心m1,m2,…,mC,任一訓(xùn)練樣本xi關(guān)于以mk為類中心的Γk類有一個實際上的隸屬度 μik。顯然,μik與點xi到mk的距離及各特征的分類權(quán)重有關(guān)。當(dāng) ωj=0時,j特征對分類不起作用,這時分量(xij-不應(yīng)作為距離分量出現(xiàn)在表征 xi到mk的距離中;而 ωj越大,j特征對分類貢獻越大。所以,當(dāng)用xi到mk間的距離Dik去表征xi關(guān)于Γk類隸屬度時,這種“距離”應(yīng)是一種加權(quán)距離。當(dāng)樣本點 xi到類中心mk的加權(quán)距離越小時,xi屬于Γk類的隸屬度越大。故

3 未確知均值聚類迭代算法

對 Γk類的類中心mk賦予質(zhì)量 μik,令 Γk類的新類中心向量為以新類中心替代初始類中心向量,可以建立求類中心的迭代算法。

步驟1 對N個訓(xùn)練樣本xi(i=1,2,…,N)的觀測數(shù)據(jù)實施標(biāo)稱化變換,標(biāo)稱化后的無量綱數(shù)據(jù)記為xi=(xi1,xi2,…,xid);給定分類數(shù)C。

步驟3 由(7)、(8)、(9)式,得分類權(quán)重向量ω(0)=(ω(10),ω(20),…,ω(C0))。

步驟4 由式(10)與式(11),得隸屬度向量 μi1,μi2,…,μiC)(i=1,2,…,N)。

步驟6 若maix‖＜δ,其中 δ＞0是預(yù)先給定得小正數(shù),則迭代停止,所求的C個聚類中心為

4 有效性檢驗

對3類共150個樣本的IRIS數(shù)據(jù),采用密度法確定3個初始類中心,結(jié)合本文算法經(jīng)10次迭代后求出3個聚類中心,然后對150個訓(xùn)練樣本按“最小加權(quán)距離準(zhǔn)則”重新歸類。經(jīng)15次重復(fù)實驗,平均誤識率為1.3%,表明本文算法穩(wěn)定、實用、魯棒性較好。

5 結(jié)論

1)未確知均值聚類根據(jù)樣本關(guān)于各類隸屬度與類中心間的內(nèi)在聯(lián)系,直接用迭代法求聚類中心,避開了構(gòu)造準(zhǔn)則函數(shù),使得算法的每一步涉及的類中心與隸屬度具有物理的可解釋性。

2)未確知均值聚類充分利用了輸入數(shù)據(jù)提供的關(guān)于分類的啟發(fā)式信息,構(gòu)造的隸屬度嚴(yán)格滿足測量準(zhǔn)則。

3)IRIS數(shù)據(jù)檢驗表明,未確知均值聚類算法較模糊均值聚類算法誤判樣本數(shù)少且收斂速度快,是一種實用、有效的無監(jiān)督聚類算法。

[1] MARQUES DE SA J P.模式識別—原理、方法及應(yīng)用[M] .北京:清華大學(xué)出版社,2002.

[2] 顧洪博,趙萬平.基于MMD聚類算法及在高校成績分析中的應(yīng)用[J] .河北工程大學(xué)學(xué)報(自然科學(xué)版),2010,27(1):96-98.

[3] 周巧萍,潘晉孝,楊明.基于核函數(shù)的混合C均值聚類算法[J] .模糊系統(tǒng)與數(shù)學(xué),2008,22(6):148-151.

[4] 高新波,裴繼紅,謝維信.模糊C-均值聚類算法中加權(quán)指數(shù)m的研究[J] .電子學(xué)報,2000,28(4):80-83.

[5] 劉蕊潔,張金波,劉銳.模糊C均值聚類算法[J] .重慶工學(xué)院學(xué)報,2008,22(2):139-141.

[6] 陳佳妮,段文英,丁徽.模糊C-均值聚類分析在基因表達數(shù)據(jù)分析中的應(yīng)用[J] .森林工程,2010,26(2):54-58.

[7] 劉坤朋,羅可.改進的模糊C均值聚類算法[J] .計算機工程與應(yīng)用,2009,45(21):97-98.

[8] 劉開第,曹慶奎,龐彥軍.基于未確知集合的故障診斷方法[J] .自動化學(xué)報,2004,30(5):747-756.

[9] 王 鑫,顏 炎,楊睿嫦,等.多批次測試數(shù)據(jù)建模新方法[J] .黑龍江科技學(xué)院學(xué)報,2010,20(3):227-229.