基于影響函數(shù)的k-近鄰分類

職為梅 張 婷 范 明

（鄭州大學(xué)信息工程學(xué)院 鄭州 450052）

基于影響函數(shù)的k-近鄰分類

職為梅*張 婷 范 明

（鄭州大學(xué)信息工程學(xué)院 鄭州 450052）

分類是一種監(jiān)督學(xué)習(xí)方法，通過(guò)在訓(xùn)練數(shù)據(jù)集學(xué)習(xí)模型判定未知樣本的類標(biāo)號(hào)。與傳統(tǒng)的分類思想不同，該文從影響函數(shù)的角度理解分類，即從訓(xùn)練樣本集對(duì)未知樣本的影響來(lái)判定未知樣本的類標(biāo)號(hào)。首先介紹基于影響函數(shù)分類的思想；其次給出影響函數(shù)的定義，設(shè)計(jì)3種影響函數(shù)；最后基于這3種影響函數(shù)，提出基于影響函數(shù)的k-近鄰（kNN）分類方法。并將該方法應(yīng)用到非平衡數(shù)據(jù)集分類中。在18個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，基于影響函數(shù)的k-近鄰分類方法的分類性能好于傳統(tǒng)的k-近鄰分類方法，且對(duì)非平衡數(shù)據(jù)集分類有效。

數(shù)據(jù)挖掘；監(jiān)督學(xué)習(xí)；非平衡數(shù)據(jù)集分類；影響函數(shù)；k-近鄰

1 引言

分類是一種監(jiān)督學(xué)習(xí)方法［1］，已有的研究提出很多經(jīng)典的分類方法，例如，決策樹(shù)歸納［2］、樸素貝葉斯法［3］、神經(jīng)網(wǎng)絡(luò)［4］、支持向量機(jī)［5］、k-近鄰（k-Nearest Neighbor，kNN）［6］、基于案例的推理［7］等。這些分類方法的做法相似，即，給定一個(gè)訓(xùn)練集 D，學(xué)習(xí)一個(gè)模型M，對(duì)于未知樣本x，由M給出x的類標(biāo)號(hào)。如果沒(méi)有類標(biāo)號(hào)已知的樣本和其他先驗(yàn)知識(shí)，則除了隨機(jī)猜測(cè)之外，沒(méi)有更好的方法確定x的類標(biāo)號(hào)。如果沒(méi)有類標(biāo)號(hào)已知的樣本，但有某種先驗(yàn)知識(shí)，例如知道每個(gè)類出現(xiàn)的概率，則推斷x屬于出現(xiàn)概率最大的類的出錯(cuò)可能性更小。換句話說(shuō)，利用先驗(yàn)知識(shí)推斷勝過(guò)隨機(jī)猜測(cè)。如果有已知類標(biāo)號(hào)的訓(xùn)練樣本集D，則可以在D上訓(xùn)練一個(gè)分類模型M（如決策樹(shù)歸納、樸素貝葉斯、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等）并用M對(duì)x分類，或者保留D并直接利用D推斷x所屬的類（如k -近鄰、基于案例的推理等）。借助于訓(xùn)練樣本集，合理的分類算法遠(yuǎn)比隨機(jī)猜測(cè)和僅利用簡(jiǎn)單的先驗(yàn)知識(shí)好得多。

一般的分類算法都是基于訓(xùn)練數(shù)據(jù)集學(xué)習(xí)得到分類器分類未知樣本，因此它們都受到訓(xùn)練數(shù)據(jù)集的影響。假設(shè)訓(xùn)練集為空集，不管一個(gè)分類算法多么優(yōu)秀，對(duì)于未知樣本，也只能采用隨機(jī)猜測(cè)的方法分類未知樣本；如果訓(xùn)練集無(wú)限大，包含了所有可能的實(shí)例，不管一個(gè)分類算法多么糟糕，分類準(zhǔn)確率很容易達(dá)到百分之百；如果訓(xùn)練集D非空也沒(méi)有包含所有的樣本，那么分類算法基于訓(xùn)練集學(xué)習(xí)分類器分類未知樣本。基于此，可以換個(gè)角度理解分類，即分類的過(guò)程也就是考察訓(xùn)練樣本對(duì)未知樣本x的影響。訓(xùn)練集為空，D對(duì)x的影響為0，只能隨機(jī)猜測(cè)未知樣本的類標(biāo)號(hào)；訓(xùn)練集無(wú)限大，一定存在某一個(gè)類對(duì)x的影響為1，這個(gè)類的標(biāo)號(hào)即為x的類標(biāo)號(hào)；如果訓(xùn)練集為有限集合，假設(shè)D只包含了兩個(gè)類C1和C2，如果C1類所有訓(xùn)練樣本對(duì)x的影響大于C2類樣本對(duì)x的影響，則x的類標(biāo)號(hào)就為C1類。反之亦然。

基于以上分析，和傳統(tǒng)的分類方法不同，從另一個(gè)角度看待分類問(wèn)題，即，從訓(xùn)練數(shù)據(jù)集對(duì)未知樣本的影響［8］角度出發(fā)看待分類。本文從新的角度闡述分類，提出基于影響函數(shù)的分類思想，也即，每個(gè)訓(xùn)練實(shí)例都對(duì)未知樣本有一定的影響，綜合所有訓(xùn)練樣本對(duì)未知樣本的影響，即可判定未知樣本的類標(biāo)號(hào)。嚴(yán)格地說(shuō)，基于影響函數(shù)的分類不是一種分類算法，而是一種分類范型。定義不同的影響函數(shù)導(dǎo)致不同的分類算法。本文給出了3種影響函數(shù)的定義，基于這3種影響函數(shù)，提出了基于影響函數(shù)的k-近鄰分類方法，UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，相對(duì)于普通的k-近鄰分類方法，該方法可以提高分類的性能。

論文剩余部分組織如下：第2節(jié)介紹影響函數(shù)的定義，設(shè)計(jì)3種影響函數(shù)，并提出基于影響函數(shù)的k-近鄰分類；第3節(jié)給出實(shí)驗(yàn)結(jié)果及相關(guān)評(píng)述；第4節(jié)給出基于影響函數(shù)的k-近鄰分類方法在非平衡數(shù)據(jù)集上的分類效果；第5節(jié)總結(jié)全文。

2 基于影響函數(shù)的k-近鄰分類

設(shè)訓(xùn)練數(shù)據(jù)集D包含L個(gè)類C1，C2，…，CL，Dl為第l類訓(xùn)練樣本的集合，x為待分類實(shí)例。基于影響函數(shù)分類的基本思想是：定義 L個(gè)實(shí)型函數(shù)fl（x），l= 1，2，…， L。其中，fl（x）計(jì)算Dl中樣本對(duì)x的影響。將待分類實(shí)例x分配到對(duì)x影響最大的類：如果，則把x分配到Cj類。

當(dāng)只有兩個(gè)類（L = 2）時(shí)，問(wèn)題可以簡(jiǎn)化為：定義一個(gè)實(shí)型影響函數(shù)f（x）=f1（x）-f2（x），計(jì)算D中樣本對(duì)x的影響。如果 f（ x ）≥ 0，則把x分配到C1類，否則把x分配到C2類。

k-近鄰分類是一個(gè)經(jīng)典的分類方法［6］，從影響函數(shù)的角度更容易理解k-近鄰分類?？紤]未知樣本x的某個(gè)領(lǐng)域，比如距離它最近的k個(gè)近鄰，定義影響函數(shù)，計(jì)算這k個(gè)近鄰對(duì)x的影響，將x劃歸為對(duì)它影響最大的那個(gè)類。下面就通過(guò)定義不同的影響函數(shù)，分析基于影響函數(shù)的k-近鄰分類方法的性能。

2.1 影響函數(shù)的定義

影響函數(shù)的定義范圍可以是全局的，也可以是局部的［8］。全局影響函數(shù)指每個(gè)訓(xùn)練實(shí)例都對(duì) x有影響；局部影響函數(shù)指只有x的那些近鄰才對(duì)x有影響。全局影響函數(shù)也很容易變換成局部影響函數(shù)，下面以全局影響函數(shù)為例介紹影響函數(shù)的定義方法：

（1）定義單個(gè)訓(xùn)練實(shí)例 'x對(duì)x的影響g（'x，x）；

（2）數(shù)據(jù)集D對(duì)x的影響 fD（x）可以定義為數(shù)據(jù)集中訓(xùn)練實(shí)例對(duì)x的影響的加權(quán)和：

其中wi是實(shí)例 'x的權(quán)重，它反映 'x的重要性。在最簡(jiǎn)單的情況下，所有實(shí)例都取相等權(quán)重。當(dāng)數(shù)據(jù)集D為第i類訓(xùn)練樣本時(shí)，fD（x）簡(jiǎn)記為fi（x）。

訓(xùn)練實(shí)例 'x對(duì) x的影響 g（'x，x）的定義也有很多種方式，最簡(jiǎn)單的，0/1影響：如果 'x和x滿足某個(gè)謂詞，則 'x對(duì)x的影響為1，否則為0。這里，簡(jiǎn)單的“謂詞”可以是“ 'x是x的k個(gè)最近鄰之一”，“ 'x在 x的 -ε鄰域內(nèi)”。更復(fù)雜的謂詞可以是，例如，分類規(guī)則的前件。除了0/1影響外，本文還設(shè)計(jì)了3種影響：

（1）線性影響：'x對(duì)x的影響隨 'x與x的距離增加而線性減小。

其中，d（'x，x）是 'x與x之間的距離，而dmax是訓(xùn)練實(shí)例之間的最大距離。

（2）平方影響：'x對(duì)x的影響隨 'x與x的距離增加而平方減小。

（3）指數(shù)影響：'x對(duì)x的影響隨 'x與x的距離增加而指數(shù)衰減。

其中，α是一個(gè)待定常數(shù)，用于控制衰減速度。

2.2 算法描述

有了訓(xùn)練實(shí)例對(duì)未知樣本的影響函數(shù)，可以對(duì)傳統(tǒng)的k-近鄰分類方法加以改進(jìn)，得到基于影響函數(shù)的 k-近鄰分類方法，其算法的具體過(guò)程見(jiàn)表 1。首先遍歷D得到x的k個(gè)近鄰Dz，對(duì)于Dz中每個(gè)實(shí)例 'x，根據(jù)影響函數(shù)的定義，計(jì)算它對(duì)x的影響，得到Dz每個(gè)類對(duì)x的影響函數(shù)值fl（x），將x的類標(biāo)號(hào)設(shè)為fl（x）最大的那個(gè)類。

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

18個(gè)數(shù)據(jù)集從UCI機(jī)器學(xué)習(xí)庫(kù)中隨機(jī)選?。?］。對(duì)于每個(gè)數(shù)據(jù)集，采用5×2折交叉驗(yàn)證分析算法的性能。數(shù)據(jù)集的詳細(xì)情況如表2所示。所有實(shí)驗(yàn)均基于weka平臺(tái)。

表1 算法描述

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)時(shí)，本文對(duì)比了樸素貝葉斯算法［3］（Navie Bayes，NB）、支持向量機(jī)算法［5］（Support Vector Machine，SVM）、判定樹(shù)算法［2］（Decision Tree，常用的判定樹(shù)算法是 C4.5）、神經(jīng)網(wǎng)絡(luò)算法［4］（Neural Network，NN），k-近鄰分類（k-Nearest Neighbor，kNN）、基于線性影響的 k-近鄰分類（Linear Effect kNN，LE-kNN）、基于平方影響的 k-近鄰分類（Square Effect kNN，SE-kNN）和基于指數(shù)影響的k-近鄰分類（Exponential Effect kNN，EE-kNN）。kNN，LE-kNN，SE-kNN以及EE-kNN 4四個(gè)算法都存在確定k值的問(wèn)題，傳統(tǒng)的k-近鄰算法，k的值一般為3，因此在實(shí)驗(yàn)中，首先給出k值為3時(shí)，kNN，LE-kNN，SE-kNN以及EE-kNN在準(zhǔn)確率上的結(jié)果，結(jié)果如表3所示。基于影響函數(shù)的分類中，如果考慮的實(shí)例少，效果不太好，為了對(duì)比實(shí)例多少對(duì)算法性能的影響，實(shí)驗(yàn)時(shí)改變k值的大小，分別取k為10，25，50，實(shí)驗(yàn)結(jié)果分別如表4～表6所示。

由表3可以發(fā)現(xiàn)，當(dāng)k值取3的時(shí)候，神經(jīng)網(wǎng)絡(luò)的平均效果最好，支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)比kNN的效果都好。而LE-kNN，SE-kNN，EE-kNN和kNN相比，kNN的效果最好，在15個(gè)數(shù)據(jù)集上的準(zhǔn)確率值都超過(guò)了其他3三個(gè)算法，kNN在這18個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率值也最高，為80.05，LE-kNN，SE-kNN和EE-kNN的分別為73.84，73.51和79.88。這個(gè)結(jié)果不難理解，kNN算法通常取值為3，而基于影響函數(shù)的kNN算法，如果考慮的實(shí)例少時(shí)，效果不好。隨著k值的增加，基于影響函數(shù)的kNN算法性能變好。

如表4所示，當(dāng)k取值為10時(shí)，仍舊是神經(jīng)網(wǎng)絡(luò)的效果最好，但是LE-kNN和SE-kNN的平均準(zhǔn)確率有明顯提高，LE-kNN由 73.84提高到79.97，SE-kNN由73.51提高到79.46。相比于LE-kNN，SE-kNN，EE-kNN的還是性能最好，LE-kNN在這18個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率值也最高?？梢钥闯觯琇E-kNN和kNN的性能相差無(wú)幾。對(duì)比表3和表4可以發(fā)現(xiàn)，LE-kNN的性能在上升，而kNN的性能在下降。當(dāng)k取值為25時(shí)，結(jié)果如表5所示，SE-kNN的性能最好，在這18個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率值也最高，為81.67，LE-kNN，EE-kNN，kNN，NB，SVM，C4.5和 NN的分別為 81.55，76.19，77.07，75.24，80.77，78.29和81.33，很明顯LE-kNN的結(jié)果要比kNN，NB，SVM，C4.5和NN都好。對(duì)比表3，表4，表5發(fā)現(xiàn)，LE-kNN和SE-kNN的性能仍舊上升，kNN的性能仍舊下降。并且LE-kNN和SE-kNN的平均準(zhǔn)確率同時(shí)超過(guò)神經(jīng)網(wǎng)絡(luò)。當(dāng)k取值為50時(shí)，結(jié)果如表6所示，SE-kNN的性能仍舊最好，在這18個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率值也最高，為 81.54，LE-kNN，EE-kNN，kNN，NB，SVM，C4.5和NN的分別為79.91，73.81，74.33，75.24，80.77，78.29和81.33。

表2 實(shí)驗(yàn)數(shù)據(jù)集信息

表3～表6的結(jié)果表明，隨著k值的增加，LE-kNN和SE-kNN的分類準(zhǔn)確率增加，當(dāng)k值增加到一定大小時(shí)，準(zhǔn)確率的值也趨于穩(wěn)定。對(duì)于k的取值，本文做了大量的實(shí)驗(yàn)，發(fā)現(xiàn)當(dāng)k的值在20～50時(shí)，LE-kNN和SE-kNN的性能最好。達(dá)到相同的準(zhǔn)確率值時(shí)，LE-kNN比SE-kNN取的k值要小一些。同時(shí)，還發(fā)現(xiàn)了一個(gè)有趣的現(xiàn)象，在大多數(shù)數(shù)據(jù)集上，EE-kNN在k值較小時(shí)達(dá)到最優(yōu)性能，并且，EE-kNN在大多數(shù)數(shù)據(jù)集上的結(jié)果和kNN的結(jié)果相似，如表3所示。仔細(xì)觀察表3～表6可以發(fā)現(xiàn)，當(dāng)k值很小的時(shí)候，LE-kNN，SE-kNN在某些數(shù)據(jù)集上準(zhǔn)確率值很差，比如tic-tac-toe，隨著k值的增加，效果越來(lái)越好，當(dāng)k達(dá)到一個(gè)特定值后，準(zhǔn)確率值不再升高。而EE-kNN正好相反，當(dāng)k值小的時(shí)候它在tic-tac-toe上的準(zhǔn)確率值很高，隨著k值的增加，準(zhǔn)確率不升反降，這是一個(gè)有趣的現(xiàn)象。本文發(fā)現(xiàn)，在另外的一些數(shù)據(jù)集上也存在這樣的現(xiàn)象。

表3 LE-kNN，SE-kNN，EE-kNN及kNN分類準(zhǔn)確率的結(jié)果（k=3）

表4 LE-kNN，SE-kNN，EE-kNN及kNN分類準(zhǔn)確率的結(jié)果（k=10）

表5 LE-kNN，SE-kNN，EE-kNN及kNN分類準(zhǔn)確率的結(jié)果（k=25）

表6 LE-kNN，SE-kNN，EE-kNN及kNN分類準(zhǔn)確率的結(jié)果（k=50）

表3～表6的實(shí)驗(yàn)結(jié)果表明，當(dāng)影響函數(shù)設(shè)置得當(dāng)時(shí)，基于影響函數(shù)的kNN分類可以提高分類的效果，并且正如所預(yù)測(cè)的那樣，基于影響函數(shù)的kNN，需要一定數(shù)目的近鄰來(lái)計(jì)算影響函數(shù)的值，如果考慮的近鄰數(shù)目過(guò)少，效果不明顯，考慮了足夠多的近鄰時(shí)，往往可以極大提高基于影響函數(shù)的kNN的分類性能。

3.3 局部性確定

傳統(tǒng)的k-近鄰學(xué)習(xí)算法通常將其設(shè)置為3，但是基于影響函數(shù)的k-近鄰算法中，如果k的值很小，意味著影響未知樣本x的訓(xùn)練樣本少，效果非常差，應(yīng)該為k選擇一個(gè)適當(dāng)?shù)闹?。本小?jié)中，本文設(shè)計(jì)了一組實(shí)驗(yàn)，學(xué)習(xí)最佳k值，論文隨機(jī)選擇兩個(gè)數(shù)據(jù)集作為代表數(shù)據(jù)集學(xué)習(xí)最佳k值，分別是breastcancer和cleve。實(shí)驗(yàn)結(jié)果如圖1和圖2所示。

圖1和圖2分別給出 3種影響函數(shù)在 breastcancer和cleve上的結(jié)果。這兩個(gè)圖有一個(gè)共同特點(diǎn)，即線性影響和平方影響隨著k值的增加性能變好，當(dāng)k達(dá)到一定時(shí)（對(duì)于線性影響來(lái)說(shuō)通常為25，平方影響為50），準(zhǔn)確率趨于穩(wěn)定。對(duì)于指數(shù)影響來(lái)說(shuō)，隨著k值的增加性能往往下降，k值在3～10之間性能最好。對(duì)于線性影響k值取15～50，對(duì)于平方影響k值取20～50。

4 影響函數(shù)分類用于非平衡數(shù)據(jù)集

基于影響函數(shù)的k近鄰分類方法通過(guò)考察未知樣本x的近鄰對(duì)x的影響確定它的類標(biāo)號(hào)，對(duì)它影響大的樣本的類標(biāo)號(hào)就是它的類標(biāo)號(hào)，這種分類的思想也適合于非平衡數(shù)據(jù)集分類，非平衡數(shù)據(jù)集分類是數(shù)據(jù)挖掘中的一個(gè)難點(diǎn)問(wèn)題，也是數(shù)據(jù)挖掘中的一個(gè)熱點(diǎn)問(wèn)題［10-16］。為了驗(yàn)證基于影響函數(shù)的分類對(duì)非平衡數(shù)據(jù)集分類有效，本文選擇了兩個(gè)常用的非平衡數(shù)據(jù)集：breast-cancer和sick（sick數(shù)據(jù)集的不平衡程度高，故在實(shí)驗(yàn)部分沒(méi)有選擇它作為數(shù)據(jù)集），對(duì)比了kNN，LE-kNN，SE-kNN在這些數(shù)據(jù)集上的分類效果（由3.2節(jié)知EE-kNN性能和kNN相似，故在此不再對(duì)比EE-kNN），使用非平衡數(shù)據(jù)集分類常用的衡量標(biāo)準(zhǔn) f-度量、召回率來(lái)衡量分類效果的好壞，并且只給出了少數(shù)類上的 f-度量和召回率。結(jié)果如圖3和圖4所示。

Breast-cancer數(shù)據(jù)集有9個(gè)屬性，286條實(shí)例，包含復(fù)發(fā)事件（recurrence-events）和非復(fù)發(fā)事件（no-recurrence-events）兩個(gè)類，其中復(fù)發(fā)事件類為少數(shù)類，有85條實(shí)例，非復(fù)發(fā)事件類為多數(shù)類，有201條實(shí)例。由圖4可以發(fā)現(xiàn)，LE-kNN和SE-kNN在復(fù)發(fā)事件類上的召回率和 f-度量都明顯好于kNN。

sick數(shù)據(jù)集有 30個(gè)屬性，3772條實(shí)例，包含negative和sick兩個(gè)類，其中sick類為少數(shù)類，有231條實(shí)例，0類為多數(shù)類，有3541條實(shí)例。由圖4可以發(fā)現(xiàn)，LE-kNN和SE-kNN在sick類上的召回率和f-度量都明顯好于kNN，并且隨著k值的增加，這3個(gè)算法的性能都下降。

在這2個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明基于影響函數(shù)的分類方法的確對(duì)非平衡數(shù)據(jù)集分類有效。在此，本文只是簡(jiǎn)單的將LE-kNN和SE-kNN算法應(yīng)用于二元的非平衡數(shù)據(jù)集分類中（實(shí)驗(yàn)中使用的2個(gè)數(shù)據(jù)集都是二元數(shù)據(jù)集），我們工作的下一步是設(shè)計(jì)更好的影響函數(shù)，并推廣到多元的非平衡數(shù)據(jù)集分類中去。

5 總結(jié)

圖1 LE-kNN，SE-kNN，EE-kNN在breast-cancer 上的準(zhǔn)確率值

圖2 LE-kNN，SE-kNN，EE-kNN在cleve 上的準(zhǔn)確率值

圖3 kNN，LE-kNN，SE-kNN 在breast-cancer上的召回率和f-度量

圖4 kNN，LE-kNN，SE-kNN 在sick上的召回率和f-度量

本文從一個(gè)新的角度理解分類問(wèn)題，即，從訓(xùn)練數(shù)據(jù)集對(duì)未知樣本的影響角度出發(fā)看待分類。本文給出了幾種影響函數(shù)的定義方法，并將這些影響函數(shù)的定義運(yùn)用到k-近鄰算法中，介紹了基于影響函數(shù)的k-近鄰分類方法。通過(guò)實(shí)驗(yàn)對(duì)比，發(fā)現(xiàn)基于影響函數(shù)的k-近鄰分類方法的確比普通的k-近鄰分類方法性能好，當(dāng)選定合適的k值時(shí)，基于影響函數(shù)的k-近鄰算法并常用的分類算法性能還好。但是基于影響函數(shù)的k-近鄰分類算法往往比普通的k-近鄰分類方法需要考慮更多的近鄰。本文中，將基于影響函數(shù)的分類方法應(yīng)用與非平衡數(shù)據(jù)集分類中，發(fā)現(xiàn)該方法對(duì)于非平衡數(shù)據(jù)集分類也有效，我們工作的下一步是設(shè)計(jì)更復(fù)雜的影響函數(shù)，并推廣至多元的非平衡數(shù)據(jù)集分類中去?？紤]將基于影響函數(shù)分類和支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)方法結(jié)合起來(lái)，進(jìn)一步提高分類的性能。

［1］ Tan P N and Steinbach M著，范明，范宏建，譯. 數(shù)據(jù)挖掘入門(mén)［M］. 第2版，北京：人民郵電出版社，2011：127-187.

［2］ Quinlan J S. Induction of decision trees［J］. Machine Learning，1986，1（1）：81-106.

［3］ Domingos P and Pazzani M J. Beyond independence：conditions for the optimality of the simple bayesian classifier［C］. Proceedings of the International Conference on Machine Learning，Bari，Italy，1996：105-112.

［4］ Rumelhart D E，Hinton G E，and Williams R J. Learning representations by back-propagating errors［J］. Nature，1986，323（9）：533-536.

［5］ Boser B E，Guyon I M，and Vapnik V N. A training algorithm for optimal margin classifiers［C］. Proceedings of the Conference on Learning Theory，Pittsburgh，USA，1992：144-152.

［6］ Dasarathy B V. Nearest Neighbor （NN） norms：NN Pattern Classification Techniques［M］. Michigan：IEEE Computer Society Press，1991：64-85.

［7］ Leake D B. Experience，introspection and expertise：learning to refine the case-based reasoning process［J］. Journal of Experimental & Theoretical Artificial Intelligent，1996，8（3/4）：319-339.

［8］ Hinneburg A and Keim D A. An efficient approach to clustering in large multimedia databases with noise［C］. Proceedings of the Knowledge Discovery and Data Mining，New York，USA，1998：58-65.

［9］ Bache K and Lichman M. UCI repository of machine learning databases［OL］. http：//www.ics.uci.edu/～mlearn/MLRepository. html. 2014.5.

［10］ Liu X Y，Li Q Q，and Zhou Z H. Learning imbalanced multi-class data with optimal dichotomy weights［C］. Proceedings of the 13th IEEE International Conference on Data Mining，Dallas，USA，2013：478-487.

［11］ He H B and Edwardo A G. Learning from imbalanced Data［J］. IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

［12］ Maratea A，Petrosino A，and Manzo M. Adjusted F-measure and kernel scaling for imbalanced data learning［J］. Information Sciences，2014（257）：331-341.

［13］ Wang S and Yao X. Multiclass imbalance problems：analysis and potential solutions［J］. IEEE Transactions on Systems，Man and Cybernetics， Part B，2012，42（4）：1119-1130.

［14］ Lin M，Tang K，and Yao X. Dynamic sampling approach to training neural networks for multiclass imbalance classification［J］. IEEE Transactions on Neural Networks and Learning Systems，2013，24（4）：647-660.

［15］ Peng L Z，Zhang H L，Yang B，et al.. A new approach for imbalanced data classification based on data gravitation［J］. Information Sciences，2014（288）：347-373.

［16］ Menardi G and Torelli N. Training and assessing classification rules with imbalanced data［J］. Data Mining and Knowledge Discovery，2014，28（1）：92-122.

職為梅： 女，1977年生，博士生，講師，研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、人工智能.

張 婷： 女，1988年生，碩士，研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、人工智能.

范 明： 男，1948年生，教授，博士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)挖掘、模式識(shí)別、人工智能.

k-nearest Neighbor Classification Based on Influence Function

Zhi Wei-mei Zhang Ting Fan Ming

（College of Information Engineering， Zhengzhou University， Zhengzhou 450052，China）

Classification is a supervised learning. It determines the class label of an unlabeled instance by learning model based on the training dataset. Unlike traditional classification，this paper views classification problem from another perspective，that is influential function. That is，the class label of an unlabeled instance is determined by the influence of the training data set. Firstly，the idea of classification is introduced based on influence function. Secondly，the definition of influence function is given and three influence functions are designed. Finally，this paper proposes k-nearest neighbor classification method based on these three influence functions and applies it to the classification of imbalanced data sets. The experimental results on 18 UCI data sets show that the proposed method improves effectively the k-nearest neighbor generalization ability. Besides，the proposed method is effective for imbalanced classification.

Data mining；Supervised learning；Classification of imbalanced data sets；Influence function；k-Nearest Neighbor （kNN）

TP181

A

1009-5896（2015）07-1626-07

10.11999/JEIT141433

2014-11-13收到，2015-04-03改回，2015-06-01網(wǎng)絡(luò)優(yōu)先出版

國(guó)家自然科學(xué)基金（61170223）和河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（14A520016）資助課題

*通信作者：職為梅 iewmzhi@zzu.edu.cn