惰性學(xué)習(xí)中實(shí)例選擇研究與應(yīng)用.pdf

1、惰性學(xué)習(xí)不同于傳統(tǒng)的急性學(xué)習(xí)，它具有訓(xùn)練代價(jià)少、假說(shuō)空間豐富、漸進(jìn)學(xué)習(xí)能力強(qiáng)、能進(jìn)行增量學(xué)習(xí)等優(yōu)點(diǎn)，因而被廣泛應(yīng)用于數(shù)據(jù)挖掘和網(wǎng)絡(luò)信息處理等領(lǐng)域。然而由于惰性學(xué)習(xí)在分類查詢實(shí)例時(shí)，需要計(jì)算查詢實(shí)例與所有存儲(chǔ)實(shí)例的距離，因而存在查詢代價(jià)大的缺點(diǎn)。為了解決這個(gè)問(wèn)題，在惰性學(xué)習(xí)誕生后不久，就出現(xiàn)了第一個(gè)實(shí)例選擇算法，直至今天仍不斷有新的實(shí)例選擇算法出現(xiàn)?？梢妼?shí)例選擇算法是提高惰性學(xué)習(xí)性能的重要方法，這同時(shí)也反映出現(xiàn)有實(shí)例選擇算法仍有不足。為此

2、，本文展開了如下研究。
　　首先，進(jìn)行了實(shí)例的特定鄰域的分析。本文歸納和總結(jié)了一類經(jīng)典的實(shí)例選擇算法的共同點(diǎn)：它們都使用一種由實(shí)例的最近異類實(shí)例限定的特定鄰域，并且顯式或隱式地用到由這個(gè)特定鄰域得到的兩個(gè)同類實(shí)例集。可見這個(gè)特定鄰域和這兩個(gè)同類實(shí)例集在實(shí)例選擇中有著重要作用。然而這些算法都忽視了限定鄰域的最近異類實(shí)例在實(shí)例選擇中的重要作用。本文由此提出了兩個(gè)新的集合：最近異類實(shí)例集和異類實(shí)例覆蓋集。然后分析了這兩個(gè)集合在實(shí)例選擇的

3、作用，由此設(shè)計(jì)了一種邊界實(shí)例選擇算法（BIS）。最后在二維模擬數(shù)據(jù)集和UCI數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，BIS算法能較大量地約簡(jiǎn)實(shí)例存儲(chǔ)量，并在很多數(shù)據(jù)集上取得較好的分類精度，但是在部分?jǐn)?shù)據(jù)集上得到的選擇集的分類精度不夠理想。這也促使本文從更深層次——實(shí)例的分類性能上分析實(shí)例選擇問(wèn)題。
　　其次，進(jìn)行了實(shí)例分類性能評(píng)價(jià)函數(shù)的研究。由于經(jīng)典的算法中沒(méi)有考慮實(shí)例覆蓋交疊的情況，對(duì)實(shí)例的分類性能的評(píng)價(jià)不夠精確，因此本文分析和使用了

4、更精確的相對(duì)同類實(shí)例覆蓋來(lái)評(píng)價(jià)實(shí)例在分類同類實(shí)例的潛在貢獻(xiàn)。同時(shí)，由于實(shí)例的最近異類實(shí)例集和異類實(shí)例覆蓋集也存在交疊的情況，因此本文分析和定義了相對(duì)異類實(shí)例覆蓋來(lái)精確地評(píng)價(jià)實(shí)例在維護(hù)分類邊界方面的貢獻(xiàn)。然后，同時(shí)從同類實(shí)例的角度和異類實(shí)例的角度綜合考慮，定義了更精確和全面的實(shí)例分類性能評(píng)價(jià)函數(shù)，以此作為設(shè)計(jì)實(shí)例選擇算法的基礎(chǔ)。
　　再次，進(jìn)行了實(shí)例選擇算法的設(shè)計(jì)。針對(duì)直接使用實(shí)例分類性能函數(shù)進(jìn)行實(shí)例選擇時(shí)，需要優(yōu)化分類性能閾值選擇

5、的問(wèn)題，本文設(shè)計(jì)了一種一致子集的實(shí)例選擇方式，避開了這個(gè)問(wèn)題。由此設(shè)計(jì)了基于實(shí)例分類性能的一致子集實(shí)例選擇算法（IPECSS）。然后，根據(jù)IPECSS算法的特點(diǎn)，通過(guò)實(shí)驗(yàn)系統(tǒng)地分析了IPECSS算法的性能，并在二維模擬數(shù)據(jù)集和UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的32個(gè)數(shù)據(jù)集上與經(jīng)典的實(shí)例選擇算法進(jìn)行了實(shí)驗(yàn)比較。實(shí)驗(yàn)結(jié)果表明，IPECSS算法能在大幅度約簡(jiǎn)實(shí)例集的存儲(chǔ)量的同時(shí)，保持著與訓(xùn)練實(shí)例集相同或更好分類精度，并較大地提高了分類效率。