使用基因規劃建構多元分類樹

Applying Genetic Programming in Classification Trees with Multivariate Split Points

林國偉(Kuowei Lin)

指導教授 ： 邱昭彰

元智大學/資訊學院/資訊管理學系/碩士(2002年)

摘要

在資料探勘的應用領域中，分類是其中一種常用的技術，它可從資料庫中讀取所需的資料，進而找出相關的分類規則，並提供給經營階層作為一決策分析的參考。在本研究中，有別於過去所使用統計或計算資料混亂程度來建立分類樹的做法，由於基因規劃是一種用來搜尋最佳解的演算法，因此我們使用了基因規劃的技術來尋找切割點與相關屬性來建立分類樹。與過去的研究不同的是，本研究將分類規則以包含非線性的數學運算元來呈現。其做法乃是藉由基因規劃來搜尋分類規則所需的常數、資料欄位、門檻值與非線性的數學運算元(例如Sin、Cos、Log..等)，來建立相關的分類規則。此外，本研究方法亦考量到處理類別型態的資料，使所產生的分類規則能處理更多的資料，進而使其準確率達到最佳化。在實驗結果中，藉由與其他傳統的分類方法比較，可發現本研究在特定領域的資料庫中，有不錯的表現。

關鍵字

基因規劃 ； 分類樹 ； 資料探勘 ； 決策樹

並列摘要

In the data mining field, classification is a common and useful technique. It can find the classification rule by learning data from database. The manager can use the rule to decision support. In this paper, propose a methodology different from other classification rule. The proposed methodology is different from using statistic or entropy to build classification tree. Genetic Programming (GP) is an algorithm for searching the optimal. Therefore, we construct the classification tree by GP that search the threshold and feature. The different between our methodology and traditional way, the classification rule contains the non-linear operators (For example: Sin、Cos、Log… ). We apply GP to construct the classification tree with multiple variables. The rule expressed by equation with nonlinear operators. Searching the constants, variable, and threshold through GP, until find an optimal classification tree and then have a perfect accuracy. Besides, it can also deal with the discrete data to improve accuracy. In experiment, our methodology compare with the other methods, it has a good accuracy in some specify datasets.

並列關鍵字

Genetic Programming ； Classification Tree ； Data Mining ； Decision Tree

參考文獻

[23] Ngan, P. S., Wong, M. L., Lam, W., Leung, K. S., and Cheng, C.Y., “Medical Data Mining Using Evolutionary Computation,” Artificial Intelligence in Medicine, Vol. 16, pp. 73-96, 1999.

[1] Apte, G. and Weiss, S., “Data Mining with Decision Trees and Decision Rules,” Future Generation Computer Systems, Vol. 13, pp. 197-210, 1997.

[4] Breslow, L. and D. W. Aha, "Simplifying Decision Trees: A Survey," Knowledge Engineering Review, Vol. 12, pp. 1-40, 1997.

[7] Chai, B. B., Huang, T., Zhuang, X., Zhao, Y. and Sklansky, J., "Piecewise Linear Classifiers Using Binary Tree Structure and Genetic Algorithm," Pattern Recognition, Vol. 29, No.11, pp. 1905-1917, 1996.

[8] Chris, G., “An Investigation of Supervised Learning in Genetic Programming,” PhD thesis, University of Edinburgh, 1998.