一種基于SMOTE的不均衡樣本KNN分類方法*

林泳昌， 朱曉姝

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

0 引言

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

1 材料與方法

1.1 邏輯回歸

邏輯回歸通過構建損失函數，并進行優化，迭代，求解出最優的模型參數，最后得到邏輯回歸分類模型。其方法如下[9]：

步驟1：隨機初始化W和b，利用公式(1)計算預測標簽。

Z=WTX+b，

(1)

其中，Z為預測結果，W為權重矩陣，X為特征矩陣，b為偏移量。

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

(2)

其中，m為樣本數，a(i)為樣本i的真實標簽，y(i)為樣本i的預測標簽。

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

(3)

(4)

其中，α為學習率。

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

1.2 KNN方法

KNN是一個簡單而經典的機器學習分類方法，通過度量待分類樣本和已知類別樣本之間的距離(一般使用歐氏距離)，對樣本進行分類。其方法如下[10]：

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

(5)

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

步驟3：選取前K個距離最近的鄰居樣本點。

步驟4：統計K個最近的鄰居樣本點分別屬于每個類別的個數。

步驟5：將K個鄰居樣本點里出現頻率最高的類別，作為該樣本點的預測類別。

可以看出，當數據樣本不均衡時，KNN方法預測結果會偏向于樣本數占優類。

1.3 SMOTE

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

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

SMOTE的步驟如下[8]：

步驟1：在少數樣本集中，對于少數類的樣本x，利用公式(5)計算x到其他所有樣本的歐氏距離，得到K個最近鄰點。

步驟2：通過設置采樣比例，得到采樣倍率N，并對每一個少數類樣本x，從其K近鄰中隨機選取近鄰樣本y。

步驟3：對于近鄰樣本y和樣本x，通過計算公式(6)，構建新樣本。

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

(6)

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

1.4 KSID方法

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

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

步驟2：構建邏輯回歸模型。將經過步驟1采樣后的訓練集放入邏輯回歸模型，訓練其正則化懲罰項、學習率等參數。并使用訓練好的邏輯回歸模型，對訓練集進行預測。

步驟3：生成KNN模型的訓練集并利用SMOTE均衡化。將步驟2中預測為正樣本的數據集，作為KNN模型的訓練集，并使用SMOTE進行采樣，使得訓練集的正負樣本均衡。

步驟4：構建KNN模型。使用步驟3輸出的訓練集，訓練KNN模型的參數K，并得到模型結果。

步驟5：預測測試集標簽。把測試集放入步驟2構建的邏輯回歸模型預測，將預測為正樣本的數據放入步驟4構建的KNN模型預測，并得到預測結果；最后將KNN模型預測標簽與邏輯回歸模型預測為負樣本的標簽合并，得到測試集的預測標簽。

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

算法1：KSID算法

Begin

輸入：訓練數據x_train,訓練標簽y_train，近鄰數K，倍率N

輸出：新樣本類別y_pred

0：將x_train、y_train、K、N傳入SMOTE得到數據集newdata

1：將newdata傳入邏輯回歸方法得到預測結果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得到數據集newdata1

5：將newdata1傳入邏輯回歸方法得到預測結果y_true_pred

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

7：輸出結果y_pred

End

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

1.5 實驗數據來源

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

表1 實驗數據集Table 1 List of the data sets

(7)

1.6 實驗環境

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

1.7 實驗參數設置

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

1.8 實驗方案設計

將本文提出的KSID方法分別與邏輯回歸方法、KNN方法、SVM決策樹方法相比較?；?個數據集分別測試這4種方法的準確率、精確度、查全率、F1值、運行時間等性能指標，并分析實驗結果。

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

2 結果與分析

2.1 評價指標

在機器學習的分類方法中，常常使用準確率來衡量模型的分類效果。但對于不均衡數據集，還需要使用查全率、查準率、F1值等指標評價模型性能。這4種評價指標都是基于表2的正負樣本混淆矩陣。

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

其中TP和TN分別表示正確分類的正類和負類的樣本數量；FN和FP分別表示錯誤分類的正類和負類的樣本數量。

1)準確率(Accuracy)

準確率是衡量模型的總體分類效果的指標，準確率越高模型分類效果越好[13]：

(8)

2)精確率(Precision)

精確率是模型預測的正樣本在真實正樣本中所占的比例[11]：

(9)

3)查全率(Recall)

(10)

4)F1值(F1 score)

F1值是精確率和查全率的調和值，其結果更接近兩者較小的值[11]：

(11)

2.2 準確率測試實驗

對6個數據集進行準確率測試。從表3的測試結果可以看出，KSID方法在6個數據集上準確率的均值基本大于其他3種方法，即KSID的分類性優于其他3種方法，特別是員工離職數據集，比KNN方法提高了4.2%。這是因為KSID使用邏輯回歸進行第一次分類，再使用KNN對第一次分類預測為正樣本的數據進行第二次分類，進而提高了模型的準確率。但對于樣本量和特征維度較大的廣告點擊數據集，KSID方法使用SMOTE采樣產生較多的偽樣本，影響模型對原始樣本的分類準確率，使得KSID方法的分類準確率低于SVM決策樹方法。

表3 準確率測試結果Table 3 Results of accuracy test results

2.3 精確率測試實驗

對6個數據集進行精確率測試，其測試結果如表4所示。

表4 精確率測試結果Table 4 Results of precision test results

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

2.4 查全率測試實驗

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

表5 查全率測試結果Table 5 Resules of recall test results

2.5 F1 值測試實驗

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

表6 F1值的測試結果Table 6 Resules of F1 score test results

2.6 運行時間測試實驗

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

表7 運行時間測試結果Table 7 Run time of test results

3 結論

針對KNN方法對樣本不均衡數據集的預測偏差問題，本文通過使用SOMTE方法對少數樣本類的訓練集進行采樣操作，使得訓練集的正負樣本數量保持基本一致，從而改善了不均衡數據對KNN模型預測性能的影響。對比實驗結果發現，基于SMOTE改進后的KSID方法，比邏輯回歸方法、原始KNN方法、SVM決策樹方法的分類效果更優，對于較大數據集其時間復雜度更小。但對于樣本量和特征維度較大的數據集(如廣告點擊數據集)，KSID方法使用SMOTE采樣會產生較多的偽樣本，導致影響了模型對原始樣本的分類性能，使得KSID方法的分類性能低于SVM決策樹方法。