不平衡數(shù)據(jù)集上的Relief特征選擇算法*

菅小艷 韓素青 崔彩霞

(太原師范學院計算機系，晉中,030619)

?

不平衡數(shù)據(jù)集上的Relief特征選擇算法*

菅小艷 韓素青 崔彩霞

(太原師范學院計算機系，晉中,030619)

Relief算法為系列特征選擇方法，包括最早提出的Relief算法和后來拓展的ReliefF算法，核心思想是對分類貢獻大的特征賦予較大的權(quán)值；特點是算法簡單，運行效率高，因此有著廣泛的應(yīng)用。但直接將Relief算法應(yīng)用于有干擾的數(shù)據(jù)集或不平衡數(shù)據(jù)集，效果并不理想。基于Relief算法，提出一種干擾數(shù)據(jù)特征選擇算法，稱為閾值-Relief算法，有效消除了干擾數(shù)據(jù)對分類結(jié)果的影響。結(jié)合K-means算法，提出兩種不平衡數(shù)據(jù)集特征選擇算法，分別稱為K-means-ReliefF算法和K-means-Relief抽樣算法，有效彌補了Relief算法在不平衡數(shù)據(jù)集上表現(xiàn)出的不足。實驗證明了本文算法的有效性。

特征選擇；Relief算法；ReliefF算法；不平衡數(shù)據(jù)集

引 言

分類系統(tǒng)的好壞取決于所利用的特征是否能夠很好地反映所要研究的分類問題。特征選擇即從輸入的p個特征中選擇d

不平衡數(shù)據(jù)集是指一個數(shù)據(jù)集中，某一類的樣本數(shù)目明顯大于另一類的樣本數(shù)目。由于在不平衡數(shù)據(jù)集上采樣的懸殊，傳統(tǒng)方法往往得不到很好的分類效果。目前用于處理不平衡數(shù)據(jù)集分類問題的方法可以分為兩類：(1)從數(shù)據(jù)集入手，通過改變數(shù)據(jù)的分布，將不平衡數(shù)據(jù)變?yōu)槠胶鈹?shù)據(jù)；或者通過特征選擇，選出更能表達不平衡數(shù)據(jù)集的特征。(2)從算法入手，根據(jù)算法應(yīng)用在不平衡數(shù)據(jù)上所體現(xiàn)的缺點，改進算法，提高正確率[5,6]。本文從數(shù)據(jù)集入手，通過改變隨機選擇樣本的策略，利用Relief算法，研究有干擾數(shù)據(jù)集的分類問題，以及通過將K-means算法和抽樣機制與ReliefF 和Relief算法巧妙結(jié)合起來，利用KNN分類算法，研究不平衡數(shù)據(jù)集的分類問題。

1 Relief和ReliefF算法

(1)

式中：xi(j)表示樣本xi關(guān)于第j個特征的值；d(·)表示距離函數(shù)，用于計算兩個樣本關(guān)于某個特征的距離；m是隨機抽取樣本的次數(shù)。

(1)如果xi和NMi關(guān)于某個特征的距離大于xi和NHi關(guān)于該特征的距離，說明該特征對區(qū)分同類和不同類的最近鄰是有益的，則根據(jù)式(1)該特征的權(quán)重增加，反之，該特征的權(quán)重減少。

(2)距離函數(shù)定義

當特征為非數(shù)值型特征時，定義

(2)

當特征為數(shù)值型特征時，定義

(3)

其中max(j)，min(j)分別表示第j個特征所取值中的最大值和最小值。

ReliefF算法是Knonenko在1994年對Relief作的擴展，可以用于處理多類別問題[9]。ReliefF算法每次從訓練樣本集中隨機取出一個樣本xi，然后從與xi同類的樣本中找出xi的k個近鄰樣本NHi，同時從每個與xi不同類的樣本中也找出k個近鄰樣本NMi，然后根據(jù)以下規(guī)則更新每個特征的權(quán)重[9]，有

(4)

式中：class(xi)表示樣本xi所屬的類別；c表示某個類別，p(c)表示類別c的先驗概率[10，11]。

2 干擾數(shù)據(jù)和不平衡數(shù)據(jù)分類

Relief算法不僅算法原理比較簡單，運行效率高，而且對數(shù)據(jù)類型沒有限制，因此獲得了廣泛的應(yīng)用。然而在實際應(yīng)用中，該算法卻存在一些局限性,比如不適合處理有干擾的數(shù)據(jù),也不適合處理不平衡數(shù)據(jù)。

2.1 干擾數(shù)據(jù)分類問題

Relief算法首先需要從樣本集中隨機選擇一個樣本作為訓練樣本，這種隨機選擇樣本的方式，很可能取到不具有代表性的樣本，或干擾樣本，這意味著訓練得到的特征可能不具有代表性，從而影響分類結(jié)果。針對上述問題，本文提出一種新的樣本選取方法。首先計算樣本集中每個樣本與各自類中心的距離，將距離小于某一閾值的樣本生成一個樣本集D′，然后再從D′中隨機選擇一個樣本,這樣得到的樣本可以比較好地排除干擾樣本和不具有代表性的樣本。

算法1(閾值-Relief算法)

輸入： 樣本集D，特征集F，類別集C，取樣次數(shù)m，閾值δ

輸出： 特征權(quán)重向量W

過程：

(a)特征權(quán)值初始化:W(i)=0；

(b)計算與每個類中心距離小于某一閾值δ的樣本集合D′；

(c)從過濾后的樣本集D'中隨機選取一個樣本xi，同時從D與xi同類的樣本集中選取最近鄰的樣本NHi，從異類樣本集中選取最近鄰的樣本NMi；

(d)利用式(1)更新特征權(quán)重；

(e)重復(fù)(c,d)m次；

(f)輸出特征權(quán)重向量W。

2.2 不平衡數(shù)據(jù)分類問題

在不平衡數(shù)據(jù)集上，利用Relief算法選擇的特征有可能出現(xiàn)權(quán)重值偽偏大。因為在隨機選擇樣本時，樣本數(shù)目較多的類別中樣本被選中的概率要大，而樣本較少的類別中樣本被選中的概率要小，因而影響分類的效果。本文首先利用K-means算法對大類樣本集中的樣本進行聚類，然后在多類數(shù)據(jù)集上，分別基于K-means-ReliefF算法和K-means-Relief抽樣算法解決數(shù)據(jù)不平衡帶來的問題[12,13]。

2．2．1K-means-ReliefF算法

首先將大類集聚類得到一些新的類別集，從而使得樣本類別集基本平衡；然后采用ReliefF算法進行特征選擇。

算法2(K-means-ReliefF算法)

輸入：大類集L，小類集S(L和S同時表示類標簽)和聚類數(shù)q(q為大類集與小類集中的樣本數(shù)之比取整)

輸出：特征權(quán)重向量W

過程：

(a)利用K-means算法對樣本集L聚類，得到q個新類集S1,S2,…,Sq，與S一起構(gòu)成q+1個基本平衡的數(shù)據(jù)類集；

(b)利用ReliefF算法在q+1個類集上計算特征權(quán)重；

(c)輸出特征權(quán)重向量W。

2．2．2K-means-Relief抽樣算法

首先將大類集聚類，得到一些新類，在每個類內(nèi)抽取樣本，組成新的集合，代表大類集，然后采用Relief算法計算特征權(quán)重[14]。

算法3(K-means-Relief抽樣算法)

輸入：大樣本集L，小樣本集S(L和S同時表示類標簽)和聚類數(shù)q(q為大類集與小類集中的樣本數(shù)之比取整)

輸出：特征權(quán)重向量W

過程：

(a) 利用K-mean算法對樣本集L聚類，得到q個新的類集S1,S2,…,Sq；

(c)利用Relief算法在L′和S上計算特征權(quán)重；

(d)輸出特征權(quán)重向量W。

3 實驗結(jié)果

3.1 數(shù)據(jù)集

本文采用的數(shù)據(jù)集均來自UCI數(shù)據(jù)集。為了實驗的需要，在原始數(shù)據(jù)集上做了人為的修改。首先，為了得到有干擾樣本的數(shù)據(jù)集，修改了原始數(shù)據(jù)集中一些樣本的類別標簽；其次，為了得到不平衡數(shù)據(jù)集，刪除了原始數(shù)據(jù)集中的一些樣本。具體數(shù)據(jù)見表1。

表1 3個數(shù)據(jù)集

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

實驗利用Relief算法或ReliefF算法進行特征權(quán)重計算，以KNN做分類器(K=3)，為了得到更可靠的實驗結(jié)果，采用5折交叉驗證法，即將數(shù)據(jù)集平均分成5份，隨機選擇其中1份作為測試數(shù)據(jù)，其余的作為訓練數(shù)據(jù)，并且取5次的平均值作為最終的結(jié)果。結(jié)果表明，選擇原始數(shù)據(jù)特征數(shù)的20%進行分類效果最佳(以ionosphere為例，選擇權(quán)重較大的7個特征進行分類效果最佳)。

2.2.1 實驗1

實驗中，迭代次數(shù)m取訓練集中的樣本數(shù)。表2為在ionosphere數(shù)據(jù)集上隨機選擇樣本和閾值選擇得到的權(quán)重較大的7個特征以及它們的權(quán)重；圖1為在ionosphere數(shù)據(jù)集上兩種方法選擇樣本得到各特征權(quán)重值。表3為3個數(shù)據(jù)集上的分類正確率。

表2 Relief算法與閾值-Relief算法在ionosphere數(shù)據(jù)集上獲得的前7個特征的權(quán)重

圖1 Relief算法與閾值-Relief算法在ionosphere數(shù)據(jù)集上各特征權(quán)重值比較Fig.1 Comparison of feature weights of Relief algorithm and Threshold-Relief algorithm in ionosphere表3 Relief算法與閾值-Relief算法在3個數(shù)據(jù)集上的分類正確率 %Tab．3 The classification accuracy of Relief algorithm and threshold -Relief algorithm in three data sets

算 法ionospherewdbcBreastRelif算法88．390．389．5閾值?Relief算法909293．3

從表2和圖1可以看出，在ionosphere數(shù)據(jù)集上，Relief算法與閾值-Relief算法得到的特征排序和權(quán)重并不相同。由表3可知，在3個數(shù)據(jù)集上，閾值-Relief算法的分類正確率均比Relief算法的分類正確率要高，說明干擾點確實是Relief算法的消極因素，而改進后的閾值-Relief算法，可以有效地避開干擾點，選出更能代表類別的特征。該方法同樣也適用于不平衡數(shù)據(jù)。

3．2．2 實驗2

表4為在ionosphere的不平衡數(shù)據(jù)集上使用Relief算法、K-means-ReliefF算法(K=10)和Kmeans-Relief抽樣算法得到的權(quán)重較大的7個特征的排序、特征權(quán)重以及小類別的分類正確率和總的分類正確率。圖2為在Ionosphere數(shù)據(jù)集上3種方法得到的各特征權(quán)重。

表4 3種抽樣算法在Ionosphere數(shù)據(jù)集上的前7個特征權(quán)重及分類正確率

圖2 Relief算法、Kmeans-ReliefF算法和Kmeans-Relief抽樣算法在ionosphere數(shù)據(jù)集上各特征權(quán)重Fig.2 Feature weights of Relief algorithm, Kmeans-ReliefF algorithm and Kmeans-Relief sampling algorithm in ionosphere

通過表4和圖2可以看出，Relief，K-means-ReliefF算法和K-means-Relief抽樣算法在ionosphere數(shù)據(jù)集上得到的前7個權(quán)重較大的特征及其特征權(quán)重，同時可以看到，在小類別的分類正確率上有了明顯的提高。表5給出了Relief算法、K-means-ReliefF算法和K-means-Relief抽樣算法在不同數(shù)據(jù)集上分類正確率的比較。實驗結(jié)果顯示，大類集聚類后，無論是利用ReliefF算法在多類上進行特征選擇，還是利用Relief算法通過從多個類別中抽取樣本進行特征選擇，都可以有效彌補不平衡數(shù)據(jù)帶來的不足。在wdbc數(shù)據(jù)集上表現(xiàn)不明顯的原因是由于數(shù)據(jù)集的特征較少，抽取的特征有限，可能丟掉了一些相對重要的特征。

表5 Relief算法、K-means-ReliefF算法和K-means-Relief抽樣算法在3個數(shù)據(jù)集上的分類正確率 %

4 結(jié)束語

本文提出的閾值Relief算法，可以有效消除干擾數(shù)據(jù)集中干擾點對分類準確率的消極影響，提高分類精度。而結(jié)合K-means聚類算法提出的K-means-ReliefF算法和K-means-Relief抽樣算法，可以有效避開Relief算法在隨機選擇樣本時在不平衡數(shù)據(jù)集上表現(xiàn)出來的不足。實驗結(jié)果表明，在不降低大類樣本的正確率的基礎(chǔ)上，有效地提高了小類樣本的正確率。本文還存在一定的不足之處，希望能在下面幾方面加以改進：(1)首先干擾點和不平衡樣本集是人工構(gòu)造，存在一定的隨機性，下一步的工作希望能在真實的不平衡數(shù)據(jù)集上去驗證算法的有效性；(2)數(shù)據(jù)集中特征偏少，這樣可能在少量的特征上，每個特征都是比較重要的特征，故實驗結(jié)果不是很明顯。今后的工作重點是將該算法應(yīng)用在不同的更大規(guī)模的真實地數(shù)據(jù)集上測試，針對數(shù)據(jù)集的不同改進算法。

[1] 張學工.模式識別(第三版)[M].北京:清華大學出版社,2010．

Zhang Xuegong. Pattern recognition (Third Edition) [M]. Beijing: Tsinghua University Press, 2010．

[2] 錢宇華,梁吉業(yè),王鋒.面向非完備決策表的正向近似特征選擇加速算法[J].計算機學報,2011,31(3):435-442.

Qian Yuhua,Liang Jiye,Wang Feng. A positive-approximation based accelerated algorithm to feature selection from incomplete decision tables[J]. Chinese Journal of Computers, 2011,31(3):435-442.

[3] 劉全金,趙志敏,李穎新.基于特征間距的二次規(guī)劃特征選取算法[J].數(shù)據(jù)采集與處理，2015,30(1)：126-136．

Liu Jinquan,Zhao Zhimin,Li Yingxin. Feature selection algorithm based on quadratic programming with margin between features[J]. Journal of Data Acquisition and Processing,2015,30(1)：126-136．

[4] 李嘉.語音情感的維度特征提取與識別[J].數(shù)據(jù)采集與處理,2012,27(3):389-393．

Li Jia. Dimensional feature extraction and recognition of speech emotion[J]. Journal of Data Acquisition and Processing,2012,27(3)：389-393．

[5] Chawla NV, Japkowicz N, Kotcz A. Editorial: Special issue onlearning from imbalanced data sets[J]. SIGKDD Explorations Newsletters,2004,6(1): 1-6.

[6] Abe N, Kudn M. Non-parametric classifier-independent feature selection[J]. Pattern Recognition,2006,39(5):737-746.

[7] Kira K, Rendell L. A practical approach to feature selection[C]//Proc 9th International Workshop on Machine Learning. San Francisco: Morgan Kaufmann, 1992: 249-256.

[8] Kira K, Rendell L. The feature selection problem: Traditional methods and new algorithm[J]. Proc AAAI′92. San Jose, CA：[s.n.]，1992:129-134.

[9] Knonenko I. Estimation attributes: Analysis and extensions of Relief [C]//Euopean Conference on Machine Learning. Catania: Springer Verlag, 1994: 171-182.

[10]Sun Yijun. Iterative Relief for feature weighting:Algorithms,theories,and applications[J]. IEEE Trans on Pattern Anslysis and Machine Intelligence, 2007,29(6):1035-1051.

[11]Sun Y, Wu D. A Relief based feature extraction algorithm [C]//Proceedings of the 8th SIAM International Conference on Data Mining. Atlanta,GA,USA:[s.n.],2008：188-195.

[12]Liang Jiye, Bai Liang, Dang Chuangyin, et al. The K-means-type algorithms versus imbalanced data distributions[J]. IEEE Transactions on Fuzzy Systems, 2012, 20(4):728-745.

[13]黃莉莉.基于多標簽ReliefF的特征選擇算法[J].計算機應(yīng)用,2012,32(10):2888- 2890,2898.

Huang Lili. Feature selection algorithm based on multi-label ReliefF[J].Journal of Computer Applications,2012,32(10):2888-2890,2898.

[14]林舒楊,李翠華.不平衡數(shù)據(jù)的降采樣方法研究[J].計算機研究與發(fā)展,2011,48(S):47-53.

Lin Shuchang, Li Cuihua. Under-sampling method research in class-imbalanced data[J].Journal of Computer Research and Development,2011,48(S):47-53.

菅小艷(1975-)，女，講師，研究方向：數(shù)據(jù)挖掘，機器學習，E-mail:jianxiaoyan@tynu.edu.cn。

韓素青(1964-)，女，副教授，研究方向：數(shù)據(jù)挖掘，機器學習，E-mail:hansuqing@tynu.edu.cn。

崔彩霞(1974-)，女，副教授，研究方向：數(shù)據(jù)挖掘，機器學習，E-mail:cuicaixia@tynu.edu.cn。

Relief Feature Selection Algorithm on Unbalanced Datasets

Jian Xiaoyan, Han Suqing, Cui Caixia

(Department of Computer Science, Taiyuan Normal University, Jinzhong, 030619, China)

Relief algorithm is a series of feature selection method. It includes the basic principle of Relief algorithm and its later extensions reliefF algotithm. Its core concept is to weight more on features that have essential contributions to classification. Relief algorithm is simple and efficient, thus being widely used. However, algorithm performance is not satisfied when applying the algorithm to noisy and unbalanced datasets. In this paper, based on the Relief algorithm, a feature selection method is proposed, called threshold-Relief algorithm, which eliminates the influence of noisy data on classification results. Combining with the K-means algorithm, two unbalanced datasets feature selection methods are proposed, called K-means-ReliefF algorithm and K-means-relief sampling algorithm, respectively, which can compensate for the poor performance of Relief algorithm in unbalanced datasets. Experiments show the effectiveness of the proposed algorithms.

feature selection; Relief algorithm; ReliefF algorithm; unbalanced datasets

國家自然科學基金(61273294)資助項目;山西省科技基礎(chǔ)條件平臺(2014091004-0104)資助項目。

2015-05-26；

2015-07-22

TP18

A