简单解释：采用测量不同特征值之间距离的方法进行分类的算法。
主要优点是精度高，缺点是计算和空间负责度高，适用于数值型和标称型。
已下是通过Python实现的k-近邻算法，大致思路是计算样本数据data_set中的点与待分类点的距离，按距离递增排序，然后取出前K个点，计算这些点所属标签的数量，计数最高的标签为分类结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
"""
k-近邻算法
"""
import math
import operator
from collections import Counter
def knn(position, data_set, labels, k):
"""
k-近邻算法
:param position: 待分类点
:param data_set: 数据样本
:param labels: 标签集合
:param k: 取值
:return: 所属标签
"""
distance_list = []
for index, item in enumerate(data_set):
distance_list.append((
labels[index],
math.sqrt(reduce(operator.add, [(v - position[i]) ** 2 for i, v in enumerate(item)]))
))
distance_list = sorted(distance_list, key=lambda x: x, reverse=True)
result = Counter([val[0] for val in distance_list[:k]])
result_labels = sorted(result.items(), lambda x, y: cmp(x[1], y[1]), reverse=True)
return result_labels[0][0]
if __name__ == "__main__":
point = [0.2, 0.3]
data_set = [[1, 1.1], [1, 1], [0, 0], [0, 0.1]]
labels = ['A', 'A', 'B', 'B']
k = 3
print knn(point, data_set, labels, k)
|
k-d tree算法
http://www.cnblogs.com/eyeszjwang/articles/2429382.html
k近邻法 给定一个训练数据集，对新输入的实例，在训练的数据集中找到与该实例最近邻的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。
kd树 是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
算法：（构造平衡kd树）
输入：k维空间数据集
$$ T={x_1,x_2,…,x_N} $$,
$$ x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T, i=1,2,…,N; $$
输出：kd树。
生成：
从深度为0的结点开始。重复对深度为j的结点，选择x(l)为切分的坐标轴，l=j(mode k) + 1，以该结点的区域中所有实例的x(l)坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴x(l)垂直的超平面实现。由该结点生成深度为j+1的左、右子结点：左子节点对应坐标x(l)小于切分点的子区域，右子节点对应坐标x(l)大于切分点的子区域。
实例：
对以下给定二维数据集构造一个平衡kd树
$$ T= {(2,3)^T, (5,4)^T, (9,6)^T, (4,7)^T, (8,1)^T, (7,2)^T } $$