UNIT-V

Clustering: Introduction to Clustering

1. Introduction

Clustering is an unsupervised learning technique used to group similar data points together
based on their features.
 Unlike supervised learning, clustering does not require labeled data.

 The goal is to maximize intra-cluster similarity (points in the same cluster are similar) and
minimize inter-cluster similarity (points in different clusters are dissimilar).

Applications:

 Customer segmentation in marketing

 Image segmentation in computer vision

 Document clustering in text mining

 Anomaly detection in fraud detection

Clustering is an unsupervised machine learning technique that groups similar data points
together based on their features, without using labeled data.

 Goal: Discover natural groupings or structure in unlabeled data.

 How it works: Data points are assigned to clusters using similarity or distance measures
(e.g., Euclidean distance, cosine similarity).
 Output: Each data point is assigned a cluster ID representing shared characteristics.

Example: Customer purchase data can be clustered to group customers with similar shopping habits
for targeted marketing or personalized recommendations.

2. Types of Clustering

2.1 Hard Clustering

 Definition: Each data point belongs strictly to one cluster; no overlap.

 Example: Customer assigned fully to either Cluster 1 or Cluster 2.

 Use cases: Market segmentation, customer grouping, document clustering.

 Limitation: Cannot represent ambiguity or overlapping groups.

Data Point Hard Clustering Soft Clustering

A Cluster 1 Cluster 1: 0.91, Cluster 2: 0.09

B Cluster 2 Cluster 1: 0.30, Cluster 2: 0.70

C Cluster 3 Cluster 1: 0.17, Cluster 2: 0.83

D Cluster 4 Cluster 1: 1.00, Cluster 2: 0.00

2.2 Soft Clustering

 Definition: Each data point can belong to multiple clusters with different probabilities.

 Example: A data point may have 70% membership in Cluster 1 and 30% in Cluster 2.

 Use cases: Overlapping class boundaries, fuzzy categories like customer personas or medical
diagnosis.
 Benefits: Captures ambiguity, models gradual transitions between clusters.

3. Types of Clustering Methods

3.1 Centroid-based Clustering (Partitioning Methods)

 Idea: Organizes data around central prototypes (centroids).

  Algorithms:

o K-Means: Assign points to nearest centroid; update centroids iteratively.

o K-Medoids: Uses actual data points as centers, robust to outliers.

 Pros: Fast, scalable, simple to interpret.

 Cons: Needs predefined k, sensitive to outliers, not suitable for non-spherical clusters.

3.2 Density-based Clustering (Model-based Methods)

 Idea: Clusters are regions of high data density separated by low-density regions.

 Algorithms:
o DBSCAN: Groups points with enough neighbors; labels sparse points as noise.

o OPTICS: Extends DBSCAN for varying densities.

 Pros: Handles arbitrary shapes, noisy data, no need to define number of clusters.

 Cons: Parameter tuning (epsilon, min points) can be tricky.

3.3 Connectivity-based Clustering (Hierarchical)

 Idea: Builds nested clusters based on data connectivity; creates dendrogram.

 Approaches:

o Agglomerative: Bottom-up; merge closest clusters.

o Divisive: Top-down; split clusters iteratively.

 Pros: Visual hierarchy, no predefined cluster number.

 Cons: Computationally expensive, merging/splitting is irreversible.

3.4 Distribution-based Clustering

 Idea: Assumes data is generated from mixture distributions (e.g., Gaussian).

 Algorithm: Gaussian Mixture Model (GMM) assigns points based on likelihood.

 Pros: Flexible shapes, probabilistic memberships, supports overlaps.

 Cons: Requires number of components, sensitive to initialization, computationally heavier.

3.5 Fuzzy Clustering

 Idea: Each data point can belong to multiple clusters with degrees of membership.

 Algorithm: Fuzzy C-Means

 Pros: Models ambiguity, handles overlapping clusters.

 Cons: Fuzziness parameter selection can be tricky, more computationally expensive than hard
clustering.
4. Use Cases

 Customer Segmentation: Group customers for targeted marketing and personalized

services.
 Anomaly Detection: Detect outliers or fraud in finance, networks, or sensors.

 Image Segmentation: Divide images into meaningful parts for object detection or medical
imaging.
 Recommendation Systems: Cluster user preferences to suggest movies, products, or
content.
 Market Basket Analysis: Discover frequently bought-together products to optimize store
layouts.

5. Conclusion

Clustering is a powerful unsupervised learning tool to uncover hidden patterns in unlabeled data.

 Hard clustering is crisp and easy to interpret.

 Soft/fuzzy clustering handles overlaps and ambiguity.

 Methods vary from centroid-based to density-based, hierarchical, and distribution-based,

each suitable for different data types.

Partitioning of Data in Clustering

1. Introduction

Partitioning of data is a clustering technique where the dataset is divided into distinct non-
overlapping clusters.

 Each data point belongs to exactly one cluster.

 The number of clusters, 𝑘, is specified in advance.

 Often used in centroid-based methods like K-Means.

Goal: Minimize intra-cluster distance (points in same cluster are similar) and maximize inter-cluster
distance (clusters are well-separated).
2. Definition

Partitioning clustering creates a single-level division of the dataset into 𝑘clusters:

𝐶1 , 𝐶2 , . . . , 𝐶𝑘

Where:

 𝐶𝑖 ∩ 𝐶𝑗 = ∅for 𝑖 ≠ 𝑗(no overlap)

 𝑘
 ⋃𝑖=1 𝐶𝑖 = All data points

3. Working of Partitioning Clustering

1. Initialize 𝑘clusters (randomly choose centroids).

2. Assign data points to the nearest cluster centroid (based on distance metric, e.g., Euclidean
distance).
3. Update cluster centroids based on the mean of assigned points.
4. Repeat steps 2–3 until centroids do not change or maximum iterations reached.

4. Example

Suppose we have a dataset of 6 points:

Point X Y

A 2 3

B 3 4
 Point X Y

C 5 8

D 6 9

E 1 2

F 7 10

 Choose 𝑘 = 2clusters

 Assign points to nearest centroid

 Update centroids iteratively
Resulting clusters:

 Cluster 1: A, B, E

 Cluster 2: C, D, F

5. Advantages

 Simple and easy to implement

 Works well with spherical clusters

 Scalable for large datasets

 Efficient in terms of computation

6. Disadvantages

 Requires pre-specifying number of clusters 𝑘

 Sensitive to initial centroids

 Not suitable for non-spherical or overlapping clusters

 Sensitive to outliers

7. Applications

 Market segmentation

 Image compression and segmentation

 Document clustering

 Customer grouping for personalized recommendations

8. Conclusion
Partitioning clustering is a fundamental clustering approach where data is divided into non-
overlapping clusters based on similarity.

 Forms the basis of K-Means and K-Medoids algorithms

 Efficient for large datasets but less effective for complex cluster shapes

Matrix Factorization and Clustering of Patterns

1. Introduction

Matrix Factorization is a technique in machine learning and data analysis that decomposes a data
matrix into a product of two or more smaller matrices.

 Used to reduce dimensionality, find latent features, and uncover hidden patterns in data.

 Often applied in recommendation systems, image processing, and pattern discovery.

Clustering of Patterns refers to the process of grouping similar patterns (rows or columns in a
matrix) into clusters based on their characteristics.

 Helps discover hidden relationships among data points or features.

2. Definition

2.1 Matrix Factorization

Given a data matrix 𝑋of size 𝑚 × 𝑛:

𝑋 ≈𝑊⋅𝐻

Where:
  𝑊→ 𝑚 × 𝑘matrix (feature matrix)

 𝐻→ 𝑘 × 𝑛matrix (coefficient matrix)

 𝑘→ number of latent factors

 The goal is to minimize the difference between 𝑋and 𝑊 ⋅ 𝐻

Applications: Collaborative filtering, dimensionality reduction, noise reduction.

2.2 Clustering of Patterns

 Definition: Grouping rows (data points) or columns (features) of a matrix that exhibit similar
patterns.
 Often done after matrix factorization, where latent features capture the underlying structure.
Goal: Find clusters of similar patterns in the reduced feature space.

3. Working

1. Start with a data matrix 𝑋representing observations (rows) and features (columns).

2. Apply matrix factorization to decompose into 𝑊and 𝐻(latent factors).

3. Compute similarity between rows (or columns) in the reduced feature space.

4. Apply clustering algorithm (e.g., K-Means, hierarchical) to group similar patterns.

5. Interpret clusters to identify hidden structures or relationships.

4. Example

Movie Recommendation Data:

User Movie 1 Movie 2 Movie 3

A 5 3 ?

B 4 ? 2

C ? 5 4

 Step 1: Factorize user-movie rating matrix using matrix factorization (e.g., SVD or NMF).

 Step 2: Extract latent features for users and movies.

 Step 3: Cluster users or movies based on similar patterns in latent feature space.

 Result: Users with similar tastes or movies with similar ratings are grouped together.
5. Advantages

 Reduces dimensionality while preserving structure

 Reveals hidden relationships in data

 Combines matrix factorization and clustering for effective pattern discovery

 Improves interpretability of large datasets

6. Disadvantages

 Computationally intensive for very large matrices

 Requires careful selection of latent factors 𝑘

 Sensitive to noise in data

 Clustering results depend on distance metrics and algorithm choice

7. Applications

 Recommendation systems: Group users or items based on preferences

 Image processing: Identify clusters of similar images or patterns

 Bioinformatics: Cluster gene expression patterns

 Market analysis: Group products or customers with similar behaviors

8. Conclusion

Matrix factorization combined with clustering is a powerful technique to extract latent features
and group similar patterns.
Divisive Clustering

1. Introduction

Divisive Clustering is a top-down hierarchical clustering technique.

 Starts with all data points in a single cluster.

 Iteratively splits clusters into smaller sub-clusters until each data point forms its own cluster
or a stopping criterion is met.
 Produces a dendrogram, which is a tree-like structure representing cluster splits.

Applications:

 Document classification
  Gene expression analysis

 Image segmentation

 Social network analysis

2. Definition

Divisive clustering builds nested groupings of data from top (one cluster) to bottom (individual
points):

Start: 𝐶 = {All points} → 𝐶1 , 𝐶2 , . . . , 𝐶𝑛

 Hierarchical: Each split forms sub-clusters

 No need to specify number of clusters in advance

3. Working of Divisive Clustering

1. Start with one cluster containing all data points.

2. Identify the most heterogeneous cluster (largest dissimilarity).

3. Split the cluster into two (or more) sub-clusters based on distance or dissimilarity measures.

4. Repeat steps 2–3 for sub-clusters until:

o Each data point is in its own cluster or

o A stopping criterion (e.g., desired number of clusters) is met.

 5. Build a dendrogram representing the hierarchy of splits.

4. Example

Suppose we have 6 points (A, B, C, D, E, F):

1. Start with all points in Cluster 1.

2. Split into Cluster 1a = {A, B, E} and Cluster 1b = {C, D, F} based on distance.

3. Further split Cluster 1b into Cluster 1b1 = {C, D} and Cluster 1b2 = {F}.

4. Repeat until desired granularity.

Result: Hierarchical clusters shown as a dendrogram.

5. Advantages

 Provides complete hierarchy of clusters

 No need to predefine number of clusters

 Can handle varied cluster shapes and sizes

 Useful for visualization and exploration of data structure

6. Disadvantages

 Computationally expensive for large datasets

 Splitting decisions are irreversible

 Sensitive to distance metrics and outliers

 Less efficient compared to bottom-up (agglomerative) clustering for very large data
7. Applications

 Text mining and document classification

 Bioinformatics (gene clustering)

 Customer segmentation in marketing

 Hierarchical image segmentation

8. Conclusion
Divisive clustering is a top-down hierarchical approach that splits clusters iteratively to reveal the
data’s structure.
 Produces a dendrogram for hierarchical representation.

 Effective for exploring data hierarchy but computationally intensive for large datasets.

Agglomerative Clustering

1. Introduction

Agglomerative Clustering is a bottom-up hierarchical clustering technique.

 Starts with each data point as its own cluster.

 Iteratively merges the closest clusters until all points are combined into a single cluster or a
stopping criterion is met.
 Produces a dendrogram, a tree-like representation of cluster merges.

Applications:

 Document clustering

 Customer segmentation

 Image segmentation

 Bioinformatics (gene expression analysis)

2. Definition

Agglomerative clustering builds a hierarchy of clusters from bottom to top:

𝐶1 , 𝐶2 , . . . , 𝐶𝑛 → 𝐶1,2,...,𝑛

Where:
 Each point starts in its own cluster

 Closest clusters are merged iteratively

 Stops when all points belong to one cluster or the desired number of clusters is reached

3. Working of Agglomerative Clustering

 1. Initialize each data point as its own cluster.

2. Compute distance matrix between all clusters (using Euclidean, Manhattan, or other distance
metrics).
3. Merge the two closest clusters into a single cluster.

4. Update distance matrix to reflect new cluster distances (methods include single-linkage,
complete-linkage, average-linkage).
5. Repeat steps 3–4 until all points are merged or desired number of clusters is reached.

6. Visualize the hierarchy using a dendrogram.

4. Example

Suppose we have 5 points (A, B, C, D, E):

1. Start: 5 clusters → {A}, {B}, {C}, {D}, {E}

2. Merge closest: {A, B}, {C}, {D}, {E}

3. Merge next closest: {A, B}, {C, D}, {E}

4. Merge remaining clusters until all points belong to one cluster

Dendrogram represents the hierarchy of merges.

5. Advantages

 Produces complete hierarchy of clusters

 No need to predefine the number of clusters
  Can handle non-spherical clusters

 Provides visual representation of data structure

6. Disadvantages

 Computationally expensive for large datasets (𝑂(𝑛3 ) in naive implementations)

 Merging decisions are irreversible

 Sensitive to distance metrics and outliers

 Less scalable compared to partitioning methods like K-Means

7. Applications

 Text mining (document or article clustering)

 Customer segmentation

 Image segmentation (medical imaging, computer vision)

 Bioinformatics (gene expression patterns, protein clustering)

8. Conclusion

Agglomerative Clustering is a bottom-up hierarchical approach that merges clusters iteratively to

reveal the structure of data.
 Produces a dendrogram for hierarchical visualization.

 Effective for exploratory data analysis but computationally heavy for very large datasets.

Partitional Clustering

1. Introduction

Partitional Clustering is a clustering technique that divides a dataset into a set of non-
overlapping clusters.
 Each data point belongs to exactly one cluster.

 Unlike hierarchical clustering, partitional clustering does not create nested clusters.

 Typically requires predefining the number of clusters 𝑘.

Applications:
 Customer segmentation

 Image compression
  Market basket analysis

 Recommendation systems

2. Definition

Partitional clustering partitions the data set into 𝑘clusters:

𝐶1 , 𝐶2 , . . . , 𝐶𝑘

Where:
 𝐶𝑖 ∩ 𝐶𝑗 = ∅for 𝑖 ≠ 𝑗
𝑘
 ⋃𝑖=1 𝐶𝑖 = All data points

The goal is to minimize intra-cluster distance and maximize inter-cluster distance.

3. Working of Partitional Clustering

1. Choose number of clusters 𝑘

2. Initialize cluster centers (randomly or using heuristics)

3. Assign each data point to the nearest cluster center

4. Recompute cluster centers as the mean of points in each cluster

5. Repeat steps 3–4 until:

o Cluster assignments do not change, or

o Maximum iterations reached

4. Example

Suppose we have 6 points: A, B, C, D, E, F and we want k = 2 clusters:

 Step 1: Randomly select initial centroids

 Step 2: Assign points to nearest centroid → Cluster 1: {A, B, E}, Cluster 2: {C, D, F}
  Step 3: Update centroids and reassign points

 Step 4: Repeat until centroids stabilize

5. Advantages

 Simple and easy to implement

 Efficient for large datasets

 Works well for spherical or evenly-sized clusters

 Scalable and computationally faster than hierarchical methods

6. Disadvantages

 Requires predefining 𝑘

 Sensitive to initial centroids

 Not suitable for non-spherical or overlapping clusters

 Sensitive to outliers and noise

7. Applications

 Customer segmentation: Grouping based on purchasing behavior

 Image compression: Grouping pixels with similar intensity

 Market analysis: Identifying product clusters

 Recommendation systems: Clustering users or items

8. Conclusion

Partitional clustering is an efficient and widely used technique for dividing data into non-
overlapping clusters.

K-Means Clustering
1. Introduction

K-Means Clustering is a popular partitional clustering algorithm used to group data points into
𝑘clusters.

 Each cluster is represented by its centroid (mean of points in the cluster).

 The algorithm is iterative, optimizing cluster assignments to minimize intra-cluster variance.

 Widely used in data mining, image processing, and customer segmentation.

2. Definition

K-Means clustering aims to partition 𝑛data points into 𝑘clusters 𝐶1 , 𝐶2 , . . . , 𝐶𝑘 by minimizing the sum
of squared distances (SSD) between points and their cluster centroids:
𝑘

Minimize ∑ ∑ ∥ 𝑥 − 𝜇𝑖 ∥2
𝑥∈𝐶𝑖
𝑖=1

Where:

 𝑥→ Data point

 𝜇𝑖 → Centroid of cluster 𝐶𝑖

 𝑘→ Number of clusters

3. Working of K-Means

1. Initialize 𝑘centroids (randomly select 𝑘points).

2. Assign each data point to the nearest centroid based on a distance metric (e.g., Euclidean
distance).
3. Recalculate centroids as the mean of points in each cluster.
 4. Repeat steps 2–3 until:
o Cluster assignments do not change, or

o Maximum iterations reached.

4. Example

Suppose we have 6 data points: A, B, C, D, E, F, and want k = 2:

1. Initialize 2 centroids (say A and D)

2. Assign each point to nearest centroid → Cluster 1: {A, B, E}, Cluster 2: {C, D, F}

3. Recompute centroids → new means of clusters

4. Reassign points → repeat until centroids stabilize
Result: Two distinct clusters with minimized intra-cluster distance

5. Advantages

 Simple and easy to implement

 Efficient for large datasets

 Converges quickly for well-separated clusters

 Scalable and widely used

6. Disadvantages

 Requires predefining number of clusters 𝑘

 Sensitive to initial centroids (may converge to local minima)

 Not suitable for non-spherical clusters

 Sensitive to outliers and noise

7. Applications

 Customer segmentation for marketing

 Image compression and segmentation

 Document clustering
 Recommendation systems

 Pattern recognition in sensor data

8. Conclusion

K-Means Clustering is a simple and efficient clustering algorithm suitable for many practical
applications.
 Works best for spherical, well-separated clusters

 Forms the foundation for many advanced clustering techniques

Soft Partitioning (Fuzzy Clustering)

1. Introduction

Soft Partitioning, also called Fuzzy Clustering, is a clustering technique where each data point
can belong to multiple clusters with varying degrees of membership.

 Unlike hard partitioning, where a point belongs to exactly one cluster, soft partitioning
assigns probabilities or membership values to each cluster.

 Useful when clusters overlap or boundaries are not well-defined.

Applications:

 Customer segmentation with overlapping behaviors

 Medical diagnosis (uncertain categories)

 Pattern recognition

 Image segmentation with fuzzy boundaries

2. Definition

Soft partitioning assigns a membership degree 𝑢𝑖𝑗 to each data point 𝑥𝑗 for each cluster 𝐶𝑖 :
𝑘

0 ≤ 𝑢𝑖𝑗 ≤ 1, ∑ 𝑢𝑖𝑗 = 1
𝑖=1

Where:
 𝑢𝑖𝑗 → Membership of data point 𝑥𝑗 in cluster 𝐶𝑖

 𝑘→ Number of clusters
 Points can have partial membership in multiple clusters

3. Working of Soft Partitioning (Fuzzy C-Means)

 1. Initialize cluster centers (randomly) and membership degrees.

2. Compute membership values of each point to clusters using:

1
𝑢𝑖𝑗 =
𝑘 ∣∣ 𝑥 − 𝑐𝑖 ∣∣ 2
∑𝑙=1( 𝑗 )𝑚−1
∣∣ 𝑥𝑗 − 𝑐𝑙 ∣∣

Where 𝑚 > 1is the fuzziness parameter.

3. Update cluster centers based on weighted membership:

𝑛
𝑚
∑ 𝑢𝑖𝑗 𝑥𝑗
𝑗=1
𝑐𝑖 = 𝑛
𝑚
∑ 𝑢𝑖𝑗
𝑗=1

4. Repeat steps 2–3 until membership values converge.

4. Example

Suppose a point X has partial membership in 2 clusters:

Data Point Cluster 1 Cluster 2

X 0.7 0.3

Y 0.2 0.8

Z 0.5 0.5

 Interpretation:

o X mostly belongs to Cluster 1

o Y mostly belongs to Cluster 2

o Z equally belongs to both clusters

5. Advantages

 Captures ambiguity and overlaps in data

 Useful for gradual transitions between clusters

 Provides membership probabilities, not just hard assignments

 Flexible for complex datasets

6. Disadvantages

 Computationally more expensive than hard clustering

 Choosing the fuzziness parameter 𝑚is critical

 Sensitive to initial cluster centers

 Membership interpretation can be subjective

7. Applications

 Customer segmentation: Overlapping buyer behavior

 Medical diagnosis: Patients with symptoms belonging to multiple categories

 Image segmentation: Soft boundaries in images

 Recommendation systems: Items can belong to multiple preference groups

8. Conclusion

Soft Partitioning (Fuzzy Clustering) allows flexible cluster assignment, making it ideal for
datasets with overlapping or uncertain clusters.

 Extends the idea of hard clustering

 Forms the basis for Fuzzy C-Means (FCM) algorithm

 Widely used in pattern recognition, medical, and image analysis

Soft Clustering

1. Introduction

Soft Clustering is a clustering technique where data points can belong to multiple clusters
simultaneously with varying degrees of membership.

 Different from hard clustering, where each point belongs to exactly one cluster.

 Also known as fuzzy clustering, widely used when cluster boundaries are ambiguous.

Applications:

 Customer segmentation with overlapping behaviors

 Medical diagnosis with uncertain categories

 Image segmentation with soft edges

 Pattern recognition
2. Definition

Soft clustering assigns a membership value 𝑢𝑖𝑗 to each data point 𝑥𝑗 for each cluster 𝐶𝑖 :
𝑘

0 ≤ 𝑢𝑖𝑗 ≤ 1, ∑ 𝑢𝑖𝑗 = 1
𝑖=1

Where:

 𝑢𝑖𝑗 → Degree of membership of data point 𝑥𝑗 in cluster 𝐶𝑖

 𝑘→ Number of clusters
 Points may belong partially to multiple clusters

3. Working of Soft Clustering

1. Initialize cluster centers randomly and set initial membership values.

2. Compute membership values for each data point based on distance to cluster centers.

3. Update cluster centers using weighted membership values:

𝑛
𝑚
∑ 𝑢𝑖𝑗 𝑥𝑗
𝑗=1
𝑐𝑖 = 𝑛
𝑚
∑ 𝑢𝑖𝑗
𝑗=1

Where 𝑚 > 1is the fuzziness parameter.

4. Repeat steps 2–3 until membership values converge.

4. Example

Data Point Cluster 1 Cluster 2

A 0.8 0.2

B 0.4 0.6

C 0.5 0.5

 Interpretation:

o A mostly belongs to Cluster 1

o B mostly belongs to Cluster 2

 o C equally belongs to both clusters

5. Advantages

 Models overlaps and ambiguity in data

 Provides probabilistic cluster membership

 Flexible for complex or fuzzy datasets

 Useful in soft decision-making scenarios

6. Disadvantages

 More computationally intensive than hard clustering

 Requires choosing fuzziness parameter 𝑚carefully

 Sensitive to initial cluster centers

 Interpretation of memberships can be subjective

7. Applications

 Customer segmentation: Overlapping purchasing behavior

 Medical diagnosis: Patients fitting multiple categories

 Image processing: Soft segmentation of images

 Recommendation systems: Items belonging to multiple preference groups

8. Conclusion

Soft Clustering allows data points to belong to multiple clusters, capturing ambiguity and fuzzy
boundaries.
 Extends hard clustering by allowing partial membership

 Forms the basis for Fuzzy C-Means and other soft clustering algorithms

 Widely used in pattern recognition, medical, and image analysis applications

Fuzzy C-Means (FCM) Clustering

1. Introduction
Fuzzy C-Means (FCM) is a soft clustering algorithm that allows data points to belong to multiple
clusters with varying degrees of membership.

 It is an extension of K-Means, but instead of hard assignments, it uses fuzzy memberships.

 Widely used in pattern recognition, image processing, and medical data analysis.

2. Definition

FCM minimizes the following objective function:

𝑘
𝑛
𝑚
𝐽𝑚 = ∑ ∑ 𝑢𝑖𝑗 ∥ 𝑥𝑗 − 𝑐𝑖 ∥2
𝑗=1
𝑖=1

Where:

 𝑥𝑗 → Data point

 𝑐𝑖 → Cluster center

 𝑢𝑖𝑗 → Membership of 𝑥𝑗 in cluster 𝑖

 𝑚 > 1→ Fuzziness parameter controlling the degree of cluster overlap

 𝑘→ Number of clusters

 𝑛→ Number of data points

The goal is to minimize the weighted sum of squared errors, considering membership degrees.
3. Working of Fuzzy C-Means

1. Initialize cluster centers 𝑐𝑖 and membership matrix 𝑈randomly.

2. Compute cluster centers based on membership values:

𝑛
𝑚
∑ 𝑢𝑖𝑗 𝑥𝑗
𝑗=1
𝑐𝑖 = 𝑛
𝑚
∑ 𝑢𝑖𝑗
𝑗=1

3. Update membership values for each data point:

1
𝑢𝑖𝑗 = 𝑘
2
∥ 𝑥𝑗 − 𝑐𝑖 ∥ 𝑚−1
∑ (∥ 𝑥 − 𝑐 ∥)
𝑗 𝑙
𝑙=1

4. Repeat steps 2–3 until convergence (changes in 𝑈are below a threshold).

4. Example

Suppose 3 data points (A, B, C) and 2 clusters:

Point Cluster 1 Cluster 2

A 0.8 0.2

B 0.5 0.5

C 0.3 0.7

 Interpretation:

o A mostly belongs to Cluster 1

o B belongs equally to both clusters

o C mostly belongs to Cluster 2

5. Advantages

 Captures overlaps and ambiguity in data

 Provides fuzzy membership probabilities

 More flexible than hard clustering (like K-Means)

 Useful in medical diagnosis, image segmentation, and pattern recognition

6. Disadvantages

 Requires predefining number of clusters 𝑘

 Sensitive to initialization of membership matrix

 Choosing fuzziness parameter 𝑚can be tricky

 More computationally intensive than hard clustering

7. Applications

 Medical imaging: Segmenting tissues in MRI/CT scans

 Pattern recognition: Speech or handwriting analysis

 Customer segmentation: Overlapping behavioral groups

 Image processing: Soft object segmentation in images

8. Conclusion

Fuzzy C-Means Clustering is a soft clustering technique that allows partial membership of points
in clusters.
 Extends K-Means by adding fuzzy membership

 Ideal for overlapping clusters or uncertain boundaries

 Widely used in data analysis, pattern recognition, and image processing

Rough Clustering
1. Introduction

Rough Clustering is a clustering technique based on Rough Set Theory.

 Each cluster is represented by a lower approximation (definite members) and an upper

approximation (possible members).

 It allows uncertainty and vagueness in cluster assignments.

 Useful when data is imprecise or overlapping.

Applications:

 Medical diagnosis with uncertain categories

 Customer segmentation with ambiguous behavior

 Decision support systems

 Pattern recognition

2. Definition

In Rough Clustering, each cluster 𝐶is divided into:

1. Lower Approximation (𝐶𝐿 ): Data points that definitely belong to the cluster.

2. Upper Approximation (𝐶𝑈 ): Data points that possibly belong to the cluster.

 Points in 𝐶𝑈 ∖ 𝐶𝐿 are boundary points, representing uncertainty.

 The goal is to cluster data while handling uncertainty.

3. Working of Rough Clustering

1. Start with the dataset and define indiscernibility relations based on features.
 2. Identify lower and upper approximations for potential clusters.

3. Assign certain points to the lower approximation and uncertain points to the upper
approximation.
4. Iterate to refine cluster boundaries using similarity or distance measures.

5. Output rough clusters with definite and boundary points.

4. Example

Suppose 6 points: A, B, C, D, E, F.
 Cluster 1:

o Lower Approximation: {A, B} → definitely belong

o Upper Approximation: {A, B, C} → possibly belong

 Cluster 2:

o Lower Approximation: {D, E} → definitely belong

o Upper Approximation: {D, E, F} → possibly belong

Boundary points: C in Cluster 1, F in Cluster 2 → uncertain cluster assignment

5. Advantages

 Handles uncertainty and vagueness in data

 Identifies boundary points clearly

 Suitable for noisy or overlapping datasets

 Provides flexible cluster definitions

6. Disadvantages

 Computationally more complex than K-Means or hard clustering

 Requires defining approximations carefully

 Interpretation of boundary points can be subjective

 Less widely used than traditional clustering methods

7. Applications
  Medical diagnosis: Handling ambiguous patient data

 Customer segmentation: Overlapping or unclear behavioral groups

 Decision support systems: Handling uncertain data inputs

 Pattern recognition: Clustering ambiguous or noisy patterns

8. Conclusion

Rough Clustering is a soft clustering approach based on Rough Set Theory.

 Uses lower and upper approximations to handle uncertainty

 Ideal for overlapping, ambiguous, or noisy datasets

 Extends traditional clustering methods to incorporate vagueness

Rough K-Means Clustering Algorithm

1. Introduction

Rough K-Means Clustering is an extension of the K-Means algorithm that incorporates Rough Set
Theory to handle uncertain or overlapping data points.

 Unlike standard K-Means where each point belongs to a single cluster, Rough K-Means uses
lower and upper approximations:

o Lower approximation: points that definitely belong to a cluster

o Upper approximation: points that possibly belong to a cluster

 It is useful for noisy, ambiguous, or overlapping datasets.

Applications:

 Customer segmentation with ambiguous behavior

 Image segmentation with unclear boundaries

 Medical data analysis with uncertain classifications

 Pattern recognition in noisy datasets

2. Definition

Rough K-Means clusters 𝑛data points into 𝑘clusters using rough set concepts:

 Lower approximation (C_L): points definitely in cluster

 Upper approximation (C_U): points possibly in cluster

 Boundary region (C_U − C_L): uncertain points

Goal: Minimize intra-cluster distance while handling uncertainty:
𝑘

𝐽 = ∑ ∑ ∥ 𝑥𝑗 − 𝑐𝑖 ∥2 + ∑ 𝑤 ∥ 𝑥𝑗 − 𝑐𝑖 ∥2
𝑥𝑗 ∈𝐶𝐿 𝑥𝑗 ∈𝐶𝐵
𝑖=1

Where:

 𝑥𝑗 → Data point

 𝑐𝑖 → Cluster centroid

 𝐶𝐵 = 𝐶𝑈 − 𝐶𝐿 → Boundary points

 𝑤→ Weight factor for boundary points

3. Working of Rough K-Means

1. Initialize 𝑘cluster centroids randomly.

2. Assign points to clusters based on distance:

o If a point is clearly closer to one centroid → assign to lower approximation

o If a point is ambiguous → assign to upper approximation (boundary region)

3. Update cluster centroids using weighted averages of points in lower and boundary regions:

∑ 𝑥𝑗 + 𝑤 ∑ 𝑥𝑗
𝑥𝑗 ∈𝐶𝐿 𝑥𝑗∈𝐶𝐵
𝑐𝑖 =
∣ 𝐶𝐿 ∣ +𝑤 ∣ 𝐶𝐵 ∣

4. Reassign points based on updated centroids.

5. Repeat steps 3–4 until centroids stabilize.

6. Output clusters with lower and upper approximations.

4. Example

Suppose 6 points: A, B, C, D, E, F and 2 clusters:

Cluster Lower Approximation Upper Approximation

1 {A, B} {A, B, C}

2 {D, E} {D, E, F}

 Boundary points: C (Cluster 1) and F (Cluster 2) → uncertain membership

  Centroids updated using both lower and boundary points with weight 𝑤

5. Advantages

 Handles uncertain and overlapping data points

 Incorporates rough set concepts for flexible clustering

 Produces clusters with lower and upper approximations, clearly showing boundary points

 Useful for noisy datasets

6. Disadvantages

 More computationally intensive than standard K-Means

 Requires choosing weight factor 𝑤

 Sensitive to initial centroids

 Boundary interpretation can be subjective

7. Applications

 Customer segmentation: Overlapping buying behaviors

 Medical data analysis: Patients with ambiguous symptoms

 Image segmentation: Soft boundaries in images

 Pattern recognition: Clustering ambiguous or noisy data points

8. Conclusion

Rough K-Means Clustering extends traditional K-Means by incorporating lower and upper
approximations using Rough Set Theory.

 Captures uncertainty in cluster membership

Expectation Maximization (EM)-Based Clustering

1. Introduction

Expectation Maximization (EM)-Based Clustering is a probabilistic clustering technique used to

assign data points to clusters based on likelihood.

 EM clustering assumes that data points are generated from a mixture of probability
distributions (e.g., Gaussian).

 Each point has a probability of belonging to each cluster, making it a soft clustering
method.

 Widely used in pattern recognition, image processing, and machine learning.

Applications:

 Customer segmentation

 Image segmentation

 Anomaly detection

 Natural language processing (topic modeling)

2. Definition

EM clustering models data as a mixture of 𝑘distributions and aims to maximize the likelihood of
the observed data:
𝑛
𝑘

𝐿(𝜃) = ∏ ∑ 𝜋𝑖 𝑃(𝑥𝑗 ∣ 𝜃𝑖 )
𝑖=1
𝑗=1

Where:

 𝑥𝑗 → Data point
  𝑘→ Number of clusters

 𝜋𝑖 → Mixing proportion for cluster 𝑖

 𝜃𝑖 → Parameters of the 𝑖-th distribution (mean, covariance, etc.)

 𝑃(𝑥𝑗 ∣ 𝜃𝑖 )→ Probability density of point 𝑥𝑗 under cluster 𝑖

Goal: Estimate cluster parameters that maximize the likelihood of the data.

4. Working of EM-Based Clustering

1. Initialize cluster parameters (𝜃𝑖 ) and mixing proportions (𝜋𝑖 ) randomly.

2. Expectation Step (E-step):

o Compute probability of each data point belonging to each cluster:

𝜋𝑖 𝑃(𝑥𝑗 ∣ 𝜃𝑖 )
𝛾𝑖𝑗 = 𝑘
∑𝑙=1 𝜋𝑙 𝑃(𝑥𝑗 ∣ 𝜃𝑙 )

Where 𝛾𝑖𝑗 is the responsibility of cluster 𝑖for point 𝑥𝑗 .

3. Maximization Step (M-step):

o Update cluster parameters (𝜃𝑖 ) and mixing proportions (𝜋𝑖 ) based on probabilities:
𝑛 𝑛
∑ 𝛾𝑖𝑗 𝑥𝑗 ∑ 𝛾𝑖𝑗
𝑗=1 𝑗=1
𝜇𝑖 = 𝑛 , 𝜋𝑖 =
𝑛
∑ 𝛾𝑖𝑗
𝑗=1

4. Repeat E-step and M-step until convergence (changes in likelihood are small).
 5. Assign points to clusters based on highest probability.

4. Example

Suppose we have 5 points and 2 clusters:

Point Cluster 1 Probability Cluster 2 Probability

A 0.8 0.2

B 0.4 0.6

C 0.7 0.3

D 0.3 0.7

E 0.5 0.5

 Points A and C mostly belong to Cluster 1

 Points B and D mostly belong to Cluster 2

 Point E is ambiguous → soft assignment

5. Advantages

 Handles overlapping clusters using probabilities

 Supports complex distributions (e.g., Gaussian mixtures)

 Provides soft clustering, not hard assignments

 Can model real-world uncertain data effectively

6. Disadvantages

 Requires predefining number of clusters 𝑘

 Sensitive to initialization of parameters

 Can converge to local maxima instead of global maximum

 Computationally more intensive than K-Means

7. Applications

 Image processing: Segmenting overlapping objects

  Customer segmentation: Soft assignment to multiple categories

 Anomaly detection: Detecting abnormal behavior probabilistically

 Natural language processing: Topic modeling in text data

8. Conclusion

Expectation Maximization-Based Clustering is a probabilistic soft clustering technique that

assigns data points to clusters based on likelihood and probability.

 Handles overlapping or ambiguous clusters better than hard clustering

 Forms the basis for Gaussian Mixture Models (GMMs)

 Widely used in data mining, machine learning, and pattern recognition

Spectral Clustering

1. Introduction

Spectral Clustering is a graph-based clustering technique that uses the eigenvalues (spectrum)
of similarity matrices to perform clustering.

 It works well for complex cluster shapes, including non-convex clusters, which traditional
algorithms like K-Means may fail to detect.
 Data points are represented as nodes in a graph, with edges weighted by similarity.

Applications:

 Image segmentation

 Social network analysis

 Document clustering
 Pattern recognition in complex datasets
2. Definition

Spectral clustering aims to partition a graph 𝐺 = (𝑉, 𝐸)into clusters such that similar points are in
the same cluster.

 Build a similarity matrix 𝑊representing pairwise similarity between points.

 Compute the graph Laplacian 𝐿 = 𝐷 − 𝑊, where 𝐷is the degree matrix.

 Perform eigen decomposition of 𝐿to extract key features (eigenvectors).

 Apply K-Means or other clustering on these eigenvectors to get final clusters.

3. Working of Spectral Clustering

1. Construct similarity graph: Connect data points based on distance or similarity.

o Examples: Fully connected, k-nearest neighbors, or epsilon neighborhood.

2. Compute similarity matrix 𝑊:

o 𝑊𝑖𝑗 = similarity(𝑥𝑖 , 𝑥𝑗 )

3. Compute Laplacian matrix 𝐿:

o 𝐿 = 𝐷 − 𝑊, where 𝐷is diagonal with 𝐷𝑖𝑖 = ∑ 𝑊𝑖𝑗

𝑗

4. Eigen decomposition:
 o Extract first 𝑘eigenvectors corresponding to smallest eigenvalues

5. Clustering in reduced space:

o Treat rows of eigenvectors as features and apply K-Means or other clustering methods

6. Output:

o Assign clusters based on K-Means in spectral space

4. Example

Suppose 8 points forming two crescent shapes:

 Traditional K-Means fails because clusters are non-convex

 Spectral Clustering uses similarity graph → Laplacian → eigenvectors → K-Means

 Successfully separates two crescent-shaped clusters

5. Advantages

 Can detect non-convex and complex-shaped clusters

 Works for overlapping clusters with proper similarity measure

 Does not assume clusters are spherical like K-Means

 Flexible due to graph representation

6. Disadvantages

 Computationally expensive for large datasets (eigen decomposition)

 Requires choosing similarity measure carefully

 Sensitive to graph construction parameters (k in k-NN, epsilon)

 Number of clusters 𝑘must be specified

7. Applications

 Image segmentation: Separating objects in complex images

 Social network analysis: Detecting communities

 Text/document clustering: Grouping similar documents

 Biology: Gene expression clustering

8. Conclusion

Spectral Clustering is a graph-based method capable of detecting non-convex and complex

cluster structures.
 Uses similarity graph and eigen decomposition to project data into a lower-dimensional
space

 Combines graph theory and clustering for better performance on complex datasets

 A powerful alternative to K-Means when clusters are not linearly separable