KNN算法的基本思路：
给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把这个输入实例分为这个类。
三个核心要素：
k：邻近的实例个数
距离：如何度量新的输入实例与训练集中样本的距离【如何度量两个样本点的相似程度】
对于n维实数向量空间Rn，使用欧氏距离；
其他的距离/相似度度量方法有：
http://www.cnblogs.com/daniel-D/p/3244718.html
分类决策规则：多数投票等方法实现分类
KNN算法的实现逻辑：
KNN方法的3要素：
1. 距离：Lp距离
2. k的选择：
如果k=1，则近似误差比较小，但是模型整体变得复杂，容易出现过拟合；
如果k=N(样本数)，则近似误差大，模型整体变得简单（预测值都是训练集中出现次数最多的类别），但是忽略了训练实例中的大量有效信息
采用交叉验证的方法来选择k
3. 分类决策规则：
多数表决规则
K邻近算法的实现：kd树
问题：如何对训练数据进行快速的k邻近搜索；在特征空间维数大及训练数据容量大时尤其必要
KNN算法的简单实现：
import numpy as np
import operator
# 训练集
data_set = np.array([[1., 1.1],
[1.0, 1.0],
[0., 0.],
[0, 0.1]])
labels = ['A', 'A', 'B', 'B']
def classify_knn(in_vector,training_data,training_label,k):
"""
:param in_vector:待分类向量
:param training_data:训练集向量
:param training_label:训练集标签
:param k:选择最近邻居的数目
:return:分类器对 in_vector 分类的类别
"""
data_size=training_data.shape[0] # 若data为m行n列的二维矩阵，则data.shape=[m,n], data.shape[0]=m，也就是矩阵的行数
diff_mat=np.tile(in_vector,(data_size, 1))-data_set
sq_diff_mat=diff_mat**2 #array的**指对array中的每个元素求平方
sq_distances=sq_diff_mat.sum(axis=1) #numpy中的sum函数，若没有axis表示所有元素相加，axis=0表示按列相加，axis=1表示按行相加
distance_sorted_index=sq_distances.argsort() #numpy中的argsort()函数，返回sq_distance矩阵中的列元素，按照从小到大的顺序排列得到的索引值
class_count_dict = {} # 用于统计类别的个数
for i in range(k):
label = training_label[distance_sorted_index[i]]
try:
class_count_dict[label] += 1
except KeyError:
class_count_dict[label] = 1
class_count_dict = sorted(class_count_dict.items(), key=operator.itemgetter(1), reverse=True)
# operator.itemgetter(1)表示定义了函数key，获取对象的第一个域的值
# class_count_dict.items()表示返回class_count_dict中可遍历的（键，值）元组数组
return class_count_dict[0][0]
if __name__ == '__main__':
vector = [0, 0.3] # 待分类数据集
print(classify_knn(in_vector=vector, training_data=data_set, training_label=labels, k=3))
参考资料：
