多目標監督聚類GA研究

索 飛,張洪偉,鄒書蓉

(成都信息工程學院計算機學院,四川 成都 610225)

多目標監督聚類GA研究

索 飛,張洪偉,鄒書蓉

(成都信息工程學院計算機學院,四川 成都 610225)

提出了多目標監督聚類GA算法,即:根據樣本的類標簽有監督地將樣本聚類,在每個類中根據樣本屬性的相似性有監督地聚成類簇.如果分屬不同類標簽的類簇出現相交,則相交類簇再次聚類,直到所有類簇均不相交.適應度矢量函數由類簇數和類內距離2個目標確定,類簇數和類簇中心由目標函數自動確定,從而類簇數和中心就不受主觀因素的影響,并且保證了這2個關鍵要素的優化性質.預測分類時,刪去單點類簇,并根據類簇號和離某個類簇中心距離的最近鄰法則以及該類簇的類標簽進行分類.算法模型采用C#實現,采用3個UCI數據集進行實例分析,實驗結果表明,本算法優于著名的Native Bayes、Boost C4.5和KNN算法.

多目標GA;監督聚類;類標簽;最近鄰法則

0 引 言

近年來,聚類已經成為數據挖掘領域中一個熱門的研究課題[1].一方面,它可以作為一個專門工具來處理數據分布信息;另一方面,也可以作為數據挖掘算法的一個預處理步驟[2].監督聚類分析是聚類分析的一種,它根據樣本的先驗信息或假設來決定樣本的分類,據此建立判別模型,并利用該判別模型對未知對象進行分類.

遺傳算法(Genetic Algorithm,GA)是一類借鑒生物界的進化規律演化而來的隨機化搜索方法.它由美國J.Holland教授首先提出.經過多年的研究、改進,遺傳算法已經被廣泛地應用于組合優化、機器學習及人工生命等領域.現階段,科研人員仍在不斷地研究、改進和拓展遺傳算法的應用領域[3-4].

本研究提出了多目標監督聚類GA算法,該算法主要有以下特點:多目標遺傳算法是自適應全局優化概率搜索算法,具有簡單通用、魯棒性強、適于并行處理的優點.引入適應度矢量函數和擂臺選擇法,而不使用聚集函數法[5-6],從而解決了難以搜索到非凸解的問題[7].由于適應度矢量函數可自動確定類簇數和類簇中心,而不受主觀因素的影響,從而提高預報的可靠性.為減少數據噪聲對學習的影響,采取樣本歸一化處理的方法來提高學習的準確性,并在遺傳優化過程中,采用有效的保憂策略以提高收斂速度和泛化能力.

1 多目標監督聚類GA算法模型

1.1 算法描述

算法的基本思路是:對樣本歸一化處理,根據樣本的類標簽有監督地將樣本分類,在每個類中按樣本屬性的相似性有監督地聚成類簇,如果分屬不同類標簽的類簇出現相交,則相交類簇再次聚類,直到所有類簇均不相交,樣本的類簇號構成染色體及種群;根據類簇數最少化及類內距離最小化原則構造適應度矢量函數;利用遺傳算法全局尋優的特點對樣本進行多目標優化,并找到較好的染色體;進行預測分類時,刪去單點類簇,并根據最近鄰法則用較優染色體及類標簽進行分類.

1.2 算法體系結構

1.2.1 樣本歸一化.

設第 i個樣本為,xi=(xi1,…,xim),xij∈ R.為了更準確地學習樣本,對所有樣本進行歸一化處理,

其中,m為樣本屬性的個數,xij表示第i行樣本的第j列屬性所對應的值,x′ij表示處理后的值.經過處理后,所有樣本的值都對應到[0,1]區間.

1.2.2 編碼與解碼.

1)編碼.輸入樣本集S,總數為N,可能被分成的類簇數為c,設第i個樣本xi被唯一指定在第ki個類簇中,xi∈Cki則,從而可定義染色體e為,

其中,基因ki表示第i個樣本被指定在第ki類簇,染色體e即表示這些樣本被唯一指定屬于某個類簇.

2)解碼.若已知染色體,則將樣本xi指定屬于第ki個類簇Cki,并且確定了類簇數 c,即,

1.2.3 適應度矢量函數.

m為樣本屬性的個數,xi,xk表示第i,k號樣本,定義距離,

根據類簇數最少和類內距離最小原則定義2維適應度矢量函數,

1.2.4 擂臺選擇法.

本研究采用擂臺法(Arena's Principle,AP)作為選擇評價算子[9-10],其過程為,

1)令E=?,E中存放偏序比較后較優的染色體;

3)若～Z ≠ ?,從 ～Z中選出Zi作為擂臺主,重復步驟 ①和 ②,①從～Z中選出另一個Zj與Zi做偏序比較,若Zj優于Zi,則從～Z中刪除Zi,并令Zj作為新擂主,②若擂臺主與 ～Z中其他元素比較遍歷了～Z后,將擂臺主所對應的染色體增加到E中,從 ～Z中刪除擂臺主,返回到3);

4)輸出E.

1.2.5 保優策略.

將經過AP算法選擇后的較優染色體加入到記憶池中,迭代結束后,對記憶池中的染色體再次進行AP選擇,最終得到的即為經過優化的染色體.這樣做既保留了祖先的優良基因,又經過了全局選擇,即不會因為保優而陷入局部最優解[11].

1.2.6 分類方法.

進行預測分類時,刪除單點類簇.由最優染色體計算各類簇中心,根據最近鄰法則分類,

若輸入的樣本離聚類中心Sr的距離最近,則該樣本的類簇號和類標簽與第r類的相同.

1.3 算法步驟

多目標監督聚類GA算法具體步驟為:

1)初始化參數,樣本歸一化處理;

2)根據樣本的類標簽有監督地將樣本分類,在每個類中按樣本屬性的相似性有監督地聚成類簇,若分屬不同類標簽的類簇不存在相交,則轉到6);

3)記錄出現相交的類簇的類簇號;

4)將出現相交的類簇再次聚類成多個類簇;

5)將聚好的新類簇再次進行有無相交的判斷.若存在相交,則返回3),進行再次聚類,直到所有類簇均不存在相交的情況;

6)樣本的類簇號構成染色體及種群;

7)計算各染色體的適應度矢量函數值;

8)利用AP算法對種群進行選擇,被選擇出染色體稱為父染色體,并將其加入到記憶池中;

9)父染色體進行交叉和變異生成新染色體,其中類別相同的基因進行交叉變異;

10)若新生成的染色體數量小于種群的數量,則返回步驟2)生成染色體,共同作為下一代種群;

11)若滿足結束條件,則對記憶池中的染色體求適應度,并用AP算法做選擇,輸出較優染色體,否則轉到7).

2 仿真實驗分析

2.1 仿真實驗數據與結果

為了驗證本算法的可行性及有效性,選用實驗平臺Windows XP,C#語言編程環境,采用國際上專門用來測試機器學習和數據挖掘算法的標準UCI數據集中使用頻繁的Iris、Echocardiogram和Post-operative-patient 3組數據集作為測試數據.3組數據集的簡單描述如表1所示.

表1 數據集的簡單描述

為了計算分類的準確率,將整個數據集均分為10份進行交叉驗證,即9個子數據集作為訓練樣本,一個子數據集作為預測樣本,每個子數據集輪流作為預測樣本,從而保證了對整個數據集的分類.

經過多次試驗,最后確定算法參數如下,種群規模為50,遺傳代數為1000,交叉概率為0.8,變異概率為0.2.

將算法進行交叉驗證,Iris樣本分類結果的平均正確率為96.66%.本算法與Native Bayes、Boost C4.5和Bayesian Network(K2)算法的平均分類正確率相比[12],結果如表2所示.

表2 平均準確率比較表

將算法進行交叉驗證,Echocardiogram樣本分類結果的平均正確率為72.73%.本算法與C4.5、CN2和KNN算法的平均分類正確率相比[13],結果如表3所示.

表3 平均準確率比較表

將算法進行交叉驗證,Post-operative-patient樣本分類結果的平均正確率為74.17%.本算法與Native Bayes、9-NN和 9-NN2算法的平均分類正確率相比[14],結果如表4所示.

表4 平均準確率比較表

2.2 實驗結果分析

通過對 Iris、Echocardiogram和 Post-operative-patient 3組數據集進行分類,由表2、3、4可知,本算法在平均準確率上有了一定的提高.其中,在Iris數據集中,本算法的平均準確率比3種算法中最高平均準確率提升了1.13%;在Echocardiogram數據集中,本算法的平均準確率比3種算法中最高平均準確率提升了 0.92%;在Post-operative-patient數據集中,本算法的平均準確率比3種算法中最高平均準確率提升了3.07%.同時,由這3組數據集可以說明,無論樣本屬性為連續型或者離散型,本算法都可以有效地進行分類,此表明了本算法的有效性.

3 結 語

本研究提出的基于多目標監督聚類GA算法利用遺傳算法全局尋優的特點,對整個樣本空間按屬性的相似性和類標簽進行分類,使得具有相似規則知識的樣本被劃分為同一類簇.實驗結果表明,算法有較高的準確性和有效性.

[1] 孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[2] 周煒奔,石躍祥.基于密度的K-means聚類中心選取的優化算法[J].計算機應用研究,2012,29(5):1726-1728.

[3] 郭志剛,鄒書蓉.基于非劣排序的多目標優化免疫遺傳算法[J].成都:成都信息工程學院學報,2012,27(2):136-141.

[4] 黃曉濱,鄒書蓉,張洪偉.免疫遺傳算法及其在VRP中的應用[J].成都:成都信息工程學院學報,2008,23(6):637-641.

[5] Gen M,Li Y Z.Spanning tree-based genetic algorithm forbicriteria fixed charge transportation problem[C]//Proceedings of the 1999 Congress on Evolutionary Computation.Washington,DC:IEEE Press,1999:2265-2271.

[6] Gen Mitsuo,Cheng Runwei.Genetic algorithms and engineering optimization[M].New York:John Wiley&sons,Inc.,1999.

[7] Das Indraned.Acloser look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multicriteria optimization problems[J].Structural Optimization,1997,14(1):63-69.

[8] Zhang Hongwei,Yang Zhenyu,Zou Shurong.Multi-objective supervised clustering GA and megathermal climate forecast[C]//IEEE 2011 International Conference on Management and Service Science.Wuhan:IEEE Press,2011:20-23.

[9] Zhang Hongwei,Cui Xiaoke,Zou Shurong.Multi objective transportation optimization based on fmcica[C]//The 2nd IEEE International Conference on Information Management and Engineering.Chengdu:IEEE Press,2010:426-430.

[10] 鄭金華.多目標進化算法及其應用[M].北京:科學出版社,2007.

[11] 雷德明,嚴新平.多目標智能優化算法及其應用[M].北京:科學出版社,2009.

[12] Kotsiantis S B,Pintelas P E.Logitboost of simple bayesian classifier[J].Informatica,2005,29:53-59.

[13] Todorovski L,Dzeroski S.Experiments in meta-level learning with ILP[C]//Third European Conference,PKDD'99.Pragve:Springer Berlin Herdel berg,1999:98-106.

[14] Petri K,Jussi L,Petri M,et al.Unsupervised bayesian visualization of high-dimensional data[C]//Proceedings of the 6th ACMSIG KDD International Conference on Knowledge Discovery and Data Mining.Boston:ACM Press,2000:325-329.

Research of Multi-objective Supervised Clustering GA

SUO Fei,ZHANG Hongwei,ZOU Shurong
(College of Computer Science&Technology,Chengdu University of Information Technology,Chengdu 610225,China)

This paper presents a new multi-objective supervised clustering genetic algorithm.Samples are supervise dly clustered into several classes by class labels.In each class,samples are supervise dly clustered into class clusters according to the similarity of the sample properties.If the class clusters which belong to different class labels intersect,these intersecting class clusters are clustered again into class clusters until all the class clusters don't intersect.The fitness vector function is determined by the number of class clusters and within-class distance.The number and center of class clusters can be determined automatically by using the fitness vector function.The two key elements can be unaffected by subjective factors and have optimization natures.During classification for cast,the single-point class cluster is deleted and then classification is done according to the class cluster number,the nearest neighbor rule and the class labels.The algorithm model is implemented with C#,using three UCI data sets as the experiment data.The experimental results indicate that this algorithm is better than Native Bayes,Boost C4.5 and KNN algorithms.

multi-objective GA;supervised clustering;class label;nearest neighbor rule

TP301.6

A

1004-5422(2013)01-0058-04

2013-01-21.

索 飛(1988—),男,碩士研究生,從事計算機智能計算技術研究.