多目標優(yōu)化方法在機器學習中的應用簡述

鄭秀蓮

(泰州機電高等職業(yè)技術學校，江蘇泰州 225300)

多目標優(yōu)化方法在機器學習中的應用簡述

鄭秀蓮

(泰州機電高等職業(yè)技術學校，江蘇泰州 225300)

文章概述了多目標優(yōu)化方法解決機器學習問題的現(xiàn)狀，重點對基于Pareto的多目標優(yōu)化方法進行分析，通過有監(jiān)督學習中的分類問題和無監(jiān)督學習中的聚類問題，表明使用基于Pareto多目標優(yōu)化方法解決機器學習問題的優(yōu)點，得到對所解決問題的更深的認識。

多目標優(yōu)化;有監(jiān)督學習;無監(jiān)督學習

一、引言

機器學習可以大致分為三類，一類是有監(jiān)督學習，該類問題的模型能近似地實現(xiàn)給定的輸入數(shù)據(jù)和輸出數(shù)據(jù)之間的映射，典型的有回歸問題或分類問題;二是無監(jiān)督學習，數(shù)據(jù)聚類是一個典型的無監(jiān)督的機器學習，聚類將給定的數(shù)據(jù)集中的數(shù)據(jù)分配到不同的簇中，使屬于同一簇的數(shù)據(jù)具有較高的相似度;第三類是強化學習，其目的是在某一特定的環(huán)境下，找到一個模型能最大限度地累積獎勵。

在機器學習中按詞典排序的多目標優(yōu)化，標量式的多目標優(yōu)化以及基于Pareto的多目標優(yōu)化較常用，下面就多目標優(yōu)化在有監(jiān)督學習和無監(jiān)督學習中用法做出具體闡述。

二、多目標優(yōu)化的有監(jiān)督學習

多目標優(yōu)化的有監(jiān)督學習的關注點是必須產生具備良好性能的學習模型，該模型既對訓練數(shù)據(jù)集有良好的逼近性能，又對測試數(shù)據(jù)集有效。

近年來，關于將多目標優(yōu)化算法應用到分類問題中的研究越來越多，分類算法經常使用總體分類精確度為指導標準來構造一個模型，最主要的目標是最大化模型的分類性能。文獻中利用多目標優(yōu)化算法NSGAⅡ來建立對于某個特定的類的分類模型。算法步驟總結如下：

步1：將分類問題轉化為一個二維多目標優(yōu)化問題，確定多目標優(yōu)化算法的目標為同時最大化精確度和覆蓋率;

步2：利用統(tǒng)一的編碼形式來表示解(二進制編碼字符串)，并通過初始化程序來初始化解集(種群);

步3：對種群中的每個解進行解碼，再評估，評估的過程就實現(xiàn)了規(guī)則的選取，主要是對規(guī)則的前提中所包含的屬性集進行篩選;若達到最大迭代次數(shù)，則算法終止，輸出當前非支配解集;否則，繼續(xù)執(zhí)行步4;

步4：利用多目標進化算法NSGAⅡ來產生新一代的種群，轉步3。

將該算法應用到一些典型的分類數(shù)據(jù)集中，并與一般啟發(fā)算法(如：遺傳算法)的實驗結果進行比較，結果表明應用多目標進化算法來解決該分類問題效果更好。這主要體現(xiàn)在三個方面：

第一，啟發(fā)算法搜索到的解之間存在相互支配關系，也就是說啟發(fā)算法最終搜索到的最優(yōu)解集不是實際最優(yōu)的，不能充分滿足分類問題的需求。而多目標進化算法最終搜索到的解就是最后一輪迭代產生的非支配集，這些解都是非支配的，不可能存在某個解在各維目標上都優(yōu)于另一個解。

第二，這里的啟發(fā)算法其實是一種標量式的多目標優(yōu)化算法，將多個目標聚集成一個目標來解決，所以算法的搜索空間很小，實驗結果表明對于某些數(shù)據(jù)集，啟發(fā)算法無法搜索到全局最優(yōu)解。而多目標進化算法把每個目標看成獨立的函數(shù)來解決，搜索空間更大，對于實驗中的每個數(shù)據(jù)集，多目標進化算法都能找出全局最優(yōu)解。

第三，啟發(fā)算法搜索到的最優(yōu)解的分布性很差，容易聚集到同一個區(qū)域內;而多目標進化算法中本身就帶有分布性控制的部分，因而，得出的解能夠均勻分布到最優(yōu)邊界上。

如上所述，對于一個分類問題，若要實現(xiàn)最大化模型的分類性能這一主要目標，應用多目標優(yōu)化算法效果更好，得出的解集更優(yōu)，實驗表明多目標優(yōu)化算法在分類問題上有很大的應用前景。

在此基礎上，產生了越來越多的關于將多目標優(yōu)化算法應用到分類問題上的深入研究。最大化模型的分類性能是研究的主要內容，同時模型的系統(tǒng)易理解性也是研究的重要內容。文獻中詳細講述了如何利用基于Pareto的多目標優(yōu)化算法來產生易理解的模糊分類規(guī)則系統(tǒng)。算法基本思想概括如下：

步1：對數(shù)據(jù)集做標準化處理，即基于各維屬性值的范圍做模糊分割，將屬性值劃分為特定的幾個區(qū)域值。

步2：初始規(guī)則集的產生，基于短規(guī)則的原理，只選取前提條件長度較短的規(guī)則來構建分類系統(tǒng)，假定對于一個有維屬性值的數(shù)據(jù)集，各個屬性值模糊處理后都為個值，現(xiàn)在要選擇長度小于等于的規(guī)則，則可以產生的規(guī)則數(shù)為個，由此產生的規(guī)則數(shù)量仍然很龐大。

步3：應用數(shù)據(jù)挖掘知識，產生候選規(guī)則集。這里產生候選規(guī)則集的方法就是一個單目標算法，基本思想就是根據(jù)評估標準(如：置信度，支持度，兩者的乘積)對步2產生的初始規(guī)則集排序來選擇指定數(shù)量的候選規(guī)則，通過對不同標準進行實驗，實驗結果表明利用置信度和支持度的乘積作為標準選取的候選規(guī)則生成的系統(tǒng)，在測試分類時正確率最高。

步4：在候選規(guī)則集的基礎上應用多目標優(yōu)化算法抽取候選規(guī)則集的一個子集來構成易理解的分類系統(tǒng)。將候選規(guī)則集中的每個規(guī)則編號，利用二進制串來表示某一分類系統(tǒng)的構成，即二進制串某一位上為1表示對應編號的規(guī)則包含在該分類系統(tǒng)中，否則為0表示不包含。由這樣的一些二進制串就構成了多目標優(yōu)化算法的種群，再根據(jù)多目標優(yōu)化算法的原理，經過迭代最后產生的非支配集就是所求的解。

實驗結果表明，對數(shù)據(jù)集的預處理操作可以提高整個算法的效率，利用多目標進化算法產生的分類模型是有效的，且模型比較簡單易于被用戶理解，此外，文中還對多目標進化算法進行了擴展，即結合了局部搜索算法和規(guī)則權重的概念。

總之，從上面兩個例子可以看出多目標進化算法在分類問題上的應用是有效的，也具備良好的發(fā)展前景。此外，多目標進化算法在有監(jiān)督學習的其他一些問題上也有研究，如神經網(wǎng)絡，系統(tǒng)控制等。這些研究足以表明將多目標進化算法應用到有監(jiān)督學習問題的解決中是有效的。

三、多目標優(yōu)化的無監(jiān)督學習

聚類問題通常被定義為將一個數(shù)據(jù)集分成幾個自然組合，屬于同一個組合的數(shù)據(jù)之間的相似性較大，而不同組合的數(shù)據(jù)之間的相似性較小。在實踐中，聚類往往很難實現(xiàn)，主要是因為對于有的數(shù)據(jù)集，即使是人工來分類也很難分清數(shù)據(jù)該屬于什么組合;另一個原因就是聚類算法的發(fā)展還不成熟，具體實現(xiàn)的過程中只側重于優(yōu)化一個目標函數(shù)。后來的研究提出了對多個目標進行優(yōu)化的要求，研究表明多目標進化算法也可以應用到聚類問題中。如提出基于Pareto的多目標聚類算法，該算法中考慮了四個目標：第一個目標是簇的內聚性，該目標偏愛密集型的類;第二個目標是最大化簇之間的距離;第三個目標是減少簇的個數(shù);第四個目標是減少所選的特征數(shù)。

將基于Pareto的多目標進化算法應用到聚類問題中的優(yōu)勢也得以證明。算法主要分為兩個步驟，首先利用多目標優(yōu)化算法PESAⅡ來尋求非支配解，再通過分析Pareto最優(yōu)邊界來自動確定簇的個數(shù)。文中多目標優(yōu)化算法的目標為最小化兩個目標，這兩個目標分別表示簇的緊湊性(如式6)和數(shù)據(jù)點的連通性(如式7)。簇的緊湊性是指對于某個分割部分的數(shù)據(jù)點與簇中心點之間的整體偏離值;連通性用于檢查相鄰區(qū)域內的數(shù)據(jù)點分到同一個簇的可能性。

其中C={C1，C2，…，Ck} 是簇的集合，ck是簇Ck的中心，k=1，2，…，K，K是簇的個數(shù)，xi是屬于簇Ck的一個數(shù)據(jù)點，L是預先定義的一個領域參數(shù)，N是數(shù)據(jù)集大小，γ定義：若x與NN(x)屬于同一個簇，則γ=，否則γ=0。NN(x)是數(shù)據(jù)點x的第j個鄰居點。通過以上的多目標優(yōu)化算法可以得出一組基于Pareto的非支配解集，這些解都是通過取兩個目標函數(shù)的折中而得到的，且各個解所包含的簇的數(shù)量不同。基于此，算法又設計出一個自動的方法以選擇其中某一個解作為最終結果。該自動選擇方法根據(jù)目標空間的結果圖定義了一個關于簇的個數(shù)的函數(shù)以選擇最優(yōu)解。文中將算法應用到一些數(shù)據(jù)集的聚類中，并與其他的算法結果進行了比較，實驗表明能夠找出高質量的解且能夠正確的確定簇的個數(shù)。

通過實現(xiàn)對多個目標同時進行優(yōu)化來聚類的，這樣的聚類不同于單目標優(yōu)化算法只局限于優(yōu)化一個目標而找不到較優(yōu)的解，通過多目標優(yōu)化算法找到的解不會只受單一的目標牽制著，能夠達到全局優(yōu)化，因而解的質量更好，效果更佳。以上分析表明，多目標優(yōu)化算法可以用于解決聚類問題，且在聚類問題的解決中有良好的應用前景。

四、結論

實例表明：源于多目標進化算法本身的特點，使得在解決機器學習問題時，免去了用戶對參數(shù)設置的責任，也不需要對具有不同意義的目標函數(shù)進行整合，多目標進化算法還可以得到一組Pareto最優(yōu)解集，用戶可以從中抽取關于問題的知識，因而在做最后的決策時能做出更好的選擇，并得到對問題的更深的認識。

［1］Beatriz de la Iglesia，Mark S.Philpott，Anthony J.Bagnall and Vie J.Rayward－Smith.Data Mining Rules Using Multi－Objective Evolutionary Algorithms.IEEE 2003

［2］Hisao Ishibuchi and Takashi Yamamoto.Fuzzy Rule Selection by Multi－Objective Genetic Local Search Algorithms and Rule Evaluation Measures in Data Mining.Department of Industrial Engineering，Osaka Prefecture University.

［3］H.Abbass，“A memetic Pareto approach to artificial neural networks，”in Proc.14th Aust.Joint Conf.Artif.Intell.，2001，pp.1–12.

［4］S.Park，D.Nam，and C.H.Park，“Design of a neural controller using multi－objective optimization for nonminimum phase systems，”in Proc.IEEE Int.Conf.Fuzzy Sets Syst.，1999，vol.I，pp.533 – 537.

［5］Y.Kim，W.Street，and F.Menczer，“Evolutionary model selection in unsupervised learning，” Intell.Data Anal.，vol.6，pp.531–556，2002.

［6］Julia Handl and Joshua Knowles.Exploiting the Trade－ Off—The Benefits of Multiple Objectives in Data Clustering.Springer－Verlag Berlin Heidelberg 2005.

The Application of Multi－objective Optimization Method in Machine Learning

ZHENG Xiu－lian
(Taizhou Vocational School of Mechanical＆ Electrical Technology，Taizhou Jiangsu 225300)

The article provides an overview of the use of multi－objective optimization methods to solve machine learning problems，focusing on the multi objective optimization method based on Pareto，through the analysis of specific examples，including the classification problem in supervised learning and the clustering problem in unsupervised learning.The author introduces the advantage of the use of multi－objective optimization method based on Pareto to solve machine learning problems，and the users can get to the deeper understanding of problem solving.

multi－objective optimization;supervised learning;unsupervised learning

O153 < class="emphasis_bold">文獻標識碼：A

A

1671－3974(2012)03－0084－03

2012－05－10

鄭秀蓮(1985－)，女，大學，泰州機電高等職業(yè)技術學校教師，助教，研究方向為計算機軟件及網(wǎng)絡安全技術。