概述
对于分类问题，最主要的任务就是找到对应数据合适的分类。而机器学习的另一项任务就是回归，比如CTR预测之类的。ml算法按照有无label可以分为有监督学习和无监督学习，对于无监督学习的算法比较经典的有聚类算法，有监督的相对来说较多，回归类算法基本都是的。按照参数有可以划分成有参数模型和无参数模型和半参数模型，有参数模型有两个特征，一个是用参数代表从训练数据中获得的信息，只有当target function包含在了hypothesis set里面才会收敛。无参数模型是没有参数的，直接存储所以的训练数据，也就是不再用参数代表训练数据，比如KNN，无训练过程，而且一定收敛。对于半参数模型，参数一定有，但是一定收敛，最经典的就是神经网络模型，神经网络模型在理论上是可以拟合所有的target function，所有只要训练数据够多，一定可以收敛，因为他的hypothesis set包含了所以的target function。
如何选择算法，需要考虑两个方面：首先是使用这个算法的目的是什么，想要完成什么任务，其次就是数据怎么来，规模多大。开放ml程序一般要经历一下步骤，首先是收集数据，准备输入数据，也就是数据预处理，分析输入数据，训练算法。
KNN Algorithm
KNN算法是属于近邻算法的一种，之前的Chapter 6一章就有专门提到。KNN的VC维是无穷的，但是效果缺不会差过最优分类器的两倍，Chapter 6博客中有证明。这个算法优点很明显，没有training cost，因为他根本没有训练过程，所以很简单，拿到直接上手预测，所以需要存储完整的训练数据来预测测试数据；预测精度高，对异常值不敏感，偶尔有几个值超出预期对于预测不会有太大影响；另外也没有数据的假定输入。
没有十全十美的事物，training cost其实不是没有了，而是转换到了预测阶段，而且空间复杂度高，需要每一次都计算distance然后sort by order。
工作原理就很简单了，首先找到一个样本数据集合，也称作训练样本集，并且样本中每一个数据都存在label，也就是知道每一个样本和分类之间的对应关系。输入新的数据后，会计算与当前新数据点最近的k个数据，最后选择k个样本中classification最多的组合，通常对于k的选择是不能被类数所整除，避免有两个类的voting是相同的，事实上就是相当于一个poll，投票选举。
计算前就涉及到了相似度的衡量，前面的文章也提到了。
伪代码
首先要计算已知类别数据集中的点与当前点之间的距离。
然后就是排序，
选取最近的K个点，
确定k个点钟类别出现的频率，
频率最高的类别就是当前新数据点的类别。
当然，K的选择一搬就是3，越高，其实越好，但是，你的回报是无法和计算代价所平衡。比如k = 3，accuracy = 97%，k = 5，accuracy = 97.1%，这样就很不值得了，不应该为百分之一的提升增加这么多的计算机消耗。
from numpy import *
import operator
class KNN(object):
@staticmethod
def classify(inX, dataSet, labels, k):
datasetsize = dataSet.shape[0]
diffmat = tile(inX, (datasetsize, 1)) - dataSet
sqdiffMat = diffmat ** 2
sqdistance = sqdiffMat.sum(axis=1)
distance = sqdistance ** 0.5
sortDistance = distance.argsort()
classcount = {}
for i in range(k):
voteLabel = labels[sortDistance[i]]
classcount[voteLabel] = classcount.get(voteLabel, 0) + 1
sortclasscount = sorted(classcount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortclasscount[0][0]
这就是具体实现。比较烦的就是上面的numpy.tile，这个方法是复制数组方法，第二个参数有两个(a,b)，意思是把第一个参数先纵向复制a次，再横向复制b次，这么做是因为要用一个数据点减去所以的训练集，这么多相同的直接复制就好了。
使用KNN改进约会网站配对效果
约会网站会提供三种类型的人选，不喜欢的人，魅力一般的人，极具魅力的人。
实现步骤
收集数据，拿到提供的文本数据
准备数据，使用Python来解析文本文件
分析数据，画图
训练算法，KNN是没有training的，所以可以忽略，也正因为如此，KNN算法的Ein永远是0
测试算法，用给出的数据做测试
使用算法，投入工程使用
准备数据
数据类似于这样，包含了三种特征，每年获得飞行常客的里程数，玩游戏视频所消耗时间百分比，每周冰淇淋公升数。
显示数据
@staticmethod
def drawDataSet(X, Y):
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(X[:, 1], X[:, 2])
plt.show()
这里只是使用了第一和第二个特征，加上类别颜色：
最后试一下之后会发现，23，13，12列得到的分布差不多一样的，只有12列是不同：
数据归一化
不同数据的大小算出来的距离是不一样的，第一个特征都是以千为单位，而后面两个feature相对较小，所以需要归一化把特征都转换成同一大小单位。
@staticmethod
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataset = np.zeros(shape(dataSet))
m = dataSet.shape[0]
normDataset = dataSet - tile(minVals, (m, 1))
normDataset = normDataset / tile(ranges, (m, 1))
return normDataset, ranges, minVals
测试数据
还是可以的
手写数字识别
所有的手写数字都是这个样子。预测效果，代码就不贴了，很普通。
还是可以的。但是KNN算法如果作用于对图片相似度的话可能不太好，因为图片相等的地方很大程度上是背景相同，有可能导致误识别。比如两张图片，一张是汽车，一张是飞机，两张图片都是大片的天空做背景的话可能就会出现问题。KNN算法是对于实例的学习，使用算法的时候必须接近实际数据的训练样本数据，而且要保存所有的数据，在数据过多的情况下可能导致computational cost，计算开销会很大。而且，他无法给出任何数据的基础结构信息，也无法知道平均实力样本和典例样本有什么特征。
最后附上所有GitHub代码：https://github.com/GreenArrow2017/MachineLeariningnAction
