最小化類內(nèi)距離和分類算法

王曉初 王士同 包 芳 蔣亦樟

?

最小化類內(nèi)距離和分類算法

王曉初*①②王士同①包 芳②蔣亦樟①

①(江南大學數(shù)字媒體學院 無錫 214122)②(江陰 214405)

支持向量機分類算法引入懲罰因子來調(diào)節(jié)過擬合和線性不可分時無解的問題，優(yōu)點是可以通過調(diào)節(jié)參數(shù)取得最優(yōu)解，但帶來的問題是允許一部分樣本錯分。錯分的樣本在分類間隔之間失去了約束，導(dǎo)致兩類交界處樣本雜亂分布，并且增加了訓(xùn)練的負擔。為了解決上述問題，該文根據(jù)大間隔分類思想，基于類內(nèi)緊密類間松散的原則，提出一種新的分類算法，稱之為最小化類內(nèi)距離和(Intraclass-Distance-Sum-Minimization, IDSM)分類算法。該算法根據(jù)最小化類內(nèi)距離和準則構(gòu)造訓(xùn)練模型，通過解析法求解得到最佳的映射法則，進而利用該最佳映射法則對樣本進行投影變換以達到類內(nèi)間隔小類間間隔大的效果。相應(yīng)地，為解決高維樣本分類問題，進一步提出了該文算法的核化版本。在大量UCI數(shù)據(jù)集和Yale大學人臉數(shù)據(jù)庫上的實驗結(jié)果表明了該文算法的優(yōu)越性。

支持向量機；懲罰因子；大間隔分類思想；類內(nèi)距離和；映射法則

1 引言

分類一直是人工智能和模式識別等領(lǐng)域研究的熱點，分類算法廣泛應(yīng)用于數(shù)據(jù)挖掘、圖像處理、視頻跟蹤與檢測、智能收索、推薦系統(tǒng)、識別系統(tǒng)等領(lǐng)域，所以分類算法的發(fā)展與進步改變著人們的生產(chǎn)和生活方式。 目前常用的分類算法有決策樹算法、貝葉斯分類器、K近鄰算法、fisher判別分析法，神經(jīng)網(wǎng)絡(luò)算法和SVM等分類算法。決策樹[1,2]是通過一定的規(guī)則對樣本已知屬性進行選擇達到分類目的的算法。主要的決策樹算法有ID3, C4.5等。ID3算法的目的在于減少樹的深度，但不能處理具有連續(xù)值和具有缺失的數(shù)據(jù)屬性。C4.5算法在ID3算法的基礎(chǔ)上對于預(yù)測變量的缺值等方面作了較大的改進，使之適合于分類和回歸問題。但決策樹本身有容易過度擬合及忽略了數(shù)據(jù)集中屬性之間的相關(guān)性等缺點。貝葉斯分類器[3,4]的分類原理是對屬性決定類別可能性大小用訓(xùn)練樣本進行判斷，然后對新樣本進行預(yù)測。貝葉斯分類算法假設(shè)數(shù)據(jù)屬性之間是相對獨立的，而現(xiàn)實中的問題并不總是這樣。K近鄰算法原理簡單易于實現(xiàn)，但它假設(shè)樣本每個屬性的作用都是相同的，當數(shù)據(jù)集包含有許多不相關(guān)屬性時，會誤導(dǎo)分類過程。fisher判別分析法是找到一個映射法則，使得樣本投影到該空間后能在保證方差最小的情況下，將不同的樣本很好分開，但該算法僅僅用方差來衡量樣本的離散程度，具有一定局限性。人工神經(jīng)網(wǎng)絡(luò)由眾多的神經(jīng)元可調(diào)的連接權(quán)值連接而成，具有大規(guī)模并行處理、分布式信息存儲、良好的自組織自學習能力等特點。BP (Back Propagation)網(wǎng)絡(luò)[11,12]是一種按誤差逆向傳播算法訓(xùn)練的多層前饋網(wǎng)絡(luò)，是目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型之一。人工神經(jīng)網(wǎng)絡(luò)算法和SVM (Support Vector Machine)都支持非線性分類，因此都有很高的精確率，但人工神經(jīng)網(wǎng)絡(luò)算法的可解釋性不強，并且需要大量的參數(shù)。而SVM以其良好的抗噪聲性能在小樣本的分類上優(yōu)秀的表現(xiàn)成為了目前最為常用的分類算法，但SVM最求間隔最大化，并沒有太多關(guān)注類內(nèi)樣本間的關(guān)系，并且引入懲罰因子后增加了訓(xùn)練的難度。

關(guān)于SVM的改進大多在時間方面的優(yōu)化：文獻[17~19]提出SMO(Sequential Minimal Optimization), SVMlight和libSVM等算法，其中SVMlight和libSVM已經(jīng)成為目前最常用的方法，這些算法將SVM時間復(fù)雜度由降低為。其他改進如文獻[20]提出的拉格朗日支持向量機(LSVNM)等，最好的情況下可以達到。另外文獻[21~23]將SVM推廣到半監(jiān)督領(lǐng)域。文獻[24]提出了一種改進的支持向量機NN-SVM算法，它先對訓(xùn)練集進行修剪，根據(jù)每個樣本與其最近鄰類標的異同決定其取舍，然后再用SVM訓(xùn)練得到分類器，改善支持向量機的泛化能力。

上述方法都沒有很好地解決引入懲罰因子后，錯分的樣本在分類間隔之間失去了約束，導(dǎo)致兩類交界處樣本雜亂分布的問題。本文提出的最小化類內(nèi)距離和分類算法，利用樣本通過映射法則投影到1維空間后可以在該1維空間重新分布的特性，對樣本在該1維空間的分布進行訓(xùn)練。歸一化投影后正負標簽樣本均值的相對間隔，且最小化投影后正負標簽樣本的類內(nèi)距離和。訓(xùn)練后得到一個映射法則，樣本通過該映射法則投影到1維空間后重新分布為線性可分的形式，同時該方法可引入核函數(shù)用于線性不可分的情況。該方法通過最小化類內(nèi)距離和，使得樣本投影到1維空間后同類樣本的分布向各自均值集中，非同類樣本產(chǎn)生間隔，使得分類更加容易?？偟貋碚f本研究的貢獻主要有以下幾個方面。(1)從距離和大間隔的角度提供了一種新的實現(xiàn)類內(nèi)差異最小化，類間差異最大化思想下的分類算法。提出了最小化類內(nèi)距離和準則，用于構(gòu)造大間隔思想下的分類模型?？梢赃x擇不同的距離公式用于不同的要求。(2)適當避免了支持向量機分類算法引入懲罰因子來調(diào)節(jié)過擬合和線性不可分時無解的問題時允許一部分樣本錯分，錯分的樣本在分類間隔之間失去了約束，導(dǎo)致兩類交界處樣本雜亂分布的問題。同時優(yōu)化了線性訓(xùn)練時參數(shù)選優(yōu)帶來的額外開銷。

2 大間隔分類算法

近年來機器學習領(lǐng)域，間隔成為代表性的特征評估策略之一，已成為研究的熱點。間隔概念首次由Vapnik在構(gòu)建SVM模型時提出，SVM也成為運用了大間隔思想最具代表算法。圖1為2維空間中對樣本用SVM分類算法分類原理圖，其中橫、縱坐標分別表示樣本的兩個維度。

如圖1所示，SVM的目的就是通過間隔最大化，找到最優(yōu)超平面，其中且。當訓(xùn)練樣本線性可分時，則存在超平面使得訓(xùn)練樣本中的樣本滿足：

圖1 SVM分類原理圖

對于非線性問題，SVM通過引入核函數(shù)，其對應(yīng)的對偶問題式(4)變?yōu)?/p>

最優(yōu)決策超平面式(4)變?yōu)?/p>

支持向量機在分類過程中，利用結(jié)構(gòu)化風險最小原理，求出最優(yōu)決策超平面。并且引入懲罰因子來調(diào)節(jié)過擬合和線性不可分時無解的問題，這樣做的好處是可以通過調(diào)節(jié)參數(shù)取得最優(yōu)解，但同樣帶來的問題是訓(xùn)練時允許一部分樣本錯分，而允許錯分的樣本并不一定是噪聲，錯分的樣本在分類間隔之間失去了約束，導(dǎo)致錯分的樣本在兩類交界處樣本雜亂分布；另外，引入?yún)?shù)后，增加了訓(xùn)練的成本。

3 最小化類內(nèi)距離和分類算法

鑒于支持向量機的上述缺點，本文依據(jù)大間隔思想提出了最小化類內(nèi)距離和(Intraclass- Distance-Sum-Minimization, IDSM)分類算法，該算法的原理是：將樣本通過映射法則做投影變換，以最小化類內(nèi)距離和為準則構(gòu)造一個最大化類間間隔的訓(xùn)練模型，對該模型求解，尋找到最佳的映射法則。樣本經(jīng)過該最佳映射法則轉(zhuǎn)化為線性可分問題。通過與之匹配的判別規(guī)則來判定未知樣本的屬性。由于本文采用最小化類內(nèi)距離和準則，使得同類樣本聚集，非同類樣本相對遠離，從而兩類之間形成間隔。這樣所有訓(xùn)練樣本都向同類樣本聚集。一定程度上解決了兩類交界處樣本雜亂分布的問題。另外，線性IDSM算法并不需要調(diào)節(jié)參數(shù)，相比支持向量機訓(xùn)練更加容易。圖2展示了IDSM算法的構(gòu)造原理。

圖2 IDSM算法構(gòu)造原理

為了更加清晰地說明兩者的區(qū)別，本文在兩類服從高斯分布的2維數(shù)據(jù)(如圖3(a))上進行模擬實驗， 圖3(b)是懲罰因子取0.001時的SVM的分類結(jié)果的3維圖，可清晰看到兩類交界處附近點的分布很雜亂。圖3(c)是歐氏距離和用于本文算法所得的結(jié)果，可以看到兩類樣本在投影后的空間上均值相對間隔為1，并且兩類樣本聚集在同類均值附近，類內(nèi)更加緊湊，類間相對形成間隔。

3.1 IDSM算法框架的提出

樣本間的距離和反映了樣本在類內(nèi)的聚集程度。距離和越小，樣本越集中。假設(shè)兩樣本間的距離用表示。訓(xùn)練樣本集包含個特征為的樣本。由訓(xùn)練集的前個樣本組成。

圖3 SVM與IDSM算法區(qū)別示意圖

正樣本和負樣本的均值表達式為

歸一化正負樣本均值差且最小化類內(nèi)距離和，得到IDSM算法訓(xùn)練模型：

得到的模型可以用遞歸最小二乘算法進行求解，進而得到最佳映射法則。對于測試樣本，通過最優(yōu)映射法則投影變換得到：。由于IDSM算法訓(xùn)練模型使得投影后的樣本類內(nèi)距離和達到最小，同類樣本向各自均值聚集，從而類間產(chǎn)生間隔。那么，通過最優(yōu)映射法則變換得到的測試樣本便具有靠近同類樣本均值，遠離非同類樣本的特性。因此，可以通過比較經(jīng)過最佳映射法則投影變換后測試樣本與正負訓(xùn)練樣本均值之間的距離來判斷樣本的屬性。假設(shè)測試樣本到正訓(xùn)練樣本均值的距離，到負訓(xùn)練樣本均值的距離。IDSM算法具體判別規(guī)則：

上面介紹了IDSM算法的訓(xùn)練模型和判別方法，IDSM算法提供了一個框架，可以在不同的需求下選擇不同的距離公式。本文選用歐氏距離公式來推理驗證IDSM算法的有效性。歐氏距離公式下的IDSM算法簡稱為EIDSM。3.2節(jié)是對EIDSM算法的推導(dǎo)。

3.2 EIDSM算法

歐氏距離作為IDSM算法中距離和的衡量標準，投影變換后兩樣本間的距離為

那么，歐氏距離和表達式：

那么歐氏距離和式(15)，式(16)衡量的最小化類內(nèi)距離和分類算法(EIDSM算法)，去掉常數(shù)2，不影響結(jié)果，得目標函數(shù)：

3.3 非線性EIDSM算法

設(shè)

此時正樣本歐氏距離和的非線性表達式可化簡為矩陣形式：

同理，負樣本歐氏距離和的非線性表達式可化簡為矩陣形式：

那么非線性歐氏距離和式(24)，式(25)衡量的最小化類內(nèi)距離和分類算法(非線性EIDSM)，去掉常數(shù)2，不影響結(jié)果，可以寫成如式(26)目標函數(shù)：

判別方法見3.1節(jié)式(12)。

4 目標函數(shù)求解算法

目標函數(shù)式(17)，式(26)是非線性有約束優(yōu)化問題，并且是凸優(yōu)化問題。有多種方法可以選擇，比如擬牛頓法，Rosen梯度投影法等，線性和非線性目標函數(shù)可以化簡到相同的形式，我們只解析線性目標函數(shù)算法過程。這里我們用解析法對該優(yōu)化問題進行求解，算法步驟如下：

步驟 2 目標函數(shù)式(17)可寫為

步驟 7 重復(fù)步驟5，步驟6直到收斂或滿足停止條件；

步驟 9 根據(jù)式(12)對新樣本進行歸類。

分析最小二乘的遞歸求解過程，本文算法在線性和非線性的時間復(fù)雜度分別為和，為最小二乘算法收斂時循環(huán)的次數(shù)。

5 實驗與分析

設(shè)計了兩組試驗來驗證本文方法的有效性。第1組用UCI公共有效數(shù)據(jù)集中的10個數(shù)據(jù)集進行隨機抽取75%的樣本用于訓(xùn)練，剩余的25%用于測試，記錄正確率和每次運行所用時間(s)。表1列出了10個UCI數(shù)據(jù)集的信息。第2組用Yale大學人臉數(shù)據(jù)庫，在小樣本下，不斷增加訓(xùn)練樣本個數(shù)，記錄正確率和每次運行所用時間(s)。這樣設(shè)計可驗證其在小樣本上的表現(xiàn)。鑒于IDSM算法和fisher用于分類的算法[32]都具有使類內(nèi)樣本聚集的特點，相同之處在于他們都利用了最小化類內(nèi)差異的思想，區(qū)別在于IDSM算法是用距離來度量類內(nèi)和類間的差異，而fisher用于分類算法是用方差來度量類內(nèi)差異；其次IDSM算法由于引入了，對不平衡數(shù)據(jù)適應(yīng)性相對較好。所以用SVM和fisher作為EIDSM算法的對比試驗。表2包含了對實驗平臺和部分算法英文縮寫的說明。

5.1 UCI數(shù)據(jù)集

表1 UCI數(shù)據(jù)集信息

數(shù)據(jù)集

breast

cleve

German

haberman

heart

ionosphere

liver

pima

sonar

WBC

正樣本個數(shù)

81

160

300

225

150

126

145

268

111

444

負樣本個數(shù)

196

136

700

81

120

225

200

500

97

239

屬性個數(shù)

9

13

24

3

13

34

6

8

60

9

表2 實驗說明

實驗平臺

CPU: Intel(R)Core(TM)2Duo 3.00 GHz

RAM: 4.00 GB

系統(tǒng)：64位Win8.1操作系統(tǒng)

工具：32位MatlabR2012a

實驗中縮寫算法的全稱

LSVM：線性支持向量機

KSVM：非線性支持向量機

LFISHER: fisher線性判別分類算法

KFISHER：核fisher判別分類算法

LEIDSM：線性歐氏距離和衡量的最小化類內(nèi)距離和分類算法

KEIDSM：非線性歐氏距離和衡量的最小化類內(nèi)距離和分類算法

表3 UCI數(shù)據(jù)集的正確率測試結(jié)果(%)

UCI

LSVM

KSVM

LFISHER

KFISHER

LEIDSM

KEIDSM

breast

75.36±3.92

75.71±4.74

66.81±3.58

72.17±2.38

72.17±5.19

74.88±2.11

cleve

51.30±4.38

68.15±5.62

81.43±2.31

81.84±3.50

82.59±3.52

83.01±2.33

German

32.16±1.71

73.32±1.88

71.60±3.35

71.68±2.20

73.84±2.01

69.20±3.86

haberman

71.84±3.34

77.37±4.96

72.76±3.40

76.58±2.35

75.63±0.72

79.39±2.47

heart

51.34±3.89

68.36±2.45

83.13±4.39

80.30±4.34

87.16±3.27

80.63±3.11

ionosphere

88.41±8.22

91.82±3.25

87.16±2.99

87.27±3.15

90.91±2.41

89.39±5.37

liver

52.56±9.60

64.19±3.03

61.63±4.87

62.09±2.11

64.88±7.04

67.83±2.69

pima

46.06±17.68

69.06±4.37

73.83±3.09

69.08±3.13

77.92±2.46

76.83±2.27

sonar

79.52±4.17

86.92±2.85

73.00±6.14

73.63±8.64

75.00±3.85

80.13±4.84

WBC

96.37±1.12

97.89±0.89

96.19±0.88

97.54±0.64

96.61±0.96

97.96±0.89

均值

64.49±5.80

77.28±3.40

76.75±3.50

77.22±3.24

79.67±3.14

79.93±2.99

表4 UCI數(shù)據(jù)集的時間測試結(jié)果(s)

UCI

LSVM

KSVM

LFISHER

KFISHER

LEIDSM

KEIDSM

breast

0.1719±0.0082

0.0780±0.0061

0.0035±0.0004

0.1156±0.0301

0.0040±0.0004

0.1780±0.0060

cleve

0.4265±0.2948

0.0961±0.0039

0.0031±0.0003

0.0906±0.0007

0.0043±0.0003

0.0746±0.0028

German

3.7270±0.5067

0.6778±0.0139

0.0094±0.0037

1.3044±0.2950

0.0181±0.0012

2.6074±0.3863

haberman

0.2881±0.2186

0.0762±0.0110

0.0041±0.0035

0.1088±0.0381

0.0035±0.0005

0.2166±0.0130

heart

0.4100±0.2112

0.0839±0.0048

0.0047±0.0005

0.0781±0.0053

0.0043±0.0005

0.0682±0.0032

ionosphere

0.4992±0.2488

0.1208±0.0049

0.0063±0.0004

0.1469±0.0075

0.0081±0.0004

0.3057±0.0075

liver

0.2979±0.1338

0.0764±0.0057

0.0054±0.0011

0.1031±0.0013

0.0044±0.0009

0.1621±0.0080

pima

1.0151±0.3822

0.2824±0.0079

0.0070±0.0005

0.3719±0.0104

0.0096±0.0007

0.5191±0.0202

sonar

0.6587±0.1144

0.0679±0.0046

0.0062±0.0002

0.0500±0.0020

0.0100±0.0004

0.0654±0.0045

WBC

0.1167±0.0442

0.1290±0.0029

0.0031±0.0017

0.5125±0.0036

0.0089±0.0009

1.4975±0.3204

均值

0.7611±0.2163

0.1689±0.0066

0.0043±0.0012

0.2882±0.039

0.0075±0.0006

0.5695±0.0752

根據(jù)表3所示，通過比較本文LEIDSM算法與其他對比算法在各UCI數(shù)據(jù)集上的實驗結(jié)果可知：

(1)LEIDSM和KEIDSM算法在大部分數(shù)據(jù)集上取得了比LSVM和KSVM更高的正確率。說明本文算法的通過類內(nèi)距離和最小化準則構(gòu)造的大間隔分類模型在一定程度上優(yōu)于SVM結(jié)構(gòu)風險化最小和引入懲罰因子構(gòu)造的標準SVM大間隔分類模型。

(2)LEIDSM和KEIDSM算法在大部分數(shù)據(jù)集上取得了比LFISHER和KFISHER更高的正確率。分析數(shù)據(jù)知，對于正負樣本個數(shù)差別不大的數(shù)據(jù)集，如cleve, liver, sonar等上的表現(xiàn)，fisher用于分類的算法與本文算法正確率差距相對較小，而在正負樣本個數(shù)差別很大的數(shù)據(jù)集，如breast等上的表現(xiàn)，fisher算法與本文算法正確率差距相對較大。這是由于本文算法在提出時便考慮到樣本不平衡時算法的適應(yīng)性問題，加入了參數(shù)，一定程度上解決了數(shù)據(jù)樣本不平衡帶來的不適性。而fisher算法認為兩類均衡，在不平衡數(shù)據(jù)集上表現(xiàn)相對較差。

根據(jù)表4所示，線性方面，LFISHER平均用時最短，LSVM用時最長，LEIDSM介于他們之間。非線性方面，KSVM用時最短。由于本文采用遞歸最小二乘法對算法進行求解，在線性時時間復(fù)雜度為，非線性時時間復(fù)雜度為。而fisher算法線性和非線性時間復(fù)雜度分別為和。由于SVM用經(jīng)典的改進算法SMO作對比，SMO在線性和非線性平均時間復(fù)雜度為。分析實驗中UCI數(shù)據(jù)集知，幾乎所有數(shù)據(jù)集的特征個數(shù)遠小于訓(xùn)練樣本數(shù)，因此在線性時有，所以fisher算法平均用時最短。而非線性時，在訓(xùn)練樣本個數(shù)相同的情況下，有，所以KSVM用時最短。

5.2 Yale大學人臉數(shù)據(jù)庫

Yale大學人臉數(shù)據(jù)庫由Yale大學計算視覺與扼制中心創(chuàng)立，包括15位志愿者的165張圖片，每人11張照片，主要包括光照條件和表情等的變化，每幅圖片重新采樣為10×10的大小。實驗參數(shù)的設(shè)置與5.1節(jié)相同，實驗中采取兩兩配對的方法，共有105種配對方式，在每個訓(xùn)練樣本級別都取這105種準確率結(jié)果的平均值。每個圖像分別用2, 3, 4, 5, 6, 7, 8, 9, 10個進行訓(xùn)練，剩下的樣本作為測試樣本。表5記錄了5次獨立重復(fù)實驗的正確率均值，表6記錄了平均每次運行所用的時間均值。

依據(jù)表5所示，樣本變化時，隨著訓(xùn)練樣本的增多，各種算法下分類的正確率幾乎都有提升。

(1)比較各算法線性情況在樣本變時的表現(xiàn)：LEIDSM大部分情況下比LSVM和LFISHER正確率高。這是由于人臉本身是非線性的，SVM引入懲罰因子來解決非線性無解的情況，允許部分樣本錯分，錯分后的樣本在兩類交界處雜亂分布。而本文算法，使得投影變換后的樣本向各自均值聚集，并且本文算法訓(xùn)練和判別都用距離最小準則，訓(xùn)練和判別更加匹配，所以更有利于分類。

(2)比較各算法非線性情況在樣本變化時的表現(xiàn)：在樣本個數(shù)較少時，KSVM比KEIDSM和KFISHER表現(xiàn)要好，而當樣本個數(shù)增大到一定程度時，KEIDSM表現(xiàn)更好。這是因為SVM只需關(guān)鍵的支持向量，所以對小樣本有很強的學習能力。而樣本增加時，本文算法的類內(nèi)距離和利用了更多的樣本信息，所以取得了更好的結(jié)果。另外，由于實驗105個配對分類，每次實驗對不同的人臉圖像分類選用的是同一個參數(shù)，若是算法對參數(shù)較為敏感，實驗結(jié)果會偏差。

表5 Yale人臉數(shù)據(jù)庫實驗準確率測試結(jié)果(%)

Yale

LSVM

KSVM

LFISHER

KFISHER

LEIDSM

KEIDSM

2

81.48±17.41

88.35±13.34

88.41±24.52

84.11±14.21

91.80±8.89

86.98±8.95

3

85.60±14.17

86.42±15.70

93.21±9.33

81.79±15.19

92.62±9.45

87.68±9.96

4

88.44±10.02

89.09±10.3

91.16±10.46

82.04±15.09

92.04±10.21

88.78±8.63

5

91.43±7.88

91.75±7.96

94.05±7.55

80.57±16.74

94.29±8.36

86.67±10.80

6

89.43±12.62

92.00±9.24

93.81±8.01

85.43±17.37

92.48±10.72

90.67±8.69

7

91.19±10.67

91.43±1.30

94.16±5.23

86.50±18.70

91.79±11.73

91.67±9.44

8

88.73±13.30

89.05±13.24

95.24±8.24

89.31±18.12

95.87±7.59

93.02±9.18

9

93.57±11.51

94.76±6.67

94.76±10.79

90.71±17.63

96.67±8.54

96.90±8.66

10

93.81±16.55

94.47±9.76

92.38±11.03

86.67±16.51

96.67±12.53

97.14±10.06

表6 Yale人臉數(shù)據(jù)庫實驗時間測試結(jié)果(s)

Yale

LSVM

KSVM

LFISHER

KFISHER

LEIDSM

KEIDSM

2

0.0059±0.0008

0.0049±0.0003

0.0060±0.0004

0.0025±0.0003

0.1378±0.2362

0.0303±0.0554

3

0.0069±0.0009

0.0053±0.0009

0.0071±0.0003

0.0058±0.0007

0.0085±0.0026

0.0069±0.0005

4

0.0070±0.0014

0.0055±0.0009

0.0071±0.0017

0.0060±0.0007

0.0171±0.0083

0.0076±0.0003

5

0.0073±0.0019

0.0066±0.0016

0.0079±0.0006

0.0042±0.0002

0.0077±0.0003

0.0084±0.0005

6

±0.0015

0.0071±0.0009

0.0077±0.0006

0.0075±0.0013

0.0073±0.0005

0.0092±0.0010

7

0.0093±0.0017

0.0088±0.0016

0.0109±0.0012

0.0057±0.0005

0.0110±0.0004

0.0095±0.0006

8

0.0105±0.0025

0.0090±0.0014

0.0116±0.0009

0.0126±0.0111

0.0145±0.0011

0.0103±0.0007

9

0.0125±0.0039

0.0098±0.0009

0.0058±0.0018

0.0135±0.0056

0.0078±0.0008

0.0113±0.0009

10

0.0104±0.0030

0.0101±0.0011

0.0094±0.0002

0.0138±0.0019

0.0082±0.0009

0.0116±0.0004

依據(jù)表6所示，樣本增加時各算法用時都變長。大部分情況下LSVM和KSVM用時更短，這是由于圖片本身維度為100維，所以有，此時LEIDSM, LFISHER失去了線性方面時間復(fù)雜度的優(yōu)勢。

6 結(jié)束語

本文依據(jù)大間隔思想，提出了最小化類內(nèi)距離和分類算法。并且在歐式距離標準下對本文算法進行推理實驗，通過與SVM和fisher判別分類算法的比較，證明了該分類算法的有效性。另外，本文只在歐氏距離下驗證了算法的有效性，歐氏距離要求數(shù)據(jù)樣本在模式空間中呈球狀分布，接下來的工作可以針對不同的數(shù)據(jù)選擇不同的距離公式來構(gòu)建距離矩陣拓展本文算法。該分類算法時間復(fù)雜度方面還有待改進，且該分類算法是一種二分類算法，對于多類問題，需要設(shè)計多分類器。

[1] QUINLAN J R. Induction of decision trees[J].,1986, 1(1): 81-106.

[2] QUINLAN J R. Improved use of continuous attributes in C4.5[J]., 1996, 4(1): 77-90.

[3] PENG F, SCHUURMANS D, and WANG S. Augmenting naive Bayes classifiers with statistical language models[J]., 2004, 7(3/4): 317-345.

[4] CHENG J and GREINER R. Comparing Bayesian network classifiers[C]. Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, San Francisco, USA, 1999: 101-108.

[5] COVER T and HART P. Nearest neighbor pattern classification [J].,1967, 13(1): 21-27.

[6] BIJALWAN V, KUMAR V, KUMARI P,. KNN based machine learning approach for text and document mining[J].2014, 7(1): 61-70.

[7] 黃劍華, 丁建睿, 劉家鋒, 等. 基于局部加權(quán)的Citation-kNN算法[J]. 電子與信息學報, 2013, 35(3): 627-632.

HUANG Jianhua, DING Jianrui, LIU Jiafeng,. Citation- kNN algorithm based on locally-weighting[J].&, 2013, 35(3): 627-632.

[8] WELLING M. Fisher linear discriminant analysis[J]., 2008, 16(94): 237-280.

[9] FUIN N, PEDEMONTE S, ARRIDGE S,. Efficient determination of the uncertainty for the optimization of SPECT system design: a subsampled fisher information matrix[J]., 2014, 33(3): 618-635.

[10] DUFRENOIS F. A one-class kernel fisher criterion for outlier detection[J].&, 2014, 26(5): 982-994.

[11] VAN Ooyen A and NIENHUIS B. Improving the convergence of the back-propagation algorithm[J]., 1992, 5(3): 465-471.

[12] 潘舟浩, 李道京, 劉波, 等. 基于BP算法和時變基線的機載InSAR數(shù)據(jù)處理方法研究[J]. 電子與信息學報, 2014, 36(7): 1585-1591.

PAN Zhouhao, LI Daojing, LIU Bo,. Processing of the airborne InSAR data based on the BP algorithm and the time-varying baseline[J]&, 2014, 36(7): 1585-1591.

[13] SUYKENS J A K and VANDEWALLE J. Least squares support vector machine classifiers[J]., 1999, 9(3): 293-300.

[14] 胡文軍, 王士同, 王娟, 等. 非線性分類的分割超平面快速集成方法[J]. 電子與信息學報, 2012, 34(3): 535-542.

HU Wenjun, WANG Shitong, WANG Juan,. Fast ensemble of separating hyperplanes for nonlinear classification[J].&, 2012, 34(3): 535-542.

[15] GAO X, LU T, LIU P,. A soil moisture classification model based on SVM used in agricultural WSN[C]. 2014 IEEE 7th Joint International, Information Technology and Artificial Intelligence Conference (ITAIC), Chongqing, 2014: 432-436.

[16] RIES C X, RICHTER F, ROMBERG S,. Automatic object annotation from weakly labeled data with latent structured SVM[C]. 2014 12th IEEE International Workshop on Content-based Multimedia Indexing (CBMI), Klagenfurt, Austria, 2014: 1-4.

[17] PLATT J. Fast training of support vector machines using sequential minimal optimization[J].:, 1999(3): 185-208.

[18] JOACHIMS T. Making large scale SVM learning practical[R]. Universit?t Dortmund, 1999.

[19] CHANG C C and LIN C J. LIBSVM: A library for support vector machines[J].&, 2011, 2(3): 389-396.

[20] MANGASARIAN O L and MUSICANT D R. Lagrangian support vector machines[J]., 2001, 1(3): 161-177.

[21] SEOK K. Semi-supervised regression based on support vector machine[J].&, 2014, 25(2): 447-454.

[22] LENG Y, XU X, and QI G. Combining active learning and semi-supervised learning to construct SVM classifier[J].-, 2013, 44(1): 121-131.

[23] CHEN W J, SHAO Y H, XU D K,. Manifold proximal support vector machine for semi-supervised classification[J]., 2014, 40(4): 623-638.

[24] 李紅蓮, 王春花, 袁保宗. 一種改進的支持向量機NN- SVM[J]. 計算機學報, 2003, 26(8): 1015-1020.

LI Honglian, WANG Chunhua, and YUAN Baozong. An improved SVM: NN-SVM[J]., 2003, 26(8): 1015-1020.

[25] 陳寶林. 最優(yōu)化理論與算法[M]. 北京: 清華大學出版社, 2005: 281-322.

CHEN Baolin. Optimization Theory and Algorithm[M]. Beijing, Tsinghua University Press, 2005: 281-322.

[26] YOSHIYAMA K and SAKURAI A. Laplacian minimax probability machine[J]., 2014, 37: 192-200.

[27] MIGLIORATI G. Adaptive polynomial approximation by means of random discrete least squares[J].&, 2013, 103: 547-554.

[28] HUANG K, YANG H, KING I,. The minimum error minimax probability machine[J]., 2004(5): 1253-1286.

[29] PLAN Y and VERSHYNIN R. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach[J].,2013, 59(1): 482-494.

[30] ALIZADEN F. Interior point methods in semidefinite programming with applications to combinatorial optimization[J]., 1995, 5(1): 13-51.

[31] BOYD S and VANDENBERGHE L. Convex Optimi- zation[M]. Cambridge University Press, 2009: 127- 214.

[32] 邊肇祺, 張學工. 模式識別[M]. 北京: 清華大學出版社, 2001: 83-90.

BIAN Zhaoqi and ZHANG Xuegong. Pattern Recognition[M]. Beijing, Tsinghua University Press, 2001: 83-90.

王曉初： 男，1987年生，碩博連讀生，研究方向為模式識別、數(shù)字圖像處理.

王士同： 男，1964年生，教授，研究方向為人工智能、模式識別、生物信息.

包 芳： 女，1970年生，教授，研究方向為人工智能、模式識別.

蔣亦樟： 男，1988年生，博士，研究方向為模式識別、智能計算.

Foundation Items: The National Natural Science Foundation of China (61170122, 61272210)

Intraclass-Distance-Sum-Minimization Based Classification Algorithm

WANG Xiaochu①②WANG Shitong①BAO Fang②JIANG Yizhang①

①(School of Digital Media, Jiangnan University, Wuxi 214122, China)②(Information Fusion Software Engineering Research and Development Center of Jiangsu Province, Jiangyin 214405, China)

Classification algorithm of Support Vector Machine (SVM) is introduced the penalty factor to adjust the overfit and nonlinear problem. The method is beneficial for seeking the optimal solution by allowing a part of samples error classified. But it also causes a problem that error classified samples distribute disorderedly and increase the burden of training. In order to solve the above problems, according to large margin classification thought, based on principles that the intraclass samples must be closer and the interclass samples must be looser, this research proposes a new classification algorithm called Intraclass-Distance-Sum-Minimization (IDSM) based classification algorithm. This algorithm constructs a training model by using principle of minimizing the sum of the intraclass distance and finds the optimal projection rule by analytical method. And then the optimal projection rule is used to samples’ projection transformation to achieve the effect that intraclass intervals are small and the interclass intervals are large. Accordingly, this research offers a kernel version of the algorithm to solve high-dimensional classification problems. Experiment results on a large number of UCI datasets and the Yale face database indicate the superiority of the proposed algorithm.

Support Vector Machine (SVM); Penalty factor; Large margin classification thought; Sum of intraclass distance; Projection rule

TP391.41

A

1009-5896(2016)03-0532-09

10.11999/JEIT150633

2015-05-04；改回日期：2016-01-05；網(wǎng)絡(luò)出版：2015-11-19

王曉初 icnice@yeah.net

國家自然科學基金(61170122, 61272210)