模糊C均值聚類(lèi)算法的改進(jìn)研究

,,

(安徽科技學(xué)院 理學(xué)院,安徽 風(fēng)陽(yáng) 233100)

0 引言

隨著計(jì)算機(jī)、通信和網(wǎng)絡(luò)技術(shù)的發(fā)展,人們被海量信息淹沒(méi)的同時(shí)又面臨著知識(shí)的貧乏,因此,開(kāi)始思考采用一定的方法從蘊(yùn)含著豐富信息的數(shù)據(jù)中抽取感興趣的知識(shí)和信息,包括有效的、新穎的、潛在有用的概念、規(guī)律和模式等,這就是數(shù)據(jù)挖掘．在數(shù)據(jù)挖掘技術(shù)中,聚類(lèi)分析是其中最主要的研究課題之一,其主要功能是根據(jù)對(duì)象的屬性,將大規(guī)模的數(shù)據(jù)集合分為由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)．其中,類(lèi)內(nèi)具有最大的相似性,類(lèi)間具有最小的相似性．

目前,常用的聚類(lèi)分析方法有劃分的方法、層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法和模糊聚類(lèi)方法．由于在現(xiàn)實(shí)生活中,很多對(duì)象沒(méi)有嚴(yán)格的屬性,不能把它絕對(duì)的劃分到某個(gè)類(lèi)別中,因此,模糊聚類(lèi)分析成為聚類(lèi)的研究主流,它得到的是樣本屬于某個(gè)類(lèi)別的不確定程度,更能客觀的反映真實(shí)的世界．模糊C均值聚類(lèi)算法(FCM)是一種代表性的模糊聚類(lèi)算法[1,2],但是FCM還有很多缺陷和不足,其中最主要的就是算法的性能依賴(lài)于初始中心的選擇,選取不同的初始中心,會(huì)得到不同的聚類(lèi)結(jié)果,影響到聚類(lèi)的穩(wěn)定性和準(zhǔn)確率．針對(duì)上述問(wèn)題,我們首先對(duì)要聚類(lèi)的數(shù)據(jù)采用數(shù)據(jù)分區(qū)技術(shù)進(jìn)行預(yù)處理,然后根據(jù)物質(zhì)質(zhì)心的定義及質(zhì)心運(yùn)動(dòng)原理,計(jì)算每個(gè)數(shù)據(jù)分區(qū)的質(zhì)心做為FCM聚類(lèi)的初始聚類(lèi)中心,降低FCM對(duì)初始中心的依賴(lài)性．

1 經(jīng)典FCM算法

在非監(jiān)督模式識(shí)別領(lǐng)域,FCM聚類(lèi)算法是應(yīng)用最廣泛的算法之一．Dunn在Ruspini提出模糊劃分概念的基礎(chǔ)上,改進(jìn)傳統(tǒng)的硬C均值聚類(lèi)算法,把其推廣到模糊情形,形成FCM算法．Bezdek在其提出的FCM算法的基礎(chǔ)上推廣到更一般的形式,就形成了我們今天所看到的經(jīng)典FCM算法．經(jīng)典FCM算法的基本思想是:隨機(jī)初始化若干個(gè)聚類(lèi)中心,計(jì)算樣本中的每個(gè)數(shù)據(jù)對(duì)聚類(lèi)中心的隸屬度,構(gòu)成隸屬度矩陣,然后通過(guò)若干次的迭代更新聚類(lèi)中心和隸屬度矩陣,使目標(biāo)函數(shù)值達(dá)到最?。繕?biāo)函數(shù)如下:

(1)

假設(shè)待聚類(lèi)數(shù)據(jù)集合X中含有n個(gè)對(duì)象,其中,m是模糊加權(quán)指數(shù),控制算法的柔性,m>1;c表示分類(lèi)數(shù);uij∈[0,1]表示第i個(gè)樣本點(diǎn)xi屬于第j個(gè)分類(lèi)的隸屬度;dij表示樣本點(diǎn)xi與聚類(lèi)中心vj的歐幾里德距離;V={vi}(i=1,2,…,c)表示聚類(lèi)中心矩陣,U={uij}表示隸屬度矩陣,其中隸屬度值uij具有如下的約束條件:

(2)

(3)

在迭代求Jm(U,V)最小值過(guò)程中,可通過(guò)(4)、(5)不斷的更新隸屬度和聚類(lèi)中心矩陣．

隸屬度更新公式為:

(4)

聚類(lèi)中心更新公式為:

(5)

2 改進(jìn)FCM算法

2.1 數(shù)據(jù)分區(qū)

在海量高維數(shù)據(jù)中,統(tǒng)計(jì)數(shù)據(jù)在每一維上的分布特性,根據(jù)它的分布特性,可將數(shù)據(jù)劃分為若干個(gè)分布均勻的區(qū)域[3-5]．劃分的基本過(guò)程如下:首先,從采集的大量數(shù)據(jù)中選取一個(gè)子數(shù)據(jù)集做為樣本數(shù)據(jù)．然后,用直方圖分析子數(shù)據(jù)集中每一維上的分布密度．直方圖是表示數(shù)據(jù)分布變化情況的一種統(tǒng)計(jì)工具,是由若干個(gè)高度不等的矩形組成,橫軸表示數(shù)據(jù)類(lèi)型,縱軸表示分布情況．繪制直方圖之前,要統(tǒng)計(jì)數(shù)據(jù)點(diǎn)中的最大值和最小值,根據(jù)數(shù)據(jù)的特點(diǎn)決定組數(shù)并利用每組中兩個(gè)端點(diǎn)的差值求出組距．最后,繪制直方圖,得到的直方圖的類(lèi)型有雙峰型、偏態(tài)型、折齒型等,通過(guò)分析結(jié)果,決定在那一維上分區(qū)、劃分為幾個(gè)區(qū)及各分區(qū)的邊界．

2.2 質(zhì)心計(jì)算

定義1 數(shù)據(jù)點(diǎn)鄰域[6]:設(shè)置距離閾值σ,數(shù)據(jù)集中與數(shù)據(jù)點(diǎn)的距離小于等于σ的對(duì)象組成的區(qū)域?yàn)樵摂?shù)據(jù)點(diǎn)的鄰域．

定義2 數(shù)據(jù)點(diǎn)質(zhì)量[7]:數(shù)據(jù)點(diǎn)在σ鄰域內(nèi)所包含的對(duì)象的個(gè)數(shù)為該數(shù)據(jù)點(diǎn)的質(zhì)量．

定義3 數(shù)據(jù)分區(qū)內(nèi)的質(zhì)心:假設(shè)劃分的數(shù)據(jù)分區(qū)為D維空間中N個(gè)數(shù)據(jù)點(diǎn)組成的系統(tǒng),在物理學(xué)中忽略其體積,只考慮數(shù)據(jù)點(diǎn)質(zhì)量,定義質(zhì)量中心為系統(tǒng)的質(zhì)心,質(zhì)心和質(zhì)心位置矢量的計(jì)算公式為:

(6)

(7)

其中,mi和ri分別為該數(shù)據(jù)分區(qū)內(nèi)第i個(gè)數(shù)據(jù)點(diǎn)的質(zhì)量和位置矢量,M和R分別為整個(gè)系統(tǒng)的質(zhì)心及質(zhì)心位置矢量．對(duì)于三維空間中的數(shù)據(jù)分區(qū),其維度分別為x,y,z,第i個(gè)數(shù)據(jù)點(diǎn)坐標(biāo)為(xi,yi,zi),則質(zhì)心的坐標(biāo)為:

(8)

2.3 改進(jìn)后的算法流程

在數(shù)據(jù)分區(qū)和質(zhì)心運(yùn)動(dòng)原理的基礎(chǔ)上,改進(jìn)后的FCM算法流程如下:

步驟1: 根據(jù)樣本數(shù)據(jù)集中某一維的直方圖進(jìn)行數(shù)據(jù)分區(qū),分區(qū)個(gè)數(shù)c既為聚類(lèi)類(lèi)別數(shù),設(shè)置一個(gè)足夠小的正數(shù)ε;

步驟2: 用式(6)、(7)、(8)計(jì)算每個(gè)數(shù)據(jù)分區(qū)的質(zhì)心坐標(biāo)和質(zhì)量形成初始聚類(lèi)中心集合V;

步驟3: 用式(4)計(jì)算或更新劃分矩陣U;

步驟4: 用式(5)更新聚類(lèi)中心V;

步驟6: 輸出隸屬度矩陣U和聚類(lèi)中心矩陣V．

3 實(shí)驗(yàn)分析

為了測(cè)試改進(jìn)算法的有效性,我們?cè)贛atlab6.5平臺(tái)的基礎(chǔ)上,采用數(shù)據(jù)挖掘研究院網(wǎng)站提供的某校園網(wǎng)日志記錄進(jìn)行仿真實(shí)驗(yàn)．截取子數(shù)據(jù)集共812條日志記錄,經(jīng)過(guò)數(shù)據(jù)預(yù)處理后得到8個(gè)用戶(hù)U={U1,U2,U3,U4,U5,U6,U7,U8}對(duì)該校園網(wǎng)6個(gè)頁(yè)面P={P1,P2,P3,P4,P5,P6}的訪(fǎng)問(wèn)次數(shù)統(tǒng)計(jì)矩陣,為了進(jìn)行用戶(hù)聚類(lèi),把相似瀏覽行為的用戶(hù)聚成放在一起,對(duì)該矩陣數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理,即用戶(hù)訪(fǎng)問(wèn)某個(gè)頁(yè)面的次數(shù)除以訪(fǎng)問(wèn)該網(wǎng)站所有頁(yè)面的總次數(shù),得到如下的矩陣:

根據(jù)上述矩陣,統(tǒng)計(jì)各維度上的直方圖(圖1),得到P1維度上的分布出現(xiàn)兩個(gè)密集區(qū),而且相對(duì)分布比較均勻,符合我們分區(qū)的要求,因此在P1維上把數(shù)據(jù)集分為3個(gè)區(qū),也就是把用戶(hù)初步分為3類(lèi)．

在上述分區(qū)的基礎(chǔ)上,計(jì)算每個(gè)分區(qū)的質(zhì)心及質(zhì)心位置矢量,然后再應(yīng)用FCM算法進(jìn)行聚類(lèi),下面給出直接進(jìn)行FCM聚類(lèi)和數(shù)據(jù)分區(qū)及計(jì)算質(zhì)心后再進(jìn)行FCM聚類(lèi)后的性能比較．通過(guò)表1我們可以看出計(jì)算分區(qū)質(zhì)心后,降低了迭代次數(shù)和運(yùn)行時(shí)間．

圖1 P1維上數(shù)據(jù)分布直方圖

表1 兩種 FCM算法的性能比較

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

FCM目前被廣泛的應(yīng)用到Web挖掘,圖像處理,模式識(shí)別等研究領(lǐng)域,引起了人們的廣泛關(guān)注．針對(duì)FCM對(duì)初始聚類(lèi)中心依賴(lài)性比較強(qiáng)這一缺陷,本文在數(shù)據(jù)分區(qū)和質(zhì)心計(jì)算的基礎(chǔ)上,粗略的確定分類(lèi)數(shù),計(jì)算的初始質(zhì)心接近實(shí)際的類(lèi)中心,因此降低了迭代次數(shù)和運(yùn)行時(shí)間,得到比較穩(wěn)定的聚類(lèi)結(jié)果,體現(xiàn)了改進(jìn)的FCM的優(yōu)越性.

[1]江克勤.優(yōu)化初始中心的模糊C-均值算法[J].合肥工業(yè)大學(xué)學(xué)報(bào),2009,32(5):762-768.

[2]張慧哲,王堅(jiān).基于初始聚類(lèi)中心選取的改進(jìn)FCM聚類(lèi)算法[J].計(jì)算機(jī)科學(xué),2009,36(6): 206-209.

[3]鄭洪英.大規(guī)模數(shù)據(jù)集聚類(lèi)中的數(shù)據(jù)分區(qū)及應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用研究,2007,2(2):203-205.

[4]何中勝,劉宗田,莊燕濱.基于數(shù)據(jù)分區(qū)的并行DBSCAN算法[J].小型微型計(jì)算機(jī)系統(tǒng).2006,27(1):114-116.

[5]王鑫,王洪國(guó).基于數(shù)據(jù)分區(qū)的最近鄰優(yōu)先聚類(lèi)算法[J].計(jì)算機(jī)科學(xué),2005,32(12):188-190.

[6]韋相,許海成,王紅曉.網(wǎng)格質(zhì)心運(yùn)動(dòng)的聚類(lèi)初始化方法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(13):135-138.

[7]汪永生,李均利.質(zhì)心粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(3):34-37.