基于尺度化凸殼的最大間隔分類(lèi)方法研究.pdf

1、以SVM為代表的最大間隔機(jī)器學(xué)習(xí)方法，因?yàn)榫哂泻?jiǎn)潔的數(shù)學(xué)形式、直觀的幾何解釋和良好的泛化能力，在模式分類(lèi)、數(shù)據(jù)挖掘等領(lǐng)域受到越來(lái)越多的關(guān)注。本文受壓縮凸殼思想的啟發(fā)，提出了一種新的用最大間隔思想構(gòu)造線性不可分問(wèn)題分類(lèi)器的方法——尺度化凸殼（Scaled Convex Hull, 簡(jiǎn)記為SCH）方法。該方法可以把求解線性不可分問(wèn)題轉(zhuǎn)化為求解兩類(lèi)樣本分別生成的SCH間的最近點(diǎn)對(duì)的問(wèn)題。通過(guò)使用核技巧，該方法還可以用于解決非線性分類(lèi)問(wèn)題。

2、r>　　 首先，給出了SCH的定義，證明了與其相關(guān)的一些性質(zhì)，這些性質(zhì)從理論上保證了在采用SCH構(gòu)造分類(lèi)器時(shí)的推廣能力。SCH的大小是由尺度因子控制的，因此，通過(guò)不斷地減小尺度因子，兩個(gè)SCH不斷縮小直至可分。然后，就可以通過(guò)計(jì)算幾何中已有的成熟的最近點(diǎn)對(duì)算法，求解SCH間的最近點(diǎn)對(duì)，把垂直平分連接最近點(diǎn)對(duì)線段的超平面作為線性不可分問(wèn)題的分類(lèi)超平面，其對(duì)應(yīng)的分類(lèi)器稱(chēng)為基于SCH的最大間隔分類(lèi)器。這種構(gòu)造分類(lèi)器的思想和用壓縮凸殼構(gòu)造SV

3、M最大間隔分類(lèi)器的思想是一致的，因此，該方法也可以看成是一種變形的SVM方法。SCH方法改進(jìn)了壓縮凸殼方法的不足之處，這是因?yàn)镾CH與原凸殼有相同數(shù)量的頂點(diǎn)，這就給求解最近點(diǎn)對(duì)提供簡(jiǎn)單的方法，并且求解最近點(diǎn)對(duì)的復(fù)雜度與尺度因子無(wú)關(guān)。此外， SCH的形狀不隨尺度因子的變化而變化，這也是稱(chēng)之為尺度化凸殼的原因。
　　 其次，介紹了求解最近點(diǎn)對(duì)的三種計(jì)算幾何算法，即Gilbert算法、SK算法和MDM算法，把這三種算法應(yīng)用到SCH最近

4、點(diǎn)對(duì)的求解中去。并與壓縮凸殼的情形下的三種算法進(jìn)行了計(jì)算復(fù)雜度的對(duì)比分析，說(shuō)明了SCH方法的優(yōu)點(diǎn)。
　　 再次，SCH方法還可用于解決類(lèi)不平衡問(wèn)題。一般地，對(duì)于類(lèi)不平衡問(wèn)題，正類(lèi)樣本數(shù)較少，生成的凸殼相對(duì)也較小，而負(fù)類(lèi)點(diǎn)生成的凸殼較大，在這種情況下，得到的分類(lèi)面會(huì)傾向于誤分正類(lèi)樣本。而利用本文提出的SCH方法，通過(guò)不同程度的縮小兩個(gè)凸殼，則可以解決這個(gè)問(wèn)題。即對(duì)于負(fù)類(lèi)點(diǎn)的凸殼，賦予小的尺度因子，而正類(lèi)點(diǎn)的凸殼，則賦予大的尺度因子