Decision Trees: Definition, Learning & Construction

Decision Trees

Definition

• Classification algorithm that divides feature space into smaller regions until each region contains data points of a single class.
• Each node represents a question about a feature.
• Each branch represents a possible answer.
• Each leaf represents a class.

Learning

• Involves two steps: tree construction and pruning.
• Tree construction involves choosing the feature that best separates the data into groups.
• Pruning involves removing insignificant branches.

Tree Construction

• A recursive process is used.
• The feature that best separates the data into two groups is selected.
• A node is created for this feature.
• Two branches are created for the two data groups.
• The process repeats for each branch.

Feature Selection Criteria

• Gini Index measures the probability that a randomly selected element will be misclassified if labeled randomly according to the distribution of labels in the set.
  • $Gini = 1 - \sum_{i=1}^{n} P_i^2$, where $P_i$ is the probability of class i.
• Entropy measures disorder in a dataset.
  • $H(X) = - \sum_{i=1}^{n} P(x_i) log_2 P(x_i)$, where $P(x_i)$ is the probability of the value $x_i$.

Advantages

• Easy to understand and interpret.
• Can be used for both numerical and categorical data.
• Used for classification and regression problems.

Disadvantages

• Sensitive to noise in the data.
• Prone to overfitting.

k-Nearest Neighbors (k-NN)

Definition

• Classification algorithm that assigns a data point to the most frequent class among its k-nearest neighbors.
• 'k' is a parameter.
• Distance between data points can be calculated in various ways, such as Euclidean or Manhattan distance.

Learning

• Learning involves storing the training data.

Prediction

• To predict a new data point, its distance is calculated from all training data points.
• The k-nearest neighbors are selected.
• The new point is assigned to the most frequent class among those neighbors.

Advantages

• Simple to understand and implement.
• Used for classification and regression problems.

Disadvantages

• Poor performance with large datasets.
• Sensitive to the choice of distance metric and the value of k.
• Requires data normalization.

Support Vector Machine (SVM)

Definition

• Classification algorithm that finds the hyperplane that best separates data into two classes.
• The hyperplane maximizes the margin between the two classes.
• Support vectors are the data points closest to the hyperplane.

Learning

• Finding the hyperplane that maximizes the margin between the two classes.
• This problem is solvable using quadratic programming or more efficient algorithms like gradient descent.

Prediction

• To predict a new data point, its distance is calculated from the hyperplane.
• The point is assigned to the class corresponding to the side of the hyperplane where it lies.

Advantages

• Performs well for binary classification problems.
• Relatively insensitive to noisy data.
• Can be used for nonlinear classification with the kernel trick.

Disadvantages

• Poor performance with large datasets.
• Sensitive to the choice of kernel and parameters.

Multi-Layer Perceptron (MLP)

Definition

• An artificial neural network consisting of multiple layers of interconnected neurons.
• Each neuron receives inputs from the previous layer, performs a linear transformation, and applies an activation function.
• The activation function can be sigmoid, hyperbolic tangent, or ReLU.

Learning

• Adjusting the connection weights between neurons to minimize the error between the network output and the desired output.
• The backpropagation algorithm is used to calculate the gradient of the error with respect to the weights.
• The weights are adjusted in the opposite direction of the gradient.

Prediction

• The data point is presented to the network input, and the network calculates the corresponding output to predict a new data point.

Advantages

• Can be used for complex classification problems.
• Can be used for nonlinear classification problems.

Disadvantages

• Difficult to interpret.
• Prone to overfitting.
• Requires a lot of training data.