林泳昌， 朱曉姝

(玉林師范學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西玉林 537000)

0 引言

K近鄰(K-nearest Neighbor，KNN)方法由Cover和Hart于1968年提出，使用節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息構(gòu)建最近鄰圖來(lái)做分類(lèi)，是機(jī)器學(xué)習(xí)中常用、簡(jiǎn)單、易實(shí)現(xiàn)的二分類(lèi)方法。當(dāng)前，很多數(shù)據(jù)集具有不均衡性，比如信用卡欺詐、用戶(hù)違約預(yù)測(cè)數(shù)據(jù)集等。這導(dǎo)致KNN方法面臨一個(gè)挑戰(zhàn)：當(dāng)數(shù)據(jù)樣本不均衡時(shí)，KNN方法的預(yù)測(cè)結(jié)果會(huì)偏向于樣本數(shù)占優(yōu)類(lèi)。為了提高KNN方法的運(yùn)行效率、分類(lèi)效果等性能，很多學(xué)者對(duì)KNN方法進(jìn)行了優(yōu)化。比如沈焱萍等[1]提出基于元優(yōu)化的KNN方法。王軼凡[2]提出數(shù)據(jù)時(shí)效性的高效KNN方法。王志華等[3]提出基于改進(jìn)K-modes聚類(lèi)的KNN方法。張萬(wàn)楨等[4]提出環(huán)形過(guò)濾器的K值自適應(yīng)KNN方法。余鷹等[5]使用變精度粗糙集上下近似概念，增強(qiáng)了KNN方法的魯棒性。樊存佳等[6]采用改進(jìn)的K-Medoids聚類(lèi)方法裁剪對(duì)KNN分類(lèi)貢獻(xiàn)小的訓(xùn)練樣本，提高KNN的分類(lèi)精度。羅賢鋒等[7]使用K-Medoids方法對(duì)文本訓(xùn)練集進(jìn)行聚類(lèi)，解決了傳統(tǒng)KNN方法在文本訓(xùn)練集過(guò)大時(shí)存在速度慢的問(wèn)題。針對(duì)不均衡數(shù)據(jù)集，KNN方法預(yù)測(cè)結(jié)果會(huì)偏向于樣本數(shù)占優(yōu)類(lèi)的問(wèn)題，本文將Synthetic Minority Oversampling Technique(SMOTE)[8]和邏輯回歸引入KNN方法中，提出了一種基于SMOTE的KNN不均衡樣本分類(lèi)優(yōu)化方法(A Modified KNN Algorithm based on SMOTE for Classification Imbalanced Data，KSID)。使用SMOTE改進(jìn)邏輯回歸方法或改進(jìn)KNN方法，雖然可以提高不均衡數(shù)據(jù)集的查全率，但也會(huì)很明顯地降低模型查準(zhǔn)率；特別是在大數(shù)據(jù)集上，使用SMOTE會(huì)大大增加KNN方法的時(shí)間復(fù)雜度。因此，本文先使用SMOTE對(duì)訓(xùn)練集做上采樣，并使用訓(xùn)練過(guò)的邏輯回歸對(duì)該均衡的訓(xùn)練集預(yù)測(cè)分類(lèi)，再利用SMOTE和KNN對(duì)預(yù)測(cè)為正樣本的數(shù)據(jù)集做上采樣并預(yù)測(cè)分類(lèi)，從而訓(xùn)練得到新的KNN模型，以有效地解決SMOTE會(huì)降低模型查準(zhǔn)率和增加時(shí)間復(fù)雜度的問(wèn)題。

1 材料與方法

1.1 邏輯回歸

邏輯回歸通過(guò)構(gòu)建損失函數(shù)，并進(jìn)行優(yōu)化，迭代，求解出最優(yōu)的模型參數(shù)，最后得到邏輯回歸分類(lèi)模型。其方法如下[9]：

步驟1：隨機(jī)初始化W和b，利用公式(1)計(jì)算預(yù)測(cè)標(biāo)簽。

Z=WTX+b，

(1)

其中，Z為預(yù)測(cè)結(jié)果，W為權(quán)重矩陣，X為特征矩陣，b為偏移量。

步驟2：利用公式(2)計(jì)算模型的損失函數(shù)。

(2)

其中，m為樣本數(shù)，a(i)為樣本i的真實(shí)標(biāo)簽，y(i)為樣本i的預(yù)測(cè)標(biāo)簽。

步驟3：利用公式(3)(4)計(jì)算W、b的梯度并更新。

(3)

(4)

其中，α為學(xué)習(xí)率。

步驟4：迭代步驟1到步驟3，直到最小化損失函數(shù)J(a,b)。

1.2 KNN方法

KNN是一個(gè)簡(jiǎn)單而經(jīng)典的機(jī)器學(xué)習(xí)分類(lèi)方法，通過(guò)度量待分類(lèi)樣本和已知類(lèi)別樣本之間的距離(一般使用歐氏距離)，對(duì)樣本進(jìn)行分類(lèi)。其方法如下[10]：

步驟1：根據(jù)公式(5)計(jì)算樣本點(diǎn)到所有樣本點(diǎn)的歐氏距離(d)。

(5)

步驟2：根據(jù)歐式距離的大小對(duì)樣本進(jìn)行排序(一般是升序)。

步驟3：選取前K個(gè)距離最近的鄰居樣本點(diǎn)。

步驟4：統(tǒng)計(jì)K個(gè)最近的鄰居樣本點(diǎn)分別屬于每個(gè)類(lèi)別的個(gè)數(shù)。

步驟5：將K個(gè)鄰居樣本點(diǎn)里出現(xiàn)頻率最高的類(lèi)別，作為該樣本點(diǎn)的預(yù)測(cè)類(lèi)別。

可以看出，當(dāng)數(shù)據(jù)樣本不均衡時(shí)，KNN方法預(yù)測(cè)結(jié)果會(huì)偏向于樣本數(shù)占優(yōu)類(lèi)。

1.3 SMOTE

SMOTE是常用于樣本不均衡數(shù)據(jù)集的采樣方法[8]。其思路是通過(guò)合成一些少數(shù)類(lèi)樣本，增加少數(shù)類(lèi)樣本個(gè)數(shù)，使得樣本均衡。SMOTE的生成策略：對(duì)于每個(gè)少數(shù)類(lèi)樣本x，從它的最近鄰樣本中隨機(jī)選一個(gè)樣本y，然后在x、y屬性的歐氏距離之間隨機(jī)合成新的少數(shù)類(lèi)樣本，其工作原理如圖1所示。

圖1 SMOTE工作原理Fig.1 Working principle of the SMOTE method

SMOTE的步驟如下[8]：

步驟1：在少數(shù)樣本集中，對(duì)于少數(shù)類(lèi)的樣本x，利用公式(5)計(jì)算x到其他所有樣本的歐氏距離，得到K個(gè)最近鄰點(diǎn)。

步驟2：通過(guò)設(shè)置采樣比例，得到采樣倍率N，并對(duì)每一個(gè)少數(shù)類(lèi)樣本x，從其K近鄰中隨機(jī)選取近鄰樣本y。

步驟3：對(duì)于近鄰樣本y和樣本x，通過(guò)計(jì)算公式(6)，構(gòu)建新樣本。

L=x+rand(0,1)×x-y，

(6)

其中，x表示少數(shù)樣本，y表示x的最近鄰樣本。

1.4 KSID方法

將SMOTE和邏輯回歸引入KNN方法中，提出了一種基于SMOTE的KNN不均衡樣本分類(lèi)優(yōu)化方法(KSID)。針對(duì)數(shù)據(jù)樣本不均衡對(duì)KNN二分類(lèi)器分類(lèi)效果影響的問(wèn)題，使用SMOTE進(jìn)行采樣，增加少數(shù)樣本的數(shù)量，并消除數(shù)據(jù)樣本不均衡對(duì)KNN分類(lèi)效果的影響。KSID方法描述如下：

步驟1：使用SMOTE將不均衡訓(xùn)練集均衡化。將不均衡數(shù)據(jù)集按照一定的比例劃分為訓(xùn)練集和測(cè)試集。使用SMOTE對(duì)訓(xùn)練集中的每個(gè)少數(shù)樣本，計(jì)算其與其他少數(shù)樣本的歐氏距離，得到K個(gè)近鄰樣本點(diǎn)。通過(guò)設(shè)置采樣比例，隨機(jī)選取少數(shù)類(lèi)樣本，對(duì)每一個(gè)選出的少數(shù)類(lèi)樣本，利用公式(6)構(gòu)建新樣本，一直迭代到訓(xùn)練集的正負(fù)樣本均衡終止。

步驟2：構(gòu)建邏輯回歸模型。將經(jīng)過(guò)步驟1采樣后的訓(xùn)練集放入邏輯回歸模型，訓(xùn)練其正則化懲罰項(xiàng)、學(xué)習(xí)率等參數(shù)。并使用訓(xùn)練好的邏輯回歸模型，對(duì)訓(xùn)練集進(jìn)行預(yù)測(cè)。

步驟3：生成KNN模型的訓(xùn)練集并利用SMOTE均衡化。將步驟2中預(yù)測(cè)為正樣本的數(shù)據(jù)集，作為KNN模型的訓(xùn)練集，并使用SMOTE進(jìn)行采樣，使得訓(xùn)練集的正負(fù)樣本均衡。

步驟4：構(gòu)建KNN模型。使用步驟3輸出的訓(xùn)練集，訓(xùn)練KNN模型的參數(shù)K，并得到模型結(jié)果。

步驟5：預(yù)測(cè)測(cè)試集標(biāo)簽。把測(cè)試集放入步驟2構(gòu)建的邏輯回歸模型預(yù)測(cè)，將預(yù)測(cè)為正樣本的數(shù)據(jù)放入步驟4構(gòu)建的KNN模型預(yù)測(cè)，并得到預(yù)測(cè)結(jié)果；最后將KNN模型預(yù)測(cè)標(biāo)簽與邏輯回歸模型預(yù)測(cè)為負(fù)樣本的標(biāo)簽合并，得到測(cè)試集的預(yù)測(cè)標(biāo)簽。

算法1給出了KSID算法的形式描述。

算法1：KSID算法

Begin

輸入：訓(xùn)練數(shù)據(jù)x_train,訓(xùn)練標(biāo)簽y_train，近鄰數(shù)K，倍率N

輸出：新樣本類(lèi)別y_pred

0：將x_train、y_train、K、N傳入SMOTE得到數(shù)據(jù)集newdata

1：將newdata傳入邏輯回歸方法得到預(yù)測(cè)結(jié)果y_pred

2：y_true=-y_train[y_pred==1]

3：x_true=-x_trian[:,y_pred==1]

4：將x_true、y_true、K、N傳入SMOTE得到數(shù)據(jù)集newdata1

5：將newdata1傳入邏輯回歸方法得到預(yù)測(cè)結(jié)果y_true_pred

6：y_pred[y_pred==0].append(y_true_pred) #合并結(jié)果

7：輸出結(jié)果y_pred

End

KSID方法雖然將訓(xùn)練集通過(guò)SMOTE采樣，可以消除數(shù)據(jù)不均衡性,但是SMOTE對(duì)訓(xùn)練集均衡化后，產(chǎn)生合成的正樣本影響分類(lèi)性能。針對(duì)這個(gè)問(wèn)題，將邏輯回歸預(yù)測(cè)的正樣本，繼續(xù)使用KNN進(jìn)行預(yù)測(cè)，進(jìn)而提高分類(lèi)性能。且KSID方法先使用邏輯回歸模型預(yù)測(cè)出大量正確的負(fù)樣本，再使用KNN預(yù)測(cè)少量的正樣本，可以有效降低模型計(jì)算復(fù)雜度，減少模型計(jì)算時(shí)間。

1.5 實(shí)驗(yàn)數(shù)據(jù)來(lái)源

本文實(shí)驗(yàn)數(shù)據(jù)集為信用卡欺詐數(shù)據(jù)集、員工離職數(shù)據(jù)集、企業(yè)誠(chéng)信數(shù)據(jù)集、廣告點(diǎn)擊預(yù)測(cè)數(shù)據(jù)集、用戶(hù)違約數(shù)據(jù)集、疝氣病癥預(yù)測(cè)病馬是否死亡數(shù)據(jù)集，前5個(gè)數(shù)據(jù)集均來(lái)源于DC競(jìng)賽網(wǎng)(https://www.dcjingsai.com/)，第6個(gè)數(shù)據(jù)集來(lái)源于百度百科網(wǎng)。數(shù)據(jù)集的具體描述如表1所示，其中樣本不均衡率計(jì)算公式如下[11]：

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 List of the data sets

(7)

1.6 實(shí)驗(yàn)環(huán)境

使用notebook編譯軟件、Python 3.6語(yǔ)言編程，分別使用sklearn里的KNN方法、邏輯回歸方法和imblearn包中的SMOTE。計(jì)算機(jī)硬件配置為8 GB內(nèi)存、64位操作系統(tǒng)、i5-6300HQ處理器。

1.7 實(shí)驗(yàn)參數(shù)設(shè)置

訓(xùn)練集和測(cè)試集劃分比例為7∶3，隨機(jī)種子設(shè)置為0；邏輯回歸設(shè)置fit_intercep為T(mén)rue；SMOTE中的K取值為5，SMOTE采樣倍率設(shè)置為5；支持向量機(jī)(SVM)決策樹(shù)方法[12]最大深度設(shè)置為4；邏輯回歸模型和KNN模型都使用3折交叉驗(yàn)證。

1.8 實(shí)驗(yàn)方案設(shè)計(jì)

將本文提出的KSID方法分別與邏輯回歸方法、KNN方法、SVM決策樹(shù)方法相比較?；?個(gè)數(shù)據(jù)集分別測(cè)試這4種方法的準(zhǔn)確率、精確度、查全率、F1值、運(yùn)行時(shí)間等性能指標(biāo)，并分析實(shí)驗(yàn)結(jié)果。

當(dāng)前PPD發(fā)病率正逐年增加，臨床上主要表現(xiàn)有悲傷、落淚、情緒不穩(wěn)定、睡眠障礙等。臨床上往往需要針對(duì)患病的神經(jīng)衰弱、抑郁癥及神經(jīng)官能癥等進(jìn)行對(duì)癥治療，但是后期效果不佳，雖然新的抗抑郁藥物不斷出現(xiàn)，但是多數(shù)價(jià)格昂貴，且存在較多不良反應(yīng)，哺乳期婦女服用這類(lèi)藥物可能會(huì)有損嬰兒健康，因此，PPD的治療成為業(yè)界人士研究的重點(diǎn)課題之一。

2 結(jié)果與分析

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

在機(jī)器學(xué)習(xí)的分類(lèi)方法中，常常使用準(zhǔn)確率來(lái)衡量模型的分類(lèi)效果。但對(duì)于不均衡數(shù)據(jù)集，還需要使用查全率、查準(zhǔn)率、F1值等指標(biāo)評(píng)價(jià)模型性能。這4種評(píng)價(jià)指標(biāo)都是基于表2的正負(fù)樣本混淆矩陣。

表2 混淆矩陣Table 2 Confusion matrix of samples

其中TP和TN分別表示正確分類(lèi)的正類(lèi)和負(fù)類(lèi)的樣本數(shù)量；FN和FP分別表示錯(cuò)誤分類(lèi)的正類(lèi)和負(fù)類(lèi)的樣本數(shù)量。

1)準(zhǔn)確率(Accuracy)

準(zhǔn)確率是衡量模型的總體分類(lèi)效果的指標(biāo)，準(zhǔn)確率越高模型分類(lèi)效果越好[13]：

(8)

2)精確率(Precision)

精確率是模型預(yù)測(cè)的正樣本在真實(shí)正樣本中所占的比例[11]：

(9)

3)查全率(Recall)

(10)

4)F1值(F1 score)

F1值是精確率和查全率的調(diào)和值，其結(jié)果更接近兩者較小的值[11]：

(11)

2.2 準(zhǔn)確率測(cè)試實(shí)驗(yàn)

對(duì)6個(gè)數(shù)據(jù)集進(jìn)行準(zhǔn)確率測(cè)試。從表3的測(cè)試結(jié)果可以看出，KSID方法在6個(gè)數(shù)據(jù)集上準(zhǔn)確率的均值基本大于其他3種方法，即KSID的分類(lèi)性?xún)?yōu)于其他3種方法，特別是員工離職數(shù)據(jù)集，比KNN方法提高了4.2%。這是因?yàn)镵SID使用邏輯回歸進(jìn)行第一次分類(lèi)，再使用KNN對(duì)第一次分類(lèi)預(yù)測(cè)為正樣本的數(shù)據(jù)進(jìn)行第二次分類(lèi)，進(jìn)而提高了模型的準(zhǔn)確率。但對(duì)于樣本量和特征維度較大的廣告點(diǎn)擊數(shù)據(jù)集，KSID方法使用SMOTE采樣產(chǎn)生較多的偽樣本，影響模型對(duì)原始樣本的分類(lèi)準(zhǔn)確率，使得KSID方法的分類(lèi)準(zhǔn)確率低于SVM決策樹(shù)方法。

表3 準(zhǔn)確率測(cè)試結(jié)果Table 3 Results of accuracy test results

2.3 精確率測(cè)試實(shí)驗(yàn)

對(duì)6個(gè)數(shù)據(jù)集進(jìn)行精確率測(cè)試，其測(cè)試結(jié)果如表4所示。

表4 精確率測(cè)試結(jié)果Table 4 Results of precision test results

從表4可以看出，KSID方法在6個(gè)數(shù)據(jù)集上精確率的均值基本大于其他3種方法，即KSID模型對(duì)正樣本預(yù)測(cè)更準(zhǔn)確，如信用卡欺詐數(shù)據(jù)比KNN方法提升了21%、員工離職數(shù)據(jù)比KNN方法提高了24.4%等。這是因?yàn)镵SID使用KNN模型對(duì)正樣本進(jìn)行二次分類(lèi)，進(jìn)而提高了模型的精確率。但對(duì)于企業(yè)誠(chéng)信和廣告點(diǎn)擊等數(shù)據(jù)集，由于KSID使用邏輯回歸進(jìn)行第一次分類(lèi)，而邏輯回歸無(wú)法識(shí)別正樣本(其精確率為0)，影響了模型的分類(lèi)精確率，使得KSID方法的分類(lèi)精確率低于SVM決策樹(shù)方法。

2.4 查全率測(cè)試實(shí)驗(yàn)

對(duì)6個(gè)數(shù)據(jù)集進(jìn)行查全率測(cè)試，從表5的測(cè)試結(jié)果可以看出，KSID方法在6個(gè)數(shù)據(jù)集上查全率的均值基本大于其他3種方法，即KSID模型對(duì)正樣本的召回?cái)?shù)量更多，如在信用卡欺詐數(shù)據(jù)集中，KSID模型的查全率比邏輯回歸模型高23.8%、比KNN模型高13.6%等。這是因?yàn)镵SID使用SMOTE將不均衡數(shù)據(jù)集均衡化，改進(jìn)KNN方法對(duì)不均衡數(shù)據(jù)集分類(lèi)偏向的缺點(diǎn)，進(jìn)而提高了模型的查全率。但對(duì)于員工離職和廣告點(diǎn)擊等數(shù)據(jù)集，由于KSID使用KNN對(duì)正樣本進(jìn)行二次分類(lèi)，而KNN對(duì)正樣本查全率不高，影響了模型的分類(lèi)查全率，使得KSID方法的分類(lèi)查全率低于邏輯回歸和SVM決策樹(shù)方法。

表5 查全率測(cè)試結(jié)果Table 5 Resules of recall test results

2.5 F1 值測(cè)試實(shí)驗(yàn)

對(duì)6種數(shù)據(jù)集進(jìn)行F1值測(cè)試，從表6的測(cè)試結(jié)果可以看出，KSID方法在6個(gè)數(shù)據(jù)集上F1值的均值基本大于其他3種方法，如用戶(hù)違約數(shù)據(jù)集KSID模型的F1值比邏輯回歸模型高6.4%、比KNN模型高18.3%、比SVM決策樹(shù)模型高28.2%等。但對(duì)于廣告點(diǎn)擊數(shù)據(jù)集，由于KSID使用邏輯回歸和KNN進(jìn)行第一、第二次分類(lèi)，而KNN和邏輯回歸對(duì)正樣本識(shí)別率不高(其F1值較低)，導(dǎo)致影響了模型的分類(lèi)F1值，使得KSID方法的分類(lèi)F1值低于SVM決策樹(shù)方法。

表6 F1值的測(cè)試結(jié)果Table 6 Resules of F1 score test results

2.6 運(yùn)行時(shí)間測(cè)試實(shí)驗(yàn)

對(duì)6種數(shù)據(jù)集進(jìn)行運(yùn)行時(shí)間測(cè)試，從表7的測(cè)試結(jié)果可以看出，對(duì)于小數(shù)據(jù)集，KNN方法的運(yùn)行時(shí)間小，但對(duì)于大數(shù)據(jù)集(比如用卡欺詐數(shù)據(jù)集)，KSID方法時(shí)間復(fù)雜度明顯比KNN方法小得多，如信用卡欺詐數(shù)據(jù)集KSID運(yùn)行時(shí)間比KNN快266.545 s等。這是因?yàn)镵SID方法先使用邏輯回歸方法預(yù)測(cè)了量大的負(fù)樣本，再使用KNN方法預(yù)測(cè)量少的正樣本，進(jìn)而降低了方法時(shí)間復(fù)雜度。此外，邏輯回歸方法總的運(yùn)行時(shí)間最少，但它在4個(gè)預(yù)測(cè)性能指標(biāo)上都是最低。KSID既能獲得最好的預(yù)測(cè)性能，也能極大地降低運(yùn)行時(shí)間。

表7 運(yùn)行時(shí)間測(cè)試結(jié)果Table 7 Run time of test results

3 結(jié)論

針對(duì)KNN方法對(duì)樣本不均衡數(shù)據(jù)集的預(yù)測(cè)偏差問(wèn)題，本文通過(guò)使用SOMTE方法對(duì)少數(shù)樣本類(lèi)的訓(xùn)練集進(jìn)行采樣操作，使得訓(xùn)練集的正負(fù)樣本數(shù)量保持基本一致，從而改善了不均衡數(shù)據(jù)對(duì)KNN模型預(yù)測(cè)性能的影響。對(duì)比實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，基于SMOTE改進(jìn)后的KSID方法，比邏輯回歸方法、原始KNN方法、SVM決策樹(shù)方法的分類(lèi)效果更優(yōu)，對(duì)于較大數(shù)據(jù)集其時(shí)間復(fù)雜度更小。但對(duì)于樣本量和特征維度較大的數(shù)據(jù)集(如廣告點(diǎn)擊數(shù)據(jù)集)，KSID方法使用SMOTE采樣會(huì)產(chǎn)生較多的偽樣本，導(dǎo)致影響了模型對(duì)原始樣本的分類(lèi)性能，使得KSID方法的分類(lèi)性能低于SVM決策樹(shù)方法。