KNN算法ruby实现

February 17, 2013

###背景

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

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

readable angular tests

In this post, I'll provdes some tips to create readable angular test.### General Tips#### Use describe or nested describe to structure sp...… Continue reading

Exposing event stream from monolith

Published on September 18, 2017