李艷芳　高大啟

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

?

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

李艷芳高大啟

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

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

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

0引言

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

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

1FLD基本原理和常用閾值

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

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

(1)

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

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

(2)

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

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

(3)

(4)

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

(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)

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

(8)

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

通過最大化準則函數(shù)可以確定最佳投影方向，但是當樣本按投影方向投影到一維空間后，還需在一維空間中確定一個點即閾值θ，來將兩類樣本分開。不同閾值對分類結(jié)果影響很大，常用的閾值有θ1和θ2[6]。

(9)

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

(10)

(11)

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

(12)

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

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

(13)

(14)

即投影均值的中點閾值θ2。

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

2.1樣本不平衡因素

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

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

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

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

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

2.2經(jīng)驗閾值

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

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

(15)

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

(16)

(17)

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

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

(18)

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

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

(19)

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

(20)

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

(21)

解此方程可以得到另外一個閾值：

(22)

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

(23)

(24)

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

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

(25)

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

(26)

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

(27)

(28)

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

(29)

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

(30)

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

Avc=(tprate+tnrate)/2

(31)

或幾何識別率：

(32)

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

3實驗結(jié)果分析

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

3.1閾值比較實驗

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

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

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

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

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

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

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

3.2優(yōu)化閾值選擇實驗

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

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

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

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

續(xù)表2

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

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

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

4結(jié)語

線性分類器雖然屬于最簡單的一種分類器，但在實際應(yīng)用中往往能取得比較好的結(jié)果。在FLD中，閾值最終決定了決策平面的位置，在不平衡問題中，常用閾值往往會出現(xiàn)偏差，致使分類性能變差。本文研究了不平衡問題對FLDs閾值的影響，提出主要影響FLD性能的不平衡因素是樣本分布區(qū)域的不平衡，而不是樣本數(shù)的不平衡，并且提出一些經(jīng)驗閾值以及根據(jù)分類精度選擇優(yōu)化閾值。實驗證明，考慮到樣本分布的閾值對解決不平衡問題更有利，以及在具體問題中利用所提出的優(yōu)化閾值選擇方法選取合適的閾值確實能在提升分類效果，在實際應(yīng)用中有指導作用。本文主要關(guān)注的是兩類問題下的閾值選取問題，而在多類情況下閾值的選取問題可能會更加復雜，我們今后將把問題關(guā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。國家自然科學基金項目(21176077)。李艷芳，碩士生，主研領(lǐng)域：模式識別。高大啟，教授。

中圖分類號TP391

文獻標識碼A

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