多目標(biāo)監(jiān)督聚類GA研究

索 飛,張洪偉,鄒書蓉

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院,四川 成都 610225)

多目標(biāo)監(jiān)督聚類GA研究

索 飛,張洪偉,鄒書蓉

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院,四川 成都 610225)

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

多目標(biāo)GA;監(jiān)督聚類;類標(biāo)簽;最近鄰法則

0 引 言

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

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

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

1 多目標(biāo)監(jiān)督聚類GA算法模型

1.1 算法描述

算法的基本思路是:對樣本歸一化處理,根據(jù)樣本的類標(biāo)簽有監(jiān)督地將樣本分類,在每個(gè)類中按樣本屬性的相似性有監(jiān)督地聚成類簇,如果分屬不同類標(biāo)簽的類簇出現(xiàn)相交,則相交類簇再次聚類,直到所有類簇均不相交,樣本的類簇號(hào)構(gòu)成染色體及種群;根據(jù)類簇?cái)?shù)最少化及類內(nèi)距離最小化原則構(gòu)造適應(yīng)度矢量函數(shù);利用遺傳算法全局尋優(yōu)的特點(diǎn)對樣本進(jìn)行多目標(biāo)優(yōu)化,并找到較好的染色體;進(jìn)行預(yù)測分類時(shí),刪去單點(diǎn)類簇,并根據(jù)最近鄰法則用較優(yōu)染色體及類標(biāo)簽進(jìn)行分類.

1.2 算法體系結(jié)構(gòu)

1.2.1 樣本歸一化.

設(shè)第 i個(gè)樣本為,xi=(xi1,…,xim),xij∈ R.為了更準(zhǔn)確地學(xué)習(xí)樣本,對所有樣本進(jìn)行歸一化處理,

其中,m為樣本屬性的個(gè)數(shù),xij表示第i行樣本的第j列屬性所對應(yīng)的值,x′ij表示處理后的值.經(jīng)過處理后,所有樣本的值都對應(yīng)到[0,1]區(qū)間.

1.2.2 編碼與解碼.

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

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

2)解碼.若已知染色體,則將樣本xi指定屬于第ki個(gè)類簇Cki,并且確定了類簇?cái)?shù) c,即,

1.2.3 適應(yīng)度矢量函數(shù).

m為樣本屬性的個(gè)數(shù),xi,xk表示第i,k號(hào)樣本,定義距離,

根據(jù)類簇?cái)?shù)最少和類內(nèi)距離最小原則定義2維適應(yīng)度矢量函數(shù),

1.2.4 擂臺(tái)選擇法.

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

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

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

4)輸出E.

1.2.5 保優(yōu)策略.

將經(jīng)過AP算法選擇后的較優(yōu)染色體加入到記憶池中,迭代結(jié)束后,對記憶池中的染色體再次進(jìn)行AP選擇,最終得到的即為經(jīng)過優(yōu)化的染色體.這樣做既保留了祖先的優(yōu)良基因,又經(jīng)過了全局選擇,即不會(huì)因?yàn)楸?yōu)而陷入局部最優(yōu)解[11].

1.2.6 分類方法.

進(jìn)行預(yù)測分類時(shí),刪除單點(diǎn)類簇.由最優(yōu)染色體計(jì)算各類簇中心,根據(jù)最近鄰法則分類,

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

1.3 算法步驟

多目標(biāo)監(jiān)督聚類GA算法具體步驟為:

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

2)根據(jù)樣本的類標(biāo)簽有監(jiān)督地將樣本分類,在每個(gè)類中按樣本屬性的相似性有監(jiān)督地聚成類簇,若分屬不同類標(biāo)簽的類簇不存在相交,則轉(zhuǎn)到6);

3)記錄出現(xiàn)相交的類簇的類簇號(hào);

4)將出現(xiàn)相交的類簇再次聚類成多個(gè)類簇;

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

6)樣本的類簇號(hào)構(gòu)成染色體及種群;

7)計(jì)算各染色體的適應(yīng)度矢量函數(shù)值;

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

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

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

11)若滿足結(jié)束條件,則對記憶池中的染色體求適應(yīng)度,并用AP算法做選擇,輸出較優(yōu)染色體,否則轉(zhuǎn)到7).

2 仿真實(shí)驗(yàn)分析

2.1 仿真實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

為了驗(yàn)證本算法的可行性及有效性,選用實(shí)驗(yàn)平臺(tái)Windows XP,C#語言編程環(huán)境,采用國際上專門用來測試機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法的標(biāo)準(zhǔn)UCI數(shù)據(jù)集中使用頻繁的Iris、Echocardiogram和Post-operative-patient 3組數(shù)據(jù)集作為測試數(shù)據(jù).3組數(shù)據(jù)集的簡單描述如表1所示.

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

為了計(jì)算分類的準(zhǔn)確率,將整個(gè)數(shù)據(jù)集均分為10份進(jìn)行交叉驗(yàn)證,即9個(gè)子數(shù)據(jù)集作為訓(xùn)練樣本,一個(gè)子數(shù)據(jù)集作為預(yù)測樣本,每個(gè)子數(shù)據(jù)集輪流作為預(yù)測樣本,從而保證了對整個(gè)數(shù)據(jù)集的分類.

經(jīng)過多次試驗(yàn),最后確定算法參數(shù)如下,種群規(guī)模為50,遺傳代數(shù)為1000,交叉概率為0.8,變異概率為0.2.

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

表2 平均準(zhǔn)確率比較表

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

表3 平均準(zhǔn)確率比較表

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

表4 平均準(zhǔn)確率比較表

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

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

3 結(jié) 語

本研究提出的基于多目標(biāo)監(jiān)督聚類GA算法利用遺傳算法全局尋優(yōu)的特點(diǎn),對整個(gè)樣本空間按屬性的相似性和類標(biāo)簽進(jìn)行分類,使得具有相似規(guī)則知識(shí)的樣本被劃分為同一類簇.實(shí)驗(yàn)結(jié)果表明,算法有較高的準(zhǔn)確性和有效性.

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

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

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

[4] 黃曉濱,鄒書蓉,張洪偉.免疫遺傳算法及其在VRP中的應(yīng)用[J].成都:成都信息工程學(xué)院學(xué)報(bào),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] 鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2007.

[11] 雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,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—),男,碩士研究生,從事計(jì)算機(jī)智能計(jì)算技術(shù)研究.