[發明專利]基于線性規劃的高效超平面分類方法

無效

• 申請號: 201110157534.1
• 申請日: 2011-06-13
• 公開（公告）號: CN102236704A
• 公開（公告）日: 2011-11-09
• 發明（設計）人: 劉怡光
• 申請（專利權）人: 劉怡光
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及模式識別、機器學習領域，尤其是基于線性規劃實現的高效分類方法。?

背景技術

超平面常用于構建分類器，如在二分類情況時，根據經驗風險最小原則，可簡單地尋找一個超平面使得錯分樣本最少（F.?W.?SMITH,?1968.）。由于根據經驗風險最小原則確定的超平面常常推廣能力較弱，不適應現代模式識別發展需要。為此，在結構風險最小原則下，基于最優超平面提出了支持向量機（V.?N.?Vapnik,?1998）。支持向量機旨在尋找一超平面，在超平面垂直方向兩類樣本的兩個最近鄰點具有最大距離。支持向量機推廣能力佳，已獲得較廣泛應用，但是在使用支持向量機時需要求解二次數學規劃問題，計算量大，尤其是具有海量訓練樣本時，支持向量機的訓練問題往往成為應用桎梏。在優化規模相同時，一次規劃問題相對于二次規劃問題常具有較高求解效率。結合一次規劃和支持向量機優點，Q.?Wu等提出了一次規劃支持向量機（Q.?Wu?and?D.-X.?Zhou,?2005），可適應大規模樣本的分類。一次規劃支持向量機具有多種形式，有些以減小超平面一次項系數向量的二次范數為目的（V.?N.?Vapnik,?1998），把規模為k的二次規劃問題等價為規模為k²的一次規劃問題；有些僅以增大最近鄰樣本的距離為目的（W.?Zhou,?L.?Zhang?&?L.?Jiao,?2002），與支持向量機的優化效果具有明顯卻別，支持向量機不僅使得最近鄰樣本在某個方向相距最大，同時也考慮了使得兩類樣本易于區分的整體優化效應。?

發明內容

本發明的目的是克服現有技術不足，提供基于線性規劃的高效超平面分類方法，包括兩類共五個分類器。?

第一類基于線性規劃的高效超平面分類方法包括兩個分類器，其實現步驟如下：?

(a)????尋找一個超平面，使得兩類樣本分別在超平面正負兩邊，且兩類樣本離超平面距離和盡量遠，用以下一次規劃問題確定超平面

(b)????由于樣本不總是線性可分，引入松弛參數和，使得部分負樣本可位于超平面正方向，部分正樣本位于超平面負方向，但錯分樣本應盡量貼近超平面。用以下一次規劃問題實現基于LPHC-1的第一個分類器

(c)????一次規劃問題計算量與變量規模密切相關，為減小計算量，提高效率，用代替，我們得到基于LPHC-1的第二個分類器，用以下一次規劃問題確定超平面

(d)????分類器LPHC-1-1和LPHC-1-2的分類規則如下，即位于超平面及其正方向的樣本歸類為正樣本，否則歸類為負樣本

。

LPHC-1-1和LPHC-1-2都只有一個超平面，不能解決“異或”分類問題。為此，用兩個超平面建立第二類分類方法，包括三個分類器，其實現步驟如下：?

(a)??所有正樣本都位于第一個超平面正方向，負樣本位于負方向；對第二個超平面，負樣本位于正方向，正樣本位于負方向。用以下一次規劃問題確定兩個超平面

(b)??引入松弛參數，使得第一個超平面盡量貼近正樣本，遠離負樣本；第二個超平面盡量貼近負樣本，遠離正樣本。用以下一次規劃問題確定兩個超平面

(c)??為減小變量規模，提高確定兩超平面的計算效率，用代替

(d)??為進一步減小變量規模，分析LPHC-2-2，得到第三個分類器

(e)??兩超平面把樣本空間分割成多個區域，基于產生兩超平面的優化思路和相互關系，?LPHC-2-1、LPHC-2-2和LPHC-2-3采用以下分類準則：樣本在L1正方向L2負方向的樣本歸類為正樣本，樣本在L1負方向L2正方向的樣本歸類為負樣本，對其他樣本，如果更接近L1確定為正樣本，更接近L2確定為負樣本。

??

通過核函數方法，提高LPHC系列分類器的非線性分類適應能力。用替代樣本，并且用表述核函數改造后的一個超平面。經過核函數改造后，LPHC系列分類器成為KLPHC-1-1、KLPHC-1-2、KLPHC-2-1、KLPHC-2-2、KLPHC-2-3。由于當核函數取內積函數時，KLPHC系列分類器就退化為LPHC-1-1、LPHC-1-2、LPHC-2-1、LPHC-2-2、LPHC-2-3。實用中KLPHC系列分類器具有更廣泛適應性。