cs3002-supervised-learning-entropy

The entropy function is used to quantify the uncertainty or randomness associated with the distribution of different classes within a dataset. In the context of ID3 and decision tree algorithms, it is primarily used to determine the best attribute to split the dataset into subsets during the tree-building process. The attribute with the lowest entropy, after the split, is typically chosen as the root of the tree or the next node.

Here’s how the entropy function is defined and used:

1. Entropy Formula: The entropy (H) of a dataset with respect to a specific class (e.g., a binary classification task with classes A and B) is calculated using the following formula:

   $H(S)=-p(A)\ast log2(p(A))-p(B)\ast log2(p(B))$

   • H(S) is the entropy of the dataset S.
   • p(A) is the proportion of data points in class A.
   • p(B) is the proportion of data points in class B.

2. Entropy Interpretation:

   • If all the data points in the dataset belong to a single class (e.g., all A or all B), the entropy is 0 because there is no uncertainty (perfectly pure).
   • If the data points are equally divided between the classes, the entropy is at its maximum, which is 1 (for a binary classification problem). In this case, there is a high degree of uncertainty or disorder.

3. Information Gain: The information gain measures the reduction in entropy that results from partitioning the dataset based on a particular attribute. It is calculated as follows:

   Information Gain $(IG)=H(S)-\sum (Sv/S)\ast H(Sv)$

   • IG is the information gain.
   • H(S) is the entropy of the original dataset.
   • Sv represents the subsets obtained by splitting the dataset using the attribute.
   • H(Sv) is the entropy of each subset Sv.
   • S is the total number of data points in the dataset.

4. Attribute Selection: In the ID3 algorithm, attributes are evaluated based on their information gain. The attribute that maximises the information gain is chosen for the split. This attribute is expected to reduce the uncertainty or entropy the most when creating subsets.

The ID3 algorithm iteratively constructs a decision tree by selecting attributes at each node to minimise the entropy or maximise the information gain. It continues this process until all the data points are classified into their respective classes.

By using the entropy function and information gain, the ID3 algorithm efficiently builds a decision tree that can be used for classification tasks, with the goal of making accurate predictions based on the features of the data.