有一句话这样说：如果你想了解一个人，你可以从他身边的朋友开始。
如果与他交往的好友都是一些品行高尚的人，那么可以认为这个人的品行也差不了。
其实古人在这方面的名言警句，寓言故事有很多。例如：物以类聚，人以群分；近朱者赤，近墨者黑。
其实K-近邻算法和古人的智慧想通，世间万物息息相通，你中有我，我中有你。

简述机器学习

在日常生活中，人们很难直接从原始数据本身获得所需信息。而机器学习就是把生活中无序的数据转换成有用的信息。例如，对于垃圾邮件的检测，侦测一个单词是否存在并没有多大的作用，然而当某几个特定单词同时出现时，再辅以考虑邮件的长度及其他因素，人们就可以更准确地判定该邮件是否为垃圾邮件。

机器学习分为监督学习和无监督学习，其中：

（1）监督学习：包含分类和回归。分类，是将实例数据划分到合适的分类中。回归，主要用于预测数值形数据。因为这类算法必须知道预测什么，即目标变量的分类信息，所以称为监督学习。
（2）无监督学习：此时数据没有类别信息，不能给定目标值。在无监督学习中，将数据集合分成由类似的对象组成的多个类的过程称为聚类，将寻找描述数据统计值的过程称为密度估计，此外，无监督学习还可以减少数据特征的维度，以便我们可以使用二维或三维图形更加直观地展示数据信息。

以下是机器学习的主要算法：

监督学习：k-近邻算法（KNN），朴素贝叶斯算法，支持向量机（SVM），决策树，线性回归，局部加权线性回归，Ridge回归，Lasso最小回归系数估计
无监督学习：K-均值，DBSCAN，最大期望算法，Parzen窗设计

注意：K-近邻是监督学习，K-Means是无监督学习

简述K-近邻（KNN）算法

概述

KNN算法非常简单和有效。通过对K个最相似的实例(邻居)对整个训练集进行搜索并汇总这些K个实例的输出变量，可以对一个新的数据点进行预测。对于回归问题，它可能是平均输出变量，对于分类问题，可能是模型(或最常见)类值。
关键在于如何确定数据实例之间的相似性。如果您的属性都具有相同的比例(例如，以英寸为单位)，最简单的技术是使用欧几里得距离，您可以根据每个输入变量之间的差异直接计算该数字。

K近邻（k-Nearest Neighbor,kNN）

KNN可能需要大量内存或空间来存储所有数据，但只在需要预测时才进行计算（或学习）。您还可以随着时间的推移更新和策划您的训练实例，以保持预测准确。
当维数提高时，空间的体积提高得很快，因而可用数据变得很稀疏，这会对算法的性能产生负面影响。这被称为维度灾难。故建议您只使用那些与预测输出变量最相关的输入变量。

K-近邻算法采用测量不同特征值之间的距离方法进行分类。
KNN（K-最近邻）算法是相对比较简单的机器学习算法之一，它主要用于对事物进行分类。
工作原理：首先有一个样本数据集合（训练样本集），并且样本数据集合中每条数据都存在标签（分类），即我们知道样本数据中每一条数据与所属分类的对应关系，输入没有标签的数据之后，将新数据的每个特征与样本集的数据对应的特征进行比较（欧式距离运算），然后算出新数据与样本集中特征最相似（最近邻）的数据的分类标签，一般我们选择样本数据集中前k个最相似的数据，然后再从k个数据集中选出出现分类最多的分类作为新数据的分类。

优缺点

优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算度复杂、空间度复杂。
适用范围：数值型和标称型

数学公式

欧式距离：欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。
(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：

(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：

(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：

算法实现

k-近邻算法的伪代码
对未知类型属性的数据集中的每个点依次执行以下操作：
(1) 计算已知类别数据集中的点与当前点之间的距离；
(2) 按照距离增序排序；
(3) 选取与当前点距离最近的k个点；
(4) 决定这k个点所属类别的出现频率；
(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

应用示例

给一个新的数据时，离它最近的 k 个点中，哪个类别多，这个数据就属于哪一类。
栗子：要区分猫和狗，通过 claws 和 sound 两个feature来判断的话，圆形和三角形是已知分类的了，那么这个 star 代表的是哪一类呢？

k＝3时，这三条线链接的点就是最近的三个点，那么圆形多一些，所以这个star就是属于猫。

KNN算法应用—手写数字识别

KNN算法代码

#-*- coding: utf-8 -*-
from numpy import *
import operator
import time
from os import listdir

def classify(inputPoint,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]     #已知分类的数据集（训练集）的行数
    #先tile函数将输入点拓展成与训练集相同维数的矩阵，再计算欧氏距离
    diffMat = tile(inputPoint,(dataSetSize,1))-dataSet  #样本与训练集的差值矩阵
    sqDiffMat = diffMat ** 2                    #差值矩阵平方
    sqDistances = sqDiffMat.sum(axis=1)         #计算每一行上元素的和
    distances = sqDistances ** 0.5              #开方得到欧拉距离矩阵
    sortedDistIndicies = distances.argsort()    #按distances中元素进行升序排序后得到的对应下标的列表
    #选择距离最小的k个点
    classCount = {}
    for i in range(k):
        voteIlabel = labels[ sortedDistIndicies[i] ]
        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1
    #按classCount字典的第2个元素（即类别出现的次数）从大到小排序
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)
    return sortedClassCount[0][0]

下面介绍如何使用knn算法对手写识别数据进行分类，这里构造的分类系统只能识别数字0到9，数字经图形处理软件处理成具有相同的色彩和大小，宽高为32x32像素，为了便于处理，已将图像转换为文本格式，其效果图如下：

数据集有两个目录，其中目录trainingDigits中包含了1934个例子，命名规则如 9_45.txt，表示该文件的分类是9，是数字9的第45个实例，每个数字大概有200个实例。testDigits目录中包含946个例子。使用trainingDigits中的数据作为训练集，使用testDigits中的数据作为测试集测试分类的效果。两组数据没有重叠。

算法应用步骤如下：

1. 数据准备：数字图像文本向量化，这里将32x32的二进制图像文本矩阵转换成1x1024的向量。循环读出文件的前32行，存储在向量中。

#文本向量化 32x32 -> 1x1024
def img2vector(filename):
    returnVect = []
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect.append(int(lineStr[j]))
    return returnVect

2. 构建训练数据集：利用目录trainingDigits中的文本数据构建训练集向量，以及对应的分类向量

#从文件名中解析分类数字
def classnumCut(fileName):
    fileStr = fileName.split('.')[0]
    classNumStr = int(fileStr.split('_')[0])
    return classNumStr

#构建训练集数据向量，及对应分类标签向量
def trainingDataSet():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #获取目录内容
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))                          #m维向量的训练集
    for i in range(m):
        fileNameStr = trainingFileList[i]
        hwLabels.append(classnumCut(fileNameStr))
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    return hwLabels,trainingMat

3. 测试集数据测试：通过测试testDigits目录下的样本，来计算算法的准确率。

#测试函数
def handwritingTest():
    hwLabels,trainingMat = trainingDataSet()    #构建训练集
    testFileList = listdir('testDigits')        #获取测试集
    errorCount = 0.0                            #错误数
    mTest = len(testFileList)                   #测试集总样本数
    t1 = time.time()
    for i in range(mTest):
        fileNameStr = testFileList[i]
        classNumStr = classnumCut(fileNameStr)
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        #调用knn算法进行测试
        classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print("\nthe total number of tests is: %d" % mTest)               #输出测试总样本数
    print("the total number of errors is: %d" % errorCount)           #输出测试错误样本数
    print("the total error rate is: %f" % (errorCount/float(mTest)))  #输出错误率
    t2 = time.time()
    print("Cost time: %.2fmin, %.4fs."%((t2-t1)//60,(t2-t1)%60))      #测试耗时

if __name__ == "__main__":
    handwritingTest()

运行结果如下：

the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9

the total number of tests is: 946
the total number of errors is: 10
the total error rate is: 0.010571
Cost time: 0.00min, 18.2610s.

利用KNN算法识别手写数字数据集，错误率为1.6%，算法的准确率还算可观。也可以通过改变变量k的值，观察错误率的变化，关于k值的选择，一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的K值。

通过运行以上代码，我们会发现KNN算法的执行效率并不高，因为算法需要为每个测试向量计算约2000次欧氏距离，每个距离计算包括1024个维度浮点运算，全部样本要执行900多次，可见算法实际耗时长，另外，KNN算法必须保存全部数据集，每次需为测试向量准备2MB的存储空间（2个1024x1024矩阵的空间）。所以如何优化算法，减少存储空间和计算时间的开销，需要我们进一步深入学习。

KNN算法应用—电影题材分类

我们知道，电影可以按题材分类，但题材本身是如何定义的？由谁来判定某部电影属于哪个题材？即同一题材的电影会具有哪些公共特征？这些都是在做电影分类时一定要搞清楚的问题。这里以动作片和爱情片为例做简要说明。动作片具有哪些公共特征，使得动作片之间非常相似，却明显有别于爱情片？动作片中也可能有接吻镜头，爱情片中也可能存在打斗镜头，所以，不能简单地依靠是否存在打斗或者接吻来判断一部电影的类型。但很明显的是，动作片中的打斗镜头更多、爱情片中的接吻次数更频繁，基于此类场景在一部电影中出现的次数可用来进行电影分类。

有人曾经统计过很多电影的打斗镜头和接吻镜头，下方图1-1 给出了6部电影的打斗和接吻镜头。假如现在有一部从未看过的电影，你如何判断它属于动作片还是爱情片呢？

图1-1

首先，我们弄清楚这部未知电影中存在多少打斗镜头、多少接吻镜头，图1-1中问号位置是该未知电影出现的镜头数图示，具体见下方表1-1。

表1-1每部电影的打斗镜头数、接吻镜头数及电影评估类型

由图1-1和表1-1，可用将未知电影在图1-1的具体位置标出，利用欧式距离公式，计算出未知电影与样本集中其他电影之间的距离，相见下方表2-2所示。

表2-2 已知电影与未知电影之间的距离

由表2-2所示，显然，如果样本集中所有电影与未知电影之间的距离按照递增排序的话，可以得到k个距离最近的电影，这里假设k=2的话，则未知电影与电影He’s Not Really into Dudes，Beautiful Woman影片类型最为相似，判定未知电影属于爱情片。

KNN算法代码

#-*- coding: utf-8 -*-
import numpy as np
import operator

'''
    trainData - 训练集
    testData - 测试集
    labels - 分类
'''


def knn(trainData, testData, labels, k):
    # 计算训练样本的行数
    rowSize = trainData.shape[0]
    # 计算训练样本和测试样本的差值
    diff = np.tile(testData, (rowSize, 1)) - trainData
    # 计算差值的平方和
    sqrDiff = diff ** 2
    sqrDiffSum = sqrDiff.sum(axis=1)
    # 计算距离
    distances = sqrDiffSum ** 0.5
    # 对所得的距离从低到高进行排序
    sortDistance = distances.argsort()

    count = {}

    for i in range(k):
        vote = labels[sortDistance[i]]
        count[vote] = count.get(vote, 0) + 1
    # 对类别出现的频数从高到低进行排序
    sortCount = sorted(count.items(), key=operator.itemgetter(1), reverse=True)

    # 返回出现频数最高的类别
    return sortCount[0][0]


trainData = np.array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
labels = ['爱情片', '爱情片', '爱情片', '动作片', '动作片', '动作片']
testData = [18, 90]
X = knn(trainData, testData, labels, 3)
print(X)

机器学习—K近邻（k-Nearest Neighbor,kNN）

机器学习—K近邻（k-Nearest Neighbor,kNN）

简述机器学习

简述K-近邻（KNN）算法

概述

优缺点

数学公式

算法实现

应用示例

KNN算法应用—手写数字识别

KNN算法代码

KNN算法应用—电影题材分类