4
$\begingroup$

I am using silhouette_score to find the optimal k value. So I am running a for loop with a range of possible k values. I have added my code below. this program takes a very long time to run. Could you suggest some improvements for a more efficient run time?

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from sklearn.cluster import KMeans
from sklearn import metrics

data=np.load(filename)


coeffs=[]


for i in range(2,8):

    clusters=KMeans(n_clusters=i)
    clusters.fit(data)
    labels = clusters.labels_
    sil_coeff = metrics.silhouette_score(data, labels,metric='euclidean')
    coeffs.append(sil_coeff)


coeffs=np.array(coeffs)    
k=np.argmax(coeffs)+2
$\endgroup$
  • 1
    $\begingroup$ Probably this is a question for stackoverflow.com $\endgroup$ – RLave Jul 9 '18 at 15:24
  • $\begingroup$ This question could be here. People can help him in understanding the algorithm's runtime. It is important in data science to understand how algorithms work. It is annoying that people are nowadays treating data science as a pure programming problem (i.e. which package and parameters should I choose?). $\endgroup$ – Bruno Lubascher Jul 27 '18 at 6:51
3
$\begingroup$

Do some measurements to identify your bottlenecks.

Here, I suggest to not use Silhouette. Because it is much slower than k-means. Silhouette need O(n²) distance computations every run!

The obvious was to speed this up would this be to compute and store a distance matrix just once. This won't help k-means, but it will make multiple Silhouette runs a little bit faster (it will still be O(n²), but only array lookups instead of distance computations now). Nevertheless, this will not be scalable to large data.

The better approach is to use a cheaper heuristic to guess the "best" value of k. None such measure is perfect anyway.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Algorithmically speaking, your code is fine. My main guess as to why your code is slow to run is that you have many instances. How many instances do you exactly have?

There are certain ways to improve the speed of KMeans, here are a few:

  • Use GridSearchCV

What you are trying to do is hyperparameter tuning. Sklearn already has a built-in way to do this with GridSearchCV. This will optimize some of the processes.

  • Use the n_jobs argument

This will help parallelize some of the processes

  • Use MiniBatchKMeans instead

MiniBatchKMeans uses only part of the data at every step, and therefore, computing distances will be less expensive.

  • Use pre-computed distances for your silhouette score computation

As it was mentioned by others, there is no point in computing the distances between all your instances for each K since your instances do not change. Compute these distances once, and pass the distance matrix as X, and set metric="precomputed" according to the documentation

| improve this answer | |
$\endgroup$
  • $\begingroup$ I am not familiar with the ways you had mentioned. Could you provide some and comments for the ways you have mentioned. Would be greatly helpful. $\endgroup$ – listener Jul 11 '18 at 2:42
  • $\begingroup$ What are you not familiar with? First of all, I would go on the sklearn website and check out their document for KMeans and the other stuff that I linked $\endgroup$ – Valentin Calomme Jul 11 '18 at 5:00
  • 1
    $\begingroup$ Please demonstrate how to use the Ball tree with KMeans and silhouette in sklearn. I guess the sklearn authors would really appreciate such a contribution! $\endgroup$ – Has QUIT--Anony-Mousse Jul 27 '18 at 6:05
  • $\begingroup$ @Anony-Mousse my bad, just realized that indeed, this is not an option in the documentation, as they are doing this optimization themselves already by default (which is a good thing), thanks for pointing it out $\endgroup$ – Valentin Calomme Jul 27 '18 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.