程汝峰，梁永全，劉 彤

(山東科技大學(xué) 計算機科學(xué)與工程學(xué)院，山東 青島 266590)

一種適用于不同分類器的樣本約簡算法

程汝峰，梁永全，劉 彤

(山東科技大學(xué) 計算機科學(xué)與工程學(xué)院，山東 青島 266590)

現(xiàn)有的樣本約簡算法多數(shù)是針對某種分類器設(shè)計的，在實際應(yīng)用中有一定的局限性。結(jié)合聚類算法的思想，設(shè)計了一種適用于不同分類器的樣本約簡算法，核心是選取密度高且距離相對較遠(yuǎn)的樣本點。與其他樣本約簡算法相比較，該算法可以根據(jù)需求獲得任意大小的樣本子集，并適用于多種分類算法；而對包含噪聲點的樣本集，算法的分類精度和穩(wěn)定性均有一定程度的提高。

樣本約簡；準(zhǔn)則；密度；樣本子集

一般來說，不同樣本的重要程度是不同的。一些冗余和噪音數(shù)據(jù)不僅造成大量的存儲耗費，而且還會影響學(xué)習(xí)精度。因此更傾向于根據(jù)一定的性能標(biāo)準(zhǔn)，選擇代表性樣本形成原樣本空間的一個子集，之后在這個子集上進行學(xué)習(xí)。在保持某些性能的基礎(chǔ)上，最大限度地降低時間、空間的耗費。

樣本約簡算法根據(jù)性能的要求大致可分為增強型、保持型和混合類型三類。增強型算法的代表有ENN(edited nearest neighbor)[1]、RENN(repeated ENN)[2]、AKNN(aggregate k nearest neighbor)[3]等；保持型算法的代表有CNN(condensed nearest neighbor)[4]、RNN(reduced nearest neighbor)[5]、MCS(minimal consistent set)[6]、FCNN(fast nearest neighbor condensation)[7]等；混合型算法的代表性工作有ICF(iterative case filtering algorithm)[8]、DROP3(decremental reduction optimization procedure)[9]等。文獻[10]和文獻[11]對樣本約簡算法進行了很好的綜述。

近幾年，研究者嘗試用不同的方法來實現(xiàn)樣本約簡。針對支持向量機，Chen等[12]提出一種可以加速支持向量機訓(xùn)練的樣本約簡算法；針對貝葉斯分類器，Pabitra等[13]提出一種多尺度的樣本約簡算法；基于保留區(qū)分?jǐn)?shù)據(jù)超平面和最大化間隔的思想，文獻[14]提出了一種間隔最大化的樣本約簡算法；基于超矩形聚類算法的思想，文獻[15]提出了一種能夠有效剔除非邊界數(shù)據(jù)、保留邊界和鄰近邊界數(shù)據(jù)的樣本約簡算法；基于譜圖理論，文獻[16]提出了一種能夠有效劃分?jǐn)?shù)據(jù)集邊界和內(nèi)部實例的譜圖樣本約簡算法；基于K-MEANS聚類算法的思想，文獻[17]提出了一種能夠處理較大數(shù)據(jù)集的高效樣本約簡算法；基于部分剔除的思想，文獻[18]提出了一種僅剔除可疑噪聲數(shù)據(jù)部分屬性的部分樣本約簡算法。

通過分析可以發(fā)現(xiàn)，現(xiàn)有的樣本約簡算法或者是針對某種分類器設(shè)計，或者是傾向于選擇邊界數(shù)據(jù)。由于邊界數(shù)據(jù)通常較稀疏并且很可能存在噪聲，對原始樣本集的代表性較差，很難適用于不同的分類算法。受文獻[19]的啟發(fā)，結(jié)合已有的約簡準(zhǔn)則，本文提出了一種新的樣本點選取標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)不針對于某種特定分類器，核心思想是選取密度高且相互之間距離相對較遠(yuǎn)的樣本點。實驗表明該標(biāo)準(zhǔn)在多種分類器上都有好的表現(xiàn)，有效地提高了樣本約簡效果。

1 理論基礎(chǔ)

1.1 已有的約簡準(zhǔn)則

已有的約簡準(zhǔn)則多數(shù)為不確定性準(zhǔn)則，通常是選擇不確定性信息量大的樣本。不確定性的度量方法有多種，相對應(yīng)的準(zhǔn)則也有多個。

最小置信度準(zhǔn)則[20]是用概率學(xué)習(xí)模型計算或估計樣本的后驗概率。最大熵準(zhǔn)則[21]是用信息熵度量樣例的不確定性。投票熵準(zhǔn)則[22]是綜合若干個概率學(xué)習(xí)模型度量不確定性。一致性約簡準(zhǔn)則的核心概念是最近異類近鄰子集[6]，最小一致子集樣本約簡算法(MCS)就是用這種度量標(biāo)準(zhǔn)來選擇樣例，生成最小一致子集。

1.2 精英點約簡準(zhǔn)則

已有的約簡準(zhǔn)則忽視了樣本的分布信息。本文基于密度和距離的方法提出新的樣本點選取準(zhǔn)則。在這里稱原始樣本集中的數(shù)據(jù)為原數(shù)據(jù)，被選擇出來的樣本子集中的數(shù)據(jù)為精英點。以支持向量機(support vector machine,SVM)[23]為例，如果選擇了具有代表性的數(shù)據(jù)，則對應(yīng)的分類超平面應(yīng)該非常接近“正中間”，并且能夠有效排除噪聲點的影響。從圖1可以看出，通過精英點訓(xùn)練得出的分類器更具有通用性。

圖2[14]表示的是一組按密度排序的樣本分布圖，圖中數(shù)字是按密度降序后各個樣本的編號。從圖2中可以看出，如果僅考慮密度因素，樣本點1～9都比樣本點10的密度大，故選取的前9個精英點為樣本點1～9。顯然這樣的選取過于集中，對整個樣本集的代表性較差，如果存在重復(fù)的數(shù)據(jù)則效果更差。為了使選擇的精英點更具有代表性，則需要更加分散，因此需要考慮距離因素。根據(jù)以上分析，易知精英點應(yīng)同時具有兩個特點：精英點本身的密度要高；精英點與其他密度較大的數(shù)據(jù)點之間的距離要大。

圖1 精英點和相對應(yīng)的分超平面Fig.1 Elite data points and corresponding classified hyperplane

圖2 一組按密度排序的樣本分布圖Fig.2 A set of instance distribution according to the density sort

1.2.1 密度的計算

局部密度ρi包括截斷核和高斯核兩種計算方式：

截斷核為離散型而高斯核為連續(xù)型，因此相對來說后者產(chǎn)生沖突的概率更小。此外對于高斯核，如果與xi的距離小于dc的數(shù)據(jù)點越多，則ρi的值越大。

1.2.2 高密度點距離

(1)

式(1)含義為：當(dāng)xi具有最大局部密度時，δi表示與xi的距離最大的數(shù)據(jù)點與xi之間的距離；否則，δi表示在所有局部密度大于xi的數(shù)據(jù)點中與xi距離最小的數(shù)據(jù)點與xi之間的距離。

1.2.3 精英點綜合考察量

綜合兩種因素，定義一個將局部密度ρi和高密度點距離δi綜合考慮的量

γi=ρiδi,i∈ID。

(2)

(3)

圖3 精英點選取情況對比Fig..3 Comparison of elite selection

根據(jù)給出的γ值標(biāo)準(zhǔn)，可以對樣本數(shù)據(jù)進行選取。圖3是保留比例為30%情況下，精英點選取情況對比其中被圈出的點是精英點。

2 樣本約簡算法

基于精英點選取標(biāo)準(zhǔn)，提出了基于密度的DBES(density-basedeliteselecting)樣本約簡算法如下：

輸入:樣本集D,閾值截取位置Pdc,精英保留比例Pelite輸出:樣本子集Delite1.計算得到距離矩陣Dd;2.根據(jù)Pdc得到對應(yīng)位置的dc及密度ρ;3.for樣本集中的每一條數(shù)據(jù)xi4. Ifxi具有最大局部密度5. 找到與xi的距離最大的數(shù)據(jù)點xj;δi=dij;6. else7. 找到密度比xi大的數(shù)據(jù)點中,與xi距離最小的數(shù)據(jù)點xk;δi=dik;8. endif9.endfor10.計算γ值;根據(jù)Pelite值保留對應(yīng)百分比的樣本集Delite。

算法中，樣本集D表示的是帶約簡的原始樣本集；Pdc決定了算法所得到密度的有效性，同時也會影響到選取樣本子集的有效性；Pelite決定了樣本子集的大小，可以根據(jù)需要進行設(shè)定。關(guān)于Pdc和Pelite這兩個參數(shù)的設(shè)定將在第3.3節(jié)進行討論。

表1 樣本集說明

假設(shè)樣本集中包含數(shù)據(jù)點個數(shù)為n，計算距離矩陣Dd的時間復(fù)雜度為O(n2)。由于距離矩陣Dd是對稱矩陣，所以在實際計算時可以計算一個上三角矩陣，節(jié)省一半的計算時間。計算δ值，需要比較兩兩之間的密度，時間復(fù)雜度為O(n2)。和計算距離矩陣Dd類似，根據(jù)矩陣的對稱性可以節(jié)省一半的時間。算法中其他部分時間復(fù)雜度很低，因此整個算法的時間復(fù)雜度為O(n2)。

3 實驗分析與討論

實驗包括三部分。3.1節(jié)是本文算法與其他樣本約簡算法的對比實驗，對算法的約簡比例和在分類算法上的分類精度進行了實驗。其中用于對比的樣本約簡算法考慮到了所屬類別以及影響力[11]，用于測試的分類算法包括SVM、KNN和C4.5三種不同類型的分類算法。3.2節(jié)是樣本約簡后對分類的影響實驗。3.3節(jié)是算法約簡穩(wěn)定性及參數(shù)設(shè)置的分析實驗，通過實驗給出了DBES算法的參數(shù)設(shè)置建議。

實驗所用樣本集見表1，表2是選擇對比的樣本約簡算法。

3.1 約簡算法實驗對比

本節(jié)選擇了幾種不同類型的算法進行對比分析。表3是樣本約簡比例(reductionrate,RR)的對比。表4～7是分類精度的對比，其中DBES1和DBES2分別表示：在Pdc取值分別為0.02的情況下，Pelite取值為0.3和取值為0.5時的計算結(jié)果。

表2 選擇對比的樣本約簡算法

從表3可以看出，MCS算法在w1a樣本集上沒有實現(xiàn)有效約簡，樣本集大小無變化；在mushrooms樣本集上，MCS、ICF和DROP3算法得到的樣本子集偏小，而RENN算法得到的樣本子集和原樣本集相同，約簡效果較差；相比于其他算法，DBES算法可以對樣本集進行有效約簡，并且根據(jù)Pelite的不同，可以得到任意大小的樣本子集。通過調(diào)整參數(shù)Pelite，可以使得約簡比例高于其他的幾種算法。

表3 樣本約簡比例對比

表4 樣本子集分類精度對比(SVM)

表4是樣本子集的分類精度對比，使用約簡后的樣本子集作為訓(xùn)練集，用LIBSVM進行訓(xùn)練得到分類模型，在測試集上進行測試得到分類精度。表格中average行表示樣本約簡比例以及樣本子集分類精度的均值。表5和表6分別是KNN算法和C4.5算法的實驗結(jié)果。結(jié)合表3、表4和表5可以看出，采用不同的分類算法測試，DBES算法都有較好的表現(xiàn)，其中在決策樹(C4.5)算法下的優(yōu)勢最為明顯。由于提出的準(zhǔn)則以及算法不針對某種分類器，因此受分類算法的影響較??；與之相比較，其他算法受分類算法的影響較大。另外，對比3個表中DBES算法在Pelite不同取值時的分類精度可以看出，增大Pelite可以提高DBES算法的分類精度。

通過表3～6中的average可以看到，有的算法對樣本集平均約簡比例較大，但分類精度偏低，如DROP3算法；有的算法分類精度較高，但對樣本集平均約簡比例較小，如RENN算法；相比較于其他的方法，DBES算法能夠在兩個方面都保持較好的效果。

為了更好的說明DBES算法的優(yōu)越性，采用文獻[11]中的約簡算法比較方法，將約簡比例和分類精度的乘積作為新的綜合指標(biāo)，得到約簡效果是綜合指標(biāo)對比如表7，從表中可以看出DBES算法(Pelite=0.3)的綜合指標(biāo)最高且非常穩(wěn)定。

表8和圖4是各個算法在不同樣本集上分類精度和約簡比例的方差。方差的大小反映了算法的穩(wěn)定性。DBES算法可以根據(jù)參數(shù)將樣本集約簡到指定大小，約簡穩(wěn)定性高；對比不同分類算法上的分類精度方差可以發(fā)現(xiàn)，本文提出算法方差都非常小，分類精度的穩(wěn)定性也明顯好于其他算法。

3.2 約簡算法對分類的影響

本節(jié)以SVM為例，采用交叉驗證的方式，對算法進行了測試。實驗選擇了fourclass、heart和a1a樣本集。其中fourclass是人工數(shù)據(jù)集，heart是低維真實數(shù)據(jù)集，a1a是高維真實數(shù)據(jù)集。實驗結(jié)果如圖5～7所示，圖中實線代表約簡后的分類精度及其均值，虛線代表原樣本集分類精度及其均值。

表5 樣本子集分類精度對比(KNN)

表6 樣本子集分類精度對比(C4.5)

表7 約簡效果綜合指標(biāo)對比

表8 約簡比例和分類精度的方差

圖4 約簡比例和分類精度的方差Fig.4 Variance of reduction ratio and classification accuracy

圖5 fourclass隨機抽樣驗證結(jié)果Fig.5 Random sample validation results of data set 1

圖6 heart隨機抽樣實驗結(jié)果Fig.6 Random sample validation results of data set 2

圖7 a1a降維后的實驗結(jié)果Fig.7 Results of data set 3 after dimension reduction

在fourclass上進行試驗，隨機抽樣10次，抽取比例為50%，閾值截取位置Pdc=0.2，精英保留比例Pelite=0.25。由圖5可以看出，因為fourclass為人工樣本集合，樣本點是使用算法按規(guī)則產(chǎn)生的，隨機抽樣驗證結(jié)果的均值非常接近，其中有些情況下的精度甚至超過了原樣本集的結(jié)果。

在heart上進行試驗，隨機抽樣20次，抽取比例為50%，閾值截取位置Pdc=0.2，精英保留比例Pelite=0.3。由圖6可以看出，該算法在該樣本集上有較好的表現(xiàn)，約簡后樣本子集的分類結(jié)果甚至超過了原樣本集的結(jié)果。真實數(shù)據(jù)中存在噪聲數(shù)據(jù)，使用這樣的數(shù)據(jù)進行訓(xùn)練，分類模型很可能受到噪聲數(shù)據(jù)的影響。提出的約簡算法能夠過濾掉噪聲數(shù)據(jù)，從而提高分類精度。

DBES算法在處理高維數(shù)據(jù)時效果有所下降。由于高維數(shù)據(jù)的稀疏性，將低維空間中的距離度量函數(shù)應(yīng)用到高維空間時，隨著維數(shù)的增加，數(shù)據(jù)對象之間距離的差異將不復(fù)存在，其有效性大大降低。實際應(yīng)用中最常用的是PCA降維的方法。圖7是對a1a使用PCA降到10維之后的實驗結(jié)果，隨機抽樣10次，抽取比例為50%，閾值截取位置Pdc=0.02，精英保留比例Pelite=0.3。

通過以上實驗可以看出，提出的樣本約簡算法能夠較好地保持原分類算法的分類精度；對某些包含噪聲的樣本集合能夠提高分類精度；對于高維數(shù)據(jù)經(jīng)過降維處理之后，也能保持分類精度。

3.3 算法中參數(shù)的討論

算法中包含三個參數(shù)，除了參數(shù)D，其他兩個參數(shù)都需要給定。其中Pdc決定了算法所得到密度的有效性，Pelite決定了樣本子集的大小。Pdc和Pelite的取值都在(0,1]之間并且由用戶給定。圖8表示的是Pelite=0.3時，Pdc取值變化對分類精度的影響(其中橫軸代表Pdc取值變化，縱軸代表分類精度百分比)。圖9表示的是Pdc=0.2時，Pelite取值變化對分類精度的影響(其中橫軸代表Pelite取值變化，縱軸代表分類精度百分比)。

從圖8中可以看出，Pdc的取值在[0.1,0.4]區(qū)間有較穩(wěn)定的表現(xiàn)，取值過大或過小都會影響算法的穩(wěn)定性；雖然在某些樣本集上如ionosphere，隨著Pdc的增大，分類精度有所提升，但在大部分樣本集上，都會保持不變或者下降。從圖9中可以看出，當(dāng)Pelite的取值小于0.2時，分類精度會出現(xiàn)較大的波動。結(jié)合實際分析，保留更多的樣本點意味著保留了更多的信息，會提高分類的精度。Pelite的增大意味著保留的樣本子集逐漸增大，當(dāng)Pelite值為1時意味著沒有約簡。所以，Pelite的取值可以根據(jù)樣本數(shù)據(jù)和實際需求自行設(shè)定，建議取值區(qū)間為[0.2,1]。

圖8 Pdc取值變化對分類精度的影響Fig..8 Effect of change of Pdc onclassification accuracy

圖9 Pelite取值變化對分類精度的影響Fig.9 Effect of change of Peliteon classification accuracy

4 結(jié)語

本文給出了一種新的樣本點選取標(biāo)準(zhǔn)，并基于該標(biāo)準(zhǔn)設(shè)計實現(xiàn)了一種適用于不同分類器的樣本約簡算法。與其他算法相比較，該算法可以根據(jù)需求獲得任意大小的樣本子集。與多種分類算法進行測試對比，算法的約簡效果綜合指標(biāo)要優(yōu)于其他算法。對包含噪聲點的樣本集，算法的分類精度和穩(wěn)定性均有一定程度的提高。在模式挖掘中使用該算法，可以提高模式挖掘效率。如何針對大數(shù)據(jù)做并行化改進，是下一步需要研究的問題。

[1]WILSONDL.Asymptoticpropertiesofnearestneighborrulesusingediteddata[J].IEEETransactionsonSystemsMan&Cybernetics,1972,2(3):408-421.

[2]WILSONDR,MARTINEZTR.Reductiontechniquesforinstance-basedlearningalgorithms[J].MachineLearning,2000,38(3):257-286.

[3]TOMEKI.Anexperimentwiththeeditednearest-neighborrule[J].IEEETransactionsonSystemsMan&Cybernetics,1976,SMC-6(6):448-452.

[4]HARTP.Thecondensednearestneighborrule[J].IEEETransactionsonInformationTheory,1968,14(3):515-516.

[5]GATESG.Thereducednearestneighborrule[J].IEEETransationsonInformationTheory,1972,18(3):431-433.

[6]DASARATHYBV.Minimalconsistentset(MCS)identificationforoptimalnearestneighbordecisionsystemsdesign[J].IEEETransactionsonSystemsMan&Cybernetics,1994,24(3):511-517.

[7]ANGIULLIF.Fastnearestneighborcondensationforlargedatasetsclassification[J].IEEETransactionsonKnowledgeandDataEngineering,2007,19(11):1450-1464.

[8]BRIGHTONH,MELLISHC.Advancesininstanceselectionforinstance-basedlearningalgorithms[J].DataMining&KnowledgeDiscovery,2002,6(2):153-172.

[9]WILSONDR,MARTINEZTR.Reductiontechniquesforinstance-basedlearningalgorithms[J].MachineLearning,2000,38(3):257-286.

[10]REINARTZT.Aunifyingviewoninstanceselection[J].DataMining&KnowledgeDiscovery,2002,6(2):191-210.

[11]GARCIAS,DERRACJ,CANOJR,etal.Prototypeselectionfornearestneighborclassification:Taxonomyandempiricalstudy[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,2012,34(3):417-435.

[12]CHENJ,ZHANGC,XUEX,etal.Fastinstanceselectionforspeedingupsupportvectormachines[J].Knowledge-BasedSystems,2013,45(3):1-7.

[13]WANGXZ,DONGLC,YANJH.Maximumambiguity-basedsampleselectioninfuzzydecisiontreeinduction[J].IEEETransactionsonKnowledge&DataEngineering,2012,24(8):1491-1505.

[14]HAMIDZADEHJ,MONSEFIR,YAZDIHS.LMIRA:Largemargininstancereductionalgorithm[J].Neurocomputing,2014,145(18):477-487.

[15]HAMIDZADEHJ,MONSEFIR,YAZDIHS.IRAHC:Instancereductionalgorithmusinghyperrectangle[J].PatternRecognition,2015,48(5):1878-1889.

[16]NIKOLAIDISK,RODRIGUEZ-MARTINEZE,GOULERMASJY,etal.Spectralgraphoptimizationforinstancereduction[J].IEEETransactionsonNeuralNetworks&LearningSystems,2012,23(7):1169-1175.

[17]GARCIA-LIMONM,ESCALANTEHJ,MORALES-REYESA.IndefenseofonlineKmeansforprototypegenerationandinstancereduction[C]//ACMConferenceonComputerSupportedCooperativework,CSCW2004,Chicago,2016:274-283.

[18]JAMJOOMM,HINDIKE.Partialinstancereductionfornoiseelimination☆[J].PatternRecognitionLetters,2016,74:30-37.

[19]RODRIGUEZA,LAIOA.Clusteringbyfastsearchandfindofdensitypeaks[J].Science,2014,344 (6191):1492-1496.

[20]LEWISDD,GALEWA.Asequentialalgorithmfortrainingtextclassifiers[C]//AcmSigirForum.Springer-VerlagNewYork,Inc.1994:3-12.

[21]SETTLESB.Activelearningliteraturesurvey[J].UniversityofWisconsinmadison,2010,39(2):127-131.

[22]DAGANI,ENGELSONSP.Committee-basedsamplingfortrainingprobabilisticclassifiers[J].MachineLearningProceedings,1995:150-157.

[23]SUYKENSJAK,VANDEWALLEJ.Leastsquaressupportvectormachineclassifiers[J].NeuralProcessingLetters,1999,9(3):293-300.

[24]THOTK,KLEINBERGEM.Buildingprojectableclassifiersofarbitrarycomplexity[C]//InternationalConferenceonPatternRecognition.IEEEComputerSociety,1996:880.

[25]HSUCW,CHANGCC,LINCJ.Apracticalguidetosupportvectorclassification[R].Taiwan:NationalTaiwanUniversity.

[26]PLATTJC.Fasttrainingofsupportvectormachinesusingsequentialminimaloptimization[C]//AdvancesinKernelMethods-supportVectorRning.MITPress,1999:185-208.

(責(zé)任編輯：傅 游)

An Instance Reduction Algorithm for Different Classifiers

CHENG Rufeng,LIANG Yongquan,LIU Tong

(College of Computer Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266590,China)

Most of the existing instance reduction algorithms are designed for particular classifiers,which have some limitations in practical application.Combined with the idea of clustering algorithm,this paper proposes an instance reduction algorithm applicable to different classifiers.The core idea is to select instances with high density and relatively far distance.Compared with other instance reduction algorithms,this algorithm can obtain the instance subset in any size and can be applied to a variety of classification algorithms.For the set with noise,both the classification accuracy and stability of the proposed algorithms can be improved to some extent.

instance reduction; criterion; density; instance subset

2016-10-12

山東省高等學(xué)?？萍加媱濏椖?J14LN33)；中國博士后科學(xué)基金項目(2014M561949)；2014青島市博士后項目；山東科技大學(xué)研究生科技創(chuàng)新項目(SDKDYC170340)

程汝峰(1992—),男,山東德州,碩士研究生,主要從事數(shù)據(jù)挖掘與機器學(xué)習(xí)研究． 梁永全(1968—),男,山東聊城,教授,博士生導(dǎo)師,主要從事分布式人工智能、數(shù)據(jù)挖掘與機器等的學(xué)習(xí)研究,本文通信作者．E-mail：lyq@sdust.edu.cn

TP181

A

1672-3767(2017)03-0114-09