2
$\begingroup$

I've got a set of approx. 50 000 2-dimensional euclidean vectors which are connected with 20 groups, i.e. each group has approx. 2500 2-dimensional euclidean vectors. My data includes endpoints coordinates, i.e. $x_0, y_0, x_1, y_1$. Now I would like to cluster the vectors within these groups, probably using k-means/k-medoids clutering (or other clustering algorithm with pre-defined no. of clusters). What is also important, my main focus is on vector's direction, length is the minor concern (but at best, still should be taken into conideration). What I'm struggling with is a choice of dissimilarity measure that would be suited to my problem. So here are my question:

  1. Does it matter how the data is specified? Alternatively, I could calculate an angle and length of vector and specify the data as $x_0, y_0, angle, length$. My intuition is that if angle is explicitely present, the euclidean distance should do a better job capturing the vector's direction. What is more I could maybe use some weighting, modify a euclidean distance and calculate distance between two observations as for example:

$\sqrt{(x^1_0 - x^2_0)^2 + (y^1_0 - y^2_0)^2 + (angle^1-angle^2)^2 + \frac{1}{n}(length^1-length^2)^2}$

where $n$ is some constant.

  1. I also considered angular distance as a dissimilarity measure. From what I know this is equivalent to clustering the standarised data points and therefore doesn't capture size (lengths in my case). But I'm not sure if k-means clustering can be done with cosine distance. If so, is there any package in R that allows that?

  2. Is is a good and statistically valid idea to perform clustering twice: firstly, to cluster starting points and secondly, within those clusters perform clustering for angles and lengths?

  3. Do you guys know any papers regarding similar problem, i.e. clustering the 2-dimensional data points? Any example would be very handy.

$\endgroup$
0
$\begingroup$

I hope I followed your question correctly. If you have those data points on as 2D vectors, that would mean, that you have, say $N=50,000$ data points each represented as $\left(x_i,y_i\right)$ , right? If angle and length are what you are concerned about, then your formulation seems right. You can convert each data point $\left(x_i,y_i\right)$ into $\left(\theta_i, d_i\right)$, which are the angle and length of the vector. These two parameters $\left(\theta_i, d_i\right)$ act as two features in each of your samples and you can run k-means on this. You have to be careful about using a consistent measure on your angle (always anti clockwise or clockwise). Your dissimilarity measure seems quite correct as far as I can tell. I'm sure you are aware of this python package but just for the sake of completion you can use this or in MATLAB you can use this. I'm not sure about R, so pardon me if that was the essential part of your question.

$\endgroup$
  • $\begingroup$ I've got 50,000 data points each represented as $(x_0^i, y_0^i, x_1^i, y_1^i)$ where subscript 0 refers to starting point of vector and subscript 1 refers to ending point of a vector. Basically, I want to treat two observations as similar when they have similar starting point AND angle. The length is minor concern, but it would be perfect if average length could be still calculated within clusters. $\endgroup$ – jakes Jul 12 '18 at 12:33
  • $\begingroup$ Then you can have three features. The starting coordinates $x_0^i$,$y_i^i$ and the angle given as $\theta_i$. Hence three features and $N$ samples. Or add a 4th feature which could be distance $d_i$. Does it make sense? Pardon me if I'm completely off-track. $\endgroup$ – Ashesh Jul 12 '18 at 23:39
  • $\begingroup$ Actually, it is exactly what I characterised in point 1. But the results are not satisfying and that is pretty understandable as the $x_0^i, y_0^i$ and $length$ range from 0 to 100 and $angle \in (0, 6.28)$ so minimizing euclidean distance captures most variability in $x_0, y_0, length$, and not the angle. I tried to standarise the features before using k-means but it still didn't work as expected and vectors with exactly opposite direction sometimes are within the same cluster, which doesn't make sense in my case. $\endgroup$ – jakes Jul 13 '18 at 5:26
  • $\begingroup$ Then I guess there is more to it. But since you mentioned that vectors of opposite direction are clustered in the same class , are you sure the angles are computed correctly for the vectors that are parallel but opposite? Since an opposite vector has the magnitude of the principal argument (smallest angle) equal. I'm just speculating here, but maybe you could provide your data set for me to run a few experiments in case I get lucky with one? Also, have you tried increasing your clusters (may separate overlapping features) or using fuzzy c-means or maybe EM with gaussian mixture? $\endgroup$ – Ashesh Jul 13 '18 at 6:25
  • $\begingroup$ Angles are correct, I am sure about that. Actually, I'm limited only to first and fourth quadrant, so $angle \in (0, \pi)$. Unfortunetely, I can't share my data as it is not public. $\endgroup$ – jakes Jul 13 '18 at 8:54
0
$\begingroup$

$(x_0,y_0,x_1,y_1)$ will be better behaved than, e.g., $(x_0,y_0,angle,length)$ (because the angle has a very different scale). Alternatively, you could also use $(x_0,y_0,x_1-x_0,y_1-y_0)$.

As you want to consider both points, you of course should use both.

But if all vectors are very short, you may still need to carefully scale attributes for best results, or the clustering may be mostly based on the starting point.

Euclidean distance on these vectors may be fine. The x and y values are all in Euclidean space, and presumably a difference of 1 in x is the same as a difference of 1 in y, isn't it? This doesn't hold anymore if you used the angle! One could argue that the two points should be considered independent. It's okay to try to take the sum of two distances in $(x_0,y_0)$ and $(x_1,y_1)$. But I don't expect the results to be very different. But for k-means, I'd stick to the usual sum of squares (it doesn't minimize Euclidean distances, but squared errors). If your data is too noisy, consider more robust algorithms such as DBSCAN.

$\endgroup$
  • $\begingroup$ What would be an advantage of converting to $(x_0, y_0, x_1-x_0, y_1-y_0)$? My vectors are not so short (average length is around 30), but the elements $x_1-x_0$ and $y_1-y_0$ can be relatively small (at least one of them) in comparison to $x_0, y_0$. Then the most importance would be paid on vector's starting coordinate, which is not of my interest. What am I missing here? $\endgroup$ – jakes Jul 16 '18 at 10:41
  • $\begingroup$ Well, it depends on your goals. If you study the equation, you can see the effects. Look at vectors (0,0,2,1) vs (1,1,3,2) and (-1,-1,2,1). Which should be more similar? $\endgroup$ – Anony-Mousse Jul 16 '18 at 18:10
  • $\begingroup$ Actually, to my application (1,1,3,2) is more similar to (0, 0, 2, 1) as they have the same direction. And indeed, your example shows the case. So to make sure that I understand it correctly - if two vectors have similar direction, their $(x_1-x_0, y_1-y_0)$ components are very close to each other. To have small overall distance they have to share similar starting point as well. This trick is brilliant! Additional question though - the vector's length is still taken into consideration, but it is not so important as the direction and starting point, right? $\endgroup$ – jakes Jul 17 '18 at 7:39
0
$\begingroup$

For this kind of situation, spectral clustering is an intuitive solution. Basically, the idea is to perform the k-means clustering in a transformed feature space, by defining what the inner product should be in that space.

The main point is to give yourself a similarity measure. In your case, this could be:

$$S(v_1, v_2) = exp(-\frac{(x_0^{(1)}-x_0^{(2)})^2+(y_0^{(1)}-y_0^{(2)})^2}{2\sigma_{start}^2} - \frac{(l^{(1)} - l^{(2)})^2}{2\sigma_{l}^2} - \frac{(\theta^{(1)} - \theta^{(2)})^2}{2\sigma_{\theta}^2})$$

where:

  • the $^{(1)}$ and $^{(2)}$ supscripts relate to vectors 1 and 2
  • $x_0$ and $y_0$ are the vector starting point coordinates
  • $l$ denotes the vector length (euclidian norm)
  • $\theta$ denotes the angle
  • $\sigma_{start}$, $\sigma_{l}$ and $\sigma_{\theta}$ are custom parameters that you should adjust to give more or less importance to each aspect of your vector (a low $\theta$ value will mean that the corresponding feature will be dealt with high sensitivity)

Then you should build the graph laplacian matrix and get the eigen vectors associated to the lowest eigen values, and project your data on these eigen vectors. You get a higher dimensional space, but your data will be easily separable by k-means algorithm.

The key is to adjust the $\sigma$ values well to get the clustering that you need.

Please note that this may be computationally intensive if your data contains too many points. You might want to use a smaller subset to find the right projection and cluster centers.

$\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.