人工智慧中決策樹的最佳推導方法

Abstract

隨著專家系統的需求日益增加，如何使機器學習儼然成為一項重要的課題，目前有許多研究成功的提出學習的演算法，其中J. R. Quinlan提出的ID3演算法來產生決策樹十分著名。但此法在語意的表達上有先天上的限制，另一方面亦無法處理含有雜訊的資料。 本篇論文提出一個藉由0-1整數規劃產生決策樹的新方法（命名為C-MAX演算法），此法並可進一步導出只含一層的決策樹，同時它亦能提供一個處理雜訊資料的方法。最後本篇論文將ID3與C-MAX演算法針對決策樹的大小及所產出規劃的正確率和普及率做一比較，我們將可發現C-MAX可以獲得較佳的決策樹。

The algorithms for building knowledge-based systems by inductive inference from example have been demonstrated successfully in several researches. The ID3 algorithm is a well-known approach (proposed by J.R. Quinlan) to synthesizing decision trees that has been used in a variety of systems. But it lacks of powerful expression and ignores the uncertain data. This thesis proposes a new algorithm (named C-MAX algorithm) to establish decision trees by using 0-1 integer programming, and it can be further utilized to construct one-level trees. Meanwhile, the treatment for uncertain data is also considered in this new algorithm. Finally, this thesis provides the comparison between ID3 and C-MAX algorithm to show the size of decision trees can be much reduced as well as the accuracy and coverage rate can be upgraded.