特征提取與多目標(biāo)機(jī)器學(xué)習(xí)研究及應(yīng)用

何 濤，張洪偉，鄒書蓉

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

引言

令W是給定世界的有限或無限的所有觀測對象的集合，由于我們觀察能力的限制，我們只能獲得這個世界的一個有限的子集Q?W，稱為樣本集。機(jī)器學(xué)習(xí)就是根據(jù)這個樣本集，推算出這個世界的模型，使它對這個世界(盡可能地)為真［1］。

目前，機(jī)器學(xué)習(xí)領(lǐng)域的研究工作主要圍繞在以下三個方面進(jìn)行:

(1)面向任務(wù)的研究。研究和分析改進(jìn)一組預(yù)定任務(wù)的執(zhí)行性能的學(xué)習(xí)系統(tǒng)。

(2)認(rèn)知模型。研究人類學(xué)習(xí)過程并進(jìn)行計(jì)算機(jī)模擬。

(3)理論分析。從理論上探索各種可能的學(xué)習(xí)方法和獨(dú)立于應(yīng)用領(lǐng)域的算法。

機(jī)器學(xué)習(xí)是繼專家系統(tǒng)之后人工智能應(yīng)用的又一重要研究領(lǐng)域，也是人工智能和神經(jīng)計(jì)算的核心研究課題之一?，F(xiàn)有的計(jì)算機(jī)系統(tǒng)和人工智能系統(tǒng)沒有什么學(xué)習(xí)能力，至多也只有非常有限的學(xué)習(xí)能力，因而不能滿足科技和生產(chǎn)提出的新要求。對機(jī)器學(xué)習(xí)的討論和機(jī)器學(xué)習(xí)研究的進(jìn)展，必將促使人工智能和整個科學(xué)技術(shù)的進(jìn)一步發(fā)展。

本文的特征提取與多目標(biāo)機(jī)器學(xué)習(xí)算法正是根據(jù)機(jī)器學(xué)習(xí)中的聚類算法和進(jìn)化算法理論提出的新的機(jī)器學(xué)習(xí)算法。算法有以下主要特點(diǎn):(1)通過特征提取進(jìn)行降維操作找到核屬性，由核屬性與其他非核屬性組成屬性組，從而提高了分類的精度。利用各最小屬性組協(xié)同進(jìn)化，能有效的跳出局部最優(yōu)點(diǎn)而尋找更好的優(yōu)化解;(2)采用機(jī)器學(xué)習(xí)算法中的多目標(biāo)進(jìn)化算法，它是自適應(yīng)全局優(yōu)化概率搜索算法，具有簡單通用、魯棒性強(qiáng)、適于并行處理的優(yōu)點(diǎn)。引入適應(yīng)度矢量函數(shù)和擂臺選擇法，而不使用聚集函數(shù)法［2-3］，這就解決了難以搜索到非凸解的問題［4］;(3)根據(jù)預(yù)估類簇?cái)?shù)和適應(yīng)度矢量函數(shù)通過機(jī)器學(xué)習(xí)算法自動確定類簇個數(shù)和類簇中心，而不受主觀因素的影響，從而提高了分類的可靠性;(4)為減少數(shù)據(jù)噪聲對學(xué)習(xí)的影響，對數(shù)據(jù)進(jìn)行預(yù)處理，提高學(xué)習(xí)的準(zhǔn)確性。

將算法應(yīng)用到UCI數(shù)據(jù)集中的Liver Disorders和Hepatitis兩個數(shù)據(jù)集，以及浙江省北部地區(qū)夏天異常高溫天氣預(yù)報(bào)，實(shí)驗(yàn)結(jié)果表明，該算法具有獨(dú)特的智能性和較高的準(zhǔn)確性和實(shí)用性。

1 算法模型

1.1 算法描述

進(jìn)化算法(Evolutionary Algorithm，簡稱EA)作為一類啟發(fā)式搜索算法，已被成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域，發(fā)展成為一個相對較熱的研究方向。進(jìn)化算法通過在代與代之間維持由潛在解組成的種群來實(shí)現(xiàn)全局搜索，這種從種群到種群的方法對于搜索多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解集是很有用的［5］。

本文提出的算法基本思想是:由特征提取對樣本集進(jìn)行屬性分解得到各子屬性組。將各子屬性組所對應(yīng)的學(xué)習(xí)樣本集通過學(xué)習(xí)器進(jìn)行機(jī)器學(xué)習(xí)。根據(jù)學(xué)習(xí)樣本的類簇號構(gòu)成染色體及種群，且隨機(jī)生成并修補(bǔ);根據(jù)類內(nèi)最小化和學(xué)習(xí)誤差最小原則構(gòu)造適應(yīng)度矢量函數(shù);利用多目標(biāo)EA全局尋優(yōu)的特點(diǎn)對學(xué)習(xí)樣本進(jìn)行多目標(biāo)優(yōu)化，找到較好的染色體并將其保存下來以便每次系統(tǒng)運(yùn)行的時候?qū)⑵湔{(diào)出進(jìn)行運(yùn)算，找到更優(yōu)的解;用找到的染色體根據(jù)最近鄰法則用較優(yōu)染色體及類標(biāo)簽對測試樣本進(jìn)行預(yù)測，最后根據(jù)學(xué)習(xí)誤差小及類內(nèi)距離最小化原則，篩選出各子屬性組最優(yōu)染色體，再根據(jù)最近鄰法則用較優(yōu)染色體及類標(biāo)簽對測試樣本進(jìn)行協(xié)同分類。只要一個子屬性組將該樣本分為顯性類，則該樣本為顯性。

1.2 特征提取算法

本文采用的特征提取的方法為降維機(jī)器學(xué)習(xí)算法，這是一種自上而下的搜索方法，從全部特征開始每次剔除一個特征。具體規(guī)則如下:

(1)初始屬性個數(shù)m，去掉的屬性個數(shù)n=0，當(dāng)前保留屬性集P，當(dāng)前去掉屬性集D。

(2)if(xij==x(i+1)j)j++，其中j∈P，xij表示第i行樣本的第j列屬性所對應(yīng)的值。

(3)i∈P判斷i，i+1這兩個樣本的類標(biāo)簽是否一致，如果不一致則找到學(xué)習(xí)樣本的核屬性，屬性組P則為核屬性組，跳到(6);如果一致，D≠φ則轉(zhuǎn)到(5)，否則轉(zhuǎn)到(4)。

(4)n=n+1，m=m-1。

(5)從P中取n個屬性加入D中，轉(zhuǎn)到(2)，直至P中每n個組合都被取出過。

(6)由核屬性組構(gòu)造各子屬性組Propertyi，每個子屬性組由核屬性組加上一個非核屬性構(gòu)成。

1.3 多目標(biāo)機(jī)器學(xué)習(xí)算法的體系結(jié)構(gòu)

1.3.1 預(yù)估類簇?cái)?shù)

本文采用基本K均值算法作為多目標(biāo)機(jī)器學(xué)習(xí)算法預(yù)估類簇?cái)?shù)的算法，基本K均值算法步驟如下:

(1)選擇K個點(diǎn)作為初始中心。

(2)將每個點(diǎn)指派到最近的中心，形成K個簇。(3)重新計(jì)算每個類簇的中心。

(4)若類簇中心不再發(fā)生變化，算法停止;否則，轉(zhuǎn)到步驟(2)。

1.3.2 數(shù)據(jù)預(yù)處理

為了得到更準(zhǔn)確無噪音的樣本數(shù)據(jù)，需對所有樣本進(jìn)行去噪的預(yù)處理。步驟如下:

(1)如果該樣本數(shù)據(jù)中含有非法值或空值，則直接從樣本集中刪除該樣本。

(2)如果某屬性的值在［0，1］區(qū)間內(nèi)，則不做任何處理;否則，對該屬性進(jìn)行歸一化處理:

其中，n為樣本的個數(shù)，xij表示第i行樣本的第j列屬性所對應(yīng)的值，表示處理后的值。

1.3.3 編碼與解碼

編碼:輸入學(xué)習(xí)樣本總數(shù)為N，可能被分成的類簇?cái)?shù)為c，染色體e定義為:

其中ki表示每個樣本的類簇號，若相同，即表示這些樣本屬于同一類簇，具有相同的類標(biāo)簽。

解碼:f(xi)=ki，i∈{1，2，…，N}，其中i表示樣本編號，ki表示樣本xi所對應(yīng)的類簇號。

1.3.4 類簇類標(biāo)簽判定

(1)若該類簇所涵蓋的學(xué)習(xí)樣本的類標(biāo)簽一致，則該類簇的類標(biāo)簽為學(xué)習(xí)樣本的類標(biāo)簽。

(2)若該類簇所涵蓋的學(xué)習(xí)樣本的類標(biāo)簽不一致，則統(tǒng)計(jì)各類標(biāo)簽所涵蓋的學(xué)習(xí)樣本的數(shù)量，涵蓋學(xué)習(xí)樣本最多的類標(biāo)簽即為該類簇的類標(biāo)簽。

1.3.5 修補(bǔ)染色體

一條染色體中，若存在樣本x1，x2的類簇號(基因)相同，但對應(yīng)的類標(biāo)簽不同，即類標(biāo)簽不同的樣本被劃分到同一類簇中，則該基因需要修補(bǔ)。修補(bǔ)的思想是將x1，x2兩個樣本根據(jù)最近鄰法則調(diào)整到不同的類簇中。具體實(shí)現(xiàn)步驟如下:

(1)選擇x1或者x2，與其它類簇中和x1或者x2具有相同類標(biāo)簽的樣本或聚類中心求距離，并選出距離最小的類簇號k0:

(2)根據(jù)找到距離最小的類簇號k0，將x1或者x2的類簇號調(diào)整為k0。

(3)繼續(xù)搜索該染色體中其他基因位是否需要修補(bǔ)，若需要則反復(fù)執(zhí)行(1)、(2)，否則該染色體修補(bǔ)完成。

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

m為樣本屬性的個數(shù)，xi，xk表示第i，k號樣本。定義距離:

根據(jù)類內(nèi)最小化與學(xué)習(xí)誤差最小原則定義適應(yīng)度矢量函數(shù):

其中:f是學(xué)習(xí)誤差，即用得到的類簇中心對學(xué)習(xí)樣本分類，分類錯誤的數(shù)量，是屬于第r類的樣本，nr為第r類的樣本個數(shù)，sr為第r類的類簇中心，c是類簇個數(shù)。

1.3.7 類別判定方法

由最優(yōu)染色體計(jì)算各類聚類中心mr，分類是根據(jù)最近鄰法則:

若輸入的待分類樣本離聚類中心mr的距離最近，則該樣本的類標(biāo)簽與第r類的相同。每個子屬性組都進(jìn)行相同操作，最后根據(jù)各子屬性組的分類結(jié)果協(xié)同決策，只要在任一子屬性組中該待分類樣本的類標(biāo)簽為顯性，則將其歸類為顯性。

1.4 算法步驟

(1)學(xué)習(xí)樣本特征提取，劃分為p個子屬性組。

(2)選擇初始化學(xué)習(xí)樣本集M和待分類樣本集N，初始各子屬性組樣本數(shù)據(jù)及算法運(yùn)行參數(shù)，設(shè)置每組子屬性的運(yùn)算次數(shù)iter1，樣本歸一化處理。

(3)設(shè)置該子屬性組學(xué)習(xí)迭代次數(shù)iter2。

(4)隨機(jī)生成多個染色體構(gòu)成種群，并對每個染色體進(jìn)行修補(bǔ)。

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

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

(7)父染色體進(jìn)行交叉和變異生成新染色體，并對該染色體進(jìn)行修補(bǔ)。

(8)若新生成的染色體的數(shù)量小于種群的數(shù)量，則隨機(jī)生成染色體，并對其進(jìn)行修補(bǔ)，讓其作為下一代種群。

(9)若滿足iter2，則對記憶池中的染色體求適應(yīng)度，并用AP算法做選擇，將較優(yōu)染色體保存下來，否則轉(zhuǎn)到(5)。

(10)若滿足iter1，則取下一組子屬性轉(zhuǎn)到(3)，直至所有子屬性組被取完，否則轉(zhuǎn)到(3)。

(11)將所有子屬性組得到的染色體按學(xué)習(xí)誤差小及類內(nèi)最小化原則，篩選出各子屬性組最優(yōu)染色體，進(jìn)行協(xié)同決策分類。

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

2.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文提出算法的有效性和實(shí)用性，將用UCIMachine Learning Repository中的LDD(Liver Disorders Dataset)和Hepatitis Dataset數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn)，并將算法應(yīng)用到浙江省北部地區(qū)夏天異常高溫的預(yù)測中。其中，浙江省北部地區(qū)夏天異常高溫?cái)?shù)據(jù)來源于文獻(xiàn)［7］。對于數(shù)據(jù)集浙江省北部地區(qū)夏天異常高溫按照選取前32年樣本作為學(xué)習(xí)樣本，后8年樣本作為測試樣本。LDD與Hepatitis，采用十折交差驗(yàn)證算法，將數(shù)據(jù)集分為10份，輪流讓其中的每1份作為測試樣本，其余9份作為學(xué)習(xí)樣本來驗(yàn)證算法。利用機(jī)器學(xué)習(xí)軟件weka中的SimpleKMeans通過多次試驗(yàn)來確定預(yù)估類簇?cái)?shù)。實(shí)驗(yàn)數(shù)據(jù)描述見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)描述

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

2.2.1 Liver Disorders

采用UCI數(shù)據(jù)集的LDD(判斷病人是否為乙肝患者)的數(shù)據(jù)樣本作為算例。該數(shù)據(jù)樣本中總樣本數(shù)為345，去掉其中4個重復(fù)的樣本后。患者數(shù)為142人，非患者數(shù)為199人，數(shù)據(jù)樣本包括6個條件屬性和1個決策屬性。條件屬性包括:Mcv(X1)、Alkphos(X2)、SGPT(X3)、SGOT(X4)、Gammagt(X5)、Drinks(X6)。

通過特征提取降維操作，得到核屬性為(X1，X4，X5，X6)。由其余任一非核屬性與核屬性構(gòu)成最小屬性組，各屬性組見表2。

表2 子屬性組

采用十折交差驗(yàn)證進(jìn)行實(shí)驗(yàn)，算法運(yùn)行參數(shù)如下:預(yù)估類簇?cái)?shù):100;每組子屬性運(yùn)行次數(shù):8;種群規(guī)模:100;遺傳代數(shù):500;交叉概率:0.8;變異概率:0.2。經(jīng)過10折交叉實(shí)驗(yàn)驗(yàn)證，測試樣本分類結(jié)果的平均正確率為74.12%。通過實(shí)例說明該算法在應(yīng)用到中規(guī)模數(shù)據(jù)樣本中，能得到較滿意的分類結(jié)果。將本文提出的算法與樸素貝葉斯、C4.5決策樹、BP神經(jīng)網(wǎng)絡(luò)、KNN和SVM五種分類算法的平均分類正確率相比［8-9］結(jié)果見表3。

表3 幾種算法的分類正確率對比

2.2.2 Hepatitis

采用UCI數(shù)據(jù)集的Hepatitis的數(shù)據(jù)樣本作為算例。該數(shù)據(jù)樣本中總樣本數(shù)為155，其中，32個樣本為Die(顯性)，123個樣本為Live(隱性)。去掉有缺失數(shù)據(jù)的樣本后，樣本總數(shù)為80。數(shù)據(jù)樣本包括19個條件屬性和1個決策屬性。條件屬性包括:AGE(X1)、SEX(X2)、STEROID(X3)、ANTIVIRALS(X4)、FATIGUE(X5)、MALAISE(X6)、ANOREXIA(X7)、LIVER BIG(X8)、LIVER FIRM(X9)、SPLEEN PALPABLE(X10)、SPIDERS(X11)、ASCITES(X12)、VARICES(X13)、BILIRUBIN(X14)、ALK PHOSPHATE(X15)、SGOT(X16)、ALBUMIN(X17)、PROTIME(X18)、HISTOLOGY(X19)。

通過特征提取降維操作，得到核屬性為(X2，X3，X4，X5，X6，X7，X8，X9，X10，X11，X12，X13，X19)。由其余任一非核屬性與核屬性構(gòu)成最小屬性組。

采用十折交差驗(yàn)證進(jìn)行實(shí)驗(yàn)，算法運(yùn)行參數(shù)如下:預(yù)估類簇?cái)?shù):30;每組子屬性運(yùn)行次數(shù):5;種群規(guī)模:100;遺傳代數(shù):500;交叉概率:0.8;變異概率:0.2。經(jīng)過10折交叉實(shí)驗(yàn)驗(yàn)證，測試樣本分類結(jié)果的平均正確率為90%。通過該實(shí)例說明該算法在應(yīng)用到中規(guī)模數(shù)據(jù)樣本中，同樣能得到較滿意的分類結(jié)果。將本文提出的算法與樸素貝葉斯、C4.5決策樹、Bagging、Boost和SVM五種分類算法的平均分類正確率相比［8-11］結(jié)果見表4。

表4 幾種算法的分類正確率對比

2.2.3 夏天異常高溫天氣預(yù)報(bào)

采用浙江省北部地區(qū)夏天異常高溫天氣數(shù)據(jù)樣本作為算例，根據(jù)文獻(xiàn)［11］，異常高溫氣候數(shù)據(jù)樣本共10個屬性，其中9個條件屬性，1個決策屬性。條件屬性包括:上年7～9月降水量(X1)、上年7～8月的降水量(X2)、上年年積溫(X3)、當(dāng)年3月溫度(X4)、當(dāng)年1～6月積溫(X5)、上年7～12月積溫增量(X6)、上年4～6月降水量(X7)、上年11月溫度(X8)、上年10～12月積溫(X9)。通過特征提取降維操作，得到核屬性為(X4，X6)。由其余任一非核屬性與核屬性構(gòu)成最小屬性組。

文獻(xiàn)［11］中共有1956年到1996年這40年的數(shù)據(jù)樣本，選擇1956年到1988年32年的數(shù)據(jù)作為學(xué)習(xí)樣本，1989年到1996年8年數(shù)據(jù)為待分類樣本。算法運(yùn)行參數(shù)如下:預(yù)估類簇?cái)?shù):7;每組子屬性運(yùn)行次數(shù):3;種群規(guī)模:50;遺傳代數(shù):500;交叉概率:0.8;變異概率:0.2。各屬性組預(yù)測結(jié)果見表5。

表5 異常高溫分類結(jié)果(1:高溫，0:非高溫)

由各子屬性組預(yù)報(bào)結(jié)果，根據(jù)各子屬性組協(xié)同決策分類，則準(zhǔn)確率為87.5%。由此可見，本文所提出的算法在異常高溫預(yù)報(bào)方面具有重要的意義，通過實(shí)例的驗(yàn)證，說明該算法的有效性。

3 結(jié)束語

本文基于多目標(biāo)協(xié)同EA提出特征提取與多目標(biāo)機(jī)器學(xué)習(xí)算法，并將其應(yīng)用到UCI數(shù)據(jù)集中的Liver Disorders和Hepatitis兩個數(shù)據(jù)集，以及浙江省北部地區(qū)夏天異常高溫天氣預(yù)報(bào)實(shí)例中。由實(shí)驗(yàn)結(jié)果可知，該算法表現(xiàn)出其獨(dú)特的智能性和準(zhǔn)確性以及實(shí)用性。如何進(jìn)一步提高算法的執(zhí)行效率，將是下一步需要研究的課題。

［1］王 玨，周志華，周傲英.機(jī)器學(xué)習(xí)及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

［2］Gen M，Li Y.Spanning tree-based genetic algorithm for bicriteria fixed charge transportation problem［C］.Proc.of the Congress on Evolutionary Computation.Washington：IEEE Press，1999.

［3］Gen Mitsuo，Cheng Runwei.Genetic algorithms and engineering optimization［M］.San Francisco：John Wiley＆Sons，Inc，1999.

［4］Das I，Dennis JE.A closer look at drawbacks ofminimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems［J］.Structural Optimization，1997，14(1)：63-69.

［5］公茂果，焦李成，楊咚咚.進(jìn)化多目標(biāo)優(yōu)化算法研究［J］.軟件學(xué)報(bào)，2009，20(2)：271-289.

［6］Zheng Jinhua.Multi-objective evolutionary computations and their applications［M］.Science Press，2007.

［7］周洪祥.災(zāi)害性天氣的預(yù)測方法［M］.北京：氣象出版社，2002.

［8］Bendi V R，Prasad Babu M S，Venkateswarlu N B.A critical study of selected classification algorithms for Liver Disease Diagnosis［J］.International Journal of Database Management Systems(IJDMS)，2011，3(2)：101-114.

［9］Michael L，Raymer，Travis E，et al.Knowledge discovery in medical and biological datasets using a hybrid Bayes classifier/evolutionary algorithm［J］.IEEE Transactions on Systems，Man，and Cybernetics，2003(2)：33.

［10］Li Jinyan，Wong Limsoon.Using rules to analyse bio-medical data：a comparison between C4.5 and PC［J］.Lecture Notes in Computer Science，2003，2762：254-265.

［11］Elena Smirnova，Ida G，Sprinkhuizen Kuyper，et al.Unanimous voting using support vector machines［EB/OL］.http：//www.personeel.unimaas.nl/Smirnov/papers/bnaic04.pdf，2004.