嵌入式模糊集數(shù)據(jù)庫的FCM增量式聚類算法研究

斯亞民

(上海財經(jīng)大學(xué)浙江學(xué)院,浙江 金華 321013)

0 引 言

嵌入式模糊集數(shù)據(jù)庫技術(shù)被廣泛應(yīng)用在各種網(wǎng)絡(luò)或大規(guī)模集成系統(tǒng)中，對各種系統(tǒng)重要數(shù)據(jù)存儲具有重要意義[1]。嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)信息的管理與調(diào)度通常利用云計算與云儲存實現(xiàn)[2]，對嵌入式模糊集數(shù)據(jù)庫中原始數(shù)據(jù)與新增數(shù)據(jù)進(jìn)行準(zhǔn)確分類與整合，極大提高了人們利用數(shù)據(jù)庫進(jìn)行日常工作的工作效率。

以往對嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)檢索、分類、整合與挖掘通常采用小波變化算法、向量機(jī)分類挖掘算法等[3]。文獻(xiàn)[4]方法提出基于AutoEncoder的增量式聚類算法，利用AutoEncoder學(xué)習(xí)數(shù)據(jù)樣本的特征，進(jìn)行低維特征整合，實現(xiàn)模糊數(shù)據(jù)庫的增量聚類。該算法未設(shè)計濾波去噪功能，數(shù)據(jù)挖掘的過程中抗干擾性能差，導(dǎo)致聚類結(jié)果不準(zhǔn)確。文獻(xiàn)[5]方法提出基于多代表點的大規(guī)模數(shù)據(jù)模糊聚類算法。先對海量數(shù)據(jù)進(jìn)行分塊，對每個數(shù)據(jù)塊逐一聚類，聚類時使用多個代表點描述捕捉數(shù)據(jù)的潛在結(jié)構(gòu)和各個類信息,完成數(shù)據(jù)庫增量聚類。該算法迭代次數(shù)過多，運算過于復(fù)雜，無法有效聚類動態(tài)數(shù)據(jù)，導(dǎo)致數(shù)據(jù)聚類效率較低。

為解決上述問題，提出對嵌入式模糊集數(shù)據(jù)庫的FCM(模糊C均值(Fuzzy C-means算法))增量式聚類算法進(jìn)行研究。先根據(jù)嵌入式模糊集數(shù)據(jù)庫的結(jié)構(gòu)，構(gòu)建了數(shù)據(jù)信息流模型。采用自適應(yīng)級跟蹤濾波器對干擾進(jìn)行抑制。關(guān)鍵步驟是引入了FCM增量式聚類算法，來動態(tài)地調(diào)整數(shù)據(jù)庫中數(shù)據(jù)的聚類過程，得到高精度的數(shù)據(jù)聚類結(jié)果。且通過實驗驗證得出，該算法具有較高的聚類精度和聚類效率。

1 嵌入式模糊集數(shù)據(jù)庫增量式聚類算法

1.1 嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)信息流模型

將信息庫數(shù)據(jù)調(diào)度目標(biāo)信息與FCM聚類實施收斂性測試，初始化聚類中心，重組嵌入式模糊集數(shù)據(jù)庫結(jié)構(gòu)，將待推薦檢索數(shù)據(jù)的時間變多徑關(guān)聯(lián)維代入數(shù)據(jù)庫結(jié)構(gòu)中去，對冗余干擾實施濾波處理，形成嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)信息流模型。

1.1.1嵌入式模糊集數(shù)據(jù)庫結(jié)構(gòu)分析

(1)

(2)

Fd(Ci)=Fn(Ci)+Fo(Ci)

(3)

1.1.2構(gòu)建嵌入式模糊集數(shù)據(jù)庫信息流模型

依據(jù)上小節(jié)分析的嵌入式模糊集數(shù)據(jù)庫結(jié)構(gòu)，構(gòu)建嵌入式模糊集數(shù)據(jù)庫待挖掘信息流模型。嵌入式模糊集數(shù)據(jù)控中待挖掘數(shù)據(jù)特征用WS表示，設(shè)WS概率分布均勻，融合聚類分析經(jīng)線性調(diào)頻解擴(kuò)三階自相關(guān)特征的信息流內(nèi)指定數(shù)據(jù)，離散控制嵌入式模糊集數(shù)據(jù)中負(fù)荷信息流時間序列{x(t0+iΔt)}，i=0,1,…,N-1，VMj表示過載數(shù)據(jù)信息流矢量長度，則基于待推薦檢索數(shù)據(jù)的時間變多徑關(guān)聯(lián)維在嵌入式模糊集數(shù)據(jù)庫結(jié)構(gòu)中公式如下：

x(t)=λRe{an(t)e-j2πfcτn(t)sl(t-τn(t))e-j2πfct}

(4)

(5)

在嵌入式模糊集數(shù)據(jù)庫信息流模型中，通過自適應(yīng)級跟蹤濾波器抑制數(shù)據(jù)庫挖掘過程中受到的干擾[10]，對冗余干擾實施濾波處理，自適應(yīng)級跟蹤濾波器輸出函數(shù)見公式(6)：

(6)

其中，A表示自適應(yīng)級聯(lián)濾波幅值，m與ρ表示待挖掘數(shù)據(jù)干擾濾波階數(shù)與差值系數(shù)。Ta表示待挖掘信息數(shù)據(jù)碼元寬度，設(shè)Ta=1/Ra，濾波處理后形成嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)信息流模型為：

(7)

自適應(yīng)級跟蹤濾波器對數(shù)據(jù)挖掘過程中的干擾因子進(jìn)行了抑制和濾除，因此經(jīng)過濾波處理后，構(gòu)建的嵌入式模糊集數(shù)據(jù)庫信息流模型提高了抗干擾能力，數(shù)據(jù)挖掘過程所得到的數(shù)據(jù)結(jié)果更加準(zhǔn)確。在此基礎(chǔ)上，采用FCM增量式聚類算法獲取分離度與凝聚度評價數(shù)據(jù)庫中數(shù)據(jù)聚類結(jié)果，依據(jù)聚類結(jié)果決定該數(shù)據(jù)需要插入或刪除，進(jìn)而通過自適應(yīng)FCM增量式聚類算法實現(xiàn)數(shù)據(jù)庫的增量式聚類。

1.2 自適應(yīng)FCM增量式聚類算法

增量式聚類算法是在新聚類計算過程中融入前期聚類運算結(jié)果。采用自適應(yīng)FCM增量式聚類算法提高嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)計算效率，嵌入式模糊集數(shù)據(jù)庫中的更新數(shù)據(jù)對象集操作過程為插入數(shù)據(jù)與刪除數(shù)據(jù)，使該聚類簇刪除掉造成該聚類只剩下一個孤立點。在FCM聚類算法的基礎(chǔ)上，基于凝聚度與分離度所得FCM增量式聚類算法。

1.2.1插入數(shù)據(jù)與刪除數(shù)據(jù)

原始數(shù)據(jù)庫中的數(shù)據(jù)集采用FCM聚類方法操作后，操作剩下數(shù)據(jù)與新增數(shù)據(jù)全部列入新增數(shù)據(jù)集中[11]，新增數(shù)據(jù)集與通過聚類操作后數(shù)據(jù)集會形成情況如下：

(1)已有聚類不受新增數(shù)據(jù)影響，新增數(shù)據(jù)與原有聚類無任何聯(lián)系。新增數(shù)據(jù)形成新的聚類或者不形成聚類作為孤立點存在，若該點在后續(xù)計算中被加入新的聚類中，則認(rèn)為該點不是真正的孤立點；若孤立點直至計算終止仍然為孤立點，則計算終止后將它刪除，

(2)新增數(shù)據(jù)被已有聚類接收，原有聚類增大，除此之外的聚類無變化。

(3)新增數(shù)據(jù)可同時被多個聚類接收，與多個聚類相似度高，因此可將相似的幾個聚類通過該新增數(shù)據(jù)合并為新聚類，則與新增數(shù)據(jù)無關(guān)的聚類不發(fā)生變化。

(4)由于新增數(shù)據(jù)的插入，使原有聚類密度與分布受到影響而形成分裂[12]，一個聚類可分裂成兩個聚類或者多個聚類。

數(shù)據(jù)對象集內(nèi)的數(shù)據(jù)刪除也會形成以上分裂情況，從而將一個聚類由于某個數(shù)據(jù)的刪除分裂成兩個或者多個聚類。將數(shù)據(jù)直接刪除對其它聚類不會產(chǎn)生影響[13]，但有時因刪除數(shù)據(jù)為此聚類中主要數(shù)據(jù)，因此將該數(shù)據(jù)刪除后會使該聚類簇刪除掉造成該聚類只剩下一個孤立點。

1.2.2增量式操作

用分離度與凝聚度來評價嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)聚類結(jié)果。假設(shè)聚類中一個簇，可通過將該簇分為多個子簇優(yōu)化其凝聚性[14]。假如聚類中兩個或多個簇分離性差但是凝聚性較高，可將其合并為一個簇。

為使聚類結(jié)果分離度與凝聚度均達(dá)到較高的值，在FCM聚類算法的基礎(chǔ)上基于凝聚度與分離度所得的FCM增量式聚類算法如下：

采用歐式距離表示數(shù)據(jù)x與數(shù)據(jù)y間的距離，?x,y∈RP，該算法距離公式如下：

(8)

聚類中代表相似與緊密性的凝聚度公式為：

(9)

聚類中代表互相差異性的分離度公式為：

separation(Fi,Fj)=d(fi,fj)

(10)

其中，fi表示Fi聚類的中心，fj表示Fj聚類的中心。

通過式(8)得到新增數(shù)據(jù)點xnew與聚類間距Di=d(xnew,fi)利。

當(dāng)計算結(jié)果Di>maxdist時，則該點不屬于之前的聚類，該點作為新聚類的中心，后續(xù)計算中與該點具有相似性加入到該聚類中。

當(dāng)計算結(jié)果Di

當(dāng)計算結(jié)果Di

將所有新增數(shù)據(jù)按如上步驟重復(fù)直至結(jié)束。

為獲取準(zhǔn)確的聚類算法結(jié)果，在新增數(shù)據(jù)聚類后，對新增數(shù)據(jù)插入的簇利用公式(9)運算凝聚度，對比插入新數(shù)據(jù)后的聚類cohesion(Fi)′與未插入新數(shù)據(jù)前的聚類cohesion(Fi)相似與緊密性是否有改變。利用數(shù)值α作為凝聚度是否滿足要求的衡量數(shù)值[15]，α值通常由大量實驗獲取。當(dāng)|cohesion(Fi)′-cohesion(Fi)|<α?xí)r，說明插入新數(shù)據(jù)后的聚類凝聚度值符合要求，無需進(jìn)一步處理；當(dāng)|cohesion(Fi)′-cohesion(Fi)|>α?xí)r，說明插入新數(shù)據(jù)后的聚類凝聚度值不符合要求，利用自適應(yīng)FCM聚類算法對該類進(jìn)行進(jìn)一步分裂。

算法1具體過程為：

算法1 初始聚類中心算法

Entering 待分類的類S

Export 分裂時的初始聚類中心F和聚類個數(shù)jj

Initialization (S)

Start

(1)W={x1,x2,…,xm}; /*待分裂聚類內(nèi)數(shù)據(jù)包含m個數(shù)據(jù)，W為候選聚類中心為該聚類中每一點時的數(shù)據(jù)集*/

(2)F=φ; /*F是初始聚類中心集*/

(3)For(i=1;i<=m;i++)

Len[i]=Calculate Number(xi,t); /*計算球體范圍圓心xi與半徑t內(nèi)包含數(shù)據(jù)個數(shù)*/

(4)For(j!=1,j=1;j<=m;j++)

If ‖xj-xi‖<=r then

Tag xj; /*標(biāo)記xj鄰域范圍包含的點*/

Endif

(5) simultaneously(W≠)

{ j=1;

Species(len[i]);

Fj←len[1]相應(yīng)數(shù)據(jù)xi;/聚類中心選取密度最大點/

F←Fj; /*初始聚類中心融入聚類中心集F中*/

Delete 含有xi的xj；

W←W-{xj}；/*更新聚類中心集*/

j=j+1}

(6)back(F，j)

End

1.2.3增量式聚類

依據(jù)上述聚類結(jié)果，采用自適應(yīng)FCM增量式聚類算法(AIFCM)，實現(xiàn)嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)的增量式聚類。算法2具體過程如下：

算法2 自適應(yīng)FCM增量式聚類算法

Entering 對已有數(shù)據(jù)對象的聚類結(jié)果F={F1,F2,…,FC}，新增數(shù)據(jù)Xnew，閾值α

Export Fi為最終聚類結(jié)果

AIFCM(F，xnew，α)

Start

(1)如果是插入的數(shù)據(jù)，那么

(2)(i=1;i<=c;i++)

(j=1;j<=c;j++)

(Fi,Fj)的可分性用式(11)計算。

(3)當(dāng)最大距離=最小距離Maximum distance(Fi,Fj)時：

(4)(i=1;i<=c;i++)

Di=d(xnew,fi)

(5) If Di>Maximum distance then

c=c+1;

Otherwise If count(i)==1 then

Xnew→Ci； /Xnew加進(jìn)Ci聚類內(nèi)/

If |cohesionFi)′-cohesion(Fi|>α then

break up(Fi)；/分裂聚類Fi/

c=c+j

End if

Else

Ci→Ci+Cj; /*融合Ci與Cj*/

c=c-1;

Xnew→Ci； /*Xnew加進(jìn)合并后的聚類Ci中*/

End if

End if /*插入操作*/

Otherwise /*刪除操作*/

Delete xnew from Ci ;

If |cohesionFi)′-cohesion(Fi| >α then

break up(Ci)；/*分裂聚類Ci*/

c=c+j

End if

Else

(6)back (Ci)；

End

通過以上過程，實現(xiàn)嵌入式模糊集數(shù)據(jù)庫的增量式聚類。

2 實驗分析

通過兩組實驗數(shù)據(jù)集驗證本文算法對嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)聚類效果，將本文算法與文獻(xiàn)[4]提出的基于AutoEncoder的增量式聚類算法、文獻(xiàn)[5]提出的基于多代表點的大規(guī)模數(shù)據(jù)模糊聚類算法兩種增量式聚類算法進(jìn)行比較。

采用系統(tǒng)為Windows 7.0，Intel ivy Bridge處理器，內(nèi)存接口為DDR3-1600，運行內(nèi)存為4GB，主板為i965的計算機(jī)配置作為仿真實驗平臺。實驗基于Simulink和MATLAB軟件，利用Java進(jìn)行編程，實驗數(shù)據(jù)集采用該平臺生成的210個范圍為[0 1；0 1]的嵌入式模糊集數(shù)據(jù)樣本集，數(shù)據(jù)集共有兩個，兩個數(shù)據(jù)集進(jìn)行等量化分，分別記作數(shù)據(jù)集一和數(shù)據(jù)集二，由此避免實驗結(jié)果的偶然性。該數(shù)據(jù)庫含有三類數(shù)據(jù)樣本，每類樣本數(shù)量為70個，利用180個樣本進(jìn)行初始聚類數(shù)據(jù)，剩余30個樣本作為增量聚類數(shù)據(jù)。

三種算法實驗數(shù)據(jù)集一的聚類結(jié)果見圖1、圖2、圖3。

圖1 本文算法對實驗數(shù)據(jù)集一的聚類結(jié)果

圖2 文獻(xiàn)[4]算法對實驗數(shù)據(jù)集一的聚類結(jié)果

圖3 文獻(xiàn)[5]算法對實驗數(shù)據(jù)集一的聚類結(jié)果

根據(jù)圖1～圖3可以看出，采用文獻(xiàn)[4]算法對數(shù)據(jù)集一進(jìn)行聚類，在三組聚類結(jié)果中，都混有少量的其他組特征，但混入量較?。徊捎梦墨I(xiàn)[5]算法對數(shù)據(jù)集一進(jìn)行聚類，在三組聚類結(jié)果中，都混有大量的其他組特征，聚類效果并不明顯；采用本文算法對數(shù)據(jù)集一進(jìn)行聚類，在三組聚類結(jié)果中，完全沒有混入的其他特征量，聚類結(jié)果十分準(zhǔn)確。

實驗數(shù)據(jù)集二采用國際上通用于數(shù)據(jù)聚類的IRIS嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)集，該數(shù)據(jù)庫包含于UCI數(shù)據(jù)庫，是一類多重變量分析的數(shù)據(jù)集。該數(shù)據(jù)集中包含四維樣本點共150個，該數(shù)據(jù)庫含有三類數(shù)據(jù)樣本。將該數(shù)據(jù)庫隨機(jī)分成兩組，一組內(nèi)含有120個樣本為聚類初始樣本，剩余30個樣本作為增量聚類樣本。利用三種增量聚類算法對實驗數(shù)據(jù)集二進(jìn)行數(shù)據(jù)聚類，聚類結(jié)果如圖4、圖5和圖6所示。

圖4 本文算法對實驗數(shù)據(jù)集二的聚類結(jié)果

圖5 文獻(xiàn)[4]算法對實驗數(shù)據(jù)集二的聚類結(jié)果

圖6 文獻(xiàn)[5]算法對實驗數(shù)據(jù)集二的聚類結(jié)果

根據(jù)圖4～圖6可以看出，數(shù)據(jù)集二中的三種特征與數(shù)據(jù)集一不同，但聚類條件和聚類方式均相同，那么，采用文獻(xiàn)[4]算法對數(shù)據(jù)集二進(jìn)行聚類，在三組聚類結(jié)果中，都混入了大量的其他特征，且數(shù)據(jù)并不集中，分布散亂；采用文獻(xiàn)[5]算法對數(shù)據(jù)集二進(jìn)行聚類，在三組聚類結(jié)果中，雖然明顯地實現(xiàn)了聚類，但少量混入了的其他組特征；采用本文算法對數(shù)據(jù)集二進(jìn)行聚類，在三組聚類結(jié)果中，完全沒有混入的其他特征量，聚類結(jié)果十分準(zhǔn)確。對比上述兩次實驗結(jié)果得出，本文算法聚類效果優(yōu)于其他兩種方法，可將特征精準(zhǔn)的分類，沒有錯分樣本。另兩種算法雖然可以將大部分特征分類，但是分類并不精準(zhǔn)。主要原因在于本文算法通過自適應(yīng)級跟蹤濾波器抑制數(shù)據(jù)庫挖掘過程中受到的干擾，對冗余干擾實施濾波處理，構(gòu)建的嵌入式模糊集數(shù)據(jù)庫信息流模型提高了抗干擾能力，數(shù)據(jù)挖掘過程所得到的數(shù)據(jù)結(jié)果更加準(zhǔn)確，避免其他組特征混入，使聚類數(shù)據(jù)集中。

統(tǒng)計三種算法對實驗數(shù)據(jù)集一和二進(jìn)行聚類的聚類性能，結(jié)果用表1描述。

表1 不同算法的聚類性能比較

分析表1可以看出，本文算法對嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)進(jìn)行聚類運算時用時最少，并且所得聚類中心與實際聚類中心差距極小，在兩個實驗中沒有錯分樣本，說明了本文算法的有效與準(zhǔn)確性。主要原因在于本文算法采用自適應(yīng)FCM增量式聚類算法，提高嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)計算效率，進(jìn)而縮短了聚類時間。降低了聚類中心誤差。

實驗為了驗證本文算法的大數(shù)據(jù)聚類性能，采用大數(shù)據(jù)樣本驗證本文算法對嵌入式模糊集大數(shù)據(jù)庫增量聚類的有效性。在Matlab平臺生成20000個嵌入式模糊集數(shù)據(jù)樣本，將其中10000個數(shù)據(jù)樣本為初始聚類數(shù)據(jù)，其余10000個樣本分為10次增量加入初始數(shù)據(jù)庫中，檢測三種算法的增量聚類準(zhǔn)確度，有效性。三種算法進(jìn)行10次增量數(shù)據(jù)后聚類精準(zhǔn)度和時間見表2和表3。

綜合分析上述兩表可得，本文算法聚類大規(guī)模數(shù)據(jù)增量時依然可以保持很高的聚類準(zhǔn)確度，并且聚類用時很短，說明本文算法對嵌入式模糊集數(shù)據(jù)庫進(jìn)行增量聚類，具有較高的精度和效率。主要原因在于本文算法在FCM聚類算法的基礎(chǔ)上，進(jìn)行凝聚度與分離度FCM增量式聚類，使聚類結(jié)果分離度與凝聚度均達(dá)到較高的值。

表2 三種算法10次增量準(zhǔn)確度

表3 三種算法對大數(shù)據(jù)的平均聚類時間

3 結(jié) 語

目前對于嵌入式模糊集數(shù)據(jù)增量式聚類算法研究較少，數(shù)據(jù)庫中數(shù)據(jù)挖掘結(jié)果應(yīng)隨著數(shù)據(jù)庫中數(shù)據(jù)的更新而進(jìn)行更新，本文提出新的嵌入式模糊集數(shù)據(jù)庫增量式聚類算法，在嵌入式模糊集數(shù)據(jù)庫數(shù)據(jù)信息流模型中加入了自適應(yīng)級跟蹤濾波器，抑制數(shù)據(jù)庫挖掘過程中受到的干擾，將冗余干擾實施濾波處理，經(jīng)處理后的算法對噪聲樣本敏感，可將噪聲點區(qū)分出來，使處理后的數(shù)據(jù)受外界干擾較??；在此基礎(chǔ)上采用自適應(yīng)FCM增量式聚類算法，實現(xiàn)數(shù)據(jù)庫中數(shù)據(jù)的增量式聚類，該算法不隨增量數(shù)據(jù)的改變而改變聚類數(shù)量，增量式聚類效果較好。經(jīng)過大量實驗驗證本文算法完成了嵌入式模糊集數(shù)據(jù)庫中數(shù)據(jù)的高速、精準(zhǔn)聚類，對大規(guī)模增量數(shù)據(jù)聚類效果明顯，準(zhǔn)確率高，應(yīng)用價值高。