多側面遞進算法在機器學習中的應用

摘 要:本文在已有文獻建立的機器學習方法的基礎上，提出將多側面遞進算法作為數據預處理方法，并用UCI數據集進行實驗，實驗結果表明這是一種行之有效的特征提取方法。

關鍵詞:多側面 特征提取 機器學習

中圖分類號:G6文獻標識碼:A文章編號:1674-098X(2012)04(b)-0149-02

1 引言

人類在分析現實復雜問題時，通常不是一次性給出判斷結果，而是會分層次、分角度地給出各個方面的判斷，最后再綜合評判并給出最終結論。多側面遞進算法MIDA(Multi-side Increase by Degrees Algorithm)[1]對不同樣本在不同側面進行分類識別，最后通過投票方式決定測試樣本的決策屬性。這符合人類在認知復雜事物時分側面、多角度考慮最后權衡作出判斷的過程。

2 多側面方法

2.1 方法介紹

現有的特征提取方法[2、3]都有一個共同點，那就是希望找到一組特征對全體數據都適合，即借助這組特征能把所有討論的數據進行合乎要求的識別、分辨。可是在很多現實問題的分析中，是不能采用這種“一刀切”的做法的。多側面方法是不同于以往所有方法的一種新的特征提取方法。該方法從樣本本身出發，充分考慮到樣本自身的多樣性，將樣本集分成幾個部分，對各部分分別選擇一組適合它們的特征子集，這種區別對待、分而治之的方法，在保證一定精度的前提下，可有效提高泛化能力，并降低計算過程中的復雜性。

我們以一個簡單的例子來說明多側面特征提取方法的基本思想。設樣本集

，即分為兩類，其中每個樣本對應一位學生，每一列對應一門課程成績，即一個屬性，院系為決策信息。具體取值如表1所示。

特征提取的是以類內區分盡可能小和類間區分盡可能大為目標的。然而觀察表1所示樣本集合，我們卻找不到這樣的屬性子集，因為對每一門功課，兩個院系都有一部分學生成績非常接近(如表中圓角矩形所示)。換言之，每個屬性對樣本的區分能力都有盲區。在這種情況下，如果非要根據四門功課成績之差絕對值的大小來選取一個屬性子集的話，就會有點牽強附會。因為不管選取的子集是什么，都有這個子集無法處理的情況，亦即會很明顯地降低原屬性集合的分辨能力。

但是當我們仔細分析樣本集合后發現，和的區別主要集中在外語和體育成績上，而和的區別則主要集中在計算機和思想道德修養成績上。所以特征提取并非不可以，只要對樣本集區別對待即可。具體的，對和選取屬性子集外語，體育，對和選取屬性子集計算機，思想道德修養，這樣既簡化了特征空間(由四維降為二維)，又保持了原有決策表的分辨能力，這正是多側面方法的實質所在。

2.2 多側面特征提取方法性能分析

假設問題規模為，即個樣本，個屬性;不失一般性，假設對特征提取效果評價過程是借助學習效果來實現的，設所使用的學習方法的計算量為;又假設每次提取的特征子集為原屬性集合容量的，為分側面次數，當整個樣本集合能很快特征提取結束時，較小，即摸索的速度很快，逼近的過程很短;若不能很快結束，則限定一個最大分側面次數。

首先若不進行特征提取，直接進行學習的計算量即為

再考慮多側面方法計算量為:

，其中，=，=，一般，，假設設、均為線性函數，所以

得出多側面方法具有較小的計算復雜性，但只是在一個常數級的較小。這是因為我們假設、均為線性函數，而一般是沒有這樣低復雜度的學習算法的。一旦變成關于的二次方以上的函數，提取出來時，就是二次方的分母;若是關于的二次方以上的函數，則有成立，所以能保證一定小于，且越大，即分的側面越多，越能降低計算的復雜度;原學習算法的時間復雜度越高，多側面方法的性能提高越明顯。

3 實驗

為驗證多側面方法在特征提取中的有效性，用從UCI數據集上下載的一批數據進行實驗。表2為經過多側面特征提取的機器學習方法和原學習方法各項參數的對比。表中實驗結果為做10次實驗取的平均值。

實驗結果表明，經多側面特征提取對測試樣本的識別率和正確率都有明顯提高，且這種提高不受樣本的維數及測試樣本數與學習樣本數的比例等各項因素的影響。

4 結論

多側面特征提取方法，采用將學習樣本集合劃分成若干個子集，對每個子集選取適合的側面(在此側面，樣本點更易于被識別)投影，測試樣本點經過每一個側面均有一個輸出，再由多個側面綜合給出決策信息。子集的劃分是通過在機器學習的過程中，根據所得分類器的泛化能力來進行篩選的，這是一個自動進行的過程。這樣的處理符合人類在認知復雜事物時分側面、多方位考慮的過程。

實驗結果表明經多側面特征提取的機器學習方法的有效性，達到了預期的效果。采用多側面方法并沒有作重復學習[4]，多側面特征提取本質上是一種屬性約簡，和其他屬性約簡方法的對比研究將是下一步研究重要目標工作。

參考文獻

[1]張燕平，張鈴，吳濤.機器學習中多側面遞進算法MIDA[J].電子學報，2005，33(2):328～331.

[2]丁衛平，鄧偉，管致錦.基于粗糙集的屬性約簡優化算法研究[J].蘇州大學學報(自然科學版)，2008，4，24(2):52～56.

[3]孟國艷.一種改進的屬性約簡方法[J].忻州師范學院學報，2008，24(5):11～13.

[4]張燕平.機器學習中特征提取的新方法—重復覆蓋算法[J].安徽大學學報，2002，26(2):9～13.