基于最小二乘支持向量機的多屬性決策
2008-12-31 00:00:00張弓長郭燁曹瀟杜喆
計算機應用研究 2008年9期
摘 要：分析多屬性決策問題， 提出了基于最小二乘支持向量機的多屬性決策方法。該方法從決策問題本身出發，構造學習樣本，再通過最小二乘支持向量機擬合出多屬性效用函數，從而實現對方案的排序。該模型與支持向量機相比，參數少，算法簡單、可靠。最后通過算例表明方法的可行性與有效性。
關鍵詞：多屬性決策； 最小二乘支持向量機； 效用函數
中圖分類號：TP181; C934 文獻標志碼：A
文章編號：10013695(2008)09274602
Multiple attribute decision making based on least square support vector machine
ZHANG Gongchang1， GUO Ye2， CAO Xiao1， DU Zhe3
（1.Center of Economical Research， Northwestern Polytechnical University， Xi’an 710072， China; 2.College of Information Technology， Luoyang Normal University， Luoyang Henan 471022， China; 3.Dept.of Applied Mathematics， Xidian University， Xi’an 710071， China)
Abstract:By analyzing multiple attribute decision making(MADM) problem， the paper proposed a method for solving MADM based on least square support vector machine. It extracted learning samples from the MADM problem， estimated the Multiple Attribute Utility Function via LSSVM，and then selected the most desirable alternative. The proposed method has less number of parameter and is simple and reliable， comparing with SVM. In the end， an example demonstrates the method is feasible and availability.
Key words：multiple attribute decision making; least square support vector machine(LSSVM); utility function
多屬性決策(multiple attribute decision making，MADM)也稱為有限方案多目標決策，是決策分析理論研究的重要內容，在工程、管理、經濟、軍事等領域均有廣泛的應用。解決多屬性決策問題的關鍵步驟是得出決策者對方案的偏好結構，而多屬性效用函數(multiple attribute utility function，MAUF)是衡量決策者對備選方案的滿意度，其可根據效用函數值對方案集進行排序，選出最佳方案。由于多屬性效用函數結構復雜，難以確定。為此常常將滿足一定約束條件的多屬性效用函數分解為單個屬性效用函數的加性形式、乘法形式或擬加性形式[1]，而對于復雜的實際決策問題， 這些約束條件很難滿足。一種解決思路是從問題本身出發，通過已知數據來擬合出效用函數。支持向量機[2](support vector machine， SVM)是基于統計學習理論提出的一種新小樣本模式分類算法，當引入ε不敏感損失函數后，可以實現對非線性函數擬合，而無須先作任何函數關系假設。最小二乘支持向量機[3]是SVM的一種變形，用二次損失函數代替SVM中的不敏感損失函數，省去參數ε，并將求解二次規劃的問題變成求解線性方程組，降低計算復雜度；且最小二乘支持向量機能夠擴展為自回歸的形式來處理動態問題[4]；文獻[5]將其應用于故障診斷。文獻[6]使用SVM來擬合效用函數進行決策，有一定的效果，并提出幾種構造學習樣本的方法。但是這些方法會無形中固定函數類型，使樣本不具有全局性。本文從問題本身出發重新設定樣本構造方法，并提出多屬性決策的最小二乘支持向量機方法，實現對方案的排序，進而完成決策。
1 最小二乘支持向量機
設樣本集{xi，yi}Ni=1∈Rm×R，使用最小二乘支持向量機進行回歸函數估計，則問題轉換為
min (1/2)‖w‖2+γ∑Ni=1ε2i
SVM需要求解一個二次規劃[2]，而LSSVM只求解一個線性方程組，所以比SVM更加簡單快捷。
2 基于LSSV M的多屬性決策原理
設方案集為X={x1，x2，…，xn}，屬性集為Y={y1，y2，…，ym}。則方案xi在屬性yj下的屬性值記為aij（i=1，…，n；j=1，…，m）。寫成決策矩陣表示方案集X關于屬性集Y的決策矩陣有：
A=a11 … a1m an1 … anm 。為了消除不同物理量綱對決策結果的影響，一般需要對決策矩陣進行歸一化為R=(rij)n×m。多屬性決策實際上就是對備選方案進行排序，以選出最佳者；而效用函數就是描述決策者偏好結構的實值函數， 是從決策方案集合到效用值域上的映射：u=F(R)， 它反映了決策者對風險和后果的偏好。
與文獻[6]中的思路類似，本文方法按照如圖1所示利用LSSVM擬合出方案xi與效用評價值ui之間的近似映射F⌒，即
整個決策過程如圖2所示，使用LSSVM實現方案效用函數的擬合，并對方案進行排序。與基于SVM的方法相比，參數少，算法簡單、快捷，可適應于具有大量數據的問題。
3 構造學習樣本及模型選擇
在實際的決策問題中，幾乎不存在學習樣本，則需要構造具有代表性，能反映決策對象特征的學習樣本。文獻[6]利用簡單的兩種效用函數曲線，構造出大量的樣本點，但實際上這些學習樣本都隱含了效用函數的類型，不具備權威性和普遍性。本文只需簡單地構造幾個具有代表性樣本點，就可完成曲線擬合。
將屬性集I分為J∪K。其中：J為效益型屬性集；K為成本型屬性集。對于效益型屬性而言，最高屬性值的方案具有最高的效用函數值，具有最低屬性值的方案具有最低效用函數值；而對于成本型屬性則相反，介于最高與最低屬性值之間的方案，其效用函數值也位于最高與最低值之間。所以將構造具有最高屬性值的屬性作為理想點x*，構造具有最低屬性值的屬性作為負理想點x-，并指定兩者的效用函數值分別為0.95和0.05，故效用函數的取值期間為[0.05，0.95]；最后利用中值公式，確定之間的中值點(x)和中值效用值為新的樣本點及相應的函數值。即可表示為
模型選擇時，可以選核函數為徑向基核函數(RBF：K(x，y)=exp(-s‖x-y‖2))，因為RBF核在一般光滑性假設條件下具有良好的擬合性能[7]。關于核參數和懲罰因子γ的確定，本文使用的判定標準為∑li=1(u-ulssvm)2盡可能小。其中：l為樣本數；u為期望效用值；ulssvm為訓練值，然后通過交叉驗證確定參數。
4 算例
為了與文獻[6]中的方法比較，以及驗證本文方法的有效性，同樣選取文獻[8]中的決策實例，即戰斗機的購買問題。現有四種類型飛機供選擇，即四種方案，共六項評價指標。具體如表1所示。除購買費用為成本型外，其他均為效益型。
同樣采用文獻[9]中的向量歸一化方法得到規范的決策矩陣如表2所示。
從表2中計算出樣本點以及對樣本點的LSSVM擬合結果如表3所示。其中選取參數C=1 000，s=2，LSSVM算法采用LSSVMlab軟件包[10]。
再根據LSSVM擬合出的效用函數對每個方案的計算結果如表4所示。
可得出方案排序為x3＞x1＞x4＞x2。這與基于SVM決策的文獻[6]和基于信息熵決策的文獻[8]中的結果完全一致。雖然LSSVM對每個方案的最終效用函數值與SVM擬合出的不一樣，但并不影響方案的排列。
5 結束語
本文通過構造學習樣本，利用LSSVM擬合多屬性決策的效用函數，再根據函數值對方案進行排序，選出最優。本方法無須考慮決策屬性簡單的復雜關系，計算可靠；且比基于SVM的決策方法參數個數少、構造樣本簡單、算法復雜度低，故可完全替代之；同時也擴展了最小二乘支持向量機的應用范圍。
參考文獻：
［1］陳珽. 決策分析[M]. 北京：科學出版社，1987.
[2]VAPNIK V. The nature of statistical learning theory[M]. New York: Springer， 1995.
[3]SUYKENS J A K，VANDEWALLE J. Least square support vector machine classifiers[J]. Neural Processing Letters，1999，9:293300.
[4]楊奎河，單甘霖，趙玲玲. 基于最小二乘支持向量機的故障診斷方法[J]. 計算機應用研究， 2007，24(7):99101.
[5]王強，沈永平，陳英武. 多屬性決策的支持向量機方法[J].系統工程理論與實踐，2006，26(6):5458.
[6]徐澤水.不確定多屬性決策方法及其應用[M].北京：清華大學出版社，2004.
[7]劉樹林，邱菀華. 多屬性決策理論基礎研究[J].系統工程理論與實踐，1998，18 (1):3843.
[8]SUYKENS J A K，VANDEWALLE J. Recurrent least squares support vector machines[J].IEEE Trans on Circuits and Systems， 2000，47(7):11091114.
[9]CHALIMOURDA A， SCHLKOPF B， SMOLAA. Experimentally optimal v in support vector regression for different noise models and parameter setting[J].Neural Networks，2004，17(1):127141.
[10]PELCKMANS K， SUYKENS J A K， et al. LSSVMlab:a MATLAB toolbox for least squares support vector machines[EB/OL].(2002)[20071005]. http://www.esat.kuleuven.ac.be/sista/lssvmlab/.
