机器学习实战（k-近邻算法-入门篇）

k-近邻算法概述

k-近邻算法就是采用测量不同的特征值之间的距离进行分类

它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所分类类别的对应关系。输入没有标签的新数据后，将新数据的每个特征最相似数据（最邻近）的分类标签。一般来说，我们只选择样本数据集中的前k个最相似的数据，这就是k-近邻算法中的k的出处，通常k<=20(整数)。最后我们选择k个最相似数据中出现次数最多的分类，最为新数据的分类。

优缺点

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

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

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

k-近邻算法的一般流程

（1）、收集数据：可以使用任何方法

（2）、准备数据：距离计算所需要的数据，最好是结构化的数据格式

（3）、分析数据：可以使用任何方法

（4）、测试算法：计算错误率

（5）、使用算法：首先输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个类，最后应用对计算 出的分类执行后续的处理

电影分类的例子

使用k-近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头。假如有一部看过的电影，如何确定它是爱情片还是动作片？我们可以使用KNN来 解决这个问题。

每部电影的打斗镜头、接吻镜头以及电影评估类型

电影名称	打斗镜头	接吻镜头	电影类型
Colifornia Man	3	104	爱情片
He’s Not Really into Dudes	2	100	爱情片
Beautiful Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Robo Slayer 3000	99	5	动作片
Amped II	98	2	动作片
？	18	90	未知

即使不知道未知电影的类型，我们也可以通过某种方法计算出来。首先计算出未知电影与样本集中其他电影的距离。

现在我们得到了样本中所有与未知电影的距离，按照递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是 He’s Not Really into Dudes 、Beautiful Woman 、 Colifornia Man。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型。而这三部电影全是爱情片，因此我们判定未知电影属于爱情片。

假设这里有五组数据，五个对应的标签以及一组未知标签的数据如下，我们要来预测未知标签的数据属于哪一类

已知数据：

    A   1.0,1.1

    A   1.0,1.0

    B   0.0,0.0

    B   0.0,0.1

    B   0.0,0.1

未知数据

    1.0,1.0

代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
'''
@Time    : 2018/8/13 16:15
@Author  :
@Site    : 
@File    : KNN.py
@Software: PyCharm
'''
from numpy import *
import operator

def createDataSet():
    """
    准备数据集
    A   1.0,1.1
    A   1.0,1.0
    B   0.0,0.0
    B   0.0,0.1
    B   0.0,0.1
    :return: group,labels
    """
    group = array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1], [0.0, 0.1]])
    labels = ['A', 'A', 'B', 'B', 'B']
    return group, labels


def classify(inX, dataSet, labels, k):
    """
     K-近邻算法
    :param inX:用于分类的输入向量
    :param dataSet: 输入的训练样本
    :param labels: 向量的标签
    :param k:用于选择最近邻居的数目
    :return:
    """
    dataSetSize = dataSet.shape[0]                  #获取训练样本的个数
    diffMat = tile(inX,(dataSetSize, 1)) - dataSet  #tile(A,n) 将A重复n次构成一个新的数组
    sqDiffMat = diffMat**2                          #将两向量之间的差值分别平方
    sqDistance = sqDiffMat.sum(axis=1)              #axis=1表述行，axis=0表述列
    distances = sqDistance**0.5                     #开方算出欧氏距离
    sortedDistancesIndex = distances.argsort()      #将距离从小到大排序并将其下表存入sortedDistanceIndex
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistancesIndex[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1   #统计各个标签出现的次数
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

#----------------测试------------------
group, labels = createDataSet()
print(classify([1,1], group, labels, 3))
"""
结果输出:A
"""