多目標(biāo)優(yōu)化方法在機(jī)器學(xué)習(xí)中的應(yīng)用簡述

鄭秀蓮

(泰州機(jī)電高等職業(yè)技術(shù)學(xué)校，江蘇泰州 225300)

多目標(biāo)優(yōu)化方法在機(jī)器學(xué)習(xí)中的應(yīng)用簡述

鄭秀蓮

(泰州機(jī)電高等職業(yè)技術(shù)學(xué)校，江蘇泰州 225300)

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

多目標(biāo)優(yōu)化;有監(jiān)督學(xué)習(xí);無監(jiān)督學(xué)習(xí)

一、引言

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

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

二、多目標(biāo)優(yōu)化的有監(jiān)督學(xué)習(xí)

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

近年來，關(guān)于將多目標(biāo)優(yōu)化算法應(yīng)用到分類問題中的研究越來越多，分類算法經(jīng)常使用總體分類精確度為指導(dǎo)標(biāo)準(zhǔn)來構(gòu)造一個(gè)模型，最主要的目標(biāo)是最大化模型的分類性能。文獻(xiàn)中利用多目標(biāo)優(yōu)化算法NSGAⅡ來建立對(duì)于某個(gè)特定的類的分類模型。算法步驟總結(jié)如下：

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

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

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

步4：利用多目標(biāo)進(jìn)化算法NSGAⅡ來產(chǎn)生新一代的種群，轉(zhuǎn)步3。

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

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

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

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

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

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

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

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

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

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

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

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

三、多目標(biāo)優(yōu)化的無監(jiān)督學(xué)習(xí)

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

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

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

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

四、結(jié)論

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

［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">文獻(xiàn)標(biāo)識(shí)碼：A

A

1671－3974(2012)03－0084－03

2012－05－10

鄭秀蓮(1985－)，女，大學(xué)，泰州機(jī)電高等職業(yè)技術(shù)學(xué)校教師，助教，研究方向?yàn)橛?jì)算機(jī)軟件及網(wǎng)絡(luò)安全技術(shù)。