Is Clustering used in real world systems/products involving large amounts of data? How are the nuances taken care of?

Question

I am working with a real dataset of around 2.5 million short text data (posts, around 10 words in an average data element). I wanted to group similar posts together. So, I applied KMeans clustering on the dataset after doing the standard pre processing. After vectorization (I did TfIdf), the matrix was huge (2.5 million rows and around 60 k columns). I did an SVD + LSA transformation which made it smaller (2.5 million x 150 ). I gave 200 as the number of clusters and applied K Means. I must say that the results are not very bad. There are clusters which have similar posts (not the semantics, but the words similar), but there are those clusters which are randomly placed too.

Because of the large size of the data, I am not able to effectively visualize the results or measure the goodness of the clusters. Though I tried implementing silhouette coefficient, elbow methods for finding the optimal number of clusters, I was getting continuous memory errors. I don't know if 150 is the right number to use during dimensionality reduction. Could you please suggest any other methods for solving these issues?

When I reached this point, I started doubting the effectiveness of clustering as a method. I am curious to know if anybody is using clustering in large production scale systems, if so, what kind of techniques do people use?

Please find the code below:

`

 tfidf_vectorizer = TfidfVectorizer(max_df=0.5, max_features=200000,
                                 min_df=0.001,decode_error='ignore', stop_words='english',strip_accents='ascii',use_idf=True, ngram_range=(1,2),tokenizer=tokenizeAndFilter,lowercase=True)`

`    tfidf_matrix = tfidf_vectorizer.fit_transform(tokens.values()) #fit the vectorizer to synopses


    svd = TruncatedSVD(150)
    normalizer = Normalizer(copy=False)
    lsa = make_pipeline(svd, normalizer)

    X = lsa.fit_transform(tfidf_matrix) 
    feature_names = tfidf_vectorizer.get_feature_names()

    with open(path+'terms.csv','w') as f:
       for col in tfidf_matrix.nonzero()[1]:
          f.write(feature_names[col]+','+str( tfidf_matrix[0, col]))
          f.write('\n')

        sil_dict={}
        for n_clusters in range(50,500,10):
            km=KMeans(n_clusters=n_clusters,init='k-means++',max_iter=500,n_init=1)
        km.fit(X)
            label = km.labels_
            sil_coeff = silhouette_score(X, label, metric='cosine',n_jobs=10)
    #        print("For n_clusters={}, The Silhouette Coefficient is {}".format(n_cluster, sil_coeff))
        sil_dict[n_clusters]=sil_coeff
            with open('kmeans_model'+str(n_clusters)+'.pkl','wb') as f:
               cPickle.dump(km,f)



    original_centroids=svd.inverse_transform(km.cluster_centers_)
    order_centroids=original_centroids.argsort()[:,::-1]

    terms=tfidf_vectorizer.get_feature_names()
    clusters=collections.defaultdict(list)
    k=0
    for i in km.labels_:
        clusters[i].append(tokens.values()[k])
        k+=1
        for i in range(10):
            print i
            for j in order_centroids[i, :10]:
                  print(terms[j] )
        for key,valueList in clusters.items():
            with open(path+'\\'+OUTPUTFILE+'_'+str(key)+'.csv','w') as f:
                 for value in valueList:
                    f.write(value+'\n')

`

Answer 1

1. Clustering (mostly) does not apply to huge data.

   Since you cannot automate result evaluation and validation (forget the 'internal' measures, they are useless) nor use the automatic results in any meaningful way (partially because clustering is just way too unreliable for automatic use).

   Clustering requires you to study the result, learn, and then decide what to do next. You can't automate this.

   It is explorative. A tool for you to study your data; not a tool for machines to automatically predict labels. Some clusters will be good, some will be bad. This is fine, you got some good clusters! Just don't rely on everything being clustered. There will always be data that does not belong to any cluster. And often, there will be clusters that just don't make any sense to you, or that are too trivial to be of use or interest.

2. Results just do not improve with data size.

3. Methods don't scale well.

   Most clustering methods (including k-means) have worst case runtimes of O(n^2) or O(n^3). That is really problematic. But since they are analyzing an NP-hard problem, that is quite decent.

   So I guess, you want to work on a sample.

4. RAM is big these days, and vectors are compact.

   You can usually squeeze a billion vectors into RAM. So anything that - like k-means - works with numerical vectors (and not, say, videos and images) just fits into main memory. No need to go larger than that.

Answer 2

I agree with Anony-Mousse that if you can't easily visualize the resulting clusters and evaluate them manually then this technique is probably not going to be very useful.

That being said...

• Choosing Number of dimensions to reduce to: typically you decide on an acceptable level of information loss in terms of how much total variance of the original data is lost once you execute your dimensionality reduction. Then you make the number of dimensions as small as possible without dropping below this limit.
• Choosing Number of clusters: You can take a look at wikipedia for some info on how people assess this. If you take average distance of points from their assigned cluster centers as a metric, then one common approach is to graph this "error" as a function of number of clusters. Obviously it will always get smaller with more clusters but sometimes there is an "elbow" where you stop getting much more "bang for your buck" as you add more clusters.

It looks like you're using sklearn, so you could take a closer look at the documentation and User Guide for those tools.

Answer 3

Already great answers have been provided, but I will add my two cents. What worked for me is to take a random sample and make hierarchical clustering. Since it requires a distance matrix to be created, the sample size must be small enough to fit the memory.

Based on the results, you can choose the optimal number of clusters. Note that you should play a bit with the random sample, distance measure and the way you standardize data (z-score worked best for me, I would recommend to read this paper).

To put it simply, the tinkering with hierarchical clustering could look like this:

from sklearn import datasets
from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy import stats

# import some data to play with
iris = datasets.load_iris()
X = iris.data
Y = iris.target

X_std = stats.zscore(X)

Z = linkage(X_std,'ward')

# calculate full dendrogram
plt.figure(figsize=(5, 5))
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('sample index')
plt.ylabel('distance')
dendrogram(
    Z,
    leaf_rotation=90.,  # rotates the x axis labels
    leaf_font_size=8.,  # font size for the x axis labels
)
plt.show()

There is a great tutorial here.

You mentioned the silhouette plots - I would do the same as with the hierarchical clustering. Draw random sample large enough to fit the memory and have a look at the plot. Repeat this to see whether you get similar results with different samples.

Lastly, do you have anyone to discuss the amount of clusters with? Since this is not exact method, but merely exploratory as mentioned by others, have business knowledge can be of great value.