3
$\begingroup$

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).

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    Oct 26, 2011 at 18:44
  • $\begingroup$ 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. $\endgroup$
    – adavid
    Oct 26, 2011 at 18:58
  • $\begingroup$ 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? $\endgroup$
    – whuber
    Oct 26, 2011 at 21:00
  • $\begingroup$ Not really. And multi-dimensional PDF estimation sounds like a challenge. $\endgroup$
    – adavid
    Oct 26, 2011 at 21:32
  • $\begingroup$ thank you, knn looks exactly the algorithm I am looking for, and lots of lovely pre-existing code :) $\endgroup$
    – meepmeep
    Oct 27, 2011 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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