未確知均值聚類

龐彥軍,劉立民,劉開(kāi)第

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

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

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

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

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

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

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

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

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

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

2 未確知均值聚類算法

2.1 問(wèn)題描述

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

2.2 基本假設(shè)

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

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

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

令

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

2.4 隸屬度計(jì)算

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

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

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

步驟1 對(duì)N個(gè)訓(xùn)練樣本xi(i=1,2,…,N)的觀測(cè)數(shù)據(jù)實(shí)施標(biāo)稱化變換,標(biāo)稱化后的無(wú)量綱數(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個(gè)聚類中心為

4 有效性檢驗(yàn)

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

5 結(jié)論

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

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

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

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

[2] 顧洪博,趙萬(wàn)平.基于MMD聚類算法及在高校成績(jī)分析中的應(yīng)用[J] .河北工程大學(xué)學(xué)報(bào)(自然科學(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é)報(bào),2000,28(4):80-83.

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

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

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

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

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