謝 妙, 林泳昌, 朱曉姝

(玉林師范學院 計算機科學與工程學院,廣西 玉林 537000)

0 引 言

k最近鄰(k-nearest neighbor,KNN)算法是十大數(shù)據(jù)挖掘“經(jīng)典算法”之一[1]。對于任意給定測試樣本,KNN算法基于距離度量找出訓練集中與其最靠近的k個訓練樣本,然后基于這k個最近“鄰居”的分類屬性來預(yù)測該測試樣本的類型[2]。由于KNN算法的k值一般是根據(jù)經(jīng)驗設(shè)定或利用十折交叉法得到,使得k值存在一定的不合理性。另外,由于沒有考慮樣本之間的相關(guān)性,相同屬性的權(quán)重也影響了分類準確率。為此,許多學者對KNN算法進行了改進;文獻[3]提出了一種距離加權(quán)KNN算法,該算法在傳統(tǒng)KNN算法基礎(chǔ)上,考慮分類時各類近鄰樣本與待分類樣本的平均距離,但并未考慮屬性值對類別的影響;文獻[4]考慮不同的特征對分類重要性的影響,通過特征選擇和特征加權(quán)途徑改進距離度量;文獻[5]基于待分類樣本的互近鄰及近鄰誘導待分類樣本類標簽的可信度,提出了一種新的k最近鄰的分類算法;文獻[6]提出利用數(shù)據(jù)集本身的特征預(yù)測最優(yōu)k值的方法;文獻[7]提出一種基于屬性值信息熵的KNN改進算法,該算法首先定義2個樣本間的距離為相同屬性值的平均信息熵,然后根據(jù)此距離選取與待測試樣本距離最小的k個近鄰,最后根據(jù)各類近鄰樣本點的平均距離及個數(shù)判斷待測試樣本的類別。雖然分類準確率有所提高,但未考慮近鄰樣本間的相似度;文獻[8]提出了一種自適應(yīng)的KNN算法,自適應(yīng)計算k值和每個樣本點的權(quán)重向量,但需要消耗大量的計算資源;文獻[9]提出一種基于高斯函數(shù)加權(quán)的自適應(yīng)KNN算法,利用高斯函數(shù)計算距離權(quán)值向量,然后根據(jù)該向量計算樣本點的自適應(yīng)最近鄰個數(shù);文獻[10]提出基于環(huán)形過濾器的k值自適應(yīng)KNN算法,該算法通過環(huán)形過濾器過濾出每個測試點的內(nèi)圍訓練集,然后通過新訓練集來構(gòu)建每個待測點的稀疏向量,從而得出每個測試點的動態(tài)k值,雖然分類準確率有所提高,但對不平衡數(shù)據(jù)集誤判率較高。本文提出一種基于信息熵的自適應(yīng)k值KNN二分類算法(adaptivek-value KNN bisecting classification algorithm based on information entropy,EAKNN)。該算法通過引入樣本比例定義信息熵,加強小樣本的重要性;通過計算小于預(yù)設(shè)熵閾值的最小信息熵,得到對應(yīng)的k值和模型分數(shù);在此基礎(chǔ)上,結(jié)合提出的精度提升模型計算得到模型精度,不斷迭代模型精度,直到不能提升。在客戶分類預(yù)測等7個數(shù)據(jù)集上的實驗表明,EAKNN算法比傳統(tǒng)KNN算法、基于高斯函數(shù)加權(quán)的自適應(yīng)KNN算法和基于屬性值信息熵的KNN改進算法都有更高的分類準確率。

1 相關(guān)知識

1.1 KNN算法

KNN算法[11]是一個簡單而經(jīng)典的機器學習分類方法。通過度量待分類樣本和已知類別樣本之間的距離(通常使用歐氏距離)或相似度,對樣本進行分類。其算法步驟如下所述。

(1) 使用歐氏距離[12]計算樣本點到所有樣本點之間的距離,其定義公式為:

(1)

其中:d(x,y)為樣本x和樣本y之間的距離；n為特征維數(shù)；xi為樣本x的第i個屬性；yi為樣本y的第i個屬性。

(2) 根據(jù)計算出來的歐氏距離大小對樣本進行遞增排序。若距離越小,則相似度越高。

(3) 選擇前k個距離最近的鄰居樣本點。

(4) 統(tǒng)計k個最近的鄰居樣本點分別屬于每個類別的個數(shù)。

(5) 采用投票法和少數(shù)服從多數(shù)的原則,將k個鄰居樣本點里出現(xiàn)頻率最高的類別,作為該樣本點的預(yù)測類別。

可以看出,KNN算法中只有一個超參數(shù)k,k值的確定對KNN算法的預(yù)測結(jié)果有著至關(guān)重要的作用。k值過小容易導致KNN算法的過擬合;k值過大,算法的近鄰誤差會偏大,容易發(fā)生欠擬合。另外,當數(shù)據(jù)樣本不均衡時,KNN方法預(yù)測結(jié)果會偏向于樣本數(shù)占優(yōu)類,對稀有類別的預(yù)測準確率低。

1.2 信息熵

熵是對系統(tǒng)混亂程度的衡量。熵越小,混亂度越小,系統(tǒng)的不確定程度越小。信息熵用以衡量數(shù)據(jù)本身含有信息量的大小,信息量的大小隨著其發(fā)生概率而遞減。信息熵[13]定義為:

(2)

其中:H(X)為信息熵;X為一組隨機事件x1、x2、…、xn的集合；P(xi)(0≤P(xi)≤1)為出現(xiàn)隨機事件的概率,且P(x1)+P(x2)+…+P(xn)=1。

1.3 模型評價方法R2

模型的優(yōu)劣會影響最終的分類結(jié)果,在常用的模型評估指標中,選擇判定系數(shù)R2來度量預(yù)測值的總變差與真實值的總變差的比值,換言之,就是用來衡量模型的擬合程度。R2定義為:

(3)

2 EAKNN算法

2.1 基本概念與定義

定義1 數(shù)據(jù)集D的信息熵。設(shè)D={x1,x2,…,xn,L}是數(shù)據(jù)的集合,其中:xi={xi1,xi2,…,xid}；d為維度;n為數(shù)據(jù)的個數(shù)；屬性L是數(shù)據(jù)的標簽類別,設(shè)L={-1,1}。數(shù)據(jù)集D的信息熵表示為:

H(D)=-∑Pi(x)lbPi(x)

(4)

其中,Pi表示集合D中屬于類別i的樣本比例。

假設(shè)二分類后得到數(shù)據(jù)集的2個分類子集是不均衡的,數(shù)據(jù)樣本少的分類有時在一定程度上也能起到關(guān)鍵作用。為了提高小樣本的重要性,平衡大小樣本的作用,在數(shù)據(jù)集信息熵中引入類別樣本比例參數(shù)α。α為總樣本數(shù)與該類中樣本數(shù)的比例,計算公式為:

(5)

其中:n為總樣本數(shù);nci為分類中屬于某類的樣本數(shù)。例如,總樣本數(shù)為100、標簽為1的樣本數(shù)為30,則標簽為1的該類樣本的α1=100/30。因此,改進后的信息熵公式為:

H(D)=-∑αiPi(x)lbPi(x)

(6)

定義2 精度提升模型。設(shè)G(x)為模型精度,βi為模型i的分數(shù),gi為模型i的分類結(jié)果。為了提升模型總分類精度,利用分類結(jié)果乘以該模型分數(shù)得到該模型分類結(jié)果,迭代計算,將分類結(jié)果累加,得到模型精度。精度提升模型為:

(7)

2.2 算法描述

在EAKNN算法中,輸入數(shù)據(jù)集(分為訓練集、驗證集和測試集)、最大k值kmax、最小k值kmin、熵閾值HT、訓練集樣本采樣比例和特征采樣比例、循環(huán)變量i、最小迭代次數(shù)m。算法流程如圖1所示,具體實現(xiàn)步驟如下:

圖1 EAKNN算法流程

(1) 根據(jù)樣本采樣比例和特征采樣比例隨機抽取訓練集,遍歷kmin到kmax之間的k值,利用定義的信息熵公式(6)求得最小信息熵及對應(yīng)的k值。

(2) 判斷所求最小信息熵是否小于熵閾值HT。若不小于,則利用步驟(1)求得的k值和共享近鄰[14]方法進行分類;若小于,則利用則步驟(1)求得的k值和KNN方法進行分類,得到驗證集分類結(jié)果和由(3)式計算得到模型分數(shù)。

(3) 將驗證集分類結(jié)果乘以該模型分數(shù)得到該模型分類結(jié)果,迭代計算,將分類結(jié)果累加,得到模型精度,與前一次累加得到的總模型精度進行比較。若精度有所提升,則保留該訓練集作為模型一部分。

(4) 迭代步驟(1)～步驟(3),直到迭代m次模型精度不再提升,則終止。

(5) 輸出測試樣本的分類結(jié)果。

EAKNN方法將數(shù)據(jù)集分為有標簽的訓練集和驗證集,以及無標簽的測試集,獲取數(shù)據(jù)集每個類別的樣本比例,并根據(jù)樣本采樣比例和特征采樣比例隨機抽取訓練集,利用定義的信息熵公式(6)求得最小信息熵時的k值,實現(xiàn)自適應(yīng)選擇k值。

3 實 驗

3.1 實驗數(shù)據(jù)來源

本文實驗數(shù)據(jù)集為疝氣病癥預(yù)測病馬是否死亡數(shù)據(jù)集、收入分類數(shù)據(jù)集、銀行電話營銷數(shù)據(jù)集、銀行貸款分類數(shù)據(jù)集、存款有無預(yù)測數(shù)據(jù)集、客戶分類數(shù)據(jù)集和個人貸款建模數(shù)據(jù)集,其中疝氣病癥預(yù)測病馬是否死亡數(shù)據(jù)集來源于百度百科網(wǎng),其余6個數(shù)據(jù)集均來源于kaggle比賽官網(wǎng)(https://www.kaggle.com/)。數(shù)據(jù)集的具體描述見表1所列。

表1 實驗數(shù)據(jù)集具體描述

3.2 實驗環(huán)境

本實驗使用notebook編譯軟件、Python3.6語言編程,分別使用sklearn里的KNN方法、高斯函數(shù)方法。計算機硬件配置為:內(nèi)存8 GiB,64位操作系統(tǒng),i5-6300HQ處理器。

3.3 評價指標

在機器學習的分類方法中,常常使用準確率來衡量模型的分類效果。

正負樣本混淆矩陣見表2所列,實驗評價指標基于表2。

表2 正負樣本的混淆矩陣

其中:TP和TN分別表示正確分類的正類和負類的樣本數(shù)量;FN和FP分別表示錯誤分類的正類和負類的樣本數(shù)量。

準確率越高模型分類效果越好[15]。準確率計算公式為：

(8)

3.4 實驗參數(shù)設(shè)置

訓練集、驗證集和測試集劃分比例為6∶2∶2,隨機種子設(shè)置為0;kmin=3,kmax=21,entropy=0.5,最小迭代次數(shù)m=5,特征和樣本采樣比例使用高斯分布函數(shù)在[0.5,0.8]中隨機選取。

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

將本文提出的EAKNN方法分別與傳統(tǒng)KNN、基于高斯函數(shù)加權(quán)的自適應(yīng) KNN算法和基于屬性值信息熵的KNN改進算法相比較?；?個數(shù)據(jù)集測試這4種方法的準確率指標,結(jié)果見表3所列。

表3 4種方法的分類準確率

從表3可以看出,EAKNN方法在7個數(shù)據(jù)集上準確率值都大于其他3種方法,即EAKNN的分類性優(yōu)于其他3種方法,特別是銀行電話營銷和銀行貸款分類數(shù)據(jù)集,比KNN方法提高了50%以上,主要原因如下:① 使用改進的信息熵作為KNN分類指標,不僅能刻畫出數(shù)據(jù)集少量樣本的重要性,還能找出最純的k個近鄰點集合,使樣本分類更準確;② 使用隨機屬性、隨機樣本思想,挖掘數(shù)據(jù)特征組合潛在特點,自適應(yīng)地選取特征構(gòu)建多個KNN模型,并對模型進行加權(quán)融合,進一步使樣本分類更準確;③ EAKNN方法引入了共享近鄰方法,當k個近鄰點的樣本特征相似,并無法以信息熵指標進行類別劃分時,使用鄰居相同數(shù)量最多作為其分類指標,避免信息熵無法區(qū)分樣本屬性相近的不足,更進一步提升了模型的分類準確率。

4 結(jié) 論

針對傳統(tǒng)KNN方法k值需要設(shè)定和對樣本不均衡數(shù)據(jù)集的預(yù)測偏差問題,本文提出了一種基于信息熵的自適應(yīng)k值KNN二分類算法。通過引入樣本比例定義信息熵,刻畫出小樣本的重要性,同時找出最純的k個近鄰點集合,使樣本分類更準確。實驗結(jié)果表明,EAKNN算法的模型精度提升明顯,分類準確率比KNN算法平均提高20%。