Implementation of the k-Nearest Neighbour Algorithm (as presented in the lecture "Knowledge Discovery in Databases" at LMU Munich) in Haskell.

knn.hs

module Main where
import Data.List

------------------------------------------------------------------------
-- k Nearest Neighbor Algorithm
------------------------------------------------------------------------

type Distance = Double
class FeatureVector fv where
  dist :: fv -> fv -> Distance

type ClassLabel = Bool

kNearestNeighbor :: (FeatureVector fv) => [(fv, ClassLabel)] -> fv -> Int -> ClassLabel
kNearestNeighbor training new k = voteForClass kNearest
  where
    voteForClass nearest = (countVotesForTrue nearest) >= (k `div` 2)
    countVotesForTrue nearest = length $ [x | x <- nearest, (snd x) == True]
    kNearest = take k $ sortByDist training
    sortByDist = sortBy (\(v1,_) (v2,_) -> compare (dist v1 new) (dist v2 new))

------------------------------------------------------------------------
-- Algorithm Application
------------------------------------------------------------------------

data Simple2DFeature = Simple2D (Integer, Integer)
instance FeatureVector Simple2DFeature where
  dist (Simple2D v1) (Simple2D v2) = manhatten v1 v2
    where manhatten (x1,y1) (x2,y2) = fromIntegral $ (abs $ x1-x2) + (abs $ y1-y2)

main = do
  putStrLn $ "k =  4: " ++ (show $ knr 4)
  putStrLn $ "k =  7: " ++ (show $ knr 7)
  putStrLn $ "k = 10: " ++ (show $ knr 10)
  where
    -- Note: ClassLabel True = Circle, ClassLabel False = Rectangle
    knr = kNearestNeighbor (circles ++ rectangles) $ Simple2D (6,6)
    circles    = let ds = [(1,3), (1,8), (1,9), (4,6), (5,7), (6,8), (7,6)] in
                 map (\v -> (Simple2D v, True)) ds
    rectangles = let ds = [(5,4), (6,1), (6,3), (7,2), (7,4), (8,2), (8,3)] in
                 map (\v -> (Simple2D v, False)) ds