KNN算法的ruby实现

原文链接：nicholasren.github.com/2013/02/17/knn.html

背景

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},
]

分类

对于给定的数据，要判断其属于样本数据中的哪一类，需解决如下几个问题：

1. 计算给定数据和样本数据之间的距离
2. 找出与给定数据距离最小的K个样本数据
3. 从这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}
end

2. 找出与给定数据距离最小的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)
end

3. 从这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

代码的完整版本可以在这里找到。