多側(cè)面遞進(jìn)算法在機(jī)器學(xué)習(xí)中的應(yīng)用

摘 要:本文在已有文獻(xiàn)建立的機(jī)器學(xué)習(xí)方法的基礎(chǔ)上，提出將多側(cè)面遞進(jìn)算法作為數(shù)據(jù)預(yù)處理方法，并用UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明這是一種行之有效的特征提取方法。

關(guān)鍵詞:多側(cè)面 特征提取 機(jī)器學(xué)習(xí)

中圖分類號(hào):G6文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1674-098X(2012)04(b)-0149-02

1 引言

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

2 多側(cè)面方法

2.1 方法介紹

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

我們以一個(gè)簡(jiǎn)單的例子來說明多側(cè)面特征提取方法的基本思想。設(shè)樣本集

，即分為兩類，其中每個(gè)樣本對(duì)應(yīng)一位學(xué)生，每一列對(duì)應(yīng)一門課程成績(jī)，即一個(gè)屬性，院系為決策信息。具體取值如表1所示。

特征提取的是以類內(nèi)區(qū)分盡可能小和類間區(qū)分盡可能大為目標(biāo)的。然而觀察表1所示樣本集合，我們卻找不到這樣的屬性子集，因?yàn)閷?duì)每一門功課，兩個(gè)院系都有一部分學(xué)生成績(jī)非常接近(如表中圓角矩形所示)。換言之，每個(gè)屬性對(duì)樣本的區(qū)分能力都有盲區(qū)。在這種情況下，如果非要根據(jù)四門功課成績(jī)之差絕對(duì)值的大小來選取一個(gè)屬性子集的話，就會(huì)有點(diǎn)牽強(qiáng)附會(huì)。因?yàn)椴还苓x取的子集是什么，都有這個(gè)子集無法處理的情況，亦即會(huì)很明顯地降低原屬性集合的分辨能力。

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

2.2 多側(cè)面特征提取方法性能分析

假設(shè)問題規(guī)模為，即個(gè)樣本，個(gè)屬性;不失一般性，假設(shè)對(duì)特征提取效果評(píng)價(jià)過程是借助學(xué)習(xí)效果來實(shí)現(xiàn)的，設(shè)所使用的學(xué)習(xí)方法的計(jì)算量為;又假設(shè)每次提取的特征子集為原屬性集合容量的，為分側(cè)面次數(shù)，當(dāng)整個(gè)樣本集合能很快特征提取結(jié)束時(shí)，較小，即摸索的速度很快，逼近的過程很短;若不能很快結(jié)束，則限定一個(gè)最大分側(cè)面次數(shù)。

首先若不進(jìn)行特征提取，直接進(jìn)行學(xué)習(xí)的計(jì)算量即為

再考慮多側(cè)面方法計(jì)算量為:

，其中，=，=，一般，，假設(shè)設(shè)、均為線性函數(shù)，所以

得出多側(cè)面方法具有較小的計(jì)算復(fù)雜性，但只是在一個(gè)常數(shù)級(jí)的較小。這是因?yàn)槲覀兗僭O(shè)、均為線性函數(shù)，而一般是沒有這樣低復(fù)雜度的學(xué)習(xí)算法的。一旦變成關(guān)于的二次方以上的函數(shù)，提取出來時(shí)，就是二次方的分母;若是關(guān)于的二次方以上的函數(shù)，則有成立，所以能保證一定小于，且越大，即分的側(cè)面越多，越能降低計(jì)算的復(fù)雜度;原學(xué)習(xí)算法的時(shí)間復(fù)雜度越高，多側(cè)面方法的性能提高越明顯。

3 實(shí)驗(yàn)

為驗(yàn)證多側(cè)面方法在特征提取中的有效性，用從UCI數(shù)據(jù)集上下載的一批數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。表2為經(jīng)過多側(cè)面特征提取的機(jī)器學(xué)習(xí)方法和原學(xué)習(xí)方法各項(xiàng)參數(shù)的對(duì)比。表中實(shí)驗(yàn)結(jié)果為做10次實(shí)驗(yàn)取的平均值。

實(shí)驗(yàn)結(jié)果表明，經(jīng)多側(cè)面特征提取對(duì)測(cè)試樣本的識(shí)別率和正確率都有明顯提高，且這種提高不受樣本的維數(shù)及測(cè)試樣本數(shù)與學(xué)習(xí)樣本數(shù)的比例等各項(xiàng)因素的影響。

4 結(jié)論

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

實(shí)驗(yàn)結(jié)果表明經(jīng)多側(cè)面特征提取的機(jī)器學(xué)習(xí)方法的有效性，達(dá)到了預(yù)期的效果。采用多側(cè)面方法并沒有作重復(fù)學(xué)習(xí)[4]，多側(cè)面特征提取本質(zhì)上是一種屬性約簡(jiǎn)，和其他屬性約簡(jiǎn)方法的對(duì)比研究將是下一步研究重要目標(biāo)工作。

參考文獻(xiàn)

[1]張燕平，張鈴，吳濤.機(jī)器學(xué)習(xí)中多側(cè)面遞進(jìn)算法MIDA[J].電子學(xué)報(bào)，2005，33(2):328～331.

[2]丁衛(wèi)平，鄧偉，管致錦.基于粗糙集的屬性約簡(jiǎn)優(yōu)化算法研究[J].蘇州大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，4，24(2):52～56.

[3]孟國(guó)艷.一種改進(jìn)的屬性約簡(jiǎn)方法[J].忻州師范學(xué)院學(xué)報(bào)，2008，24(5):11～13.

[4]張燕平.機(jī)器學(xué)習(xí)中特征提取的新方法—重復(fù)覆蓋算法[J].安徽大學(xué)學(xué)報(bào)，2002，26(2):9～13.