@INPROCEEDINGS { Rsds3827,
author = {Tsumoto, Shusaku and Tanaka, Hiroshi}, 
title = {Characterization of Structure of Decision Tree Based on Rough Sets and Greedoid Theory}, 
booktitle = {Soft Computing}, 
conference = {International Workshop on Rough Sets and Soft Computing}, 
pages = {271--275}, 
publisher = {The Society for Computer Simulation}, 
address = {San Diego, U.S.A.}, 
month = {November}, 
year = 1994, 
editor = {Lin, Tsau Young and Wildberger, A.M.}, 
isbn = {1-56555-077-3}, 
abstract = {We formerly introduced matroid theory and rough sets to describe algebraic characteristics of empirical learning methods which induce knowledge from attribute-value pattern databases. It was shown that combination of the concepts of rough sets and matroid theory gives us an excellent framework and enables us to understand the differences of these methods clearly. However, this method does not capture the differences between truncation and pruning, since matriods cannot deal with the ordering of those elements. In order to solve this problem, we introduce greedoid theory, which is the extension of matroid theory, and apply it to the formalization of the search space of ID3 method, which we call ID3 greedoid. The results show that combination of greedoids and rough sets gives us a simple framework of describing truncation sets given us a simple framework of describing truncation and pruning in terms of the search space spanned by attribute-value pairs and that structural constraints of ID3 cause ID3 greedoid to lose the interval property, which is one of the most important characteristics of matroids.}, 
keywords = {machine learning, decision-tree learning, rough sets, matroid theory, greedoid theory, }, 
}