不平衡數(shù)據(jù)集分類問題研究

1、不平衡數(shù)據(jù)集分類問題研究 學(xué)號：2009021251 姓名：孫曉燕 ：1XXXXXXXXXX Email ：xiaomeixi_1987163 所在學(xué)院：信息科學(xué)與工程學(xué)院 單位代碼 10445 學(xué) 號 2009021251 1 分 類 號 TP391 研究生類別 全日制 碩 士 學(xué) 位 論 文 論文題目 不平衡數(shù)據(jù)集分類問題研究 學(xué)科專業(yè)名稱：計算機軟件與理論 申 請人姓 名：孫曉燕 指 導(dǎo) 教 師：張化祥 教授 論文提交時間：2012 年 6 月 15 日 獨 創(chuàng) 聲 明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究成果。 據(jù)我所知，除了文中特別加以標注和致謝的地方

2、外，論文中不包含其他人已經(jīng)發(fā)表或撰寫 過的研究成果，也不包含為獲得 （注：如沒有其他需要特別聲明的，本 欄可空）或其他教育機構(gòu)的學(xué)位或證書使用過的材料。與我一同工作的同志對本研究所做 的任何貢獻均已在論文中作了明確的說明并表示謝意。 學(xué)位論文作者簽名： 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解 學(xué)校 有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國家 有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán) 學(xué)校 可以 將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復(fù) 制手段保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后適用本授權(quán)書） 學(xué)位論文作者簽名

3、： 導(dǎo)師簽字： 簽字日期：20 年 月 日 簽字日期：20 年 月 日 山東師范大學(xué)碩士學(xué)位論文 目錄 摘要.I ABSTRACT . III 第一章 緒論. 1 1.1 課題研究背景及意義. 1 1.2 本文主要研究內(nèi)容及創(chuàng)新點. 2 1.3 本文組織結(jié)構(gòu). 2 第二章 不平衡數(shù)據(jù)集領(lǐng)域的研究現(xiàn)狀. 4 2.1 不平衡數(shù)據(jù)集分類難點. 4 樣本缺失. 4 不恰當(dāng)?shù)脑u價標準. 4 數(shù)據(jù)噪聲. 4 不恰當(dāng)?shù)臍w納偏置. 5 2.2 不平衡數(shù)據(jù)集研究現(xiàn)狀. 5 數(shù)據(jù)層面方法. 5 算法層面方法. 7 評價標準. 8 2.3 分類器的性能評估方法. 10 測試集. 10 交叉驗證. 11 其他估計方法

4、. 11 第三章 KNN 算法在不平衡數(shù)據(jù)集中的應(yīng)用. 13 3.1 KNN 算法概述. 13 3.2 遺傳算法概述. 14 3.3 基于KNN 算法的少數(shù)類樣本生成方法G-KNN 算法. 14 3.4 G-KNN 算法實驗. 16 G-KNN 算法實驗設(shè)計. 16 G-KNN 實驗結(jié)果及分析. 17 3.5 總結(jié). 18 第四章 基于Bagging 的欠抽樣集成學(xué)習(xí)算法. 19 4.1 Bagging 算法概述. 19 4.2 聚類算法概述. 20 4.3 基于Bagging 的欠抽樣集成學(xué)習(xí)算法描述. 20 4.4 實驗結(jié)果及分析. 23 實驗環(huán)境設(shè)計. 23 實驗結(jié)果及分析. 24 山東

5、師范大學(xué)碩士學(xué)位論文 4.5 結(jié)論.27 第五章 基于AdaBoost 的抽樣層算法.28 5.1 AdaBoost 算法概述.28 5.2 基于Adaboost 的抽樣層算法.30 基于Adaboost 的欠抽樣集成學(xué)習(xí)算法.30 基于AdaBoost 的邊界樣本過抽樣算法.31 5.3 U- Ensemble 算法實驗.33 U- Ensemble 算法實驗設(shè)計.33 U- Ensemble 算法實驗結(jié)果及分析.34 5.4 BOBA 算法實驗.35 BOBA 算法實驗設(shè)計.35 BOBA 算法實驗結(jié)果及分析.36 5.5 本章小結(jié).38 第六章 總結(jié)與展望.39 6.1 本文研究內(nèi)容總結(jié)

6、.39 6.2 下一步工作.39 參考文獻.40 攻讀碩士學(xué)位期間發(fā)表的論文和參與的項目.43 致謝.44 山東師范大學(xué)碩士學(xué)位論文 不平衡數(shù)據(jù)集分類問題研究 摘要 分類是機器學(xué)習(xí)領(lǐng)域的重要研究方向之一，經(jīng)過多年發(fā)展形成了一些較為成熟的算 法，并在實際中取得成功的應(yīng)用。這些傳統(tǒng)的分類算法以分類正確率作為最大的目標，且 假定數(shù)據(jù)集中各類別樣本數(shù)量基本平衡。然而在實際問題中，存在這樣的一類數(shù)據(jù)，在數(shù) 據(jù)集中某一類的樣本數(shù)量遠遠少于其它類樣本數(shù)量，即數(shù)據(jù)集中不同類別樣本的數(shù)量是非 平衡的，這樣的數(shù)據(jù)稱為不平衡數(shù)據(jù)。通常，將數(shù)量上占多數(shù)的類稱為多數(shù)類，而占少數(shù) 的類稱為少數(shù)類。對不平衡數(shù)據(jù)集分類時，傳

7、統(tǒng)分類算法為追求更高的分類正確率，在分 類的過程中偏好數(shù)量上占多數(shù)的多數(shù)類，結(jié)果多數(shù)類的分類正確率較高，而少數(shù)類分類正 確率較低。例如，在某些極端情況下，某個傳統(tǒng)的分類算法將所有的樣本都分類為多數(shù)類， 依然能獲得較高的整體分類精度，卻不能識別一個少數(shù)類。而在實際問題中，少數(shù)類的分 類精度往往更為重要。因此，如何對不平衡數(shù)據(jù)集進行正確分類、提高少數(shù)類的分類精度 成為數(shù)據(jù)挖掘領(lǐng)域中的一個研究重點。 針對不平衡數(shù)據(jù)集的研究集中在三個方面：數(shù)據(jù)層面的方法、算法層面的方法及評價 標準。數(shù)據(jù)層面方法即是對數(shù)據(jù)集進行預(yù)處理，采用采樣技術(shù)重構(gòu)數(shù)據(jù)集，以此改變原有 的數(shù)據(jù)分布，減少不平衡程度，進而使的數(shù)據(jù)集類分

8、布基本平衡，較常用的方法包括欠采 樣、過采樣；算法層面的方法，即改進傳統(tǒng)分類算法，使其在分類過程中更加注重對少數(shù) 類的分類，提高少數(shù)類的分類精度，從而適應(yīng)不平衡數(shù)據(jù)集的分類問題，如代價敏感學(xué)習(xí)、 集成學(xué)習(xí)等；對不平衡數(shù)據(jù)集分類的性能評價標準也是研究的重點之一，常用的標準有 F-Measure 、G-Mean 等。 本文針對不平衡數(shù)據(jù)集分類問題，嘗試將采樣技術(shù)與傳統(tǒng)分類算法相結(jié)合，提出了四 種用于解決不平衡數(shù)據(jù)集分類問題的新方法。主要創(chuàng)新成果有： 1 使用遺傳算法中的交叉算子與變異算子生成新的少數(shù)類樣本，采用兩樣本間的歐幾 里得距離檢驗新生成少數(shù)類樣本的有效性。在UCI 數(shù)據(jù)集的實驗結(jié)果表明，該

9、方法在提高 少數(shù)類的分類精度方面取得了較好的效果。 2 使用聚類技術(shù)中的K-means 算法首先將多數(shù)類樣本聚成多個簇，然后依次從每個簇 中抽取一定數(shù)量的多數(shù)類樣本，使所有抽取到的多數(shù)類樣本個數(shù)與少數(shù)類樣本個數(shù)基本相 同，最后將多數(shù)類樣本與少數(shù)類樣本合并，作為Bagging 成員分類器的訓(xùn)練數(shù)據(jù)。K-means 算法的不穩(wěn)定性，可以在一定程度上保證成員分類器之間的差異性。 3 使用 AdaBoost 算法對數(shù)據(jù)集預(yù)處理，得到各樣例權(quán)重。訓(xùn)練基分類器時，針對多 數(shù)類數(shù)據(jù)不再采用bootstrap 抽樣方法，而是分別隨機選擇部分權(quán)重較大的樣例與部分權(quán)重 I 山東師范大學(xué)碩士學(xué)位論文 較小的樣例，使

10、兩部分樣例個數(shù)與少數(shù)類樣例個數(shù)相同，并組成Bagging 成員分類器的訓(xùn) 練數(shù)據(jù)。 4 提出基于AdaBoost 的邊界數(shù)據(jù)過抽樣算法，使用AdaBoost 算法迭代多次后，選擇 部分權(quán)重較大的數(shù)據(jù)作為邊界數(shù)據(jù)，并對這部分邊界數(shù)據(jù)進行隨機過抽樣，進而使數(shù)據(jù)集 中兩類樣本分布趨于平衡，從而達到提高少數(shù)類分類精度的目的。 關(guān)鍵字：不平衡數(shù)據(jù)集；AdaBoost 算法；Bagging 算法；KNN 算法；采樣技術(shù)； 分類號：TP391 II 山東師范大學(xué)碩士學(xué)位論文 Study of Classification Algorithm on Unbalanced Data Sets ABSTRACT

11、Classification is an important research direction in the field of machine learning. Some sophisticated algorithms have been formed after years of development and succeed in practice. These traditional classification algorithms intend to imize the overall prediction accuracy, and assume that the clas

12、s distribution is basic balanced. However, in real world applications, we often face the problem of imbalanced data sets where the instances of one class are fewer than that of other classes, which means that the class distribution is highly skewed. We often refer the minority and majority class as

13、positive and negative class respectively. Traditional algorithms tend to show a strong bias toward the majority, since they aim to imize the overall accuracy. For example, in some extreme cases, if a traditional classification algorithm predicts all the instances as the majority class, it still gets

14、 a high accuracy of 100%, but it cannot recognize the minority class instances. However, in many cases, the accuracy of the minority class is much more important. Therefore, many studies have been discussed to tackle this demanding problem in the field of data mining. The approaches proposed are mai

15、nly focus on three aspects: data level, algorithm level and evaluation criterion. On data level, solutions are proposed to artificially balance the training sets by modifying the distribution of the data sets and the commonly used methods are known as under-sampling and over-sampling respectively. O

16、n algorithm level, approaches are designed to modify the learning algorithm, making it more sensitive to the minority class, such as cost-sensitive learning, integrated learning and so on. Accuracy represents the population of the correctly predicted examples, which is not an appropriate evaluation

17、criterion in imbalanced data sets. We need more reasonable evaluation criteria, such as F-Measure 、G-Mean. This paper discusses on both data-level and algorithm-level, and proposes four methods to tackle this demanding problem. The main contributions of this paper are summarized as follows: 1 We use

18、 the crossover operator and mutation operator to generate some of the new minority class samples. The method employs Euclidean geometric distance between two samples to evaluate the effectiveness of the newly generated minority class instances. The proposed method is applied on UCI data sets and exp

19、erimental results indicate that our method is effective in improving the classification accuracy of minority class. 2 The majority class is clustered into several groups by K-means algorithm. Then we randomly sample a certain number of instances from each group. Those sampled instances almost equal

20、the minority class instances. At last, we combine the sampled majority class III 山東師范大學(xué)碩士學(xué)位論文 instances and all the minority class instances to train a base classifier. Final predictions are produced by combining those classifiers. The instability of K-mean makes different results of each cluster. 3

21、 Firstly, AdaBoost is used to process the imbalanced data sets in order to get the weights of samples. Then, we use Bagging as the classifier, bootstrap is no longer used when sample the majority class, but we randomly select some of samples that have larger and smaller weights .Meanwhile, we should

22、 ensure that the number of the samples selected from the majority class equals the number of the minority class. At last, we combine the sampled majority class samples and all the minority class samples as the training data set for a component classifier. 4 AdaBoost is used to process the imbalanced

23、 data sets in order to get the weights of samples. Instances that have lager weight are considered as the boundary data. Only those borderline instances are over-sampled, making balanced a data set to train a base classifier. Keywords: imbalance datasets; KNN algorithm; AdaBoost; Bagging; resampling

24、 Classification ：TP391 IV 山東師范大學(xué)碩士學(xué)位論文 第一章緒論 1.1 課題研究背景及意義 分類是指通過對已有數(shù)據(jù)的分析和學(xué)習(xí)，發(fā)現(xiàn)隱藏在數(shù)據(jù)內(nèi)的規(guī)律，并利用這些規(guī)律 去對未來的數(shù)據(jù)進行預(yù)測和判斷。在信息社會高速發(fā)展的今天，面對海量的數(shù)據(jù)，分類技 術(shù)就顯得尤為重要，分類也是機器學(xué)習(xí)、數(shù)據(jù)挖掘領(lǐng)域的一個重要研究方向。已有的經(jīng)典 分類算法，例如：KNN 、貝葉斯算法、神經(jīng)網(wǎng)絡(luò)算法、支持向量機算法、集成學(xué)習(xí)等，都 在實際應(yīng)用中獲得良好的分類效果。 然而在實際的問題中，我們經(jīng)常面對這樣的一類數(shù)據(jù)：在訓(xùn)練數(shù)據(jù)集中，某一個類別 的樣本數(shù)量遠遠少于其它類別的樣本數(shù)量，即數(shù)據(jù)集分布是

25、不平衡的。例如在信用卡欺詐 1 2 識別數(shù)據(jù)中 ，可能10 萬起交易中只有一起是欺詐；在網(wǎng)絡(luò)入侵檢測數(shù)據(jù)中 ，絕大部分 34 5 是正常的網(wǎng)絡(luò)訪問，而入侵訪問只占一少部分，在醫(yī)療檢測 、雷達圖像檢測 、電信客 6 戶流失預(yù)測 等領(lǐng)域也都存在數(shù)據(jù)分布不平衡的問題。所謂不平衡數(shù)據(jù)集，指在數(shù)據(jù)集中 某一類的樣本數(shù)量遠遠少于其它類樣本數(shù)量，其中數(shù)量占多數(shù)的類稱為多數(shù)類，而占少數(shù) 7 的類稱為少數(shù)類 。 在傳統(tǒng)的學(xué)習(xí)算法分類過程中，假設(shè)數(shù)據(jù)集的分布基本均衡，且以總體分類精度作為 目標，這就導(dǎo)致在對不平衡數(shù)據(jù)集分類過程中分類器對數(shù)量上占優(yōu)勢的多數(shù)類存在明顯的 8 偏好，使得多數(shù)類的分類精度提高，而少數(shù)類的

26、分類精度降低 。而在實際問題中，人們 往往更為看重少數(shù)類分類精度。例如：在癌癥檢測領(lǐng)域中，大多數(shù)身體健康的人屬于多數(shù) 類，很少部分身患癌癥的人屬于少數(shù)類。使用傳統(tǒng)的分類算法進行分類預(yù)測時，由于身患 癌癥的少數(shù)類樣本數(shù)量較少，分類算法為追求較高的整體分類精度，會盡量提高多數(shù)類的 分類精度，而忽略對少數(shù)類的分類性能，即盡可能將樣本預(yù)測為身體健康的人，卻忽略了 對真正患病人的識別率。而實際存在這樣一個問題：樣本的類別不同，它們的誤分代價是 有差異的。在這個例子中，算法如果把一個身體健康的人預(yù)測為患有癌癥的病人，會給他 造成額外的檢測費用和沉重的心理負擔(dān)；但是算法如果把一個真正患有癌癥的人誤診為身 體

27、健康的人，那么可能就會使他錯過治療的最佳時機，所造成的代價是巨大的。又比如網(wǎng) 絡(luò)入侵檢測中的入侵樣本一般少于1%，如果分類算法將所有的樣本均預(yù)測為多數(shù)類樣本， 依然會獲得99%的正確率，卻不能識別一個少數(shù)類樣本，顯然這樣的分類對識別入侵檢測 樣本而言是沒有意義的。 因此，不平衡數(shù)據(jù)集及相關(guān)問題成為了機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點及重 點。近年來，國際上的學(xué)者不斷在相關(guān)會議上對這一課題進行深入探討：2000 年的美國智 能協(xié)會（AAAI ）與 2003 年的機器學(xué)習(xí)國際會議（ICML ）上，都針對不平衡數(shù)據(jù)集問題 召開了專題研討會；2004 年美國計算機協(xié)會針對相關(guān)問題出版了一期通訊；而在

28、國際知識 1 山東師范大學(xué)碩士學(xué)位論文 9 發(fā)現(xiàn)與數(shù)據(jù)挖掘會議（KDD ）中，也有發(fā)表關(guān)于不平衡數(shù)據(jù)集及相關(guān)問題的論文 。 1.2 本文主要研究內(nèi)容及創(chuàng)新點 本文首先分析不平衡數(shù)據(jù)集問題的研究現(xiàn)狀，并在此基礎(chǔ)上，通過分析 KNN 算法、 Adaboost 算法和Bagging 算法在對不平衡數(shù)據(jù)集進行分類時存在的問題，借鑒了相關(guān)采樣 技術(shù)和聚類方法，提出了四種改進的算法，并通過實驗驗證了算法的有效性。 1 針對KNN 在處理不平衡數(shù)據(jù)集時，少數(shù)類分類精度不高的問題，本文提出了一種 改進的算法G-KNN 。該算法首先對少數(shù)類樣本使用交叉算子和變異算子生成部分新的少數(shù) 類樣本，若新生成的少數(shù)類樣本

29、到父代樣本的歐幾里得距離小于父代少數(shù)類之間的最大距 離，則認為是有效樣本，并把這類樣本加入到下輪產(chǎn)生少數(shù)類的過程中。 2 使用聚類技術(shù)中的K-means 算法將多數(shù)類樣本聚成多個簇，然后依次從每個簇中抽 取一定數(shù)量的多數(shù)類樣本，使所有抽取到的多數(shù)類樣本個數(shù)與少數(shù)類樣例個數(shù)基本相同， 最后將多數(shù)類樣本與少數(shù)類樣本合并，作為Bagging 成員分類器的訓(xùn)練數(shù)據(jù)。K-means 算 法的不穩(wěn)定性，可以在一定程度上保證成員分類器之間的差異性。 3 使用 AdaBoost 算法對數(shù)據(jù)集預(yù)處理，得到各樣例權(quán)重。訓(xùn)練基分類器時，針對多 數(shù)類數(shù)據(jù)不再采用bootstrap 抽樣方法，而是分別隨機選擇部分權(quán)重較

30、大的樣例與部分權(quán)重 較小的樣例，使兩部分樣例個數(shù)與少數(shù)類樣例個數(shù)相同，并組成Bagging 成員分類器的訓(xùn) 練數(shù)據(jù)。 4 提出一種基于AdaBoost 的邊界數(shù)據(jù)過抽樣算法，該方法首先使用AdaBoost 算法對 數(shù)據(jù)集預(yù)處理，得到各樣例權(quán)重。然后從中選擇部分權(quán)重較大的數(shù)據(jù)作為邊界數(shù)據(jù)，并對 這部分邊界數(shù)據(jù)進行隨機過抽樣，進而使數(shù)據(jù)集中兩類樣本分布趨于平衡，從而達到提高 少數(shù)類分類精度的目的。 1.3 本文組織結(jié)構(gòu) 第一章：緒論。簡單介紹不平衡數(shù)據(jù)集課題的研究背景與意義，并說明了針對本課題 所做的主要研究工作和提出的創(chuàng)新點。 第二章：不平衡數(shù)據(jù)集領(lǐng)域的研究。簡單分析了不平衡數(shù)據(jù)集問題在分類過程

31、中存在 的瓶頸，說明了目前相關(guān)問題的研究現(xiàn)狀。 第三章：KNN 算法在不平衡數(shù)據(jù)集中的應(yīng)用。針對KNN 在處理不平衡數(shù)據(jù)集時，少 數(shù)類分類精度不高的問題，提出一種改進的算法G-KNN 。 第四章：基于Bagging 的欠抽樣集成學(xué)習(xí)算法。首先使用聚類算法將多數(shù)類聚成多個 簇，然后從每個簇中抽取多數(shù)類樣本，合并后與少數(shù)類樣本一起訓(xùn)練Bagging 的成員分類 器。 第五章：基于AdaBoost 的抽樣層算法。將AdaBoost 算法分別與欠采樣技術(shù)和過采樣 2 山東師范大學(xué)碩士學(xué)位論文 技術(shù)相結(jié)合，提出了兩種改進的算法：基于AdaBoost 的欠抽樣集成學(xué)習(xí)算法、基于AdaBoost 的過抽樣集

32、成學(xué)習(xí)算法。使用 AdaBoost 算法區(qū)分訓(xùn)練樣本中的邊界樣本與易分樣本，針 對這些邊界樣本進行欠采樣或過采樣，并在迭代過程中的每一輪構(gòu)造平衡的訓(xùn)練樣本集。 第六章：總結(jié)與展望。本章對全文研究的主要內(nèi)容與創(chuàng)新點進行歸納，并提出接下來 的研究內(nèi)容與方向。 3 山東師范大學(xué)碩士學(xué)位論文 第二章不平衡數(shù)據(jù)集領(lǐng)域的研究現(xiàn)狀 本章首先介紹不平衡數(shù)據(jù)集在分類問題上遇到的困難，接著介紹目前不平衡數(shù)據(jù)集的 研究現(xiàn)狀，最后闡釋常用的分類器性能評估方法。 2.1 不平衡數(shù)據(jù)集分類難點 分類是機器學(xué)習(xí)領(lǐng)域的一個重要研究方向，分類算法發(fā)展已經(jīng)比較成熟，有許多經(jīng)典 10 11 12 13 的算法，如決策樹算法 、貝葉斯算法 、神經(jīng)網(wǎng)