Clustering based on similarity scores

Question

Assume that we have a set of elements E and a similarity (not distance) function sim(ei, ej) between two elements ei,ej ∈ E.

How could we (efficiently) cluster the elements of E, using sim?

k-means, for example, requires a given k, Canopy Clustering requires two threshold values. What if we don't want such predefined parameters?

Note, that sim is not neccessarily a metric (i.e. the triangle inequality may, or may not hold). Moreover, it doesn't matter if the clusters are disjoint (partitions of E).

Answer 1

1. I think a number of clustering algorithms that normally use a metric, do not actually rely on the metric properties (other than commutativity, but I think you'd have that here). For example, DBSCAN uses epsilon-neighborhoods around a point; there is nothing in there that specifically says the triangle inequality matters. So you can probably use DBSCAN, although you may have to do some kind of nonstandard spatial index to do efficient lookups in your case. Your version of epsilon-neighborhood will likely be sim > 1/epsilon rather than the other way around. Same story with k-means and related algorithms.

2. Can you construct a metric from your similarity? One possibility: dist(ei, ej) = min( sim(ei, ek) + sim(ek, ej) ) for all k ... Alternately, can you provide an upper bound such that sim(ei, ej) < sim(ei, ek) + sim(ek, ej) + d, for all k and some positive constant d? Intuitively, large sim values means closer together: is 1/sim metric-like? What about 1/(sim + constant)? What about min( 1/sim(ei, ek) + 1/sim(ek, ej) ) for all k? (that last is guaranteed to be a metric, btw)

3. An alternate construction of a metric is to do an embedding. As a first step, you can try to map your points ei -> xi, such that xi minimize sum( abs( sim(ei, ej) - f( dist(xi, xj) ) ), for some suitable function f and metric dist. The function f converts distance in the embedding to a similarity-like value; you'd have to experiment a bit, but 1/dist or exp^-dist are good starting points. You'd also have to experiment on the best dimension for xi. From there, you can use conventional clustering on xi. The idea here is that you can almost (in a best fit sense) convert your distances in the embedding to similarity values, so they would cluster correctly.

4. On the use of predefined parameters, all algorithms have some tuning. DBSCAN can find the number of clusters, but you still need to give it some parameters. In general, tuning requires multiple runs of the algorithm with different values for the tunable parameters, together with some function that evaluates goodness-of-clustering (either calculated separately, provided by the clustering algorithm itself, or just eyeballed :) If the character of your data doesn't change, you can tune once and then use those fixed parameters; if it changes then you have to tune for each run. You can find that out by tuning for each run and then comparing how well the parameters from one run work on another, compared to the parameters specifically tuned for that.

Answer 2

Alex made a number of good points, though I might have to push back a bit on his implication that DBSCAN is the best clustering algorithm to use here. Depending on your implementation, and whether or not you're using accelerated indices (many implementations do not), your time and space complexity will both be O(n2), which is far from ideal.

Personally, my go-to clustering algorithms are OpenOrd for winner-takes-all clustering and FLAME for fuzzy clustering. Both methods are indifferent to whether the metrics used are similarity or distance (FLAME in particular is nearly identical in both constructions). The implementation of OpenOrd in Gephi is O(nlogn) and is known to be more scalable than any of the other clustering algorithms present in the Gephi package.

FLAME on the other hand is great if you're looking for a fuzzy clustering method. While the complexity of FLAME is a little harder to determine since it's an iterative process, it has been shown to be sub-quadratic, and similar in run-speed to knn.

Answer 3

DBSCAN (see also: Generalized DBSCAN) does not require a distance. All it needs is a binary decision. Commonly, one would use "distance < epsilon" but nothing says you cannot use "similarity > epsilon" instead. Triangle inequality etc. are not required.

Affinity propagation, as the name says, uses similarities.

Hierarchical clustering, except for maybe Ward linkage, does not make any assumption. In many implementations you can just use negative distances when you have similarities, and it will work just fine. Because all that is needed is min, max, and <.

Kernel k-means could work IF your similarity is a good kernel function. Think of it as computing k-means in a different vector space, where Euclidean distance corresponds to your similarity function. But then you need to know k.

PAM (K-medoids) should work. Assign each object to the most similary medoid, then choose the object with the highest average similarity as new medoid... no triangle inequality needed.

... and probably many many more. There are literally hundreds of clustering algorithms. Most should work IMHO. Very few seem to actually require metric properties. K-means has probably the strongest requirements: it minimizes variance (not distance, or similarity), and you must be able to compute means.

Answer 4

Topological Data Analysis is a method explicitly designed for the setting you describe. Rather than a global distance metric, it relies only on a local metric of proximity or neighborhood. See: Topology and data and Extracting insights from the shape of complex data using topology. You can find additional resources at the website for Ayasdi.

Answer 5

I guess you are refering to "similarity-based clustering", which is

Clustering, which only uses the similarities between objects but does not require to represent the objects via feature vectors, is called similarity-based clustering.

There are 3 approaches:

1. Aspect model

[... ]Hofmann and Puzicha [1999], Hofmann et al. [1999], considers discrete data, where observations are pairs (x, y) taht are counted. That means the number of occurrences of x together with y are counted. Such data appear if relations like “person x buys product y” or “person x participates in y” are counted. Applications are found in information retrieval by document-word relations or in bioinformatics by sample-gene relations.

2. Affinity Propagation

[...] Frey and Dueck [2006, 2007], Givoni and Frey [2009]. Affinity propagation is both a similarity-based and an exemplar-based clustering method. The similarities between object i and object k are given by s(i, k). The values s(k, k) are called “preferences” and used to determine how likely object k becomes an exemplar. The larger s(k, k), the more likely object k becomes an exemplar.

3. Similarity-based Mixture Models

[...] The similarity between object i and object j is considered as the conditional probability p(xj | xi). This idea was already introduced in stochastic neighbor embedding (SNE), where this was the probability that xi would pick xj as its neighbor. Another interpretation is: the more xj is similar to xi , the less modifications are necessary to obtain xj from xi , the higher is the probability to obtain xj (randomly) from xi . In contrast to SNE, we now assume that the p(xj | xi) are given to allow for similarity-based clustering.

Source Machine Learning: Unsupervised Techniques, 2014, Sepp Hochreiter, Lecture Notes Bioinformatics Johannes Kepler University Linz