title
lemene发表于 2016-10-28 08:18:00
概述
k近邻（k nearest neighbor）算法是一种监督算法，用于分类。它基本思想是计算新实例和训练集元素的**距离**，找出k个最接近的实例（neighbor），统计它们所属分类，次数最多的类别作为新实例的类别。
原理与步骤
监督算法可大致分成两个步骤：训练（train）和分类（classify）。从实现考虑还需要算法初始化过程。
本节的代码为python风格的示意代码，不能直接运行，可运行代码参考zxml。
示意代码
class KNearestNeighbor: def __init__(...): pass def train(...): pass def classify(...): pass
训练（train）
理论上k近邻算法不需要训练，可直接使用原始数据进行分类。
归一化
数据的分类的量纲差别较大时，小量纲分类在计算的权重将被削弱。使用归一化消除这种影响。方法如下：
x̂ = (x − xmin)/(xmax − xmin)
预处理
将数据进行某种形式的处理可加快寻找k近邻的速度，常用的处理方式有KD-Tree和Ball-Tree，前者对低维欧氏距离有效，后者对所有距离有效。
示意代码
def train(self, X, C): '''X,C分别代表实例和类别''' # 实例数据归一化，并保留数据备份 (self.X, self.C) = (normalize(X), C.copy()) # 可选，如果需要，则构建KD-Tree() self.tree = KDTree() self.tree.create(self.X)
分类（classify）
分类的大致步骤：找出k个近邻 和*统计类别的次数* 。 分类的部分处理与训练的处理向对应，如：
- 训练对数据进行归一化，则分类是也需要归一化。
- 训练使用如KD-Tree等方式进行处理，则分类使用对应的方法寻找k个近邻。
示意代码
def classify(self, x): _x = normalize(x) # 将x归一化 nearest = self.find_neighbors(_x) # 找出k个近邻 freq = frequency(nearests) # 统计每个类型的次数 return freq.sorted()[-1] # 排序后，返回次数最多的类别 def find_neighbors(self, x): '''寻找与x最接近的k个点''' if self.tree == None: # 判断是否使用了kd-tree ds = self.distance(x, self.X) # 计算所有点的距离 indices = ds.argsort()[0:k] # 排序后，取前面k个 else: indices = self.tree.find_neighbors(x, self.k) # indices是k个近邻的索引位置 return self.C[indices]
初始化（init）
初始化需要设置算法参数，如k的值，距离公式。
距离
实例之间的距离一般采用欧氏距离，但不排除使用其它的距离计算方法。欧氏距离：
d = ∥x − y∥ = √(∑(xi − yi)2) ≥ ∥xi − yi∥
def __init__(self, k, distance=euclidean ): (self.k, self.distance) = (k, distance)
scikit-learn
下面使用scikit-learn中的k近邻算法分类的例子。
import numpy as np from sklearn import neighbors # 准备数据，分成A B两类。A类在[0,0]附近，B类在[1,1]附近。 X = np.array([[0, 0.1], [-0.1, 0], [0.1, 0.1], [0, 0], [1, 1], [1.1, 1], [1, 1.1], [1.1, 1.1]]) C = ['A','A','A','A','B','B','B','B'] # 初始化 clf = neighbors.KNeighborsClassifier(n_neighbors=3, weights="uniform") # 训练 clf.fit(X, C) # 分类 c = clf.predict(np.array([[0.9,0.8]])) print(c)
上面的例子可以将k近邻算法分成三步，初始化、训练和分类。初始化可设置参数，本文涉及到的参数有：
- n_neighbors: 指参数k
- weights: 指定数据分类的权重，归一化 是其中的一个方式。
- algorithm: 该参数可设定使用kd-tree等方法。
- metric: 距离计算公式