I'm working on a local outlier factor implementation based on the wikipedia entry : http://en.wikipedia.org/wiki/Local_outlier_factor

This article seems to explain it in just two dimensional data. But what gaurantees that the algorithm still works for higher dimensional data ?

I've seen this same principal used in other algorithms : k-means, knn etc. Two dimensional data is used to explain how the algorithms work and then for higher dimensions it "just works". Is there some piece of knowledge that I'm not aware of which allows the same principles be applied to low and high dimensions. It's much easier to visualize algorithms using 2 dimensions but is difficult in higher dimensions. So if higher dimensions are difficult to visualize then why do the same algorithm steps apply ?

Excluding performance considerations can all algorithms which work for 2 dimensions be applied to 2+n dimensions ?

Update (response to @Anony-Mousse) :

"There is nothing specific to 2 dimensions in that article at all - what makes you think it only works in 2d?" I don't think it only works in 2d but I don't know why it may or may not work with higher dimensions. So in the wikipedia sample below is a LOF implementation using 2d :

enter image description here

But I could not use a graph like this for dimensions > 2

"2 dimensional data is just what your screen can present, so the figures are 2d. If you had a 4d screen, one could consider 4d examples" ok, I think this makes sense to me, for higher dimensions then attempt to visualize below shapes :

enter image description here

A plot of a graph of anything > 2 dimensions is difficult to draw based on above shapes. So in summary I think if can understand why an algorithm works in 2d then can apply same principles to why algorithm should work in higher dimensions, given all dimensions are accessible.

  • $\begingroup$ You can project 4d to 2d, but it's still not 4d. You can have outliers that are projected right into a cluster. But the visualization is not part of LOF. $\endgroup$ – Anony-Mousse Sep 23 '14 at 13:03
  • $\begingroup$ @Anony-Mousse "the visualization is not part of LOF" the visualization is the outcome of LOF according to Wikipedia, ive updated LOF screenshot in original question. $\endgroup$ – blue-sky Sep 23 '14 at 13:31
  • $\begingroup$ No, the visualization is not the outcome of LOF. It's a visualization of the outcome of LOF. The visualization is a part of ELKI, not of LOF. ELKI does allow visualization of more than 2d; I've tried it. But it's not a limitation of LOF at all. LOF produces numbers, not figures. $\endgroup$ – Anony-Mousse Sep 23 '14 at 15:23
  • $\begingroup$ @Anony-Mousse "LOF produces numbers" I agree, those numbers are plotted on ELKI LOF visualization. Apologies, my language may have been ambiguous. $\endgroup$ – blue-sky Sep 23 '14 at 15:48
  • $\begingroup$ So, which part of the question is about LOF? I guess it's not the same question as stats.stackexchange.com/questions/115421/… again? $\endgroup$ – Anony-Mousse Sep 23 '14 at 16:15

There is nothing specific to 2 dimensions in that article at all - what makes you think it only works in 2d? 2 dimensional data is just what your screen can present, so the figures are 2d. If you had a 4d screen, one could consider 4d examples...

The example uses Euclidean distance, which is defined as

$$ d(x,y) = \sqrt{\sum_{i=1}^d (x_i-y_i)^2} $$

which obviously is not restricted to 2 dimensions.

However, due to the Curse of dimensionality (Wikipedia), distance functions tend to work much worse in high dimensionality than they do in low dimensionality.

As far as I can tell, LOF should work with any distance function. It's just less intuitive... - in contrast to k-means, which minimizes variance and thus squared Euclidean distance; but can actually stop converging with other distances. Since LOF is not iterative (and LOF does not use centroids), this cannot happen in LOF.

  • $\begingroup$ please see update $\endgroup$ – blue-sky Sep 23 '14 at 12:26
  • $\begingroup$ The figure in the Wikipedia article is not part of LOF. It's not from the original LOF article, is it? $\endgroup$ – Anony-Mousse Sep 23 '14 at 13:02
  • $\begingroup$ its not from original article but from Wikipedia "LOF scores as visualized by ELKI. While the upper right cluster has a comparable density to the outliers close to the bottom left cluster, they are detected correctly." $\endgroup$ – blue-sky Sep 23 '14 at 13:30

Algorithms that rely on general linear algebra principles will usually still work if you change from 2 dimensional data to 3 dimensional data.

To give an example, kmeans works by picking k points and assigning all your data points to the closest of the k points. Once you've assigned a group for each point, you take each group and find the center. Then you iterate through your points but this time you assign them to the closest center (then repeat this process until your assignments don't change).

We require two operations for this algorithm to work. We need to be able to calculate the distance between two points and we need to be able to center if a group of points. Both of those operations are defined data of any dimensionality so kmeans works no matter if your data has 2 or n dimensions.

However, in general the answer is no. Not all algorithms work well on high dimensional data, because the more dimensions you have, the more data points you will need to say something meaningful about how the data behaves in the given dimension. For data with high dimensions this can quickly become computationally intractable or require more training samples than you have access to.

  • $\begingroup$ please see update $\endgroup$ – blue-sky Sep 23 '14 at 12:26

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.