基于復雜學習分類系統的密度聚類方法

黃虹瑋, 葛笑天, 陳烜松

(1.計算機軟件新技術國家重點實驗室(南京大學)，南京 210023； 2. 江蘇省審計廳, 南京 210009)

基于復雜學習分類系統的密度聚類方法

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

(1.計算機軟件新技術國家重點實驗室(南京大學)，南京 210023； 2. 江蘇省審計廳, 南京 210009)

提出一種基于復雜學習分類系統(XCS)的密度聚類方法，可以用于對任意形狀且帶有噪聲的二維數據進行聚類分析。此方法稱為DXCSc，主要包括以下三個過程：1)基于學習分類系統，對輸入數據生成規則種群，并對規則進行適當壓縮；2)將已經生成的規則視為二維數據點，進而基于密度聚類思想對二維數據點進行聚類；3)對密度聚類后的規則種群進行適當聚合，生成最終的規則種群。在第一個過程中，采用學習分類系統框架生成規則種群并進行適當約減。第二個過程認為種群的各規則簇中心比它們的鄰居規則具有更高的密度，并且與密度更高的規則間距離更大。在第三個過程中，采用圖分割方法對相關重疊簇進行適當聚合。在實驗中，將所提方法與K-means、近鄰傳播聚類算法(AP)、Voting-XCSc等算法進行了比較，實驗結果表明，所提方法在精度方面優于對比算法。

學習分類系統；進化計算；強化學習；密度聚類；規則合并

0 引言

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

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

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

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

1 密度聚類學習分類系統框架與學習機制

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

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

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

(1)

(2)

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

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

(3)

LCi=ECi≥μ(ρi)

(4)

1.1 規則聚合(Merge)

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

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

(5)

(6)

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

DXCSc算法具體內容如下所示：

輸入：X={X1,X2,…,Xn}無監督數據集;dc計算局部密度ρi所需半徑;

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

算法過程1：基于學習分類系統框架，通過強化學習及遺傳學習模塊，對輸入數據生成規則種群，并對規則進行適當壓縮。

算法過程2：對規則種群進行密度聚類。

2.1)計算各規則的局部密度ρ和δ。

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

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

算法過程3：對規則種群進行適當聚合。

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

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

3.3)重復3.1)、3.2)步，直至終止條件達到。

2 實驗結果和分析

2.1 實驗設置

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

2.2 典型數據集實驗分析

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

如圖3所示，DXCSc算法可以在無預先簇數目輸入的情況下對任意形狀的二維數據Flame Data進行有效聚類。

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

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

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

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

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

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

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

與此同時，為確保評價指標的科學性，本文采用NMI(Normalized Mutual Information)評價指標對DXCSc、K-means、AP以及Voting-XCSc算法在上述數據集上的聚類效果進行了比較(如表2所示)，該指標可用于衡量兩個數據分布的吻合程度，取值范圍為[0，1]，該值越大表明聚類結果與真實情況越吻合。

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

2.3 真實數據集實驗分析

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

如表3所示，K-means算法在事先指定聚類簇數量k的情況下，聚類精度一般優于AP和DXCSc算法。在不指定聚類簇數量k的條件下，DXCSc算法精度優于AP算法。上述算法在未進行大量參數調整實驗情況下，對真實數據的聚類效果并不是很好。

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

2.4 算法復雜度分析

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

基于上述分析，本文對實驗所耗時間進行了比較分析，結果如表4所示。AP算法復雜度較高，耗時較長，K-means算法與DXCSc算法耗時較為接近。

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

2.5 討論

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

圖6 規則種群降低數據表示復雜度示意圖Fig. 6 Diagram of reducting data representation complexity by rule population

其次，DXCSc將合并約減后的規則再次表示為二維數據點(如圖7所示)，并應用密度聚類思想將上述數據點進行快速聚類，從而可以將Voting-XCSc的多輪學習轉化為了單輪學習，避免了對原始數據的多次遍歷。

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

3 結語

本文提出了一個新的基于學習分類系統的密度聚類方法(DXCSc)，用于研究學習分類系統在無監督環境下的聚類效果。DXCSc聚類方法的主要流程包含3個階段:第一，DXCSc基于學習分類系統框架，通過強化學習及遺傳學習模塊，對輸入數據生成規則種群，并對規則進行適當壓縮；第二，DXCSc對規則種群進行密度聚類；第三，對規則種群進行適當聚合，生成最終的規則種群。本文通過一些數據集的無監督聚類實驗說明了DXCSc的學習過程與效果。實驗結果表明， DXCSc能夠在不提前設定簇數量k的前提下，對無監督的典型二維數據取得較好的聚類效果，聚類精度優于AP、Voting-XCSc等算法。

下一步的工作有:首先，基于學習分類系統框架具有適應在線學習環境的特點，嘗試把DXCS運用到二維流數據在線聚類中，并與一些更為復雜的流數據聚類算法比較性能。其次，設計面向流數據的Online Voting-XCSc算法。此外，可進一步將DXCSc算法擴展為面向高維數據以及高維流數據的聚類算法。

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。

江蘇省重點研發計劃(產業前瞻與共性關鍵技術)項目(BE2015213)。

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

1001- 9081(2017)11- 3207- 05

10.11772/j.issn.1001- 9081.2017.11.3207

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

TP181

A