黃虹瑋, 葛笑天, 陳烜松

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

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

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

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

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

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

0 引言

學(xué)習(xí)分類系統(tǒng)(Learning Classifier System, LCS)是一個動態(tài)感應(yīng)環(huán)境、模擬認(rèn)知的機(jī)器學(xué)習(xí)系統(tǒng)，它可根據(jù)環(huán)境反饋并通過強(qiáng)化學(xué)習(xí)[1]來評估種群中的分類規(guī)則，進(jìn)而借助遺傳算法[2-3]對種群進(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聚類算法， 每個數(shù)據(jù)點(diǎn)由規(guī)則對表示，并迭代合并包含共同數(shù)據(jù)點(diǎn)的規(guī)則; Shi等[7]還提出了一種名為XCSc(XCS clustering)的聚類方法，該方法采用基于多規(guī)則的表示法，通過隨機(jī)生成幾個規(guī)則來初始化每個數(shù)據(jù)點(diǎn), 同時，受Chameleon算法中使用的分層策略的啟發(fā)，XCSc采用基于圖的規(guī)則合并方法，能夠處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)集; Qian等[8]提出一種基于多輪投票的XCSc(Voting-XCSc)聚類方法，可以實(shí)現(xiàn)自動確定聚類簇?cái)?shù)量。Voting-XCSc算法在XCSc[7]算法基礎(chǔ)上演變而來，二者區(qū)別如圖1所示。在Voting-XCSc中，當(dāng)有新數(shù)據(jù)來自環(huán)境時，系統(tǒng)將自動檢查整個規(guī)則種群，對于新數(shù)據(jù)，Voting-XCSc會基于一定規(guī)則生成規(guī)則匹配集，并計(jì)算規(guī)則匹配集中每條規(guī)則的相應(yīng)獎勵，之后Voting-XCSc通過強(qiáng)化學(xué)習(xí)機(jī)制更新規(guī)則的相應(yīng)參數(shù)。Voting-XCSc 屬于無監(jiān)督學(xué)習(xí)，一般在沒有外部輸入的情況下對未標(biāo)記數(shù)據(jù)進(jìn)行聚類分析。通過若干輪(需要設(shè)定最大學(xué)習(xí)次數(shù))學(xué)習(xí)，Voting-XCSc對規(guī)則進(jìn)行合并整合，從而生成規(guī)則集群，最后為每個新數(shù)據(jù)確定相應(yīng)的集群。 Voting-XCSc算法雖然可以自動確定聚類數(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)的選擇，同時對于相似度矩陣的對稱性沒有要求。AP算法較為成功的特點(diǎn)是能夠自動產(chǎn)生合理的聚類簇?cái)?shù)目，在數(shù)據(jù)比較充足的情況下，AP能夠準(zhǔn)確地找出聚類代表點(diǎn)，其最終所獲得的聚類效果往往也較為理想。然而，雖然AP算法同樣解決了預(yù)先人為設(shè)定聚類簇?cái)?shù)目的問題，但需要進(jìn)行多輪迭代計(jì)算，同時由于AP算法是基于中心的聚類方法，它與其他基于中心的聚類方法一樣，在緊湊的具有超球形分布的數(shù)據(jù)集上具有較好的聚類性能，但并不適合任意形狀聚類問題。

為避免預(yù)先人為設(shè)定聚類簇?cái)?shù)目，同時對任意形狀的數(shù)據(jù)取得良好聚類效果，并保證一定的聚類算法效率，以適應(yīng)未來流數(shù)據(jù)在線聚類需求，本文提出一種基于復(fù)雜學(xué)習(xí)分類系統(tǒng)(XCS)的密度聚類方法(Density XCS clustering， DXCSc)，主要貢獻(xiàn)在于可自動確定聚類數(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ù)雜度，同時運(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ù)來到并對應(yīng)生成相關(guān)規(guī)則集合后，通過對重復(fù)冗余規(guī)則進(jìn)行壓縮，初步形成規(guī)則種群; 之后本文創(chuàng)新性地提出，將規(guī)則種群中的規(guī)則再次視為二維數(shù)據(jù)點(diǎn)，用對規(guī)則點(diǎn)的聚類取代對原始數(shù)據(jù)點(diǎn)的聚類，一條規(guī)則可代表大量數(shù)據(jù)點(diǎn)，從而可大量減少聚類所需計(jì)算量，并后續(xù)存在將高維數(shù)據(jù)降至低維的可能。其中對于每一個規(guī)則數(shù)據(jù)點(diǎn)i，計(jì)算i的局部密度ρi和與更高密度點(diǎn)之間的距離δi，二者定義如下所示：

(1)

(2)

其中，χ<0時，χ(x)=1，當(dāng)χ≥0時，χ(x)=0，其中dij是規(guī)則點(diǎn)i與規(guī)則點(diǎn)j之間的距離，dc是用戶指定的一個距離參數(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]對初始子類間距離進(jìn)行了式(5)、(6)相關(guān)計(jì)算，主要進(jìn)行類間相似性衡量比較，進(jìn)而將相似性聚類子類進(jìn)行合并得到最終聚類結(jié)果。Chameleon算法在融合子類的過程中，既考慮兩個類之間的相對緊密情況RIij(類i與類j之間的相對互連性)，又考慮兩個類的內(nèi)部連接情況RCij(類i與類j之間的相對近似性)。

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

(5)

(6)

其中：AIij(絕對互連性)是將圖Gi中點(diǎn)連接到圖Gj中點(diǎn)的邊權(quán)重之和。AIi或AIj(絕對內(nèi)部互連)是屬于圖Gi或圖Gj的最小切分平分線的邊的權(quán)重之和。ACij(絕對近似性)是將圖Gi中的點(diǎn)連接到圖Gj中點(diǎn)的邊平均權(quán)重。ACi或ACj(絕對內(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í)模塊，對輸入數(shù)據(jù)生成規(guī)則種群，并對規(guī)則進(jìn)行適當(dāng)壓縮。

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

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

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

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

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

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

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

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

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

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

對于實(shí)驗(yàn)中的參數(shù)設(shè)置，本文遵循Voting-XCSc[8]中對應(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ù)量在整個數(shù)據(jù)集中占比約1%至2%即可，因?yàn)樵跊Q策圖中選擇簇中心主要取決于數(shù)據(jù)點(diǎn)密度和高密度距離的相對關(guān)系，而不是絕對值，因此dc的選擇對最終聚類效果影響不大。實(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，編程語言為Java、C++和Matlab。

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

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

如圖3所示，DXCSc算法可以在無預(yù)先簇?cái)?shù)目輸入的情況下對任意形狀的二維數(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)情況下，對任意形狀的二維數(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ù)目，但對任意形狀的二維數(shù)據(jù)Flame Data聚類效果也不好。此外，本文將上述算法分別在Aggregation[14]、D31[15]、R15[15]數(shù)據(jù)集上進(jìn)行了測試比對，實(shí)驗(yàn)結(jié)果表明: DXCSc算法在任意形狀分布數(shù)據(jù)集Flame和超球形分布數(shù)據(jù)集D31、R15上都具有較好的聚類性能; 而K-means、AP算法只在超球形分布數(shù)據(jù)集上具有較好聚類性能，對任意形狀數(shù)據(jù)集聚類效果不好。

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

如表1所示，本文對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

與此同時，為確保評價指標(biāo)的科學(xué)性，本文采用NMI(Normalized Mutual Information)評價指標(biāo)對DXCSc、K-means、AP以及Voting-XCSc算法在上述數(shù)據(jù)集上的聚類效果進(jìn)行了比較(如表2所示)，該指標(biāo)可用于衡量兩個數(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ù)集對上述算法進(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ù)集，可通過花萼長度、花萼寬度、花瓣長度、花瓣寬度4個屬性預(yù)測鳶尾花卉屬于Setosa、Versicolour、Virginica三個種類中的哪一類。Wine數(shù)據(jù)集(N=178，D=13，K=3)包含來自3種不同起源的葡萄酒的共178條記錄，數(shù)據(jù)集中13個屬性是葡萄酒的13種化學(xué)成分，通過化學(xué)分析可以來推斷葡萄酒的起源。Ionosphere數(shù)據(jù)集(N=351，D=34，K=2)根據(jù)給定的電離層中的自由電子的雷達(dá)回波預(yù)測大氣結(jié)構(gòu)。Letter Recognition數(shù)據(jù)集(N=20 000，D=16，K=2)將大量的黑白矩形像素顯示的每一個字符標(biāo)識為英文字母表中的26個大寫字母之一。

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

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

表4 聚類時間比較 sTab. 4 Comparison of clustering time s

2.5 討論

本文提出的DXCSc算法在任意形狀的二維分布數(shù)據(jù)集上能夠取得良好的聚類效果，主要取決于以下幾個因素：首先，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)一個數(shù)據(jù)點(diǎn)Ii滿足Ci-Si≤Ii≤Ci+Si時，則該點(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í)，避免了對原始數(shù)據(jù)的多次遍歷。

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

3 結(jié)語

本文提出了一個新的基于學(xué)習(xí)分類系統(tǒng)的密度聚類方法(DXCSc)，用于研究學(xué)習(xí)分類系統(tǒng)在無監(jiān)督環(huán)境下的聚類效果。DXCSc聚類方法的主要流程包含3個階段:第一，DXCSc基于學(xué)習(xí)分類系統(tǒng)框架，通過強(qiáng)化學(xué)習(xí)及遺傳學(xué)習(xí)模塊，對輸入數(shù)據(jù)生成規(guī)則種群，并對規(guī)則進(jìn)行適當(dāng)壓縮；第二，DXCSc對規(guī)則種群進(jìn)行密度聚類；第三，對規(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的前提下，對無監(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ì)師，碩士，CCF會員，主要研究方向：政務(wù)大數(shù)據(jù)、審計(jì)信息化； 陳烜松(1971—)，男，江蘇南京人，高級審計(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