Database Reference
In-Depth Information
If the truth level of one of the classes is above a predefined threshold
β then no additional partitioning is needed and the node become a leaf in
which all instance will be labeled to the class with the highest truth level.
Otherwise the procedure continues in a recursive manner. Note that small
values of β will lead to smaller trees with the risk of underfitting. A higher
β may lead to a larger tree with higher classification accuracy. However, at
a certain point, higher values β may lead to overfitting.
14.7 Simplifying the Decision Tree
Each path of branches from root to leaf can be converted into a rule with
the condition part representing the attributes on the passing branches from
the root to the leaf and the conclusion part representing the class at the leaf
with the highest truth level classification. The corresponding classification
rules can be further simplified by removing one input attribute term at a
time for each rule we try to simplify. Select the term to remove with the
highest truth level of the simplified rule. If the truth level of this new rule
is not lower than the threshold β or the truth level of the original rule,
the simplification is successful. The process will continue until no further
simplification is possible for all the rules.
14.8 Classification of New Instances
In a regular decision tree, only one path (rule) can be applied for every
instance. In a fuzzy decision tree, several paths (rules) can be applied for
one instance. In order to classify an unlabeled instance, the following steps
should be performed [ Yuan and Shaw (1995) ] :
Step 1: Calculate the membership of the instance for the condition part
of each path (rule). This membership will be associated with the label
(class) of the path.
Step 2: For each class, calculate the maximum membership obtained from
all applied rules.
Step 3: An instance may be classified into several classes with different
degrees based on the membership calculated in Step 2.
14.9 Other Fuzzy Decision Tree Inducers
There have been several fuzzy extensions to the ID3 algorithm. The UR-
ID3 algorithm [ Maher and Clair (1993) ] starts by building a strict decision
tree, and subsequently fuzzifies the conditions of the tree. Tani and Sakoda
Search WWH ::




Custom Search