Pattern Recognition (Ch 6)

Nearest Neighbor

Nearest Single Neighbor

A nearest neighbor coloring tries to mark each uncolored square with the sample that is closest to it. We will count diagonal squares as 1.5 distance. When there for nearest neighbor tie between two colors, leave the square blank. The example below walks through the process.

Starting, off we know the value of these 6 squares: ../_images/nn1.png
Anything right next to only one known cell is easy - distance of 1 can’t be beat (remember diagonal is distance 1.5):

I have colored the new squares light blue/pink so we do not lose track of which squares are the known samples. We will never color a new square based on one we have “guessed” (a pink/light blue one), only based on the known squares (red/blue).
../_images/nn2.png
The two white squares in the upper right are 1 away from both red and blue. They are a tie. Now let us look at the other two squares. The middle left white square is 1.5 away from blue and from red (diagonal). That is a tie, so it stays white: ../_images/nn3.png
Now the lower right white square. It is 1.5 away from a red and 2.5 away from a blue (sideways = 1, diagonal = 1.5). Red wins, giving us the final coloring shown below. ../_images/nn4.png
Final nearest neighbor coloring. Pink/Blue show squares we can make an educated guess about. White ones we are too unsure about to guess at. ../_images/nn5.png

Nearest 3 Neighbors

Nearest three neighbors is the same idea, but we look at the closest three known values to color each cell. If 2 of the closest known ones are one color and 1 is the other, we chose the color that has 2 “votes”. This prevents say one red square in a sea of blue from having much influence.

Starting from the same known squares: ../_images/nn6.png
The two in the top row are closest to the 2 blue and one red squares… they all become blue: ../_images/nn7.png
These next two cells have these three as “nearest three neighbors: ../_images/nn8.png
This next cell is pink. It is closest to 2 red and 1 blue: ../_images/nn9.png
These all become pink as well. Each is pretty easy to determine visually: ../_images/nn10.png
Now the square above the bottom blue. It is 1 away from the blue below it, 2 away from the blue above it, 2 away from the red below it and 2.5 away from the red above and to the right. 2 blues and one red are closest, so it is blue: ../_images/nn11.png
Those bottom two are closest to the two bottom reds and the one bottom blue… they must be pink: ../_images/nn12.png
Finally, the last square. It is 1.5 from a red and blue (the diagonal neighbors). It is 2.5 away from the upper left blue and lower left red and lower right red. We have a tie for 3rd closest value and the first two closest were split. We will call this a tie. (We could take votes for the most common 3rd closest color, but we will not complicate things by doing so). ../_images/nn13.png
The final result with 3-nearest neighbors.
Notice that compared to Nearest Single Neighbor, we have fewer tied squares and that some of the squares have switched from the nearest neighbor map. The 3-nearest tends to smooth out the pattern and favor contiguous regions of blue and red.
../_images/nn14.png