[發(fā)明專利]基于線性規(guī)劃的高效超平面分類方法

無效

• 申請?zhí)枺?/td>: 201110157534.1
• 申請日: 2011-06-13
• 公開（公告）號: CN102236704A
• 公開（公告）日: 2011-11-09
• 發(fā)明（設(shè)計(jì)）人: 劉怡光
• 申請（專利權(quán)）人: 劉怡光
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.基于線性優(yōu)化實(shí)現(xiàn)的快速超平面分類方法可歸為兩類，分別需要一個和兩個超平面，其特征在于：

1)?建立超平面時，優(yōu)化各樣本與超平面的距離和；

2)?用數(shù)學(xué)一次規(guī)劃方法求解超平面，求解速度快；

3)?用松弛參數(shù)提高分類方法的非線性分類適應(yīng)性；

4)?用核方法進(jìn)一步提高分類方法非線性分類能力。

2.根據(jù)權(quán)利要求1所述優(yōu)化各樣本與超平面距離和，其特征在于：優(yōu)化各樣本????????????????????????????????????????????????與超平面?的距離和時，優(yōu)化而不是優(yōu)化，如等。

3.?根據(jù)權(quán)利要求1所述的第一類快速超平面分類方法，包括兩個分類器LPHC-1-1和LPHC-1-2，其特征在于包括以下步驟：

步驟1：對線性可分的兩類樣本建立一超平面L：y=w^Tx+b，使得y_i=1的正樣本x_i滿足w^Tx_i+b>0，y_i=-1的負(fù)樣本x_i滿足w^Tx_i+b<0，并且為使得所建立超平面具有好的分類推廣能力，盡量增大各樣本與超平面的距離和：argmax_w,b∑_i?|w^Tx_i+b|，即：對于線性可分情況我們提出LPHC-1分類器，其超平面L：y=w^Tx+b從以下關(guān)系解出

??

步驟2：LPHC-1分類器不適于對線性不可分樣本進(jìn)行分類，為此引入松弛參數(shù)ξ_i≥0和η_i≥0，允許少部分y_i=1的正樣本位于超平面L的負(fù)方向，w^Tx_i+b>-ξ_i；少部分y_i=-1的負(fù)樣本位于超平面L的正方向，w^Tx_i+b<η_i；且錯分的樣本應(yīng)盡可能少，因此從LPHC-1衍生出第一類快速超平面分類方法的第一個分類器：

步驟3：線性優(yōu)化速度與變量個數(shù)密切相關(guān)，為加快求解速度，對LPHC-1-1中ξ_i≥0和η_i≥0分別用一個數(shù)ξ≥0和η≥0替代，得到第二個分類器

步驟4：LPHC-1-1和LPHC-1-2分類器的分類規(guī)則為：如果樣本位于超平面正方向則把樣本歸類為正樣本，在超平面負(fù)方向歸類為負(fù)樣本。

4.根據(jù)權(quán)利要求1所述的第二類快速超平面分類方法，包括LPHC-2-1、LPHC-2-2和LPHC-2-3三個分類器，其特征在于：

步驟1：建立兩個超平面L1和L2，使得L1緊貼y_i=1的正樣本，盡量遠(yuǎn)離y_i=-1的負(fù)樣本；L2緊貼y_i=-1的負(fù)樣本，遠(yuǎn)離y_i=1的正樣本，即從以下優(yōu)化問題中求解L1和L2

步驟2：對LPHC-2引入松弛參數(shù)ξ_i≥0和η_i≥0，使得正樣本位于L1的正方向，并且離L1的最小距離盡可能大；允許少部分負(fù)樣本位于L1的正方向，但這些錯分的樣本應(yīng)盡可能貼近L1；類似地建立L2；即從以下一次規(guī)劃問題求解L1和L2

?步驟3：為減少變量數(shù)，用ξ≥0代替ξ_i≥0，用η≥0代替η_i≥0，得到分類器LPHC-2-2

步驟4：為進(jìn)一步減少變量數(shù)，從LPHC-2-2得到

步驟5：兩超平面把樣本空間分割成多個區(qū)域，基于產(chǎn)生兩超平面的優(yōu)化思路和相互關(guān)系，?LPHC-2-1、LPHC-2-2和LPHC-2-3采用以下分類準(zhǔn)則：樣本在L1正方向L2負(fù)方向的樣本歸類為正樣本，樣本在L1負(fù)方向L2正方向的樣本歸類為負(fù)樣本，對其他樣本，如果更接近L1確定為正樣本，更接近L2確定為負(fù)樣本。

5.根據(jù)權(quán)利要求1所述的進(jìn)一步提高LPHC-1-1、LPHC-1-2、LPHC-2-1、LPHC-2-2、LPHC-2-3非線性分類能力的核方法，其特征在于：

1)?用向量替代樣本；

2)?用作為超平面的基本表述形式；

3)?通過核方法改造，LPHC-1-1、LPHC-1-2、LPHC-2-1、LPHC-2-2、LPHC-2-3分類器改進(jìn)為KLPHC-1-1、KLPHC-1-2、KLPHC-2-1、KLPHC-2-2、KLPHC-2-3；當(dāng)核函數(shù)取內(nèi)積函數(shù)時，KLPHC系列分類器就是LPHC系列分類器，實(shí)際應(yīng)用中一般用KLPHC系列分類器。