李長(zhǎng)生，劉宗成，劉 碩

(蘭州石化職業(yè)技術(shù)學(xué)院 信息處理與控制工程學(xué)院，甘肅 蘭州 730060)

分類(lèi)算法是機(jī)器學(xué)習(xí)和模式識(shí)別中的重要研究?jī)?nèi)容之一，諸如貝葉斯網(wǎng)絡(luò)算法、神經(jīng)網(wǎng)絡(luò)算法、決策樹(shù)C4.5算法、SVM(支持向量機(jī))算法、Random forest算法、Bagging算法、KNN算法等。其中，由于K最近鄰算法[1](k-Nearest Neighbor，KNN)思想簡(jiǎn)單、容易實(shí)現(xiàn)、重新訓(xùn)練數(shù)據(jù)的較低代價(jià)、以及較高的分類(lèi)準(zhǔn)確率，使其在自動(dòng)分類(lèi)領(lǐng)域應(yīng)用較廣[2]。

KNN算法簡(jiǎn)單易懂，是一種理論上非常成熟的分類(lèi)算法，但是KNN分類(lèi)算法在遇到數(shù)據(jù)集規(guī)模較大或者維數(shù)較多的時(shí)候，會(huì)陷入維度災(zāi)難的情況，造成KNN模型的計(jì)算開(kāi)銷(xiāo)增大、分類(lèi)效率降低。針對(duì)這一問(wèn)題，許多專(zhuān)家學(xué)者提出在KNN算法運(yùn)行之前預(yù)處理數(shù)據(jù)集，期望緩解這一問(wèn)題，例如張著英等[3]將數(shù)據(jù)集用粗糙集進(jìn)行預(yù)先處理，得到簡(jiǎn)約屬性之后的數(shù)據(jù)集，然后用KNN處理以提高分類(lèi)效率。張孝飛等[4]通過(guò)降低待分類(lèi)對(duì)象與K個(gè)最近鄰對(duì)象的相似性度量的計(jì)算量來(lái)提高分類(lèi)效率。余鷹等[5]利用變精度粗糙集處理數(shù)據(jù)集，計(jì)算新樣本集的歸屬區(qū)域，降低分類(lèi)的代價(jià)，提高分類(lèi)的效率。而在對(duì)數(shù)據(jù)集進(jìn)行屬性簡(jiǎn)約時(shí)，如何對(duì)原始特征集進(jìn)行判斷，得到最優(yōu)的評(píng)估子集，在不降低分類(lèi)精確度的前提下，利用這些評(píng)估子集更快的得到分類(lèi)結(jié)果，這也是目前研究的一個(gè)熱點(diǎn)，像陳珠英等[6]應(yīng)用線(xiàn)性回歸在2型糖尿病患者中剖析丙酮的影響因素，經(jīng)由相關(guān)系數(shù)判別各個(gè)因變量對(duì)丙酮濃度的影響強(qiáng)弱。

此外，KNN分類(lèi)算法通常采用歐式距離來(lái)計(jì)算訓(xùn)練集與待測(cè)樣本集之間的關(guān)系，但不同特征量對(duì)分類(lèi)結(jié)果準(zhǔn)確性影響是不同的。針對(duì)這一問(wèn)題，趙靜等[7]通過(guò)對(duì)現(xiàn)有的基于信息熵和區(qū)間距離的不確定性度量公式進(jìn)行優(yōu)化，但這種方法運(yùn)行效率有所下降；針對(duì)上述問(wèn)題，本文采用線(xiàn)性回歸簡(jiǎn)約數(shù)據(jù)集屬性，利用卡方距離替換歐式距離，然后根據(jù)得出的特征向量影響強(qiáng)度賦予權(quán)重實(shí)驗(yàn)表明，改進(jìn)后的算法與傳統(tǒng)的KNN算法相比，在特征識(shí)別性能方面有了一定的提高。

1 相關(guān)算法概述

1.1 KNN算法

KNN是一種懶惰式的機(jī)器學(xué)習(xí)算法，算法思想是：當(dāng)一個(gè)待分對(duì)象在訓(xùn)練集中與K個(gè)距離最近的實(shí)例中的max(K個(gè)樣本)屬于同一個(gè)類(lèi)別，那么就把該測(cè)試集數(shù)據(jù)分到大多數(shù)實(shí)例所屬類(lèi)別中。其判斷條件可以定義為公式：

fi(x)=max(k)，(i=1，2，…n) (1)

其中，i表示訓(xùn)練集中不同的對(duì)象，k表示K個(gè)數(shù)據(jù)樣本。

1.2 卡方距離

K近鄰算法中常用測(cè)距方法是歐式距離法，但是歐式距離只考慮各個(gè)屬性間的絕對(duì)距離，會(huì)忽視各特征屬性間的相對(duì)距離，而且會(huì)因?yàn)橥葯?quán)量數(shù)據(jù)集中不同屬性間的差異，導(dǎo)致不能滿(mǎn)足實(shí)際需求中的要求；而卡方距離能有效反映各個(gè)屬性間相對(duì)距離的變化，故利用線(xiàn)性回歸計(jì)算各個(gè)特征向量對(duì)分類(lèi)影響的強(qiáng)弱，從而彌補(bǔ)歐式距離對(duì)屬性間距離量化的不足之處。

卡方距離計(jì)算公式如下所示：

1.3 線(xiàn)性回歸

基于數(shù)理統(tǒng)計(jì)中的回歸分析方法，通過(guò)對(duì)兩個(gè)或者兩個(gè)以上自變量與一個(gè)因變量的相關(guān)分析，建立模型預(yù)測(cè)結(jié)果。這里利用數(shù)據(jù)集的多維屬性變量之間相互依賴(lài)的定量關(guān)系，然后根據(jù)變量之間的關(guān)系約簡(jiǎn)數(shù)據(jù)集屬性。

(1)評(píng)估模型的擬合程度時(shí)需要計(jì)算判定系數(shù)R2，其公式如下：

(2)選擇目標(biāo)屬性時(shí)可利用公式(4)計(jì)算Adjusted.R2(屬性間的權(quán)重系數(shù))，篩選出真正適合用于建模的屬性集合。其公式如下：

式中n表示屬性序列數(shù)，k表示變量數(shù)。

2 基于線(xiàn)性回歸的改進(jìn)KNN算法

本文首先利用線(xiàn)性回歸方法簡(jiǎn)約屬性集合，得到降維之后的較優(yōu)特征屬性集合，然后按照屬性間的決定系數(shù)計(jì)算得到的各個(gè)特征向量對(duì)分類(lèi)的貢獻(xiàn)度，賦予不同的屬性權(quán)值，卡方距離利用新的屬性權(quán)值，得到KNN改進(jìn)之后的樣本距離，然后判斷待分類(lèi)對(duì)象的歸屬。

2.1 改進(jìn)的KNN算法

基于線(xiàn)性回歸方法改進(jìn)的KNN算法的流程如圖1所示.

圖1 算法流程圖

具體步驟如下所示：

(1)首先將數(shù)據(jù)集進(jìn)行清洗預(yù)處理，即清除缺失值、噪聲數(shù)據(jù)、以及不一致的數(shù)據(jù)集，得到質(zhì)量較高的有效數(shù)據(jù)集。

(2)應(yīng)用線(xiàn)性回歸方法處理清洗后的數(shù)據(jù)，即通過(guò)公式(4)計(jì)算出數(shù)據(jù)集各個(gè)屬性之間的決定系數(shù)，從而篩選出合適的簡(jiǎn)約屬性集合。

(3)創(chuàng)建測(cè)試集，將步驟二中的數(shù)據(jù)集，采用隨機(jī)抽樣的方法，選擇3/4作為訓(xùn)練集X，剩余1/4作為測(cè)試集Y。

(4)給K隨機(jī)創(chuàng)建一個(gè)初始訓(xùn)練值。

(5)利用公式(3)比較特征向量對(duì)目標(biāo)變量的影響強(qiáng)弱，根據(jù)強(qiáng)弱確定屬性權(quán)重的值。

(6)運(yùn)用加權(quán)卡方距離計(jì)算測(cè)試集樣本與訓(xùn)練集樣本之間的加權(quán)距離。加權(quán)卡方距離公式如下：

式中，wi代表屬性i的特征權(quán)重。

(7)選取K個(gè)訓(xùn)練樣本，與測(cè)試集中待分類(lèi)對(duì)象比較，通過(guò)公式(1)得到待分類(lèi)對(duì)象的類(lèi)別。在改進(jìn)的KNN算法中，通過(guò)不斷調(diào)整K的取值，得到每一個(gè)K值所對(duì)應(yīng)的正確率，基于此正確率的折線(xiàn)圖得到適合簡(jiǎn)約屬性之后數(shù)據(jù)集的K值,如圖2所示。由折線(xiàn)圖可知，當(dāng)K=6的時(shí)候，算法的正確率達(dá)到最高值，之后隨著K的增加趨于平穩(wěn)，所以選取K值為6。

圖2 聚類(lèi)K值的最優(yōu)值分析

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

實(shí)驗(yàn)基于Python語(yǔ)言集成開(kāi)發(fā)平臺(tái)PyCharm配置的機(jī)器學(xué)習(xí)環(huán)境進(jìn)行研究。實(shí)驗(yàn)數(shù)據(jù)分別使用機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)UCI中的四個(gè)標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集和從甘肅省某醫(yī)院采集的乳腺癌臨床試驗(yàn)數(shù)據(jù)集。

UCI庫(kù)中的四個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集分別是breast cancer(乳腺癌)，heart disease(心臟病)，hepatitis(肝炎)和乳腺癌臨床數(shù)據(jù)集，關(guān)于這四個(gè)具體的數(shù)據(jù)集的相關(guān)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集的表現(xiàn)格式

采用改進(jìn)算法對(duì)訓(xùn)練集和測(cè)試集處理后，計(jì)算平均召回率(recall)、平均精確率(precision)和準(zhǔn)確率(accuracy)，作為評(píng)價(jià)分類(lèi)算法的性能指標(biāo)。

其中：ai表示在類(lèi)中準(zhǔn)確預(yù)測(cè)到的數(shù)目；bi表示測(cè)試樣本中為類(lèi)的總數(shù)目。

其中：ai公式(6)所示，ci表示預(yù)測(cè)為第i類(lèi)的測(cè)試樣本數(shù)目。

其中：a代表訓(xùn)練集樣本中預(yù)測(cè)準(zhǔn)確的樣本數(shù)量；b表示總的樣本數(shù)量。

實(shí)驗(yàn)數(shù)據(jù)集經(jīng)屬性簡(jiǎn)約之后的情況如表2所示。

表2 簡(jiǎn)約結(jié)果

由表2中的結(jié)果可以得出本文所改進(jìn)的KNN算法較傳統(tǒng)的KNN算法在簡(jiǎn)約屬性上具有微弱優(yōu)勢(shì)，說(shuō)明線(xiàn)性回歸在屬性簡(jiǎn)約上是有效的。

在保持K值相同的情況下，對(duì)測(cè)試數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，結(jié)果如表3、表4所示。

表3 K=6實(shí)驗(yàn)結(jié)果1

表4 K=6實(shí)驗(yàn)結(jié)果2

通過(guò)上述實(shí)驗(yàn)數(shù)據(jù)，當(dāng)K=6時(shí)，改進(jìn)KNN的方法在召回率率recall、精確率precision以及準(zhǔn)確率accuracy的判斷上都有了一定的提高，例如在心臟病數(shù)據(jù)集上，改進(jìn)KNN算法的查全率要比傳統(tǒng)KNN算法的查全率高1.5%，查準(zhǔn)率比傳統(tǒng)KNN算法高0.8%，精確度增加了1.4%，說(shuō)明改進(jìn)的KNN算法的各項(xiàng)指標(biāo)均優(yōu)于傳統(tǒng)的KNN算法。

4 結(jié)束語(yǔ)

KNN分類(lèi)算法數(shù)據(jù)挖掘中比較常用的、而且簡(jiǎn)單易懂的算法，在處理較大的數(shù)據(jù)集中具有明顯優(yōu)勢(shì)，本文對(duì)KNN算法的改進(jìn)模型，對(duì)消除冗余特征屬性和改善因數(shù)據(jù)分布不均勻有一定的積極作用。

但是改進(jìn)算法還存在以下問(wèn)題以待進(jìn)行進(jìn)一步研究：

(1)改進(jìn)算法測(cè)試的關(guān)于KNN的二分類(lèi)，而對(duì)多類(lèi)別的分類(lèi)檢測(cè)還需要進(jìn)一步的測(cè)試研究；

(2)改進(jìn)算法在處理更高維數(shù)據(jù)集的效率以及降低時(shí)間復(fù)雜度和空間復(fù)雜度問(wèn)題；

(3)在改進(jìn)KNN中如何準(zhǔn)確根據(jù)影響強(qiáng)弱得到具體屬性權(quán)值也是下一步研究的方向。