李洪奇　楊中國(guó)　朱麗萍　劉　薔

(中國(guó)石油大學(xué)石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室　北京 102249)(中國(guó)石油大學(xué)計(jì)算機(jī)系　北京 102249)

?

基于數(shù)據(jù)集特征的KNN最優(yōu)K值預(yù)測(cè)方法

李洪奇楊中國(guó)朱麗萍劉薔

(中國(guó)石油大學(xué)石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室北京 102249)(中國(guó)石油大學(xué)計(jì)算機(jī)系北京 102249)

摘要KNN算法中的參數(shù)K的選擇一般采取多次交叉驗(yàn)證方法求取，數(shù)據(jù)規(guī)模較大時(shí)并不適用。同時(shí)，影響參數(shù)選擇最根本的因素是數(shù)據(jù)集本身。因此，提出利用數(shù)據(jù)集本身的特征預(yù)測(cè)最優(yōu)K值的方法。首先提取歷史數(shù)據(jù)集的簡(jiǎn)單特征、統(tǒng)計(jì)特征、信息熵特征、簡(jiǎn)單算法精度特征、復(fù)雜度特征等構(gòu)建特征向量，然后利用線性回歸、神經(jīng)網(wǎng)絡(luò)等方法建立特征向量與最優(yōu)K值之間的預(yù)測(cè)模型，并用該模型預(yù)測(cè)新數(shù)據(jù)集的最優(yōu)K值。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明，該方法能迅速預(yù)測(cè)最優(yōu)K值，并確保一定的精度。

關(guān)鍵詞KNN分類算法數(shù)據(jù)集特征信息熵最優(yōu)K

0引言

KNN分類算法[1]是機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)經(jīng)典算法，該算法簡(jiǎn)單、易于實(shí)現(xiàn)，被列為數(shù)據(jù)挖掘十大算法之一[2]。KNN是一種基于實(shí)例的學(xué)習(xí)算法，它的分類原理是尋找與被預(yù)測(cè)對(duì)象最相似的K個(gè)對(duì)象—鄰居，由鄰居確定被預(yù)測(cè)對(duì)象的類別。K值決定了鄰居的個(gè)數(shù)，進(jìn)一步?jīng)Q定了密度估計(jì)的平滑度，它的取值是一個(gè)重要的問(wèn)題[3]。如果值取得過(guò)小，則算法易受噪聲的影響，使分類結(jié)果不穩(wěn)定；值取得過(guò)大，則模型偏向于將預(yù)測(cè)對(duì)象為類別數(shù)量多的一類。同時(shí)，過(guò)大的K值也增加了算法的時(shí)間復(fù)雜度。

前人有很多工作研究了最優(yōu)K值選擇的問(wèn)題。文獻(xiàn)[4,5]從理論上說(shuō)明當(dāng)鄰居距離使用的是歐式距離的時(shí)候，K的選擇應(yīng)該遵循原則：k→∞,k/n→0，這個(gè)理論對(duì)小樣本數(shù)據(jù)并不適用。文獻(xiàn)[6,7]使用交叉驗(yàn)證的方式評(píng)估取得最小錯(cuò)誤率的K值作為最優(yōu)K值。這種方式是目前普遍使用的方法，它的計(jì)算復(fù)雜性較大，存在多值性，難以取舍。

模型的精度、參數(shù)本質(zhì)上是由數(shù)據(jù)集本身的特征決定的。文獻(xiàn)[18]利用各種數(shù)據(jù)集構(gòu)建元數(shù)據(jù)建立回歸模型對(duì)算法精度進(jìn)行預(yù)測(cè)并取得較好效果。借鑒文獻(xiàn)[18]的思想，利用已有數(shù)據(jù)集的先驗(yàn)知識(shí)，提取數(shù)據(jù)集的特征直接預(yù)測(cè)KNN算法中的參數(shù)K值。對(duì)UCI公共數(shù)據(jù)集[19]的特征進(jìn)行度量，利用線性回歸模型建立數(shù)據(jù)集特征和最優(yōu)K值之間的模型。對(duì)新的數(shù)據(jù)集提取相應(yīng)的特征，利用訓(xùn)練好的回歸模型對(duì)最優(yōu)K值進(jìn)行預(yù)測(cè)。該方法在UCI120個(gè)數(shù)據(jù)集測(cè)試上取得理想結(jié)果，能在短時(shí)間內(nèi)預(yù)測(cè)出KNN算法的最優(yōu)K值。

1算法精度與數(shù)據(jù)集的關(guān)系

文獻(xiàn)[17]通過(guò)分析UCI上的五個(gè)數(shù)據(jù)集(sick、labor、pima、iono和vechicle)的K值與精度變化曲線指出KNN算法的精度會(huì)隨著K值呈現(xiàn)一定規(guī)律變化。K值從1開始逐漸增大的過(guò)程中，精度會(huì)出現(xiàn)一定的抖動(dòng)，之后會(huì)出現(xiàn)平穩(wěn)的下降趨勢(shì)。并分析了上述規(guī)律的主要原因：K較小時(shí)候，精度會(huì)受到噪聲的很大影響；當(dāng)K較大的時(shí)候，精度會(huì)受到多數(shù)類別樣本的影響。不同的數(shù)據(jù)集由于數(shù)據(jù)分布、噪聲點(diǎn)、離群點(diǎn)、屬性類別等不一樣，參數(shù)K的取值也不一樣。文獻(xiàn)[20]指出影響模型精度的原因是數(shù)據(jù)集本身的特征，他們用數(shù)據(jù)集上提取的特征向量預(yù)測(cè)各個(gè)模型的精度，并取得較好效果。

圖1是UCI數(shù)據(jù)集中任意挑選的20個(gè)數(shù)據(jù)集在十種分類算法下的精度表現(xiàn)，參數(shù)為weka(http://www.cs.waikato.ac.nz/ml/weka/)的默認(rèn)參數(shù)。同時(shí)計(jì)算了每個(gè)數(shù)據(jù)集對(duì)應(yīng)各個(gè)算法的精度平均值、方差以及KNN算法最優(yōu)K值，這里的最優(yōu)K值是通過(guò)十折交叉驗(yàn)證的方式取得精度最高對(duì)應(yīng)的K值。

圖1　20個(gè)數(shù)據(jù)集精度以及KNN算法中的最優(yōu)K值

表1列舉了部分?jǐn)?shù)據(jù)集的算法精度值，從表1可以看出，每個(gè)數(shù)據(jù)集在各種算法上的精度表現(xiàn)都有一定規(guī)律性。比如：數(shù)據(jù)集horse-colic的精度在0.8附近，最小值為0.75(KStar)，最大值0.856(PART、C4.5)。此數(shù)據(jù)集在基于實(shí)例的算法，3NN和KStar的精度都不如基于樹規(guī)則的C4.5、PART算法。這本質(zhì)上是由于數(shù)據(jù)集的數(shù)據(jù)分布規(guī)律和特征決定的。同樣，KNN算法中，最優(yōu)K值是和數(shù)據(jù)集的特征緊密聯(lián)系的，數(shù)據(jù)集的特征決定了各個(gè)分類器的精度以及最優(yōu)K值。尋找到合適的數(shù)據(jù)集特征來(lái)刻畫數(shù)據(jù)集，就能有效地預(yù)測(cè)算法的精度以及最優(yōu)K值。

表1　部分?jǐn)?shù)據(jù)集的算法精度以及最優(yōu)K值

2數(shù)據(jù)集與最優(yōu)K值預(yù)測(cè)

2.1數(shù)據(jù)集的刻畫

刻畫數(shù)據(jù)集的方法，可以分為六個(gè)方面：簡(jiǎn)單特征[21]、統(tǒng)計(jì)特征[22]、基于信息熵的特征[23]、基于模型的特征[24]、基于地標(biāo)算法精度的特征[25]、基于數(shù)據(jù)集復(fù)雜性的特征[26]。這些數(shù)據(jù)集特征的詳細(xì)內(nèi)容如下：

1) 簡(jiǎn)單特征：樣本數(shù)量、類別數(shù)量、特征數(shù)量、類別型特征的數(shù)量、數(shù)值型特征的數(shù)量、類別型特征的比例、數(shù)值型特征個(gè)數(shù)比例、維度比。

2) 統(tǒng)計(jì)特征：峰度、偏度、典型相關(guān)分析、特征值、最大關(guān)聯(lián)系數(shù)。

3) 信息熵：標(biāo)準(zhǔn)化類別信息熵、標(biāo)注化類別平均信息熵、聯(lián)合信息熵、互信息、信噪比、信息熵度量下的等同特征數(shù)目。計(jì)算公式如下：

(1)

(2)

(3)

(4)

其中，X是屬性變量，Y是類別量，p(x)是屬性變量X的概率分布。JointEntropy是聯(lián)合熵，MutualInf(X,Y)是屬性和類別的互信息，ClassEntropy是類別熵，AttsEntropy是屬性熵。

4) 基于決策樹的特征：構(gòu)建一棵沒(méi)有剪枝的決策樹，關(guān)于這棵決策樹的很多統(tǒng)計(jì)量作為特征。用到的統(tǒng)計(jì)量是葉節(jié)點(diǎn)的個(gè)數(shù)、節(jié)點(diǎn)的個(gè)數(shù)、每個(gè)特征的平均節(jié)點(diǎn)數(shù)、每個(gè)樣本的平均節(jié)點(diǎn)數(shù)。利用決策樹來(lái)判別數(shù)據(jù)集相似性的原理是認(rèn)為相似的數(shù)據(jù)集會(huì)產(chǎn)生的決策樹有相似的結(jié)構(gòu)。圖2是決策樹的統(tǒng)計(jì)特征示意圖。

圖2　決策樹指標(biāo)示意圖

決策樹指標(biāo)的提取，包括樹的寬度、高度、層數(shù)、分支數(shù)目、屬性使用次數(shù)等，都是以圖2所示的決策樹作為基礎(chǔ)。

5) 簡(jiǎn)單算法精度特征：簡(jiǎn)單分類器的精度，比如：樸素貝葉斯算法、線性判別、1NN。簡(jiǎn)單分類器的精度表現(xiàn)能在一定程度上反映數(shù)據(jù)集的特征。

6) 數(shù)據(jù)復(fù)雜性指標(biāo)：特征最大Fisher判別率、類別間重合比例、最大單特征分類效率、聯(lián)合特征分類效率、類別重合率、邊界比例、邊界點(diǎn)不同類別比例、屬性純凈度等。這些指標(biāo)的具體定義的詳細(xì)介紹見文獻(xiàn)[26]。其中屬性純凈度的概念是針對(duì)離散型數(shù)據(jù)集，它用來(lái)定義數(shù)據(jù)集中的屬性對(duì)類別的區(qū)別能力大小，計(jì)算公式如下：

(5)

(6)

定義數(shù)據(jù)集的總的純凈度為：

(7)

首先定義屬性的每個(gè)屬性值的純凈度為對(duì)應(yīng)屬性值vi的樣本在各個(gè)類別下的分布的混亂程度，也就是對(duì)應(yīng)該分布的信息熵，見式(5)。屬性f是類別型屬性，設(shè)f有m個(gè)屬性值{v1,v2,…,vm}，樣本取值為屬性值vk的個(gè)數(shù)為|vk|，式(5)中的pkj為樣本在特征f下取值為vk且屬于第j類的樣本概率。Purej指的是第j個(gè)特征的純凈度，見式(6)，它是每個(gè)屬性值純凈度的加權(quán)和。數(shù)據(jù)集E的純凈度定義為所有特征純凈度的最小值，見式(7)。

前人利用數(shù)據(jù)集的特征在算法選擇問(wèn)題上做了很多工作。比如：用于模型選擇[27]、用于模型參數(shù)確定[28]、樣本選擇[29]。

2.2影響KNN算法精度的指標(biāo)

文獻(xiàn)[18]指出類別個(gè)數(shù)、峰度、聯(lián)合熵、相當(dāng)于類別屬性信息熵的屬性數(shù)量、互信息、決策樹的寬度、寬度均值、寬度方差、1NN、C4.5、NB(樸素貝葉斯算法)等特征對(duì)KNN算法的精度有較大影響。同時(shí)，為了保證計(jì)算效率，文中只選擇部分?jǐn)?shù)據(jù)集特征作為預(yù)測(cè)K值的特征。選擇的特征的復(fù)雜度要小于O(N×|D|×log|D|)。

數(shù)據(jù)集屬性可能是數(shù)值型或者類別型的，計(jì)算數(shù)據(jù)集的特征向量會(huì)涉及到屬性類型的轉(zhuǎn)化。數(shù)值型數(shù)據(jù)離散化有基于信息熵的MDLP算法、頻率等；類別型數(shù)據(jù)數(shù)值化一般采取的是二進(jìn)制的方法。實(shí)際運(yùn)用算法過(guò)程中，一般將連續(xù)數(shù)據(jù)離散化，而較少將類別數(shù)據(jù)數(shù)值化。因此本文使用的數(shù)據(jù)集特征向量的提取指標(biāo)中不考慮只針對(duì)數(shù)值型數(shù)據(jù)的指標(biāo)。例如：去掉了峰度、偏度等指標(biāo)。這樣避免了由于數(shù)據(jù)類型之間的轉(zhuǎn)化對(duì)結(jié)果造成影響。而對(duì)于混合型數(shù)據(jù)集，在計(jì)算類別型指標(biāo)的時(shí)候就要先將連續(xù)數(shù)據(jù)離散化，離散化方法采取的最后選擇的用于預(yù)測(cè)KNN算法最優(yōu)K值的數(shù)據(jù)集特征如表2所示。

表2　數(shù)據(jù)集特征指標(biāo)

2.3最優(yōu)K值預(yù)測(cè)流程

算法流程為首先提取每個(gè)數(shù)據(jù)集的特征向量，以及在十折交叉驗(yàn)證下的最優(yōu)K值。最優(yōu)K值的求取采取窮舉的方法。如果用交叉驗(yàn)證方式評(píng)價(jià)的最優(yōu)K值有多個(gè)，則選擇較小的K值。利用特征向量和K值構(gòu)成訓(xùn)練樣本，采取線性回歸模型建立模型。最后，對(duì)新的數(shù)據(jù)集預(yù)測(cè)最優(yōu)K值。具體流程如圖3所示。

圖3　最優(yōu)K值預(yù)測(cè)方法流程

利用特征向量和K值構(gòu)成的訓(xùn)練樣本構(gòu)建線性回歸模型，利用weka(http://www.cs.waikato.ac.nz/ml/weka/)自帶的線性回歸算法進(jìn)行建模。特征向量的計(jì)算指標(biāo)都是復(fù)雜性在O(N×|D|×log|D|)內(nèi)的，而且避免了多次交叉驗(yàn)證求取最優(yōu)K值，因此該方法預(yù)測(cè)K值是有意義的。對(duì)于新樣本，首先提取該數(shù)據(jù)集的特征，然后利用訓(xùn)練好的模型預(yù)測(cè)出K值。

預(yù)測(cè)模型的建立有很多種選擇，可以使用神經(jīng)網(wǎng)絡(luò)、決策樹、KNN算法、支持向量機(jī)等。本文僅以線性回歸模型為例進(jìn)行說(shuō)明。處理具體應(yīng)用的數(shù)據(jù)集的時(shí)候，可以選擇本領(lǐng)域的大量數(shù)據(jù)集作為歷史數(shù)據(jù)集。根據(jù)機(jī)器學(xué)習(xí)理論，更具有代表性的、更多的歷史數(shù)據(jù)集的積累會(huì)改善機(jī)器學(xué)習(xí)的準(zhǔn)確性。本文實(shí)驗(yàn)以來(lái)自網(wǎng)絡(luò)的公開的加州大學(xué)歐文分校的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[19]為例進(jìn)行說(shuō)明，實(shí)驗(yàn)結(jié)果證明了該方法的有效性。

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

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

數(shù)據(jù)集來(lái)自加州大學(xué)歐文分校公開的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)。選取其中120個(gè)分類型數(shù)據(jù)集作為本實(shí)驗(yàn)的數(shù)據(jù)來(lái)源，涉及計(jì)算機(jī)工程、生命科學(xué)、物理科學(xué)、社會(huì)生活、電子商務(wù)以及游戲等領(lǐng)域。數(shù)據(jù)集的實(shí)例個(gè)數(shù)分布在14到20 000個(gè)；屬性個(gè)數(shù)分布在3到101個(gè)；類別個(gè)數(shù)分布在2到28個(gè)。這些都是數(shù)據(jù)集的表面特征，取更大的范圍能保證本文方法的適用性。

3.2評(píng)價(jià)指標(biāo)

本文提出的方法在計(jì)算復(fù)雜度上遠(yuǎn)遠(yuǎn)低于重復(fù)多次的十次交叉驗(yàn)證方法。為了支持這一結(jié)論，本文在評(píng)價(jià)指標(biāo)中加入了算法性能指標(biāo)。

其次預(yù)測(cè)的K值與最優(yōu)K值的差距是算法效果的直接體現(xiàn)。為了計(jì)算預(yù)測(cè)的K值與最優(yōu)K值的距離，要計(jì)算數(shù)據(jù)在這兩個(gè)K值下的精度差距。借鑒文獻(xiàn)[17]采用的三個(gè)評(píng)價(jià)指標(biāo)：

1)MAE(magnitudeofabsoluteerror)表示推薦的值對(duì)應(yīng)的分類精度(預(yù)測(cè)精度)與最優(yōu)對(duì)應(yīng)的分類精度(最優(yōu)精度)的絕對(duì)誤差，即MAE=(最優(yōu)精度-預(yù)測(cè)精度) × 100%。

2)MRE(magnitudeofrelativeerror)表示預(yù)測(cè)精度與最優(yōu)精度之間的相對(duì)誤差，即MRE=(最優(yōu)精度-預(yù)測(cè)精度)÷最優(yōu)精度×100%。對(duì)于MAE和MRE，它們的值越小表示預(yù)測(cè)精度越接近最優(yōu)精度，意味著算法效果越好。

3)PRED(·)是另一個(gè)常用的評(píng)價(jià)指標(biāo)。PRED(m)表示MAE小于m%的數(shù)據(jù)集個(gè)數(shù)占總預(yù)測(cè)數(shù)據(jù)集個(gè)數(shù)的百分比；最優(yōu)的K和預(yù)測(cè)出來(lái)的K值對(duì)應(yīng)精度的差別在5%之內(nèi)就認(rèn)為是不錯(cuò)的結(jié)果。

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

3.3.1算法性能測(cè)試

算法的性能測(cè)試，測(cè)試環(huán)境是：CPU是Intelcorei5duo3.2GHz，內(nèi)存4GB。

實(shí)驗(yàn)?zāi)康氖菧y(cè)試算法的運(yùn)行效率，選擇了120個(gè)數(shù)據(jù)集進(jìn)行對(duì)比測(cè)試。表3顯示了部分?jǐn)?shù)據(jù)集的在最優(yōu)K值預(yù)測(cè)算法運(yùn)行時(shí)間、文獻(xiàn)[17]提出的壓縮K值范圍的算法時(shí)間、使用多次交叉驗(yàn)證算法運(yùn)行的時(shí)間。K值的初始范圍為1～logN，文獻(xiàn)[17]的算法的是進(jìn)一步壓縮了K值范圍為1～log(logN)。由表3可以看出，本文使用的算法的運(yùn)行效率明顯高于多次交叉驗(yàn)證算法的運(yùn)行效率。當(dāng)數(shù)據(jù)集的樣本個(gè)數(shù)較大的情況下，差異越是明顯。

表3　最優(yōu)K值預(yù)測(cè)算法與KNN算法運(yùn)行效率對(duì)比

續(xù)表3

3.3.2算法效果

根據(jù)選擇的120個(gè)數(shù)據(jù)集特征以及最優(yōu)K值構(gòu)成的訓(xùn)練樣本，利用分層抽樣的辦法選擇其中60個(gè)數(shù)據(jù)集作為訓(xùn)練集，總的120個(gè)數(shù)據(jù)集作為測(cè)試集。此模型只是在有限的歷史數(shù)據(jù)集中學(xué)習(xí)得到的案例，不能直接使用到任意應(yīng)用領(lǐng)域中。為了說(shuō)明實(shí)驗(yàn)的有效性，本文給出了實(shí)驗(yàn)得到的回歸模型如圖4所示。

圖4　回歸模型

可以看到的是，指標(biāo)屬性個(gè)數(shù)比例(RateOfnumericAtt以及RateOfNominalAtt)、簡(jiǎn)單算法精度(C4.5、NB、1NN)以及基于未剪枝決策樹的統(tǒng)計(jì)量(樹高-treeheight、最長(zhǎng)分支-LongBranch)等對(duì)回歸模型影響較大。用預(yù)測(cè)的K值與最優(yōu)K值對(duì)應(yīng)的KNN算法精度衡量本方法的效果。部分?jǐn)?shù)據(jù)集的在兩個(gè)K值下的精度偏差，如表4所示。

表4　預(yù)測(cè)K值和最優(yōu)K值的絕對(duì)

續(xù)表4

表5統(tǒng)計(jì)了120個(gè)數(shù)據(jù)集上MAE和MRE的最小值(min)、最大值(max)、中位數(shù)(median)、眾數(shù)(mode)、平均值(mean)和標(biāo)準(zhǔn)差(std)，并給出了PRED(m)的值。

表5　整體測(cè)試數(shù)據(jù)集上的絕對(duì)誤差MAE(%)與相對(duì)誤差MRE(%)

從表5可以看出有86.13%的數(shù)據(jù)集的預(yù)測(cè)K值精度與最優(yōu)K值對(duì)應(yīng)精度的絕對(duì)偏差在5%范圍內(nèi)。此結(jié)果與文獻(xiàn)[17]對(duì)比，預(yù)測(cè)準(zhǔn)確率要低于94%，但是本方法避免了多次交叉驗(yàn)證即可求取最優(yōu)K值，因此在速度上更優(yōu)。

4結(jié)語(yǔ)

本文針對(duì)KNN算法中近鄰數(shù)的確定問(wèn)題進(jìn)行了研究。不同于從交叉驗(yàn)證方式、概率分布角度、快速搜索方式求取K值，本文從數(shù)據(jù)集特征的角度直接預(yù)測(cè)最優(yōu)K值。在120個(gè)公開數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了該算法的運(yùn)行效率高，實(shí)驗(yàn)效果較好。實(shí)驗(yàn)過(guò)程中算法采取的回歸模型能很好地預(yù)測(cè)未知數(shù)據(jù)集最優(yōu)K值，為快速確定模型參數(shù)提供了新的方法。雖然本方法預(yù)測(cè)模型參數(shù)取得較快速度，但是在精度上有所損失，只有86%的數(shù)據(jù)集能確保精度誤差在5%范圍內(nèi)。

計(jì)算眾多數(shù)據(jù)集特征影響模型參數(shù)會(huì)影響預(yù)測(cè)性能，進(jìn)一步篩選有效、可用的數(shù)據(jù)集特征是下一步的工作。另外，數(shù)據(jù)集特征對(duì)模型多參數(shù)的預(yù)測(cè)、模型的選擇是下一步要研究的工作。

參考文獻(xiàn)

[1]CoverT,HartP.Nearestneighborpatternclassification[J].IEEETransonInformationTheory,1967,13(1):21-27.

[2]WuXD,KumarV,RossQuinlanJ,etal.Top10algorithmsindatamining[J].KnowledgeandInformationSystems,2008,14(1):1-37.

[3]GuoG,WangH,BellD,etal.KNNmodel-basedapproachinclassification[C]//IntConfonCooperativeInformationSystems.Berlin:Springer-Verlag,2003:986-996.

[4]LoftsgaardenDO,QuesenberryCP.Anonparametricestimateofmultivariatedensityfunction[J].AnnMathStatist,1965,36(3):1049-1051.

[5]CoverTM,HartPE.Nearestneighborpatternclassification[J].IEEETransInformTheory,1968,13(1):21-27.

[6]LachenbruchPA,MickeyMR.Estimationoferrorratesindiscriminantanalysis[J].Technometrics,1968,10(1):1-11.

[7]StoneM.Crossvalidation:areview.MathOperationsforschungundStatistik[J].SeriesStatistics,1978,9(1):127-139.

[8]GatesG.Thereducednearestneighborrule[J].IEEETransonInformationTheory,1972,18(3):431-433.

[9]FukunagaK,HostetlerLD.Optimizationofk-nearest-neighbordensityestimates[J].IEEETransInformTheoryIT,1973,19(3):320-326.

[10]WettschereckD,DietterichTG.Locallyadaptivenearestneighboralgorithms[C]//AdvancesinNeuralInformationProcessingSystems.Colorado:MorganKaufmann,1993:184-191.

[11]G′oraG,WojnaA.RIONA:Anewclassificationsystemcombiningruleinductionandinstance-basedlearning[J].FundamentaInformaticae,2002,51(4):369-390.

[12]DavidJHand,VeronicaVinciotti.Choosingkfortwo-classnearestneighbourclassifierswithunbalancedclasses[J].PatternRecognitionLetters,2003,24(9):1555-1562.

[13]WangJigang,PredragN,LeonNC.Neighborhoodsizeselectioninthek-nearest-neighborruleusingstatisticalconfidence[J].PatternRecognition,2006,39(3):417-423.

[14]GhoshAK.Onnearestneighborclassificationusingadaptivechoiceofk[J].JofComputationalandGraphicalStatistics,2007,16(2):482-502.

[15]PeterHall,ByeongUPark,RichardJSamworth.Choiceofneighbororderinnearest-neighborclassification[J].TheAnnalsofStatistics,2008,36(5):2135-2152.

[16]SunLY,ChenL.Afastandscalablefuzzy-roughnearestneighboralgorithm[C]//ProcoftheWRIGlobalCongressonIntelligentSystems.Washington:IEEEComputerSociety,2009:311-314.

[17] 杜磊,杜星,宋擒豹.一種KNN分類器K值自動(dòng)選取方法[J].控制與決策,2013,28(7):1073-1077.

[18]MatthiasReif,FaisalShafait,MarkusGoldstein,etal.Automaticclassifierselectionfornon-experts[J].PatternAnalApplic,2014,17(7):83-96.

[19]BlakeC,MerzCJ.UCIrepositoryofmachinelearningdatabases[DB/OL].[2011-06-20].http://archive.ics.uci.edu/ml/.

[20]NúriaMaciàa,EsterBernadóMansillaa,AlbertOrriolsPuiga,etal.Learnerexcellencebiasedbydatasetselection:acasefordatacharacterisationandartificialdatasets[J].PatternRecognition,2013,46(3):1054-1066.

[21]RobertEngels,ChristianeTheusinger.UsingaDataMetricforPreprocessingAdviceforDataMiningApplications[C]//PradeH.(ed.)Proceedingsofthe13thbiennialEuropeanConferenceonArtificialIntelligence(ECAI1998),1998:430-434.

[22]SohnSY.Metaanalysisofclassificationalgorithmsforpatternrecognition[J].IEEETransonPatternAnalysisandMachineIntelligence,1999,21(11):1137-1144.

[23]SaddysSegrera,JoelPinho,MaríaNMoreno.Information-theoreticmeasuresformeta-learning[J].HybridArtificialIntelligenceSystemsLectureNotesinComputerScience,2008,5271(3):458-465.

[24]NguyenP,HilarioM,KalousisA.UsingMeta-miningtoSupportDataMiningWorkflowPlanningandOptimization[J].JournalofArtificialIntelligenceResearch,2014,51(1):605-644.

[25]BernhardPfahringer,HilanBensusan,ChristopheGCarrier.Meta-learningbylandmarkingvariouslearningalgorithms[C]//ProceedingsoftheSeventeenthInternationalConferenceonMachineLearning,2000:743-750.

[26]José-RamónCano.Analysisofdatacomplexitymeasuresforclassification[J].ExpertSystemswithApplications,2014,40(12):4820-4831.

[27]ChristianMoewes,AndreasNurnberger.ComputationalIntelligenceinIntelligentDataAnalysis[M].Springer-VerlagBerlinandHeidelbergGmbH&Co.K,2013.

[28]KotthoL,GentIP,MiguelI.Anevaluationofmachinelearninginalgorithmselectionforsearchproblems[J].AICommunications,2012,25(3):257-270.

[29]EnriqueLeyva,YoelCaises,AntonioGonzález,etal.Ontheuseofmeta-learningforinstanceselection:Anarchitectureandanexperimentalstudy[J].InformationSciences,2014,266(10):16-30.

PREDICTION METHOD OF OPTIMAL K VALUE IN KNN BASEDONDATASETFEATURES

Li HongqiYang ZhongguoZhu LipingLiu Qiang

(Key Lab of Petroleum Data Mining,China University of Petroleum,Beijing 102249,China)(Department of Computer,China University of Petroleum,Beijing 102249,China)

AbstractMultiple cross validation method is usually used in KNN algorithm to choose parameter K, but it is not applicable when the size of dataset is big. Meanwhile, the most fundamental factor affecting the parameter selection is dataset itself. Therefore, we proposed an optimal K value prediction method by using the featurs of dataset itself. First is the eigenvector construction by extracting the features of historical dataset including the simple feature, statistic feature, information entropy feature, precision feature of simple algorithm, and complexity feature, etc. Then, the method employs the methods of linear regression and neural network to build a prediction model between eigenvector and optimal K value, and uses the model to predict the optimal K of new dataset. It was indicated by the experiment on UCI dataset that the method could quickly predict optimal K value and ensure certain precision.

KeywordsKNN classification algorithmDataset featureInformation entropyOptimal K

收稿日期：2015-01-20。中國(guó)石油大學(xué)(北京)基金項(xiàng)目(KYJJ 2012-05-25)。李洪奇，教授，主研領(lǐng)域：石油數(shù)據(jù)挖掘。楊中國(guó)，博士生。朱麗萍，副教授。劉薔，碩士生。

中圖分類號(hào)TP18

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.014