JNTU MCA MACHINE LEARNING Previous Question Paper (October/ November - 2020 - R17)

The Gain Ratio algorithm addresses the bias of the ID3 algorithm towards attributes with many values by normalizing the Information Gain using the Split Information (Intrinsic Information).

The formulas used are:

Step 1: Initial Entropy of the dataset (S)
Total examples = 13. Play = 7, No Play = 6.
Entropy(S) = - (7/13)log_2(7/13) - (6/13)log_2(6/13) ≈ 0.9957.

Step 2: Calculate Gain Ratio for each attribute
For Outlook (Sunny: 5, Overcast: 3, Rainy: 5):
Entropy(Sunny) = - (2/5)log_2(2/5) - (3/5)log_2(3/5) ≈ 0.971
Entropy(Overcast) = 0 (all play)
Entropy(Rainy) = - (3/5)log_2(3/5) - (2/5)log_2(2/5) ≈ 0.971
Gain(S, Outlook) = 0.9957 - [(5/13)*0.971 + (3/13)*0 + (5/13)*0.971] ≈ 0.247
SplitInfo(S, Outlook) = - (5/13)log_2(5/13) - (3/13)log_2(3/13) - (5/13)log_2(5/13) ≈ 1.554
GainRatio(Outlook) = 0.247 / 1.554 ≈ 0.159

Step 3: Tree Construction
1. Compare Gain Ratio of Outlook, Temp (discretized), Humidity, and Windy. Outlook yields the highest Gain Ratio and is selected as the root node.
2. The 'Overcast' branch is a leaf node labeled 'Play'.
3. For 'Sunny' and 'Rainy' branches, repeat the process recursively using the remaining attributes (Temp, Humidity, Windy) on the subset of data corresponding to those branches.
4. Continue until all leaf nodes are pure or no further attributes remain to split.

The ID3 (Iterative Dichotomiser 3) algorithm is a greedy, top-down approach for constructing a decision tree by selecting the attribute that provides the highest information gain at each step. It uses the concept of Entropy to measure the impurity of a dataset and Information Gain to determine the effectiveness of an attribute in partitioning the data.

The algorithm proceeds as follows:

1. Start with the root node containing all training examples.
2. Calculate the entropy of the current dataset:
   Entropy(S) = -Σ pᵢ log₂(pᵢ)
   where pᵢ is the proportion of examples belonging to class i.
3. For each unused attribute, calculate the information gain:
   Gain(S, A) = Entropy(S) - Σ (|Sᵥ| / |S|) * Entropy(Sᵥ)
   where Sᵥ is the subset of S for which attribute A has value v.
4. Select the attribute with the highest Information Gain.
5. Create a decision node for this attribute and partition the dataset into subsets based on the attribute's values.
6. Recursively apply the algorithm to each subset, creating child nodes.
7. Stop recursion when all examples in a node belong to the same class (pure node), no more attributes are available, or a predefined stopping criterion is met.

ID3 is limited to categorical features and is prone to overfitting, as it does not include a pruning mechanism. It assumes that the training data is noise-free and that all attributes have discrete values.