K-Means Clustering

Clustering in an unsupurvised machine learning technique that aims to group data into clusters within the input space.

Clustering is to discover hidden structures in the data without any prior knowledge of the groupings. Clustering algorithms typically rely on a distance or similaity metric to measure how close or similar data points are in the feature space.

K-means assumes there are $k$ clusters among $N$ input samples and each data point is close to its cluster center (the mean point of the cluster).

Process

1. First step is initialization where the $k$ centroids are randomly initialized within the Euclidean space
2. next we iteratively alternate between assignment and refitting

assignment: assign each data point to its closest cluster
refitting: move the centroid to the center of the new cluster

Code

We can run K-Means directly on the TF-IDF matrix, with 5 different random seeds:

from sklearn.cluster import KMeans
 
for seed in range(5):
    kmeans = KMeans(
        n_clusters=2,
        max_iter=100,
        n_init=1,
        random_state=seed,
    ).fit(train_review_tfidf)
    cluster_ids, cluster_sizes = np.unique(kmeans.labels_, return_counts=True)
    print(f"Number of elements assigned to each cluster: {cluster_sizes}")
print()

Output:

Number of elements assigned to each cluster: [5542 1958]
Number of elements assigned to each cluster: [2079 5421]
Number of elements assigned to each cluster: [2081 5419]
Number of elements assigned to each cluster: [5433 2067]
Number of elements assigned to each cluster: [2069 5431]

Argument	Meaning
n_clusters	the value of $k$, so the number of clusters to find
max_iter	the cap on assignment and refitting rounds for a single run
n_init	how many times the whole algorithm restarts from new random centroids, keeping the best result
random_state	fixes the random initialisation so a run is reproducible

• .fit() performs the clustering, and kmeans.labels_ then holds the cluster number of every document
• np.unique(..., return_counts=True) returns the distinct labels and how many documents carry each one
• kmeans.cluster_centers_ holds the centroid coordinates

Cluster numbers carry no meaning

cluster 0 in one run is cluster 1 in the next, because the labels are assigned by whichever centroid was initialised first. Never treat cluster 0 as a fixed category.

We can also reduces the dimensions before clustering, using LSA:

from sklearn.decomposition import TruncatedSVD
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import Normalizer
 
lsa = make_pipeline(TruncatedSVD(n_components=100), Normalizer(copy=False))
train_review_lsa = lsa.fit_transform(train_review_tfidf)
explained_variance = lsa[0].explained_variance_ratio_.sum()
print(f"Explained variance of the SVD step: {explained_variance * 100:.1f}%")

Explained variance of the SVD step: 11.4%

• TruncatedSVD is used rather than PCA, because the TF-IDF matrix is sparse and PCA centres the data
• Normalizer rescales each row to unit length, which suits the distance measure K-Means uses
• lsa[0] reaches the first step of the pipeline, which is the TruncatedSVD object
• 100 components keep only 11.4 percent of the variance, so most of the information is dropped and the clustering still works

We can clusters the reduced data and then reads the top words per cluster:

kmeans = KMeans(
    n_clusters=2,
    max_iter=100,
    n_init=5,
    random_state=seed,
).fit(train_review_lsa)
 
original_space_centroids = lsa[0].inverse_transform(kmeans.cluster_centers_)
order_centroids = original_space_centroids.argsort()[:, ::-1]
terms = tv.get_feature_names_out()
 
for i in range(2):
    print(f"Cluster {i}: ", end="")
    for ind in order_centroids[i, :10]:
        print(f"{terms[ind]} ", end="")
    print()

Cluster 0: movie bad good like watch make think time really film
Cluster 1: film make like good time story character movie great watch

• the model is now fitted on train_review_lsa rather than the raw TF-IDF matrix, and n_init rises to 5
• inverse_transform maps the 100 dimensional centroids back into the original word space, so each centroid can be read as word weights
• argsort() sorts ascending, so [:, ::-1] reverses each row to put the strongest word first
• terms[ind] converts a column index back into the word it stands for

Reading the result

Both clusters share most of their top words, so this split does not separate positive from negative reviews. Clustering finds whatever structure the distances expose, and it has no access to the sentiment labels.

K-Means forces each point into 1 cluster, and the version that lets a point belong to several is Fuzzy Clustering.