机器学习实战一（kNN）

跟着老师做一个项目，关于行车记录仪识别前方车辆，并判断车距，不太好做。本来是用OpenCV，做着做着，突然发现需要补习一下机器学习的内容。《机器学习实战（machine learing in action）》这本书买了很久了，当时还是看了很多人推荐，不过到现在才想起翻出来看。第二章kNN的例子刚跟着做完，书里讲的很清楚，代码条理分明，只不过我是用Python3实现的。具体的过程不再赘述，只是把自己的理解放在这里。

先来看看书里第一章的部分。

机器学习就是把无序的数据转换成有用的信息。
机器学习横跨计算机科学、工程技术和统计学等多个学科。
机器学习的主要任务，可分为监督学习和非监督学习：监督学习可用于预测目标变量的值，可分为分类，针对离散型目标变量，和回归，针对连续型目标变量；非监督学习不预测目标变量的值，将数据划分为离散的组，则称为聚类，如果还需要估计数据与每个分组的相似度，则为密度估计
步骤：
- 收集数据（前期采集）
- 准备输入数据（数据格式化）
- 分析输入数据（探索型分析）
- 训练算法
- 测试算法
- 使用算法

kNN（k-近邻算法）

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

原理：已知一组数据的属性值和类别标签，给定一个输入数据，判断所属类别。kNN的做法是计算输入数据与所有已知数据的空间距离（欧氏距离），然后从小到大排列，取前k个数据，出现次数最多的类别标签作为输入数据的所属类别。

欧式距离计算：(sqrt {left( x-x_{i} ight) ^{2}+left( y-y_{i} ight) ^{2}+ldots })

核心代码如下：

"""
Created on 2017/12/30 19:13
kNN: k-近邻算法

Input:  inX: 用于判断类别的矩阵 (1xN)
        dataSet: 已知类别的数据集向量 (NxM)
        labels: 数据集的标签 (1xN)
        k: 用于比较的近邻的数量 (应该是奇数)

Output: 最可能的类标签


@author: Lucifer
@site: plantree.me
@email: wpy1174555847@outlook.com
"""
import numpy as np
import os
import operator
# kNN
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    # np.tile()将inX重复(dataSetSize, 1)次
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    # 排序后的索引
    sortedDistanceIndices = distances.argsort()
    classCount = {}
    for i in range(k):
        # 寻找出现次数最的标签
        voteILabel = labels[sortedDistanceIndices[i]]
        classCount[voteILabel] = classCount.get(voteILabel, 0) + 1
    # 字典的排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1),
                              reverse=True)
    return sortedClassCount[0][0]

核心的代码并不算复杂，这里用到了numpy提供的tile()函数，用于将矩阵横向或者纵向复制，然后利用numpy中广播的概念：对于矩阵的操作，会具体到矩阵中每一个元素上，这样计算效率无疑会很高。

书里提供的两个例子：

使用k-近邻算法改进约会网站的配对效果
手写识别系统

两个例子都提供了原始数据，都很有意思，具体代码详见我的GitHub。

这两个例子，有几点经验需要学习。

1、数据格式化

第一步，数据的格式化是非常有必要的。因为现在数据来源广泛，可以来自网络，可以来自文本文件，也可以来自数据库，但是具体到算法，输入数据的格式是固定的，这就有必要进行数据的格式化，但是具体格式化的方式是不固定的，这个要看具体算法输入的要求，像这里输入的数据必须是numpy的array格式，但是数据源是文本文件，这就需要另写方法来自动执行这些转换。

2、数据归一化

不同属性之间的数据，不具备可对比度，有些尺度相差很大，很影响算法执行的效果，因此在真正的输入数据到算法之前，需要进行归一化。其实归一化也很简单，方式也不止一种，比如：

newValue = (oldValue - min) / (max - min)

可以看出，归一化后的数据，范围落在[-1, 1],而且避免了不同尺度数据造成的偏差。

3、探索型数据分析

说是探索型数据分析，显得有些专业，其实就是在具体执行机器学习算法之前，先来看看数据长什么样子。可以采用一些统计参数，如均值和方差等，另外一种很重要的方式就是可视化，Python中最常见的自然是Matplotlib绘图库了，Seaborn也不错，可以尝试学学，可以很直观的看到数据长什么样子。

4、训练集和预测集

通常会将原始数据分割为训练集和预测集，比如90%的数据作为训练集，用于训练模型，剩下10%作为预测集，来预测模型的准确度，由于预测集的预测目标值已知，因此可以通过判断模型输出结果与原有结果比较，得出错误的数量，然后除以预测集总数，即可得到错误率，来表征模型质量。

kNN存在的问题：

训练样本数量较大，而且必须保存全部数据集
对数据集中的每个数据计算距离值，计算量较大，十分耗时
无法给出任何数据的基础结构信息，对于数据的特征并不了解

Next:下一章将使用改率测量方法处理分类问题，即决策树。

总结：初次接触机器学习，从数据中挖掘信息听起来十分诱人，也十分有趣。kNN作为一种比较简单的算法，单纯通过比较与已知数据的距离，这是一种十分别致的思考方式，将属性放在坐标系空间，然后计算空间距离，方法简单，实现起来也比较容易。

Reference：https://github.com/plantree/Machine-Learing-In-Action/tree/master/chapter2

却道，此心安处是吾乡