Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 3 down vote favorite

Let's say I have a set of discrete, arbitrary variables sampled at continuous co-ordinates, e.g.

==================================
= x       = y       = Value      =
==================================
= 4.1     = 3.4     = A          =
= 4.6     = 7.9     = A          =
= 4.7     = 8.1     = A          =
= 2.1     = 5.0     = B          =
= 3.5     = 9.0     = B          =
= 7.0     = 1.1     = C          =
= 9.8     = 4.2     = C          =
==================================

I would like to generate a map showing the distribution of the values across a range of co-ordinates (e.g. 0<x<=10, 0<y<=10), where each value has an arbitrary colour assigned, and every point within those co-ordinates has a calculated interpolated value, where it is reasonable to do so.

E.g. we give a colour to each of A, B and C.

the point (5.0,5.0) is in the middle of the cluster of As so should be coloured as per A.

the point (7.0,4.0) is between the As and Cs so the colour should be calculated via some analysis of distance to each of those surrounding points.

Broadly I would expect the top-left quadrant to be a colour assigned to B, the bottom right quadrant to be a colour assigned to C, with a band of colour assigned to A between and the point at which the boundaries between the 3 colours occur calculated via some kind of nearest-neighbour algorithm.

Are there any existing algorithms to map the kind of information I wish to display? It should take into account any inliers (if that's the right term).

share|improve this question
1  
What kind of thing or observation do these values represent? – whuber♦ Oct 26 '11 at 21:03
survey responses from people at given geographical locations – meepmeep Oct 27 '11 at 10:06
Ah! What sense does it make to interpolate categorical survey responses over a map, then? Your answer to this will suggest appropriate interpolation methods. – whuber♦ Oct 27 '11 at 16:46

1 Answer

up vote 4 down vote

First thing that popped to my mind were Voronoi diagrams, though those are not inlier-safe.

If you do have a lot of noise, explore kNN algorithms.

share|improve this answer
1  
In the GIS world--which is the natural place to look for tools to solve this problem--Voronoi diagrams are also known as Thiessen polygons and Euclidean allocations. Some people use ad hoc methods to remove the inliers, such as performing morphological operations or local filtering (e.g., a majority filter) to clean the resulting images. – whuber♦ Oct 26 '11 at 18:44
Inliers are naturally down-weighted by a kNN-like algorithm. Depending on how the inliers come about, cleaning may or may not work. In particular, for extended boundaries between classes, there will be lines where majority will not work because it is simply 50/50. In fact there are classifiers that are based on that property. – adavid Oct 26 '11 at 18:58
I didn't say these were good methods; I was just reporting what people do :-). However, if there's an "extended line" bounding a region, it doesn't sound like it would qualify to be an inlier and probably should be kept as is. Or do you perhaps have a probability model for these data that underlies your thinking? – whuber♦ Oct 26 '11 at 21:00
Not really. And multi-dimensional PDF estimation sounds like a challenge. – adavid Oct 26 '11 at 21:32
thank you, knn looks exactly the algorithm I am looking for, and lots of lovely pre-existing code :) – meepmeep Oct 27 '11 at 11:06
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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