Solved – Implementations of clustering with asymmetrical distance/similarity matrix

clusteringmethodology

In my clustering problem I'm working with custom similarity measure and looking for any implementation of algorithms with asymmetrical distance or similarity matrix. I'm only interested in those that can offer custom similarity/distance matrix as input or a custom similarity measure function. Language of implementation doesn't really matter as long as it's working. (R would be the best, Python, C++, C, Java, Ruby)

What methods I find particularly interested in.

Taylor-Butina clustering/grouping for asymmetrical similarity. Here is the usage of it. Some R implementations, though not sure if it's usable with asymmetrical matrix.
Tarjan's hierarchical clustering with strong components. Not to be confused strongly connected components algorithm.
Spectral clustering using custom affinity matrix. I'm especially interested in implementation of this one in R.

I found some of the algorithms implemented in Mesa Suite Version 2.0 Grouping Module. However I haven't found any trials or downloads of this program.

Edit : The distance function satisfies triangle inequality.

I think this post would be interesting for all cheminformatics people using R.

Best Answer

DBSCAN and OPTICS should work with asymmetric distances as well.

Don't use the DBSCAN implementation in R. It's incredibly slow.

The version in scipy probably doesn't allow you to use arbitrary distances, and it computes the full distance matrix, so it scales badly.

The DBSCAN and OPTICS implementations in ELKI are pretty good, and scale really well when you can use index structures.

Related Solutions

Clustering – Understanding Comparisons of Clustering Results in R

First let me tell you that I am not going to explain exactly all the measures here, but I am going to give you an idea about how to compare how good the clustering methods are (let's assume we are comparing 2 clustering methods with the same number of clusters).

For example the bigger the diameter of the cluster, the worst the clustering, because the points that belong to the cluster are more scattered.
The higher the average distance of each clustering, the worst the clustering method. (Let's assume that the average distance is the average of the distances from each point in the cluster to the center of the cluster.)

These are the two metrics that are the most used. Check these links to understand what they stand for:

inter-cluster distance (the higher the better, is the summatory of the distance between the different cluster centroids)
intra-cluster distance (the lower the better, is the summatory of the distance between the cluster members to the center of the cluster)

To better understanding the metrics above, check this.

Then you should read the manual of the library and functions you are using to understand which measures represent each of these, or if these are not included try to find the meaning of the included. However, I would not bother and stick with the ones I stated here.

Let's go on with the questions you made:

Regarding scaling data: Yes you should always scale the data for clustering, otherwise the different scales of the different dimensions (variables) will have different influences in how the data are clustered, with the higher the values in the variable, the more influential that variable will be in how the clustering is done, while indeed they should all have the same influence (unless for some particular strange reason you do not want it that way).
The distance functions compute all the distances from one point (instance) to another. The most common distance measure is Euclidean, so for example, let's suppose you want to measure the distance from instance 1 to instance 2 (let's assume you only have 2 instances for the sake of simplicity). Also let's assume that each instance has 3 values (x1, x2, x3), so I1=0.3, 0.2, 0.5 and I2=0.3, 0.3, 0.4 so the Euclidean distance from I1 and I2 would be: sqrt((0.3-0.2)^2+(0.2-0.3)^2+(0.5-0.4)^2)=0.17, hence the distance matrix will result in:
```
    i1    i2
i1  0     0.17
i2  0.17  0
```

Notice that the distance matrix is always symmetrical.

The Euclidean distance formula is not the only one that exists. There are many other distances that can be used to calculate this matrix. Check for example in Wikipedia Manhattain Distance and how to calculate it. At the end of the Wikipedia page for Euclidean Distance (where you can also check its formula) you can check which other distances exist.

Solved – Clustering with asymmetrical distance measures

If the M-F distance is asymmetric because the future is different from the past, then a genuine asymmetric clustering is called for. First, an asymmetric distance function must be defined.

One way to to asymmetric clustering, given a distance function, is to embed the original data into a new coordinate space. See "Geometrical Structures of Some Non-Distance Models for Asymmetric MDS" by Naohito Chino and Kenichi Shiraiwa, Behaviormetrika, 1992 (pdf). This is called HCM (the Hermitian Canonical Model).

Find a Hermitian matrix $H$, where $$ H_{ij} = \frac 1 2 [d(x_i, x_j) + d(x_j, x_i)] + i \frac 1 2 [d(x_i, x_j) - d(x_j, x_i)] $$ Find the eigenvalues and eigenvectors, then scale each eigenvector by the square root of its corresponding eigenvalue.

This transforms the data into a space of complex numbers. Once the data is embedded, the distance between objects x and y is just x * y, where * is the conjugate transpose. At this point you can run k-means on the complex vectors.

Spectral asymmetric clustering has also been done, see the thesis by Stefan Emilov Atev, "Using Asymmetry in the Spectral Clustering of Trajectories," University of Minnesota, 2011, which gives MATLAB code for a special algorithm.

Best Answer

Related Solutions

Clustering – Understanding Comparisons of Clustering Results in R

Solved – Clustering with asymmetrical distance measures

Related Question