以基因規劃法建構迴歸樹

Regression Trees with Genetic Programming

陳顯旭(Skywood Chen)

指導教授 ： 邱昭彰

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

摘要

資料探勘為一自動搜尋資料屬性有用與有趣關係的方法。在許多的資料探勘技術中（如類神經網路） 對資料關係難以提供明確的規則描述。近年來，基因規劃法成功地被運用在許多的領域，幫助它們發展出樣式識別的能力。在本研究中，我們提出以基因規劃法建構迴歸樹之演算法，做為除目前既存迴歸樹演算法外的另一種選擇。本研究著重於利用基因規劃法找出屬性及切割值並結合區域線性規劃法，再配合樹的修剪及評估以建構出最佳的迴歸樹。我們並以二組迴歸資料進行實驗，並將提出的作法與其它迴歸演算法做比較。實驗結果顯示，本研究所提出之迴歸樹演算法在精確度上有不錯的表現，並有著其它數種優點。此外，本研究亦開發了一套雛形系統，用以輔助迴歸樹的建構並自動產生一些規則以支援決策者制定決策。

關鍵字

決策樹 ； 迴歸樹 ； 基因規劃法

並列摘要

Data mining is the automated search for interesting and useful relationships between attributes in database. In many of the best techniques (such as neural networks) yield little in terms of usable rules. In recent years, there has been considerable success in the use of Genetic Programming (GP) to evolve pattern recognizers. In this article we presents a GP-regression tree (GPRT) algorithm as an alternative to existing regression tree approaches. We focus on using genetic programming and local linear regression to construct regression trees by genetic selection of features and split points, then using tree pruning and evaluation trying to find out an optimized regression tree. Experimental results for two data mining regression problems are presented and compared with other regression algorithms. Experiments show our approach has a number of advantages over existing regression algorithms. A prototype was presented to assistant the regression tree construction and produced a set of rules to support decision makers.

並列關鍵字

Decision Tree ； Regression Tree ； Genetic Programming

參考文獻

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

[2]Back, T., Hammel, U., and Schwefel, H.P., “Evolutionary computation: Comments on the History and Current State,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp.3-17, 1997.

[5]Chou, P. A. 1991. “Optimal Partitioning for Classification and Regression Trees,” IEEE Transactions on Pattern Analysis and Machine Intelligence 13, pp. 340-354.

[7]John H. Holland, “Genetic Algorithms”, Scientific American, pp.66-72, 1992.

[9]Korenaga, M., Hagiwara, M., “Modified Genetic Programming Based on Elastic Artificial Selection and Improved Minimum Description Length,” IEEE International Conference on Systems, Man, and Cybernetics, Vol. 3, pp. 2348 -2353, 1998.