王曉初 王士同 包 芳 蔣亦樟

?

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

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

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

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

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

1 引言

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

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

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

2 大間隔分類算法

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

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

圖1 SVM分類原理圖

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

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

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

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

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

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

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

3.1 IDSM算法框架的提出

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

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

正樣本和負(fù)樣本的均值表達(dá)式為

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

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

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

3.2 EIDSM算法

歐氏距離作為IDSM算法中距離和的衡量標(biāo)準(zhǔn)，投影變換后兩樣本間的距離為

那么，歐氏距離和表達(dá)式：

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

3.3 非線性EIDSM算法

設(shè)

此時(shí)正樣本歐氏距離和的非線性表達(dá)式可化簡(jiǎn)為矩陣形式：

同理，負(fù)樣本歐氏距離和的非線性表達(dá)式可化簡(jiǎn)為矩陣形式：

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

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

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

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

數(shù)據(jù)集

breast

cleve

German

haberman

heart

ionosphere

liver

pima

sonar

WBC

正樣本個(gè)數(shù)

81

160

300

225

150

126

145

268

111

444

負(fù)樣本個(gè)數(shù)

196

136

700

81

120

225

200

500

97

239

屬性個(gè)數(shù)

9

13

24

3

13

34

6

8

60

9

表2 實(shí)驗(yàn)說(shuō)明

實(shí)驗(yàn)平臺(tái)

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

RAM: 4.00 GB

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

工具：32位MatlabR2012a

實(shí)驗(yàn)中縮寫算法的全稱

LSVM：線性支持向量機(jī)

KSVM：非線性支持向量機(jī)

LFISHER: fisher線性判別分類算法

KFISHER：核fisher判別分類算法

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

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

表3 UCI數(shù)據(jù)集的正確率測(cè)試結(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ù)集的時(shí)間測(cè)試結(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所示，通過(guò)比較本文LEIDSM算法與其他對(duì)比算法在各UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果可知：

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

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

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

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

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

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

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

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

表5 Yale人臉數(shù)據(jù)庫(kù)實(shí)驗(yàn)準(zhǔn)確率測(cè)試結(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ù)庫(kù)實(shí)驗(yàn)時(shí)間測(cè)試結(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所示，樣本增加時(shí)各算法用時(shí)都變長(zhǎng)。大部分情況下LSVM和KSVM用時(shí)更短，這是由于圖片本身維度為100維，所以有，此時(shí)LEIDSM, LFISHER失去了線性方面時(shí)間復(fù)雜度的優(yōu)勢(shì)。

6 結(jié)束語(yǔ)

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

[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]. 電子與信息學(xué)報(bào), 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算法和時(shí)變基線的機(jī)載InSAR數(shù)據(jù)處理方法研究[J]. 電子與信息學(xué)報(bào), 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]. 電子與信息學(xué)報(bào), 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] 李紅蓮, 王春花, 袁保宗. 一種改進(jìn)的支持向量機(jī)NN- SVM[J]. 計(jì)算機(jī)學(xué)報(bào), 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]. 北京: 清華大學(xué)出版社, 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] 邊肇祺, 張學(xué)工. 模式識(shí)別[M]. 北京: 清華大學(xué)出版社, 2001: 83-90.

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

王曉初： 男，1987年生，碩博連讀生，研究方向?yàn)槟Ｊ阶R(shí)別、數(shù)字圖像處理.

王士同： 男，1964年生，教授，研究方向?yàn)槿斯ぶ悄?、模式識(shí)別、生物信息.

包 芳： 女，1970年生，教授，研究方向?yàn)槿斯ぶ悄?、模式識(shí)別.

蔣亦樟： 男，1988年生，博士，研究方向?yàn)槟Ｊ阶R(shí)別、智能計(jì)算.

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

國(guó)家自然科學(xué)基金(61170122, 61272210)