8
$\begingroup$

I have a large data set and a cosine similarity between them. I would like to cluster them using cosine similarity that puts similar objects together without needing to specify beforehand the number of clusters I expect.

I read the sklearn documentation of DBSCAN and Affinity Propagation, where both of them requires a distance matrix (not cosine similarity matrix).

Really, I'm just looking for any algorithm that doesn't require a) a distance metric and b) a pre-specified number of clusters.

Does anyone know of an algorithm that would do that?

$\endgroup$
8
$\begingroup$

First, every clustering algorithm is using some sort of distance metric. Which is actually important, because every metric has its own properties and is suitable for different kind of problems.

You said you have cosine similarity between your records, so this is actually a distance matrix. You can use this matrix as an input into some clustering algorithm.

Now, I'd suggest to start with hierarchical clustering - it does not require defined number of clusters and you can either input data and select a distance, or input a distance matrix (where you calculated the distance in some way).

Note that the hierarchical clustering is expensive to calculate, so if you have a lot of data, you can start with just sample.

$\endgroup$
  • $\begingroup$ Thanks for the useful answer. I have a similar problem like this datascience.stackexchange.com/questions/20198 and would like to use the answer given in it. However, to find the most nearest points to the centroid he uses the minimum cosine distance. If I am using cosine similarity, would it be the highest cosine similarity? $\endgroup$ – Smith Volka Sep 5 '17 at 8:16
  • 1
    $\begingroup$ You can simply convert the distance into similarity. If distance from A to B is 0.3, then the similarity will be 1-0.3=0.7. $\endgroup$ – HonzaB Sep 5 '17 at 10:21
3
$\begingroup$

DBSCAN can trivially be implemented with a similarity measure instead of a distance. You just need to change the <= epsilon into a >= epsilon.

HAC also works just fine with similarities (at least single-link, complete-link, UPGMA, WPGMA - don't use Ward), if you swap "min" and "max" (you want to merge with maximum similarity rather than minimum distance).

If you are lazy, you can also just transform your similarity into a distance. If you have a fixed maximum, dist=max-sim will often do.

$\endgroup$
  • $\begingroup$ Thank you for the answer. what did ypu mean by epsilon in <= epsilon into a >= epsilon? $\endgroup$ – Smith Volka Sep 6 '17 at 6:38
  • $\begingroup$ Ok, the default value of eps in sklearn is 0.5. Is it correct if I increase this value (e.g.,0.8). Is it what you meant in your answer? $\endgroup$ – Smith Volka Sep 6 '17 at 7:19
  • $\begingroup$ DBSCAN uses a maximum epsilon distance threshold. By GDBSCAN, you can also use a minimum similarity instead. you need to change the code, not the parameter. Sklearn doesn't support a similarity. ELKI has direct support for similarity functions in GDBSCAN via SimilarityNeighborPredicate. $\endgroup$ – Anony-Mousse Sep 6 '17 at 11:09
  • $\begingroup$ If you can't code, you can do the"lazy" approach I mentioned. It should give the same results. $\endgroup$ – Anony-Mousse Sep 6 '17 at 11:13
  • $\begingroup$ What do you mean by If you have a fixed maximum, dist=max-sim will often do? I am interested in trying it. $\endgroup$ – Smith Volka Sep 6 '17 at 11:44
3
$\begingroup$

I'd use sklearn's Hierarchical clustering

from sklearn.feature_extraction.text import CountVectorizer, TfidfTransformer
from scipy.cluster import  hierarchy

#Vectorizing
X = CountVectorizer().fit_transform(docs)
X = TfidfTransformer().fit_transform(X)
#Clustering
X = X.todense()
threshold = 0.1
Z = hierarchy.linkage(X,"average", metric="cosine")
C = hierarchy.fcluster(Z, threshold, criterion="distance")

C is your clustering of the documents docs.

You can use other metrics instead of cosine, and use a different threshold than 0.1

$\endgroup$
  • $\begingroup$ is "docs" the original data matrix ? Where to put the data matrix, or where to put the cosine similarity matrix ? thanks $\endgroup$ – Bill Ancalagon the black May 4 '18 at 19:23
  • 1
    $\begingroup$ docs are the documents, Z is the cosine similarity matrix $\endgroup$ – Uri Goren May 4 '18 at 20:29
3
$\begingroup$

I think the clustMixType package might give you better results/insights.

By using this package you can use combination of Categorical and Numeric Data directly, it doesn’t need any kind of hot encoding.

You just need to feed in the data and it automatically segregates into Categorical and Numeric Data, if you find any issues at the time of segregation you can use functions like as.factor(to convert to a categorical) and as.numeric(to convert to a Numeric field).

You can calculate Lambda(mean Distance value) before hand and fed in as an input to the algorithm.

If you don’t know the optimal number of clusters, you can use WSS(within Sum of Squares), plot(elbow chart) to decide the optimal number of clusters.

$\endgroup$
2
$\begingroup$

All clustering methods use a distance metric of some sort. And remember that distance is essentially a dissimilarity measure. So if you normalize your similarity betwen 0 and 1, your distance is simply 1-similarity

As for algorithms that do not require a number of clusters to be specified, there are of course hierarchical clustering techniques, which essentially build a tree like structure that you can "cut" wherever you please (you can use some perfomance metrics to do that automatically)

X-means is a version of K-means which tries a certain number of K and picks the one that maximizes some evaluation function.

Mean shift also "finds" a natural number of clusters but is sensible to other parameters such as the bandwith for instance.

$\endgroup$

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.