基于隸屬度的模糊加權(quán)k 近質(zhì)心近鄰算法

劉利，張德生，肖燕婷

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

0 概述

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

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

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

1 預(yù)備知識

1.1 符號說明

本文算法所使用的符號說明見表1。

表1 符號說明Table 1 Symbol description

1.2 FKNCN 算法

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

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

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

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

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

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

步驟6對于一個新的待測樣本點，重復(fù)步驟1～步驟5。

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

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

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

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

2 MRFKNCN 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）對所有特征歸一化處理：

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

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

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

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

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

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

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

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

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

步驟3在T中隨機選擇樣本點xj。

步驟4找到與xj同類的k個最近鄰樣本集Hr。

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

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

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

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

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

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

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

2.2.3 待分類樣本類別的確定

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

得到待測樣本y屬于每個類別的隸屬度后，通過最大隸屬度原則確定待測樣本y的類別。

2.3 算法描述

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

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

算法2MRFKNCN 算法

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

輸出待測試樣本y的類別

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

步驟2利用式（10）和式（11）計算最小包圍球的類中心和半徑。

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

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

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

步驟6利用式（16）計算待測樣本的模糊隸屬度。

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

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

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

3 仿真實驗與分析

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

為驗證本文MRFKNCN 算法的有效性，選用UCI 和KEEL 中的11 個標(biāo)準(zhǔn)數(shù)據(jù)集和4 個含噪數(shù)據(jù)集進行仿真實驗，所有實驗都在Matlab2014b 的環(huán)境下完成。表2、表3 列出了實驗中所用數(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è)置

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

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

3.3 實驗結(jié)果與分析

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

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

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

3.3.1 MRFKNCN 算法總體性能分析

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

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

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

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

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

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

實驗3在最優(yōu)k值下比較MRFKNCN、KNN［13］、KNCN［14］、LWKNCN［15］、FKNN［16］、FKNCN［18］和BMFKNCN［19］算法的分類平均準(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 種對比算法。MRFKNCN算法在其余10 個數(shù)據(jù)集中的準(zhǔn)確率都高于其他6 種對比算法的準(zhǔn)確率，尤其是在Movement、Arrhythmia、Multivariate 這3 個高維數(shù)據(jù)集上的準(zhǔn)確率大幅提升，說明MRFKNCN 算法不僅可以去除噪聲樣本對分類性能的影響，還可以選出有代表性的特征提高分類的準(zhǔn)確率。同時，MRFKNCN 算法在11 個數(shù)據(jù)集中獲得了最高的平均準(zhǔn)確率。

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

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

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

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

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

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

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

4 結(jié)束語

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