I have as an input a number of points that I need to partition into clusters. Each point has a number of features that are ideally to be used to find the similarity between each point and the others. Some of these features are scalar values (one number) and others are vectors.

For example, assume that each point has the following features:

  1. S1: scalar value

  2. V1: 48 $\times$ 1 vector

  3. V2: 48 $\times$ 1 vector

For example one point may have (S1,V1, V2) as (100, {0, 100, 20, 30}, {75,0,10, 5})

My hypothesis is to use cosine similarity to find how similar the vector V1 or V2 of one point is to the vector V1 or V2 of another point. I have already computed the similarity matrices between all points in terms of V1 and V2 similarities.

By exploring the standard clustering algorithms in R, I have found that k-means turns to use the Euclidean distance, which might be suitable for clustering points according to their scalar values, because [subject unclear] doesn't work for the situation where I have hybrid types of features (scalars and vectors). Also the K-medoid clustering seems to be supporting only the Euclidean and the Manhattan distances.

I think what should be done is to generate one more distance/similarity matrix between all points based on the scalar value, so that we end with three similarity matrices that show the similarity between each point and the other points according to each feature regardless of it being a scalar or a vector, and use those matrices for finding the neighbourhood of points while clustering.

I wonder if there is an implementation for a clustering algorithm that accepts as an input the similarity matrices (or alternatively the dissimilarity/distance matrices) between vector features of multiple points and uses them for clustering?

  • 1
    There is no fundamental difference between scalar and vector in respect to computation of some proximity measure: scalar is simply a unidimensional vector. Important questions are: (1) is S1 data also quantitative as V1 and V2 are (I presume V1, V2 are quantitative, i.e. numeric coordinates). (2) Are values of V1 and V2 directly comparable in units and magnitude (if yes, V1 and V2 could be directly combined in one vector, else they should be normalized "before" or "after" computing a similarity) – ttnphns Jun 26 '13 at 10:02
  • Thanks for your comment. V1 and V2 are of the same units but they measure two different properties of the objects being clustered.. I think there might be cases where the dissimilarity between two objects according the combined vector (v1+v2) is less than the dissimilarity between them according to V1 and V2 . So I guess I should better combine the dissamilaritiy matrices instead of combining the vectors, is it right ? – Moustafa Alzantot Jun 26 '13 at 10:22
  • For s1: it is a scalar and has different units from the units of values in V1 & V2,, so I guess for it I should stick with euclidean distance. what I am thinking about is to generate a distance matrix between all points according to S1 and add this distance matrix to the combined dissimilarity matrices from V1 and V2 and use the final matrix for clustering .. does it sound right ? – Moustafa Alzantot Jun 26 '13 at 10:23
  • does it sound right? Why not? However add this distance matrix to the combined dissimilarity matrices leaves open the question of differential units between the two matrices. You may add a proximity based on (e.g.) colour to the proximity based on size either with a proper standardization transform or if the standardization is imbedded right in the proximity formula – ttnphns Jun 26 '13 at 10:42

Actually, K-medoids (aka: PAM) can work with any kind of distance or similarity metric. So do DBSCAN, OPTICS and Hierarchical clustering. The latter however is usually implemented in $O(n^3)$, so not an option if you have a lot of instances.

If you'd simply like to cluster your data based on a similarity metric of your choice you might want to take a look at Affinity Propagation clustering. It takes any similarity matrix as input.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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