K-Means clustering is a powerful and widely used unsupervised machine learning algorithm for partitioning data into distinct groups, or clusters, based on similarity. Scikit-learn, a popular Python library for machine learning, provides a straightforward implementation of K-Means. A common question that arises when using Scikit-learn’s K-Means is: Is it possible to specify your own distance function using scikit-learn K-Means Clustering? The answer is nuanced. While Scikit-learn’s standard K-Means implementation primarily supports Euclidean distance, there are ways to incorporate custom distance metrics through precomputed distances or alternative clustering algorithms. This flexibility allows you to tailor the clustering process to the specific characteristics of your data, ensuring more accurate and meaningful results. Understanding how to leverage these techniques is crucial for advanced data analysis and model building.

Understanding Scikit-learn’s K-Means Implementation

Scikit-learn’s KMeans class, found in the sklearn.cluster module, is designed for ease of use and efficiency. By default, it utilizes the Euclidean distance metric to measure the similarity between data points and cluster centers. The algorithm iteratively assigns each data point to the nearest cluster and updates the cluster centers to minimize the within-cluster sum of squares (WCSS). This process continues until convergence, where the cluster assignments no longer change significantly or a maximum number of iterations is reached. The simplicity and speed of Scikit-learn’s K-Means make it a go-to choice for many clustering tasks.

However, the reliance on Euclidean distance can be a limitation in certain scenarios. Euclidean distance assumes that all features are equally important and that the data is distributed in a way that this metric accurately reflects similarity. In cases where these assumptions don’t hold, using a different distance metric might lead to better clustering results. For instance, when dealing with categorical data or data with varying scales, alternative distance metrics like Manhattan distance or cosine similarity might be more appropriate. Therefore, understanding how to customize the distance function becomes essential for broader applicability of K-Means clustering.

The core of the K-Means algorithm involves calculating distances between data points and cluster centroids. While Scikit-learn’s KMeans class doesn’t directly allow passing a custom distance function, it does offer alternative approaches to achieve similar results. The most common method involves precomputing a distance matrix and using the precomputed option. This approach gives you full control over how distances are calculated, allowing you to incorporate any custom distance function you desire. This is particularly useful when dealing with complex data types or when Euclidean distance is not suitable for your specific problem.

Methods for Customizing Distance Metrics in Scikit-learn

While you can’t directly inject a custom distance function into the KMeans class, there are effective workarounds. Two primary methods exist: using precomputed distances and exploring alternative clustering algorithms that natively support custom distance metrics. Let’s delve into each of these approaches.

Precomputed Distance Matrices

The KMeans class in Scikit-learn accepts a precomputed option for the metric parameter. This allows you to provide a matrix of pairwise distances between all data points. Instead of the algorithm calculating distances using Euclidean distance, it uses the values you provide in the distance matrix. This is a powerful way to incorporate any custom distance function. To use this method, you first need to calculate the distance matrix using your desired distance function. Then, you pass this matrix to the KMeans class with metric=‘precomputed’. This approach offers flexibility but requires careful handling of the distance matrix.

Here’s how you can implement this in Python:

1. Calculate the distance matrix using your custom distance function. You can use libraries like scipy.spatial.distance to help with this.
2. Create a KMeans object with metric=‘precomputed’.
3. Fit the KMeans object to the precomputed distance matrix.
4. Obtain the cluster labels.

For example, using Manhattan distance:

from sklearn.cluster import KMeans from scipy.spatial.distance import pdist, squareform import numpy as np Sample data X = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]]) Calculate Manhattan distance matrix distance_matrix = squareform(pdist(X, metric='cityblock')) Apply K-Means with precomputed distances kmeans = KMeans(n_clusters=2, random_state=0, n_init='auto', metric='precomputed') kmeans.fit(distance_matrix) Get cluster labels labels = kmeans.labels_ print(labels) 

Alternative Clustering Algorithms

Another approach is to use clustering algorithms that natively support custom distance metrics. Algorithms like Agglomerative Clustering and DBSCAN allow you to specify a custom distance function directly. Agglomerative Clustering, for instance, can use any distance metric supported by scipy.spatial.distance.pdist. DBSCAN also allows for custom distance functions, although it might require more complex implementations. These algorithms provide more direct control over the distance metric compared to the precomputed distance matrix approach with K-Means.

• Agglomerative Clustering: Uses a bottom-up approach, starting with each data point as a separate cluster and merging them iteratively based on the specified distance metric.
• DBSCAN: Groups together points that are closely packed together, marking as outliers points that lie alone in low-density regions.

Practical Examples and Considerations

Let’s consider a real-world example. Imagine you’re clustering documents based on their content. Using Euclidean distance on raw word counts might not be effective because it doesn’t account for document length or word frequency variations. Instead, you could use cosine similarity, which measures the angle between document vectors. By precomputing a cosine distance matrix, you can then apply K-Means clustering to group documents with similar content, regardless of their length. This approach is widely used in text mining and information retrieval.

When choosing between precomputed distances and alternative algorithms, consider the size of your dataset and the complexity of your distance function. Precomputing a distance matrix can be memory-intensive for large datasets, as it requires storing an n x n matrix, where n is the number of data points. Alternative algorithms might be more efficient in such cases, but they might also have different parameter tuning requirements. For example, Agglomerative Clustering requires choosing a linkage criterion, while DBSCAN requires setting the epsilon and minimum samples parameters. These parameters can significantly impact the clustering results.

It’s also important to consider the computational cost of your custom distance function. Some distance functions are more computationally expensive than others. If your distance function is very complex, precomputing the distance matrix might take a significant amount of time. In such cases, optimizing your distance function or using a more efficient algorithm might be necessary. According to a study by Aggarwal et al. (2001), the choice of distance metric can drastically affect the outcome of clustering, especially with high-dimensional data [^1^]. Therefore, careful consideration of the distance metric is crucial for achieving meaningful clustering results.

FAQ: Custom Distance Functions and K-Means

**Q: Can I directly pass a function to the metric parameter in Scikit-learn's KMeans?**

A: No, the metric parameter in KMeans does not directly accept a custom function. You need to use the precomputed option or explore alternative clustering algorithms.

**Q: What are the advantages of using precomputed distances?**

A: Precomputed distances allow you to use any custom distance function, regardless of its complexity. This provides maximum flexibility in tailoring the clustering process to your specific data characteristics.

**Q: What are the disadvantages of using precomputed distances?**

A: Precomputing a distance matrix can be memory-intensive for large datasets, as it requires storing an n x n matrix. It can also be computationally expensive if your distance function is complex.

**Q: Which alternative clustering algorithms support custom distance metrics?**

A: Algorithms like Agglomerative Clustering and DBSCAN allow you to specify a custom distance function directly.

[^1^]: Aggarwal, C. C., Hinneburg, A., & Keim, D. A. (2001). On the surprising behavior of distance metrics in high dimensional space. International Conference on Database Theory. SpringerFor further reading, explore the Scikit-learn documentation on K-Means and the scipy.spatial.distance module for various distance metrics. Consider experimenting with different distance functions and clustering algorithms to find the best approach for your specific data and problem.

Question & Answer :
Is it possible to specify your own distance function using scikit-learn K-Means Clustering?

Here’s a small kmeans that uses any of the 20-odd distances in scipy.spatial.distance, or a user function.
Comments would be welcome (this has had only one user so far, not enough); in particular, what are your N, dim, k, metric ?

#!/usr/bin/env python # kmeans.py using any of the 20-odd metrics in scipy.spatial.distance # kmeanssample 2 pass, first sample sqrt(N) from __future__ import division import random import numpy as np from scipy.spatial.distance import cdist # $scipy/spatial/distance.py # http://docs.scipy.org/doc/scipy/reference/spatial.html from scipy.sparse import issparse # $scipy/sparse/csr.py __date__ = "2011-11-17 Nov denis" # X sparse, any cdist metric: real app ? # centres get dense rapidly, metrics in high dim hit distance whiteout # vs unsupervised / semi-supervised svm #............................................................................... def kmeans( X, centres, delta=.001, maxiter=10, metric="euclidean", p=2, verbose=1 ): """ centres, Xtocentre, distances = kmeans( X, initial centres ... ) in: X N x dim may be sparse centres k x dim: initial centres, e.g. random.sample( X, k ) delta: relative error, iterate until the average distance to centres is within delta of the previous average distance maxiter metric: any of the 20-odd in scipy.spatial.distance "chebyshev" = max, "cityblock" = L1, "minkowski" with p= or a function( Xvec, centrevec ), e.g. Lqmetric below p: for minkowski metric -- local mod cdist for 0 < p < 1 too verbose: 0 silent, 2 prints running distances out: centres, k x dim Xtocentre: each X -> its nearest centre, ints N -> k distances, N see also: kmeanssample below, class Kmeans below. """ if not issparse(X): X = np.asanyarray(X) # ? centres = centres.todense() if issparse(centres) \ else centres.copy() N, dim = X.shape k, cdim = centres.shape if dim != cdim: raise ValueError( "kmeans: X %s and centres %s must have the same number of columns" % ( X.shape, centres.shape )) if verbose: print "kmeans: X %s centres %s delta=%.2g maxiter=%d metric=%s" % ( X.shape, centres.shape, delta, maxiter, metric) allx = np.arange(N) prevdist = 0 for jiter in range( 1, maxiter+1 ): D = cdist_sparse( X, centres, metric=metric, p=p ) # |X| x |centres| xtoc = D.argmin(axis=1) # X -> nearest centre distances = D[allx,xtoc] avdist = distances.mean() # median ? if verbose >= 2: print "kmeans: av |X - nearest centre| = %.4g" % avdist if (1 - delta) * prevdist <= avdist <= prevdist \ or jiter == maxiter: break prevdist = avdist for jc in range(k): # (1 pass in C) c = np.where( xtoc == jc )[0] if len(c) > 0: centres[jc] = X[c].mean( axis=0 ) if verbose: print "kmeans: %d iterations cluster sizes:" % jiter, np.bincount(xtoc) if verbose >= 2: r50 = np.zeros(k) r90 = np.zeros(k) for j in range(k): dist = distances[ xtoc == j ] if len(dist) > 0: r50[j], r90[j] = np.percentile( dist, (50, 90) ) print "kmeans: cluster 50 % radius", r50.astype(int) print "kmeans: cluster 90 % radius", r90.astype(int) # scale L1 / dim, L2 / sqrt(dim) ? return centres, xtoc, distances #............................................................................... def kmeanssample( X, k, nsample=0, **kwargs ): """ 2-pass kmeans, fast for large N: 1) kmeans a random sample of nsample ~ sqrt(N) from X 2) full kmeans, starting from those centres """ # merge w kmeans ? mttiw # v large N: sample N^1/2, N^1/2 of that # seed like sklearn ? N, dim = X.shape if nsample == 0: nsample = max( 2*np.sqrt(N), 10*k ) Xsample = randomsample( X, int(nsample) ) pass1centres = randomsample( X, int(k) ) samplecentres = kmeans( Xsample, pass1centres, **kwargs )[0] return kmeans( X, samplecentres, **kwargs ) def cdist_sparse( X, Y, **kwargs ): """ -> |X| x |Y| cdist array, any cdist metric X or Y may be sparse -- best csr """ # todense row at a time, v slow if both v sparse sxy = 2*issparse(X) + issparse(Y) if sxy == 0: return cdist( X, Y, **kwargs ) d = np.empty( (X.shape[0], Y.shape[0]), np.float64 ) if sxy == 2: for j, x in enumerate(X): d[j] = cdist( x.todense(), Y, **kwargs ) [0] elif sxy == 1: for k, y in enumerate(Y): d[:,k] = cdist( X, y.todense(), **kwargs ) [0] else: for j, x in enumerate(X): for k, y in enumerate(Y): d[j,k] = cdist( x.todense(), y.todense(), **kwargs ) [0] return d def randomsample( X, n ): """ random.sample of the rows of X X may be sparse -- best csr """ sampleix = random.sample( xrange( X.shape[0] ), int(n) ) return X[sampleix] def nearestcentres( X, centres, metric="euclidean", p=2 ): """ each X -> nearest centre, any metric euclidean2 (~ withinss) is more sensitive to outliers, cityblock (manhattan, L1) less sensitive """ D = cdist( X, centres, metric=metric, p=p ) # |X| x |centres| return D.argmin(axis=1) def Lqmetric( x, y=None, q=.5 ): # yes a metric, may increase weight of near matches; see ... return (np.abs(x - y) ** q) .mean() if y is not None \ else (np.abs(x) ** q) .mean() #............................................................................... class Kmeans: """ km = Kmeans( X, k= or centres=, ... ) in: either initial centres= for kmeans or k= [nsample=] for kmeanssample out: km.centres, km.Xtocentre, km.distances iterator: for jcentre, J in km: clustercentre = centres[jcentre] J indexes e.g. X[J], classes[J] """ def __init__( self, X, k=0, centres=None, nsample=0, **kwargs ): self.X = X if centres is None: self.centres, self.Xtocentre, self.distances = kmeanssample( X, k=k, nsample=nsample, **kwargs ) else: self.centres, self.Xtocentre, self.distances = kmeans( X, centres, **kwargs ) def __iter__(self): for jc in range(len(self.centres)): yield jc, (self.Xtocentre == jc) #............................................................................... if __name__ == "__main__": import random import sys from time import time N = 10000 dim = 10 ncluster = 10 kmsample = 100 # 0: random centres, > 0: kmeanssample kmdelta = .001 kmiter = 10 metric = "cityblock" # "chebyshev" = max, "cityblock" L1, Lqmetric seed = 1 exec( "\n".join( sys.argv[1:] )) # run this.py N= ... np.set_printoptions( 1, threshold=200, edgeitems=5, suppress=True ) np.random.seed(seed) random.seed(seed) print "N %d dim %d ncluster %d kmsample %d metric %s" % ( N, dim, ncluster, kmsample, metric) X = np.random.exponential( size=(N,dim) ) # cf scikits-learn datasets/ t0 = time() if kmsample > 0: centres, xtoc, dist = kmeanssample( X, ncluster, nsample=kmsample, delta=kmdelta, maxiter=kmiter, metric=metric, verbose=2 ) else: randomcentres = randomsample( X, ncluster ) centres, xtoc, dist = kmeans( X, randomcentres, delta=kmdelta, maxiter=kmiter, metric=metric, verbose=2 ) print "%.0f msec" % ((time() - t0) * 1000) # also ~/py/np/kmeans/test-kmeans.py 

Some notes added 26mar 2012:

1) for cosine distance, first normalize all the data vectors to |X| = 1; then

cosinedistance( X, Y ) = 1 - X . Y = Euclidean distance |X - Y|^2 / 2 

is fast. For bit vectors, keep the norms separately from the vectors instead of expanding out to floats (although some programs may expand for you). For sparse vectors, say 1 % of N, X . Y should take time O( 2 % N ), space O(N); but I don’t know which programs do that.

2) Scikit-learn clustering gives an excellent overview of k-means, mini-batch-k-means … with code that works on scipy.sparse matrices.

3) Always check cluster sizes after k-means. If you’re expecting roughly equal-sized clusters, but they come out [44 37 9 5 5] % … (sound of head-scratching).