本篇博客是基于以Kaggle中手写数字识别实战为目标，以KNN算法学习为驱动导向来进行讲解。
写这篇博客的原因
写下这篇博客，很大程度上是希望能记录和督促自己学习机器学习的过程，同时也在以后的学习生活中，可以将以前的博客翻来看看，重新回顾知识。
什么是KNN?
在模式识别和机器学习中，k-近邻算法(以下简称:KNN)是一种常用的监督学习中分类方法。KNN可以说是机器学习算法中最简单的一个算法，我希望它能带领大家走进机器学习，了解其中最基本的原理，并应用于实际生活中。KNN的工作机制非常简单，它是一种处理分类和回归问题的无参算法，简而言之就是通过某种距离度量，计算出测试集与训练集之间的距离，选取前k个最近距离的训练样本，从这k个中选出训练样本中出现最多的类型来作为测试样本的类型。
k-近邻算法的一般流程 ：
(1)收集数据：可以使用任何方法。
(2)准备数据：格式化数据格式。
(3)分析数据：可以使用任何方法。
(4)训练算法：K-近邻算法不涉及训练。
(3)测试算法：计算错误率。
(3)使用算法：输入样本数据，进行分类。
名词解释与案例分析：
以手写数字识别为例进行说明：
训练集：一组有标签的数字图像，即每张图片，我们都对它进行了标注，表明这张图片所显示的数字是多少。在本案例中，所有的图片都是以矩阵的形式保存在数据集中。
测试集：一组没有标签的数字图像，即给出了一组图片，但是并没有对它进行标注，即它的类型是什么，我们也不清楚。
分类：比如手写数字识别中，给出一张图片，我们可以清楚的分辨，上面所写的数字，但是计算机，并不能有效的识别出来，因此机器学习的一个应用便是让计算机从已知分类情况，推断未知情况的类别。
回归：拿函数来说，一个函数在图像上是连续，且有一定规律的时候，我们可以通过函数去算出未知的情况。计算机就是通过已知情况，然后模拟生成一个函数，去拟合这样一个模型，从而推断出未知的情况。
距离度量：欧式距离、曼哈顿距离、切比雪夫距离。
样本：在本篇博客中，每个样本就是一张数字图片，测试集中的样本集，即每一张测试样本都是没有分类的。而训练集中的样本集，都是有明确的分类。
这里，博主只是使用了最基本的KNN算法进行手写数字识别，通过计算欧式距离，达到计算机对手写数字识别和分类。
kaggle实战
在Kaggle中，有一场比赛是knowledge类型的。嗯，就决定是你了！
首先从Kaggle中下载训练集及测试集。点开训练集，可以看见训练集是由42000张数字图片组成，我们可以将它转换为一个420001的标签矩阵和一个42000784的像素矩阵。（注：normaling函数和toInt函数是对返回的数据进行格式化。后面会对函数进行说明。）
# 读取Train数据
def loadTrainData():
filename = 'train.csv'
with open(filename, 'r') as f_obj:
f = [x for x in csv.reader(f_obj)]
f.remove(f[0])
f = array(f)
labels = f[:,0]
datas = f[:,1:]
# print(shape(labels))
return normaling(toInt(datas)), toInt(labels)
打开测试集。因为测试集并没有分类，因此并没有标签。所以可以将这个测试集转换为28000*784的像素矩阵。
#读取Test数据
def loadTestData():
filename = 'test.csv'
with open(filename, 'r') as f_obj:
f = [x for x in csv.reader(f_obj)]
f.remove(f[0])
f = array(f)
return normaling(toInt(f))
前面提到的normaling函数是为了将数据集进行归一化，归一化的目的是为了解决数据指标之间的可比性，防止某些数据过大，导致分类结果的偏差较大。
#归一化数据
def normaling(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
m = dataSet.shape[0]
denominator = tile(ranges, (m, 1))
molecular = dataSet - tile(minVals, (m, 1))
normData = molecular / denominator
return normData
而toInt函数是因为从csv文件中得到的数据都是字符串类型，但是测算距离度量是对于数值类型的，因此需要将字符串类型转换为数值类型。
#字符串数组转换整数
def toInt(array):
array = mat(array)
m, n =shape(array)
newArray = zeros((m, n))
for i in range(m):
for j in range(n):
newArray[i,j] = int(array[i,j])
return newArray
那么KNN算法的核心就是通过计算测试集中每一个测试样本与训练集的距离，选取与测试集最近的k个训练样本，再从这k个样本中，选取出现最多的类型作为训练样本的类别。因此计算测试样本和训练集之间的距离如下面代码所示:
# 核心代码
def k_NN(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
sortDisn = argsort(distances)
# print("sortDisn shape: ",sortDisn.shape)
# print("labels shape:",labels.shape)
classCount = {}
for i in range(k):
# print(sortDisn[i])
# print(type(sortDisn[i]))
vote = labels[sortDisn[i]]
# print("before :",type(vote))
vote = ''.join(map(str, vote))
# print("after :", type(vote))
classCount[vote] = classCount.get(vote, 0) + 1
sortedD = sorted(classCount.items(), key=operator.itemgetter(1),
reverse=True)
return sortedD[0][0]
将以上的代码进行整合，即可把测试集的数据进行分类。
#!/user/bin/python3
# -*- coding:utf-8 -*-
#@Date :2018/6/30 19:35
#@Author :Syler
import csv
from numpy import *
import operator
# 核心代码
def k_NN(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
sortDisn = argsort(distances)
# print("sortDisn shape: ",sortDisn.shape)
# print("labels shape:",labels.shape)
classCount = {}
for i in range(k):
# print(sortDisn[i])
# print(type(sortDisn[i]))
vote = labels[sortDisn[i]]
# print("before :",type(vote))
vote = ''.join(map(str, vote))
# print("after :", type(vote))
classCount[vote] = classCount.get(vote, 0) + 1
sortedD = sorted(classCount.items(), key=operator.itemgetter(1),
reverse=True)
return sortedD[0][0]
#读取Train数据
def loadTrainData():
filename = 'train.csv'
with open(filename, 'r') as f_obj:
f = [x for x in csv.reader(f_obj)]
f.remove(f[0])
f = array(f)
labels = f[:,0]
datas = f[:,1:]
# print(shape(labels))
return normaling(toInt(datas)), toInt(labels)
#读取Test数据
def loadTestData():
filename = 'test.csv'
with open(filename, 'r') as f_obj:
f = [x for x in csv.reader(f_obj)]
f.remove(f[0])
f = array(f)
return normaling(toInt(f))
#归一化数据
def normaling(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
m = dataSet.shape[0]
denominator = tile(ranges, (m, 1))
molecular = dataSet - tile(minVals, (m, 1))
normData = molecular / denominator
return normData
#字符串数组转换整数
def toInt(array):
array = mat(array)
m, n =shape(array)
newArray = zeros((m, n))
for i in range(m):
for j in range(n):
newArray[i,j] = int(array[i,j])
return newArray
#保存结果
def saveResult(res):
with open('res.csv', 'w', newline='') as fw:
writer = csv.writer(fw)
writer.writerows(res)
if __name__ == '__main__':
dataSet, labels = loadTrainData()
testSet = loadTestData()
row = testSet.shape[0]
# print("dataSet Shape:",dataSet.shape)
# print("labels Shape before",shape(labels))
labels = labels.reshape(labels.shape[1],1)
# print("labels Shape after reshape ", shape(labels))
# print("testSet Shape",testSet.shape)
resList = []
for i in range(row):
res = k_NN(testSet[i], dataSet, labels, 4)
resList.append(res)
print(i)
saveResult(resList)
那么把这个数据结果提交到Kaggle上，结果如何呢？
总的来说，这次结果还是很满意的。毕竟KNN算法算是机器学习算法中比较基础的一个算法，能够达到97.185%的准确率，且有66%的排名已经算是很不错的啦~
优点:
简单、易于理解，易于实现，无需训练。
适合对稀有事件进行分类。
特别使用于多分类问题，KNN比SVM的表现更好。
缺点:
KNN算法是基于实例的学习或者说是一种“懒惰学习”。使用算法的时候，我们必须有尽量接近实际数据的训练样本数据，这很大程度是因为它并没有训练模型这样一个步骤，导致它必须保存所有数据集。一旦数据集很大，将导致大量的存储空间。而且加上每次对样本的分类或回归，都要对数据集中每个数据计算距离值，实际使用会非常耗时。其次，它受“噪声”影响很大，尤其是样本不平衡的时候，会导致分类的结果偏差很大。加上它的另一个缺陷是无法给出任何数据的基础结构信息，并不能知道测试集与训练集之间具有什么特征。
优化方法
现在KNN算法的改进主要分成分类效率和分类效果两方面。
一种流行的增加精准率的方法是使用进化算法去优化特征范围。
另一种则是通过各种启发式算法，去选取一个适合的K值。
不管是分类还是回归，都是根据距离度量来进行加权，使得邻近值更加平均。
总结
KNN算法对于分类数据是最简单最有效的算法，它能帮助我们迅速了解监督学习中的分类算法的基本模型。
参考
Github地址：https://github.com/578534869/machine-learning
（欢迎follow，互相学习，共同进步！