何 濤，張洪偉，鄒書蓉

(成都信息工程學院計算機學院，成都 610225)

引言

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

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

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

(2)認知模型。研究人類學習過程并進行計算機模擬。

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

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

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

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

1 算法模型

1.1 算法描述

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

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

1.2 特征提取算法

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

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

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

(3)i∈P判斷i，i+1這兩個樣本的類標簽是否一致，如果不一致則找到學習樣本的核屬性，屬性組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 多目標機器學習算法的體系結(jié)構(gòu)

1.3.1 預(yù)估類簇數(shù)

本文采用基本K均值算法作為多目標機器學習算法預(yù)估類簇數(shù)的算法，基本K均值算法步驟如下:

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

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

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

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

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

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

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

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

1.3.3 編碼與解碼

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

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

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

1.3.4 類簇類標簽判定

(1)若該類簇所涵蓋的學習樣本的類標簽一致，則該類簇的類標簽為學習樣本的類標簽。

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

1.3.5 修補染色體

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

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

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

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

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

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

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

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

1.3.7 類別判定方法

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

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

1.4 算法步驟

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

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

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

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

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

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

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

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

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

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

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

2 實驗與結(jié)果分析

2.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)描述

2.2 實驗結(jié)果與分析

2.2.1 Liver Disorders

采用UCI數(shù)據(jù)集的LDD(判斷病人是否為乙肝患者)的數(shù)據(jù)樣本作為算例。該數(shù)據(jù)樣本中總樣本數(shù)為345，去掉其中4個重復的樣本后?；颊邤?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 子屬性組

采用十折交差驗證進行實驗，算法運行參數(shù)如下:預(yù)估類簇數(shù):100;每組子屬性運行次數(shù):8;種群規(guī)模:100;遺傳代數(shù):500;交叉概率:0.8;變異概率:0.2。經(jīng)過10折交叉實驗驗證，測試樣本分類結(jié)果的平均正確率為74.12%。通過實例說明該算法在應(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)成最小屬性組。

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

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

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

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

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

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

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

3 結(jié)束語

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

［1］王 玨，周志華，周傲英.機器學習及其應(yīng)用［M］.北京：清華大學出版社，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］公茂果，焦李成，楊咚咚.進化多目標優(yōu)化算法研究［J］.軟件學報，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.