利用混合整數規劃處理多類別分類

Abstract

本研究提出延伸Sueyoshi兩階段混合整數規劃，利用樹狀圖逐步分割概念提出可分多類別的方法；並加入多變量主成份分析做資料的前處理，提升分類能力。兩階段混合整數規劃的分類方法，主要用於兩類別資料判別，其優點有二：一是利用兩階段的概念對重疊區域作分類，可有效降低誤判率；另一則是用較少的二元變數(binary variables)處理分類問題，降低運算時的複雜度，也因此會比一般的分類方法來得有效能，但此法不能用於多組資料分類。故本研究以兩階段混合整數規劃為基礎，利用樹狀圖來做逐步分割，藉由兩兩類別間的中心點距離求出最佳分割順序樹狀圖來分多類別資料，同時減少誤判的發生；並藉由主成份分析對原始變數作前處理，使其轉換後的主成份變數間具有相互獨立的特性，進而提升分類時的正確率。另外，由於支持向量機是當前相當受到歡迎的分類方法，不僅可以分類多類別的資料，且在大量樣本上有良好的判別能力，因此，最後以兩個範例來做比較，結果顯示本研究所提出的多類別分類方法比支持向量機及統計上的判別分析法，更適用在小樣本上，驗證本研究的方法在小樣本上確實比支持向量機有較高的效能及可用性，且與支持向量機有相輔的特性。

This paper proposes a multiple group classification method which adopts principal components analysis as the data preprocessing and then extends Sueyoshi's two-stage mixed integer programming by using the tree concept to enhance the discriminating capability. The two-stage mixed integer programming which is usually applied to two-group classification has two mall advantages: (ⅰ) It deals with overlap area by using the two-stage approach, thus it is a more effective method for reducing the misjudgments: (ⅱ) To reduce the complexity, it uses less binary variables than other mixed integer programming methods. However, the two-stage mixed integer programming cannot deal with multiple group discrimination. In order to overcome this problem, a mixed integer programming with a tree concept and principal components analysis is proposed. A tree is generated according to the center distance of each pair groups. Then the original variables are transformed into new ones by principal components analysis, which makes the new variables independent, classifies easily and enhances the hit rate. The proposed method is compared with support vector machine (SVM), a popular classification method in large sample size, and statistical discriminant analysis by using two examples. The proposed method outperforms SVM and statistical discriminant analysis. Our approach ca be a good alternative method of SVM especially in handling small sample size.