Clustering is a technique used in data science to group together similar data points based on their attributes or features. The aim of clustering is to identify patterns and similarities in large datasets that may not be immediately apparent to the human eye.

In clustering, data points are assigned to clusters based on their similarity to other data points in the same cluster, and dissimilarity to data points in other clusters. There are various algorithms used to perform clustering, such as K-means clustering, hierarchical clustering, and density-based clustering.

Clustering is commonly used in applications such as customer segmentation, anomaly detection, and image processing. By grouping similar data points together, clustering can help to identify trends, patterns, and anomalies in data, and aid decision-making processes.

Clustering is Unsupervised

Clustering is a type of unsupervised machine learning, as it does not require labeled data or a specific target variable. In unsupervised learning, the machine learning algorithm is tasked with identifying patterns and relationships in the data without any prior knowledge of the output or expected result.

Clustering algorithms are used to group similar data points into clusters, based on their attributes or features. The algorithm analyzes the data and identifies patterns and similarities, and then groups data points together based on those patterns.

Unlike supervised learning, there is no predefined output or target variable in clustering. Instead, the algorithm groups data points based on their intrinsic characteristics, and the resulting clusters are used to gain insights and make decisions.

K-means Clustering

In K-means clustering, the "K" refers to the number of clusters to be formed from the data. The algorithm aims to partition a given dataset into K clusters, where K is a predefined number chosen by the user.

The K-means algorithm works by first randomly selecting K data points from the dataset to serve as initial cluster centroids. The remaining data points are then assigned to the nearest centroid based on their distance from it. After all data points have been assigned to clusters, the centroid of each cluster is recalculated as the mean of all the data points assigned to it. This process is repeated until the centroids no longer move significantly, or a maximum number of iterations is reached.

The choice of K is an important factor in K-means clustering, as it determines the number of clusters formed and can greatly impact the results. Choosing the optimal value for K depends on the specific problem and data being analyzed. There are various methods for determining the optimal value of K, such as the elbow method and silhouette method.

Steps involed in K-means clustering

The following are the general steps involved in the K-means algorithm:

Initialization: The user defines the number of clusters K and initializes the centroids randomly.
Assigning data points to clusters: Each data point is assigned to the nearest centroid based on its distance from it. This creates K clusters of data points.
Computing new centroids: The centroid of each cluster is recomputed as the mean of all the data points assigned to it.
Reassigning data points to clusters: Each data point is reassigned to the nearest centroid based on its distance from it. This step may create new or merged clusters.
Repeat steps 3 and 4: The previous steps are repeated until the centroids no longer move significantly, or a maximum number of iterations is reached.
Output: The final output is the K clusters of data points, along with their respective centroids.

The K-means algorithm aims to minimize the within-cluster sum of squares, which is the sum of the squared distances between each data point and its assigned centroid. The algorithm tries to find the optimal cluster centroids that minimize this objective function.

It is worth noting that the K-means algorithm can converge to local optima, meaning that the final clustering results can be different depending on the initial random centroid selection. Therefore, it is recommended to run the algorithm multiple times with different initializations and choose the best clustering results.

Optimal Value for K

Choosing the optimal value for K in K-means clustering is an important step in the algorithm, as it determines the number of clusters formed and can greatly impact the results. Here are some methods to help decide the optimal value for K:

Elbow Method: The elbow method involves plotting the sum of squared distances (or inertia) of the data points to their assigned centroid for different values of K. The optimal value for K is where the decrease in inertia begins to level off, forming an "elbow" in the graph. This point represents the trade-off between a low inertia (smaller K) and a low number of clusters (larger K).
1. For a given dataset, run K-means clustering for a range of K values (e.g., 1 to 10).
2. For each K value, compute the WCSS value, which is the sum of squared distances between each data point and its assigned centroid.
3. Plot the WCSS values against the corresponding K values, creating a line plot.
4. Identify the "elbow" point in the plot, which is the point of inflection where the decrease in WCSS begins to level off.
5. Choose the value of K that corresponds to the elbow point as the optimal number of clusters for the dataset.
The intuition behind the elbow method is that as the number of clusters K increases, the WCSS value generally decreases since the data points are closer to their assigned centroids. However, adding more clusters eventually results in diminishing returns and increased complexity, leading to only a marginal decrease in WCSS. The elbow point represents the optimal trade-off between having enough clusters to capture the structure of the data and minimizing the WCSS value.
```
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import pandas as pd

# Load the dataset
df = pd.read_csv("sample_data.csv")

# Define the range of K values to test
k_values = range(1, 11)

# Fit KMeans models for each K value and compute the sum of squared distances for each model
ssd_values = []
for k in k_values:
    kmeans = KMeans(n_clusters=k, random_state=42)
    kmeans.fit(df)
    ssd_values.append(kmeans.inertia_)

# Plot the elbow curve
plt.plot(k_values, ssd_values, 'bx-')
plt.xlabel('Number of clusters (K)')
plt.ylabel('Sum of squared distances')
plt.title('Elbow Method for Optimal K')
plt.show()
```

Silhouette Method: The silhouette method involves computing the silhouette coefficient for each data point, which measures how similar a data point is to its assigned cluster compared to other clusters. The silhouette coefficient ranges from -1 to 1, with higher values indicating better cluster assignment. The optimal value for K is where the average silhouette coefficient is maximized.

Here's an example Python code that uses the silhouette method to determine the optimal number of clusters (K) in a sample dataset:

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt
import pandas as pd

# Load the dataset
df = pd.read_csv("sample_data.csv")

# Define the range of K values to test
k_values = range(2, 11)

# Compute the silhouette scores for each K value
silhouette_scores = []
for k in k_values:
    kmeans = KMeans(n_clusters=k, random_state=42)
    cluster_labels = kmeans.fit_predict(df)
    silhouette_avg = silhouette_score(df, cluster_labels)
    silhouette_scores.append(silhouette_avg)

# Plot the silhouette scores for each K value
plt.plot(k_values, silhouette_scores, 'bx-')
plt.xlabel('Number of clusters (K)')
plt.ylabel('Silhouette score')
plt.title('Silhouette Method for Optimal K')
plt.show()

optimal_k = np.argmax(silhouette_scores) + 2

Domain Knowledge: In some cases, domain knowledge or prior information about the data may be available to help determine the appropriate value for K. For example, in customer segmentation, a business may already have some idea of the number of customer groups they want to identify.
Experimentation: It is also possible to try different values of K and evaluate the results to determine the optimal value. This approach may be time-consuming, but it can provide insights into the structure of the data and the performance of the algorithm for different values of K.

Overall, the choice of K is problem-dependent and requires a balance between accuracy and computational efficiency. It is recommended to try multiple methods to determine the optimal value for K and choose the one that best suits the problem at hand.

Hierarchical Clustering

Hierarchical clustering is a type of clustering algorithm that builds a hierarchy of clusters by recursively dividing the dataset into smaller and smaller clusters until each data point is assigned to its own cluster. This hierarchy is represented by a dendrogram, which is a tree-like diagram that shows the relationships between the clusters.

There are two main types of hierarchical clustering: agglomerative and divisive. Agglomerative clustering is a bottom-up approach where each data point starts as its own cluster and pairs of clusters are merged together until all the data points belong to a single cluster. Divisive clustering is a top-down approach where all the data points start in a single cluster and the algorithm recursively splits the clusters into smaller and smaller ones.

In hierarchical clustering, the choice of distance metric and linkage method can have a significant impact on the resulting clusters. The distance metric determines how the similarity between two data points is measured, while the linkage method determines how the distance between clusters is calculated. Common distance metrics include Euclidean distance, Manhattan distance, and cosine similarity, while common linkage methods include complete linkage, single linkage, and average linkage.

Hierarchical clustering is commonly used in fields such as biology, ecology, and social sciences to identify clusters or groups in data that have a natural hierarchy or structure. It can also be used for visualization purposes to gain insights into the underlying structure of the data.

Which takes more time? K-Means vs Hierarchical Clustering

In general, hierarchical clustering takes more time than K-means clustering because it involves building a hierarchy of clusters by recursively merging or splitting clusters until a stopping criterion is met.

In agglomerative hierarchical clustering, all pairwise distances between the data points are calculated at the beginning, resulting in a complete distance matrix. Then, at each step, the algorithm must find the closest pair of clusters and merge them, which requires searching through the entire distance matrix. This can be computationally expensive when dealing with large datasets, especially when using a distance metric that involves high-dimensional data.

In contrast, K-means clustering is an iterative algorithm that involves randomly initializing cluster centers and assigning data points to the closest cluster center. Then, the cluster centers are updated based on the mean of the assigned data points, and the assignment step is repeated until convergence is reached. This iterative process is relatively fast and efficient, especially for high-dimensional data.

However, the actual runtime of both algorithms depends on the specific implementation, dataset size, number of clusters, and distance metric used. In some cases, hierarchical clustering may be faster than K-means clustering, especially when dealing with small datasets or when the number of clusters is relatively small.

Code Example of Hierarchical Clustering

import pandas as pd
import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

# Load the text data
data = pd.read_csv("text_data.csv", encoding='utf-8')

# Vectorize the text data
vectorizer = TfidfVectorizer(stop_words='english')
X = vectorizer.fit_transform(data['text'])

# Compute the linkage matrix
Z = linkage(X.toarray(), 'ward')

# Plot the dendrogram
plt.figure(figsize=(10, 5))
dendrogram(Z, leaf_font_size=10)
plt.xlabel('Documents')
plt.ylabel('Distance')
plt.title('Dendrogram')
plt.show()

# Determine the optimal number of clusters
max_d = 1.5 # Maximum distance between merges
clusters = fcluster(Z, max_d, criterion='distance')
num_clusters = len(np.unique(clusters))

print("Optimal number of clusters:", num_clusters)

# Perform hierarchical clustering
clustering = AgglomerativeClustering(n_clusters=num_clusters, linkage='ward')
clustering.fit(X.toarray())

# Print the cluster labels
print(clustering.labels_)

K-means++

K-means++ is an improvement over the K-means clustering algorithm, which is used to partition a dataset into K clusters. The K-means algorithm randomly initializes K cluster centers, which can lead to suboptimal clustering results, particularly when the data is high-dimensional or contains outliers. K-means++ addresses this issue by choosing the initial cluster centers in a more informed manner.

The K-means++ algorithm works by first randomly selecting a single data point as the first cluster center. Then, for each subsequent center, a new data point is selected with probability proportional to its distance from the closest cluster center already chosen. This process continues until K centers have been chosen. Once the initial centers have been chosen, the K-means algorithm proceeds as usual.

K-means++ initialization typically results in better clustering results and faster convergence than random initialization.

K-means++ can be used as a drop-in replacement for the regular K-means algorithm, as they have the same API. You would simply replace the KMeans instantiation with KMeans++:

# Perform K-means clustering with K-means++
n_clusters = 8  # Number of clusters
kmeans = KMeans(n_clusters=n_clusters, init='k-means++', random_state=42)
kmeans.fit(input_ids)

# Get cluster labels
cluster_labels = kmeans.labels_

Clustering Validation

Silhouette score

The Silhouette score is a metric used to evaluate the quality of clustering in unsupervised machine learning. It measures how similar an object is to its own cluster (cohesion) compared to other clusters (separation). The score ranges from -1 to 1, with higher scores indicating better-defined clusters.

The formula for the silhouette score of a data point i is:

where a(i) is the average distance between i and all other points in its cluster, and b(i) is the average distance between i and all points in the nearest cluster (other than its own).

The silhouette score for a cluster is the average silhouette score of all data points in that cluster. The overall silhouette score of a clustering algorithm is the average of the silhouette scores of all clusters.

A score close to 1 indicates well-separated clusters, a score close to 0 indicates overlapping clusters, and a score close to -1 indicates misclassified data points.

DBSCAN

DBSCAN stands for Density-Based Spatial Clustering of Applications with Noise. It is a popular clustering algorithm used in machine learning and data mining. Unlike K-means and hierarchical clustering algorithms, DBSCAN does not require the user to specify the number of clusters. Instead, it groups together points that are close to each other and identifies outliers as noise.

DBSCAN works by defining regions of high density as clusters, and points that are not part of a dense region are considered as noise. It has two important parameters: epsilon and min_samples. Epsilon is the radius of the neighborhood around a point, and min_samples is the minimum number of points required to form a dense region.

The algorithm starts with a random point, and then it finds all the neighboring points within the radius of epsilon. If the number of neighbors is greater than or equal to min_samples, then the point is added to the cluster. The process continues until all points are assigned to clusters or marked as noise.

DBSCAN is particularly useful for clustering data that has non-linear structures and irregular shapes, and for detecting outliers or noise in the data. However, it can be sensitive to the choice of parameters, and the performance of the algorithm can degrade for high-dimensional data.

Epsilon: It is the distance within which we search for neighboring points. It is also known as the radius of the neighborhood.
Min points: It is the minimum number of points that should be present in the Epsilon neighborhood to form a dense region.
Core points: A point is called a core point if it has at least Min Points within its Epsilon neighborhood.
Border points: A point is called a border point if it is not a core point but is present in the Epsilon neighborhood of a core point.
Noise: A point is called a noise point if it is neither a core point nor a border point.

In DBSCAN clustering, we first find the core points, then we expand the clusters by including their neighboring points. The border points are included in the clusters of their corresponding core points. The noise points are not included in any cluster.

from transformers import BertTokenizer, BertModel
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.metrics import silhouette_score

# Load BERT tokenizer
tokenizer = BertTokenizer.from_pretrained('bert-base-uncased')

# Tokenize text data
tokenized_texts = [tokenizer.tokenize(text[0]) for text in filtered_questions]

# Find the maximum length of tokenized texts
max_len = max(len(tokens) for tokens in tokenized_texts)

# Pad tokenized texts to ensure all sequences have the same length
input_ids = [tokenizer.convert_tokens_to_ids(tokens) for tokens in tokenized_texts]
input_ids = np.array([ids + [0] * (max_len - len(ids)) for ids in input_ids])  # Padding with 0s

# Perform DBSCAN clustering
dbscan = DBSCAN(eps=0.5, min_samples=5)
dbscan.fit(input_ids)

# Get cluster labels
cluster_labels = dbscan.labels_

# Get number of clusters
n_clusters = len(set(cluster_labels)) - (1 if -1 in cluster_labels else 0)
print(f"Number of clusters: {n_clusters}")

# Compute Silhouette Score
silhouette_avg = silhouette_score(input_ids, cluster_labels)
print(f"Silhouette Score: {silhouette_avg}")

Animesh Sharma's Blog

Clustering Cookbook