Programming 7 - Clustering

working environment :                                                               This work's Github

OS: Windows 11 home

CPU : intel i9-13900k 

GPU : Nvidia RTX 4090

Python Version : 3.12.2

Development environment: jupyter notebook.

Typical cluster models include:

• Connectivity models: for example, hierarchical clustering builds models based on distance connectivity.

• Centroid models: for example, the k-means algorithm represents each cluster by a single mean vector.

• Distribution models: clusters are modeled using statistical distributions, such as multivariate normal distributions used by the expectation-maximization algorithm.

• Density models: for example, DBSCAN and OPTICS defines clusters as connected dense regions in the data space.

• Subspace models: in biclustering (also known as co-clustering or two-mode-clustering), clusters are modeled with both cluster members and relevant attributes.

• Group models: some algorithms do not provide a refined model for their results and just provide the grouping information.

• Graph-based models: a clique, that is, a subset of nodes in a graph such that every two nodes in the subset are connected by an edge can be considered as a prototypical form of cluster. Relaxations of the complete connectivity requirement (a fraction of the edges can be missing) are known as quasi-cliques, as in the HCS clustering algorithm.

• Signed graph models: Every path in a signed graph has a sign from the product of the signs on the edges. Under the assumptions of balance theory, edges may change sign and result in a bifurcated graph. The weaker "clusterability axiom" (no cycle has exactly one negative edge) yields results with more than two clusters, or subgraphs with only positive edges.[6]

• Neural models: the most well-known unsupervised neural network is the self-organizing map and these models can usually be characterized as similar to one or more of the above models, and including subspace models when neural networks implement a form of Principal Component Analysis or Independent Component Analysis.

A "clustering" is essentially a set of such clusters, usually containing all objects in the data set. Additionally, it may specify the relationship of the clusters to each other, for example, a hierarchy of clusters embedded in each other. Clusterings can be roughly distinguished as:

• Hard clustering: each object belongs to a cluster or not

• Soft clustering (also: fuzzy clustering): each object belongs to each cluster to a certain degree (for example, a likelihood of belonging to the cluster)

There are also finer distinctions possible, for example:

• Strict partitioning clustering: each object belongs to exactly one cluster

• Strict partitioning clustering with outliers: objects can also belong to no cluster; in which case they are considered outliers

• Overlapping clustering (also: alternative clustering, multi-view clustering): objects may belong to more than one cluster; usually involving hard clusters

• Hierarchical clustering: objects that belong to a child cluster also belong to the parent cluster

• Subspace clustering: while an overlapping clustering, within a uniquely defined subspace, clusters are not expected to overlap [3]

In this chapter we introduce 4 algorithms

I.k-means clustering [4]

k-means clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster centers or cluster centroid), serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells. k-means clustering minimizes within-cluster variances (squared Euclidean distances), but not regular Euclidean distances, which would be the more difficult Weber problem: the mean optimizes squared errors, whereas only the geometric median minimizes Euclidean distances. For instance, better Euclidean solutions can be found using k-medians and k-medoids. 

Description

Given a set of observations (x1, x2, ..., xn), where each observation is a 𝑑-dimensional real vector, k-means clustering aims to partition the n observations into k (≤ n) sets S = {S1, S2, ..., Sk} so as to minimize the within-cluster sum of squares (WCSS) (i.e. variance). Formally, the objective is to find: 

where μi is the mean (also called centroid) of points in 𝑆𝑖, i.e 

|𝑆𝑖| is the size of 𝑆𝑖, and ‖⋅‖ is the usual L2 norm . This is equivalent to minimizing the pairwise squared deviations of points in the same cluster: 

The equivalence can be deduced from identity |𝑆𝑖|∑𝑥∈𝑆𝑖‖𝑥−𝜇𝑖‖^2 = 1/2 ∑𝑥,𝑦∈𝑆𝑖‖𝑥−𝑦‖^2. Since the total variance is constant, this is equivalent to maximizing the sum of squared deviations between points in different clusters (between-cluster sum of squares, BCSS).[1] This deterministic relationship is also related to the law of total variance in probability theory. 

In scikit-learn it provide the function name sklearn.cluster.KMeans : [5]

• class sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd'), K-Means clustering.

There are some important parameters :  

1.n_clustersint, default=8 : The number of clusters to form as well as the number of centroids to generate.

For an example of how to choose an optimal value for n_clusters refer to Selecting the number of clusters with silhouette analysis on KMeans clustering.

2.n_init‘auto’ or int, default=’auto’: Number of times the k-means algorithm is run with different centroid seeds. The final results is the best output of n_init consecutive runs in terms of inertia. Several runs are recommended for sparse high-dimensional problems (see Clustering sparse data with k-means).

When n_init='auto', the number of runs depends on the value of init: 10 if using init='random' or init is a callable; 1 if using init='k-means++' or init is an array-like.New in version 1.2: Added ‘auto’ option for n_init.

3.max_iterint, default=300 : Maximum number of iterations of the k-means algorithm for a single run.

4.algorithm{“lloyd”, “elkan”}, default=”lloyd”: K-means algorithm to use. The classical EM-style algorithm is "lloyd". The "elkan" variation can be more efficient on some datasets with well-defined clusters, by using the triangle inequality. However it’s more memory intensive due to the allocation of an extra array of shape (n_samples, n_clusters).

And some commonly used method:

1. fit(X[, y, sample_weight]) : Compute k-means clustering.

2. get_params([deep]) : Get parameters for this estimator.

3. predict(X[, sample_weight]) : Predict the closest cluster each sample in X belongs to.

4. score(X[, y, sample_weight]) : Opposite of the value of X on the K-means objective.

II. Mean shift [6]

Mean shift is a non-parametric feature-space mathematical analysis technique for locating the maxima of a density function, a so-called mode-seeking algorithm.[1] Application domains include cluster analysis in computer vision and image processing.[2] 

Mean shift is a procedure for locating the maxima—the modes—of a density function given discrete data sampled from that function.[1] This is an iterative method, and we start with an initial estimate 𝑥. Let a kernel function 𝐾(𝑥𝑖−𝑥) be given. This function determines the weight of nearby points for re-estimation of the mean. Typically a Gaussian kernel on the distance to the current estimate is used, 𝐾(𝑥𝑖−𝑥)=exp(−𝑐||𝑥𝑖−𝑥||^2). The weighted mean of the density in the window determined by 𝐾 is 

where 𝑁(𝑥) is the neighborhood of 𝑥, a set of points for which 𝐾(𝑥𝑖−𝑥)≠0 

The difference 𝑚(𝑥)−𝑥 is called mean shift in Fukunaga and Hostetler.[3] The mean-shift algorithm now sets 𝑥←𝑚(𝑥), and repeats the estimation until 𝑚(𝑥) converges.

Although the mean shift algorithm has been widely used in many applications, a rigid proof for the convergence of the algorithm using a general kernel in a high dimensional space is still not known.[5] Aliyari Ghassabeh showed the convergence of the mean shift algorithm in one dimension with a differentiable, convex, and strictly decreasing profile function.[6] However, the one-dimensional case has limited real world applications. Also, the convergence of the algorithm in higher dimensions with a finite number of the stationary (or isolated) points has been proved.[5][7] However, sufficient conditions for a general kernel function to have finite stationary (or isolated) points have not been provided.

Gaussian Mean-Shift is an Expectation–maximization algorithm.[8]

Details

Let data be a finite set 𝑆 embedded in the 𝑛-dimensional Euclidean space, 𝑋. Let 𝐾 be a flat kernel that is the characteristic function of the 𝜆-ball in 𝑋, 

In each iteration of the algorithm, 𝑠←𝑚(𝑠) is performed for all 𝑠∈𝑆 simultaneously. The first question, then, is how to estimate the density function given a sparse set of samples. One of the simplest approaches is to just smooth the data, e.g., by convolving it with a fixed kernel of width ℎ, 

In scikit-learn it provide the function name sklearn.cluster.MeanShift [7]

• class sklearn.cluster.MeanShift(*, bandwidth=None, seeds=None, bin_seeding=False, min_bin_freq=1, cluster_all=True, n_jobs=None, max_iter=300) Mean shift clustering using a flat kernel. Mean shift clustering aims to discover “blobs” in a smooth density of samples. It is a centroid-based algorithm, which works by updating candidates for centroids to be the mean of the points within a given region. These candidates are then filtered in a post-processing stage to eliminate near-duplicates to form the final set of centroids. Seeding is performed using a binning technique for scalability.

There are some important parameters :   

1. bandwidthfloat, default=None : Bandwidth used in the flat kernel.If not given, the bandwidth is estimated using sklearn.cluster.estimate_bandwidth; see the documentation for that function for hints on scalability (see also the Notes, below).

2. seedsarray-like of shape (n_samples, n_features), default=None : Seeds used to initialize kernels. If not set, the seeds are calculated by clustering.get_bin_seeds with bandwidth as the grid size and default values for other parameters.

3. min_bin_freqint, default=1 : To speed up the algorithm, accept only those bins with at least min_bin_freq points as seeds.

4. max_iterint, default=300 : Maximum number of iterations, per seed point before the clustering operation terminates (for that seed point), if has not converged yet.

And some commonly used method :  

1. fit(X[, y]) : Perform clustering.

2. predict(X) : Predict the closest cluster each sample in X belongs to.

III. DBSCAN [8]

Density-based spatial clustering of applications with noise (DBSCAN) is a data clustering algorithm proposed by Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu in 1996.[1] It is a density-based clustering non-parametric algorithm: given a set of points in some space, it groups together points that are closely packed (points with many nearby neighbors), and marks as outliers points that lie alone in low-density regions (those whose nearest neighbors are too far away). DBSCAN is one of the most common, and most commonly cited, clustering algorithms.[2] 

Abstract algorithm

The DBSCAN algorithm can be abstracted into the following steps:[4]

1. Find the points in the ε (eps) neighborhood of every point, and identify the core points with more than minPts neighbors.

2. Find the connected components of core points on the neighbor graph, ignoring all non-core points.

3. Assign each non-core point to a nearby cluster if the cluster is an ε (eps) neighbor, otherwise assign it to noise.

A naive implementation of this requires storing the neighborhoods in step 1, thus requiring substantial memory. The original DBSCAN algorithm does not require this by performing these steps for one point at a time.

In scikit-learn it provide the function name sklearn.cluster.DBSCAN [9]

• class sklearn.cluster.DBSCAN(eps=0.5, *, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=None) Perform DBSCAN clustering from vector array or distance matrix. DBSCAN - Density-Based Spatial Clustering of Applications with Noise. Finds core samples of high density and expands clusters from them. Good for data which contains clusters of similar density. The worst case memory complexity of DBSCAN is O(n^2), which can occur when the eps param is large and min_samples is low.

There are some important parameters :   

1. epsfloat, default=0.5 : The maximum distance between two samples for one to be considered as in the neighborhood of the other. This is not a maximum bound on the distances of points within a cluster. This is the most important DBSCAN parameter to choose appropriately for your data set and distance function.

2. min_samplesint, default=5 : The number of samples (or total weight) in a neighborhood for a point to be considered as a core point. This includes the point itself. If min_samples is set to a higher value, DBSCAN will find denser clusters, whereas if it is set to a lower value, the found clusters will be more sparse.

3. leaf_sizeint, default=30 : Leaf size passed to BallTree or cKDTree. This can affect the speed of the construction and query, as well as the memory required to store the tree. The optimal value depends on the nature of the problem.

And some commonly used method :  

1. fit(X[, y, sample_weight]) : Perform DBSCAN clustering from features, or distance matrix.

2. get_params([deep]) : Get parameters for this estimator.

3. set_params(**params) : Set the parameters of this estimator.

IV. Hierarchical clustering [10]

In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two categories:

• Agglomerative: This is a "bottom-up" approach: Each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.

• Divisive: This is a "top-down" approach: All observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering[1] are usually presented in a dendrogram.

Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances. On the other hand, except for the special case of single-linkage distance, none of the algorithms (except exhaustive search in 𝑂(2^𝑛)) can be guaranteed to find the optimum solution.

Cluster Linkage

In order to decide which clusters should be combined (for agglomerative), or where a cluster should be split (for divisive), a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate distance d, such as the Euclidean distance, between single observations of the data set, and a linkage criterion, which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets. The choice of metric as well as linkage can have a major impact on the result of the clustering, where the lower level metric determines which objects are most similar, whereas the linkage criterion influences the shape of the clusters. For example, complete-linkage tends to produce more spherical clusters than single-linkage.

The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations.

Some commonly used linkage criteria between two sets of observations A and B and a distance d are

Hierarchical clustering basic operation process can be divided into two types: Agglomerative Hierarchical Clustering and Divisive Hierarchical Clustering.

Agglomerative Hierarchical Clustering

This is a bottom-up approach:

1. Initialization: Treat each data point as an individual cluster, resulting in n clusters.

2. Calculate Distance: Compute the distance or similarity between all clusters, typically using Euclidean distance.

3. Merge Clusters: Find the two clusters that are closest to each other and merge them into a new cluster.

4. Update Distance Matrix: Recalculate the distances between the new cluster and all other clusters.

5. Repeat Steps 3 and 4: Continue this process until all data points are merged into a single cluster, or the desired number of clusters is reached.

Divisive Hierarchical Clustering

This is a top-down approach:

1. Initialization: Treat all data points as a single cluster.

2. Split Cluster: Choose a cluster to split into two sub-clusters, often using a method like K-means.

3. Calculate Split Point: Determine the best split point based on the splitting method and distance calculation.

4. Repeat Steps 2 and 3: Continue splitting each cluster until every data point becomes a single cluster, or the desired number of clusters is reached.

Distance Calculation Methods

Calculating distance or similarity is crucial in these steps. Common methods include:

• Euclidean Distance

• Manhattan Distance

• Cosine Similarity

Cluster Merging Criteria

In agglomerative hierarchical clustering, the distance between clusters can be defined using several criteria:

• Single Linkage: Distance between the closest points of two clusters.

• Complete Linkage: Distance between the farthest points of two clusters.

• Average Linkage: Average distance between all points in the two clusters.

• Centroid Linkage: Distance between the centroids of the two clusters.

Dendrogram

The final result can be represented using a dendrogram, which is a hierarchical tree-like diagram showing how data points are merged or split into different clusters.

The advantage of hierarchical clustering is its hierarchical structure, which makes the results easy to interpret. However, the disadvantage is its high computational complexity, especially when dealing with large datasets.

In scikit-learn it provide the model name sklearn.cluster.AgglomerativeClustering [11]

• class sklearn.cluster.AgglomerativeClustering(n_clusters=2, *, metric='euclidean', memory=None, connectivity=None, compute_full_tree='auto', linkage='ward', distance_threshold=None, compute_distances=False) Agglomerative Clustering. Recursively merges pair of clusters of sample data; uses linkage distance.

There are some important parameters :

1. n_clustersint or None, default=2 : The number of clusters to find. It must be None if distance_threshold is not None.

2. metricstr or callable, default=”euclidean” : Metric used to compute the linkage. Can be “euclidean”, “l1”, “l2”, “manhattan”, “cosine”, or “precomputed”. If linkage is “ward”, only “euclidean” is accepted. If “precomputed”, a distance matrix is needed as input for the fit method.

3. compute_full_tree‘auto’ or bool, default=’auto’ : Stop early the construction of the tree at n_clusters. This is useful to decrease computation time if the number of clusters is not small compared to the number of samples. This option is useful only when specifying a connectivity matrix. Note also that when varying the number of clusters and using caching, it may be advantageous to compute the full tree. It must be True if distance_threshold is not None. By default compute_full_tree is “auto”, which is equivalent to True when distance_threshold is not None or that n_clusters is inferior to the maximum between 100 or 0.02 * n_samples. Otherwise, “auto” is equivalent to False.

4. distance_thresholdfloat, default=None : The linkage distance threshold at or above which clusters will not be merged. If not None, n_clusters must be None and compute_full_tree must be True.

5. compute_distancesbool, default=False : Computes distances between clusters even if distance_threshold is not used. This can be used to make dendrogram visualization, but introduces a computational and memory overhead.

And some commonly used method :  

1. fit(X[, y]) : Fit the hierarchical clustering from features, or distance matrix.

2. get_params([deep]) : Get parameters for this estimator.

3. set_params(**params) : Set the parameters of this estimator.

Discussion

K-means clustering is one of the most common clustering techniques. In k-means clustering, the algorithm attempts to group observations into k groups, with each group having roughly equal variance. The number of groups, k, is specified by the user as a hyperparameter. Specifically, in k-means: 

1. k cluster “center” points are created at random locations.

2. For each observation:

   1. The distance between each observation and the k center points is calculated.

   2. The observation is assigned to the cluster of the nearest center point.

3. The center points are moved to the means (i.e., centers) of their respective clusters.

4. Steps 2 and 3 are repeated until no observation changes in cluster membership.

At this point the algorithm is considered converged and stops.

It is important to note three things about k-means. First, k-means clustering assumes the clusters are convex shaped (e.g., a circle, a sphere). Second, all features are equally scaled. In our solution, we standardized the features to meet this assumption. Third, the groups are balanced (i.e., have roughly the same number of observations). If we suspect that we cannot meet these assumptions, we might try other clustering approaches.

In scikit-learn, k-means clustering is implemented in the KMeans class. The most important parameter is n_clusters, which sets the number of clusters k. In some situations, the nature of the data will determine the value for k (e.g., data on a school’s students will have one cluster per grade), but often we don’t know the number of clusters. In these cases, we will want to select k based on using some criteria. For example, silhouette coefficients (see Recipe 11.9) measure the similarity within clusters compared with the similarity between clusters. Furthermore, because k-means clustering is computationally expensive, we might want to take advantage of all the cores on our computer. We can do this by setting n_jobs=-1.

Discussion

Mini-batch k-means works similarly to the k-means algorithm discussed in Recipe 19.1. Without going into too much detail, the difference is that in mini-batch k-means the most computationally costly step is conducted on only a random sample of observations as opposed to all observations. This approach can significantly reduce the time required for the algorithm to find convergence (i.e., fit the data) with only a small cost in quality.

MiniBatchKMeans works similarly to KMeans, with one significant difference: the batch_size parameter. batch_size controls the number of randomly selected observations in each batch. The larger the size of the batch, the more computationally costly the training process.

Discussion

One of the disadvantages of k-means clustering we discussed previously is that we needed to set the number of clusters, k, prior to training, and the method made assumptions about the shape of the clusters. One clustering algorithm without these limitations is mean shift.

Mean shift is a simple concept, but it’s somewhat difficult to explain. Therefore, an analogy might be the best approach. Imagine a very foggy football field (i.e., a two-dimensional feature space) with 100 people standing on it (i.e., our observations). Because it is foggy, a person can see only a short distance. Every minute each person looks around and takes a step in the direction of the most people they can see. As time goes on, people start to group together as they repeatedly take steps toward larger and larger crowds. The end result is clusters of people around the field. People are assigned to the clusters in which they end up.

scikit-learn’s actual implementation of mean shift, MeanShift, is more complex but follows the same basic logic. MeanShift has two important parameters we should be aware of. First, bandwidth sets the radius of the area (i.e., kernel) an observation uses to determine the direction to shift. In our analogy, bandwidth is how far a person can see through the fog. We can set this parameter manually, but by default a reasonable bandwidth is estimated automatically (with a significant increase in computational cost). Second, sometimes in mean shift there are no other observations within an observation’s kernel. That is, a person on our football field cannot see a single other person. By default, MeanShift assigns all these “orphan” observations to the kernel of the nearest observation. However, if we want to leave out these orphans, we can set cluster_all=False, wherein orphan observations are given the label of -1.

Discussion

DBSCAN is motivated by the idea that clusters will be areas where many observations are densely packed together and makes no assumptions of cluster shape. Specifically, in DBSCAN:

1. A random observation, xi, is chosen.

2. If xi has a minimum number of close neighbors, we consider it to be part of a cluster.

3. Step 2 is repeated recursively for all of xi’s neighbors, then neighbor’s neighbor, and so on. These are the cluster’s core observations.

4. Once step 3 runs out of nearby observations, a new random point is chosen (i.e., restart at step 1).

Once this is complete, we have a set of core observations for a number of clusters. Finally, any observation close to a cluster but not a core sample is considered part of a cluster, while any observation not close to the cluster is labeled an outlier.

DBSCAN has three main parameters to set:

1. eps : The maximum distance from an observation for another observation to be considered its neighbor.

2. min_samples : The minimum number of observations less than eps distance from an observation for it to be considered a core observation.

3. metric : The distance metric used by eps—for example, minkowski or euclidean (note that if Minkowski distance is used, the parameter p can be used to set the power of the Minkowski metric).

Discussion

Agglomerative clustering is a powerful, flexible hierarchical clustering algorithm. In agglomerative clustering, all observations start as their own clusters. Next, clusters meeting some criteria are merged. This process is repeated, growing clusters until some end point is reached. In scikit-learn, AgglomerativeClustering uses the linkage parameter to determine the merging strategy to minimize:

• Variance of merged clusters (ward)

• Average distance between observations from pairs of clusters (average)

• Maximum distance between observations from pairs of clusters (complete)

Two other parameters are useful to know. First, the affinity parameter determines the distance metric used for linkage (minkowski, euclidean, etc.). Second, n_clusters sets the number of clusters the clustering algorithm will attempt to find. That is, clusters are successively merged until only n_clusters remain.

First introduce Olivetti faces data-set 

This dataset contains a set of face images taken between April 1992 and April 1994 at AT&T Laboratories Cambridge. The sklearn.datasets.fetch_olivetti_faces function is the data fetching / caching function that downloads the data archive from AT&T.

As described on the original website:

There are ten different images of each of 40 distinct subjects. For some subjects, the images were taken at different times, varying the lighting, facial expressions (open / closed eyes, smiling / not smiling) and facial details (glasses / no glasses). All the images were taken against a dark homogeneous background with the subjects in an upright, frontal position (with tolerance for some side movement). 

Data Set Characteristics:

• Classes : 40

• Samples total : 400

• Dimensionality : 4096

• Features : real, between 0 and 1

The image is quantized to 256 grey levels and stored as unsigned 8-bit integers; the loader will convert these to floating point values on the interval [0, 1], which are easier to work with for many algorithms.

The “target” for this database is an integer from 0 to 39 indicating the identity of the person pictured; however, with only 10 examples per class, this relatively small dataset is more interesting from an unsupervised or semi-supervised perspective.

The original dataset consisted of 92 x 112, while the version available here consists of 64x64 images.

When using these images, please give credit to AT&T Laboratories Cambridge. [12]

Below we have tried different clusters to get the better accuracy, after we experiment we can get the best n_clusters = 185

and its training acc = 1.0, test scc = 0.97, Why there are 40 different people in the data set, the expected number of cluster K is 40, but we got 185. This may because even the same people looks very different in the data set.

Next we change the model to mean shift, and test different bandwidth , below table (P7 different bandwidth) shows the training and test accuracy . Why we change bandwidth from 2 to 50000? first mean shift takes a long time to train make my cpu hot! next we have test 2 5 and 0.1 sequencely, but we also get the same training and test acc, that is why we jump so fast. 

Then we change the model to DBSCAN, below table(P7 DBSCAN) show the experiment we have tried. eps=0.1, min_samples=1 get the accuracy training =1.0, testing =1.0.

At the end we try the Hierarchical Merging, below table (P7 AgglomerativeClustering) shows the paremeters we have tried, we get 100% test accuracy when we set n_clusters=100. That's seems good.

Now Lets change the dataset to 20newsgroups datasets.

The 20 newsgroups dataset comprises around 18000 newsgroups posts on 20 topics split in two subsets: one for training (or development) and the other one for testing (or for performance evaluation). The split between the train and test set is based upon a messages posted before and after a specific date.

This module contains two loaders. The first one, sklearn.datasets.fetch_20newsgroups, returns a list of the raw texts that can be fed to text feature extractors such as CountVectorizer with custom parameters so as to extract feature vectors. The second one, sklearn.datasets.fetch_20newsgroups_vectorized, returns ready-to-use features, i.e., it is not necessary to use a feature extractor. [13]

Data Set Characteristics:

• Classes : 20

• Samples total : 18846

• Dimensionality : 1

• Features : text

Data Considerations

The Cleveland Indians is a major league baseball team based in Cleveland, Ohio, USA. In December 2020, it was reported that “After several months of discussion sparked by the death of George Floyd and a national reckoning over race and colonialism, the Cleveland Indians have decided to change their name.” Team owner Paul Dolan “did make it clear that the team will not make its informal nickname – the Tribe – its new team name.” “It’s not going to be a half-step away from the Indians,” Dolan said.”We will not have a Native American-themed name.”

We follow the tips from [14] to implement. and use 

• homogeneity, which quantifies how much clusters contain only members of a single class;

• completeness, which quantifies how much members of a given class are assigned to the same clusters;

• V-measure, the harmonic mean of completeness and homogeneity;

The V-measure is the harmonic mean between homogeneity and completeness:

v = (1 + beta) * homogeneity * completeness

     / (beta * homogeneity + completeness)

to quantifying the quality of clustering results.

Below table shows the parameters we test. We can see that when the n_clusters = 240 we have the highest V-measure = 0.31, and it is not keep increasing.

Next we try to change the model to mean shift. But we failed, because this dataset are too big than we get the MemoryError: Unable to allocate 2.82 GiB for an array with shape (15670, 24164) and data type float64. Then we use PBA try to decrease the dimensionality. And the below is what we get. I think this result cannot get anything helpful, so i give up with this method.

Next we try to change the model to mean shift. But we failed, because this dataset are too big than we get the MemoryError: Unable to allocate 2.82 GiB for an array with shape (15670, 24164) and data type float64. Then we use PBA try to decrease the dimensionality. And the below is what we get. I think this result cannot get anything helpful, so i give up with this method.

Then we change the model to DBSCAN. Below table (P7 20newsgroup DBSCAN) show the paremeters we tested, we get V-measure = 0.46, but it didn't change too much when we are tuning, i think it is because this dataset are one dimension is not fit to DBSCAN.

At the end we try the AgglomerativeClustering. seems like this method also not work well. 

Here are a few reasons why AgglomerativeClustering and MeanShift might not work well on the 20 Newsgroups dataset:

1. High Dimensionality: The 20 Newsgroups dataset consists of textual data, which is typically represented as high-dimensional sparse vectors (e.g., using TF-IDF or word embeddings). AgglomerativeClustering algorithms are known to suffer from the curse of dimensionality, as the distance or similarity measures become less reliable and discriminative in high-dimensional spaces.

2. Large Dataset Size: AgglomerativeClustering algorithms have a time complexity of O(n^2) or O(n^3), depending on the linkage method used, where n is the number of data points. This makes them computationally expensive for large datasets like the 20 Newsgroups, which contains thousands of documents. The quadratic or cubic time complexity can make the clustering process extremely slow or even infeasible for large datasets.

3. Sensitivity to Noise and Outliers: AgglomerativeClustering algorithms are sensitive to noise and outliers in the data, as they rely on pairwise distances or similarities to merge or split clusters. Text data often contains noise, such as misspellings, irrelevant words, or outlier documents, which can negatively impact the clustering performance.

4. Lack of Flat Geometry: AgglomerativeClustering works well when the clusters have a flat geometry, meaning that the data points within a cluster are roughly equidistant from each other. However, text data often exhibits a more complex, non-flat geometry, where documents within a cluster can have varying degrees of similarity or dissimilarity.

5. Difficulty in Determining the Number of Clusters: AgglomerativeClustering requires specifying the number of clusters in advance or using a stopping criterion based on a distance threshold. Determining the optimal number of clusters for text data can be challenging, as the true number of topics or categories may not be known a priori.

6. Lack of Interpretability: While AgglomerativeClustering can group similar documents together, it may not provide interpretable insights into the underlying topics or themes of the clusters, which is often desirable for text data analysis.

Instead of AgglomerativeClustering, other unsupervised learning methods like topic modeling (e.g., Latent Dirichlet Allocation, Non-negative Matrix Factorization), document clustering using algorithms like K-Means or DBSCAN, or dimensionality reduction techniques (e.g., Truncated SVD, t-SNE) are often preferred for text data analysis tasks, including the 20 Newsgroups dataset.

These methods can better handle high-dimensional sparse data, are more scalable to large datasets, and can provide more interpretable results by capturing the underlying topics or themes in the text data. However, the choice of the most suitable method ultimately depends on the specific goals and requirements of the analysis, as well as the characteristics of the dataset.