\chapter{CLASSICAL MACHINE LEARNING ALGORITHMS} \label{c1}



Classical Machine Learning (ML) refers to a set of algorithms and techniques that were foundational in the development of artificial intelligence before the deep learning era. These algorithms focus on learning patterns from data using statistical and algebraic principles. They typically operate on structured datasets, such as tabular data, and are characterized by their interpretability, simplicity, and lower computational demands compared to modern deep neural networks{\cite{Reference7}}.

Mathematically, classical machine learning models can be understood as optimization problems where the goal is to minimize a loss function \( \mathcal{L}(\theta) \) over a set of parameters \( \theta \), subject to certain constraints or assumptions about the data. For instance, in linear regression, the objective is to minimize the squared error between the predicted and actual values:
\[
\min_\theta \mathcal{L}(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \left( h_\theta(x^{(i)}) - y^{(i)} \right)^2
\]
where \( h_\theta(x) \) is a linear hypothesis.

These models rely heavily on concepts from linear algebra, probability theory, and calculus. Unlike deep learning, which often requires massive datasets and GPUs, classical methods can yield robust and accurate results with limited data and modest computational resources.

\subsection{Key Characteristics}
Classical machine learning algorithms are defined by their simplicity, efficiency, and strong mathematical foundations. They typically rely on well-established statistical principles, making them easier to interpret and analyze. These algorithms perform well on structured data and require less computational power, making them ideal for small to medium-sized datasets. Unlike deep learning, which learns features automatically, classical ML emphasizes manual feature engineering—allowing domain knowledge to play a crucial role in model performance. Their transparency, reproducibility, and theoretical tractability make them a reliable choice for many practical applications and a foundational stepping stone for understanding advanced AI systems.
\begin{itemize}
    \item \textbf{Transparency:} Most classical ML models offer clear interpretations of how decisions are made.
    \item \textbf{Efficiency:} Fast training and inference times on small to medium-sized datasets.
    \item \textbf{Foundational Value:} Many principles in classical ML underlie modern algorithms, making them essential for understanding advanced AI techniques.
\end{itemize}

\noindent
\textbf{Examples of Classical Machine Learning Algorithms: }Regression methods (Linear, Logistic), Decision Trees and Random Forests, k-Nearest Neighbors (k-NN), Naive Bayes Classifiers, Support Vector Machines (SVM), Clustering Algorithms (K-Means, Hierarchical). While deep learning excels in tasks involving unstructured data such as images and audio, classical ML remains a powerful tool for many real-world applications involving structured data, such as finance, healthcare, and operations research.

\subsection{Importance and Relevance}

Classical machine learning algorithms have stood the test of time and remain highly relevant in both academic research and industrial applications. Despite the surge in popularity of deep learning, classical algorithms offer several practical advantages that make them indispensable in many scenarios.

\subsubsection*{Why Classical ML Still Matters}
Classical machine learning remains highly relevant due to its interpretability, low computational cost, and strong performance on structured datasets. In domains such as finance, healthcare, and education, where explanations behind predictions are essential, models like logistic regression or decision trees offer transparency that deep learning often lacks. Additionally, classical ML algorithms are efficient to train, require less data, and often serve as strong baselines or final models in real-world applications. Their ability to provide fast, interpretable, and reliable results ensures they continue to be a valuable part of the AI toolkit.
\begin{enumerate}
    \item \textbf{Simplicity and Interpretability:} Models such as linear regression and decision trees provide insights into the decision-making process. This is crucial in domains like healthcare and finance, where understanding ``why'' a decision was made is as important as the decision itself.

    \item \textbf{Low Computational Cost:} Classical algorithms typically have lower time and space complexity. For instance, the training time for linear regression using the normal equation is:
    \[
    \mathcal{O}(n^3) \quad \text{(due to matrix inversion of } X^T X)
    \]
    whereas gradient-based methods scale linearly with the number of samples \( m \).

    \item \textbf{Suitability for Small Datasets:} When data is limited, classical models often outperform deep learning methods, which require large volumes of training data to generalize well.

    \item \textbf{Feature-Centric Learning:} Classical methods emphasize the importance of feature engineering. Models like logistic regression or SVM rely heavily on how features are transformed and selected:
    \[
    h_\theta(x) = \sigma(\theta^T \phi(x))
    \]
    where \( \phi(x) \) is a manually designed feature transformation.

    \item \textbf{Theoretical Foundation:} Many classical algorithms are grounded in well-established mathematical theories such as:
    \begin{itemize}
        \item Probability theory (Naive Bayes)
        \item Optimization (SVM, Logistic Regression)
        \item Information theory (Decision Trees)
    \end{itemize}

    \item \textbf{Baseline Performance:} Classical models are often used as benchmarks or starting points in machine learning pipelines. Their quick training and validation cycles allow for rapid experimentation.
\end{enumerate}


\subsection{Comparison with Deep Learning}

While deep learning has revolutionized the field of artificial intelligence, classical machine learning (ML) algorithms continue to offer unique advantages in specific contexts. The choice between classical ML and deep learning depends on multiple factors, including the size and type of data, interpretability requirements, and computational resources.

\subsubsection*{Key Differences:}

\begin{table}[H]
\caption{Comparison of Classical ML vs. Deep Learning}
\centering
\resizebox{\textwidth}{!}{
\begin{tabular}{|p{4cm}|p{5.5cm}|p{5.5cm}|}
\hline
\textbf{Aspect} & \textbf{Classical ML} & \textbf{Deep Learning} \\
\hline
Data Requirements & Works well with small to medium structured datasets & Requires large volumes of data, especially unstructured \\
\hline
Feature Engineering & Manual and critical for model performance & Often automated via hierarchical feature learning \\
\hline
Model Complexity & Lower, fewer parameters & High complexity, millions of parameters \\
\hline
Interpretability & Generally high (e.g., linear models, decision trees) & Low (black-box models) \\
\hline
Training Time & Short training duration & High computational cost; requires GPUs \\
\hline
Inference Speed & Fast for models like Logistic Regression, SVM & Slower inference due to large network depth \\
\hline
Generalization & Strong with proper feature engineering and regularization & High when trained with sufficient data \\
\hline
Best Use Cases & Structured data, tabular problems & Image, video, text, speech \\
\hline
\end{tabular}
}
\end{table}

\subsection{Mathematical Viewpoint}
Classical machine learning algorithms are typically framed as convex optimization problems, where the objective is to minimize a loss function—such as mean squared error or cross-entropy—possibly with an added regularization term to control model complexity. These problems are mathematically well-behaved, ensuring efficient convergence to a unique global minimum using techniques like gradient descent or closed-form solutions. In contrast, deep learning models optimize highly non-convex loss functions due to the layered composition of nonlinear activations, leading to complex landscapes with many local minima. As a result, deep networks rely on iterative methods such as stochastic gradient descent to update parameters. While classical ML offers mathematical transparency and analytical tractability, deep learning sacrifices this clarity for greater expressive power on unstructured data. Classical ML models often solve convex optimization problems:
\[
\min_\theta \mathcal{L}(\theta) + \lambda R(\theta)
\]
where \( \mathcal{L} \) is the loss function, and \( R(\theta) \) is a regularization term (e.g., L1 or L2).

Deep learning involves solving highly non-convex optimization problems using gradient-based techniques such as stochastic gradient descent (SGD), often involving backpropagation in neural networks:
\[
\theta := \theta - \alpha \nabla_\theta \mathcal{L}(\theta)
\]

\subsection{When to select classical ML and DL}
Classical machine learning algorithms are widely used in domains where data is structured and interpretability is important. In finance, they power credit scoring and fraud detection; in healthcare, they assist in disease prediction and risk analysis using tabular patient data. Marketing teams use them for customer segmentation and churn prediction, while text classification tasks like spam detection and sentiment analysis benefit from models like Naive Bayes and SVM. Due to their efficiency, simplicity, and effectiveness on small to medium-sized datasets, classical ML models remain valuable tools in real-world decision-making systems.
\begin{itemize}
    \item \textbf{Use Classical ML} when:
    \begin{itemize}
        \item Dataset is small or medium-sized
        \item Interpretability is crucial
        \item Quick development and deployment is required
    \end{itemize}

    \item \textbf{Use Deep Learning} when:
    \begin{itemize}
        \item Handling complex data like images, audio, and natural language
        \item Feature learning is essential
        \item You have access to large datasets and high-performance computing
    \end{itemize}
\end{itemize}

\subsection{Use Cases and Limitations}

Classical machine learning algorithms are widely used in real-world applications where data is structured, and interpretability or efficiency is prioritized. These algorithms provide practical solutions across a broad range of domains, often serving as baseline models or production-ready solutions in industry workflows.

\subsection{Common Use Cases}
Classical machine learning techniques are commonly applied in structured data scenarios across various fields. In finance, logistic regression and decision trees are used for credit scoring and fraud detection. In healthcare, models like Naive Bayes and random forests assist in predicting diseases and analyzing patient risk factors. Marketing applications include customer segmentation with k-means clustering and churn prediction using classification models. Text classification tasks—such as spam detection and sentiment analysis—are efficiently handled by Naive Bayes and SVMs. These models are also used in operations for demand forecasting and predictive maintenance, demonstrating their versatility and reliability across domains.

\begin{itemize}
    \item \textbf{Finance}
    \begin{itemize}
        \item Credit scoring using logistic regression
        \item Fraud detection using decision trees and SVMs
    \end{itemize}

    \item \textbf{Healthcare}
    \begin{itemize}
        \item Disease prediction from tabular data using Naive Bayes and Random Forests
        \item Risk factor analysis using interpretable models like linear regression
    \end{itemize}

    \item \textbf{Marketing and Sales}
    \begin{itemize}
        \item Customer segmentation with k-means clustering
        \item Lead scoring and churn prediction using logistic regression
    \end{itemize}

    \item \textbf{Text Classification}
    \begin{itemize}
        \item Spam detection using Naive Bayes
        \item Sentiment analysis with SVMs
    \end{itemize}

    \item \textbf{Operations and Industrial Systems}
    \begin{itemize}
        \item Demand forecasting using linear regression
        \item Predictive maintenance with decision trees
    \end{itemize}
\end{itemize}

These tasks involve datasets with well-defined feature columns (e.g., age, income, temperature, etc.), where classical ML models can yield accurate, interpretable, and fast predictions.

\subsection{Limitations of Classical ML}

Despite their strengths, classical ML algorithms have certain limitations, particularly when dealing with high-dimensional or unstructured data:

\begin{itemize}
    \item \textbf{Limited Expressive Power:} May struggle to model complex non-linear patterns without extensive feature engineering.
    \item \textbf{Manual Feature Engineering:} Performance depends heavily on pre-processing and domain knowledge.
    \item \textbf{Scalability Constraints:} Algorithms like k-NN are expensive at prediction time for large datasets.
    \item \textbf{Sensitivity to Noise and Outliers:} Models like linear regression and SVMs can be affected by extreme or noisy values.
    \item \textbf{Not Ideal for Unstructured Data:} Classical methods are less effective for tasks involving images, audio, or text without transformation.
\end{itemize}


\section{Regression Techniques}

Regression is a fundamental supervised learning technique used to model the relationship between input features and a continuous output variable. It is one of the earliest and most widely used methods in classical machine learning, particularly effective when the relationship between variables is assumed to be linear or smoothly varying.


\subsection*{Linear Regression}

Linear regression models the target variable \( y \) as a linear function of the input features \( x = [x_1, x_2, ..., x_n] \). The hypothesis function is defined as:
\[
h_\theta(x) = \theta^T x = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_n x_n
\]
where \( \theta \) represents the model parameters. The objective is to minimize the \textit{Mean Squared Error (MSE)} cost function:
\[
J(\theta) = \frac{1}{2m} \sum_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2
\]
Two common approaches are used for optimization: \textbf{Gradient Descent}, which iteratively updates parameters using the gradient of the cost function, and the \textbf{Normal Equation}, which provides a closed-form solution:
\[
\theta = (X^T X)^{-1} X^T y
\]

Linear regression assumes linearity in the data, independence of errors, homoscedasticity (constant variance of errors), and normally distributed residuals. To avoid overfitting, regularization techniques are often employed. \textbf{Ridge Regression} adds an L2 penalty term \( \lambda \sum \theta_j^2 \) to shrink coefficients, while \textbf{Lasso Regression} applies an L1 penalty \( \lambda \sum |\theta_j| \) to enforce sparsity, effectively performing feature selection.

\subsection*{Logistic Regression}

Although named ``regression,'' logistic regression is primarily used for \textbf{binary classification} tasks. Instead of predicting a continuous value, it estimates the probability that a given input belongs to class 1. It uses the \textit{sigmoid function} to map predictions to the range [0, 1]:
\[
h_\theta(x) = \frac{1}{1 + e^{-\theta^T x}}
\]
The cost function used in logistic regression is the \textit{cross-entropy loss}:
\[
J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_\theta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)})) \right]
\]
A decision boundary is created by thresholding the output of the sigmoid function (commonly at 0.5), and the model predicts class 1 if the output exceeds the threshold.

For \textbf{multiclass classification}, logistic regression can be extended using strategies such as \textit{One-vs-All (OvA)}, where a separate binary classifier is trained for each class, or \textit{Softmax Regression}, which generalizes the sigmoid function to handle multiple classes simultaneously:
\[
P(y = j \mid x) = \frac{e^{\theta_j^T x}}{\sum_{k=1}^{K} e^{\theta_k^T x}}
\]

Both linear and logistic regression are widely used due to their interpretability, low computational cost, and effectiveness on small to moderately sized datasets. While linear regression is suited for continuous predictions, logistic regression forms the foundation for many classification tasks in fields such as medical diagnostics, marketing, and risk analysis. The Linear vs Logistic Regression Curves are shown in Figure~\ref{Figure61}.   
\begin{figure}[h]
 	\begin{center}
 		\includegraphics[height=8cm, width=8cm]{Figure61}
 		\caption{Linear vs Logistic Regression Curves}
 		\label{Figure61}
 	\end{center}
 	 \end{figure}



\section{Optimization Techniques}

To estimate the optimal parameters in linear regression, optimization techniques are employed to minimize the cost function. One widely used method is \textbf{Gradient Descent}, an iterative algorithm that updates each parameter \( \theta_j \) in the direction that reduces the cost function the most rapidly. The update rule for each iteration is:
\[
\theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j}
\]
where \( \alpha \) is the learning rate, controlling the size of each step. This method is particularly useful for large datasets or when an analytical solution is impractical. Alternatively, the \textbf{Normal Equation} provides a closed-form solution for the optimal parameters without iteration:
\[
\theta = (X^T X)^{-1} X^T y
\]
This method is computationally efficient for datasets with a small number of features but becomes expensive when \( X \) has many columns due to the cost of matrix inversion.

\subsection{Assumptions}

Linear regression relies on several key assumptions for the validity of its estimations:
\begin{itemize}
    \item \textbf{Linearity of the relationship:} The dependent variable is a linear combination of the input variables.
    \item \textbf{Independence of errors:} Observations are independent of each other, with uncorrelated residuals.
    \item \textbf{Homoscedasticity:} The variance of error terms is constant across all levels of the independent variables.
    \item \textbf{Normal distribution of errors:} The residuals (differences between observed and predicted values) are normally distributed.
\end{itemize}
Violations of these assumptions can impact the accuracy and interpretability of the regression model.

\subsection{Regularization}

To prevent overfitting, especially in high-dimensional datasets, regularization techniques introduce a penalty term to the loss function that discourages complex models. Two widely used approaches are:

\begin{itemize}
    \item \textbf{Ridge Regression (L2 regularization):} Adds the square of the magnitude of coefficients to the cost function:
    \[
    J(\theta) = \frac{1}{2m} \sum_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2 + \lambda \sum_{j=1}^{n} \theta_j^2
    \]
    This technique shrinks coefficients but does not set any to zero.
    
    \item \textbf{Lasso Regression (L1 regularization):} Adds the absolute value of the coefficients as a penalty term:
    \[
    J(\theta) = \frac{1}{2m} \sum_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2 + \lambda \sum_{j=1}^{n} |\theta_j|
    \]
    Unlike Ridge, Lasso can shrink some coefficients to exactly zero, effectively performing feature selection.
\end{itemize}

The Effect of Regularization on Model Accuracy is shown in Figure~\ref{Figure60}.   

\begin{figure}[h]
 	\begin{center}
 		\includegraphics[height=8cm, width=8cm]{Figure60}
 		\caption{Effect of Regularization on Model Accuracy}
 		\label{Figure60}
 	\end{center}
 	 \end{figure}


\subsection{Logistic Regression}

Logistic regression is a classification algorithm that models the probability that a given input belongs to a specific binary class (e.g., 0 or 1). Instead of fitting a straight line, it uses the sigmoid function to map the output to the interval [0, 1].

\subsubsection{Sigmoid Hypothesis Function}

The hypothesis function for logistic regression is defined as:
\[
h_\theta(x) = \sigma(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}}
\]
This output represents the estimated probability that the input \( x \) belongs to class 1.

\subsubsection{Cost Function (Cross-Entropy Loss)}

The cost function for logistic regression is derived from the likelihood of the Bernoulli distribution and is expressed as:
\[
J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[y^{(i)} \log(h_\theta(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_\theta(x^{(i)}))\right]
\]
This cross-entropy loss penalizes incorrect predictions and ensures convexity of the optimization problem.

\subsubsection{Decision Boundary}

Logistic regression outputs a probability, and a threshold is applied to make a binary decision. Commonly, if the predicted probability \( h_\theta(x) \) is greater than or equal to 0.5, class 1 is predicted; otherwise, class 0 is predicted:
\[
\text{Predict } y = 
\begin{cases}
1 & \text{if } h_\theta(x) \geq 0.5 \\
0 & \text{otherwise}
\end{cases}
\]

\subsubsection{Multiclass Logistic Regression}

For problems with more than two classes, logistic regression can be extended using:
\begin{itemize}
    \item \textbf{One-vs-All (OvA):} Build \( K \) binary classifiers where each model distinguishes one class from the rest.
    \item \textbf{Softmax Regression:} A generalized form that models the probability distribution over all \( K \) mutually exclusive classes using:
    \[
    P(y = j \mid x) = \frac{e^{\theta_j^T x}}{\sum_{k=1}^{K} e^{\theta_k^T x}}
    \]
\end{itemize}
This makes logistic regression suitable for both binary and multiclass classification problems with efficient probabilistic interpretation.




\section{Decision Trees and Rule-Based Learning}

Decision trees are supervised learning algorithms used for both classification and regression tasks. They model decisions and their possible consequences as a tree-like structure consisting of nodes, branches, and leaves.

\subsection{Basics of Decision Trees}

A decision tree consists of:
\begin{itemize}
    \item \textbf{Root Node:} Represents the entire dataset and initiates the splitting process.
    \item \textbf{Internal Nodes:} Represent a test on a feature.
    \item \textbf{Branches:} Outcomes of the test, leading to further nodes.
    \item \textbf{Leaf Nodes:} Terminal nodes that represent the output or class label.
\end{itemize}

The Decision Tree Structure with Splitting is shown in Figure~\ref{Figure62}. 
\begin{figure}[h]
 	\begin{center}
 		\includegraphics[height=8cm, width=8cm]{Figure62}
 		\caption{Decision Tree Structure with Splitting}
 		\label{Figure62}
 	\end{center}
 	 \end{figure}


\subsection{Splitting Criteria}

To determine the best feature to split the data, the following criteria are used:

\begin{itemize}
    \item \textbf{Information Gain (ID3):}
    \[
    IG(S, A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \cdot Entropy(S_v)
    \]
    where \( S \) is the dataset and \( A \) is the attribute.
    
    \item \textbf{Gini Index (CART):}
    \[
    Gini(S) = 1 - \sum_{i=1}^{C} p_i^2
    \]
    where \( p_i \) is the proportion of class \( i \) in dataset \( S \).
\end{itemize}

\subsection{Overfitting and Pruning}

Decision trees are prone to overfitting, especially when the tree grows too deep. To combat this:

\begin{itemize}
    \item \textbf{Pre-Pruning:} Stop the tree growth early by setting constraints (e.g., max depth, min samples).
    \item \textbf{Post-Pruning:} Allow the tree to grow fully and then remove nodes that provide little power using techniques like Reduced Error Pruning.
\end{itemize}

The Overfitting and Pruning in Trees is shown in Figure~\ref{Figure63}. 
\begin{figure}[h]
 	\begin{center}
 		\includegraphics[height=8cm, width=8cm]{Figure63}
 		\caption{Overfitting and Pruning in Trees}
 		\label{Figure63}
 	\end{center}
 	 \end{figure}

\subsection{Common Algorithms}

\begin{itemize}
    \item \textbf{ID3 (Iterative Dichotomiser 3):} Uses information gain for selecting the splitting attribute.
    \item \textbf{C4.5:} Extension of ID3 that handles continuous values, missing data, and uses gain ratio.
    \item \textbf{CART (Classification and Regression Trees):} Produces binary trees using Gini index.
\end{itemize}

\subsection{Random Forests (Optional)}

Random Forests are ensemble models that combine multiple decision trees to improve prediction accuracy and reduce overfitting.

\begin{itemize}
    \item \textbf{Bagging (Bootstrap Aggregation):} Each tree is trained on a random subset of data with replacement.
    \item \textbf{Feature Randomization:} At each node, a random subset of features is chosen to split.
    \item \textbf{Voting Mechanism:} For classification, the final output is determined by majority voting among all trees.
\end{itemize}

Random Forests often achieve high accuracy and robustness at the cost of interpretability compared to a single decision tree.




\subsection{Tree Structure}
A decision tree is a hierarchical structure used to make decisions based on data features. The structure comprises the following elements:

\begin{itemize}
    \item \textbf{Root Node:} The topmost node in the tree representing the entire dataset. It is the starting point for decision-making and splitting.
    
    \item \textbf{Internal Nodes (Decision Nodes):} Nodes that represent a test or decision on a feature. Each internal node splits the data into subsets based on specific conditions.
    
    \item \textbf{Branches:} Edges that connect nodes. Each branch represents the outcome of a decision or test at the parent node.
    
    \item \textbf{Leaf Nodes (Terminal Nodes):} These nodes represent the final output or class labels. Once a data point reaches a leaf, a decision has been made.
\end{itemize}

The flow from the root to a leaf node represents a sequence of decisions or rules that classify or predict the target variable. For instance, in classification tasks, each path from root to leaf can be interpreted as an if-then rule:

\begin{quote}
\textit{IF (feature\textsubscript{1} < threshold\textsubscript{1}) AND (feature\textsubscript{2} $\geq$ threshold\textsubscript{2}) THEN class = C}
\end{quote}


Such interpretability makes decision trees highly valuable in domains requiring transparency and explanation.


\section{k-Nearest Neighbors (k-NN)}

The k-Nearest Neighbors (k-NN) algorithm is a simple, instance-based, non-parametric supervised learning technique used for both classification and regression. It is called a \textit{lazy learning} algorithm because it does not construct an explicit model during the training phase.

\subsection{k-NN as Lazy Learning}

Unlike other algorithms, k-NN stores all training data and defers computation until a prediction is requested. During inference, it searches for the \( k \) closest training instances to the query point and assigns a label or value based on them. The k-NN Classification in Feature Space is shown in Figure~\ref{Figure64}. 
\begin{figure}[h]
 	\begin{center}
 		\includegraphics[height=8cm, width=8cm]{Figure64}
 		\caption{k-NN Classification in Feature Space}
 		\label{Figure64}
 	\end{center}
 	 \end{figure}

\subsection{Distance Metrics}

To determine the “closeness” between data points, different distance functions can be used:

\begin{itemize}
    \item \textbf{Euclidean Distance:}
    \[
    d(x, x') = \sqrt{\sum_{i=1}^{n}(x_i - x'_i)^2}
    \]

    \item \textbf{Manhattan Distance:}
    \[
    d(x, x') = \sum_{i=1}^{n}|x_i - x'_i|
    \]

    \item \textbf{Cosine Similarity:}
    \[
    \cos(\theta) = \frac{x \cdot x'}{\|x\| \cdot \|x'\|}
    \]
\end{itemize}

\subsection{Choosing the Value of \( k \)}

The performance of k-NN depends on the value of \( k \):

\begin{itemize}
    \item Small \( k \): Low bias, high variance (risk of overfitting)
    \item Large \( k \): High bias, low variance (risk of underfitting)
\end{itemize}

Typically, \( k \) is selected using cross-validation.

\subsection{Variants of k-NN}

\begin{itemize}
    \item \textbf{Weighted k-NN:} Assigns higher weights to closer neighbors, often inversely proportional to distance:
    \[
    w_i = \frac{1}{d(x, x^{(i)}) + \epsilon}
    \]

    \item \textbf{Distance-Weighted Voting:} Improves classification by emphasizing nearer neighbors.
\end{itemize}

\subsection{Complexity and Optimizations}

k-NN suffers from high computational cost at inference time, especially with large datasets. Optimizations include:

\begin{itemize}
    \item \textbf{KD-Trees:} Efficient for low-dimensional data; partitions space using axis-aligned hyperplanes.
    \item \textbf{Ball Trees:} More efficient for higher dimensions; partitions using hyperspheres.
    \item \textbf{Approximate Nearest Neighbors (ANN):} Uses hashing or random projection techniques to reduce search time.
\end{itemize}

Despite its simplicity, k-NN performs surprisingly well on many practical problems, especially when the dataset is small and low-dimensional.




\section{Clustering Algorithms}

Clustering is an unsupervised learning technique used to group similar data points based on inherent structure or patterns in the data. It is widely applied in exploratory data analysis, market segmentation, and image compression.

\subsection{K-Means Clustering}

K-Means is a centroid-based clustering algorithm that partitions the dataset into \( k \) distinct, non-overlapping clusters.
The K-Means Clustering with Centroids is shown in Figure~\ref{Figure65}.   

\begin{figure}[h]
 	\begin{center}
 		\includegraphics[height=8cm, width=8cm]{Figure65}
 		\caption{K-Means Clustering with Centroids}
 		\label{Figure65}
 	\end{center}
 	 \end{figure}

\subsubsection*{Objective Function}
The goal is to minimize the within-cluster sum of squares (WCSS):
\[
J = \sum_{i=1}^{k} \sum_{x_j \in C_i} \|x_j - \mu_i\|^2
\]
where \( \mu_i \) is the centroid of cluster \( C_i \).

\subsubsection*{Algorithm Steps}
\begin{enumerate}
    \item Initialize \( k \) cluster centroids (randomly or using k-means++).
    \item Assign each data point to the nearest centroid.
    \item Update each centroid as the mean of the points assigned to it.
    \item Repeat steps 2 and 3 until convergence (no changes in assignments).
\end{enumerate}

\subsubsection*{Initialization Techniques}
\begin{itemize}
    \item \textbf{Random Initialization:} Centroids chosen randomly from the data.
    \item \textbf{k-means++:} Improved method that spreads out initial centroids to enhance convergence and accuracy.
\end{itemize}

\subsubsection*{Evaluation Methods}
\begin{itemize}
    \item \textbf{Elbow Method:} Plots WCSS versus \( k \) to find the optimal number of clusters.
    \item \textbf{Silhouette Score:} Measures how similar an object is to its own cluster compared to other clusters.
\end{itemize}

\subsubsection*{Limitations}
\begin{itemize}
    \item Requires the number of clusters \( k \) in advance.
    \item Sensitive to initial centroids.
    \item Assumes spherical clusters of similar size.
\end{itemize}

\subsection{Hierarchical Clustering}

Hierarchical clustering builds a tree (dendrogram) of clusters by either merging or splitting them recursively.

\subsubsection*{Types}
\begin{itemize}
    \item \textbf{Agglomerative (Bottom-Up):} Starts with individual points and merges them into clusters.
    \item \textbf{Divisive (Top-Down):} Starts with one cluster and recursively splits it.
\end{itemize}

\subsubsection*{Linkage Criteria}
\begin{itemize}
    \item \textbf{Single Linkage:} Minimum distance between points in different clusters.
    \item \textbf{Complete Linkage:} Maximum distance between points.
    \item \textbf{Average Linkage:} Average pairwise distance between clusters.
\end{itemize}

\subsubsection*{Dendrogram}
A dendrogram is a tree-like diagram that records the sequences of merges or splits. By selecting a cut-off level, clusters can be extracted.

\subsubsection*{Comparison with K-Means}
\begin{itemize}
    \item Does not require a predefined number of clusters.
    \item Better suited for discovering nested or non-spherical structures.
    \item Computationally more expensive than K-Means.
\end{itemize}



\section{Comparative Analysis and Algorithm Selection}

Different machine learning algorithms offer various trade-offs in terms of accuracy, interpretability, computational complexity, and applicability. This section summarizes the key strengths, weaknesses, and selection criteria for classical ML algorithms.

\subsection{Strengths and Weaknesses}

\begin{table}[H]
\caption{Comparative Summary of Classical ML Algorithms}
\centering
\begin{tabular}{|p{3cm}|p{5.5cm}|p{5.5cm}|}
\hline
\textbf{Algorithm} & \textbf{Strengths} & \textbf{Weaknesses} \\
\hline
Linear Regression & Simple, fast, interpretable & Assumes linearity, sensitive to outliers \\
\hline
Logistic Regression & Interpretable, probabilistic output & Limited to linear decision boundaries \\
\hline
Decision Trees & Easy to interpret, handles categorical data & Prone to overfitting \\
\hline
Random Forest & Robust, accurate, reduces overfitting & Less interpretable, requires tuning \\
\hline
k-NN & Simple, non-parametric, no training phase & High prediction time, sensitive to scaling \\
\hline
Naive Bayes & Fast, good for high-dimensional data & Assumes feature independence \\
\hline
SVM & Effective in high-dimensional spaces, robust margins & Computationally intensive, kernel selection needed \\
\hline
K-Means & Fast, scalable, intuitive & Requires \( k \), sensitive to initialization \\
\hline
Hierarchical Clustering & No need to predefine \( k \), dendrograms are interpretable & Computationally expensive, sensitive to noise \\
\hline
\end{tabular}
\end{table}

\subsection{Guidelines for Model Selection}
Selecting the appropriate machine learning algorithm is a critical step that depends on the nature of the problem, the structure of the data, and the requirements of the task at hand. There is no universal model that performs best in all scenarios—each algorithm has its strengths and weaknesses. Factors such as dataset size, feature dimensionality, interpretability needs, computational constraints, and the availability of labeled data must be considered when making this choice. This section outlines practical guidelines to help in selecting suitable algorithms based on these considerations, ensuring that the chosen model aligns with both the data characteristics and application goals.

\noindent
\textbf{Small datasets:} When working with limited data, simpler models such as linear regression, logistic regression, k-nearest neighbors (k-NN), and decision trees are highly effective. These algorithms require fewer parameters, making them less prone to overfitting and easier to train with small sample sizes. Logistic regression and decision trees, in particular, provide interpretable results and are computationally inexpensive. k-NN, being non-parametric, works well when decision boundaries are simple and data is noise-free.

\noindent
\textbf{High-dimensional data:} In scenarios with a large number of features compared to the number of samples, algorithms like Naive Bayes and Support Vector Machines (SVM) are more suitable. Naive Bayes performs well in high-dimensional spaces, especially in text classification tasks where feature vectors are sparse. SVMs, with the use of kernel functions, can handle complex decision boundaries and often perform well even when the number of dimensions far exceeds the number of observations, provided the data is well-separated.

\noindent
\textbf{Need for interpretability:} Certain domains such as healthcare, finance, and law demand transparency and explainability in decision-making. In such cases, models like linear regression and decision trees are preferred due to their straightforward structure. Linear models offer a clear view of feature contributions through their coefficients, while decision trees can be visualized as a series of human-readable rules. This interpretability helps in building user trust and in complying with regulatory standards.

\noindent
\textbf{No labels available:} When labeled data is not available, unsupervised learning techniques such as clustering must be used. K-Means and hierarchical clustering are two widely used algorithms in this category. K-Means is efficient and intuitive for partitioning datasets into distinct groups based on feature similarity. Hierarchical clustering, on the other hand, reveals data hierarchy and is suitable for exploratory data analysis where the number of clusters is not known in advance.

\noindent
\textbf{Complex patterns in large datasets:} For datasets with large volumes and intricate patterns, ensemble methods like Random Forest are highly effective. These models combine the predictions of multiple decision trees to improve accuracy and generalization. Random Forests handle nonlinear relationships, feature interactions, and noise robustly. They are especially useful in real-world applications where feature relationships are complex and the data volume is substantial enough to benefit from parallelized learning.

\subsection{Trade-offs in Algorithm Choice}

Choosing an algorithm often involves balancing several competing criteria:

\begin{itemize}
    \item \textbf{Accuracy vs. Interpretability:} Deep models may perform better but are less interpretable than simpler models.
    \item \textbf{Training Time vs. Inference Time:} Lazy algorithms like k-NN defer cost to prediction, whereas others like SVM invest more in training.
    \item \textbf{Bias-Variance Trade-off:} Simpler models may have high bias, while complex ones risk high variance.
\end{itemize}

Ultimately, model selection should be guided by problem requirements, data characteristics, and evaluation through cross-validation.

















