基因演算之模糊ID3方法和其決策樹的修剪研究

Abstract

ID3演算法是一種對於符號屬性資料的決策樹歸納且普遍有效的方法。然而，進一步能結合人類思考與感覺的知識法則有著不精確和不確定性，為了獲取不精確和不確定的知識，因此ID3決策樹方法乃推廣至模糊集語試之模糊ID3決策樹，它和ID3演算法的特徵有高度可推廣至模糊集之語試變數，並且自然擴展到應用在包含連續數值屬性的資料集。但是模糊ID3演算法只能處理連續數值資料，並且通常被批評為不夠高的辨識準確性。在本篇論文中，我們提出一個產生模糊決策樹的新方法，它可以接受非連續數值、連續數值或混雜型的資料並使用基因演算法調整決策樹法則相關的模糊集合。此外，我們提出三種決策樹刪減的方法並且加以比較，進而選擇較好的決策樹刪減方法以得到更好的正確率或是更精簡的規則庫。我們利用一些著名的資料集來測試我們所提出的方法，並且選用最好的決策樹刪減方法，以五摺交叉評比方式的結果跟C5.0方法比較，在實驗數據顯示，我們的方法有較好的結果。

ID3 algorithm is a popular and efficient method for decision tree induction from symbolic data. However, most knowledge associated with human’s thinking and perception has some imprecision and uncertainty. For the purpose of handling imprecise and uncertain knowledge; hence, ID3 has been expanded to developed a kind of decision tree is fuzzy ID3 algorithm, which is similar to ID3 algorithm and is extended to apply a data set containing continuous attribute values. But fuzzy ID3 algorithm can only deal with continuous data and it is often criticized to result in poor learning accuracy. In this thesis, we propose a genetic algorithm based fuzzy ID3 method to construct fuzzy classification system, which can accept continuous, discrete, or mixed-mode data sets. Furthermore, we formulate and compare three pruning methods, then choose better pruning method of decision tree to obtain better accuracy or a more efficient rule base. We have tested our method on some famous data sets, and the results of a five-fold cross validation are compared to those by C5.0. The experiments show that our method works better in practice.