劉利，張德生，肖燕婷

（西安理工大學(xué) 理學(xué)院，西安 710054）

0 概述

分類(lèi)任務(wù)［1］是利用已知類(lèi)別的樣本通過(guò)建立模型預(yù)測(cè)新樣本的類(lèi)別［2］。分類(lèi)是數(shù)據(jù)挖掘中最重要的任務(wù)之一，應(yīng)用十分廣泛。目前，常用的分類(lèi)算法主要有決策樹(shù)［3］、貝葉斯分類(lèi)器［4］、人工神經(jīng)網(wǎng)絡(luò)［5］、支持向量機(jī)［6］、k 近鄰（k-Nearest Neighbor，KNN）算法［7］等。這些已有的分類(lèi)算法及其改進(jìn)算法被廣泛地應(yīng)用于各個(gè)領(lǐng)域，如統(tǒng)計(jì)學(xué)［8］、醫(yī)學(xué)［9］、模式識(shí)別［10］、決策理論［11］等。KNN 算法的基本思想［12］是通過(guò)已知類(lèi)別的訓(xùn)練樣本尋找待測(cè)樣本的k個(gè)近鄰，將k個(gè)近鄰中出現(xiàn)頻率最高的類(lèi)別作為待測(cè)樣本的類(lèi)別。由于KNN 算法具有理論簡(jiǎn)單、易于操作等優(yōu)點(diǎn)，被認(rèn)為是數(shù)據(jù)挖掘中最簡(jiǎn)單的方法之一［13］。但是，KNN 算法也存在不足：第1 個(gè)問(wèn)題是它沒(méi)有考慮樣本的分布，當(dāng)樣本分布不均勻或樣本中存在噪聲樣本時(shí)，分類(lèi)精度會(huì)明顯下降；第2 個(gè)問(wèn)題是所有訓(xùn)練樣本具有同等重要性，判斷待分類(lèi)樣本的類(lèi)別時(shí)沒(méi)有考慮k個(gè)近鄰的區(qū)別；第3 個(gè)問(wèn)題是使用單一的多數(shù)投票原則進(jìn)行分類(lèi)決策。以上3 個(gè)問(wèn)題都會(huì)影響分類(lèi)的準(zhǔn)確率及效率。

針對(duì)KNN 算法存在的問(wèn)題，很多研究者提出了不同的改進(jìn)算法。文獻(xiàn)［14］提出了k 近質(zhì)心近鄰（k-Nearest Centroid Neighbor，KNCN）算法，該算法的設(shè)計(jì)思想是近鄰點(diǎn)要盡可能地離待分類(lèi)樣本近，而且近鄰點(diǎn)要均勻地分布在待分類(lèi)樣本周?chē)?，通過(guò)這些近鄰點(diǎn)所屬類(lèi)別判斷待測(cè)樣本的類(lèi)別。文獻(xiàn)［15］提出了一種基于局部權(quán)重的k 近質(zhì)心近鄰算法LMKNCN，該算法的設(shè)計(jì)思想是為k個(gè)近質(zhì)心近鄰賦予不同的權(quán)重，再通過(guò)決策函數(shù)對(duì)每個(gè)測(cè)試樣本進(jìn)行分類(lèi)。文獻(xiàn)［16］將模糊理論與KNN 相結(jié)合，提出了模糊k 近鄰（Fuzzy k-Nearest Neighbor，F(xiàn)KNN）算法，該算法的基本思想是為訓(xùn)練樣本分配隸屬度，根據(jù)k個(gè)近鄰樣本的隸屬度和距離的權(quán)重，通過(guò)最大隸屬度原則確定待分類(lèi)樣本的類(lèi)別。文獻(xiàn)［17］提出了自適應(yīng)k值的FKNN 算法，該算法的設(shè)計(jì)思想是通過(guò)改進(jìn)的粒子群算法自適應(yīng)優(yōu)化k值和模糊強(qiáng)度參數(shù)m，從而提高算法性能。文獻(xiàn)［18］將KNCN 算法和FKNN 算法相結(jié)合，提出了模糊k 近質(zhì)心近鄰（Fuzzy KNCN，F(xiàn)KNCN）算法，該算法的設(shè)計(jì)思想是使用近質(zhì)心近鄰的概念來(lái)確定最近鄰，并使用模糊理論為每個(gè)類(lèi)分配隸屬度，同時(shí)解決了樣本分布和權(quán)重問(wèn)題。文獻(xiàn)［19］提出了基于Bonferroni 均值的FKNCN 算法，該算法的設(shè)計(jì)思想是運(yùn)用均值算子和近質(zhì)心近鄰概念，計(jì)算最近的局部Bonferroni 均值向量確定待分類(lèi)樣本的類(lèi)別標(biāo)簽，該算法對(duì)異常值具有很好的魯棒性。

然而，上述FKNCN 算法及其改進(jìn)算法在計(jì)算訓(xùn)練樣本的隸屬度時(shí)沒(méi)有考慮訓(xùn)練樣本中存在的噪聲點(diǎn)或離群點(diǎn)，這在小樣本數(shù)據(jù)集中會(huì)大幅降低分類(lèi)精度。同時(shí)，算法忽略了訓(xùn)練樣本特征的差異性，沒(méi)有進(jìn)行特征選擇，影響了分類(lèi)性能。針對(duì)這2 個(gè)問(wèn)題，本文對(duì)FKNCN 算法進(jìn)行改進(jìn)，提出基于隸屬度的模糊加權(quán)k 近質(zhì)心近鄰算法MRFKNCN。設(shè)計(jì)新的隸屬度函數(shù)計(jì)算訓(xùn)練樣本的隸屬度，區(qū)分訓(xùn)練樣本中存在的噪聲或離群樣本與有效樣本。在此基礎(chǔ)上，通過(guò)基于冗余分析的Relief-F 算法計(jì)算每個(gè)特征的權(quán)重，刪去較小權(quán)重所對(duì)應(yīng)的特征和冗余特征，選出重要特征后根據(jù)加權(quán)歐氏距離選取k個(gè)有代表性的近質(zhì)心近鄰，并確定待測(cè)樣本的類(lèi)標(biāo)號(hào)。

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明

本文算法所使用的符號(hào)說(shuō)明見(jiàn)表1。

表1 符號(hào)說(shuō)明Table 1 Symbol description

1.2 FKNCN 算法

假定在p維特征空間中，訓(xùn)練樣本集T=有M個(gè)類(lèi)標(biāo)簽c1,c2,…,cM，給定一個(gè)待測(cè)樣本點(diǎn)y，F(xiàn)KNCN 算法步驟如下：

步驟1利用式（1）計(jì)算待測(cè)樣本y與所有訓(xùn)練樣本間的歐氏距離，進(jìn)行升序排列，選擇最短距離所對(duì)應(yīng)的訓(xùn)練樣本作為第1 個(gè)近質(zhì)心近鄰點(diǎn)

步驟2當(dāng)r=2,3,…,k時(shí)，利用式（2）計(jì)算T（iTi表示除去被選為近質(zhì)心近鄰的訓(xùn)練樣本之外所有剩余的訓(xùn)練樣本）中的訓(xùn)練樣本與之前所選的r-1 個(gè)近質(zhì)心近鄰的質(zhì)心：

步驟3利用式（3）計(jì)算訓(xùn)練樣本的質(zhì)心與待測(cè)樣本間的最短距離，選取所對(duì)應(yīng)的訓(xùn)練樣本作為第r個(gè)近質(zhì)心近鄰：

利用式（5）和式（6）均可計(jì)算訓(xùn)練樣本的隸屬度。一般而言，優(yōu)先選擇式（6）計(jì)算其隸屬度［18］，原因在于該計(jì)算方式引入了模糊理論，將訓(xùn)練樣本的隸屬度模糊化，通過(guò)訓(xùn)練樣本的k個(gè)近鄰確定其隸屬度，能夠確保訓(xùn)練樣本在自己的類(lèi)中被賦予較高的權(quán)重，而在其他類(lèi)中被賦予較低的權(quán)重。

步驟5通過(guò)最大的模糊隸屬度值判斷待測(cè)樣本y的所屬類(lèi)別，如式（7）所示：

步驟6對(duì)于一個(gè)新的待測(cè)樣本點(diǎn)，重復(fù)步驟1～步驟5。

1.3 特征的相關(guān)性度量

定義1皮爾遜相關(guān)系數(shù)［20］

設(shè)p維空間中的2 個(gè)樣本點(diǎn)e=(e1,e2,…,ep)，f=(f1,f2,…,fp)，兩者之間的皮爾遜相關(guān)系數(shù)的計(jì)算公式如式（8）所示：

ref表示特征之間的線性相關(guān)性，其取值范圍是[-1,1]，即0 ≤|ref| ≤1，相關(guān)系數(shù)的絕對(duì)值越大，相關(guān)性越強(qiáng)，相關(guān)系數(shù)的絕對(duì)值越接近于0，相關(guān)度越弱。

2 MRFKNCN 算法

隸屬度函數(shù)的設(shè)計(jì)是FKNCN 算法的關(guān)鍵，但FKNCN 算法在計(jì)算訓(xùn)練樣本的隸屬度時(shí)，并沒(méi)有考慮噪聲點(diǎn)或離群點(diǎn)對(duì)分類(lèi)的影響，同時(shí)該算法在計(jì)算待測(cè)樣本與訓(xùn)練樣本間的歐氏距離時(shí)，把所有訓(xùn)練樣本的各維特征等同對(duì)待，沒(méi)有區(qū)分它們的重要程度，這些都會(huì)影響分類(lèi)的性能。為此，本文提出基于隸屬度的模糊加權(quán)k 近質(zhì)心近鄰算法MRFKNCN。通過(guò)密度聚類(lèi)思想為訓(xùn)練樣本設(shè)計(jì)新的隸屬度函數(shù)、利用基于冗余分析的Relief-F 算法計(jì)算特征的權(quán)重、確定待測(cè)樣本的類(lèi)別這3 個(gè)部分克服噪聲點(diǎn)、離群點(diǎn)的影響，同時(shí)解決相同特征權(quán)重的問(wèn)題，提高分類(lèi)的效率和準(zhǔn)確率。

2.1 隸屬度函數(shù)構(gòu)造

樣本集中經(jīng)常會(huì)出現(xiàn)噪聲點(diǎn)或離群點(diǎn)，而FKNCN算法在計(jì)算訓(xùn)練樣本的隸屬度時(shí)，沒(méi)有區(qū)分這些樣本與有效樣本，導(dǎo)致所有訓(xùn)練樣本的隸屬度相同，這會(huì)在很大程度上影響分類(lèi)的準(zhǔn)確率。本文采用密度聚類(lèi)的思想構(gòu)造最小包圍球。首先計(jì)算最小包圍球的類(lèi)中心和半徑；然后根據(jù)訓(xùn)練樣本在最小包圍球的位置確定其隸屬度；最后根據(jù)隸屬度的大小判斷訓(xùn)練樣本是離群或噪聲樣本還是有效樣本。計(jì)算最小包圍球類(lèi)中心和半徑的具體步驟如下：

步驟1計(jì)算訓(xùn)練樣本xj與訓(xùn)練樣本集中其他樣本的歐氏距離，找到xj的第r個(gè)近鄰(xjr,r=1,2,…,k)。

步驟2根據(jù)樣本xj的k個(gè)近鄰構(gòu)造n×k的密度矩陣D=(d(xj,xjr))n×k。

步驟3利用式（9）計(jì)算所有樣本的密度ρ(xj)：

步驟4選擇最大密度樣本點(diǎn)xmax，并找出離該點(diǎn)最近的樣本點(diǎn)xn_max，通過(guò)這2 個(gè)點(diǎn)確定最小包圍球的類(lèi)中心O(T)：

步驟5利用式（10）計(jì)算最小包圍球的半徑：

其中：λ為自定義的懲罰因子；δ為半徑調(diào)整系數(shù)；a(T)為類(lèi)中心到所有樣本點(diǎn)距離的平均值。

計(jì)算出樣本集中最小包圍球的類(lèi)中心和半徑后，利用式（12）確定訓(xùn)練樣本的隸屬度：

其中：d(xj)為訓(xùn)練樣本xj與最小包圍球類(lèi)中心O(T)的歐氏距離。從式（12）可以看出，訓(xùn)練樣本離最小包圍球的類(lèi)中心越遠(yuǎn)，該訓(xùn)練樣本的隸屬度就越小。如果訓(xùn)練樣本位于最小包圍球之內(nèi)，其隸屬度都大于0.3；反之，位于最小包圍球之外的訓(xùn)練樣本，其隸屬度都小于等于0.3。位于最小包圍球之外的樣本一般都為離群或噪聲樣本。本文構(gòu)造最小包圍球方法簡(jiǎn)單有效，原因在于其只需計(jì)算最小包圍球的類(lèi)中心和半徑，再通過(guò)式（12）為離群或噪聲樣本賦予較小的隸屬度，即可快速區(qū)分出離群或噪聲樣本與有效樣本。

2.2 基于冗余分析的Relief-F 算法

本節(jié)提出基于冗余分析的Relief-F 特征選擇算法計(jì)算每個(gè)特征的權(quán)重。首先將FKNCN 算法中的歐氏距離改為特征加權(quán)的歐氏距離；然后通過(guò)加權(quán)歐氏距離確定待測(cè)樣本的近質(zhì)心近鄰；最后通過(guò)近質(zhì)心近鄰的隸屬度和距離加權(quán)確定待測(cè)樣本的類(lèi)隸屬度。

2.2.1 特征權(quán)重的計(jì)算

在分類(lèi)過(guò)程中，并不是所有的特征都與分類(lèi)強(qiáng)相關(guān)，也會(huì)存在一些不相關(guān)特征及冗余特征。如果在分類(lèi)時(shí)不處理這些特征，會(huì)出現(xiàn)計(jì)算成本高、分類(lèi)性能低等問(wèn)題。為了得到最優(yōu)特征子集，特征選擇是必不可少的。Relief-F 算法［21］是最成功的特征選擇方法之一，算法的具體步驟如下：

1）對(duì)所有特征歸一化處理：

2）從訓(xùn)練集中隨機(jī)選擇樣本點(diǎn)xj，找出xj同類(lèi)的k個(gè)最近鄰樣本集和不同類(lèi)的k個(gè)樣本集。

3）通過(guò)式（14）計(jì)算每個(gè)特征的特征權(quán)重［22］：

其中：diff(Al,xj,Hr)表示樣本xj與Hr在第l個(gè)特征上的距離；diff(Al,xj,Mr(c))表示樣本xj與Mr(c) 在第l個(gè)特征上的距離；p(c)表示屬于類(lèi)別c的樣本出現(xiàn)的概率。

雖然Relief-F 算法在處理多分類(lèi)問(wèn)題時(shí)效率高并且能夠很好地剔除不相關(guān)特征，但不能過(guò)濾冗余特征。為此，本文在Relief-F 算法的基礎(chǔ)上提出基于冗余分析的Relief-F 特征選擇算法計(jì)算所有特征的權(quán)重，算法描述如下：

算法1基于冗余分析的Relief-F 算法

輸入訓(xùn)練集T，樣本抽樣次數(shù)α，最近鄰樣本個(gè)數(shù)k

輸出每個(gè)特征的特征權(quán)重w

步驟1所有特征歸一化處理。

步驟2將所有特征權(quán)重置0。

步驟3在T中隨機(jī)選擇樣本點(diǎn)xj。

步驟4找到與xj同類(lèi)的k個(gè)最近鄰樣本集Hr。

步驟5每個(gè)類(lèi)c≠class(xj)，找到與xj不同類(lèi)的k個(gè)最近鄰樣本集Mr(c)。

步驟6更新每個(gè)特征的特征權(quán)重。

步驟7根據(jù)特征權(quán)重閾值，選擇分類(lèi)權(quán)重最大的特征集合。

步驟8冗余分析。利用皮爾森相關(guān)系數(shù)計(jì)算特征之間的相關(guān)性。

以上步驟是在一次抽樣下計(jì)算每個(gè)特征的特征權(quán)重，經(jīng)過(guò)α次抽樣后，將特征權(quán)重更新α次，并設(shè)置一個(gè)特征權(quán)重閾值Γ，將每個(gè)特征權(quán)重與總特征權(quán)重的比值累積，選擇累積特征權(quán)重比大于閾值Γ的特征作為新特征，并刪掉剩余的不相關(guān)特征，然后分析新特征之間的相關(guān)性，在特征相關(guān)性較大的情況下保留權(quán)重較高的特征，消除權(quán)重較低的特征，目的是消除冗余特征的干擾。通過(guò)基于冗余分析的Relief-F 算法計(jì)算特征權(quán)重，同時(shí)減少特征的數(shù)量、降低維數(shù)，從而完成特征選擇。

2.2.2 加權(quán)歐氏距離的計(jì)算

利用式（15）計(jì)算待測(cè)樣本y與訓(xùn)練樣本xj的加權(quán)歐氏距離，從而確定待測(cè)樣本的k個(gè)近質(zhì)心近鄰：

2.2.3 待分類(lèi)樣本類(lèi)別的確定

計(jì)算出每個(gè)特征的特征權(quán)重后，利用式（16）計(jì)算待測(cè)樣本y屬于每個(gè)類(lèi)別的隸屬度值：

得到待測(cè)樣本y屬于每個(gè)類(lèi)別的隸屬度后，通過(guò)最大隸屬度原則確定待測(cè)樣本y的類(lèi)別。

2.3 算法描述

MRFKNCN 算法的設(shè)計(jì)思想為：首先計(jì)算訓(xùn)練樣本的隸屬度；然后計(jì)算所有特征的權(quán)重，并找出k個(gè)近質(zhì)心近鄰；最后計(jì)算待測(cè)樣本的模糊隸屬度，通過(guò)最大隸屬度原則確定待測(cè)樣本的類(lèi)別。具體步驟如算法2 所示，算法流程如圖1 所示。

圖1 MRFKNCN 算法流程Fig.1 Procedure of MRFKNCN algorithm

算法2MRFKNCN 算法

輸入近質(zhì)心近鄰個(gè)數(shù)k，待測(cè)樣本點(diǎn)y，訓(xùn)練樣本集T，模糊強(qiáng)度參數(shù)m

輸出待測(cè)試樣本y的類(lèi)別

步驟1利用式（9）計(jì)算訓(xùn)練樣本的密度。

步驟2利用式（10）和式（11）計(jì)算最小包圍球的類(lèi)中心和半徑。

步驟3利用式（12）計(jì)算訓(xùn)練樣本隸屬度。

步驟4通過(guò)基于冗余分析的Relief-F 算法計(jì)算所有特征的權(quán)重。

步驟5利用式（15）計(jì)算待測(cè)樣本與訓(xùn)練樣本之間的加權(quán)歐氏距離，找出k個(gè)近質(zhì)心近鄰集合。

步驟6利用式（16）計(jì)算待測(cè)樣本的模糊隸屬度。

步驟7根據(jù)最大隸屬度原則確定待分類(lèi)樣本的類(lèi)別。

2.4 算法復(fù)雜度分析

假設(shè)n表示數(shù)據(jù)集的規(guī)模，p表示特征維數(shù)，k表示近鄰個(gè)數(shù)，M表示類(lèi)別個(gè)數(shù)?；陔`屬度的模糊k 近質(zhì)心近鄰算法的時(shí)間復(fù)雜度主要來(lái)源于以下5 個(gè)部分：1）通過(guò)密度聚類(lèi)思想計(jì)算訓(xùn)練樣本的隸屬度，時(shí)間復(fù)雜度為O(np)；2）計(jì)算每個(gè)特征的特征權(quán)重，時(shí)間復(fù)雜度為O(npμ)；3）計(jì)算訓(xùn)練樣本的質(zhì)心，時(shí)間復(fù)雜度為O(nk)；4）待測(cè)樣本到各個(gè)類(lèi)的加權(quán)距離，時(shí)間復(fù)雜度為O(np)；5）通過(guò)最大隸屬度原則確定待測(cè)樣本的類(lèi)別，時(shí)間復(fù)雜度為O(M)。因此，MRFKNCN 算法總的時(shí)間復(fù)雜度為O(2np+nk)。

3 仿真實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集

為驗(yàn)證本文MRFKNCN 算法的有效性，選用UCI 和KEEL 中的11 個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集和4 個(gè)含噪數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，所有實(shí)驗(yàn)都在Matlab2014b 的環(huán)境下完成。表2、表3 列出了實(shí)驗(yàn)中所用數(shù)據(jù)集的相關(guān)信息。

表2 標(biāo)準(zhǔn)數(shù)據(jù)集Table 2 Standard data sets

表3 含噪數(shù)據(jù)集Table 3 Datas sets with noise

3.2 算法參數(shù)設(shè)置

為了更好地測(cè)試各算法的分類(lèi)效果，對(duì)本文算法所使用的相關(guān)參數(shù)進(jìn)行調(diào)優(yōu)。

參考文獻(xiàn)［23］，取λ=2，δ=0.14 計(jì)算最小包圍球的半徑。計(jì)算完特征權(quán)重后，需要設(shè)置一個(gè)閾值Γ?(0,1)［22］。對(duì)本文的數(shù)據(jù)集進(jìn)行多次試驗(yàn)可知，當(dāng)Γ=0.8 時(shí)，選出的新特征最具有代表性，模糊強(qiáng)度參數(shù)m=2，當(dāng)模糊隸屬度值與距離平方成反比時(shí)，在分類(lèi)過(guò)程中會(huì)得到最優(yōu)結(jié)果［18］。

3.3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)設(shè)計(jì)了4 個(gè)實(shí)驗(yàn)來(lái)驗(yàn)證MRFKNCN 算法的有效性，將分類(lèi)的準(zhǔn)確率作為評(píng)價(jià)標(biāo)準(zhǔn)，比較本文算法與其他算法的性能。準(zhǔn)確率的計(jì)算方法如下：

其中：Nc為正確分類(lèi)的樣本個(gè)數(shù)；Nt為實(shí)際分類(lèi)的樣本個(gè)數(shù)。

對(duì)于樣本總數(shù)較小的數(shù)據(jù)集，通過(guò)10 次5 折交叉驗(yàn)證進(jìn)行實(shí)驗(yàn)；對(duì)于樣本總數(shù)大的數(shù)據(jù)集，通過(guò)10 次10 折交叉驗(yàn)證進(jìn)行實(shí)驗(yàn)，最后將所有實(shí)驗(yàn)得到的準(zhǔn)確率平均值作為測(cè)試結(jié)果。實(shí)驗(yàn)1～實(shí)驗(yàn)3 均采用交叉驗(yàn)證法確定最優(yōu)k值。

3.3.1 MRFKNCN 算法總體性能分析

實(shí)驗(yàn)1為驗(yàn)證本文所提的新的隸屬度函數(shù)在噪聲點(diǎn)或離群點(diǎn)影響下的有效性，將MRFKNCN 算法與利用式（5）計(jì)算隸屬度的FKNCN算法（命名為FKNCN1）及利用式（6）計(jì)算隸屬度的FKNCN 算法（命名為FKNCN2）進(jìn)行比較，運(yùn)用表3 含噪數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果如表4 所示。

表4 MRFKNCN 與FKNCN 算法的平均準(zhǔn)確率Table 4 Average accuracy of MRFKNCN and FKNCN algorithms %

表4 結(jié)果表明，當(dāng)訓(xùn)練集中含有噪聲點(diǎn)或離群點(diǎn)時(shí)，MRFKNCN 算法的平均準(zhǔn)確率明顯高于FKNCN1算法和FKNCN2 算法，在Iris、Vehicle、Wine、Letter 這4 個(gè)含噪數(shù)據(jù)集上，MRFKNCN 算法的平均準(zhǔn)確率比FKNCN1 算法分別提高4.48、3.16、3.64、2.86個(gè)百分點(diǎn)，比FKNCN2算法分別提高3.26、3.92、2.69、2.33 個(gè)百分點(diǎn)，這表明本文所設(shè)計(jì)的新隸屬度函數(shù)可以很好地識(shí)別出訓(xùn)練樣本集中的噪聲點(diǎn)或離群點(diǎn)，尤其是在Iris 小數(shù)據(jù)集中，MRFKNCN 算法獲得了較高的準(zhǔn)確率。

實(shí)驗(yàn)2為驗(yàn)證基于冗余分析的Relief-F 算法計(jì)算特征權(quán)重方法的有效性，將MRFKNCN 算法與未加權(quán)歐氏距離的MRFKNCN 算法（命名為MRFKNCN_N）、確定統(tǒng)一特征權(quán)重的MRFKNCN 算法（命名為MRFKNCN_U）進(jìn)行對(duì) 比，運(yùn)用 表3 中Arrhythmia、Segment、Zoo、Balance、Thyroid 這5 個(gè)數(shù)據(jù)集，3 種算法的平均準(zhǔn)確率結(jié)果如圖2 所示。

圖2 3 種算法平均準(zhǔn)確率對(duì)比Fig.2 Comparison of average accuracy of three algorithms

圖2 結(jié)果表明，5 個(gè)數(shù)據(jù)集中MRFKNCN 的分類(lèi)準(zhǔn)確率都明顯優(yōu)于MRFKNCN_N 算法和MRFKNCN_U算法，說(shuō)明不同的特征有不同的貢獻(xiàn)率。因此，為了保證算法的準(zhǔn)確率，應(yīng)分別確定每個(gè)樣本特征的權(quán)重，區(qū)分其差異，從而提高分類(lèi)的性能。

實(shí)驗(yàn)3在最優(yōu)k值下比較MRFKNCN、KNN［13］、KNCN［14］、LWKNCN［15］、FKNN［16］、FKNCN［18］和BMFKNCN［19］算法的分類(lèi)平均準(zhǔn)確率，所得結(jié)果如表5所示，其中加粗?jǐn)?shù)字為最優(yōu)值。

表5 最優(yōu)k 值下MRFKNCN 與其他6 種算法的平均準(zhǔn)確率Table 5 Average accuracy of MRFKNCN and other six algorithms under optimal k value %

表5 結(jié)果表明，雖然在Thyroid 數(shù)據(jù)集中，BMFKNCN算法取得了較高的準(zhǔn)確率，但是MRFKNCN算法的準(zhǔn)確率仍高于其他5 種對(duì)比算法。MRFKNCN算法在其余10 個(gè)數(shù)據(jù)集中的準(zhǔn)確率都高于其他6 種對(duì)比算法的準(zhǔn)確率，尤其是在Movement、Arrhythmia、Multivariate 這3 個(gè)高維數(shù)據(jù)集上的準(zhǔn)確率大幅提升，說(shuō)明MRFKNCN 算法不僅可以去除噪聲樣本對(duì)分類(lèi)性能的影響，還可以選出有代表性的特征提高分類(lèi)的準(zhǔn)確率。同時(shí)，MRFKNCN 算法在11 個(gè)數(shù)據(jù)集中獲得了最高的平均準(zhǔn)確率。

3.3.2 MRFKNCN 算法在不同k值下的性能分析

實(shí)驗(yàn)4為了驗(yàn)證MRFKNCN 算法在不同k值下的分類(lèi)性能，將MRFKNCN 算法與6 個(gè)對(duì)比算法在k=1～15時(shí)進(jìn)行比較。運(yùn)用表3的Hayes-roth、Ecoli、Glass、Sends、Cleveland 這5 個(gè)數(shù)據(jù)集。圖3～圖7 給出了7 種算法的分類(lèi)準(zhǔn)確率對(duì)比折線圖。

圖3 在Hayes-roth 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.3 Experimental results on the Hayes-roth dataset

圖4 在Ecoli 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.4 Experimental results on the Ecoli dataset

圖5 在Glass 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.5 Experimental results on the Glass dataset

圖6 在Sends 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.6 Experimental results on the Sends dataset

圖7 在Movement 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Fig.7 Experimental results on the Movement dataset

4 結(jié)束語(yǔ)

針對(duì)FKNCN 算法未區(qū)別樣本特征的不足，本文提出基于隸屬度的模糊加權(quán)k 近質(zhì)心近鄰算法MRFKNCN。利用密度聚類(lèi)思想設(shè)計(jì)新的隸屬度函數(shù)計(jì)算訓(xùn)練樣本的隸屬度，通過(guò)基于冗余分析的Relief-F 算法計(jì)算每個(gè)特征的權(quán)重，刪去不相關(guān)特征和冗余特征，選出重要的特征，并利用加權(quán)歐氏距離選取k個(gè)近質(zhì)心近鄰，最終根據(jù)最大隸屬度原則對(duì)待測(cè)樣本進(jìn)行分類(lèi)。該算法有效解決了訓(xùn)練樣本中存在噪聲樣本或離群樣本的問(wèn)題，而且還為每個(gè)特征賦予不同的權(quán)重，更符合分類(lèi)的實(shí)際情況。實(shí)驗(yàn)結(jié)果表明，MRFKNCN 算法在分類(lèi)性能上明顯優(yōu)于其他對(duì)比算法。由于FKNCN 算法對(duì)參數(shù)k和模糊強(qiáng)度因子m敏感也會(huì)影響分類(lèi)性能，因此下一步將研究如何自適應(yīng)地優(yōu)化FKNCN 算法的參數(shù)k和模糊強(qiáng)度因子m，進(jìn)一步提高算法準(zhǔn)確率。