基于復(fù)雜學(xué)習(xí)分類系統(tǒng)的密度聚類方法

黃虹瑋, 葛笑天, 陳烜松

(1.計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))，南京 210023； 2. 江蘇省審計(jì)廳, 南京 210009)

基于復(fù)雜學(xué)習(xí)分類系統(tǒng)的密度聚類方法

黃虹瑋1*, 葛笑天2, 陳烜松2

(1.計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))，南京 210023； 2. 江蘇省審計(jì)廳, 南京 210009)

提出一種基于復(fù)雜學(xué)習(xí)分類系統(tǒng)(XCS)的密度聚類方法，可以用于對(duì)任意形狀且?guī)в性肼暤亩S數(shù)據(jù)進(jìn)行聚類分析。此方法稱為DXCSc，主要包括以下三個(gè)過程：1)基于學(xué)習(xí)分類系統(tǒng)，對(duì)輸入數(shù)據(jù)生成規(guī)則種群，并對(duì)規(guī)則進(jìn)行適當(dāng)壓縮；2)將已經(jīng)生成的規(guī)則視為二維數(shù)據(jù)點(diǎn)，進(jìn)而基于密度聚類思想對(duì)二維數(shù)據(jù)點(diǎn)進(jìn)行聚類；3)對(duì)密度聚類后的規(guī)則種群進(jìn)行適當(dāng)聚合，生成最終的規(guī)則種群。在第一個(gè)過程中，采用學(xué)習(xí)分類系統(tǒng)框架生成規(guī)則種群并進(jìn)行適當(dāng)約減。第二個(gè)過程認(rèn)為種群的各規(guī)則簇中心比它們的鄰居規(guī)則具有更高的密度，并且與密度更高的規(guī)則間距離更大。在第三個(gè)過程中，采用圖分割方法對(duì)相關(guān)重疊簇進(jìn)行適當(dāng)聚合。在實(shí)驗(yàn)中，將所提方法與K-means、近鄰傳播聚類算法(AP)、Voting-XCSc等算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，所提方法在精度方面優(yōu)于對(duì)比算法。

學(xué)習(xí)分類系統(tǒng)；進(jìn)化計(jì)算；強(qiáng)化學(xué)習(xí)；密度聚類；規(guī)則合并

0 引言

學(xué)習(xí)分類系統(tǒng)(Learning Classifier System, LCS)是一個(gè)動(dòng)態(tài)感應(yīng)環(huán)境、模擬認(rèn)知的機(jī)器學(xué)習(xí)系統(tǒng)，它可根據(jù)環(huán)境反饋并通過強(qiáng)化學(xué)習(xí)[1]來評(píng)估種群中的分類規(guī)則，進(jìn)而借助遺傳算法[2-3]對(duì)種群進(jìn)行進(jìn)化，被認(rèn)為是最常用的基于規(guī)則的學(xué)習(xí)工具之一?；贚CS框架，Wilson提出了復(fù)雜學(xué)習(xí)分類系統(tǒng)(eXtended Classifier System，XCS)[4]和實(shí)值復(fù)雜學(xué)習(xí)分類系統(tǒng)(complex real Learning Classifier System, XCSR)[5]，以處理樣本連續(xù)實(shí)值屬性問題。近年來，已有一些工作通過利用XCS進(jìn)行聚類等無監(jiān)督學(xué)習(xí)研究: Shi等[6]提出了一種基于多規(guī)則表示的XCS聚類算法， 每個(gè)數(shù)據(jù)點(diǎn)由規(guī)則對(duì)表示，并迭代合并包含共同數(shù)據(jù)點(diǎn)的規(guī)則; Shi等[7]還提出了一種名為XCSc(XCS clustering)的聚類方法，該方法采用基于多規(guī)則的表示法，通過隨機(jī)生成幾個(gè)規(guī)則來初始化每個(gè)數(shù)據(jù)點(diǎn), 同時(shí)，受Chameleon算法中使用的分層策略的啟發(fā)，XCSc采用基于圖的規(guī)則合并方法，能夠處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)集; Qian等[8]提出一種基于多輪投票的XCSc(Voting-XCSc)聚類方法，可以實(shí)現(xiàn)自動(dòng)確定聚類簇?cái)?shù)量。Voting-XCSc算法在XCSc[7]算法基礎(chǔ)上演變而來，二者區(qū)別如圖1所示。在Voting-XCSc中，當(dāng)有新數(shù)據(jù)來自環(huán)境時(shí)，系統(tǒng)將自動(dòng)檢查整個(gè)規(guī)則種群，對(duì)于新數(shù)據(jù)，Voting-XCSc會(huì)基于一定規(guī)則生成規(guī)則匹配集，并計(jì)算規(guī)則匹配集中每條規(guī)則的相應(yīng)獎(jiǎng)勵(lì)，之后Voting-XCSc通過強(qiáng)化學(xué)習(xí)機(jī)制更新規(guī)則的相應(yīng)參數(shù)。Voting-XCSc 屬于無監(jiān)督學(xué)習(xí)，一般在沒有外部輸入的情況下對(duì)未標(biāo)記數(shù)據(jù)進(jìn)行聚類分析。通過若干輪(需要設(shè)定最大學(xué)習(xí)次數(shù))學(xué)習(xí)，Voting-XCSc對(duì)規(guī)則進(jìn)行合并整合，從而生成規(guī)則集群，最后為每個(gè)新數(shù)據(jù)確定相應(yīng)的集群。 Voting-XCSc算法雖然可以自動(dòng)確定聚類數(shù)目，但需要進(jìn)行多輪學(xué)習(xí)，算法效率較低。

圖1 Voting-XCSc算法與XCSc算法區(qū)別示意圖Fig. 1 Difference diagram between Voting-XCSc and XCSc

近鄰傳播聚類算法(Affinity Propagation, AP)[8]將所有的數(shù)據(jù)點(diǎn)視為候選的簇代表點(diǎn)，避免聚類結(jié)果受限于初始簇代表點(diǎn)的選擇，同時(shí)對(duì)于相似度矩陣的對(duì)稱性沒有要求。AP算法較為成功的特點(diǎn)是能夠自動(dòng)產(chǎn)生合理的聚類簇?cái)?shù)目，在數(shù)據(jù)比較充足的情況下，AP能夠準(zhǔn)確地找出聚類代表點(diǎn)，其最終所獲得的聚類效果往往也較為理想。然而，雖然AP算法同樣解決了預(yù)先人為設(shè)定聚類簇?cái)?shù)目的問題，但需要進(jìn)行多輪迭代計(jì)算，同時(shí)由于AP算法是基于中心的聚類方法，它與其他基于中心的聚類方法一樣，在緊湊的具有超球形分布的數(shù)據(jù)集上具有較好的聚類性能，但并不適合任意形狀聚類問題。

為避免預(yù)先人為設(shè)定聚類簇?cái)?shù)目，同時(shí)對(duì)任意形狀的數(shù)據(jù)取得良好聚類效果，并保證一定的聚類算法效率，以適應(yīng)未來流數(shù)據(jù)在線聚類需求，本文提出一種基于復(fù)雜學(xué)習(xí)分類系統(tǒng)(XCS)的密度聚類方法(Density XCS clustering， DXCSc)，主要貢獻(xiàn)在于可自動(dòng)確定聚類數(shù)目，聚類精度優(yōu)于Voting-XCSc、AP等算法，且算法復(fù)雜度低于Voting-XCSc和AP算法。本算法以學(xué)習(xí)分類系統(tǒng)算法XCSc為框架，運(yùn)用規(guī)則種群概念代表數(shù)據(jù)點(diǎn)集合，有效降低了表示大規(guī)模數(shù)據(jù)的復(fù)雜度，同時(shí)運(yùn)用CFSFDP(Clustering by Fast Search and Find of Density Peaks) 算法[10]將各條規(guī)則重新視為二維數(shù)據(jù)點(diǎn)進(jìn)行密度聚類，有效避免了Voting-XCSc、AP算法的多輪學(xué)習(xí)，取得良好的聚類效果。

1 密度聚類學(xué)習(xí)分類系統(tǒng)框架與學(xué)習(xí)機(jī)制

本文提出的DXCSc算法(如圖2所示)與Voting-XCSc算法的主要不同在于：DXCSc算法不需要預(yù)先設(shè)定最大聚類數(shù)目，且不用進(jìn)行kmax作為限定運(yùn)算次數(shù)下的多輪計(jì)算，算法復(fù)雜度低于Voting-XCSc算法。 DXCSc算法框圖如圖2所示。

圖2 DXCSc 算法框圖Fig. 2 Diagram of DXCSc

本文在XCSc算法框架基礎(chǔ)上，當(dāng)新的數(shù)據(jù)來到并對(duì)應(yīng)生成相關(guān)規(guī)則集合后，通過對(duì)重復(fù)冗余規(guī)則進(jìn)行壓縮，初步形成規(guī)則種群; 之后本文創(chuàng)新性地提出，將規(guī)則種群中的規(guī)則再次視為二維數(shù)據(jù)點(diǎn)，用對(duì)規(guī)則點(diǎn)的聚類取代對(duì)原始數(shù)據(jù)點(diǎn)的聚類，一條規(guī)則可代表大量數(shù)據(jù)點(diǎn)，從而可大量減少聚類所需計(jì)算量，并后續(xù)存在將高維數(shù)據(jù)降至低維的可能。其中對(duì)于每一個(gè)規(guī)則數(shù)據(jù)點(diǎn)i，計(jì)算i的局部密度ρi和與更高密度點(diǎn)之間的距離δi，二者定義如下所示：

(1)

(2)

其中，χ<0時(shí)，χ(x)=1，當(dāng)χ≥0時(shí)，χ(x)=0，其中dij是規(guī)則點(diǎn)i與規(guī)則點(diǎn)j之間的距離，dc是用戶指定的一個(gè)距離參數(shù)；ρi代表與規(guī)則點(diǎn)i距離小于δi的規(guī)則總數(shù)。式(2)中，δi代表了距離規(guī)則點(diǎn)i最近且密度大于規(guī)則點(diǎn)i的規(guī)則點(diǎn)j與i之間的距離。

ECi=(δi)≥2σ(δi)

(3)

LCi=ECi≥μ(ρi)

(4)

1.1 規(guī)則聚合(Merge)

在1.1節(jié)中，滿足ECi、LCi條件而生成的初始子類數(shù)目較多，本文算法采用Chameleon算法[11]對(duì)初始子類間距離進(jìn)行了式(5)、(6)相關(guān)計(jì)算，主要進(jìn)行類間相似性衡量比較，進(jìn)而將相似性聚類子類進(jìn)行合并得到最終聚類結(jié)果。Chameleon算法在融合子類的過程中，既考慮兩個(gè)類之間的相對(duì)緊密情況RIij(類i與類j之間的相對(duì)互連性)，又考慮兩個(gè)類的內(nèi)部連接情況RCij(類i與類j之間的相對(duì)近似性)。

RIij=AIij/[(AIi+AIj)/2]

(5)

(6)

其中：AIij(絕對(duì)互連性)是將圖Gi中點(diǎn)連接到圖Gj中點(diǎn)的邊權(quán)重之和。AIi或AIj(絕對(duì)內(nèi)部互連)是屬于圖Gi或圖Gj的最小切分平分線的邊的權(quán)重之和。ACij(絕對(duì)近似性)是將圖Gi中的點(diǎn)連接到圖Gj中點(diǎn)的邊平均權(quán)重。ACi或ACj(絕對(duì)內(nèi)部接近度)是屬于圖Gi或圖Gj最小切分平分線的邊平均權(quán)重。

DXCSc算法具體內(nèi)容如下所示：

輸入：X={X1,X2,…,Xn}無監(jiān)督數(shù)據(jù)集;dc計(jì)算局部密度ρi所需半徑;

輸出：C={C1,C2,…,Ck}簇集合。

算法過程1：基于學(xué)習(xí)分類系統(tǒng)框架，通過強(qiáng)化學(xué)習(xí)及遺傳學(xué)習(xí)模塊，對(duì)輸入數(shù)據(jù)生成規(guī)則種群，并對(duì)規(guī)則進(jìn)行適當(dāng)壓縮。

算法過程2：對(duì)規(guī)則種群進(jìn)行密度聚類。

2.1)計(jì)算各規(guī)則的局部密度ρ和δ。

2.2)采用Fuzzy-CFSFDP方法確定簇中心。

2.3)將每個(gè)規(guī)則劃歸至與其距離最近且局部密度更高的規(guī)則種群中。

算法過程3：對(duì)規(guī)則種群進(jìn)行適當(dāng)聚合。

3.1)對(duì)2.3)步驟中生成的規(guī)則種群中的每一對(duì)規(guī)則{Ci,Cj}，計(jì)算RI{Ci,Cj}*RC{Ci,Cj}α。

3.2)將具有最高RI{Ci,Cj}*RC{Ci,Cj}α值的規(guī)則對(duì){Ci,Cj}合并。

3.3)重復(fù)3.1)、3.2)步，直至終止條件達(dá)到。

2 實(shí)驗(yàn)結(jié)果和分析

2.1 實(shí)驗(yàn)設(shè)置

對(duì)于實(shí)驗(yàn)中的參數(shù)設(shè)置，本文遵循Voting-XCSc[8]中對(duì)應(yīng)參數(shù)的相同值進(jìn)行公平比較。種群最大規(guī)則數(shù)設(shè)為1 000，學(xué)習(xí)率設(shè)為0.2，遺傳算法中突變和交叉的概率分別為0.001和0.8，用于計(jì)算精度的參數(shù)α和v分別設(shè)置為0.1和5。此外，根據(jù)CFSFDP[9]中分析，通過選擇適當(dāng)?shù)膮?shù)dc使得平均鄰居數(shù)量在整個(gè)數(shù)據(jù)集中占比約1%至2%即可，因?yàn)樵跊Q策圖中選擇簇中心主要取決于數(shù)據(jù)點(diǎn)密度和高密度距離的相對(duì)關(guān)系，而不是絕對(duì)值，因此dc的選擇對(duì)最終聚類效果影響不大。實(shí)驗(yàn)計(jì)算機(jī)環(huán)境為：處理器為2.3 GHz Intel Core i5，內(nèi)存為8 GB 1 600 MHz DDR3，硬盤為320 GB，操作系統(tǒng)為Mac OS X EI Capitan，編程語(yǔ)言為Java、C++和Matlab。

2.2 典型數(shù)據(jù)集實(shí)驗(yàn)分析

本文首先使用Flame[13]、Aggregation[14]、D31[15]、R15[15]等典型數(shù)據(jù)集，測(cè)試并對(duì)比本文提出的DXCSc算法聚類效果。Flame數(shù)據(jù)集包含240個(gè)二維數(shù)據(jù)點(diǎn)，可分為2簇；Aggregation數(shù)據(jù)集包含788個(gè)二維數(shù)據(jù)點(diǎn)，可分為7簇；D31數(shù)據(jù)集包含3 100個(gè)二維數(shù)據(jù)點(diǎn)，可分為31簇；R15數(shù)據(jù)集包含600個(gè)二維數(shù)據(jù)點(diǎn)，可分為15簇。

如圖3所示，DXCSc算法可以在無預(yù)先簇?cái)?shù)目輸入的情況下對(duì)任意形狀的二維數(shù)據(jù)Flame Data進(jìn)行有效聚類。

圖3 DXCSc算法在Flame[13]數(shù)據(jù)集上聚類效果Fig. 3 DXCSc clustering effects on dataset Flame[13]

如圖4所示，K-means算法在預(yù)先輸入簇?cái)?shù)目(kmax=2)情況下，對(duì)任意形狀的二維數(shù)據(jù)Flame Data聚類效果不是很好。

圖4 K-means算法在Flame[13]數(shù)據(jù)集上聚類效果Fig. 4 K-means clustering effects on dataset Flame[13]

如圖5所示，AP算法雖然同樣不需要預(yù)先設(shè)定簇?cái)?shù)目，但對(duì)任意形狀的二維數(shù)據(jù)Flame Data聚類效果也不好。此外，本文將上述算法分別在Aggregation[14]、D31[15]、R15[15]數(shù)據(jù)集上進(jìn)行了測(cè)試比對(duì)，實(shí)驗(yàn)結(jié)果表明: DXCSc算法在任意形狀分布數(shù)據(jù)集Flame和超球形分布數(shù)據(jù)集D31、R15上都具有較好的聚類性能; 而K-means、AP算法只在超球形分布數(shù)據(jù)集上具有較好聚類性能，對(duì)任意形狀數(shù)據(jù)集聚類效果不好。

圖5 AP算法在Flame[13]數(shù)據(jù)集上聚類效果Fig. 5 AP clustering effects on dataset Flame[13]

如表1所示，本文對(duì)DXCSc、K-means、AP以及Voting-XCSc算法在上述數(shù)據(jù)集上的聚類精度(Fitness)進(jìn)行了比較，如表中結(jié)果所示，DXCSc在任意形狀的二維數(shù)據(jù)集上可以取得良好的聚類效果。

表1 聚類精度比較(典型數(shù)據(jù)集)Tab. 1 Comparison of clustering fitness on typical data sets

與此同時(shí)，為確保評(píng)價(jià)指標(biāo)的科學(xué)性，本文采用NMI(Normalized Mutual Information)評(píng)價(jià)指標(biāo)對(duì)DXCSc、K-means、AP以及Voting-XCSc算法在上述數(shù)據(jù)集上的聚類效果進(jìn)行了比較(如表2所示)，該指標(biāo)可用于衡量?jī)蓚€(gè)數(shù)據(jù)分布的吻合程度，取值范圍為[0，1]，該值越大表明聚類結(jié)果與真實(shí)情況越吻合。

表2 聚類NMI比較(典型數(shù)據(jù)集)Tab. 2 Comparison of NMI on typical data sets

2.3 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)分析

本文采用UCI中的Iris、Wine、Ionosphere、Letter[16]等真實(shí)數(shù)據(jù)集對(duì)上述算法進(jìn)行了進(jìn)一步驗(yàn)證。其中，Iris為鳶尾花卉數(shù)據(jù)集(數(shù)據(jù)實(shí)例數(shù)N=150，數(shù)據(jù)維度D=4，聚類簇?cái)?shù)K=3)，是一類多重變量分析的數(shù)據(jù)集，可通過花萼長(zhǎng)度、花萼寬度、花瓣長(zhǎng)度、花瓣寬度4個(gè)屬性預(yù)測(cè)鳶尾花卉屬于Setosa、Versicolour、Virginica三個(gè)種類中的哪一類。Wine數(shù)據(jù)集(N=178，D=13，K=3)包含來自3種不同起源的葡萄酒的共178條記錄，數(shù)據(jù)集中13個(gè)屬性是葡萄酒的13種化學(xué)成分，通過化學(xué)分析可以來推斷葡萄酒的起源。Ionosphere數(shù)據(jù)集(N=351，D=34，K=2)根據(jù)給定的電離層中的自由電子的雷達(dá)回波預(yù)測(cè)大氣結(jié)構(gòu)。Letter Recognition數(shù)據(jù)集(N=20 000，D=16，K=2)將大量的黑白矩形像素顯示的每一個(gè)字符標(biāo)識(shí)為英文字母表中的26個(gè)大寫字母之一。

如表3所示，K-means算法在事先指定聚類簇?cái)?shù)量k的情況下，聚類精度一般優(yōu)于AP和DXCSc算法。在不指定聚類簇?cái)?shù)量k的條件下，DXCSc算法精度優(yōu)于AP算法。上述算法在未進(jìn)行大量參數(shù)調(diào)整實(shí)驗(yàn)情況下，對(duì)真實(shí)數(shù)據(jù)的聚類效果并不是很好。

表3 聚類精度比較(真實(shí)數(shù)據(jù)集)Tab. 3 Comparison of clustering fitness on real data sets

2.4 算法復(fù)雜度分析

在DXCSc算法過程1中，當(dāng)有新數(shù)據(jù)輸入時(shí)，學(xué)習(xí)分類系統(tǒng)遍歷整個(gè)種群并更新相關(guān)規(guī)則參數(shù)，算法復(fù)雜度為O(n)，其中n為數(shù)據(jù)點(diǎn)數(shù)；在算法過程2中，需要O(n2)的時(shí)間來建立距離矩陣，得出任意兩點(diǎn)間的距離，并計(jì)算局部密度ρ和δ；在算法過程3中，算法運(yùn)行時(shí)間主要消耗在簇與簇之間的相似度計(jì)算和簇的融合更新之中，此部分算法復(fù)雜度為O(nlogn)。綜合分析，DXCSc的算法復(fù)雜度為O(n2+nlogn)。K-means算法優(yōu)點(diǎn)是簡(jiǎn)單實(shí)用，確定的k個(gè)劃分到達(dá)平方誤差最小，該算法當(dāng)聚類是密集的，且類與類之間區(qū)別明顯時(shí)，效果較好。對(duì)于處理大數(shù)據(jù)集，K-means算法相對(duì)可伸縮和高效的，計(jì)算的復(fù)雜度為O(nkt)(其中n是數(shù)據(jù)對(duì)象的數(shù)目，t是迭代的次數(shù)，k為簇?cái)?shù)目);雖然K-means算法復(fù)雜度相對(duì)較低，但需要用戶預(yù)先設(shè)定聚類簇?cái)?shù)目k，存在一定局限性。AP算法復(fù)雜度較高，為O(n2logn)。

基于上述分析，本文對(duì)實(shí)驗(yàn)所耗時(shí)間進(jìn)行了比較分析，結(jié)果如表4所示。AP算法復(fù)雜度較高，耗時(shí)較長(zhǎng)，K-means算法與DXCSc算法耗時(shí)較為接近。

表4 聚類時(shí)間比較 sTab. 4 Comparison of clustering time s

2.5 討論

本文提出的DXCSc算法在任意形狀的二維分布數(shù)據(jù)集上能夠取得良好的聚類效果，主要取決于以下幾個(gè)因素：首先，DXCSc采用學(xué)習(xí)分類系統(tǒng)框架后用規(guī)則代替原始二維數(shù)據(jù)點(diǎn)的表示方法，有效降低了數(shù)據(jù)表示的復(fù)雜度。具體如下，在DXCSc中，使用矩形作為規(guī)則的表示形式以處理連續(xù)值。規(guī)則可表示為(Ci,Si)(i=1，2，…，d)，其中Ci為數(shù)據(jù)點(diǎn)的中心，Si為拓展半徑。當(dāng)一個(gè)數(shù)據(jù)點(diǎn)Ii滿足Ci-Si≤Ii≤Ci+Si時(shí)，則該點(diǎn)可由規(guī)則(Ci,Si)表示。通過上述處理，海量的二維數(shù)據(jù)點(diǎn)就可以通過合并約減后的規(guī)則種群來表示，如圖6所示。

圖6 規(guī)則種群降低數(shù)據(jù)表示復(fù)雜度示意圖Fig. 6 Diagram of reducting data representation complexity by rule population

其次，DXCSc將合并約減后的規(guī)則再次表示為二維數(shù)據(jù)點(diǎn)(如圖7所示)，并應(yīng)用密度聚類思想將上述數(shù)據(jù)點(diǎn)進(jìn)行快速聚類，從而可以將Voting-XCSc的多輪學(xué)習(xí)轉(zhuǎn)化為了單輪學(xué)習(xí)，避免了對(duì)原始數(shù)據(jù)的多次遍歷。

圖7 規(guī)則種群密度聚類示意圖Fig. 7 Diagram of clustering rule population density

3 結(jié)語(yǔ)

本文提出了一個(gè)新的基于學(xué)習(xí)分類系統(tǒng)的密度聚類方法(DXCSc)，用于研究學(xué)習(xí)分類系統(tǒng)在無監(jiān)督環(huán)境下的聚類效果。DXCSc聚類方法的主要流程包含3個(gè)階段:第一，DXCSc基于學(xué)習(xí)分類系統(tǒng)框架，通過強(qiáng)化學(xué)習(xí)及遺傳學(xué)習(xí)模塊，對(duì)輸入數(shù)據(jù)生成規(guī)則種群，并對(duì)規(guī)則進(jìn)行適當(dāng)壓縮；第二，DXCSc對(duì)規(guī)則種群進(jìn)行密度聚類；第三，對(duì)規(guī)則種群進(jìn)行適當(dāng)聚合，生成最終的規(guī)則種群。本文通過一些數(shù)據(jù)集的無監(jiān)督聚類實(shí)驗(yàn)說明了DXCSc的學(xué)習(xí)過程與效果。實(shí)驗(yàn)結(jié)果表明， DXCSc能夠在不提前設(shè)定簇?cái)?shù)量k的前提下，對(duì)無監(jiān)督的典型二維數(shù)據(jù)取得較好的聚類效果，聚類精度優(yōu)于AP、Voting-XCSc等算法。

下一步的工作有:首先，基于學(xué)習(xí)分類系統(tǒng)框架具有適應(yīng)在線學(xué)習(xí)環(huán)境的特點(diǎn)，嘗試把DXCS運(yùn)用到二維流數(shù)據(jù)在線聚類中，并與一些更為復(fù)雜的流數(shù)據(jù)聚類算法比較性能。其次，設(shè)計(jì)面向流數(shù)據(jù)的Online Voting-XCSc算法。此外，可進(jìn)一步將DXCSc算法擴(kuò)展為面向高維數(shù)據(jù)以及高維流數(shù)據(jù)的聚類算法。

References)

[1] SUTTON R S, BARTO A G. Reinforcement Learning: an Introduction [M]. Cambridge: MIT Press, 1998:1.

[2] HOLLAND J H. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control and Artificial Intelligence[M]. Cambridge: MIT Press, 1992: 90-118.

[3] GOLDBERG D E. Genetic algorithm in search, optimization, and machine learning [EB/OL].[2016- 11- 20].http://www.openisbn.com/download/0201157675.pdf.

[4] WILSON S W. Classifier fitness based on accuracy [J]. Evolutionary Computation, 1995, 3(2): 149-175.

[5] WILSON S W. Get real! XCS with continuous-valued inputs[C]// Learning Classifier Systems, From Foundations to Applications. London: Springer-Verlag, 2000: 209-222.

[6] SHI L, SHI Y, GAO Y. Clustering with XCS and agglomerative rule merging[C]// Proceedings of the 10th International Conference on Intelligent Data Engineering and Automated Learning. Berlin: Springer-Verlag, 2009: 242-250.

[7] SHI L, SHI Y, GAO Y, et al. XCSc: a novel approach to clustering with extended classifier system[J]. International Journal of Neural Systems, 2011, 21(1): 79-93.

[8] QIAN L, SHI Y, GAO Y, et al. Voting-XCSc: a consensus clustering method via learning classifier system[C]// Proceedings of the 14th International Conference on Intelligent Data Engineering and Automated Learning. Berlin: Springer, 2013: 603-610.

[9] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814):972-976.

[10] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014,344(6191): 1492-1496.

[11] MEHMOOD R, BIE R, DAWOOD H, et al. Fuzzy clustering by fast search and find of density peaks[C]// Proceedings of the 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things. Piscataway, NJ: IEEE, 2015: 258-261.

[12] KARYPIS G, HAN E H, KUMAR V. Chameleon: hierarchical clustering using dynamic modeling[J]. Computer, 2002, 32(8): 68-75.

[13] FU L, MEDICO E. FLAME, a novel fuzzy clustering method for the analysis of DNA microarray data[J]. BMC Bioinformatics, 2007, 8(1): 3.

[14] GIONIS A, MANNILA H, TSAPARAS P. Clustering aggregation[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 1-30.

[15] VEENMAN C J, REINDERS M J T, BACKER E. A maximum variance cluster algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(9): 1273-1280.

[16] BLAKE C L, KEOGH E, MERZ C J. UCI repository of machine learning databases[DB/OL].[2016- 11- 20].https://archive.ics.uci.edu/ml/datasets.html.

This work is partially supported by the Key Research and Development Program (Industry Forward and Common Key Technology) Project of Jiangsu Province (BE2015213).

HUANGHongwei,born in 1986, Ph. D. candidate. His research interests include online clustering, learning classifier system.

GEXiaotian, born in 1963, M. S., senior auditors. His research interests include government affairs data, audit information.

CHENXuansong, born in 1971, M. S., senior auditors. His research interests include audit big data applications, multidimensional data analysis.

Densityclusteringmethodbasedoncomplexlearningclassificationsystem

HUANG Hongwei1*, GE Xiaotian2, CHEN Xuansong2

(1.StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),NanjingJiangsu210023,China;2.JiangsuProvincialAuditOffice,NanjingJiangsu210009,China)

A density clustering method based on eXtended Classifier Systems (XCS) was proposed, which could be used to cluster the two-dimensional data sets with arbitrary shapes and noises. The proposed method was called Density XCS Clustering (DXCSc), which mainly included the following three processes:1) Based on the learning classification system, regular population of input data was generated and compressed. 2) The generated rules were regarded as two-dimensional data points, and then the two-dimensional data points were clustered based on idea of density clustering. 3) The regular population after density clustering was properly aggregated to generate the final regular population. In the first process, the learning classifier system framework was used to generate and compact the regular population. In the second process, the rule cluster centers were characterized by a higher density than their neighbors and by a relatively large distance from points with higher densities. In the third process, the relevant clusters were properly merged using the graph segmentation method. In the experiments, the proposed DXCSc was compared withK-means, Affinity Propagation (AP) and Voting-XCSc on a number of challenging data sets. The experimental results show that the proposed approach outperformsK-means and Voting-XCSc in precision.

Learning Classifier System (LCS); evolutionary computing; reinforcement learning; density clustering; rule merging

2017- 05- 11;

2017- 07- 05。

江蘇省重點(diǎn)研發(fā)計(jì)劃(產(chǎn)業(yè)前瞻與共性關(guān)鍵技術(shù))項(xiàng)目(BE2015213)。

黃虹瑋(1986—)，男，陜西漢中人，博士研究生，主要研究方向：在線聚類、學(xué)習(xí)分類系統(tǒng)； 葛笑天 (1963—)，男，江蘇徐州人，高級(jí)審計(jì)師，碩士，CCF會(huì)員，主要研究方向：政務(wù)大數(shù)據(jù)、審計(jì)信息化； 陳烜松(1971—)，男，江蘇南京人，高級(jí)審計(jì)師，碩士，主要研究方向：審計(jì)大數(shù)據(jù)應(yīng)用、多維數(shù)據(jù)分析。

1001- 9081(2017)11- 3207- 05

10.11772/j.issn.1001- 9081.2017.11.3207

(*通信作者電子郵箱godenrainbowjade@gmail.com)

TP181

A