Understanding differences between large and small dimensional data when implementing algorithms

Question

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 :

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 :

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.

Answer 1

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.

Answer 2

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.