From mathematical foundations to edge implementation
👨🏽💻 Github: thommaskevin/TinyML (github.com)
👷🏾 Linkedin: Thommas Kevin | LinkedIn
📽 Youtube: Thommas Kevin — YouTube
👨🏻🏫 Analysis group: Conecta.ai (ufrn.br)
SUMMARY
1 — Introduction to Ok-Nearest Neighbors (KNN)
1.1 —Fundamental Idea
1.2 — Distance Metrics Utilized in KNN
1.3 —KNN Algorithm for Classification
2 — Mathematical Formulation of Classification
2.1 —Weights
2.2— Algorithms
3 —TinyML Implementation
Ok-Nearest Neighbors (KNN) is among the easiest and simplest algorithms utilized in machine studying. It’s a supervised studying algorithm that can be utilized for each classification and regression. The core thought behind KNN is that comparable information factors are shut to one another within the function area.
1.1 —Fundamental Idea
In KNN, the “proximity” between information factors is measured utilizing a distance metric, with the Euclidean distance being the commonest. To find out the category or worth of a brand new statement, the KNN algorithm searches for the kkokay nearest neighbors within the coaching set and performs a majority vote or averaging to find out the consequence.
1.2 — Distance Metrics Utilized in KNN
There are numerous methods to measure the space between two factors in a function area. Apart from the Euclidean distance, different generally used distance metrics embody Manhattan distance, Minkowski distance, and Mahalanobis distance.
1.2.1 —Euclidean Distance
The Euclidean distance between two factors x = (x_1, x_2, …, x_n) and y=(y1,y2,…,yn) in an n-dimensional area is given by:
1.2.2 — Manhattan Distance
The Manhattan distance (or L1 distance) between two factors x and y is the sum of absolutely the variations of their coordinates:
1.2.3 — Minkowski Distance
The Minkowski distance is a generalization of the Euclidean and Manhattan distances. For a parameter p≥1, the Minkowski distance between two factors xand y is:
For p=2, we get the Euclidean distance, and for p=, we get the Manhattan distance.
1.2.4— Mahalanobis Distance
The Mahalanobis distance takes into consideration the correlations between variables and is helpful in function areas the place the size are scaled otherwise. The Mahalanobis distance between two factors x and y is given by:
the place S is the covariance matrix of the dataset.
1.3 — KNN Algorithm for Classification
The KNN algorithm may be summarized within the following steps:
- Selection of okay: Outline the variety of neighbors okay.
- Distance Calculation: Calculate the space between the brand new statement and all observations within the coaching set utilizing an applicable distance metric.
- Choice of Neighbors: Choose the okay information factors within the coaching set which can be closest to the brand new statement.
- Classification: For classification issues, decide the bulk class among the many okay neighbors.
Given a coaching set D with m observations, the place every statement is a pair (xi,yi), with xi being the function vector and yi the category label. For a brand new statement x, the KNN algorithm finds the okay nearest neighbors {(xi1,yi1),…,(xik,yik). The expected class y^ is set by the next majority vote system:
the place I is the indicator perform, C is the set of doable lessons, and ccc is a selected class.
2.1 — Weights
Weights may be assigned to the neighbors to affect their affect on the classification resolution. Frequent weighting schemes embody:
- Uniform Weights: All neighbors contribute equally to the choice.
- Distance Weights: Neighbors nearer to the question level have a better affect. This may be notably helpful when the closest neighbors are extra related than the farther ones.
2.2 — Algorithms
KNN can use completely different algorithms to compute the closest neighbors effectively:
2.2.1— Brute Drive
Within the brute drive method, the KNN algorithm calculates the space between the question level and each level within the coaching set. This method may be computationally costly, particularly for big datasets.
Let X={x1,x2,…,xn} be the coaching set with n factors, and let qqq be the question level. The algorithm computes the space d(q,xi) for every xi ∈ X.
For instance, utilizing the Euclidean distance:
the place m is the variety of dimensions (options).
The computational complexity of this method is O(nm), the place nnn is the variety of factors and m is the variety of dimensions.
2.2.2— KD-Tree
A KD-Tree (k-dimensional tree) is a binary search tree used to arrange factors in a k-dimensional area. It’s environment friendly for low-dimensional information and accelerates the closest neighbor search by lowering the variety of distance calculations.
Building
- Choose Axis: At every degree of the tree, choose an axis (dimension) to separate the info.
- Median Break up: Select the median of the factors alongside the chosen axis to separate the info into two halves.
- Recursive Partitioning: Recursively apply the above steps to the 2 halves, creating left and proper subtrees.
Search
- Traverse Tree: Begin on the root and recursively traverse the tree, shifting left or proper based mostly on the comparability of the question level’s coordinate alongside the present axis.
- Backtracking: As soon as a leaf node is reached, backtrack and verify if there might be nearer factors within the different branches.
Mathematical Formulation
Let P={p1,p2,…,pn} be the set of factors, and let q be the question level. The KD-Tree partitions the area recursively:
- Node NNN: If N splits on the okay-th axis, then:
- Distance Calculation: In the course of the search, calculate the space to the present greatest candidate and evaluate with the doable nearest neighbors within the different branches.
The computational complexity for constructing a KD-Tree is O(nlogn), and for querying it’s O(logn) in the most effective case.
2.2.3 — Ball Tree
A Ball Tree is a tree information construction the place information factors are organized into hyperspheres (balls) as an alternative of hyperrectangles, making it extra environment friendly for high-dimensional information than a KD-Tree.
Building
- Break up Factors: Choose some extent as the middle and partition the info into two clusters based mostly on the space to the middle.
- Recursive Partitioning: Recursively apply the above step to every cluster, making a ball for every node.
Search
- Traverse Tree: Begin on the root and recursively traverse the tree, shifting into the ball that comprises the question level.
- Backtracking: As soon as a leaf node is reached, backtrack and verify if there might be nearer factors in different balls.
Mathematical Formulation
Let P={p1,p2,…,pn} be the set of factors, and let q be the question level. The Ball Tree partitions the area utilizing hyperspheres:
- Node N: Every node N represents a ball with heart c and radius r:
- Distance Calculation: In the course of the search, calculate the space to the present greatest candidate and evaluate with the doable nearest neighbors in different balls.
The computational complexity for constructing a Ball Tree is O(nlogn), and for querying it’s O(logn) in the most effective case.
With this instance you possibly can implement the machine studying algorithm in ESP32, Arduino, Arduino Portenta H7 with Imaginative and prescient Defend, STM, Raspberry and different completely different microcontrollers or IoT units.
3.0 — Set up the libraries listed within the necessities.txt file
!pip set up -r necessities.txt
3.1 — Importing libraries
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split,GridSearchCV
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import confusion_matrix,classification_report,roc_auc_score,roc_curve
from sklearn.pipeline import Pipeline
import warnings
warnings.filterwarnings('ignore')
3.2 — Load Dataset
Breast Most cancers Wisconsin (Diagnostic) Knowledge Set
hyperlink:https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29
df = pd.read_csv('./information/KNNAlgorithmDataset.csv')
df.head()
df.information()
df.describe()
3.3 —Clear Knowledge
df.describe()
df = df.drop(['id','Unnamed: 32'],axis=1)
df.head()
# Eradicating rows with lacking values
df.dropna(inplace=True)
df.columns
2.4 — Exploratory Knowledge Evaluation
sns.countplot(information=df,x='analysis',hue='analysis',palette='viridis')
plt.savefig('.figuresanalysis.png', dpi=300, bbox_inches='tight')
sns.pairplot(information=df,
x_vars=['radius_mean', 'texture_mean', 'perimeter_mean',
'area_mean', 'smoothness_mean'] ,
y_vars=['compactness_mean', 'concavity_mean',
'concave points_mean', 'symmetry_mean', 'fractal_dimension_mean'] ,
hue='analysis');
plt.savefig('.figurespairplot.png', dpi=300, bbox_inches='tight')
corr = df.corr()
# Adjusting the dimensions of the determine
plt.determine(figsize=(25,25))
# Your present code for producing the heatmap
heatmap = sns.heatmap(corr, xticklabels=corr.columns, yticklabels=corr.columns, cmap='coolwarm')
# Including values to the heatmap
for i in vary(len(corr.columns)):
for j in vary(len(corr.columns)):
plt.textual content(j + 0.5, i + 0.5, f"{corr.iloc[i, j]:.2f}", ha='heart', va='heart', coloration='black', fontsize=12)plt.xticks(fontsize=20, rotation=90)
plt.yticks(fontsize=20, rotation=0)
cbar = heatmap.collections[0].colorbar
cbar.ax.tick_params(labelsize=20)
plt.savefig('.figuresheatmap.png', dpi=300, bbox_inches='tight')
# Show the heatmap
plt.present()
df['diagnosis'] = df['diagnosis'].apply(lambda x : 0 if x=='B' else 1)
df['diagnosis'].distinctive()
# Prime 5 correlated variables with the analysis
abs(df.corr()['diagnosis']).sort_values().tail()
2.5 — Break up into coaching and take a look at information
X = df.drop('analysis',axis=1)
y = df['diagnosis']
# Break up the info into coaching and take a look at units
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
print('X_train: ', X_train.form)
print('X_test: ', X_test.form)
print('y_train: ', y_train.form)
print('y_test: ', y_test.form)
2.6 — Ok-Neighbors Classifier
2.6.1 — Create the mannequin
scaler = StandardScaler()
knn = KNeighborsClassifier()
pipl = Pipeline([('scaler',scaler),('knn',knn)])
k_values = np.arange(1,31)
param_grid = {'knn__n_neighbors':k_values}
final_model = GridSearchCV(estimator=pipl,param_grid=param_grid,cv=5,scoring='accuracy')
2.7 — Prepare the mannequin
final_model.match(X_train,y_train)
final_model.best_estimator_.get_params()
2.8 — Mannequin analysis
2.8.1— Consequence parameter tuning
df_result = pd.DataFrame(final_model.cv_results_)
df_result.head(5)
plt.determine(figsize=(12,4))
plt.plot(k_values,df_result['mean_test_score'],c='grey',ls='--')
plt.xlabel('k_values')
plt.ylabel('accuracy')
plt.scatter(k_values,df_result['mean_test_score'],c='pink',marker='o')
plt.savefig('.figuresresult_k_value.png', dpi=300, bbox_inches='tight')
plt.grid()
y_train_pred = final_model.predict(X_train)
y_test_pred = final_model.predict(X_test)
2.8.2 —Evaluating the mannequin with prepare information
sns.heatmap(confusion_matrix(y_train,y_train_pred),annot=True,cmap='viridis')
plt.savefig('.figuresconfusion_matrix_train.png', dpi=300, bbox_inches='tight')
print(classification_report(y_train,y_train_pred))
fpr , tpr , _ = roc_curve(y_train,final_model.predict_proba(X_train)[:,1])
plt.plot(fpr,tpr,c='pink')
plt.xlabel('FPR')
plt.ylabel('TPR')
plt.title('ROC Curve')
plt.plot([0,1],[0,1],ls='--',c='grey')
plt.savefig('.figuresROC_train.png', dpi=300, bbox_inches='tight')
# Space below curve
roc_auc_score(y_train,final_model.predict_proba(X_train)[:,1])
2.8.3 — Evaluating the mannequin with take a look at information
sns.heatmap(confusion_matrix(y_test,y_test_pred),annot=True,cmap='viridis')
plt.savefig('.figuresconfusion_matrix_test.png', dpi=300, bbox_inches='tight')
print(classification_report(y_test,y_test_pred))
fpr , tpr , _ = roc_curve(y_test,final_model.predict_proba(X_test)[:,1])
plt.plot(fpr,tpr,c='pink')
plt.xlabel('FPR')
plt.ylabel('TPR')
plt.title('ROC Curve')
plt.plot([0,1],[0,1],ls='--',c='grey')
plt.savefig('.figuresROC_test.png', dpi=300, bbox_inches='tight')
# Space below curve
roc_auc_score(y_test,final_model.predict_proba(X_test)[:,1])
2.9 — Acquiring the mannequin to be carried out within the microcontroller
def generate_knn_arduino_header(X_train, y_train, okay, dist_metric, p, algorithm, filename):
# Dictionary for distance metrics
dist_metric_dict = {
"EUCLIDEAN": 0,
"MANHATTAN": 1,
"CHEBYSHEV": 2,
"MINKOWSKI": 3
}# Dictionary for algorithms
algorithm_dict = {
"AUTO": 0,
"BALL_TREE": 1,
"KD_TREE": 2,
"BRUTE": 3
}
n_samples, n_features = X_train.form
# Arduino code header
arduino_code = f"""
#ifndef KNN_MODEL_H
#outline KNN_MODEL_H
#embody <math.h>
// Definitions of distance sorts
#outline EUCLIDEAN 0
#outline MANHATTAN 1
#outline CHEBYSHEV 2
#outline MINKOWSKI 3
// Definitions of algorithm sorts
#outline AUTO 0
#outline BALL_TREE 1
#outline KD_TREE 2
#outline BRUTE 3
// Coaching information
float X_train[{n_samples}][{n_features}] = {{
"""
# Inserting formatted X_train information
for i in vary(n_samples):
arduino_code += " {" + ", ".be a part of(map(str, X_train[i])) + "}"
if i < n_samples - 1:
arduino_code += ","
arduino_code += "n"
arduino_code += "};n"
# Inserting formatted y_train information
arduino_code += f"int y_train[{len(y_train)}] = {{ {', '.be a part of(map(str, y_train))} }};n"
# Distance features and KNN classifier class
arduino_code += f"""
// Perform to calculate Euclidean distance
float euclidean(float level[], float information[], int size) {{
float sum = 0;
for (int i = 0; i < size; i++) {{
sum += pow(level[i] - information[i], 2);
}}
return sqrt(sum);
}}
// Perform to calculate Manhattan distance
float manhattan(float level[], float information[], int size) {{
float sum = 0;
for (int i = 0; i < size; i++) {{
sum += abs(level[i] - information[i]);
}}
return sum;
}}
// Perform to calculate Chebyshev distance
float chebyshev(float level[], float information[], int size) {{
float max_diff = 0;
for (int i = 0; i < size; i++) {{
float diff = abs(level[i] - information[i]);
if (diff > max_diff) {{
max_diff = diff;
}}
}}
return max_diff;
}}
// Perform to calculate Minkowski distance
float minkowski(float level[], float information[], int size, float p) {{
float sum = 0;
for (int i = 0; i < size; i++) {{
sum += pow(abs(level[i] - information[i]), p);
}}
return pow(sum, 1.0 / p);
}}
// Perform to seek out the commonest worth in an array
int most_common(int lst[], int size) {{
int maxCount = 0;
int mostCommonValue = lst[0];
for (int i = 0; i < size; i++) {{
int rely = 0;
for (int j = 0; j < size; j++) {{
if (lst[j] == lst[i]) rely++;
}}
if (rely > maxCount) {{
maxCount = rely;
mostCommonValue = lst[i];
}}
}}
return mostCommonValue;
}}
class KNeighborsClassifier {{
public:
int okay;
float (*X_train)[{n_features}];
int* y_train;
int X_train_rows;
int X_train_cols;
int dist_metric;
float p;
int algorithm;
// Constructor
KNeighborsClassifier(int okay = {okay}, int dist_metric = {dist_metric_dict[dist_metric]}, float p = {p}, int algorithm = {algorithm_dict[algorithm]}) {{
this->okay = okay;
this->dist_metric = dist_metric;
this->p = p;
this->algorithm = algorithm;
}}
// Match methodology
void match(float X_train[][{n_features}], int y_train[], int rows, int cols) {{
this->X_train = X_train;
this->y_train = y_train;
this->X_train_rows = rows;
this->X_train_cols = cols;
}}
// Perform to calculate distance based mostly on chosen metric
float calculate_distance(float level[], float information[], int size) {{
change (dist_metric) {{
case EUCLIDEAN:
return euclidean(level, information, size);
case MANHATTAN:
return manhattan(level, information, size);
case CHEBYSHEV:
return chebyshev(level, information, size);
case MINKOWSKI:
return minkowski(level, information, size, p);
default:
return euclidean(level, information, size); // fallback to euclidean
}}
}}
// Prediction methodology
int* predict(float X_test[][{n_features}], int X_test_rows) {{
int* neighbors = new int[X_test_rows];
if (algorithm == BRUTE || algorithm == AUTO) {{
for (int i = 0; i < X_test_rows; i++) {{
float distances[this->X_train_rows];
for (int j = 0; j < this->X_train_rows; j++) {{
distances[j] = calculate_distance(X_test[i], this->X_train[j], this->X_train_cols);
}}
int y_sorted[this->X_train_rows];
for (int m = 0; m < this->X_train_rows; m++) y_sorted[m] = this->y_train[m];
for (int m = 0; m < this->X_train_rows - 1; m++) {{
for (int n = m + 1; n < this->X_train_rows; n++) {{
if (distances[m] > distances[n]) {{
float temp_dist = distances[m];
distances[m] = distances[n];
distances[n] = temp_dist;
int temp_y = y_sorted[m];
y_sorted[m] = y_sorted[n];
y_sorted[n] = temp_y;
}}
}}
}}
neighbors[i] = most_common(y_sorted, this->okay);
}}
}} else {{
Serial.println("Algorithm not supported on this implementation.");
for (int i = 0; i < X_test_rows; i++) {{
neighbors[i] = -1; // Error return
}}
}}
return neighbors;
}}
// Analysis methodology
float consider(float X_test[][{n_features}], int y_test[], int X_test_rows) {{
int* y_pred = predict(X_test, X_test_rows);
int right = 0;
for (int i = 0; i < X_test_rows; i++) {{
if (y_pred[i] == y_test[i]) right++;
}}
delete[] y_pred;
return (float)right / X_test_rows;
}}
}};
#endif // KNN_MODEL_H
"""
# Writing the code to the .h file
with open(filename, 'w') as f:
f.write(arduino_code)
print(f"File '{filename}' generated efficiently.")
2.10 — Saves the template in a .h file
p_value = float(final_model.best_estimator_.get_params()['knn__p'])
algorithm = final_model.best_estimator_.get_params()['knn__algorithm'].higher()
dist_metric = final_model.best_estimator_.get_params()['knn__metric'].higher()
X_train_cpp = X_train.values
y_train_cpp = y_train.values
n_features = 2
filename = ".KNNKNN.h"
generate_knn_arduino_header(X_train=X_train_cpp, y_train=y_train_cpp, okay=n_features, dist_metric=dist_metric, p = p_value, algorithm=algorithm, filename=filename)
2.11 —Deploy mannequin
2.11.1 — Full Arduino Sketch
// Embody the generated header file
#embody "KNN.h"KNeighborsClassifier knn;
float X_test[1][30] = {
{12.47, 18.6, 81.09, 481.9, 0.09965, 0.1058, 0.08005, 0.03821, 0.1925, 0.06373,
0.3961, 1.044, 2.497, 30.29, 0.006953, 0.01911, 0.02701, 0.01037, 0.01782,
0.003586, 14.97, 24.64, 96.05, 677.9, 0.1426, 0.2378, 0.2671, 0.1015, 0.3014,
0.0875}
};
float X_test_2[1][30] = {
{1.546e+01, 1.948e+01, 1.017e+02, 7.489e+02, 1.092e-01, 1.223e-01,
1.466e-01, 8.087e-02, 1.931e-01, 5.796e-02, 4.743e-01, 7.859e-01,
3.094e+00, 4.831e+01, 6.240e-03, 1.484e-02, 2.813e-02, 1.093e-02,
1.397e-02, 2.461e-03, 1.926e+01, 2.600e+01, 1.249e+02, 1.156e+03,
1.546e-01, 2.394e-01, 3.791e-01, 1.514e-01, 2.837e-01, 8.019e-02}
};
void setup() {
Serial.start(9600);
// Initializing the KNN mannequin
Serial.println("KNN mannequin initialized.");
// Becoming the mannequin with coaching information
knn.match(X_train, y_train, 10, 30);
Serial.println("Mannequin fitted with coaching information.");
}
void loop() {
// Instance take a look at with X_test
int* predictions = knn.predict(X_test, 1);
// Printing predictions
Serial.print("Predicted class (Actual = 0): ");
Serial.println(predictions[0]);
predictions = knn.predict(X_test_2, 1);
Serial.print("Predicted class (Actual = 1): ");
Serial.println(predictions[0]);
// Delay earlier than subsequent iteration (regulate as wanted)
delay(5000); // 5 seconds delay
// Clear up reminiscence
delete[] predictions;
}
2.12 — Outcomes
Full mission in: TinyML/16_KNN at main · thommaskevin/TinyML (github.com)
If you happen to prefer it, take into account shopping for my espresso ☕️💰 (Bitcoin)
code: bc1qzydjy4m9yhmjjrkgtrzhsgmkq79qenvcvc7qzn