Application and Study of imbalanced datasets base on Top-N Reverse k-Nearest Neighbor (TRkNN) coupled with Synthetic Minority Over-Sampling Technique (SMOTE)

不平衡分類是指數據集具有不均勻的類別分佈。若不考慮數據集的不平衡問題，大多數分類方法對於多數類的預測有較高的準確率，而少數類的準確率則明顯較低。本研究第一項工作是提出一個有效的演算法，此演算法結合反向排序K鄰近法(TRkNN)和合成少數類樣本的增量技術(SMOTE)，以克服UCI資料庫中不平衡數據集的問題。為了研究此演算法，本研究也將其應用於不同的分類方法，如邏輯回歸、C4.5、SVM和BPNN。此外，還採用不同的距離度量來分類相同的UCI數據集。經驗結果表明，歐幾里德距離和曼哈頓距離不僅具有更高的準確率，而且還有比切比雪夫距離和餘弦距離更快的計算效率。因此，基於TRkNN和SMOTE的演算法可以廣泛用於處理不平衡數據集，如何選擇合適的距離度量可以作為未來研究的參考。 對癌症預測的研究已經應用多種機器學習演算法，如類神經網絡，基因演算法和粒子群演算法，以找出分類疾病或癌症的關鍵屬性或傳統的統計預測模型，有效地區別不同類型的癌症，從而建立可以提早發現和治療的預測模型。其中以現有患者的資料作為訓練集來建立模型以預測新病患樣本的分類準確度。這個問題在資料探勘領域引起了相當大的關注，學者們提出了各種方法（例如，隨機抽樣和特徵選取）來解決類別不平衡並實現重新平衡的類別分佈，從而提高分類器的有效性。雖然重新採樣方法可以快速處理不平衡樣本的問題，但它們更重視多數類中的數據，忽略少數類中潛在的重要數據，從而限制分類的有效性。根據在不平衡醫學數據集中發現的模式，本研究第二項工作是使用合成少數類樣本的增量技術來改善不平衡數據集的問題。此外，這項研究還使用三個UCI醫療數據集來比較基於機器學習、軟計算和仿生計算之各種方法的重新採樣性能。The imbalanced classification means the dataset has an unequal class distribution among its population. For a given dataset without considering the imbalanced issue, most classification methods often predict the high accuracy for the majority class, but significantly low accuracy for the minority class. The first task in this dissertation is to provide an efficient algorithm, Top-N Reverse k-Nearest Neighbor (TRkNN), coupled with Synthetic Minority Over-Sampling TEchnique (SMOTE) to overcome this issue for several imbalanced datasets from famous UCI datasets. To investigate the proposed algorithm, it was applied into different classified methods, such as Logistic regression, C4.5, SVM, and BPNN. In addition, this research also adopted different distance metrics to classify the same UCI datasets. The empirical results illustrated that the Euclidean distance and Manhattan distance not only perform higher percentage of accuracy rate, but also show greater computational efficiency than the Chebyshev distance and Cosine distance. Therefore, the TRkNN and SMOTE based algorithm could be widely used to handle the imbalanced datasets and how to choose the suitable distance metrics can be as the reference for the future researches. Research into cancer prediction has applied various machine learning algorithms, such as neural networks, genetic algorithms, and particle swarm optimization, to find the key to classifying illness or cancer properties or to adapt traditional statistical prediction models to effectively differentiate between different types of cancers, and thus build prediction models that can allow for early detection and treatment. Training data from existing patients is used to establish models to predict the classification accuracy of new patient samples. This issue has attracted considerable attention in the field of data mining, and scholars have proposed various methods (e.g., random sampling and feature selection) to address category imbalances and achieve a re-balanced class distribution, thus improving the effectiveness of classifiers with limited data. Although resampling methods can quickly deal with the problem of unbalanced samples, they give more importance to the data in the majority class, and neglect potentially important data in the minority class, thus limiting the effectiveness of classification. Based on patterns discovered in imbalanced medical data sets, the second task in this dissertation is to use the synthetic minority oversampling technique to improve imbalanced data set issues. In addition, this research also compares the resampling performance of various methods based on machine learning, soft-computing, and bio-inspired computing, using three UCI medical data sets.Contents 致 謝 ii 中文摘要 iii Abstract iv Contents vi List of Figures viii List of Tables ix Chapter 1 Introduction 1 Chapter 2. Literatures Review 4 2.1 Sampling Techniques 4 2.2 Synthetic Minority Oversampling Technique (SMOTE) 5 2.3 Machine Learning 6 Chapter 3. Data Mining for Bioinformatics: Design with Oversampling and Performance Evaluation 8 3.1. Imbalanced Class 8 3.2. Machine Learning 10 3.3. DataBase 11 3.4. Methods 13 3.4.1. UCI Data Set Collection Stage 13 3.4.2. Data Preprocessing Stage 13 3.4.3. Prediction Model Implementation Stage 15 3.4.4. Performance Evaluation Stage 15 Chapter 4. Distance Metric Based Over-Sampling Method for Bioinformatics and Performance Evaluation 16 4.1. Materials 16 4.2. Top-N Reverse k-Nearest Neighbor (TRkNN) Algorithm 17 4.3. Distance Metrics 19 Chapter 5. Experimental Results 22 5.1. Performances of Data Mining Based Design for Bioinformatics with Oversampling 22 5.1.1. Experimental Design and Parameter Setting 22 5.1.2. Performance Evaluation 22 5.2. Performances of Distance Metric Based Over-Sampling Method for Bioinformatics 25 5.2.1. Experimental Design and Parameter Setting 25 5.2.2. Performance Evaluation 25 Chapter 6 Conclusions 31 References 3