李艷芳　高大啟

(華東理工大學(xué)信息科學(xué)與工程學(xué)院　上海 200237)

?

Fisher線性判別式閾值優(yōu)化方法研究

李艷芳高大啟

(華東理工大學(xué)信息科學(xué)與工程學(xué)院上海 200237)

摘要Fisher線性判別式FLDs(Fisher linear discriminates)的常用閾值對(duì)不平衡數(shù)據(jù)集分類效果較差。以不平衡數(shù)據(jù)集為應(yīng)用背景，主要研究各種閾值對(duì)FLDs分類性能的影響。認(rèn)為影響 FLDs性能的主要是類間分布區(qū)域不平衡而不是樣本數(shù)不平衡，因此提出多個(gè)經(jīng)驗(yàn)閾值，并依據(jù)分類精度從中選擇優(yōu)化閾值。大量實(shí)驗(yàn)結(jié)果表明，所提出的閾值優(yōu)化選擇方法能有效提高FLDs對(duì)不平衡數(shù)據(jù)集的分類性能。

關(guān)鍵詞分類Fisher線性判別式閾值不平衡數(shù)據(jù)集

0引言

線性分類器是統(tǒng)計(jì)模式識(shí)別中最簡(jiǎn)單的一類[1]。它假設(shè)兩類樣本可以被一個(gè)超平面粗略的分開(kāi)，很多情況下可以得到不太差的結(jié)果，由于不容易產(chǎn)生過(guò)擬合，有時(shí)甚至能獲得比復(fù)雜分類器更好的效果。并且由于對(duì)計(jì)算資源要求低，容易實(shí)現(xiàn)，在實(shí)際中被廣泛應(yīng)用[2]。常見(jiàn)的線性分類器有Fisher線性判別式(FLD)[3]、單層感知器[4]以及線性支持向量機(jī)[5]等。

FLD通過(guò)最大化準(zhǔn)則函數(shù)—類間散度和類內(nèi)散度之比來(lái)尋找最能將樣本分開(kāi)的投影方向，通常能取得比較好的效果[6]。但是FLD只能確定決策平面的法向量，卻不能確定最終決定分類平面位置的閾值[7]。常用閾值在不平衡數(shù)據(jù)集中往往過(guò)分偏向某類樣本，導(dǎo)致分類效果不佳[8]。本文通過(guò)研究在不平衡數(shù)據(jù)集中各種閾值對(duì)FLD分類性能的影響，提出影響分類器性能的主要是樣本分布區(qū)域的不平衡，而不是樣本數(shù)的不平衡。考慮到樣本數(shù)和樣本分布區(qū)域等因素，我們提出多個(gè)經(jīng)驗(yàn)閾值以及根據(jù)分類精度或具體的評(píng)價(jià)指標(biāo)，選擇優(yōu)化閾值。不同閾值可能適用不同的樣本分布，實(shí)驗(yàn)證明利用本文提出的閾值優(yōu)化選擇方法，在實(shí)際中根據(jù)具體情況選擇合適的閾值，確實(shí)可以提高分類性能。

1FLD基本原理和常用閾值

在兩類{ω1,ω2}問(wèn)題中，用x=(x1,x2,…,xn)T表示n維輸入空間中一個(gè)樣本，則線性分類器的判別函數(shù)可以表示為：

g(x)=wTx+w0=wTx-θ

(1)

其中,w=(w1,w2,…,wn)T為權(quán)向量，θ=-w0為閾值。從而：

π:g(x)=wTx-θ=0

(2)

就是決策平面，其中w就是決策平面的法向量。于是g(x)>0時(shí)可以決策x∈ω1，g(x)<0時(shí)x∈ω2。

Fisher線性判別式通過(guò)最大化準(zhǔn)則函數(shù)[6]：

(3)

(4)

這樣式(3)便可寫(xiě)成關(guān)于w的表達(dá)式：

(5)

其中SB代表類間散度矩陣，SW代表總類內(nèi)散度矩陣，且：

SB=(u1-u2)(u1-u2)T

(6)

SW=S1+S2,Si=∑x∈ωi(x-ui)(x-ui)Ti=1,2

(7)

化簡(jiǎn)式(5)，最終可得權(quán)向量為：

(8)

從式(8)中可以看出權(quán)向量只受到類內(nèi)散布矩陣和兩個(gè)均值向量的影響。

通過(guò)最大化準(zhǔn)則函數(shù)可以確定最佳投影方向，但是當(dāng)樣本按投影方向投影到一維空間后，還需在一維空間中確定一個(gè)點(diǎn)即閾值θ，來(lái)將兩類樣本分開(kāi)。不同閾值對(duì)分類結(jié)果影響很大，常用的閾值有θ1和θ2[6]。

(9)

閾值θ1即樣本總均值在w方向上的投影。設(shè)第p個(gè)訓(xùn)練樣本xp的期望輸出為dp，兩個(gè)類別{ω1，ω2}中所有訓(xùn)練樣本的誤差平方和為：

(10)

(11)

令ε是一個(gè)充分小的正數(shù)，當(dāng)xp屬于第ω1類時(shí)，dp→ε，當(dāng)xp屬于第ω2類時(shí)，dp→-ε，則：

(12)

實(shí)際上dp代表了樣本到?jīng)Q策平面的代數(shù)距離的期望值，ε→0就意味著所有樣本全部落在決策平面上，這與實(shí)際情況不符，所以采用閾值θ1的分類器效果可能不會(huì)很好。

假設(shè)兩類樣本的類條件概率密度都服從正態(tài)分布，由最小貝葉斯誤差率原則可知在決策點(diǎn)即閾值θ處滿足后驗(yàn)概率相等，即：

(13)

(14)

即投影均值的中點(diǎn)閾值θ2。

2經(jīng)驗(yàn)閾值及其優(yōu)化

2.1樣本不平衡因素

在研究不平衡數(shù)據(jù)集時(shí)，通常用兩類樣本數(shù)之比，即負(fù)類(樣本數(shù)多的一類)樣本數(shù)/正類(樣本數(shù)少的一類)樣本數(shù)，來(lái)表示樣本集的樣本數(shù)不平衡率。然而影響不平衡問(wèn)題的因素除了樣本數(shù)外還有樣本分布區(qū)域的不平衡，而且對(duì)于線性分類器，樣本分布區(qū)域不平衡的影響更大。

假設(shè)兩類樣本集中正類樣本數(shù)為3，負(fù)類樣本數(shù)為30，不平衡率為30/3=10。如圖1所示，負(fù)類樣本數(shù)和樣本分布區(qū)域都大于正類，采用閾值θ2時(shí)，決策平面偏向多數(shù)類方向，原本線性可分的樣本集卻沒(méi)有被全部正確分類。圖2所示兩類樣本數(shù)不變，仍是負(fù)類樣本數(shù)大于正類樣本數(shù)，但是負(fù)類樣本分布區(qū)域小于正類，此時(shí)決策平面的位置偏向了少數(shù)類。從樣本數(shù)來(lái)看，樣本數(shù)不變，決策平面偏向的方向卻完全相反；從樣本分布區(qū)域來(lái)看，分布區(qū)域大小變化，決策平面偏向的方向也相反。因此我們認(rèn)為決策平面位置的變化主要受樣本分布區(qū)域而不是樣本數(shù)的影響。

圖1　樣本不平衡時(shí)決策平面的位置(A)圖2　樣本不平衡時(shí)決策平面的位置(B)

圖3中兩類的樣本數(shù)依然不變，分別為3和30，但是由于其分布區(qū)域大小基本相同，此時(shí)FLD分類器可以很好地將兩類樣本分開(kāi)，兩類樣本到?jīng)Q策平面的最小距離基本相同。圖4中盡管兩類樣本數(shù)平衡，但是樣本分布區(qū)域卻不平衡，此時(shí)決策平面仍然會(huì)偏向樣本分布區(qū)域大的一方，對(duì)其不利。

圖3　樣本分布區(qū)域平衡時(shí)決策平面的位置圖4　樣本分布區(qū)域不平衡時(shí)決策平面的位置

2.2經(jīng)驗(yàn)閾值

在不平衡數(shù)據(jù)集中常用閾值會(huì)使得分類器對(duì)某一類樣本有利，而對(duì)另外一類不利，而這是我們不希望看到的，因此本節(jié)將樣本不平衡因素考慮進(jìn)去，提出幾個(gè)經(jīng)驗(yàn)閾值。

由式(14)可以看出，θ2與樣本數(shù)和分布區(qū)域無(wú)關(guān)，只要兩類的均值向量不變，閾值就不變。

(15)

受θ1啟發(fā)，將兩類樣本數(shù)N1、N2的位置調(diào)換，可得：

(16)

(17)

當(dāng)ω1類的分布區(qū)域大于ω2類時(shí)，閾值θ4會(huì)向ω2類方向移動(dòng)，對(duì)樣本分布區(qū)域大的類有利，與樣本數(shù)沒(méi)有直接關(guān)系。

將θ3與θ4結(jié)合起來(lái)，θ5考慮到了樣本數(shù)和樣本分布區(qū)域兩個(gè)因素：

(18)

實(shí)驗(yàn)證明在樣本充足時(shí)，隨著樣本數(shù)不平衡度的增加，θ3的變化要大于θ5，從而θ5與θ3一樣有利于多數(shù)類。

定義類內(nèi)總體絕對(duì)偏差為：

(19)

同樣考慮到樣本分布區(qū)域，但是用類內(nèi)總體絕對(duì)偏差表達(dá)樣本分布區(qū)域的差異，可以得到閾值：

(20)

從計(jì)算過(guò)程可以看出，它也會(huì)受到樣本數(shù)的影響。

(21)

解此方程可以得到另外一個(gè)閾值：

(22)

閾值θ7考慮到實(shí)際中兩類樣本方差不一定相同的情況，可能會(huì)取得比較好的效果。從式(22)可以看到，其最終結(jié)果只用到了樣本投影均值和方差，所以θ7受樣本數(shù)影響不大。

(23)

(24)

與θ6的計(jì)算過(guò)程相似，會(huì)受到樣本數(shù)的影響。

定義類內(nèi)總體平均絕對(duì)偏差為：

(25)

用其代替θ6中的總體絕對(duì)偏差，可得：

(26)

同樣只考慮兩個(gè)投影均值之間的樣本，可對(duì)應(yīng)得到：

(27)

(28)

將以上各閾值取平均，可得到θ11:

(29)

在統(tǒng)計(jì)學(xué)習(xí)理論中，經(jīng)常用經(jīng)驗(yàn)風(fēng)險(xiǎn)最小函數(shù)來(lái)近似期望風(fēng)險(xiǎn)最小函數(shù)，原因是在過(guò)去風(fēng)險(xiǎn)最小的在將來(lái)也很有可能風(fēng)險(xiǎn)最小[9]。在實(shí)際應(yīng)用中每個(gè)數(shù)據(jù)集的樣本分布都不相同，我們可以在上述11個(gè)閾值中選取能使當(dāng)前數(shù)據(jù)集的分類誤差最小(整體識(shí)別率Acc最大)的閾值作為當(dāng)前閾值，所以第12個(gè)閾值可以表示為：

(30)

對(duì)于不平衡問(wèn)題，總體分類誤差往往不能很好地衡量分類器的性能。對(duì)于樣本數(shù)極度不平衡數(shù)據(jù)集，把所有樣本都?xì)w為樣本數(shù)多的一類，仍然可以得到很好的Acc值，但這時(shí)少數(shù)類的識(shí)別率卻為零。我們常采用兩類的平均識(shí)別率：

Avc=(tprate+tnrate)/2

(31)

或幾何識(shí)別率：

(32)

來(lái)衡量分類器的性能。其中tprate=被正確分類正類樣本數(shù)/正類樣本總數(shù)，tnrate=被正確分類的負(fù)類樣本數(shù)/負(fù)類樣本總數(shù)。當(dāng)我們以Avc或G-mean作為分類器的評(píng)價(jià)指標(biāo)時(shí)，則同樣的方法，這時(shí)可以定義θ12為上述11個(gè)閾值中能使當(dāng)前的Avc或G-mean值達(dá)到最大的閾值。

3實(shí)驗(yàn)結(jié)果分析

本文用到的數(shù)據(jù)集全部來(lái)自KEEL-dataset數(shù)據(jù)庫(kù)[10]。這些數(shù)據(jù)集都是兩類分類問(wèn)題，且具有不同的不平衡率。

3.1閾值比較實(shí)驗(yàn)

本實(shí)驗(yàn)對(duì)使用了前11個(gè)閾值的FLDs進(jìn)行比較，共用到了95個(gè)不平衡數(shù)據(jù)集，不平衡率最小為1.8，最大為129，由于篇幅關(guān)系不再具體列出。

記閾值為θq，q=1,2,…,12的FLD為FLD_θq。分別用分類器FLD_θq，q=1,2,…,11這11個(gè)分類器對(duì)95個(gè)數(shù)據(jù)集進(jìn)行分類，并記錄分類結(jié)果，包括它們的Acc、Avc和G-mean。

對(duì)于每個(gè)數(shù)據(jù)集， 11個(gè)FLDs將得到11個(gè)不同的Acc結(jié)果，根據(jù)Acc值的高低對(duì)11個(gè)FLDs進(jìn)行排序，可以它們的Acc排名。對(duì)每個(gè)FLD，求其在95個(gè)數(shù)據(jù)集上的Acc排名的均值，即可得到FLDs的Acc平均排名。

同樣的方法可以得到FLDs的Avc和G-mean平均排名。

表1中分別列出了FLD_θq，q=1,2,…,11的Acc、Avc、G-mean值的平均排名。

表1　11個(gè)閾值的FLDs對(duì)KEEL數(shù)據(jù)集的Acc、Avc、G-mean平均排名

從表1中可以看出，θ4、θ7、θ9、θ10這四個(gè)閾值可以得到Avc，G-mean比較高的FLDs，這說(shuō)明閾值θ4、θ7、θ9、θ10對(duì)解決不平衡問(wèn)題比較有效。θ3、θ5、θ6、θ8這四個(gè)閾值可以得到Acc比較高的FLDs，但是由于Acc指標(biāo)本身對(duì)不平衡數(shù)據(jù)集的評(píng)價(jià)缺陷，經(jīng)常不作為評(píng)價(jià)不平衡問(wèn)題的指標(biāo)。結(jié)合2.2節(jié)的分析，前四個(gè)閾值都考慮到了樣本分布區(qū)域，且受樣本數(shù)的影響不大，后四個(gè)閾值都受到樣本數(shù)的影響，從而驗(yàn)證了FLD更容易受到樣本分布區(qū)域不平衡的影響，而不是樣本數(shù)的影響。FLD_θ2和FLD_θ11基本上處于排名的中間位置，F(xiàn)LD_θ1基本處于最后一位或倒數(shù)第二位。

3.2優(yōu)化閾值選擇實(shí)驗(yàn)

在實(shí)際應(yīng)用中，需要根據(jù)樣本具體分布情況不同，選取適合當(dāng)前數(shù)據(jù)集的閾值。本實(shí)驗(yàn)驗(yàn)證了利用θ12選擇優(yōu)化閾值可以提高分類性能。

本實(shí)驗(yàn)用Avc作為分類器的評(píng)價(jià)指標(biāo)，θ12定義為前11個(gè)閾值中使當(dāng)前Avc值達(dá)到最大的閾值。分別用分類器FLD_θq，q=1,2,…,12這12個(gè)分類器對(duì)數(shù)據(jù)集進(jìn)行分類，并記錄結(jié)果。

表2列出了所用到的數(shù)據(jù)集的統(tǒng)計(jì)信息。

表2　部分KEEL數(shù)據(jù)集的統(tǒng)計(jì)信息

續(xù)表2

表3列出了FLD_θq，q=1,2,…,12這12個(gè)分類器對(duì)這些數(shù)據(jù)集分類的Avc，其中最大值已經(jīng)用加粗標(biāo)識(shí)出來(lái)。

表3　FLD_θq,q=1,2,…,12對(duì)部分KEEL數(shù)據(jù)集分類的Avc值(%)

可以看出，得到最高Avc值的閾值盡管不完全相同，但都是θ4、θ7、θ9、θ10中的某個(gè)。除少數(shù)數(shù)據(jù)集如ecoli_0_1_4_6_vs_5和yeast6除外，再次驗(yàn)證了之前的結(jié)論。通過(guò)θ12選擇合適的閾值，確實(shí)可以提高分類器的分類性能，例如對(duì)數(shù)據(jù)集page_blocks0，平均精度Avc從θ1的82.88%提高到θ10的86.70%。

4結(jié)語(yǔ)

線性分類器雖然屬于最簡(jiǎn)單的一種分類器，但在實(shí)際應(yīng)用中往往能取得比較好的結(jié)果。在FLD中，閾值最終決定了決策平面的位置，在不平衡問(wèn)題中，常用閾值往往會(huì)出現(xiàn)偏差，致使分類性能變差。本文研究了不平衡問(wèn)題對(duì)FLDs閾值的影響，提出主要影響FLD性能的不平衡因素是樣本分布區(qū)域的不平衡，而不是樣本數(shù)的不平衡，并且提出一些經(jīng)驗(yàn)閾值以及根據(jù)分類精度選擇優(yōu)化閾值。實(shí)驗(yàn)證明，考慮到樣本分布的閾值對(duì)解決不平衡問(wèn)題更有利，以及在具體問(wèn)題中利用所提出的優(yōu)化閾值選擇方法選取合適的閾值確實(shí)能在提升分類效果，在實(shí)際應(yīng)用中有指導(dǎo)作用。本文主要關(guān)注的是兩類問(wèn)題下的閾值選取問(wèn)題，而在多類情況下閾值的選取問(wèn)題可能會(huì)更加復(fù)雜，我們今后將把問(wèn)題關(guān)注于多類問(wèn)題的情況。

參考文獻(xiàn)

[1]JainAK,DuinRPW,MaoJC.StatisticalPatternrecognition:areview[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(1):4-37.

[2]BekiosCalfaJ,BuenaposadaJM,BaumelaL.Revisitinglineardiscriminatetechniquesingenderrecognition[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2011,33(4):858-864.

[3]RozzaA,LombardiG,CasiraghiE,etal.NovelFisherdiscriminatesclassifiers[J].Patternrecognition,2012,45(10):3725-3737.

[4]LecunY,BottouL,BengioY,etal.Gradient-basedlearningappliedtodocumentrecognition[J].ProceedingsoftheIEEE,1998,86(11):2278-2324.

[5]MüllerKR,MikaS,R?tschG,etal.Anintroductiontokernel-basedlearningalgorithms[J].IEEETransactionsonNeuralNetworks,2001,12(2):181-201.

[6]DudaRO,HartPE,StorkDG.PatternClassification[M].2nded.NewYork:JohnWiley&Sons,Inc,2000.

[7]GaoDaqi,DingJun,ZhuChangming.IntegratedFisherlineardiscriminates:Anempiricalstudy[J].PatternRecognition,2014,47(2):789-805.

[8]HeHaibo,EdwardoAG.Learningfromimbalanceddata[J].IEEETransactionsonKnowledgeandDataEngineering,2009,21(9):1558-1571.

[9]PernkopfF,WohlmayrM.TschiatschekS.MaximummarginBayesiannetworkclassifiers[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2012,34(3):521-532.

[10]AlcaláFdezJ,FernandezA,LuengoJ,etal.KEELData-MiningSoftwareTool:DataSetRepository,IntegrationofAlgorithmsandExperimentalAnalysisFramework[J].JournalofMultiple-ValuedLogicandSoftComputing,2011,17(2):255-287.

ON OPTIMISING THRESHOLDS OF FISHER LINEAR DISCRIMINANT

Li YanfangGao Daqi

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

AbstractThe commonly used thresholds of Fisher linear discriminant (FLD) always have poor classification result on imbalanced datasets. On application background of the imbalanced datasets, in this paper we mainly study the influence of various thresholds on FLD’s classification performance. We argue that for FLDs, it’s the imbalance of inter-class distribution regions rather than sample sizes that mainly impacts the performance of FLDs, and thus we develop several empirical thresholds and select the optimised thresholds based on classification accuracy. Extensive experimental results show that the classification performance of FLDs on imbalanced datasets is improved effectively with the use of the proposed optimised threshold selection method.

KeywordsClassificationFisher linear discriminantThresholdsImbalanced dataset

收稿日期：2014-12-14。國(guó)家自然科學(xué)基金項(xiàng)目(21176077)。李艷芳，碩士生，主研領(lǐng)域：模式識(shí)別。高大啟，教授。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.035