亓慧,楊習貝,史穎,3

(1.太原師范學院 計算機系,山西 晉中 030619;2.江蘇科技大學 計算機學院,江蘇 鎮(zhèn)江 212003;3.山西大學 計算機與信息技術學院,山西 太原 030006)

0 引言

作為粒計算中的重要手段之一,鄰域粒化[1]無需采用離散化就可對數(shù)值型數(shù)據(jù)直接進行處理,被廣泛應用于屬性約簡、度量學習、圖像識別、多標記學習等領域[2-5]。而其最為直接、重要的應用之一就是鄰域分類器[1]。該分類器的核心機制是對給定的測試樣本進行鄰域的構建,繼而依據(jù)所生成鄰域粒中訓練樣本所提供的已知類別標簽信息,最終采用多數(shù)投票策略進行測試樣本的預測分類。事實上,鄰域分類器構造手段直觀、粒度表示靈活并且有著不俗的分類表現(xiàn),因此一經(jīng)提出就受到了眾多學者的青睞與推廣[6-11]。

面對現(xiàn)實數(shù)據(jù)的問題,鄰域分類器可能會存在以下兩點不足:1) 當訓練樣本數(shù)目不足時,測試樣本對應的鄰域粒中僅包含少量的訓練樣本,因而無法提供足夠的標簽信息,那么該測試樣本的預測將缺乏依據(jù);2) 當訓練樣本區(qū)分度不夠時,測試樣本對應的鄰域粒中的標簽信息可能會不適用于多數(shù)投票,那么該測試樣本的預測將難免出現(xiàn)偏差[12-18]。

為解決上述兩點問題,在傳統(tǒng)鄰域分類器的基礎之上,本文提出了一種擴充粒化的序列分類方式。主要涵蓋以下兩個模塊。1) 擴充?；?設計合適的樣本度量以評估排列測試樣本的預測可靠性,優(yōu)先選出最為可靠即排名最為靠前的測試樣本,利用傳統(tǒng)的鄰域分類器對其進行判別并將其加入訓練集中,進而擴充后續(xù)待測樣本潛在的鄰域搜索空間。2) 序列分類:迭代地加入,利用不斷豐富的標簽信息,依據(jù)待測樣本的可靠性排列,迭代地對待測樣本進行預測,直至完成所有測試樣本的分類。綜合這兩個模塊,我們期望利用新提出的方法改善傳統(tǒng)鄰域分類器的些許不足,并且進一步地提升鄰域粒化在分類應用上的性能表現(xiàn)。

本文的主要結構安排如下:第1節(jié)介紹鄰域?；捌湓卩徲蚍诸惼髦械膽?第2節(jié)在鄰域分類器的框架基礎上提出改進的擴充?；蛄朽徲蚍诸惙椒?第3節(jié)對所提方法進行相關的對比實驗與分析;第4節(jié)總結全文。

1 鄰域分類器

一般而言,給定一組訓練集,可被形式化地描述為形如二元組DTr≤UTr,C∪eu0wec8>的決策系統(tǒng),其中UTr為非空有限的訓練樣本的集合;C為條件屬性的集合,即特征集合;d為決策屬性。特別地,?x∈UTr,d(x)表示其決策屬性值,亦被稱作標簽。那么利用決策屬性可誘導出一組決策類,任一決策類可以表示為Xdi={x∈UTr:d(x)=di},其中di表示第i個標簽,顯然Xdi是包含所有標簽為di樣本的集合。

N(x)={y∈UTr:ΔB(x,y)≤δ}，

(1)

式(1)中ΔB是一基于特征子集B?C的距離度量函數(shù)(本文采用歐式距離),δ是一數(shù)值為非負的鄰域半徑參數(shù)。

進一步地,Hu等人[1]借助式(1)所示的鄰域概念,就可構造鄰域分類器。具體算法如下。

算法1 鄰域分類器(NEC)輸入:訓練集DTr,待測樣本x,鄰域半徑δ輸出:預測標簽^d(x)① 計算N(x)②For ?Xdi∈UTr/IND(d)do 計算Pr(Xdi,N(x))=|Xdi∩N(x)||N(x)| End③^d(x)=argmaxdiPr(Xdi,N(x))

可以發(fā)現(xiàn),對于算法1所示的傳統(tǒng)鄰域分類器而言,在對測試樣本進行鄰域粒生成時,往往集中且局限于固有的訓練樣本中。可想而知,當鄰域半徑過小或訓練樣本過少時,極有可能造成鄰域粒含有極少量甚至是不含任何有用的標簽信息,最終將致使測試樣本的分類失敗。譬如,在最壞的情況下,當求得的|N(x)|=0其中|·|表示任一集合的基數(shù),此時算法1對于該待測樣本的預測將顯得極為乏力。針對這種情形,基于對鄰域半徑的設置,Hu等人[1]在設計鄰域分類器時已做了充分的考慮,提出了鄰域半徑的max-min標準化方法,但是無法有效地解決第二種訓練樣本過少而致使的一系列問題,故本文將重點圍繞該問題,并提出相應的解決方案。

2 擴充粒化序列鄰域分類方法

本文提出了一種擴充?；男蛄朽徲蚍诸惙椒?，大體框架見圖1。

圖1 擴充?；蛄朽徲蚍诸惙椒ǖ牧鞒虉DFig.1 The flowchart of expanded granulation basedsequential neighborhood classification method

從圖1可以明顯看出,所提方法核心部分包含：

1) 得分評估。在傳統(tǒng)的鄰域分類器中,測試樣本在被分類時,并無先后順序。在所提方法中,我們將對測試樣本進行合適的得分評估,并對其進行排序賦予不同的分類優(yōu)先等級。

2) 序列擴充。在傳統(tǒng)的鄰域分類器中,訓練樣本的數(shù)目固定,且測試樣本一旦完成分類,對后續(xù)任務并無指導或輔助的作用。在所提方法中,我們將利用優(yōu)先已分類的測試樣本依次地擴大訓練樣本規(guī)模,為后續(xù)待測樣本提供可靠的參考信息。

3) 信息?；?。在傳統(tǒng)的鄰域分類器中,當訓練樣本數(shù)目過少時,測試樣本鄰域粒難以提供可借鑒的標簽信息。在所提方法中,我們在上一步驟中對其進行了擴充,力圖改善這樣的不利局面。

4) 標簽預測。在傳統(tǒng)的鄰域分類器中,利用測試樣本的信息?；Y果對其進行多數(shù)投票策略。在所提方法中,我們在鄰域粒得以擴展的基礎上,同樣利用該策略進行測試樣本的分類。

不難發(fā)現(xiàn),得分評估作為所提方法的第一環(huán)節(jié)就顯得尤為重要。為此,我們設計了兩種評估函數(shù)。

(2)

(3)

需要注意的是,式(2)、(3)中的關于測試樣本的鄰域粒為N(x)={y∈UTr∪UTe:ΔB(x,y)≤δ}。此舉主要是為了評估待測樣本的預測可靠性。若待測樣本在整個訓練與測試集上的鄰域中包含更多的已知標簽信息,那么樣本被正確分類可能性則更大,這就意味著該樣本被分類的優(yōu)先級更高,對后續(xù)分類任務更具輔助作用。同樣地,鄰域中所含訓練樣本與任一測試樣本的距離也可被引入進行評估。基于這樣的考慮,式(1)、(2)的評估可被建立起來。

接下來,我們就可給出具體的分類算法。

算法2 擴充?；蛄朽徲蚍诸惼?ESNC) 輸入:訓練集DTr,測試集DTe,鄰域半徑δ輸出:預測標簽集合D^①D^←?② For ?x∈UTe 算score1(x)或score2(x)End③ 對測試樣本排序得到RankTe={y1,y2,…,y|DTe|}④ For m=1:|DTe|do 利用算法1得到^d(ym) UTe←UTe-{ym} UTr←UTr∪{ym} D^←D^∪{d^(ym)}End

如算法2所示,不同于傳統(tǒng)鄰域分類器中的粒化手段,我們期望在更廣闊的可搜索鄰域空間上評估每個待測樣本的可靠性,并將此評估作為其候選的得分選項。顯而易見,得分越高,被預測的優(yōu)先級別也越高。進一步地,借助那些分類優(yōu)先級更高的測試樣本,我們試圖擴大測試樣本潛在的鄰域搜索范圍,以期為后續(xù)的分類提供數(shù)量更充足、信息更廣泛的標簽信息。也正因如此,所提算法2更適用于多個訓練樣本的預測,而當待測樣本的數(shù)目為1時,算法2將等同于算法1。另外,由于需要求解各個樣本之間的距離,算法的時間復雜度為O((|DTr|+|DTe|)2)。

3 實驗分析

為了驗證所提ESNC算法的有效性,在6組UCI數(shù)據(jù)集上進行了相關的對比實驗分析。數(shù)據(jù)集的基本信息如表1所示。

表1 實驗數(shù)據(jù)集描述

實驗環(huán)境為個人筆記本電腦,參數(shù)配置為CPU Intel(R) Core (TM) i7-7700HQ CPU @ 2.80 GHz,內存8.00 GB,系統(tǒng)類型Windows 10 64位,程序開發(fā)與運行平臺為MATLAB R2018b。

圖2 分類準確率結果Fig.2 Results of classification accuracies

在具體的實驗運行中,我們對數(shù)據(jù)集的特征值進行了max-min標準化,并且選取了10組鄰域半徑參數(shù),即δ=0.03,0.06,0.09,…,0.3。此外,我們隨機劃分實驗所用數(shù)據(jù)集中的10%、20%、30%、40%、50%樣本為訓練集,余下則作為測試集。主要計算統(tǒng)計ESNC1 (基于score1的ESNC)、ESNC2 (基于score2的ESNC)在10個半徑下測試樣本上的平均分類準確率,并將其與傳統(tǒng)鄰域分類器NEC[1]、基于相對距離的鄰域粒分類器NGCR[12]、基于絕對距離的鄰域粒分類器NGCA[12]的準確率比較。具體實驗結果見圖2。

從圖2可以看出:

1) 隨著訓練樣本數(shù)目的增多,幾種分類器的準確率大體都是呈上升趨勢,該現(xiàn)象與我們常識一致,即足量可靠的訓練數(shù)據(jù)對于分類模型性能表現(xiàn)是有提升作用的。

2) 本文設計的兩種得分評估機制所構建的ESNC算法在分類性能上基本沒有多大差異,可見通過個數(shù)與距離來評估待測樣本的優(yōu)先分類級別效果是相近甚至是相同的。

3) 最關鍵也是最重要的一點,不管是利用ESNC1 (基于score1的ESNC)還是ESNC2 (基于score2的ESNC),所得到分類準確率結果都要比所對比的NEC、NGCR以及NGCA要好,充分說明了在訓練樣本規(guī)模較小時,所提方法對于解決鄰域分類器的局限是有一定幫助的。

為了進一步驗證所提算法的有效性,利用Wilcoxon秩和檢驗開展了顯著性分析。需要注意的是,考慮到所提的兩種方法分類結果相近,我們采用ESNC1與其他算法進行對比,輸出的p值如表2所示,其中,粗體表示所提算法明顯優(yōu)于對比方法。

表2 分類準確率的顯著性檢驗結果

從表2可以看出,在大多數(shù)情況下,所提ESNC1算法的分類表現(xiàn)明顯優(yōu)于所對比的算法,尤其是NGCR以及NGCA。

4 結論

為解決訓練樣本規(guī)模較小時鄰域分類器的局限性,本文提出了一種擴充?；男蛄朽徲蚍诸惙椒?。該方法主要建立于待測樣本標注前的評估排序,以及標注后的擴充?；嶒灲Y果表明,本文提出的方法能夠提供較好的分類性能。

在本文工作的基礎上,筆者后續(xù)將就以下內容做進一步地探討:1) 提高算法運行效率,擬采用樣本簇的方式對訓練樣本進行擴充。2) 特征空間的優(yōu)化,擬采用特征選擇的方式選取更具鑒別能力的特征集合構建鄰域粒。