背景
KNN，全称K-nearest-neighbour，是机器学习中最简单的一个分类算法，它的原理是通过对样本数据的学习，对于给定的新的数据，找出与其距离最近的K个样本数据，根据这K个最近样本数据的类别，来确定这个给定数据的类别。
Coolshell上有对这个算法的讲解，我的同事邱俊涛也写了一篇关于KNN算法python实现的文章。本文讲解一个KNN算法的ruby实现。
输入
程序输入格式如下：
x0,x1,x2,…xn|v0
y0,y1,y2,…yn|v1
z0,z1,z2,…zn|v2
每行为一个数据样本，以第一行为例，x0,x1…xn为一个向量，v0为该数据的类别。
学习
从给定文件加载样本数据:
def train file_path
@samples = from_file(file_path)
end@sample的格式如下：
[
{:vector => [x0, x1, x2, …xn], :value => v0},
{:vector => [y0, y1, y2, …yn], :value => v1},
…
{:vector => [z0, z1, z2, …zn], :value => vn},
]
分类
对于给定的数据，要判断其属于样本数据中的哪一类，需解决如下几个问题：
- 计算给定数据和样本数据之间的距离
- 找出与给定数据距离最小的K个样本数据
- 从这K个样本数据中找出样本多的那个分类，即为给定数据的分类。
1. 计算距离
给定两个向量[x0, x1,…xn]，[y0, y1,...yn]计算两个向量之间的距离如下：
(x0 - y0)^2 + (x1 - y1)^2 + … + (xn - yn)^2
因此，对于给定的两个向量a，b，其距离计算逻辑如下：
#a and b are two vectors
def distance_between a, b
a.zip(b).map {|x| x[0] - x[1]}.inject(0){|sum, x| sum += x*x}
end2. 找出与给定数据距离最小的K个样本数据
可以采用计算给定数据与所有样本数据的距离，然后采用最大堆来找出__top k__个样本数据。
def nearest_neighbours candidate, k
heap = MaxHeap.new
@samples.each do |sample|
distance = distance_between(sample[:vector], candidate)
heap.insert Node.new(distance, sample)
end
heap.take_top(k).compact.map(&:sample)
end3. 从这K个样本数据中找出样本多的那个分类，即为给定数据的分类。
对得到的样本根据其类别进行分组，组内元素多的那个类别，即为该给定数据的分类
def value_with_max_vote xs
value_with_votes = xs.group_by{|x| x[:value]}.map{|value, group| {:value => value, :votes => group.length}}
value_with_votes.max_by{|x| x[:votes] }[:value]
end综合上面的几个小任务，我们得到KNN分类算法的实现：
def categorize candidate, k
neighbours = nearest_neighbours_for candidate, k
value_with_max_vote neighbours
end代码的完整版本可以在这里找到。