李洪奇　楊中國　朱麗萍　劉　薔

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

?

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

李洪奇楊中國朱麗萍劉薔

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

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

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

0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

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

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

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

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

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

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

(5)

(6)

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

(7)

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

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

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

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

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

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

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

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

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

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

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

3實驗

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

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

3.2評價指標(biāo)

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

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

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

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

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

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

3.3.1算法性能測試

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

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

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

續(xù)表3

3.3.2算法效果

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

圖4　回歸模型

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

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

續(xù)表4

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

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

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

4結(jié)語

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

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

參考文獻(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值自動選取方法[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。中國石油大學(xué)(北京)基金項目(KYJJ 2012-05-25)。李洪奇，教授，主研領(lǐng)域：石油數(shù)據(jù)挖掘。楊中國，博士生。朱麗萍，副教授。劉薔，碩士生。

中圖分類號TP18

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

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