CMSC 320
Introduction to Machine Learning
Turn information into knowledge
Instructor
Fardina Fathmiul Alam
Course Resource
Textbook: Chapter 10: link
The Problem:
A lady walks into your bank and requests a loan.
Ques: How do you know whether to give this woman a loan?
Let’s say: You Have Historical Data:
New Case:
Name | Income | Wealth | Job | Paid Back Loan |
Alice | 100,000 | 300,000 | Finance | Yes |
Bob | 150,000 | 10,000 | Gambler | No |
Eve | 500,000 | 1,500,000 | Hitman | Yes |
Fardina | 100,000 | -100,000 | Professor | No |
Joan | 100,000 | 350,000 | Finance | ? |
Ques: How do you know whether to give this woman a loan?
Obvious Solution:
Name | Income | Wealth | Job | Paid Back Loan |
Alice | 100,000 | 300,000 | Finance | Yes |
Bob | 150,000 | 10,000 | Gambler | No |
Eve | 500,000 | 1,500,000 | Hitman | Yes |
Max | 100,000 | -100,000 | Professor | No |
Joan | 100,000 | 350,000 | Finance | ? |
What is Classification?
Core components of a classification problem:
Target variable you want to predict
Set of historical data where target label is known
A model is a mathematical object that takes unlabeled data and assigns it a label.
Supervised Machine Learning
Goal: Assign categories or labels to data points based on patterns in historical data.
Example Application:
Categorizing loan applicants (Paid Back Loan) into "Yes" or "No" labels.
New data where target variable is unknown
What Is a Machine Learning Model?
What is a model? A model is a mathematical function that learns patterns from training data and uses those patterns to make predictions on new, unseen data.
f(x) = {
Yes, if wealth > $100,000
No, otherwise
}
Here, x represents an applicant's features, and f(x) predicts whether the loan will be repaid.
Let’s Talk About Machine Learning
“A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.”
— Tom Mitchell, Carnegie Mellon University, 1998
Handwriting Recognition Example
T
Task (T)
Recognize Handwriting
P
Performance Measure (P)
How accurately the program can recognize the handwritten characters or words.
E
Training Experience (E)
Data the program learns from (e.g. database of handwritten digits).
Traditional Programming vs Machine Learning
Traditional Programming
Machine Learning
Traditionally, software engineering combined human created rules with data to create answers to a problem.
ML enables systems to learn from data, discover underlying rules of a problem, and improve their performance over time without explicit programming.
VS
Important Terminology(s) in ML
WORKFLOW & PIPELINE
ML Process
01
Data Collection
Gather raw dataset
02
Data Prep
Clean & split data
03
Training
Fitting stage
04
Evaluation
Test on unseen data
05
Tuning
Adjust hyperparameters
1. Process Overview
2. Pipeline & Data Flow Architecture
Reinforcement Learning
Reinforcement Learning: An agent learns by interacting with an environment, taking actions, and receiving feedback in the form of rewards or penalties, improving its behavior to maximize long-term reward.
RL Loop Architecture
Environment
External System
Agent
Decision Maker
Action
State (Sₜ₊₁)
Reward / Penalty
Real-World Scenario
Feedback Mechanism: Occasional positive and negative feedback is used to reinforce desirable behaviors over time through trial and error.
Our First Algorithm: KNN
A simple algorithm in that can make predictions about an new example based on the labels of other examples "near" it.
KNN - K Nearest Neighbour
KNN (K-Nearest Neighbors) is a supervised machine learning algorithm used for classification and regression.
An instance-based learning method that stores training data and predicts new values based on the K nearest neighbors — core principle: Similar data points tend to have similar outcomes.
KNN is a lazy learning algorithm: it stores training examples rather than learning an explicit predictive formula
K in KNN (Hyperparameter)
What is K? The number of nearest data points used to vote on a prediction.
Feature scaling is important because KNN depends on distances.
Key ML Topics: Hyperparameter vs. Parameter
Hyperparameters
Set Before Training
Configurable settings chosen before training that control how the learning algorithm works.
Example:
In K-Nearest Neighbors, K (number of neighbors) is a hyperparameter.
Parameters
Learned During Training
Values that the model learns automatically from training data during training.
Example:
In linear regression, the weights (coefficients) are parameters learned from data.
Back to Our Previous Example: Let's Visualize the Data!
Plot the datapoint:
Loan not paid
Loan paid
Can we predict whether this new customer will repay the loan using nearby customers?
Wealth
Income
?
?: New customer (unknown outcome)
Let's Dumb It Down Even Further: K=1 (Nearest Neighbor)
Loan not paid
Loan paid
K = 1
Classification Rule:
Predict the class of the single nearest neighbor for the new data point.
The neighbor's class wins the vote directly!
How to improve accuracy? Let’s look at more than one neighbor!
?
Wealth
Income
Let's Dumb It Down Even Further: K = More than 1 neighbour
Loan not paid
Loan paid
For Classification:
The new point is assigned to the most common class among the K neighbors (Majority Voting).
For Regression:
Average the values of the 3 nearest neighbors.
Key Takeaway: Majority voting decides classification, while numerical averaging predicts regression outcomes.
?
Wealth
Income
Think About
Wealth
Income
Loan not paid
Loan paid
What about this?
Do you want to classify as “blue” or “red”?
?
K-Nearest Neighbors (KNN) Implementation
KNN predicts outcomes based on the similarity (distance) between data points.
01
Store Training Data
Store the complete training dataset in memory.
02
Find K Nearest Neighbors
Calculate distance to find closest points to a new instance.
03
Predict Using Neighbors
Key Takeaway
Similar data points tend to have similar outcomes.
Visualization: Feature Space & Neighbor Clusters
KNN Algorithm: Step by Step
01
1. Choose K
Select the number of neighbors to consider.
02
2. Calculate Distances
Measure distance from new point to training points.
03
3. Find Neighbors
Select the K closest points in dataset.
04
4. Make Prediction
Components of KNN Classifier:
• K Parameter:
Hyperparameter selected before prediction.
• Distance Metric:
Determines how closeness is measured (e.g., Euclidean distance).
KNN Algorithm Pseudocode
Variation of KNN: Weighted KNN
Same neighbors. Different influence on the prediction.
STANDARD KNN
?
Each neighbor gets 1 vote
Equal voting weight for all k-neighbors
Classification: Majority vote (mode)
Regression: Predicts simple average (mean) of values
WEIGHTED KNN
?
closest neighbor
Closer neighbors get higher weight
Influence on prediction decreases with distance
Classification: Weighted vote
Regression: Predicts weighted average of values
KEY IDEA Standard KNN counts votes equally; Weighted KNN gives closer neighbors more influence (votes scaled by weights; closer neighbors dominate).
Why Use Weighted KNN?
With K = 3, the same three neighbors can lead to different predictions.
New point (?) and its 3 nearest neighbors
● Red = No repayment ● Green = Repaid
?
STANDARD KNN
2 Red votes vs. 1 Green vote
Prediction: RED
WEIGHTED KNN
Green is much closer, so its vote counts more.
Prediction: GREEN
Question? Why can the prediction change even though K stays at 3?
Weighted KNN Equation
Mathematical breakdown and component logic of distance-weighted predictions
CORE LOGIC
Weights are inversely proportional to distance — closer neighbors exert a stronger influence, while farther neighbors have less impact on predicting point p.
MATHEMATICAL FORMULATION
y
Predicted Label / Value
Predicted label or value for a new data point p.
1 / dist(k, p)
Weight Factor
Inversely proportional to distance from point p.
k_label
Neighbor Class / Value
Label (or value) of the k-th nearest neighbor.
Let's Predict Using Weighted KNN Classification (K = 3)
Evaluating distance-weighted votes to determine final class prediction
CATEGORY ENCODING
-1 = Loan Not Paid
+1 = Loan Paid
We use numeric values (-1 and +1) to compute mathematical weighted votes directly from distance measurements.
FEATURE SPACE (INCOME VS DISTANCE)
Income
Prediction rule: If y > 0, predict Loan Paid (+1). If y < 0, predict Loan Not Paid (−1).
?
Hold on--What do we even mean by distance?
Distance is a crucial concept in both KNN and Weighted KNN.
PROXIMITY MEASURE
It measures the similarity or proximity between data points.
FEATURE SPACE
The numerical measure of how far apart two data points are in the feature space.
VISUAL REPRESENTATION
Why Distance Matters?
Many Supervised and Unsupervised machine learning models (such as K-Nearest Neighbor and K-Means) depend upon the distance between data points to predict outcomes.
EXAMPLE APPLICATION: WEIGHTED KNN
Distance-Based Weighting
In Weighted KNN, the distance between a target data point (point p) and its K nearest neighbors directly determines its weighting.
Closer Neighbors
Higher Influence
Distant Neighbors
Less Impact
Different kind of distance functions
The choice of distance metric depends on the nature of the data and the problem at hand.
COMMON DISTANCE METRICS
Euclidean Distance (L2)
MOST COMMON METRIC
Represents the shortest (straight-line or geometric) distance between two points.
Best Use Case
Continuous numeric data with few dimensions.
Magnitude Sensitivity
Size of differences matters — larger differences have greater impact.
Key Considerations
Sensitive to outliers & high dimensions. Requires data normalization/scaling.
MULTIDIMENSIONAL GEOMETRY
Dimensional Breakdown
Considers differences independently along each dimension.
Manhattan Distance (L1)
TAXICAB / CITY BLOCK METRIC
Measures distance between two points on a grid via horizontal and vertical paths.
Key Property
No diagonal movement — strictly mimics navigating city block streets.
Computationally Easy & Fast
Very easy to compute — requires only simple addition and absolute values, avoiding complex square roots.
High-Dimensional Advantage
Reduces influence of irrelevant dimensions by focusing on absolute differences.
Sum of Absolute Differences
MANHATTAN VS. EUCLIDEAN GEOMETRY
City Grid Navigation
Distance calculated as absolute steps along axis grid (4 + 7 = 11).
Hamming Distance
Count how many positions differ in equal-length sequences.
BITWISE STRING COMPARISON
Measures differences between two equal-length strings.
Counts mismatches: Compares corresponding positions directly.
Data Focus: Binary strings, boolean vectors, and categorical features.
In KNN: Measures how many categorical feature values differ between two observations.
Length Constraint: Both sequences MUST have the exact same length.
Compare Binary Feature Vectors
A
1
0
1
1
0
B
1
1
0
1
0
Positions 2 and 3 differ → distance = 2
d = number of mismatched positions
Key idea: Count mismatches — do not subtract the numeric values.
Cosine Similarity (Vector Angle)
ORIENTATION & VECTOR METRIC
WHEN TO USE
Ideal for Text Data
Measures the angle between vectors (e.g., TF-IDF), ignoring overall magnitude.
Works Well for Sparse Data
Highly efficient when most feature values are zero in high-dimensional spaces.
Direction Over Magnitude
Focuses strictly on vector orientation rather than length (e.g., document similarity).
MATHEMATICAL FORMULA
EXAMPLE USE CASES
• Document Similarity: Comparing news articles, essays, or reviews.
• Recommendation Systems: Analyzing user-item interaction vectors.
• Text Clustering: Grouping similar tweets or topic representations.
Cosine Similarity: Direction vs. Magnitude
Magnitude = the length (size) of a vector.
VECTOR COMPARISON
A = (1, 1)
B = (2, 2)
Same direction • Different lengths
What changes?
Vector B is twice as long as A.
What stays the same?
Their direction (angle).
Cosine similarity = 1
KEY IDEA Cosine similarity compares direction, not vector length.
Cosine Similarity (Worked Example)
VECTOR ANGLE METRIC
GEOMETRIC & NUMERICAL CALCULATION
Result Interpretation: Cosine angle θ gives similarity = 0.95, indicating document 1 and document 2 are highly similar in direction.
RANGE & VALUES
Scale: -1 to +1
+1.0: Identical or highly similar direction
0.0: Orthogonal / no correlation
-1.0: Completely dissimilar / opposite
KEY TAKEAWAYS
• Ignores Magnitude
Focuses purely on vector angle, ignoring differences in document length.
• Text Analysis Standard
Ideal for word counts & TF-IDF vectors across varying text sizes.
Summary: Choice of Distance Metric
Key Rule: The optimal metric depends on problem structure, data type, and dimensionality.
DISTANCE METRIC SUMMARY
L1 Norm
Manhattan
Best For:
High-dimensional numerical data.
Key Feature:
Robust to outliers.
L2 Norm
Euclidean
Best For:
Low-dimensional numerical data.
Key Feature:
Magnitude matters.
Bitwise / String
Hamming
Best For:
Categorical and binary data.
Key Feature:
Counts exact mismatches.
Angular Metric
Cosine
Best For:
Text and sparse high-D data.
Key Feature:
Direction over magnitude.
Python Implementation
How to Choose K in KNN (Hyperparameter Tuning)
OPTIMIZATION METHOD
CORE STRATEGY
Try multiple Ks and graph the error rate, pick the lowest!
THE ELBOW METHOD
Finding Optimal Bias-Variance Balance
This approach is known as the "elbow method" and can be an effective way to identify an appropriate K value for your specific problem.
Next: Decision Boundary
DEFINITION
Understanding Class Regions
THOUGHT EXPERIMENT
What happens if we place a new data point on either side of the dashed line?
FEATURE SPACE SEPARATION
Key Idea: The decision boundary is where the model's predicted class changes.
Decision Boundaries: Simple vs. Complex
Feature Space Separation
MODEL GENERALIZATION
Comparing Boundary Types
1. Squiggly Line
Overfit
2. Straight Line
High Bias
3. Curve
Good Generalization
A decision boundary separates regions where the model predicts different classes.
Decision Boundary of a Classifier
Purpose & Types
Purpose: Classifies new data points based on features.
Types:
Why is it useful?
KNNs: Identifies class for any point in space.
Boundary Condition of KNN
K = 1 (Overfitting Case)
K = 1: Considers only the closest neighbor, ignoring broader patterns.
Decision Boundary: Jagged and highly sensitive to individual points.
Behavior: Prone to overfitting and poor generalization.
K = N (Underfitting Case)
K = N: Considers all training points as neighbors.
Decision Boundary: Overly simple, with no meaningful separation.
Behavior: Underfits by ignoring local patterns.
Prediction: Always predicts majority class or overall mean.
K-Nearest Neighbors in Python Code Sample
Scikit-Learn's 3-Step Machine Learning Workflow
1 STEP ONE Model Specification
2 STEP TWO Model Fitting
3 STEP THREE Model Prediction
knn_workflow.py
# Step 1: First Import necessary modules
from sklearn.neighbors import KNeighborsClassifier
# Step 2: Then you have load data, create feature and target/label
# Step 3: Initialize the model
model = KNeighborsClassifier(n_neighbors = 3)
# Step 4: Train the model using training sets
model.fit(X_train, y_train)
# Step 5: Make predictions on the test set
prediction = model.predict(X_test)
# Evaluation: Compute and print model's accuracy score
score = accuracy_score(y_test, prediction)
print('Accuracy score of the model: ' + str(score))
Pros and Cons of KNN
Key strengths and limitations of the K-Nearest Neighbors algorithm
PROS (Strengths) 5 ADVANTAGES
01
Simple & Intuitive
Easy to understand and straightforward to implement.
02
No Training Phase (Lazy Learning)
No explicit training required—simply stores dataset.
03
Adapts to Complex Data
Naturally models complex, non-linear relationships.
04
Highly Versatile
Works effectively for both classification and regression.
05
No Distribution Assumptions
Non-parametric; makes zero assumptions about data layout.
CONS (Limitations) 5 LIMITATIONS
01
Computationally Expensive
Requires calculating distances to all points per prediction.
02
Memory Intensive
Must store entire dataset, becoming inefficient at scale.
03
Sensitive to Irrelevant Features
Performance degrades with noisy or unscaled features.
04
Curse of Dimensionality
Struggles significantly in high-dimensional feature spaces.
05
Hyperparameter Tuning
Requires careful selection of K value and distance metric.
Summary
Core concepts of Supervised Learning and KNN
Supervised Learning
The model learns from labeled training data (e.g., "Paid back loan" or "Did not pay back loan").
Classification
We categorize data into groups, deciding if someone falls into "Pay back" or "Not".
Binary Classification
Only two categories exist (e.g., Pay back or not).
Instance-Based Model (KNN)
Requires all training data to be stored to work. Makes decisions based on similar examples from the training data.
Later: We will be learning about the following models:
Core machine learning algorithms and foundational theoretical concepts
Decision trees 01
Random forests 02
Neural Networks 03
Naive Bayes 04
Support Vector Machines 05
FOUNDATIONAL THEOREM
No Free Lunch theorem:
“ There is no single algorithm that will work well for all tasks.”
Additional Reading Slides (not for exam)
Spherical KNN (Radius-Based KNN)
A variation of KNN that selects neighbors within a fixed distance radius (r) rather than a fixed count (K)
How It Works
1. Set Radius (r): Draw a fixed radius circle or sphere around the new point.
2. Find Neighbors: Collect all data points inside that radius.
3. Vote: Enclosed neighbors vote to decide the class.
4. Dynamic Count: Neighbor count changes based on local point density.
5. Limitation: Requires a fallback if no points fall within radius r.
X₁
X₂
r
Class A
Class B
New Point
Radius (r)
Radius-Based Neighbor Selection
Nr(x) = { xi | d(x, xi) ≤ r }
x : new data point | xi : training data point
d(x, xi) : Euclidean distance metric
r : predefined fixed radius parameter
Example Scenario
If r = 3.0, every training sample residing within 3.0 distance units from the query point is selected to participate in majority voting.
Key Difference from Standard KNN
Traditional KNN: selects a fixed count (K) of nearest neighbors.
Radius-Based KNN: Selects all points within a fixed distance (r).
Key Takeaways