原文链接: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},
]
分类
对于给定的数据,要判断其属于样本数据中的哪一类,需解决如下几个问题:
- 计算给定数据和样本数据之间的距离
- 找出与给定数据距离最小的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}
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
代码的完整版本可以在这里找到。
相关推荐
KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN...
模式识别中的KNN算法实现,基于Matlab的实现,以及剪辑近邻法的matlab实现。
这里通过python的绘图工具Matplotlib包可视化实现机器学习中的KNN算法。 需要提前安装python的Numpy和Matplotlib包。 KNN–最近邻分类算法,算法逻辑比较简单,思路如下: 1.设一待分类数据iData,先计算其到已...
Java实现kNN算法
本算法是Iris数据集使用KNN算法的代码,KNN算法的实现是比较简单的,我使用的是最简单的KNN算法,可以作为借鉴。
KNN算法 C#程序
Python实现KNN算法 Python实现KNN算法 Python实现KNN算法
KNN算法的实现过程,用java实现,很详细的哦
利用Python语言实现kNN算法分类。
机器学习实战 - k近邻算法(KNN算法)总结 适合机器学习实战入门新手 K-近邻算法,又称为 KNN 算法,是数据挖掘技术中原理最简单的算法。 KNN 的工作原理:给定一个已知类别标签的数据训练集,输入没有标签的新数据...
有关于Knn算法相关的Python实现,有多个实现的算法,学校课程设计还有详细的说明实验文档,非常实用
KNN算法JVAA实现邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法可以说是整个数据挖掘分类技术中最简单的方法了。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用她最接近的k个邻居来代表...
机器学习算法实践:knn算法实现分类,计算识别准确率(鸢尾花数据集) 机器学习算法实践:knn算法实现分类,计算识别准确率(鸢尾花数据集) 机器学习算法实践:knn算法实现分类,计算识别准确率(鸢尾花数据集) ...
通过knn算法,实现WiFi室内定位在matlab环境下的仿真
KNN(K-Nearest Neighbor)算法是机器学习算法中最基础、最简单的算法之一,这是一个简单的KNN算法的实现脚本文件,其中有具体的执行代码和提示,
C语言实现的KNN算法,在data文件中导入自己的数据集,在KNN.h中更在自己的K值。array.m中是自己曾经写的一些方便自己的函数,拿在这个算法中将一部分作为套用。
基于 KNN 算法识别水果种类系统的设计与实现代码大全.pdf基于 KNN 算法识别水果种类系统的设计与实现代码大全.pdf基于 KNN 算法识别水果种类系统的设计与实现代码大全.pdf基于 KNN 算法识别水果种类系统的设计与实现...
对4组不同的信号分别采集20组,总共80组,然后经过特征提取(特征数量为8个),得到80x8的矩阵。 划分数据集:将64组数据作为...源程序是利用KNN算法对训练集和测试集整体归一化后的测试数据进行分类,得到分类准确率。
KNN算法综述,详细介绍knn算法的原理与过程
knn算法代码实现及应用实例的所需数据,与代码片“knn算法实现及应用实例代码”配套使用。