王 進(jìn)，游 磊，黎忠文，苗 放

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院，四川 成都 610106； 2. 成都大學(xué) 大數(shù)據(jù)研究院，四川 成都 610106)

基于數(shù)據(jù)密度感知的非平衡數(shù)據(jù)模糊聚類方法

王 進(jìn)1，游 磊1，黎忠文1，苗 放2

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院，四川 成都 610106； 2. 成都大學(xué) 大數(shù)據(jù)研究院，四川 成都 610106)

非平衡數(shù)據(jù)分析是數(shù)據(jù)領(lǐng)域的重要問題之一，其類間分布的巨大差異給聚類方法帶來嚴(yán)峻挑戰(zhàn).圍繞非平衡數(shù)據(jù)聚類問題，分析了非平衡數(shù)據(jù)對模糊聚類方法的影響，提出了基于密度感知的模糊聚類方法.方法將數(shù)據(jù)分布密度特征嵌入模糊聚類初始化過程中，用于定位初始聚類中心點(diǎn)，避免了少數(shù)類中心點(diǎn)位置的消失，在此基礎(chǔ)上進(jìn)一步設(shè)計(jì)了基于密度的模糊聚類優(yōu)化更新方法.經(jīng)數(shù)據(jù)集分析驗(yàn)證，本研究方法能夠有效解決非平衡數(shù)據(jù)分類中少數(shù)類消失問題，并且在聚類算法性能上比傳統(tǒng)方法有明顯提高.

模糊聚類；分布密度；非平衡數(shù)據(jù)

0 引 言

模糊聚類方法(fuzzy C-means，F(xiàn)CM)，是一種典型的非監(jiān)督學(xué)習(xí)方法，其在傳統(tǒng)聚類方法的基礎(chǔ)上，模糊聚類方法引入隸屬度概念，刻畫了每個(gè)數(shù)據(jù)個(gè)體與不同類的相似性，隸屬度最大的類被視為該數(shù)據(jù)個(gè)體的母類.對數(shù)據(jù)隸屬度分布的分析，可以得到數(shù)據(jù)個(gè)體的細(xì)節(jié)特征.然而，如何處理非平衡數(shù)據(jù)聚類依然是模糊聚類面臨的一個(gè)重要問題[1].非平衡數(shù)據(jù)的主要特征在于不同類的數(shù)據(jù)量差異巨大，占多數(shù)數(shù)據(jù)量的主要類往往對聚類結(jié)果起決定性影響，造成占少數(shù)數(shù)據(jù)量的次要類在聚類結(jié)果中逐漸消失.針對該問題，現(xiàn)有研究主要通過聚類權(quán)重進(jìn)行解決，即按照每類所含數(shù)據(jù)量分配類權(quán)重，確保少數(shù)類不受多數(shù)類影響，例如，csiFCM、ssFCM、FMLE及siibFCM等[2-6].事實(shí)上，由于大多數(shù)數(shù)據(jù)是無標(biāo)記的，聚類初始無法明確得到每類所含數(shù)據(jù)點(diǎn)數(shù)，使得基于權(quán)重的方法應(yīng)用受到一定的限制.數(shù)據(jù)分布密度是數(shù)據(jù)集的重要特征，反映了數(shù)據(jù)的空間幾何結(jié)構(gòu).在低維場景下，可直接通過數(shù)據(jù)分布密度獲取數(shù)據(jù)聚類信息，高密度區(qū)域通常代表潛在的聚類(見圖1).基于該思路，本研究通過數(shù)據(jù)分布的密度特征進(jìn)行聚類：聚類初始，通過數(shù)據(jù)密度選擇初始中心點(diǎn)；聚類過程中，采用潛在中心點(diǎn)附近數(shù)據(jù)點(diǎn)更新聚類中心位置，由此避免少數(shù)類消失問題.具體實(shí)現(xiàn)時(shí)，采用分治思路對模糊聚類算法重新設(shè)計(jì)，將FCM算法擴(kuò)展至可并行計(jì)算，應(yīng)用數(shù)據(jù)分布密度解決非平衡數(shù)據(jù)聚類問題.

圖1聚類分布示意圖

1 基于密度的模糊聚類算法設(shè)計(jì)

基于密度的模糊聚類方法，旨在利用數(shù)據(jù)集的空間幾何結(jié)構(gòu)來優(yōu)化聚類算法.對此，本研究首先利用高斯核密度估計(jì)方法獲取數(shù)據(jù)的分布密度，將數(shù)據(jù)集粗分為不同子集，針對不同子集進(jìn)行局部迭代優(yōu)化，確保少數(shù)類中心點(diǎn)不消失.數(shù)據(jù)集粗分與子集局部優(yōu)化是該方法需要解決的2個(gè)重要問題.

1.1 基于密度的數(shù)據(jù)劃分方法設(shè)計(jì)

通常，聚類中心點(diǎn)鄰域的數(shù)據(jù)分布密度略高于附近鄰居點(diǎn)的鄰域密度，且距離更高密度點(diǎn)較遠(yuǎn)[7].基于該特征，下面給出其具體數(shù)學(xué)模型，其中包括局部密度和特征距離2個(gè)參數(shù).

(1)

其中，‖xi-xj‖為歐式距離，dc為距離門限值.

特征距離δi定義為數(shù)據(jù)點(diǎn)xi到距離其最近的高密度點(diǎn)的距離，如式(2)所示.

(2)

基于有向無環(huán)圖的數(shù)據(jù)集粗分方法如圖2所示.其中，端點(diǎn)表示數(shù)據(jù)點(diǎn)，端點(diǎn)之間的有向邊表征其有向鄰居關(guān)系，有向邊的長度則為其特征距離.

圖2基于有向無環(huán)圖的數(shù)據(jù)集粗分方法

定義1 數(shù)據(jù)點(diǎn)p的有向鄰居定義為距離該點(diǎn)最近的高密度點(diǎn)，即，

有向鄰居點(diǎn)的若干特性如下：

1)全局密度最高的數(shù)據(jù)點(diǎn)沒有有向鄰居點(diǎn)，從算法設(shè)計(jì)角度考慮，將其特征距離設(shè)置為，

2)有向鄰居點(diǎn)之間密度服從，ρpρq；

3)每個(gè)數(shù)據(jù)點(diǎn)有且僅有一個(gè)有向鄰居點(diǎn)；

4)有向鄰居關(guān)系是不可逆的，即數(shù)據(jù)點(diǎn)p的有向鄰居為q，但數(shù)據(jù)點(diǎn)q的有向鄰居不是p.

由圖2可知，特征距離小的數(shù)據(jù)點(diǎn)通常跟其有向鄰居位于同一個(gè)類中，而特征距離較大的點(diǎn)則與其有向鄰居位于不同類.由此，將有向鄰居圖按照有向邊長度進(jìn)行粗分為不同區(qū)域，即潛在的類.具體分割方法如下：對于任意數(shù)據(jù)點(diǎn)，如果其特征距離小于門限dc,則將其劃分到與其有向鄰居相同的區(qū)域；否則，以該點(diǎn)為中心點(diǎn)構(gòu)建潛在新類.其類歸并偽代碼如下：

InputtCen={tc1,tc2，…，tck，…，tcM};

Input {tClustk}，k=1,2,…，M;

Input the cluster number C;

tCennew=sortWithGama(tCen,′descending′)

FORj=1:(M-C),

waitForMerge=tCennew[M-j+1];

mergeTo=dirNeighborOf(tCennew[M-j+1]);

tClustmergeTo=Append(tClustwaitForMerge);

END;

由此，將數(shù)據(jù)集粗分為若干潛在聚類，其中心點(diǎn)具有局部最大的數(shù)據(jù)密度.本研究將門限dc設(shè)置為所有數(shù)據(jù)距離的2分位點(diǎn).實(shí)際應(yīng)用中，門限還可以通過優(yōu)化得到.

依據(jù)聚類數(shù)量，進(jìn)一步將上述潛在聚類歸并，并優(yōu)化數(shù)據(jù)集分割.假定潛在聚類為，

其中，k和nk分別為聚類標(biāo)識和每個(gè)子類tClustk中數(shù)據(jù)點(diǎn)數(shù)量,子類中心點(diǎn)為tCen={tc1,tc2,…，tck，…，tcM}?X.

由于潛在聚類中心點(diǎn)通常同時(shí)具有較大特征距離和數(shù)據(jù)密度[7].基于此，本研究依據(jù)γi=δi*σi對所有子類中心進(jìn)行排序，將所有子類歸并到就近的c個(gè)子類中，完成子類歸并.

1.2 子集聚類優(yōu)化方法

圍繞上述得到的子類，{tClustk}，k=1,2,…，C，進(jìn)一步設(shè)計(jì)基于密度的聚類優(yōu)化方法，

FN×C=[f1，1，f1，2，…，f1，C；…；fN，1，fN，2，…，fN，C]

來表示初始劃分的聚類關(guān)系，其中，

本研究進(jìn)一步將聚類中心點(diǎn)計(jì)算方法設(shè)計(jì)為如式(3)所示，

(3)

每次局部中心點(diǎn)位置更新只取決于局部子類中的數(shù)據(jù)點(diǎn).模糊聚類的隸屬度和目標(biāo)函數(shù)分別為，

(4)

(5)

基于密度的模糊聚類算法偽代碼如下：

InputtCen={tc1,tc2,…，tck，…，tcM};

Input {tClustk},k=1,2,…，M;

Input the cluster number C,ε;

[tCennew，tClustnew]=Merger(tCen,tClust);

Computed(xi,vj) with Eq. 4;

Compute membership with Eq. 5.

WHILE|Ji+1-Ji|>ε,

Update centroids with Eq. 3;

Computed(xi,vj) with Eq. 4;

Compute membership with Eq. 5.

END;

2 算法性能評估

本研究采用具有代表性的非平衡數(shù)據(jù)集ecoli-0-1-4-6[9]評估來研究所提算法的性能.數(shù)據(jù)集ecoli-0-1-4-6包括陽性和陰性2類數(shù)據(jù)，其中陽性類數(shù)據(jù)有20例，陰性類數(shù)據(jù)有260例，數(shù)據(jù)維度為8.另一個(gè)數(shù)據(jù)集來自文獻(xiàn)[7]，該數(shù)據(jù)集包括2 535數(shù)據(jù)樣本，共5類，每個(gè)數(shù)據(jù)樣本維度是2，其每個(gè)類所包含的數(shù)據(jù)量分別為，C1n=1 456,C2n=246,C3n=246,C4n=431,C5n=156.該數(shù)據(jù)集是無標(biāo)記的，并且含有噪聲(見圖3).同時(shí)，本研究應(yīng)用文獻(xiàn)[7]方法對數(shù)據(jù)進(jìn)行標(biāo)記，去除部分噪聲.表1詳細(xì)給出上述2個(gè)數(shù)據(jù)集的特征信息.

表1 數(shù)據(jù)集描述

圖3文獻(xiàn)[7]數(shù)據(jù)集分布

算法性能的比較主要通過聚類準(zhǔn)確性與迭代次數(shù)來衡量算法在聚類性能和計(jì)算性能的差異.

首先，采用文獻(xiàn)[7]數(shù)據(jù)集分析非平衡數(shù)據(jù)對聚類性能的影響.該數(shù)據(jù)集包括2個(gè)主要類和3個(gè)少數(shù)類(見圖3)，其中3個(gè)少數(shù)類分別與2個(gè)主要類極為接近，易受到主類影響.圖4與圖5為采用傳統(tǒng)模糊聚類方法得到的聚類結(jié)果.

圖4傳統(tǒng)模糊聚類方法的中心點(diǎn)變化

由圖4、圖5可知，其中1個(gè)多數(shù)類被誤分為2個(gè)類.究其原因，傳統(tǒng)聚類算法采用隨機(jī)選擇初始中心點(diǎn)，且通常距離真實(shí)聚類中心點(diǎn)距離較遠(yuǎn)(見圖4)，隨著聚類優(yōu)化過程不斷進(jìn)行，聚類中心點(diǎn)逐漸傾向于附近的主要類區(qū)域，造成最后沒有聚類中心點(diǎn)落在少數(shù)類，尤其初始中心點(diǎn)B，最后漂移到附近的多數(shù)類區(qū)域.可以看出，傳統(tǒng)模糊聚類方法在處理非平衡數(shù)據(jù)問題的誤分類率較高.

圖5傳統(tǒng)模糊聚類方法在文獻(xiàn)[7]數(shù)據(jù)集的聚類結(jié)果

相比之下，本研究設(shè)計(jì)的基于密度的聚類方法則始終能保證聚類中心點(diǎn)位于數(shù)據(jù)分布的高密度區(qū)域(見圖6、圖7). 由于本研究采用局部數(shù)據(jù)密度來優(yōu)化模糊聚類，使得聚類中心點(diǎn)能夠以較少的迭代次數(shù)平穩(wěn)地收斂.在聚類迭代次數(shù)上，本方法僅需要13次聚類迭代，而傳統(tǒng)方法則需要30次；在計(jì)算時(shí)間上，本方法依然比傳統(tǒng)方法有優(yōu)勢，具體如表2～表4所示.同時(shí)，本研究進(jìn)一步采用數(shù)據(jù)集ecoli-0-1-4-6來評估模糊聚類算法和基于密度的模糊聚類算法性能.相比于文獻(xiàn)[7]數(shù)據(jù)集，數(shù)據(jù)集ecoli-0-1-4-6空間分布相對較散(見圖8).數(shù)據(jù)分布密度差異不明顯，可通過此類數(shù)據(jù)來評估本研究方法在數(shù)據(jù)空間分布密度差異較小場景下的可用性.由計(jì)算結(jié)果也可以看出，聚類方法在此類數(shù)據(jù)集上分類準(zhǔn)確性不高.盡管如此，本研究方法依然能夠達(dá)到比傳統(tǒng)方法更優(yōu)的結(jié)果(見表3、表4).

圖6基于密度聚類過程的中心點(diǎn)變化

圖7本研究方法的聚類結(jié)果

表2 聚類計(jì)算迭代次數(shù)評估

表3 計(jì)算時(shí)間評估

表4 聚類準(zhǔn)確性比較

圖8數(shù)據(jù)集ecoli-0-1-4-6的低維分布

3 結(jié) 語

針對非平衡數(shù)據(jù)聚類少數(shù)類消失問題，本研究提出并設(shè)計(jì)了一種新的模糊聚類算法，該方法采用數(shù)據(jù)分布密度進(jìn)行聚類初始點(diǎn)選擇，旨在解決非平衡數(shù)據(jù)分布造成聚類準(zhǔn)確率低的問題.同時(shí)，本研究進(jìn)一步將密度分布應(yīng)用于模糊聚類優(yōu)化過程，提升了聚類算法計(jì)算性能.數(shù)據(jù)集上的測試結(jié)果表明，本方法確實(shí)能夠提升非平衡數(shù)據(jù)聚類性能，而且能有效降低聚類迭代次數(shù)，展示出了處理大數(shù)據(jù)的潛力.

[1]Clark M C,Hall L O,Goldgof D B，et al.Mrisegmentationusingfuzzyclusteringtechniques[J].IEEE Eng Med Biol,1994，13(5):730-742.

[2]Beyan C,Fisher R.Classifyingimbalanceddatasetsusingsimilaritybasedhierarchicaldecomposition[J].Pattern Recogn，2015，48(5)：1653-1672.

[3]Noordam J C,Van den Broek W H A M，Buydens L M C,et al.Multivariateimagesegmentationwithclustersizeinsensitivefuzzyc-means[J].Chemometr Intell Lab Syst，2002，64(1)：65-78.

[4]Bensaid A M,Hall L O,Bezdek J,et al.Partiallysupervisedclusteringforimagesegmentation[J].Pattern Recogn，1996，29(5)：859-871.

[5]Gath I,Geva A.Unsupervisedoptimalfuzzyclustering[J].IEEE Trans Pattern Anal Mach Intell，1989，11(7)：773-781.

[6]Lin P L,Huang P W，Kuo C H,et al.Asize-insensitiveintegrity-basedfuzzyc-meansmethodfordataclustering[J].Pattern Recogn，2014，47(5)：2042-2056.

[7]Rodriguez A，Laio A.Clusteringbyfastsearchandfindofdensitypeaks[J].Science,2014，344(6191):1492-1496.

ImbalancedFuzzyClusteringMethodBasedonDataDensityPerception

WANGJin1,YOULei1,LIZhongwen1,MIAOFang2

(1.School of Information Science and Engineering, Chengdu University, Chengdu 610106, China; 2.Institute of Big Data, Chengdu University, Chengdu 610106, China)

Imbalanced data analysis is a key part in biomedical areas but poses a computational challenge for clustering methods due to the huge differences in the distribution between categories.This paper discusses the effects of imbalanced datasets on fuzzy clustering method based on imbalanced data clustering,and proposes a data-density-aware fuzzy clustering method to solve this problem.Specifically,a dataset is segmented into different areas with similar local density,and then a novel fuzzy clustering algorithm is implemented based on the initial partition.As a result,the initial clustering center point can be located and the disappearance of the minority class central point can be avoided.An updated method is further optimized based on data-density-aware fuzzy clustering,which is based on the above mentioned initial density method.The experimental results show that our method can better deal with the disappearance of the minority class in imbalanced datasets classification and compared with the traditional FCM,the clustering algorithm performance of the new FCM is obviously enhanced.

FCM;distribution density;imbalanced dataset

TP301.6

A

1004-5422(2017)04-0373-04

2017-08-25.

四川省教育廳自然科學(xué)基金(17ZA0082)資助項(xiàng)目.

王 進(jìn)(1980 — )，男，博士，講師，從事機(jī)器學(xué)習(xí)相關(guān)技術(shù)研究.