Decision Trees and Information Gain

Decision Tree and Information Gain

• Compute entropy for the dataset to determine uncertainty.
• Calculate information gain for each feature to identify the highest gain attribute.
• Choose the attribute with maximum gain as the root node (e.g., Outlook).
• Continue this process for subtrees until the desired tree structure is achieved.

Nonparametric Models

• Nonparametric models are characterized by an unbounded set of parameters, contrasting parametric models which have a fixed parameter set.
• These models do not assume any specific distribution for the data.

k-Nearest Neighbors (k-NN)

• k-NN is a simple, non-parametric supervised learning method for classification tasks.
• It classifies new observations based on a similarity measure to the stored training cases.
• Classification is achieved through majority voting among the k-nearest neighbors.
• If k = 1, the object is assigned to the class of the closest neighbor.

Distance Calculation in k-NN

• Euclidean distance is commonly used to measure similarity, especially in continuous data; calculated as:
  [ \text{Distance} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} ]

Naive Bayes Algorithm

• Naive Bayes uses Bayes' Theorem to calculate the posterior probability ( P(c|x) ) of a class given predictor ( x ).
• It requires prior probabilities ( P(c) ), likelihoods ( P(x|c) ), and the prior of the predictor ( P(x) ).
• Calculations involve constructing frequency tables, transforming them into likelihood tables, and using the Naive Bayes equation.

Search Algorithms

• Depth First Search (DFS): Not complete; time complexity ( O(b^m) ); space complexity ( O(b^m) ); optimal if finding a least-cost solution.
• Breadth-First Search (BFS): Complete if branching factor is finite; time complexity ( O(b^d) ); optimal if step cost is uniform.
• Uniform Cost Search (UCS): Complete if branching factor is finite; time complexity ( O(b(c/\epsilon)) ); optimal for non-even costs.
• Depth Limited Search (DLS): Complete if the solution exceeds the depth limit; time complexity ( O(b^l) ).
• Iterative Deepening Depth First Search (IDDFS): Complete with limited depth; time complexity ( O(b^d) ).
• Bidirectional Search (BS): Complete; time complexity ( O(b^{d/2}) ); optimal if step costs are the same in both directions.

Example of Distance Calculation

• Given coordinate points A(5,4) and B(2,3), the Euclidean distance is calculated to be:
  [ \text{Distance} = \sqrt{(5-2)^2 + (4-3)^2} = \sqrt{10} ]

Supervised Learning

• Includes various regression and classification techniques:
  • Linear Regression (simple and multiple).
  • Classification methods:
    • Classification Trees
    • Logistic Regression
    • k-NN
    • Support Vector Machine (SVM)
    • Naive Bayes Classifier

Logistic Regression

• Used for classification tasks as opposed to linear regression which predicts continuous values.
• Applications include spam detecting, tumor classification, and fraud detection.
• Logistic regression estimates the probability of a certain class or event, often using a logistic function.