MachineLearning-KNN

今天呢，我们就要来接触稍微高级一点的东西了，我们所做的事情不仅仅局限于代码的层面上了，要基于某种算法解决问题，而此时的python则是我们完成问题的工具啦！

KNN，即K-近邻算法，一般是用来进行分类的算法。

它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K

根据上面的说明，现在我们举个例子来说明KNN可以用来干啥：

现在我们图书馆有三种类别的书,分别是：教科书，小说书，漫画书，三种书都有各自的特征，那现在图书馆馆长给了我一本新书X，他让我去归类，把它归类到某个类别，我们可以取出三本书的特征，然后数据化，把新书X特征数据手机好，然后对比三种书的特征，与三条数据中的哪个数据最接近，那么新书X就应该是那个类别了！

在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：

同时，KNN通过依据k个对象中占优的类别进行决策，而不是单一的对象类别决策。这两点就是KNN算法的优势。（KNN算法的结果很大程度取决于K的选择）

那下面我们来看看KNN算法是怎样的一个过程吧：

1、计算距离（测试数据与训练数据之间的距离）

2、将距离排序

3、选出距离最小的K个点

4、确认K个点它所在类别出现的频率

5、出现次数最多的标签即为最终类别

了解我们要做什么之后，我们就来选择我们的工具python来完成我们想要做的事情吧！

首先我们得要有数据集和标签吧，如果这些都没有还谈什么标签分类啊

创建数据集和标签

defcreateDataSet():

group = array([[1.0,1.1], [1.0,1.0], [,], [,0.1]])

labels = ['A','A','B','B']

returngroup, labels

下面我们就来看分类方法了

要计算距离我们就得有计算距离的方法吧，我们选择计算欧式距离，这里我们有两种方法来计算距离：

先定义一个KNN算法函数：

defclassify0(inX,dataSet,labels,k):

参数：inX: 用于分类的输入向量

dataSet: 输入的训练样本集

labels: 标签向量

k: 选择最近邻居的数目

方法1：

1. 距离计算

dataSetSize = dataSet.shape[]

# tile生成和训练样本对应的矩阵，并与训练样本求差

diffMat = tile(inX, (dataSetSize,1)) - dataSet

# 取平方

sqDiffMat = diffMat **2

# 将矩阵的每一行相加

sqDistances = sqDiffMat.sum(axis=1)

# 开方

distances = sqDistances **0.5

# 根据距离排序从小到大的排序，返回对应的索引位置

# argsort() 是将x中的元素从小到大排列，提取其对应的index（索引），然后输出到y。

# 例如：y=array([3,0,2,1,4,5]) 则，x[3]=-1最小，所以y[0]=3,x[5]=9最大，所以y[5]=5。

sortedDistIndicies = distances.argsort()

2. 选择距离最小的k个点

classCount = {}

foriinrange(k):

# 找到该样本的类型

voteIlabel = labels[sortedDistIndicies[i]]

# 在字典中将该类型加一

# 字典的get方法

# 如：list.get(k,d) 其中 get相当于一条if...else...语句,参数k在字典中，字典将返回list[k];如果参数k不在字典中则返回参数d,如果K在字典中则返回k对应的value值

# l =

# print l.get(3,0)返回的值是4；

# Print l.get（1,0）返回值是0；

classCount[voteIlabel] = classCount.get(voteIlabel,) +1

3. 排序并返回出现最多的那个类型

# 字典的 items() 方法，以列表返回可遍历的(键，值)元组数组。

# sorted 中的第2个参数 key=operator.itemgetter(1) 这个参数的意思是先比较第几个元素

sortedClassCount =sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

returnsortedClassCount[][]

方法2：

1. 距离计算

# 欧氏距离： 点到点之间的距离

# 第一行： 同一个点 到 dataSet的第一个点的距离。

# 第二行： 同一个点 到 dataSet的第二个点的距离。

# ...

# 第N行： 同一个点 到 dataSet的第N个点的距离。

# [[1,2,3],[1,2,3]]-[[1,2,3],[1,2,0]]

# (A1-A2)^2+(B1-B2)^2+(c1-c2)^2

# inx - dataset 使用了numpy broadcasting

dist = np.sum((inx - dataset)**2, axis=1)**0.5

2. k个最近的标签

k_labels = [labels[index] for index in dist.argsort()[0 : k]]

#将这k个标签存在列表k_labels中

3. 出现次数最多的标签即为最终类别

label = Counter(k_labels).most_common(1)[][]

# 使用collections.Counter可以统计各个标签的出现次数，most_common返回出现次数最多的标签tuple，例如[('lable1', 2)]，因此[0][0]可以取出标签值

returnlabel

ok,两种方法介绍完毕，我们现在来测试一下结果

print(classify0([0.1,0.1], group, labels,3))

输出：B

结果被分到了B类，目测看来还是挺准的！

下面我们用大量的数据做一个手写数字识别（这个网上有好多资料的，我这边就舍远求近了，就写一个大家都听说过的手写数字识别吧！）

导入训练数据

归一化特征值，消除属性之间量级不同导致的影响

参数：dataSet: 数据集

返回：归一化后的数据集normDataSet,ranges和minVals即最小值与范围，

归一化公式：

Y = (X-Xmin)/(Xmax-Xmin)

其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。

将图像数据转换为向量，我们的输入数据的图片格式是 32 * 32的，创建 1 * 1024 的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。

最后我们开始分类了！

之后我们来运行一下代码看一看结果：

准确率还挺高！

大家也来动手试试吧！

资源地址：链接: https://pan.baidu.com/s/1YigcJWaz3gm6ZZixQfxB2A 密码: tiab

代码地址：https://www.bytelang.com/o/s/c/Z_KCdavDCyI=

我可能想强迫你关注这个公众号