国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

一種改進(jìn)的模糊C-均值聚類算法

2012-03-22 02:20:46易,
關(guān)鍵詞:類間均值次數(shù)

曹 易, 張 寧

(上海理工大學(xué)管理學(xué)院,上海 200093)

聚類是根據(jù)對(duì)象之間的相似性來將他們聚集成不同類別的方法.評(píng)價(jià)一個(gè)聚類質(zhì)量的好壞,總體是該聚類結(jié)果中同一類內(nèi)部的對(duì)象盡可能相似,不同類之間的對(duì)象盡可能相異.到目前為止,數(shù)據(jù)挖掘中常用的聚類算法有層次聚類、劃分聚類、基于網(wǎng)格聚類、基于密度聚類及模糊聚類等[1].

傳統(tǒng)的聚類是一種硬性劃分,具有“非此即彼”性,但是,現(xiàn)實(shí)生活中很多事物是“亦此亦彼”,很難將它們嚴(yán)格地劃分到一個(gè)具體的類中.模糊C-均值聚類算法(FCM)是應(yīng)用最廣泛的聚類算法之一[2],它具有算法簡(jiǎn)單、收斂速度快、能處理大規(guī)模數(shù)據(jù)等優(yōu)點(diǎn),因此,該算法已經(jīng)有效地應(yīng)用在數(shù)據(jù)挖掘、模式識(shí)別及決策支持等領(lǐng)域,具有很大的理論以及實(shí)踐價(jià)值.但是,F(xiàn)CM算法同時(shí)也存在著很大的局限性[3]:聚類數(shù)與聚類初始中心的選擇極大地影響著聚類效果,并且該算法采用梯度法求解極值,所求解往往是局部最優(yōu).為此,文獻(xiàn)[4]用信息熵來計(jì)算最佳聚類數(shù)目,Yager和Filev[5]提出了一種稱為爬山法的初始聚類中心方法.

由于一般模糊C-均值算法的上述缺點(diǎn),本文提出了一種改進(jìn)的FCM算法.首先用概率密度的思想得到最佳聚類數(shù)和初始聚類中心,其次通過對(duì)擁有次大隸屬度的中心點(diǎn)加入一個(gè)抑制因子來加速算法收斂,最后用一個(gè)兼顧類內(nèi)距與類間距的新的目標(biāo)函數(shù)來替代原有的目標(biāo)函數(shù).經(jīng)實(shí)驗(yàn)證實(shí),該算法在聚類結(jié)果質(zhì)量與算法速度上都有了一定程度的改進(jìn).

1 普通模糊C-均值的算法

設(shè)X={x1,x2,…,xn}是待聚類的對(duì)象的全體(論域),X中每個(gè)對(duì)象(樣本)xk(k=1,2,…,n)可以用有限個(gè)參數(shù)值來描述,每個(gè)參數(shù)刻畫xkj的某個(gè)特征.所以,對(duì)象xk就可以用一個(gè)向量P(xk)=(xk1,xk2,…,xks)來表示,P(xk)為xk的特征向量[6].uik表示X中第k個(gè)對(duì)象對(duì)第i類的隸屬度函數(shù),vi(i=1,2,…,c)表示聚類中心,則第k個(gè)對(duì)象到第i個(gè)聚類中心vi的歐式距離為

目標(biāo)函數(shù)定義為

隨著隸屬函數(shù)uik和中心點(diǎn)vi不斷更新,若目標(biāo)函數(shù)Jm(U,V,c)達(dá)到了滿意的穩(wěn)定程度,就終止迭代算法.

2 改進(jìn)的模糊C-均值的算法及其實(shí)現(xiàn)

2.1 聚類數(shù)和初始聚類中心選取的改進(jìn)

上述算法具有簡(jiǎn)單、收斂速度快、能處理大規(guī)模數(shù)據(jù)等優(yōu)點(diǎn),但是,聚類數(shù)和聚類初始中心的選擇極大地影響著聚類效果,并且該算法采用梯度法求解極值,所求解往往是局部最優(yōu).

目前,在FCM算法中,聚類數(shù)和初始中心點(diǎn)的選擇對(duì)算法的復(fù)雜度以及聚類效果的影響相當(dāng)大,因此,選擇一個(gè)適合的中心點(diǎn)是至關(guān)重要的.本文利用一種概率密度函數(shù)來選擇聚類數(shù)和初始中心[9,10].定義對(duì)象xi處的密度函數(shù)為

其中,rd為鄰域半徑,其數(shù)值與數(shù)據(jù)的分布特性有關(guān).

本文取rd為n個(gè)對(duì)象的平均距離,即

顯然,xi周圍分布越密集,rd值越小,密度函數(shù)值越大.令其滿足條件的點(diǎn)取為第一個(gè)初始聚類中心,設(shè)為x*1.第k個(gè)聚類中心點(diǎn)為

第k次迭代時(shí)的聚類中心的密度函數(shù)為

2.2 隸屬度的改進(jìn)

由FCM算法可知,聚類實(shí)際上就是一個(gè)隸屬矩陣u和聚類中心v交替優(yōu)化過程.可以修正隸屬矩陣u來計(jì)算下一次迭代的聚類中心v,使計(jì)算結(jié)果更合理,提高算法的收斂速度.隸屬度越大,樣本點(diǎn)對(duì)類中心的吸引力就越大,類中心的下一次迭代值受隸屬度的影響就越大[11].本文根據(jù)競(jìng)爭(zhēng)學(xué)習(xí)算法,給出了一種修正隸屬矩陣u的算法.本文稱距離樣本點(diǎn)最近的類中心為贏者,距離次近的為贏者對(duì)手,通過減弱對(duì)手的吸引力來加快贏者的收斂速度.加入一個(gè)抑制因子α∈[0,1],抑制次近樣本點(diǎn)的吸引力,來加快算法收斂速度.具體描述為:對(duì)于對(duì)象xj,假如它對(duì)第t類的隸屬度最大,為utj;對(duì)第s類的隸屬度次大,為usj.給定抑制因子α,根據(jù)式(6)修改隸屬度為

其余對(duì)象的隸屬度不變.

2.3 目標(biāo)函數(shù)選取的改進(jìn)

聚類結(jié)果應(yīng)該是類內(nèi)盡可能緊湊,類間盡可能疏遠(yuǎn).但是,傳統(tǒng)的FCM算法的目標(biāo)函數(shù)只考慮了類內(nèi)距離,沒有重視類間距離.本文根據(jù)Xie-Beni提出的聚類有效性指標(biāo)[12],給出一種兼顧類內(nèi)和類間距離的有效性指標(biāo),將它作為新的目標(biāo)函數(shù).

類內(nèi)差異W(u,v,c)和類間差異B(u,v,c)分別為

將W(u,v,c)和B(u,v,c)的商作為新的目標(biāo)函數(shù)Jm(u,v,c),即

2.4 模糊C-均值算法改進(jìn)的具體實(shí)現(xiàn)

綜上所述,現(xiàn)給出該算法的具體步驟.

Step 1 給定待聚類對(duì)象集X,參數(shù)δ,模糊因子m,抑制因子α,迭代參數(shù)ε.

Step 2 根據(jù)式(3)~(5)求出初始聚類數(shù)c和聚類中心v.

Step 3 計(jì)算隸屬矩陣uik,再根據(jù)式(6)修改u.

Step 4 更新聚類中心vi.

Step 5 根據(jù)式(9)計(jì)算Jm(u,v,c),若式(12)成立,終止計(jì)算;否則,l=l+1,轉(zhuǎn)向Step 3.

3 實(shí)驗(yàn)結(jié)果及分析

通過實(shí)驗(yàn)來測(cè)試改進(jìn)算法的效率和聚類質(zhì)量,并與普通的模糊C-均值算法進(jìn)行比較.本次實(shí)驗(yàn)平臺(tái)操作系統(tǒng)為Windows XP,CPU為雙核E7500 2.9GHz,內(nèi)存2GB.數(shù)據(jù)采用某高校的Web訪問日志,共有2 993個(gè)IP用戶,訪問的網(wǎng)頁(yè)被綜合成了教育、娛樂、搜索等35個(gè)類別,每個(gè)類別認(rèn)為是用戶的一個(gè)屬性值,大小取該用戶對(duì)該類別的訪問頻率,得到了2 993×35的用戶類別矩陣.實(shí)驗(yàn)取模糊因子m值為2,最大可能迭代次數(shù)為200,通過改變參數(shù)δ,α和ε的值來測(cè)試算法的性能,得到參數(shù)的最佳取值范圍.聚類結(jié)果的有效性指標(biāo)p[13]用式(13)來評(píng)價(jià),值越小,則聚類效果越好;反之亦然.N為算法迭代次數(shù).

經(jīng)調(diào)整實(shí)驗(yàn)控制參數(shù)得出結(jié)果如圖1~4所示.

圖1 聚類有效性p和迭代次數(shù)N與α的關(guān)系Fig.1 Relationship of clustering validity p,iteration number Nandα

從圖1~4可以看出:

a.當(dāng)m=2,δ=0.5,ε=0.001時(shí),隨著參數(shù)α從0變化到1時(shí),有效性指標(biāo)p與迭代次數(shù)N的變化趨勢(shì)如圖1,綜合考慮該算法的聚類質(zhì)量以及迭代次數(shù),取α=0.3較為合理.

b.在圖2中,當(dāng)m=2,α=0.3,ε=0.001時(shí),隨著參數(shù)δ從0變化到1時(shí),有效性指標(biāo)p,迭代次數(shù)N以及聚類數(shù)c變化趨勢(shì)如圖2(見下頁(yè)),同樣綜合考慮該算法,取δ=0.5較為合理,此時(shí)聚類數(shù)c=43.

c.當(dāng)m=2,α=0.3,δ=0.5時(shí),隨著參數(shù)ε從0.000 5~0.001 4之間變化時(shí),有效性指標(biāo)p與迭代次數(shù)N的變化趨勢(shì)如圖3(見下頁(yè)),同樣綜合考慮該算法,取ε=0.001較為合理.

d.取m=2,α=0.3,δ=0.5,ε=0.001時(shí),用本文的改進(jìn)FCM算法與經(jīng)典的FCM算法進(jìn)行比較,從圖4(見下頁(yè))中可以看出,當(dāng)聚類數(shù)目相同時(shí),與經(jīng)典FCM算法相比,本文算法在有效性指標(biāo)p與迭代次數(shù)N上均有一定程度的提高.

綜上所述,本文提出的改進(jìn)FCM算法中,通過調(diào)節(jié)參數(shù)α,δ,ε的大小,其中本文的數(shù)據(jù)中α=0.3、δ=0.5、ε=0.001,較原有的FCM算法在聚類質(zhì)量和算法速度有一定程度的提高.

圖2 聚類有效性p,迭代次數(shù)N及聚類數(shù)c與δ的關(guān)系Fig.2 Relationship of clustering validity p,iteration number N,cluster number c andα

圖3 聚類有效性p和迭代次數(shù)N與ε的關(guān)系Fig.3 Relationship of clustering validity p,iteration number Nandε

圖4 改進(jìn)的FCM算法與經(jīng)典FCM算法比較Fig.4 Comparison of the improved FCM and classical FCM algorithm

4 結(jié) 論

通過分析經(jīng)典的FCM算法中的局限性,例如聚類結(jié)果對(duì)聚類數(shù)和初始聚類中心的敏感性,以及目標(biāo)函數(shù)選取只考慮類內(nèi)部距離而忽略了類間距離,提出了一種改進(jìn)的FCM算法.經(jīng)實(shí)驗(yàn)證明,與經(jīng)典算法相比,改進(jìn)算法不論是在聚類質(zhì)量上還是在算法復(fù)雜度上,都有一定程度的提高.用概率密度函數(shù)找到最佳的聚類數(shù)以及初始聚類中心點(diǎn);利用競(jìng)爭(zhēng)學(xué)習(xí)算法中的抑制對(duì)手來修改隸屬矩陣,從而達(dá)到加快算法的收斂速度;用一個(gè)類內(nèi)距離與類間距離兼顧的新目標(biāo)函數(shù)替換原有目標(biāo)函數(shù).實(shí)驗(yàn)證明,本文算法在參數(shù)設(shè)置合理的情況下,聚類質(zhì)量和算法速度在原有FCM算法上有一定程度的提高.

[1] Mitra S,Pal S K,Mitra P.Data mining in soft computing framework:a survey[J].IEEE Transactions on Neural Networks,2002,13(1):3-14.

[2] 賀玲,吳玲達(dá),蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述.計(jì)算機(jī)應(yīng)用研究,2007,1(1):16-19.

[3] 齊淼,張化祥.改進(jìn)的模糊C-均值聚類算法研究.計(jì)算機(jī)工程與應(yīng)用,2009,45(20):133-135.

[4] 沈紅斌,楊杰,王士同,等.基于信息理論的合作聚類算法研究[J].計(jì)算機(jī)學(xué)報(bào),2005,28(8):1287-1294.

[5] Yager R R,F(xiàn)ilev D P.Approximate clustering via the mountain method[J].IEEE Transactions on SMC,1994,24(8):1279-1284.

[6] 張敏,于劍.基于劃分的模糊聚類算法[J].軟件學(xué)報(bào),2004,15(6):858-868.

[7] 朱文婕,吳楠,胡學(xué)鋼.一個(gè)改進(jìn)的模糊聚類有效性指標(biāo)[J].計(jì)算機(jī)工程與應(yīng)用2011,47(5):206-209.

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

[9] 饒泓,扶名福,謝明詳.基于模糊聚類的神經(jīng)網(wǎng)絡(luò)故障診斷方法[J].微計(jì)算機(jī)信息,2007,1(1):196-197.

[10] 李春生,王耀南.聚類中心初始化的新方法[J].控制理論與應(yīng)用,2010,27(10):1435-1440.

[11] 張曙紅,孫建勛,諸克軍.基于遺傳優(yōu)化的采樣模糊C-均值聚類算法[J].系統(tǒng)工程理論與實(shí)踐,2004,5(1):121-125.

[12] Xie X L,Beni G.A validity measure for fuzzy clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1991,13(8):841-847.

[13] Kwon S H.Cluster Validity index of fuzzy clustering[J].Electronics Letters,1998,34(22):2176-2177.

猜你喜歡
類間均值次數(shù)
機(jī)場(chǎng)航站樓年雷擊次數(shù)計(jì)算
2020年,我國(guó)汽車召回次數(shù)同比減少10.8%,召回?cái)?shù)量同比增長(zhǎng)3.9%
商用汽車(2021年4期)2021-10-13 07:16:02
一類無界算子的二次數(shù)值域和譜
基于OTSU改進(jìn)的布匹檢測(cè)算法研究
基于貝葉斯估計(jì)的多類間方差目標(biāo)提取*
基于類間相對(duì)均勻性的紙張表面缺陷檢測(cè)
基于改進(jìn)最大類間方差法的手勢(shì)分割方法研究
依據(jù)“次數(shù)”求概率
均值不等式失效時(shí)的解決方法
均值與方差在生活中的應(yīng)用
屯留县| 哈巴河县| 开化县| 灵宝市| 山东省| 个旧市| 尼木县| 成都市| 新建县| 江安县| 山阴县| 那坡县| 宁南县| 西青区| 淮滨县| 浦北县| 钦州市| 苍山县| 胶南市| 政和县| 梧州市| 蒲江县| 宜城市| 三亚市| 广饶县| 昌吉市| 临武县| 武川县| 汉寿县| 和静县| 永康市| 墨竹工卡县| 彭山县| 台安县| 衡山县| 武山县| 台山市| 普定县| 察雅县| 丁青县| 潼南县|