Fisher線性判別式閾值優化方法研究

李艷芳　高大啟

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

?

Fisher線性判別式閾值優化方法研究

李艷芳高大啟

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

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

關鍵詞分類Fisher線性判別式閾值不平衡數據集

0引言

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

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

1FLD基本原理和常用閾值

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

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

(1)

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

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

(2)

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

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

(3)

(4)

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

(5)

其中SB代表類間散度矩陣，SW代表總類內散度矩陣，且：

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

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

(11)

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

(12)

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

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

(13)

(14)

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

2經驗閾值及其優化

2.1樣本不平衡因素

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

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

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

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

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

2.2經驗閾值

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

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

(15)

受θ1啟發，將兩類樣本數N1、N2的位置調換，可得：

(16)

(17)

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

將θ3與θ4結合起來，θ5考慮到了樣本數和樣本分布區域兩個因素：

(18)

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

定義類內總體絕對偏差為：

(19)

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

(20)

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

(21)

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

(22)

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

(23)

(24)

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

定義類內總體平均絕對偏差為：

(25)

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

(26)

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

(27)

(28)

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

(29)

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

(30)

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

Avc=(tprate+tnrate)/2

(31)

或幾何識別率：

(32)

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

3實驗結果分析

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

3.1閾值比較實驗

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

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

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

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

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

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

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

3.2優化閾值選擇實驗

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

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

表2列出了所用到的數據集的統計信息。

表2　部分KEEL數據集的統計信息

續表2

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

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

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

4結語

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

參考文獻

[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)。李艷芳，碩士生，主研領域：模式識別。高大啟，教授。

中圖分類號TP391

文獻標識碼A

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