Machine Learning 101 Warm-up

Acknowledgement: This post is based mainly on TA Duong Dinh Thang’s presentation and slides and partly on on TA, STA, and peers’ responses from the course AIO2025 offered by AI VIETNAM.

Relevance: The audience of this lecture were those who have read Data Visualization and Analysis, had some coding experience, and known a bit of AI knowledge.

In today’s post, we’ll explore KNN and Supervised Learning. We’ll also discuss some applications in AI via a case study.

Machine Learning

Terminology

Machine Learning (ML) is a subfield of Artificial Intelligent (AI) focused on the study of algorithms that can imitate how humans learn and ultilize data to generalize or predict unseen information, and thus gradually improving their performance on specific tasks without explicit programming.

A familiar example is the classification problems we discussed in Math for AI series. Specifically, given a dataset with features and a class, we need to foresee a value of one column based on others. If a dataset is small enough, it may be possible to use multiple conditions to figure out. Nevertheless, it’s hardly possible for a large dataset with thousands and thousands lines of data. This is where ML comes into play.

In particular, we feed an ML model the dataset whose features and class values are complete and accurate. Using the given condition, the model takes note and learns to find out which function can match the input and output together. Behind the scenes, this model repeatedly tries out every possible features-class pair. Once it’s done, we need to check how well the model is doing.

The whole process includes two primary steps:

• training for learning data, requiring training data which is the mentioned dataset.
• testing for checking with non-dataset input, requiring test data.

The ML model after learning the entire dataset is called a trained ML model. With the testing phase, we can conclude how well a trained ML model works. This is known as machine learning generalization which refers to a train ML model’s ability to perform well on unseen data of similar types. For example, a model classifying dogs and cats should not be pedantic and distinguish African dogs and Asian dogs; they are just dogs anyway. We’ll talk more about this in the future.

Supervised Learning (SP)

Since this example of dataset has a class/label, we call it a labeled dataset. We call the type of machine learning where we use a labeled dataset to train a ML model a supervised learning (SL). This name comes from the idea that the data is set with specific class values.

A practical example is image classification for dogs and cats. The training data includes images of dogs and cats as a feature and a label column indicates which one is a cat and which one is a dog. The goal is for computers to answer if a test input image is a dog or a cat. Of course, if an input is a picture of a human being, the model will still result in a dog or a cat.

SL can solve various problems which can be categorized into two types: classification problems and regression problems.

Classification Problems
The class values in classification problems are discrete (categorical). Some examples can be dog-cat classification (0 and 1) and spam detection.

In general, for classification problems, we want to find a border line that best divide a dataset into separate regions/classes.

DEMONSTRATION

Regression Problems
The output predicted in regression problems are continuous—any numerical value falling within a certain range. Some examples can be predicting salaries and forecasting stock prices.

For regression problems, we generally want to find a line that best fits the data distribution.

DEMONSTRATION

$k$-Nearest Neighbors (KNN)

The core idea of KNN comes straight from the saying, “Show me your friends and I’ll tell you who you are.” That is, if you know someone’s circle, you’ll know what that person is like.

Formally, KNN is a non-parametric and SL algorithm which is used to make predictions based on proximity. In particular, the predicted class depends on the majority label / average value of its k-closest neighbors in the same feature space. This algorithm can be used for both classification problems and regression problems.

Some common metrics used to determine k-closet neighbors are listed in the table below. In the following formulae, $n$ is the number of features and $x_i$ and $y_i$ are coordinates of training and test points.

DEMONSTRATION for distances

Procedure

We should always preprocess the data first. Then we can apply it to a ML model in the following steps.

1. Initialize the value of $k$.
2. Compute the distance between test data and every training data (every row of the training dataset).
3. Sort the calculated distances in ascending order.
4. Get top $k$ elements from the sorted array.
5. Get the most frequent class of these elements.
6. Return the predicted class.

flowchart LR
    A((<strong>Initialize k</strong>)) ---> B((<strong>Compute distances</strong></br> between test data</br> and training data)) ---> C((<strong>Sort distances</strong></br> in ascending order)) ---> D((<strong>Get top k elements</strong></br> from the sorted array)) ---> E((<strong>Get the most frequent class</strong></br> of these elements)) ---> F((<strong>Return predicted class</strong>))

When working on step 3, keep in mind that we want to know the training points rather than just the distances. That is, we need to obtain the indices of training data.

The steps from 1 through 4 are quite straightforward while performing step 5 takes a bit more effort. This happens because of their class type differences. For classification problems, class values are discrete wheareas they are continuous for regression problems. That is, we need to approach two tasks via different strategies:

• Classification problems: discrete class set allows us to vote for the majority label from the top $k$.

  \[\hat{y} = max \\\{y_x | x \in NB \\\}\]

• Regression problems: continuous class set requires us to average the $k$-neighbors’ values.

  \[\hat{y} = \frac{1}{k} \sum_{x \in NB} y_x\]

Note:

• Results are potentially different depending on the initialization of $k$. In Machine Learning, parameters like k are referred to as hyperparameters—predictions change as hyperparameters change.
• If the number of labels equal each other, there are many ways to go about it. We can either increase $k$ or assign the label of the closet one.

Practice Exercises

Exercise 1: Use the following table and step-by-step procedure with Euclidean distance to check which label the test point $x\_test = 2.4$ should be when

1. $k = 1$
2. $k = 2$
3. $k = 3$
4. $k = 4$
5. $k = 5$

Exercise 2: Do the same as exercise 1 for $x\_test = (2.4, 0.8)$ and $x\_test = (2.6, 0.8)$ when

1. $k = 1$
2. $k = 3$
3. $k = 5$

Exercise 3: Write code for both exercises above.
Exercise 4: Use the following table and step-by-step procedure with Euclidean distance to predict the salary for $experience = 5.3$ when

1. $k = 2$
2. $k = 3$
3. $k = 4$

Exercise 5: Write code for exercise 4 above.

Scaling

As we’ve known so far, features and distances are the main contributors of KNN algorithm. In practice, if there is a problem with feature values, the distances will cause issues.

For example, if values of feature A are way greater than that of other features, the feature A can influence and dominate the results while it may not reflect its actual meaning/importance. This results in the incorrect learning of ML models—learning based on values solely rather than relevant meaning. It happens when we apply the procedure without any extra consideration.

To resolve this issue, we can build an algorithm that explicitly tells the model to focus on more significant features. Nevertheless, we do not want to make such suggestions every single time we work on a problem, which is quite a waste of resources. This is where scaling comes in handy.

Scaling is a crucial step in data preprocessing that normalizes and standardizes feature values (both training and test points) to fit in a certain domain. This helps the KNN algorithm focus on feature importance, ensuring feature values’ fair contributions to distance-based or gradiant-sensitive algorithm.

Choosing a domain depends on which scaling algorithm we use. Common domains can be $(0, 1)$ and $(-1, 1)$. One of the formula for normalization is the following

where $\bar{x}$ is the mean and $\sigma$ is the standard deviation of training data.

In practice, we use packages for scaling. One that is based on the above formula is

# import a package
from sklearn.preprocessing import StandardScaler

# call the function
scaler = StandardScaler()

# scale training and test values
x_data_scaled = scaler.fit_transform(x_data)
x_test_scaled = scaler.transform(x_test)

KNN for Classification Tasks

Text Classification with KNN

Problem statement: Solve the task of text classification using KNN with the given procedure.
Breakdown:

• Input is a corpus of texts or strings and a random string that is not in the corpus.
• Output is a corpus string that is potentially closet to the random string.

Idea: We follow the procedure of the KNN algorithm.

1. To build a model, we follow a pipeline which is a complete model building process.
1. Obtain message input with its label values.
2. Preprocessing: convert message to numeric values like vectors.
3. Build vocabulary.
4. Create features.
5. Pass to a KNN model.
6. Obtain results.
2. We can handle preprocessing to build vocabulary via two approaches: Bag-of-Words (BoW) and Term Frequency-Inverse Document Frequency (TF-IDF).

Note: Essentially, the KNN algorithm stays similar for all types of data: image, sound, tabular, and time series data. But we need to figure out how to work with given data to induce real feature values.

BoW is simpler and more basic approach to text representation than TF-IDF. BoW only considers word occurences while TF-IDF provides more informative representation of text—taking into account both word importance and context within the entire dataset. TF-IDF is generally preferred. We’ll delve deeper into the two techniques right away.

Bag-of-Words (BoW)

Problem statement: We have the following corpus.

Doc	Label
you reap what you sow	1
beggars can't be choosers	1
like bees to honey	1
bite the hands that feed you	0
a taste of your own medicine	0
burn your bridges behind you	0

Idea: BoW is to investigate distances between two sentences based on word occurences.

1. Tokenization splits text into a list of smaller parts or separate words.
2. Initialize an empty vocabulary. Add new words from tokenized corpus into the vocabulary.
Vocabulary =
3. Take a random string: "you can't pick and choose".
4. Convert the string to a numeric value by creating a BoW from the string and assigning a number to each of them. Two common ways are
• Binary BoW: Words in the string are assigned $1$ and others are $0$.
• (Complete) BoW: Each value is the number of its' word occurrency.
We use the (complete) BoW for this problem.
• From here, we build a matrix where each row is a word in the constructed vocabulary, each column is a sentence from the corpus, and each cell of a column is the BoW value of the corresponding sentence. Corpus sentences now become training vectors/points.
• With the random string, we can build a test vector/point.
DEMONSTRATION for matrix

Term Frequency-Inverse Document Frequency (TF-IDF)

Problem statement: We use the same corpus as in BoW. We can also use this approach to do spam email detection.
Breakdown:

• A document is a sentence/ an email.
• The corpus is a collection of documents.

Idea: TF-IDF is to compute the importance level of a word or phrase relative to its parent sentence/email and the entire corpus. Thus, TF-IDF helps identify words that are significant in a specific document but maybe rare across all the documents.

1. We build the same matrix for the entire corpus as in Bag-of-Words technique.
2. We build three other matrices:
• TF matrix: Each cell is the corresponding TF value of the row word and the column document.
• IDF matrix: Each cell is the corresponding IDF value of the row word and the column document.
• TF-IDF matrix: Each cell is the corresponding TF-IDF value of the row word and the column document.
• Normalized TF-IDF matrix: Each cell is the corresponding normalized TF-IDF value of the row word and the column document.
3. We build vectors for test documents.
4. Term Frequency (TF) measures how often a term/word appears in a document, that is how important a word is in a document.
$$\begin{align*} TF_{(t,d)} &= count(t,d) \\ &= \frac{\text{Number of times word$_\textbf{i}$ appears in a document}}{\text{Total number of words in the document}} \end{align*}$$ or in practice, $$TF_{(t,d)} = \log{(count(t,d) + 1)}$$ However, a word with a high occurence may not actually be of large importance, for example "the", "and", "are", and "is". We need additional step to handle this situation.
5. Inverse Document Frequency (IDF) measures how important a word is across the entire corpus.
$$\begin{align*} IDF_{t} &= \log \frac{\text{Total number of documents}}{\text{Number of documents containing word$_\textbf{i}$}} \\ &= \frac{N}{DF_t} \end{align*}$$ or in practice, $$\begin{align*} IDF_{t} &= \log \frac{\text{Total number of documents + 1}}{\text{Number of documents containing word$_\textbf{i}$ + 1}} + 1 \\ &= \frac{N + 1}{DF_t + 1} + 1 \end{align*}$$ Adding $1$ is to avoid $0$ as a result since it could kill of the importance of a word and avoid division by zero. This technique is called smoothing used in packages like scikit-learn.
6. TF-IDF computes the importance of a word in an email relative to the entire collection.
$$TF-IDF_{(t,d)} = TF_{(t,d)} \times IDF_{t}$$ This multiplication helps compensate for the disproportionate influence of frequently occuring but uninformative words and ensure the more meaningful features contribute appropriately to the distance calculations.
This next step is not required. The TF-IDF matrix contains many zeros and possiblly much greater values, so we need to normalize them like we perform scaling in KNN. This helps avoid bias from document length.
7. Normalized TF-IDF takes the unit vector of each TF-IDF vector. L2 norm is also known as Euclidean norm.
$$L2\_norm(TF-IDF) = \frac{TF-IDF}{\left \| TF-IDF \right \|_2} = \frac{\langle x_1, \cdots, x_n}{\left( \sum_i=1^n x_i^2\right)^\frac{1}{2}}$$ DEMONSTRATION for matrix

Case Study: Code Implementation

We primarily use the scikit-learn library for ML problems.

Problem statement: Build a system to predict whether a tumor is maglinant or benign based on real-valued information using KNN.

Set Up

# for a tabular dataset
import pandas as pd

# this dataset is available in the package, so we just need to import it
from sklearn.datasets import load_breast_cancer

# 
from sklearn.model_selection import train_test_split

# for scaling data (mentioned above)
from sklearn.preprocessing import StandardScaler

# KNN algorithm in the package
from sklearn.neighbors import KNeighborsClassifier

# for classification tasks and assessing how accurate our model is
from sklearn.metrics import accuracy_score, classification_report

The pipeline for a ML problem follows the basic procedure below. In practice, there can more steps to work through.

1. Data input
2. Data preprocessing
3. Data spliting:
   • Training data
   • Test data
4. Data training
5. Model evaluation

Data Input

# load and read the dataset
cancer = load_breast_cancer()

# convert the feature columns to a DataFrame
X = pd.DataFrame(cancer.data, columns=cancer.feature_names)

# convert the label column to a Series
y = pd.Series(cancer.target, name='target')

DEMONSTRATION FOR FIRST FIVE ROWS

Since the target contains non-numerical values: benign and malignant, we need to assign numeric values to them: $1$ for benign and $0$ for malignant.

Data Spliting
We mentioned splitting a dataset (label included) into two sets: training and test data. But in practice, a dataset is usally divided into three following sets:

• Training data
• Test data
• Evaluation data: we use this set to evaluate how accurate the ML model is—checking how close its predicted label values is to its actual label values, then check the same for test data.

val_size = 0.2
test_size = 0.125
random_state = 0
is_shuffle = True

# split training and test data
X_train, X_test, y_train, y_test = train_test_split(
    X, y, 
    test_size=test_size, 
    shuffle=is_shuffle,
    random_state=random_state)

# split training and evaluation data
X_train, X_val, y_train, y_val = train_test_split(
    X, y, 
    test_size=val_size, 
    shuffle=is_shuffle,
    random_state=random_state)

Data Training

# scale data
# call scaling function
scaler = StandardScaler()

# scale both training and test data
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# initialize k
k = 5

# call KNN algorithm
knn_classifier = KNeighborsClassifier(n_neighbors=k)

# train data
knn_classifier.fit(X_train_scaled, y_train)

DEMONSTRATION IN SLIDE, ONLY TAKE 2 FOR VISUALIZATION, SHOULD BE 30 BUT THERE IS NO WAY TO VISUALIZE 30 DIMENSIONS

Model Evaluation
This step plays a very important role during the model development. Depending on the result, we can tune parameters, try different metrics, process the data differently or other methods. Once we get high-enough accuracy, we can start testing on test data.

You can think of evaluation data as a practice exam while test data is a real exam.

# make evaluation on evaluation data

# test on evaluation data
y_pred = model.predict(X_val_scaled)

# check the model's accuracy on evaluation data
accuracy = accuracy_score(y_val, y_pred)

# obtain precision, recall, and f1-score values
report = classification_report(y_val, y_pred)

# make evaluation on test data

# test on test data
y_pred = model.predict(X_test_scaled)

# check the model's accuracy on test data
accuracy = accuracy_score(y_test, y_pred)

# obtain precision, recall, and f1-score values
report = classification_report(y_test, y_pred)

We can write our own code for checking the accuracy above using the formula

The same goes for precision, recall, and F1-Score values.

KNN with K-D Tree

The original KNN algorithm has its own drawback, so methods like K-D Tree are introduced to improve the algorithm’s performance.

FAQ

Here are some good questions asked during class. The answers to these questions came from either some admin, TA, STA, or members of AIO2025.