🧪 ML Lab Programs

All 8 Algorithms — Well Commented for Understanding

Python 3 · scikit-learn · numpy · matplotlib

Topics Covered
1. Find-S Algorithm
2. Candidate Elimination Algorithm
3. Water Jug Problem (BFS)
4. Decision Tree (ID3)
5. K-Nearest Neighbors (KNN)
6. Naïve Bayes Classification
7. EM Algorithm (Gaussian Mixture)
8. Principal Component Analysis (PCA)
 1. Find-S Algorithm

📌 Concept: Find-S finds the MOST SPECIFIC hypothesis consistent with all positive examples. It ignores negative
examples entirely.
💡 Exam Tip: Start with the null hypothesis. For each positive example: if attribute matches → keep it, if differs →
replace with '?' (wildcard).

▶ find_s.py
# ════════════════════════════════════════════════════════
# FIND-S ALGORITHM
# Goal: Find the most specific hypothesis that covers all
# positive training examples.
# Output: A single hypothesis like ['Sunny', '?', 'Normal', ...]
# ════════════════════════════════════════════════════════

# ── Training Data ──────────────────────────────────────

# Format: [Outlook, Temp, Humidity, Wind, Water, Forecast, Label]
# Label 'Yes' = Positive example (enjoy sport)
# Label 'No' = Negative example (don't enjoy)
data = [
['Sunny','Warm','Normal','Strong','Warm','Same', 'Yes'],
['Sunny','Warm','High', 'Strong','Warm','Same', 'Yes'],
['Rainy','Cold','High', 'Strong','Warm','Change','No' ],
['Sunny','Warm','High', 'Strong','Cool','Change','Yes'],
]

# Separate feature columns from label column

features = [row[:-1] for row in data] # All columns except last
labels = [row[-1] for row in data] # Only the last column

# ── Step 1: Initialize hypothesis with first POSITIVE example ──

# This is the 'most specific' starting point.
hypothesis = None
for feat, label in zip(features, labels):
if label == 'Yes': # Found first positive
hypothesis = feat[:] # Copy it as initial hypothesis
break # Stop after first positive

print('Initial hypothesis:', hypothesis)

# ── Step 2: Iterate through ALL examples ──────────────────────

# For each POSITIVE example, generalize where needed.
# Negative examples are IGNORED in Find-S.
for feat, label in zip(features, labels):
 if label == 'Yes': # Only process positive examples
for i in range(len(hypothesis)):
if hypothesis[i] != feat[i]:
# Attributes differ → generalize with '?'
hypothesis[i] = '?'
print('After example', feat, '→', hypothesis)

print('\n=== Final Find-S Hypothesis ===\n', hypothesis)

💡 Exam Tip: Output will look like: ['Sunny', 'Warm', '?', 'Strong', '?', '?'] — '?' means 'accept any value for this
attribute'.
 2. Candidate Elimination Algorithm

📌 Concept: Maintains TWO boundaries: S (most specific) and G (most general). All valid hypotheses lie between
them — this is the VERSION SPACE.
💡 Exam Tip: Positive example → generalize S + prune G. Negative example → specialize G + prune S. Final S=G
means unique hypothesis found.

▶ candidate_elimination.py
# ════════════════════════════════════════════════════════
# CANDIDATE ELIMINATION ALGORITHM
# S-boundary: most specific consistent hypothesis
# G-boundary: most general consistent hypothesis
# Version Space = all hypotheses between S and G
# ════════════════════════════════════════════════════════

data = [
['Sunny','Warm','Normal','Strong','Warm','Same', 'Yes'],
['Sunny','Warm','High', 'Strong','Warm','Same', 'Yes'],
['Rainy','Cold','High', 'Strong','Warm','Change','No' ],
['Sunny','Warm','High', 'Strong','Cool','Change','Yes'],
]
features = [row[:-1] for row in data]
labels = [row[-1] for row in data]
n = len(features[0]) # Number of attributes

# ── Initialize Boundaries ───────────────────────────────────

# S starts as None (most specific = nothing matches)
# G starts as [['?','?',...]] (most general = everything matches)
S = [None] * n # Null hypothesis — nothing
G = [['?'] * n] # Universal hypothesis — everything

# ── Process each training example ───────────────────────────

for feat, label in zip(features, labels):

if label == 'Yes': # ── POSITIVE EXAMPLE ──

# Generalize S to include this example
if S[0] is None:
S = feat[:] # First positive → init S
else:
for i in range(n):
if S[i] != feat[i]:
S[i] = '?' # Generalize differing attribute
# Remove G hypotheses that DON'T cover this positive example
G = [g for g in G if all(g[i]=='?' or g[i]==feat[i] for i in range(n))]
 elif label == 'No': # ── NEGATIVE EXAMPLE ──
# Specialize G so it no longer covers this negative example
new_G = []
for g in G:
for i in range(n):
if g[i] == '?': # This attribute is too general
for val in set(r[i] for r in features):
if val != feat[i]: # Any specific value except
negative's
new_h = g[:]
new_h[i] = val
# Keep only if consistent with S
if all(new_h[j]=='?' or new_h[j]==S[j] for j in
range(n)):
new_G.append(new_h)
G = new_G if new_G else G # Update G

print(f'\nAfter {feat}, label={label}')

print('S =', S)
print('G =', G)

print('\n=== Final Version Space ===')

print('S (specific):', S)
print('G (general) :', G)

💡 Exam Tip: If S == G at the end, there is exactly ONE hypothesis consistent with all examples. Otherwise the
version space contains multiple possibilities.
 3. Water Jug Problem (BFS)

📌 Concept: Given two jugs (capacity 4L and 3L) and no measuring marks, obtain exactly 2L using BFS to explore
all possible states.
💡 Exam Tip: State = (water_in_jug_A, water_in_jug_B). 6 possible actions: fill A, fill B, empty A, empty B, pour
A→B, pour B→A. BFS finds shortest path.

▶ water_jug.py
from collections import deque # deque = double-ended queue, used for BFS

# ── Main BFS Function ───────────────────────────────────────

# cap_a = capacity of Jug A
# cap_b = capacity of Jug B
# target = amount we want to measure
def water_jug_bfs(cap_a, cap_b, target):
start = (0, 0) # Both jugs empty initially
visited = set() # Track visited states to avoid loops
queue = deque() # BFS queue
[Link]((start, [start])) # (current_state, path_so_far)

while queue:
(a, b), path = [Link]() # Pop from front (BFS)

# ── Goal Check ─────────────────────────────────────

# Stop if either jug holds the target amount
if a == target or b == target:
print(f'\n✅ Goal reached: {(a,b)}')
print('\nSteps taken:')
for step in path:
print(f' Jug A: {step[0]}L | Jug B: {step[1]}L')
return path

if (a, b) in visited:
continue # Skip already visited states
[Link]((a, b))

# ── Generate All Possible Next States ────────────────

# Each line below is one 'action'
next_states = [
(cap_a, b), # Action 1: Fill Jug A to max
(a, cap_b), # Action 2: Fill Jug B to max
(0, b), # Action 3: Empty Jug A completely
(a, 0), # Action 4: Empty Jug B completely
# Action 5: Pour A → B (pour as much as fits in B)
 (a - min(a, cap_b - b), b + min(a, cap_b - b)),
# Action 6: Pour B → A (pour as much as fits in A)
(a + min(b, cap_a - a), b - min(b, cap_a - a)),
]

for state in next_states:

if state not in visited:
[Link]((state, path + [state]))

print('No solution found!')

return None

# ── Run the problem ──────────────────────────────────────────

# Classic: 4L jug, 3L jug → get exactly 2L
water_jug_bfs(cap_a=4, cap_b=3, target=2)

💡 Exam Tip: The key formula for pouring: min(amount_in_source, space_in_dest). This ensures you never
overflow or go negative.
 4. Decision Tree (ID3 Algorithm)

📌 Concept: ID3 builds a tree by selecting the attribute with highest Information Gain at each node. Entropy
measures impurity; high IG means the split is more informative.
💡 Exam Tip: Entropy = -Σ p*log2(p). Information Gain = Entropy(parent) - weighted avg Entropy(children). Pick
attribute with MAX Information Gain.

▶ decision_tree.py
import numpy as np
import pandas as pd
from [Link] import load_iris
from [Link] import DecisionTreeClassifier, export_text
from sklearn.model_selection import train_test_split
from [Link] import accuracy_score, classification_report
import [Link] as plt
from sklearn import tree

# ── Load Dataset ─────────────────────────────────────────────

# Iris: 150 flowers, 4 features (sepal/petal length & width), 3 classes
iris = load_iris()
X = [Link] # Feature matrix (150 x 4)
y = [Link] # Labels: 0=setosa, 1=versicolor, 2=virginica

# ── Split into Train / Test ───────────────────────────────────

# 70% training, 30% testing | random_state=42 for reproducibility
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42
)

# ── Build Decision Tree ──────────────────────────────────────

# criterion='entropy' → uses Information Gain (ID3 style)
# criterion='gini' → uses Gini impurity (CART style)
# max_depth=4 → limit tree height to prevent overfitting
clf = DecisionTreeClassifier(
criterion='entropy', # ID3 uses entropy
max_depth=4, # Depth limit
random_state=42
)
[Link](X_train, y_train) # Train the tree

# ── Predict & Evaluate ────────────────────────────────────────

y_pred = [Link](X_test) # Predict on test set

print('=== Decision Tree (ID3) ===\n')

print(f'Accuracy: {accuracy_score(y_test, y_pred)*100:.2f}%')
print('\nClassification Report:')
print(classification_report(y_test, y_pred, target_names=iris.target_names))

# ── Print Tree Structure ──────────────────────────────────────

# export_text shows the actual decision rules in text form
print('\n--- Decision Tree Rules ---')
print(export_text(clf, feature_names=list(iris.feature_names)))

# ── Plot the Tree ─────────────────────────────────────────────

[Link](figsize=(14, 6))
tree.plot_tree(clf,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, # Color nodes by class
rounded=True) # Rounded boxes
[Link]('Decision Tree — ID3 (Iris Dataset)')
plt.tight_layout()
[Link]('decision_tree.png')
[Link]()

💡 Exam Tip: Key formula: Entropy(S) = -p+ log2(p+) - p- log2(p-). For multi-class: sum over all classes. IG =
E(parent) - Σ(|Sv|/|S|)*E(Sv).
 5. K-Nearest Neighbors (KNN)

📌 Concept: A lazy learner — no explicit training. At prediction, find K most similar training points (by distance)
and take majority vote for classification.
💡 Exam Tip: Common distance = Euclidean: sqrt(Σ(xi-yi)²). Small K = complex boundary (overfit), Large K = smooth
boundary (underfit). Best K found by cross-validation.

▶ [Link]
import numpy as np
from [Link] import load_iris
from [Link] import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from [Link] import accuracy_score, confusion_matrix
import [Link] as plt

# ── Load & Split Data ─────────────────────────────────────────

iris = load_iris()
X, y = [Link], [Link]

X_train, X_test, y_train, y_test = train_test_split(

X, y, test_size=0.3, random_state=42
)

# ── Find Best K ───────────────────────────────────────────────

# We try K=1 to K=14 and pick whichever gives highest accuracy
accuracies = []
k_range = range(1, 15) # Test K values from 1 to 14

for k in k_range:
knn = KNeighborsClassifier(
n_neighbors=k, # How many neighbors to look at
metric='euclidean' # Distance formula
)
[Link](X_train, y_train) # No real 'training', just stores data
acc = accuracy_score(y_test, [Link](X_test))
[Link](acc)

best_k = list(k_range)[[Link](accuracies)] # K with highest accuracy

print(f'Best K = {best_k} | Accuracy = {max(accuracies)*100:.2f}%')

# ── Train Final Model with Best K ─────────────────────────────

knn_best = KNeighborsClassifier(n_neighbors=best_k)
knn_best.fit(X_train, y_train)
y_pred = knn_best.predict(X_test)
# ── Confusion Matrix ──────────────────────────────────────────
# Rows = actual class, Columns = predicted class
# Diagonal = correct predictions
cm = confusion_matrix(y_test, y_pred)
print('\nConfusion Matrix:\n', cm)

# ── Plot Accuracy vs K ────────────────────────────────────────

[Link](figsize=(8, 4))
[Link](list(k_range), accuracies, marker='o', color='steelblue')
[Link](best_k, color='red', linestyle='--', label=f'Best K={best_k}')
[Link]('K (Number of Neighbors)')
[Link]('Accuracy')
[Link]('KNN: Accuracy vs K')
[Link]()
[Link](True)
plt.tight_layout()
[Link]('knn_accuracy.png')
[Link]()

💡 Exam Tip: KNN has NO training phase (lazy learner). Time complexity is O(n*d) per query (n=samples,
d=dimensions). Feature scaling (StandardScaler) is important for fair distance comparison.
 6. Naïve Bayes Classification

📌 Concept: Uses Bayes' Theorem: P(class|features) ∝ P(class) × ∏P(feature_i|class). 'Naïve' = assumes all
features are independent given the class.
💡 Exam Tip: P(Y|X) = P(X|Y)·P(Y) / P(X). For classification, pick class Y that maximizes P(Y|X). Denominator P(X) is
same for all classes, so ignore it.

▶ naive_bayes.py
import numpy as np
import pandas as pd
from sklearn.naive_bayes import GaussianNB
from [Link] import load_iris
from sklearn.model_selection import train_test_split
from [Link] import accuracy_score, classification_report

# ════════════════════════════════════════════════════════════
# PART A: Gaussian Naïve Bayes on Iris (continuous features)
# GaussianNB assumes each feature follows a Gaussian (normal) distribution
# ════════════════════════════════════════════════════════════
iris = load_iris()
X, y = [Link], [Link]

X_train, X_test, y_train, y_test = train_test_split(

X, y, test_size=0.3, random_state=42
)

gnb = GaussianNB() # Gaussian Naïve Bayes model

[Link](X_train, y_train) # Learns mean & variance per class
y_pred = [Link](X_test) # Predicts using Bayes theorem

print('=== Gaussian Naïve Bayes (Iris) ===')

print(f'Accuracy: {accuracy_score(y_test, y_pred)*100:.2f}%')
print(classification_report(y_test, y_pred, target_names=iris.target_names))

# ════════════════════════════════════════════════════════════
# PART B: Manual Naïve Bayes on Play Tennis (categorical)
# This shows the calculation step by step
# ════════════════════════════════════════════════════════════
print('\n=== Manual Naïve Bayes — Play Tennis ===')

data = [Link]([
['Sunny', 'Hot', 'High', 'Weak', 'No' ],
['Sunny', 'Hot', 'High', 'Strong','No' ],
['Overcast','Hot', 'High', 'Weak', 'Yes'],
 ['Rain', 'Mild', 'High', 'Weak', 'Yes'],
['Rain', 'Cool', 'Normal','Weak', 'Yes'],
['Rain', 'Cool', 'Normal','Strong','No' ],
['Overcast','Cool','Normal','Strong','Yes'],
['Sunny', 'Mild', 'High', 'Weak', 'No' ],
['Sunny', 'Cool', 'Normal','Weak', 'Yes'],
['Rain', 'Mild', 'Normal','Weak', 'Yes'],
], columns=['Outlook','Temp','Humidity','Wind','Play'])

# Test sample: new day, predict if we play tennis

test = {'Outlook':'Sunny','Temp':'Cool','Humidity':'High','Wind':'Strong'}
features= ['Outlook','Temp','Humidity','Wind']
classes = ['Yes','No']

# For each class, compute P(class) × P(f1|class) × P(f2|class) × ...

for cls in classes:
subset = data[data['Play'] == cls] # Rows of this class
prob = len(subset) / len(data) # Prior probability P(class)

for feat in features:

count = len(subset[subset[feat] == test[feat]])
# Conditional probability P(feature=value | class)
prob *= count / len(subset)

print(f'P(Play={cls} | test) ∝ {prob:.6f}')

print('(Higher value = predicted class)')

💡 Exam Tip: Laplace smoothing: add 1 to each count to avoid zero probability when a feature value never appears
with a class in training data. sklearn does this automatically.
 7. EM Algorithm (Gaussian Mixture Model)

📌 Concept: EM finds maximum likelihood estimates when some data is hidden/latent. Two steps: E-step
(estimate which cluster each point belongs to) and M-step (update cluster parameters).
💡 Exam Tip: E-step: compute P(cluster_k | point_i) for each point. M-step: update means, variances, and weights
using weighted averages. Repeat until log-likelihood converges.

▶ em_algorithm.py
import numpy as np
import [Link] as plt
from [Link] import GaussianMixture
from [Link] import make_blobs

# ── Generate Synthetic Data with 3 clusters ──────────────────

# make_blobs creates Gaussian clusters perfect for GMM
X, true_labels = make_blobs(
n_samples=300, # 300 data points
centers=3, # 3 cluster centers
cluster_std=0.8, # Spread of each cluster
random_state=42
)

# ── Apply Gaussian Mixture Model (EM) ────────────────────────

# GMM uses the EM algorithm internally to fit Gaussian distributions
gmm = GaussianMixture(
n_components=3, # Number of clusters (Gaussians)
covariance_type='full', # Each cluster has its own covariance matrix
max_iter=100, # Maximum EM iterations
init_params='kmeans', # Initialize using K-Means
random_state=42
)

# fit() runs the EM loop:

# E-step: compute soft assignments (responsibilities)
# M-step: update means, covariances, mixing weights
# Repeat until log-likelihood change < tolerance
[Link](X)
labels = [Link](X) # Hard assignment (MAP estimate)
probs = gmm.predict_proba(X) # Soft assignment (responsibilities)

print('=== EM Algorithm — GMM ===')

print(f'Converged : {gmm.converged_}')
print(f'Iterations : {gmm.n_iter_}')
print(f'Log-Likelihood: {gmm.lower_bound_:.4f}')
print('\nCluster Means:\n', gmm.means_)
print('\nMixture Weights:', gmm.weights_)

# ── Visualization ─────────────────────────────────────────────
colors = ['#60a5fa','#f472b6','#34d399']
[Link](figsize=(8, 5))
for i in range(3):
[Link](X[labels==i, 0], X[labels==i, 1],
c=colors[i], label=f'Cluster {i+1}',
alpha=0.6, s=30)
# Plot cluster centers (learned means)
[Link](gmm.means_[:, 0], gmm.means_[:, 1],
c='red', marker='X', s=200, zorder=5, label='Centroids')
[Link]('EM Algorithm — GMM Clustering')
[Link]()
plt.tight_layout()
[Link]('em_clusters.png')
[Link]()

💡 Exam Tip: EM guarantees improvement of log-likelihood each iteration but may converge to a LOCAL
maximum. Run multiple times with different initializations (n_init parameter) for better results.
 8. Principal Component Analysis (PCA)

📌 Concept: PCA reduces dimensionality by finding the directions (principal components) of maximum variance in
the data. PC1 explains the most variance, PC2 the next most, and so on.
💡 Exam Tip: Steps: 1) Standardize data 2) Compute covariance matrix 3) Compute eigenvectors & eigenvalues 4)
Sort by eigenvalue 5) Project onto top-k eigenvectors.

▶ [Link]
import numpy as np
import [Link] as plt
from [Link] import PCA
from [Link] import StandardScaler
from [Link] import load_iris

# ── Load Dataset ─────────────────────────────────────────────

# Iris has 4 features → we will reduce to 2 for visualization
iris = load_iris()
X, y = [Link], [Link] # Shape: (150, 4)

# ── Step 1: Standardize Data ──────────────────────────────────

# CRITICAL: PCA is sensitive to scale.
# StandardScaler: subtract mean, divide by std → mean=0, std=1
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X) # Standardized feature matrix

# ── Step 2: Apply PCA (reduce 4D → 2D) ───────────────────────

# Internally: covariance matrix → eigendecomposition → sort by eigenvalue
pca = PCA(n_components=2) # Keep top 2 principal components
X_pca = pca.fit_transform(X_scaled) # Project data onto new axes

print('=== PCA Results ===')

print(f'Original shape : {[Link]} # 150 samples × 4 features')
print(f'Reduced shape : {X_pca.shape} # 150 samples × 2 components')

# Explained Variance Ratio: how much variance each PC captures

print(f'\nVariance by PC1: {pca.explained_variance_ratio_[0]*100:.2f}%')
print(f'Variance by PC2: {pca.explained_variance_ratio_[1]*100:.2f}%')
print(f'Total Variance Explained: {sum(pca.explained_variance_ratio_)*100:.2f}%')

# The principal components (eigenvectors) = the new axes

print('\nPrincipal Components (eigenvectors):')
for i, comp in enumerate(pca.components_):
print(f'PC{i+1}: {comp}')
# ── Plot 1: 2D Scatter after PCA ─────────────────────────────
fig, axes = [Link](1, 2, figsize=(13, 5))
colors = ['#60a5fa','#f472b6','#34d399']

for i, name in enumerate(iris.target_names):

axes[0].scatter(X_pca[y==i, 0], X_pca[y==i, 1],
c=colors[i], label=name, alpha=0.7, s=50)
axes[0].set_xlabel('Principal Component 1')
axes[0].set_ylabel('Principal Component 2')
axes[0].set_title('PCA — Iris (4D → 2D)')
axes[0].legend()

# ── Plot 2: Scree Plot (variance explained per component) ─────

# Shows how much each PC contributes — helps decide how many to keep
pca_full = PCA().fit(X_scaled) # All 4 components
axes[1].bar(range(1, 5), pca_full.explained_variance_ratio_*100,
color='#a78bfa', edgecolor='white')
axes[1].set_xlabel('Principal Component')
axes[1].set_ylabel('Variance Explained (%)')
axes[1].set_title('Scree Plot — Iris')
axes[1].set_xticks(range(1, 5))

plt.tight_layout()
[Link]('pca_result.png')
[Link]()

💡 Exam Tip: The 'elbow' in the scree plot tells you how many PCs to keep. If PC1+PC2 explain >95% variance, 2
components is sufficient. PCA is unsupervised — it doesn't use class labels.