基于特征權重與K-Medoids 算法結合的非均衡數據處理方法*

楊 棟 程 科 張 晨 張瑞祥

（江蘇科技大學計算機學院 鎮江 212100）

1 引言

非均衡數據集中不同類別之間數據樣本分布不均衡，其中多數類樣本屬于某種類別，而余下的屬于其它類別。這些數據廣泛地存在于醫療診斷［1］、信息檢索系統［2］、欺詐性電話的檢測［3］、直升機故障檢測［4］等領域中，并且它們都有一個共同的特性，即數據的類別、數量不均衡。非均衡數據處理方法的出現，使得數據挖掘技術向前邁進了一大步的同時也極大地推動了大數據的發展，提高了大數據的市場價值。

非均衡數據處理的方法主要分為兩種：一是基于樣本數據的處理，通過重采樣等方法，對原始數據增加或者減少，從而使得非均衡數據轉化為均衡數據；另一種則是基于算法的處理，通過改進傳統的分類學習算法。目前基于樣本數據處理的方法通常存在會引入新的噪音數據同時還會改變原始數據的分布等問題，而現有的基于算法的處理通常會有算法過于復雜、計算復雜度高等問題［5］。本文主要研究的是欠采樣方法，基于上述問題，提出了一種基于特征權重與K-Medoids 算法相結合的欠采樣處理方法，其關注于數據處理方面并且考慮了樣本數據特征權重值大小的問題。

2 相關工作

2.1 重采樣算法研究

欠采樣方法［6］就是在樣本數據多數類數據中對一部分樣本數據進行增刪處理，使之與少數類樣本數量相對平衡，從而轉化為均衡分類問題，常用的方法主要有隨機欠采樣方法、Hart提出的緊縮最近鄰規則、Wilson提出的Tomek links方法等。欠采樣方法即是去除一部分樣本數據，導致其刪去了所具有的一部分特征屬性，從而影響到了不平衡數據分類效果。

過采樣方法則是增加少數類的數據，其中最簡單的一種就是隨機過采樣算法；其中最著名的算法就是文獻［7］中的SMOTE算法。文獻［8］中，Borderline-SMOTE 方法則是對先前算法的改進；Sáez［9］等提出了一種名為SMOTE-IPF 的框架，經實驗表明該框架具有很好的效率；KE CHENG［10］等提出具有噪聲過濾的分組SMOTE 改進算法，其采用高斯混合模型準確估計了每個訓練實例的概率密度，進一步發現和過濾噪聲實例，并根據實例的分布特征將實例劃分為不同的組，以進行個體采樣。

上述方法在數據層面上對于非均衡數據分類問題得以解決，提高了樣本的分類精確度，但都使得數據的特征分布發生改變以及其他問題，這些問題對整體樣本的分類結果造成了一定影響。

2.2 K中心點算法（K-Medoids）的研究

K-Means算法是一種基于樣本間相似性度量的間接聚類算法，可以將數據集劃分成不同的簇［11］。該算法實現的代碼簡單、訓練效果快速［12］。但是，該算法也有聚類個數難以確定等缺陷［13］。而K 中心點聚類（K-Medoids）算法則是提出了新的選取質點方式，很好地解決了上述問題，該算法使用不同于相對誤差標準的絕對誤差標準來定義一個分類簇中緊密程度變化。每次選取的質點都是從其聚類方法的樣本點中選取，選取當該樣本點成為新質點后能提高各分類簇的聚類質量的樣本點作為新的質點，因而各簇的樣本更為緊靠一起［14］。

3 基于特征權重與K 中心點算法結合的欠采樣方法

在數據分類過程中，并不是所有的數據樣本都是重要的，因為其中有一部分樣本數據容易被學習，對于新樣本的合成提供的信息少。而上述提到的方法的缺點就是未能將全部樣本數據的特征權重納入分類算法或者采樣方法中。因此，本文提出了一種基于特征權重與K 中心點聚類算法（K-Medoids）相結合的欠采樣方法（Under-sampling method based on the feature weights and K-Medoids，UsfwKM），其在對不平衡數據分類決策時，起主要作用的樣本特征的權重值進行增大，又同時減小了對分類決策時起次要作用的樣本特征的權重值，又結合K 中心點算法，抽樣出的數據對于分類決策會更加有用，并且提高分類器對于不平衡數據的分類性能。

3.1 提出的UsfwKM方法

該方法分為兩部分，一是對樣本數據特征權重值提取，二是基于特征權重的K-Medoids 聚類。如圖1 是UsfwKM 方法的流程圖，其中，D表示樣本集；DMi定義為樣本集中的少數類樣本；DMa定義為其中多數類樣本；少數類樣本的第i特征與多數類樣本的第i特征之間的相關系數定義為Corri；Wi定義為第i特征值的權重值；Masizei定義為通過K中心點聚類算法得到的第i簇中的多數類樣本的數量，Misizei定義為通過K 中心點聚類算法得到的第i簇中的少數類樣本的數量；Db表示均衡數據。

圖1 UsfwKM方法流程圖

該欠采樣方法的具體實現步驟如下。

1）設定一個非均衡數據D={(x1,y1),(x2,y2),(x3,y3),…(xn,yn)}，（其中，xi表示為第i個樣本，yi是指其所屬類別，n為樣本數量。）按照數據的標簽分類為少數類數據DMi、多數類數據DMa，對于少數類樣本中DMi的第i個特征，計算其與多數類樣本DMa的第i個特征之間的皮爾遜相關系數，因此可以得到其相關系數為Corri。

2）針對計算出的第i個特征之間的相關系數，計算第i個特征所擁有的權重值，Wi的計算公式為Wi=1-Corri，上述過程中得到具有特征權重樣本集Dw，然后用K-Medoids 方法對具有特征權重的樣本集Dw進行聚類，得到k個簇C1,C2,…Ck。

3）由式（1）計算得出各簇中應抽取的多數類樣本數量：

其中，Majsize定義為原始訓練集D中多數類樣本集的數量。

4）根據上步得到的CMadatasize，采用隨機采樣方法從多數類數據集中得到多數類樣本，然后再與D中全部的少數類樣本DMi相結合組成均衡數據樣本集。

3.2 數據特征權重值的選取

設訓練數據集為D={(x1,y1),(x2,y2),(x3,y3),…(xn,yn)}，其中第i個數據定義為為(xi,yi)，根據所擁有的標簽yi得出少數類樣本DMi與多數類樣本DMa。其分類方法的公式為

具體計算特征權重的步驟如下：

1）首先是數據樣本間的特征相關性系數Corri。先設各Fmii之間的皮爾遜相關系數為1，針對少數類樣本的第i特征Fmii，再計算其與多數類樣本的第i特征Fmai之間的相關系數Corri。由于在非均衡數據中多數類與少數類樣本數量有很大差距，所以本文將多數類樣本的第i特征Fmai分成若干個與少數類樣本數量相當的小集Fmai-j，并假設j有k個，然后分別計算Fmii與Fmai-j之間的相關系數，以求取平均值，平均值計算公式可以表示為

2）在計算樣本特征權重值時，如果多數類數據中的特征Fmai與少數類數據的特征Fmii相關程度較低，則說明此特征對于分類非常有用。特征權重Wi=corrcoef(Fmii,Fmii)-corri，corrcoef(Fmii,Fmii)值近似為1，所以可以默認為1，此時Wi=1-corri。W={W1，W2，…Wi,…Wm} ，m為數據集中的特征數目。

3.3 基于特征權重的K中心點聚類

1）根據第一步得到的特征權重W，將其與原始樣本D相組合，得到Dw，即Dw=D×W。

2）使用K-Medoids 方法對附有特征權重的數據集Dw聚類，得到k個簇，即C1,C2,…Ck，對于第i個簇Ci，其少數類樣本數量表示為Misizei，多數類樣本數量表示為Masizei。此時，對簇Ci對應的去特征權重值后的多數類樣本使用無放回抽樣方法抽取數量為CMadatasize的樣本數據量，其計算的公式為

因而得到與少數類數據樣本數量相等的多數類數據Dsample，最終組成的均衡數據集為Db=Dsample+DMi。實驗需求可以多次欠采樣得到多個均衡數據Db。

4 實驗結果及分析

4.1 實驗數據集描述

本實驗采用的標準數據集來源于KEEL 高度不平衡數據集庫，數據集的不平衡率從一點幾到幾百不等，非常適合做非均衡數據分類的研究，對于本次實驗，隨機選擇其中六組數據集，其樣本對應的屬性如表1所示，表中IR表示其樣本數據的非均衡比。

表1 標準非均衡數據集介紹

4.2 實驗過程及結果分析

使用本文提出的UsfwKM 方法與隨機欠抽樣方法對其中選取的六個數據集進行采樣處理，對采樣得到的均衡數據使用樸素貝葉斯算法［15］、集成規則為Max Rule 方法［16］作為基準分類器進行測試。在實驗中，設K-Medoids 算法聚類為三個簇，實驗性能評估指標則采用AUC（Area Under the Curve）值［17］。使用上述非均衡數據集進行實驗，可分別測得本文所提出的欠采樣方法（UsfwKM）與已有方法的實驗結果如表2所示。

表2 經實驗測得的AUC值

由圖2 可以看出，基于本節結合的集成方法得到的分類結果相比于隨機欠采樣方法得到的分類結果在選取的六個標準非均衡數據集上性能均有較大的提升，并且AUC指標值平均提升了約0.10。

通過上述實驗證明，本文提出的UsfwKM 方法將所有樣本特征權重值考慮到分類方法中，在與K中心點聚類方法相結合使用時抽樣得到的多數類數據更加適合于分類。通過實驗得到的柱形圖上可以清楚表明，在處理非均衡數據時能夠擁有更好的分類效果。

5 結語

在處理非均衡數據時，為了考慮各樣本的特征權重值，本論文提出了一種基于特征權重與K-Medoids 算法結合的非均衡數據處理欠采樣方法——UsfwKM算法。這是對特征權重賦值進行改進的一種方法，從而抽樣出更有利于分類決策的數據，通過將其與K-Medoids 算法相結合，用來構建非均衡數據處理的分類模型。選擇KEEL 公開標準數據集上的六組數據集進行實驗后，結果表明了本文提出的UsfwKM 方法提高了分類器對于非均衡數據的分類性能，分類效果較好，同時有較強的魯棒性。本文后續工作在于從非均衡數據算法的層面對現有集成規則進行改進來解決不平衡問題。