自適應(yīng)半徑選擇的近鄰鄰域分類器

張清華 肖嘉瑜 艾志華 王國(guó)胤

粗糙集模型[1-2]作為一種處理不完備、不確定性信息的數(shù)據(jù)分析工具，廣泛應(yīng)用在機(jī)器學(xué)習(xí)[3-4]、模式識(shí)別[5-6]、特征選擇[7-9]、數(shù)據(jù)挖掘[10-12]、不確定性信息處理[13-15]等眾多領(lǐng)域中.然而經(jīng)典粗糙集模型建立在等價(jià)關(guān)系的基礎(chǔ)上，將樣本數(shù)據(jù)劃分成等價(jià)類，只能處理名義型數(shù)據(jù).對(duì)于現(xiàn)實(shí)生活中廣泛存在的數(shù)值型數(shù)據(jù)，經(jīng)典粗糙集模型處理原始數(shù)據(jù)時(shí)必須先離散化，導(dǎo)致部分信息丟失.為了克服經(jīng)典粗糙集這個(gè)缺陷，大量研究工作在非等價(jià)關(guān)系上推廣經(jīng)典粗糙集模型，如鄰域粗糙集(Neighborhood Rough Set, NRS)[16-18]、模糊粗糙集[19-21]、覆蓋粗糙集[22-23]等.

胡清華等[24-25]基于拓?fù)淇臻g球形鄰域引入鄰域粗糙集，使用鄰域近似(鄰域)代替經(jīng)典粗糙集中的等價(jià)關(guān)系，使其既可以支持離散型數(shù)據(jù)又可以支持?jǐn)?shù)值型數(shù)據(jù).之后，該理論成功擴(kuò)展到特征選擇[26-27]、分類[28-30]、機(jī)器學(xué)習(xí)[31-32]等眾多應(yīng)用領(lǐng)域.在分類應(yīng)用中，Hu等[33]基于NRS實(shí)現(xiàn)基于多數(shù)原則的鄰域分類器(Neighborhood Classifiers, NNC).之后，學(xué)者們以NNC為基本框架展開相關(guān)研究.徐蘇平等[34]在協(xié)同表達(dá)分類(Collaborative Representation Based Classification, CRC)思想的基礎(chǔ)上，提出鄰域協(xié)同分類器(Neighborhood Collaborative Classifiers, NCC).亓慧等[35]提出擴(kuò)充?；男蛄朽徲蚍诸惙椒?Expanded Granulation Based Sequen-tial Neighborhood Classification, ESNC)，設(shè)計(jì)得分評(píng)估機(jī)制，排序測(cè)試樣本，并標(biāo)注最靠前的待測(cè)樣本，將其加入訓(xùn)練集，以此擴(kuò)充待測(cè)樣本潛在的鄰域?；臻g.Rao等[36]提出FNEC-NNC，將鄰域策略引入標(biāo)簽噪聲數(shù)據(jù)的分析中，不僅去除帶噪聲標(biāo)簽的樣本，而且與基于最近鄰域的濾波器進(jìn)行對(duì)比，可有效克服噪聲樣本的影響.Kumar等[37]提出NRSC(Neighborhood Rough Set Based Classification)，在疾病預(yù)測(cè)和決策過程中，分類性能較優(yōu).

在上述鄰域分類器中:對(duì)于訓(xùn)練樣本，標(biāo)簽已知，不需要計(jì)算鄰域半徑，只考慮其與待測(cè)試樣本的距離；對(duì)于測(cè)試樣本，標(biāo)簽未知，需要計(jì)算其鄰域半徑，獲取鄰域，進(jìn)而預(yù)測(cè)標(biāo)簽.并且鄰域分類器在預(yù)測(cè)標(biāo)簽過程中，僅涉及測(cè)試階段.因此，基于已有的鄰域分類器，鄰域半徑作為決定鄰域分類器分類性能的關(guān)鍵因素，構(gòu)建方式主要存在如下不足.1)缺乏訓(xùn)練過程.傳統(tǒng)分類器中缺乏訓(xùn)練階段，沒有計(jì)算訓(xùn)練樣本的鄰域半徑，未充分挖掘訓(xùn)練樣本的條件屬性與其標(biāo)簽之間的有效關(guān)聯(lián)信息.2)鄰域半徑不通用.傳統(tǒng)鄰域半徑僅通過人工參數(shù)調(diào)節(jié)大小，不能較好地適用于所有測(cè)試樣本鄰域的構(gòu)建.3)分類器失效.面對(duì)數(shù)據(jù)中樣本分布不均勻等特殊情況，鄰域半徑劃分得到的部分樣本鄰域可能出現(xiàn)無樣本的情況，導(dǎo)致分類器失效而無法預(yù)測(cè)測(cè)試樣本標(biāo)簽.

為了解決上述問題，本文引入K近鄰算法(KNearest Neighbor, KNN)[38-39]，并為鄰域半徑增添訓(xùn)練階段，構(gòu)建新的訓(xùn)練鄰域半徑、近鄰鄰域半徑和近似鄰域半徑，由此提出自適應(yīng)半徑選擇的近鄰鄰域分類器(Near Neighborhood Classifier with Adaptive Radius Selection, NNC-AR).對(duì)于訓(xùn)練集上的樣本，基于K近鄰算法得到每個(gè)訓(xùn)練樣本能被正確分類的鄰域半徑，定義新的訓(xùn)練鄰域半徑，為鄰域半徑增添訓(xùn)練階段.同時(shí)充分挖掘訓(xùn)練樣本的條件屬性與其已知標(biāo)簽之間的有效關(guān)聯(lián)信息.對(duì)于測(cè)試集上的樣本，定義自適應(yīng)的近鄰鄰域半徑，克服選取傳統(tǒng)鄰域半徑參數(shù)時(shí)的主觀性.結(jié)合近鄰思想，以訓(xùn)練鄰域半徑為有效依據(jù)，最大化利用訓(xùn)練樣本與測(cè)試樣本間的相似性等關(guān)聯(lián)信息，有效提升樣本鄰域的分類精度和自適應(yīng)性.對(duì)于分類器失效的測(cè)試樣本，定義新的近似鄰域半徑.結(jié)合近鄰思想，有效解決數(shù)據(jù)分布不均勻時(shí)鄰域中無樣本導(dǎo)致分類器失效的問題，進(jìn)一步提升鄰域分類器的精度和泛化能力.在多個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明，NNC-AR的F1值和分類精度均較高.

1 相關(guān)工作

本節(jié)簡(jiǎn)要介紹鄰域分類器的相關(guān)定義，詳細(xì)介紹可見文獻(xiàn)[33]和文獻(xiàn)[40].

在分類學(xué)習(xí)中，常把決策信息系統(tǒng)表示為四元組

S=〈U,C∪D,V,f〉.

其中,

U={x1,x2,…,xn},

表示為由n個(gè)訓(xùn)練樣本構(gòu)成的非空有限集合，稱為論域或樣本空間.在分類任務(wù)中:通常將U劃分為訓(xùn)練樣本空間UTr和測(cè)試樣本空間UTe；

C={a1,a2,…,am}

表示U中所有樣本的條件屬性集合；

D={d1,d2,…,dp}

表示決策屬性值集合，對(duì)于?x∈U，d(x)表示決策屬性值，即標(biāo)簽；Va表示特征a的值域；f∶U×C→V表示信息函數(shù).

由決策屬性D可誘導(dǎo)樣本空間U生成若干個(gè)決策類

U/IND(D)={D1,D2,…,Dp}，

其中,IND(D)表示U上的一個(gè)等價(jià)關(guān)系，且對(duì)任一決策類,包含所有標(biāo)簽為dk的樣本集合

Dk={x∈U|d(x)=dk}，

其中dk表示第k個(gè)標(biāo)簽.

1.1 鄰域分類器

定義1[41]給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉，

屬性集合

C={a1,a2,…,am}，

對(duì)于?x∈U,y∈U，在條件屬性集合C下，不同樣本間的閔可夫斯基距離定義如下：

其中,?ai∈C，f(x,ai)表示樣本x在條件屬性ai上的取值.距離的度量常采用歐氏距離函數(shù),即P=2.

定義2[33]給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉，

對(duì)于?x∈U，樣本x對(duì)應(yīng)的鄰域

δ(x)={y∈U|Δ(x,y)≤δ},

其中δ表示鄰域半徑.

在構(gòu)建鄰域分類器模型過程中，為了將NRS進(jìn)一步適用于分類任務(wù),Hu等[33]定義δ作為鄰域半徑，通過鄰域決策完成樣本分類.

定義3[33]給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉,

對(duì)于測(cè)試樣本x∈U，樣本x的鄰域半徑為

δ=min(Δ(x,yi))+

ω(max(Δ(x,yi))-min(Δ(x,yi))).

其中:ω∈(0,1]，表示一個(gè)隨機(jī)參數(shù)；min(Δ(x,yi))表示距離x最短的訓(xùn)練樣本yi與x之間的距離；max(Δ(x,yi))表示距離x最長(zhǎng)的訓(xùn)練樣本yi與x之間的距離.

鄰域半徑δ決定鄰域分類器分類性能優(yōu)劣.然而，傳統(tǒng)鄰域分類器在構(gòu)建δ時(shí)采用帶有人工參數(shù)ω的動(dòng)態(tài)調(diào)節(jié)方式，具有一定程度上的不確定性和主觀性.隨著δ逐漸增大，鄰域δ(x)也越大，即落到x的鄰域空間中的樣本越多.如圖1所示，在鄰域分類器中存在3個(gè)不同的鄰域半徑，相應(yīng)存在3個(gè)不同大小的鄰域，分別使用實(shí)線、虛線和點(diǎn)線表示.因此在鄰域分類器中，鄰域半徑設(shè)定偏大或偏小時(shí)都會(huì)直接影響測(cè)試樣本標(biāo)簽的預(yù)測(cè).

圖1 鄰域決策圖示例Fig.1 Example of neighborhood decision

定義4[31]給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉，

對(duì)于測(cè)試樣本x∈U，利用鄰域δ(x)得出x屬于每種決策類Dj的鄰域粗糙隸屬度，鄰域粗糙隸屬函數(shù)為

其中,Dj∈U/IND(D)，表示論域U根據(jù)決策屬性D劃分并誘導(dǎo)生成的決策類.

以定義4中的鄰域粗糙隸屬度為依據(jù)，鄰域分類器進(jìn)一步通過多數(shù)投票原則，為測(cè)試集中的樣本完成最終的鄰域決策：當(dāng)決策類Dj對(duì)應(yīng)的決策標(biāo)簽dj滿足

時(shí)，測(cè)試樣本x的標(biāo)簽被預(yù)測(cè)為dj.

如圖1所示，鄰域分類器中δ1>δ2>δ3.當(dāng)鄰域半徑為δ3時(shí)，根據(jù)多數(shù)投票規(guī)則測(cè)試樣本將被預(yù)測(cè)為黑色標(biāo)簽；當(dāng)鄰域半徑增加到δ2時(shí)，測(cè)試樣本將被預(yù)測(cè)為鄰域粗糙隸屬度最大的灰色標(biāo)簽；當(dāng)鄰域半徑繼續(xù)增加到δ1時(shí)，測(cè)試樣本會(huì)被標(biāo)注為白色標(biāo)簽.由此可見，鄰域半徑的構(gòu)建會(huì)直接干擾鄰域分類器對(duì)測(cè)試樣本的鄰域決策.因此，鄰域半徑作為決定預(yù)測(cè)樣本標(biāo)簽過程的關(guān)鍵因素還需要進(jìn)一步優(yōu)化.

1.2 KNN分類算法

KNN分類算法是模式識(shí)別中簡(jiǎn)單有效的經(jīng)典算法之一，基本原理如下：給定一組已知類別的訓(xùn)練樣本和待分類樣本，找到訓(xùn)練樣本中距離待分類樣本最近的K個(gè)最近鄰居，進(jìn)而將K個(gè)近鄰中最多個(gè)數(shù)的標(biāo)簽分配給待分類樣本.

對(duì)于待分類樣本xte∈UTe，KNN的分類過程如下.首先，為待分類樣本xte定義一組超過K個(gè)相似的目標(biāo)鄰居，即按照xte與訓(xùn)練樣本之間的歐氏距離遞增排序，取排名前K個(gè)訓(xùn)練樣本.再利用多數(shù)投票原則，根據(jù)K個(gè)最近鄰居的標(biāo)簽，預(yù)測(cè)得出待分類樣本xte的標(biāo)簽.重復(fù)上述步驟，直到所有待分類樣本預(yù)測(cè)結(jié)束.

2 自適應(yīng)半徑選擇的近鄰鄰域分類器

2.1 鄰域半徑訓(xùn)練

已有的鄰域分類器模型僅涉及測(cè)試階段，對(duì)于已知標(biāo)簽的訓(xùn)練樣本，不需要計(jì)算鄰域半徑，也未構(gòu)建鄰域進(jìn)行鄰域決策，只考慮其與待測(cè)樣本之間的距離作為待測(cè)試樣本鄰域決策的依據(jù).為了進(jìn)一步利用訓(xùn)練樣本的有效信息，NNC-AR結(jié)合KNN,為訓(xùn)練樣本定義訓(xùn)練鄰域半徑，增添鄰域半徑的訓(xùn)練階段，為提升待測(cè)試樣本的預(yù)測(cè)精度提供有效根據(jù).

訓(xùn)練鄰域半徑的構(gòu)建過程如下：結(jié)合KNN，對(duì)每個(gè)已知標(biāo)簽的訓(xùn)練樣本xtr，選取距離xtr最近的K個(gè)樣本，進(jìn)而根據(jù)這K個(gè)樣本的標(biāo)簽值,基于多數(shù)表決原則預(yù)測(cè)得到xtr的標(biāo)簽，依次取K=1,2,…,10直至xtr被預(yù)測(cè)正確.最后得到xtr被預(yù)測(cè)成功時(shí)的值，選取距離xtr排名的第K個(gè)近鄰點(diǎn)與xtr之間的距離，作為訓(xùn)練樣本xtr的鄰域半徑，即訓(xùn)練鄰域半徑.

如圖2所示，當(dāng)K=4時(shí)，訓(xùn)練樣本xtr的標(biāo)簽?zāi)鼙徽_預(yù)測(cè)為白色，繼而將距離xtr排名的第4個(gè)近鄰點(diǎn)與xtr之間的距離作為xtr的訓(xùn)練鄰域半徑.

圖2 訓(xùn)練鄰域半徑構(gòu)建圖Fig.2 Training neighborhood radius construction

定義5給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉，

其中

U=UTr∪UTe.

對(duì)于訓(xùn)練樣本xtr∈UTr，訓(xùn)練鄰域半徑為：

δtr=Δ(xtr,NNk(xtr)),

其中,NNk(xtr)表示與當(dāng)前訓(xùn)練樣本xtr距離排名第K個(gè)的近鄰點(diǎn)，也是使xtr能被正確分類的最近鄰，K=1,2,…,10.另外若依次取K=1,2,…,10，訓(xùn)練樣本xtr都無法被分類，即只有K>10時(shí)，訓(xùn)練樣本xtr才能被正確預(yù)測(cè)為已知標(biāo)簽，這表明訓(xùn)練樣本xtr顯然偏離其它同類訓(xùn)練樣本的正常分布范圍，因此將樣本xtr歸為噪聲點(diǎn)并刪除，不參與NNC-AR本輪訓(xùn)練階段和測(cè)試階段的構(gòu)建.

NNC-AR通過KNN計(jì)算已知標(biāo)簽的訓(xùn)練樣本能被正確預(yù)測(cè)時(shí)的訓(xùn)練鄰域半徑，為鄰域半徑的構(gòu)建增添訓(xùn)練階段，充分挖掘訓(xùn)練樣本條件屬性與決策屬性之間的有效關(guān)聯(lián)性信息，有利于構(gòu)建預(yù)測(cè)精度較高、分類性能較強(qiáng)的NNC-AR.

2.2 近鄰鄰域半徑

在已有分類器模型的預(yù)測(cè)階段中，動(dòng)態(tài)調(diào)節(jié)人工參數(shù)以構(gòu)建待測(cè)樣本的鄰域半徑，具有一定程度上的主觀性和不確定性.因此，在NNC-AR的測(cè)試階段，考慮待測(cè)試樣本與訓(xùn)練樣本之間的相似性以解決待測(cè)試樣本標(biāo)簽的預(yù)測(cè)問題.基于近鄰思想，選取距離待測(cè)試樣本最近的訓(xùn)練樣本，并以訓(xùn)練鄰域半徑為根據(jù)，為待測(cè)試樣本構(gòu)建新的近鄰鄰域半徑，有效克服傳統(tǒng)鄰域半徑中的動(dòng)態(tài)調(diào)節(jié)方式帶來的不確定性問題.

近鄰鄰域半徑的構(gòu)建過程如下：結(jié)合訓(xùn)練鄰域半徑和近鄰思想，根據(jù)定義5得到每個(gè)訓(xùn)練樣本被預(yù)測(cè)成功的鄰域半徑δtr.進(jìn)而求取距離待測(cè)試樣本xte最近的訓(xùn)練樣本，將其對(duì)應(yīng)的訓(xùn)練鄰域半徑作為該待測(cè)樣本xte的鄰域半徑，即近鄰鄰域半徑.

定義6給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉，

其中

U=UTr∪UTe.

表示與當(dāng)前測(cè)試樣本xte距離最近的訓(xùn)練樣本.

由于訓(xùn)練鄰域半徑的構(gòu)建是基于已知標(biāo)簽的訓(xùn)練樣本能被正確預(yù)測(cè)，NNC-AR將其進(jìn)一步融入測(cè)試階段.結(jié)合近鄰思想選取距離待測(cè)試樣本最近的訓(xùn)練樣本構(gòu)建近鄰鄰域半徑，不僅考慮測(cè)試樣本與訓(xùn)練樣本之間的關(guān)聯(lián)性，還能極大程度以訓(xùn)練階段的有效信息為根據(jù)準(zhǔn)確預(yù)測(cè)待測(cè)試樣本的標(biāo)簽,克服以往鄰域分類器模型選取鄰域半徑參數(shù)時(shí)的不確定性問題，一定程度上提升鄰域半徑的合理性和自適應(yīng)性，有效提升NNC-AR的分類性能.

圖3 近鄰鄰域半徑構(gòu)建圖Fig.3 Near neighborhood radius construction

2.3 近似鄰域半徑

在待測(cè)試樣本的標(biāo)簽預(yù)測(cè)階段中，通過近鄰鄰域半徑構(gòu)建鄰域能完成大多數(shù)測(cè)試樣本標(biāo)簽的正確預(yù)測(cè).然而，對(duì)于少數(shù)分布不均勻的待測(cè)試樣本，采用近鄰鄰域半徑構(gòu)造的鄰域可能會(huì)出現(xiàn)無樣本的情況，導(dǎo)致分類器失效而無法預(yù)測(cè)樣本標(biāo)簽.為了進(jìn)一步提升分類器模型的泛化能力，NNC-AR結(jié)合近鄰思想，為少數(shù)分類器失效的待測(cè)試樣本構(gòu)建新的近似鄰域半徑，解決部分樣本鄰域中無樣本的情況.

近似鄰域半徑的構(gòu)建過程如下：根據(jù)定義6先求取待測(cè)試樣本xte的近鄰鄰域半徑,用于劃分xte的鄰域.若發(fā)現(xiàn)鄰域內(nèi)沒有樣本，表示分類器失效，進(jìn)而將距離xte最近的訓(xùn)練樣本與xte之間的距離作為xte的鄰域半徑，即近似鄰域半徑.

定義7給定一個(gè)決策信息系統(tǒng)

S=〈U,C∪D,V,f〉，

其中

U=UTr∪UTe.

對(duì)于測(cè)試樣本xte∈UTe，近似鄰域半徑為：

其中

表示與當(dāng)前測(cè)試樣本距離最近的訓(xùn)練樣本.

綜上所述，NNC-AR結(jié)合近鄰思想，對(duì)于少數(shù)分布不均勻、出現(xiàn)空鄰域的待測(cè)試樣本，利用其與距離最近的訓(xùn)練樣本構(gòu)建近似鄰域半徑，完成對(duì)標(biāo)簽信息的有效預(yù)測(cè)，有效解決測(cè)試階段中的分類器失效問題，提升NNC-AR的泛化性能.

圖4 分類器失效圖Fig.4 Classifier failure

圖5 近似鄰域半徑構(gòu)建圖Fig.5 Approximate neighborhood radius construction

2.4 算法步驟

最終，得到NNC-AR步驟如算法1所示.

算法1NNC-AR

輸入決策信息系統(tǒng)〈UTr∪UTe,C∪D,V,f〉,

待測(cè)試樣本xte∈UTe

輸出輸出測(cè)試樣本xte的標(biāo)簽dj

#計(jì)算所有訓(xùn)練樣本的半徑及刪除噪點(diǎn)樣本

forxtr∈UTr:

計(jì)算δtr=Δ(xtr,NNk(xtr));

ifi>10 then:

從UTr剔除樣本xtr;

end if

end for

#計(jì)算測(cè)試樣本的半徑并對(duì)測(cè)試樣本預(yù)測(cè)

δ(xte)={xtr∈UTr|Δ(xte,xtr)≤δte};

ifdj=? then:

δ(xte)={xtr∈UTr|Δ(xte,xtr)≤δsim};

end if

returndj

NNC-AR的流程圖如圖6所示.

圖6 NNC-AR流程圖Fig.6 Flowchart of NNC-AR

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

在本節(jié)中，將NNC-AR與其它目前較先進(jìn)的模型進(jìn)行實(shí)驗(yàn)對(duì)比.對(duì)比的模型有NNC[33]、NCC[34]、ESNC[35]；對(duì)比算法有KNN，ID3(Iterative Dicho-tomiser 3)，CART(Classification and Regression Tree)、NB(Naive Bayes).在實(shí)驗(yàn)中,ESNC分為ESNC1(Score1 Based ESNC)和ESNC2(Score2 Based ESNC).NCC、NNC和ESNC的鄰域半徑均采用動(dòng)態(tài)調(diào)節(jié)的方式，設(shè)定隨機(jī)參數(shù)ω=0.1.

實(shí)驗(yàn)共選取10個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集，數(shù)據(jù)集信息如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental datasets

實(shí)驗(yàn)采用5折交叉驗(yàn)證，實(shí)驗(yàn)環(huán)境為Windows操作系統(tǒng)，16 GB內(nèi)存，3.60 Hz主頻，編程語言采用Python.

為了直觀展示算法之間的對(duì)比效果，采用的分類指標(biāo)為準(zhǔn)確率(Accuracy)和F1值.因此，給定一個(gè)數(shù)據(jù)集合，假設(shè)TP表示正確預(yù)測(cè)為正例的樣本數(shù)，F(xiàn)P表示錯(cuò)誤預(yù)測(cè)為正例的樣本數(shù)，TN表示正確預(yù)測(cè)為負(fù)例的樣本數(shù)，F(xiàn)N表示錯(cuò)誤預(yù)測(cè)為負(fù)例的樣本數(shù)，準(zhǔn)確率和F1值的定義為

其中，

表示精確率，

表示召回率.

為了對(duì)比NNC-AR的有效性，在10個(gè)UCI數(shù)據(jù)集上同時(shí)對(duì)比分類模型和經(jīng)典算法，將5折交叉驗(yàn)證實(shí)驗(yàn)的平均分類準(zhǔn)確率作為最終結(jié)果，具體如表2所示，F(xiàn)1值對(duì)比結(jié)果如表3所示，表中黑體數(shù)字表示最優(yōu)值.

實(shí)驗(yàn)參數(shù)設(shè)置如下：NCC、NNC和ESNC的鄰域半徑均采用動(dòng)態(tài)調(diào)整方法，人工參數(shù)ω=0.1，NCC的正則化參數(shù)λ=0.01，KNN中K=10.

表2 各模型在10個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率對(duì)比Table 2 Classification accuracy comparison of different models on 10 datasets %

表3 各模型在10個(gè)數(shù)據(jù)集上的F1值對(duì)比Table 3 F1 score of different models on 10 datasets %

由表2和表3可見，相比NCC、NNC、ESNC1和ESNC2，NNC-AR通過訓(xùn)練集找到最優(yōu)的半徑閾值，能有效適應(yīng)不同的數(shù)據(jù)分布，提升分類準(zhǔn)確率，在大部分?jǐn)?shù)據(jù)集上均能達(dá)到最優(yōu)值，同樣F1值也均能達(dá)到最優(yōu)效果.

相比KNN、ID3、CART和NB，NNC-AR和KNN能達(dá)到較優(yōu)的分類結(jié)果.但是KNN容易受到數(shù)據(jù)分布的影響，進(jìn)而影響分類效果.相比而言，NNC-AR可動(dòng)態(tài)調(diào)整鄰域半徑，在訓(xùn)練集上找到最優(yōu)半徑，適應(yīng)不同分布下的數(shù)據(jù)場(chǎng)景.

NNC-AR中引入KNN構(gòu)造訓(xùn)練階段，同時(shí)將K>10時(shí)仍無法被分類的訓(xùn)練樣本視為噪聲點(diǎn).由于在對(duì)比算法中，沒有為鄰域分類器構(gòu)建訓(xùn)練階段，未使用KNN為訓(xùn)練樣本構(gòu)建鄰域半徑，因此在噪聲點(diǎn)檢測(cè)方面，無法與其余算法完成對(duì)比.因此，在10個(gè)數(shù)據(jù)集上，分別統(tǒng)計(jì)NNC-AR刪除的噪聲點(diǎn)個(gè)數(shù)，取5折交叉驗(yàn)證實(shí)驗(yàn)的平均值作為結(jié)果.統(tǒng)計(jì)結(jié)果如下:Satimage數(shù)據(jù)集上NNC-AR刪除的噪聲點(diǎn)有264.8個(gè),Banknote數(shù)據(jù)集上有1.6個(gè)，Wbc數(shù)據(jù)集上有9.6個(gè)，Mushroom數(shù)據(jù)集上有0.2個(gè)，Breast數(shù)據(jù)集上有10.0個(gè)，Heart數(shù)據(jù)集上有24.6個(gè)，Parkinson數(shù)據(jù)集上有2.2個(gè)，Pima數(shù)據(jù)集上有90.4個(gè)，Credit數(shù)據(jù)集上有48.6個(gè)，Ionosphere數(shù)據(jù)集上有25.4個(gè).噪聲點(diǎn)刪除個(gè)數(shù)與數(shù)據(jù)集分布狀況總體呈正相關(guān).在分布較好的數(shù)據(jù)集(如Mushroom數(shù)據(jù)集)上，刪除的噪聲點(diǎn)較少，在分布較差的數(shù)據(jù)集(如Satimage數(shù)據(jù)集)上，刪除的噪聲點(diǎn)較多.通過刪除噪聲點(diǎn)，不僅能提升后續(xù)模型的分類精度，還能降低模型在分類時(shí)的時(shí)間損耗.

為了進(jìn)一步凸顯噪聲點(diǎn)定義中K的最大閾值設(shè)定為10 的有效性，計(jì)算K取不同最大值，即Kmax=11,12,13時(shí),NNC-AR的準(zhǔn)確率和F1值，并與NNC-AR的原始實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比.具體對(duì)比結(jié)果如圖7所示.由圖可見，相比Kmax=11、12、13，Kmax=10時(shí)NNC-AR在大部分?jǐn)?shù)據(jù)集上達(dá)到最優(yōu)的分類效果.

(a)準(zhǔn)確率(a)Accuracy

總之，NNC-AR通過增添鄰域半徑的訓(xùn)練階段、克服鄰域半徑人為參數(shù)的不確定性缺陷、解決數(shù)據(jù)分布不均出現(xiàn)空鄰域的問題等措施，有效提升鄰域分類器的F1值和分類準(zhǔn)確率.

4 結(jié) 束 語

本文針對(duì)鄰域半徑缺乏訓(xùn)練過程、鄰域半徑不通用、分類器失效等問題，提出自適應(yīng)半徑選擇的近鄰鄰域分類器(NNC-AR).構(gòu)建訓(xùn)練鄰域半徑，充分挖掘訓(xùn)練樣本中條件屬性與其已知標(biāo)簽間的有效關(guān)聯(lián)信息，為待測(cè)樣本標(biāo)簽的預(yù)測(cè)階段提供有力依據(jù).構(gòu)建近鄰鄰域半徑，調(diào)整以往分類器模型預(yù)測(cè)階段選取鄰域半徑參數(shù)時(shí)的主觀性.在一定程度上提升鄰域半徑的合理性和自適應(yīng)性，有效提升NNC-AR的分類性能.構(gòu)建近似鄰域半徑，解決測(cè)試階段分類器失效的問題，提升NNC-AR的泛化性能.在10組UCI數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)表明，NNC-AR的F1值和分類準(zhǔn)確率都取得顯著提升.下一步的研究工作是從時(shí)間性能方面實(shí)現(xiàn)鄰域分類器性能的進(jìn)一步提升.