決策樹形式知識的合併修剪之研究

A Decision-Tree-Based Merging-Pruning Approach

馬芳資(Fang-Tz Ma) ； 林我聰(Woo-Tsong Lin)

《Electronic Commerce Studies》 4卷2期 (2006/06) Pp. 123-156

https://doi.org/10.29767/ECS.200606.0001

摘要

隨著知識經濟時代的來臨，知識的產生、儲存、應用、整合等已成為重要的討論議題，本研究將針對知識整合此一議題進行探討；而在知識的呈現方式中，決策樹(Decision Tree)形式知識為樹狀結構，可用圖形化方式加以呈現，它的結構簡單且易於瞭解，本研究擬針對決策樹形式知識來探討其知識整合的課題。本研究提出一個決策樹合併修剪方法DTBMPA (Decision-Tree-Based Merging-Pruning Approach)以整合既有／原始的決策樹形式知識；此方法包括三個主要程序：決策樹合併、修剪，和驗證，其做法是先將兩棵原始樹經由合併程序結合成一棵合併樹，再透過修剪程序產生修剪樹，最後由驗證程序來評估修剪樹的準確度。此決策樹合併修剪方法藉由合併程序來擴大樹的知識，再利用修剪程序來修剪合併後樹的過度分支。在本研究的實驗中，合併樹的準確度優於原始一棵樹的比率有90%，而修剪樹的準確度大於或等於合併樹的比率有80%。在統計檢定中，合併樹和修剪樹的準確度優於原始一棵樹的準確度達顯著差異；而修剪樹與合併樹的準確度雖無顯著差異。然在節點數的比較上，修剪樹的節點數較合併樹的節點數平均約少了15%。

關鍵字

知識整合 ； 決策樹 ； 決策樹合併 ； 決策樹修剪

並列摘要

Along with approaching of knowledge economy era, knowledge creation, retaining, application and integration are becoming the important themes for discussion in nowadays. This research tends to focus on discussion of knowledge integration and regarding subjects. In the way of knowledge representation, ”decision tree” is the most common type to show the knowledge structure in a tree-shaped graphic. This ”decision tree” is considerably simple and easy understanding, thus we focus on decision-tree-based knowledge in connection with knowledge integration theme. Our research proposes an approach called DTBMPA (Decision-Tree-Based Merging-Pruning Approach) to integrate the knowledge of decision trees. There are 3 steps included in this approach. In the merging step, the first step, two primitive decision trees are merged as a merged tree to enlarge the knowledge of primitive trees. In the pruning step, the second step, the merged tree from the first step is pruned as a pruned tree to cut off the bias branches of the merged tree. In the validating step, the last step, the performance of the pruned tree from the second step is validated. In the simulation experiments, the percentage accuracy for the merged tree will have 90% of chance that is greater than or equal to the accuracy for those primitive trees, and the percentage accuracy for the pruned tree will have 80% of chance that is greater than or equal to the accuracy for merged tree. And we also find that the average number of nodes of the pruned tree will have 15% less than that of the merged tree.

並列關鍵字

Knowledge Integration ； Decision Tree ； Decision Tree Merging ； Decision Tree Pruning

參考文獻

馬芳資、林我聰(2003)。決策樹形式知識之線上預測系統架構。圖書館學與資訊科學。29(2)，60-76。

馬芳資()。

陳重銘(1995)。結合直線最適法於決策樹修剪之影響研究(碩士論文)。國立中山大學資訊管理研究所。

曾憲雄、黃國禎(2005)。人工智慧與專家系統－理論／實務／應用。台北市:旗標出版股份公司。

Bauer, E.,Kohavi, R.(1999).An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants.Journal of Machine Learning.36(1/2)