MACHINE LEARNING

UNIT 4
UNSUPERVISED LEARNING ALGORITHMS

INTRODUCTION TO CLUSTERING
Clustering is a technique in machine learning and data analysis that involves
grouping similar data points based on certain features or characteristics.
The goal of clustering is to partition a dataset into groups, or clusters, in such a
way that the data points within a cluster are more similar to each other than to
those in other clusters. This helps identify patterns, structures, or relationships
within the data.

Clustering is useful in a variety of industries. Some common applications for

clustering:
• Market segmentation
• Social network analysis
• Search result grouping
• Medical imaging
• Image segmentation
• Anomaly detection
TYPES OF CLUSTERING

1. PARTITIONAL CLUSTERING:
This type of clustering divides the dataset into distinct clusters without
any overlap. Each data point belongs to exactly one cluster. A common
example is the K-means clustering algorithm.

K-Means Clustering
K-Means stands as one of the most widely used clustering algorithms due
to its simplicity and efficiency. This centroid-based technique organizes
data points around central vectors that represent clusters. The algorithm
works through a straightforward process:
1. Randomly initialize K centroids (cluster centers)
2. Assign each data point to its nearest centroid
3. Recalculate the centroids based on the assigned points
4. Repeat until convergence or maximum iterations reached
K-Means excels with spherical clusters of similar size but requires
specifying the number of clusters (K) beforehand. This makes it ideal for
customer segmentation, image compression, and document clustering
applications.
 Role of Distance Measures in Clustering:
Distance metrics are quantitative measures that allow us to compare
points in a dataset. Choosing the appropriate metric is critical because:
• Accuracy: It directly affects the formation of clusters by capturing the true
geometrical or statistical properties of data.
• Efficiency: Different calculation complexities can influence algorithm
performance, especially on large datasets.
• Interpretability: Understanding the underlying metric can provide
insights into the relationship between data points.

For Quantitative (Numeric) Data:

1. Euclidean Distance →

2. Manhattan Distance →
d(x,y)=∣x1−y1∣+∣x2−y2∣

For Qualitative (Categorical) Data:

1. Hamming Distance → Counts how many positions are different between
two categorical values.
Example: (Red, Blue) → distance = 1; (Red, Red) → distance = 0
2. Simple Matching Coefficient (SMC) → Compares matches and
mismatches of categorical attributes.

When to use K-means

• You want interpretability: K-means is easy to understand and interpret.
• Clusters are even-sized and globular-shaped: K-means work well when
clusters are well-separated globular shapes but do not perform well if
clusters are long and irregularly shaped.
 2. HIERARCHICAL CLUSTERING
Hierarchical clustering in machine learning builds a tree-like structure of clusters
that shows relationships at multiple levels. This method comes in two main
varieties:
• Agglomerative clustering: A “bottom-up” approach where each data
point starts as its cluster, and similar clusters merge iteratively until all
points form a single cluster
• Divisive clustering: A “top-down” approach that begins with all data in
one cluster and recursively splits into smaller groups
The results appear in a dendrogram—a tree diagram visualizing the arrangement
of clusters. Hierarchical clustering works well with any valid distance measure
and excels with hierarchical data like taxonomies.

When to use Hierarchical Clustering

• You are unsure about the number of clusters: Hierarchical clustering
requires the number of clusters to be predefined, but the clusters can be
viewed on a dendrogram and the number of clusters can be tweaked
without recomputation.
• You want computation efficiency: Cluster labels at any intermediate stage
can be recovered, therefore it is not necessary to recompute the proximity
matrix if the number of clusters changes.
• You have high dimensional data: Output can be visualized using a
dendrogram which can be used with higher dimensional data.
 K Means Vs Hierarchical Clustering
This comparison highlights the key differences between K Means and
Hierarchical Clustering, illustrating their suitability for different types of data
analysis tasks.

Feature K Means Clustering Hierarchical Clustering

Requires the number of clusters (K) Does not require the number of clusters
Initialization
to be specified in advance. to be specified; builds a dendrogram.

Algorithm Partitional: Divides the data into Agglomerative or Divisive: Builds a

Type non-overlapping clusters. hierarchy of clusters.

Relatively lower computational Higher computational complexity,

Complexity complexity, making it suitable for especially for large datasets, due to the
large datasets. hierarchical linkage.

Produces a dendrogram, allowing for

Result Produces a single level of clusters.
different levels of clustering granularity.

More flexible, as the dendrogram can be

Less flexible, as changing K requires
Flexibility cut at different levels to get different
re-running the algorithm.
clusterings.

Cluster Assumes clusters are spherical or Can accommodate clusters with various
Shape circular in shape. shapes and sizes.

Sensitive to the initial choice of Sensitive to the choice of distance metric

Sensitivity
centroids. and linkage criteria.

Provides a comprehensive view of data

Tends to find local optima; the
grouping but can also lead to different
Optimality result may vary across different
results based on distance and linkage
runs.
choices.

Suitable for applications requiring a Ideal for exploratory data analysis where
Use Case fixed number of clusters, like the relationships and hierarchies between
customer segmentation. data points are of interest.
KOHONEN SELF ORGANIZING MAP (SOM)
Kohonen self organizing map (SOM) is a type of unsupervised neural network.
It takes a large chunk of complicated, high-dimensional data and maps it onto a
two-dimensional grid while keeping things that are similar close together.
This makes SOMs great for:
• Clustering
• Dimensionality reduction
• Data visualization

Why Do We Need SOMs?

The main goals are:
1. Dimensionality Reduction: Convert data from many dimensions to 1D or
2D for visualization
2. Topology Preservation: Maintain neighborhood relationships - data
points that are similar in the original high-dimensional space remain close
in the output map
3. Clustering: Group similar data into clusters automatically
4. Visualization: Make complex high-dimensional data easy to see and
understand

How Does a Kohonen Self Organizing Map Work?

Let’s get into the meat of it — but keep it digestible.
Step 1: Initialize Weights
Assign random small values to the weight vectors of all neurons in the SOM grid.
Step 2: Input a Data Vector
Select an input vector (x) from the dataset.
Step 3: Find the Winning Neuron (BMU)
Compute the Euclidean distance between the input vector and each neuron’s
weight vector: The neuron with the smallest distance (D) is the winner (BMU).
Step 4: Update Weights
Update the weights of the BMU and its neighboring neurons using the formula:
New Weight=Old Weight+Learning Rate(α)×Neighborhood Function×(Input - Ol
d Weight)
wnew=wold+α×h×(x−wold)
Meaning of Each Term
• (x - w_{old}) → tells how far the neuron’s weight is from the input.
• α×h→ decides how big a step the neuron should move toward the input.
• So, the neuron’s weights shift closer to the input’s values.

Step 5: Repeat
Repeat steps 2–4 for all input data for many iterations until the map stabilizes.

Example:
Suppose we have two input features (X1, X2), and 4 neurons with random
weights.
Input vector: (0.8, 0.6)
Neuron weights (initial):

Neuron W1 W2

A 0.2 0.4

B 0.7 0.5

C 0.9 0.7
Neuron W1 W2

D 0.3 0.2

Compute distances:
• D(A) = √((0.8–0.2)² + (0.6–0.4)²) = 0.63
• D(B) = √((0.8–0.7)² + (0.6–0.5)²) = 0.14 (Smallest)
• D(C) = 0.14 (close, but not smaller)
• D(D) = 0.67
So Neuron B is the winner (BMU).
Now update Neuron B’s weights (and its neighbors):
W new=w old+α(x−w old)
If learning rate α=0.5
WB(new)=(0.7,0.5)+0.5[(0.8,0.6)−(0.7,0.5)]=(0.75,0.55)
Hence, the BMU’s weights move closer to the input.

FEATURE SELECTION
Feature Selection is the process of selecting the most important and relevant
features (attributes or variables) from a dataset to build an efficient and accurate
model.
It removes unnecessary, irrelevant, or redundant data, which helps in:
• Reducing model complexity
• Improving accuracy and performance
• Decreasing computation time
• Avoiding overfitting
Example:
Imagine predicting whether someone will get diabetes. You have data about:
• Age (useful)
 • Blood sugar level (useful)
• Glucose level (useful)
• Favorite color (not useful)
• Middle name (not useful)
• Shoe size (not useful)
Feature selection removes the useless columns (favorite color, middle name,
shoe size) and keeps only the useful ones.

Why is Feature Selection Important?

1. Improves Accuracy
By removing useless information, your model focuses on what actually matters.
Result: More accurate predictions.
2. Reduces Overfitting
Overfitting happens when a model learns noise and irrelevant patterns instead
of real patterns.
Supervised Feature Selection technique
supervised feature selection in machine learning can be further divided into
three categories.
1. Filters Method:
In the Filter Method, features are selected based on statistics measures. The
filter method filters out the model's irrelevant features and redundant columns
by using different metrics through ranking. Filter methods need low
computational time and do not overfit the data. Some standard techniques of
Filter methods are as follows:
1. Missing Value: Feature having the highest proportion of missing value can
be dropped.
2. Information Gain: Calculating the information gain of each variable to the
target variable helps to discard useless features.
3. Chi-square Test: The chi-square value is calculated between each feature
and the target variable, and the desired number of features with the best
chi-square value is selected.
4. Fisher's Score: Fisher's score returns the rank of the variable on the
Fisher's criteria in descending order. Then we can select the variables with
a significant fisher score.
3. Embedded Method:
These iterative methods optimally find the essential features in a
particular iteration. Some techniques of embedded methods are:
• Regularization: regularization adds a penalty term to different
parameters. Features with almost zero coefficients can be discarded from
the dataset. L1 Regularization (Lasso Regularization) or Elastic Nets (L1
and L2 regularization) are some of these regularization techniques.
• Random Forest Importance: Random Forest is a bagging algorithm that
aggregates a different number of decision trees. It ranks the nodes by their
performance or decreases in the Gini impurity over all the trees. Nodes
are arranged as per the impurity values, and thus it allows the pruning of
trees below a specific node. The leftover nodes create a subset of the most
important features.
 4. Wrapper Methods

In wrapper methodology, feature selection in Machine Learning is considered a

search problem. Based on the model's output, features are added or subtracted,
and the model has trained again with this feature set. Some popular techniques
of wrapper methods are:
• Forward selection: Forward selection begins with an empty set of
features. After each iteration, it keeps adding on a feature and evaluates
the performance to check whether it is improving the performance or not.
The process continues until adding a new feature does not enhance the
model's performance.
 • Backward elimination: Backward elimination is also an iterative approach.
It is also called as opposite of forward selection. This technique starts with
all the features and keeps removing the less significant ones. This
elimination process continues until removing the features does not
improve the model's performance.
• Exhaustive Feature Selection: Exhaustive feature selection in machine
learning tries each possible feature combination and returns the best-
performing feature set.
• Recursive Feature Elimination: It is a recursive greedy optimization
approach where features are selected by recursively taking a smaller and
smaller subset of features. Now, an estimator is trained with each set of
features, and the importance of each feature is determined to choose the
best set of features discarding the redundant ones.
Unsupervised Feature Selection Technique

Unsupervised feature selection techniques are used for unlabeled data, where
the target variable is not known. These techniques include:
• Principal Component Analysis (PCA): Reduces dimensionality by
transforming features into a new set of orthogonal components.
• Independent Component Analysis (ICA): Separates a multivariate signal
into additive, independent components.
 • Clustering-Based Methods: Group similar features together and select
representative features from each cluster.

DIMENSIONALITY REDUCTION
Dimensionality reduction is the process of transforming data from a high-
dimensional space into a lower-dimensional one while preserving its most
meaningful properties. This transformation effectively removes irrelevant or
redundant features to create a model with fewer variables, making analysis both
simpler and more powerful.

Why high-dimensional data is a problem

High-dimensional data refers to datasets with numerous predictor variables,
which pose several significant challenges for machine learning algorithms. This
phenomenon is often referred to as the “curse of dimensionality”.
The primary issues with high-dimensional data include:
• Data sparsity: As dimensions increase, data points become more sparse.
In fact, to maintain the same level of coverage, the number of data points
needed grows exponentially with each added dimension.
• Decreased accuracy: High dimensionality can lead to decreased accuracy
in predictive models. A typical rule of thumb suggests you need at least 5
training examples for each dimension to achieve reasonable
generalization.
• Computational burden: More dimensions mean increased computation
time and storage requirements.
• Overfitting risk: Models may learn noise instead of actual patterns,
especially when dimensions outnumber observations.
• Visualization difficulties: Data with more than three dimensions becomes
nearly impossible to visualize intuitively.
Dimensionality Reduction Techniques
1. Principal Component Analysis (PCA)
PCA stands as the most widely used dimensionality reduction algorithm that
identifies dominant patterns and creates linear combinations of original
variables with maximum variance. This technique transforms your data into
a new coordinate system where the first principal component captures the
largest variance, followed by subsequent components that are uncorrelated
with previous ones.
The beauty of PCA lies in its straightforward approach:
1. Standardize your data so each variable contributes equally
2. Compute the covariance matrix to understand relationships between
variables
3. Find eigenvectors and eigenvalues that determine new axes maximizing
variance
4. Sort components by importance based on eigenvalues
5. Project your data onto this new lower-dimensional space
PCA excels at exploratory data analysis, visualization, and preprocessing for
machine learning algorithms by extracting the most informative features
while minimizing information loss.

Linear Discriminant Analysis (LDA)

• Unlike previous techniques, LDA is a supervised approach that solves
multi-class classification problems. It separates multiple classes by finding
linear combinations of features that best characterize or distinguish
different classes.
• LDA works by maximizing the distance between projected means of
different classes (between-class variance) while minimizing the variance
within each class (within-class variance). This makes LDA particularly
valuable for classification tasks.
• The technique follows a generative model framework, meaning it models
data distribution for each class and uses Bayes’ theorem to classify new
data points. LDA works best when your data follows a normal distribution
and classes have equal covariance matrices.
[Link]:
These are neural network models designed for compression. They
encode input data into a lower-dimensional representation and then
attempt to reconstruct it. In the process, they learn efficient feature
representations, making them highly useful in deep learning and image
processing tasks.