在分類樹建構上數值型屬性的啟發式分割法

A Heuristic Partition Method of Numerical Attributes in Classification Tree Construction

曾文科(Wen-Ke Tseng)

指導教授 ： 顏語青 ； 楊燕珠

大同大學/經營設計學院/資訊經營學系所/碩士(2004年)

摘要

歸納式學習法(Inductive Learning)是一種廣被應用於機器學習(Machine Learning)領域的一種學習法，分類樹(Classification Trees)便是其中相當有名的一種歸納學習法。Quinlan在1986年提出ID3分類樹演算法，此演算法在分類樹的建構上已有相當不錯的表現，又於1993年針對ID3的一些缺點而提出C4.5，但是C4.5在面對數值型屬性(Numerical Attributes)分割點的搜尋上並沒有相當好的效率。雖然相繼有釵h學者提出改善方法甚至提出新的分割方法，然而這些方法都有其假設與限制。因此，我們以C4.5演算法為基礎提出一啟發式分割方法，來改善原本C4.5演算法無法有效率地處理數值型屬性的分割點搜尋。此一啟發式分割方法能在數值型屬性的分割點搜尋上大大地降低其搜尋時間。

關鍵字

C4.5演算法 ； ID3演算法 ； 分類樹 ； 數值型屬性

並列摘要

Inductive Learning, a kind of learning methods, has been applied extensively in Machine Learning. Thus, Classification tree is a well-known method in Inductive Learning. The ID3, a popular classification tree algorithm, had been proposed by Quinlan on 1986. Quinlan proposed the C4.5 algorithm on 1993 again. The C4.5 has not been efficiently searching the splitting points on numerical attributes. Therefore, some researchers had proposed improved approaches and new partition methods for the partition on numerical attributes. However, these approaches and methods have its assumptions and restrictions. So we have proposed a heuristic partition method to improve the defect, which the C4.5 algorithm could not process numerical attributes efficiently. Since the heuristic partition method is based on C4.5 algorithm, the method can greatly reduce the time for searching splitting point on numerical attributes.

並列關鍵字

C4.5 Algorithm ； Classification Tree ； ID3 Algorithm ； Numerical Attribute

參考文獻

[1] Breiman, L. et. al., 1984. Classification and Regression Trees. Wadsworth, Belmont.

[2] Chen, T.Y. and Poon, P.L., 1996. Classification-Hierarchy Table: A Methodology for Construction the Classification Tree. In Proceedings of Australian Software Engineering Conference, pp.93-104.

[3] Chen, T.Y., Poon, P.L. and Tse, T.H., 1999. A New Restructuring Algorithm for the Classification-Tree Method. Proceedings of 9th International Workshop on Software Technology and Engineering Practice (IEEE Computer Society, Los Alamitos, CA), pp.105-114

[4] Chen, T.Y., Poon, P.L. and Tse, T.H., 2002. Classification-tree Restructuring Methodologies: A New Perspective. IEE Proceedings: Software, 149(2), pp.65-74.

[10] Fayyad, U.M., 1992. On the Handling of Continuous-Valued Attributes in Decision Tree Generation. Machine Learning, 8, pp.87-102.