K-近邻算法（一）
k-近邻算法是采用不同特征之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
k-近邻算法的一般流程
（1）收集数据集：可以使用任何方法
（2）准备数据集：距离计算所需要的数值，最好是结构化的数据格式
（3）分析数据：可以使用任何方法
（4）训练数据集：此步骤不适用与k-近邻算法
（5）测试算法：计算错误率
（6）使用算法：首先需要输入样本数据和结构化输出结果，然后运行k-近邻算法判断输入数据分别属于那个分类，最后应用对计算出的分类执行后续的处理。
2.1.1 准备：使用Python导入数据
#createDataSet()
from numpy import *
import operator
def createDataSet():
group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels=['A','A','B','B']
return group,labels2.1.2 实施K-近邻算法
K-近邻算法的伪代码：
对未知属性集中的每个点依次执行以下操作：
（1）计算已知类别数据中心的点与当前点之间的距离
（2）按照距离递增次序排序
（3）选取与当前点距离最最小的K个点
（4）确定当前k个点所在类别的出现频率
（5）返回前k个点出现频率最高的类别作为当前点的预测分类
#K-近邻算法
def classify0(inX,dataSet,labels,k):
dataSetSize=dataSet.shape[0]#计算有多少个点
diffMat=tile(inX,(dataSetSize,1))-dataSet #计算欧氏距离
sqDiffMat=diffMat**2
sqDistance=sqDiffMat.sum(axis=1)
distances=sqDistance**0.5
sortedDistIndicies=distance.argsort()
classCount={}
for i in range(k): #选择距离最小的k个点
voteIlabel=labels[sortedDistIndicies[i]]
classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
sortedClassCount=sorted(classCount.iteritems(), #排序
key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]2.1.3 通过学习函数理解K-近邻算法
看了上述KNN的实现，可能大家还是一头雾水，因为其中用到了很多内嵌函数，所以下面我们就先来学习这些内嵌函数。
1.tile函数
函数形式是tile（A，reps） A的类型几乎所有类型都可以：array,list,tuple,dict,matrix以及基本的数据类型int,string,float,bool等。 reps的类型可以使tuple,list,dict,array,int,bool但不可以是float,string,matrix。
import numpy
numpy.tile(1,(5,1))
array([[1],
[1],
[1],
[1],
[1]])
numpy.tile(2,(5,2))
array([[2, 2],
[2, 2],
[2, 2],
[2, 2],
[2, 2]])
numpy.tile((3,2),(5,2))
array([[3, 2, 3, 2],
[3, 2, 3, 2],
[3, 2, 3, 2],
[3, 2, 3, 2],
[3, 2, 3, 2]])2.shape函数
功能是读取矩阵的长度，输入参数可以是一个整数表示维度，也可以是一个矩阵。 举例说明：
import numpy
array1 = numpy.tile(1,(3,2))
array1
array([[1, 1],
[1, 1],
[1, 1]])
array1.shape
(3L, 2L)
array1.shape[0] #shape[0]表示第一维的长度
3L
array1.shape[1] #shape[1]表示第二维的长度
2L3.sum函数
sum（a,axis=0）或者sum（axis=1） axis=0就是普通的相加，axis=1则是将一个矩阵的每一行向量相加 举例说明：
import numpy
array1 = numpy.tile(1,(3,2))
array1
array([[1, 1],
[1, 1],
[1, 1]])
array1.sum()
array1.sum(axis=1)
array([2, 2, 2])
4.argsort函数
返回数组值从小到大的索引值 举例说明：
import numpy as np
x = np.array([3, 1, 2])
np.argsort(x)
array([1, 2, 0], dtype=int64)
x = np.array([[0, 3], [2, 2]])
x
array([[0, 3],
[2, 2]])
np.argsort(x, axis=0) #按列排序
array([[0, 1],
[1, 0]], dtype=int64)
np.argsort(x, axis=1) #按行排序
array([[0, 1],
[0, 1]], dtype=int64)
x = np.array([3, 1, 2])
np.argsort(x) #按升序排列
array([1, 2, 0], dtype=int64)
np.argsort(-x) #按降序排
array([0, 2, 1], dtype=int64)