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

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

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

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

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