[Type the document title]
DR. B R AMBEDKAR NIT JALANDHAR Page 1
HUNT’S ALGORITHM
Classification-rule learning involves finding rules or decision trees that partition given data into
predefined classes. For any realistic problem domain of the classification-rule learning, the set of
possible decision trees is too large to be searched exhaustively. In fact, the computational
complexity of finding an optimal classification decision tree is NP hard.
Most of the existing induction-based algorithms use Hunt's method as the basic algorithm.Here
is a recursive description of Hunt's method for constructing a decision tree from a set T of
training cases with classes denoted {C
1
, C
2
, … ,C
k
}.
Case 1:
T contains one or more cases, all belonging to a single class C
j
: The decision tree for T is a leaf
identifying class c
j.
Case 2:
T contains no cases: The decision tree for T is a leaf, but the class to be associated with the leaf
must be determined from information other than T.
Case 3:
T contains cases that belong to a mixture of classes: A test is chosen, based on a single attribute,
that has one or more mutually exclusive outcomes {O
1
, O
2
, .. ,O
n
}. T is partitioned into subsets
T
1
, T
2
, … ,T
n
, where T
i
contains all the cases in T that have outcome O
i
of the chosen test. The
decision tree for T consists of a decision node identifying the test, and one branch for each
possible outcome. The same tree building machinery is applied recursively to each subset of
training
Table 2.1: A small training data set [2]
Outlook
Temp(F)
Humidity(%)
Windy?
Class
sunny
75
70
true
Play
