机器学习实战笔记（一）k-近邻算法

k-近邻算法（kNN）的工作原理：
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
一般来说，只选择样本集中前 k 个最相似的数据，通常 k 是不大于20的正式。

k-近邻算法（kNN）的一般流程：
（1）收集数据：可以使用任何方法。
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式。
（3）分析数据：可以使用任何方法。
（4）训练算法：此步骤不适用于k-近邻算法。
（5）测试算法：计算错误率。
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行 k-近邻算法 判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

下面开始算法流程：
（本文是在jupyter中完成，文末有完整代码）

一、准备：简易的导入数据及可视化

from numpy import *  #科学计算包
import operator  #运算符模块
def createDataset():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

这里有4组数据，每组数据有两个我们已知的属性或者特征值。
由于人脑的限制，通常我们只能可视化处理三维以下的事物。因此为了简单的实现数据可视化，对于每个数据点我们通常只使用两个特征。我们将数据点（1,1.1）定义为A类，数据点（0,0.1）定义为B类。

附上绘图代码：

import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

group,labels = createDataset()
data = pd.DataFrame(group,labels)
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
plt.scatter(data[0],data[1])
#以下是描述坐标点
plt.title('A B 坐标图')
ax.text(0.95,0.98,'A')
ax.text(0.95,1.08,'A')
ax.text(0.02,-0.01,'B')
ax.text(0.02,0.08,'B')

学会了python的基本导入数据，解析数据以及简单的可视化。

二、实施kNN分类算法

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

python代码如下：

classify0()函数有4个参数：
inX 用于分类的输入向量
dataSet 输入的训练样本集
labels 标签向量
k 用于选择最近邻居的数目
其中，标签向量的元素数目和矩阵dataSet的行数相同。

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0] #训练样本集的行数
    diffMat = tile(inX, (dataSetSize,1)) - dataSet #diffMat为“特征差” 
    #tile使需要分类的向量（inX）的行数与dataSet相同。
    sqDiffMat = diffMat**2 # “特征差” 平方
    sqDistances = sqDiffMat.sum(axis=1) #按行方向求和
    distances = sqDistances**0.5 #开2次根
    #距离计算结束
    sortedDistIndicies = distances.argsort() #从小到大排列，提取其对应的index(索引)
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]] #得到最近距离的标签
        calssCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #标签值加1
    sortedClassCount = sorted(classCount.items(),\
                             key = operator.itemgetter(1),\
                             reverse = True)
    #classCount.items() 将字典中的所有项，以列表方式返回
    #sorted参数key=operator.itemgetter(1)表示根据标签值排序
    #reverse=True（bool）  降序排列
    return sortedClassCount[0][0]

预测数据所在分类：

classify0([2,1],group,labels,3)

到目前为止，第一个分类器已经构造。我们可以根据这个分类器完成很多分类任务，根据这个分类器也可以构造更多分类算法。

三、测试分类器
检验分类器给出的答案是否符合预期值，答案是否不会出错。很显然，分类器不会百分之白保证结果正确，我们可以使用多种方法检测分类器的正确率。比如我们使用已知答案的数据集去测试，通过大量的测试数据，可以得到错误率（错误结果的次数 / 测试次数）。
不同的算法在不同数据集上的表现可能完全不同。

附上完整代码：

from numpy import *  
import operator 

def createDataset():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0] 
    diffMat = tile(inX, (dataSetSize,1)) - dataSet 
    sqDiffMat = diffMat**2 
    sqDistances = sqDiffMat.sum(axis=1) 
    distances = sqDistances**0.5 
    sortedDistIndicies = distances.argsort() 
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]] 
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 
    sortedClassCount = sorted(classCount.items(),\
                             key = operator.itemgetter(1),\
                             reverse = True)
    return sortedClassCount[0][0]

**

示例一：使用kNN算法改进约会网站的配对效果

**

1.从文本文件解析数据

训练样本：datingTestSet2.txt
链接:https://pan.baidu.com/s/1KjHfyd52pguOV9Q6LY0Vgw 密码:m4ui

将文本记录转换为NumPy的解析程序：

def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()  #读取整个文件所有行，保存在一个列表(list)变量中
    numberOfLines = len(arrayOLines)   #获取文件行数
    returnMat = zeros((numberOfLines,3))  #创建对应的零矩阵
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()   #删除 表示开头或结尾的字符
        listFromLine = line.split('\t')  #根据水平制表符（\t）切片
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

代码的思想是，首先我们要知道文本文件有多少行。打开文件，获取文件的行数。创建以零填充的矩阵NumPy。循环处理文件中的每行数据，首先使用 line.strip() 截取掉所有回车字符，然后使用tab字符（制表符 \t）将整行数据分割为一个元素列表。需要的注意的是，我们应该明确的告诉解释器列表中存储的元素值类型，不解释则以字符串来处理。

获取数据：

datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')

2.数据可视化

用散点图来观察数据。

这里选取的是数据的第2行和第3行来观察。

再选取第1行和第2行观察。

很明显第二幅图更好的反映数据。
所以有时候数据的选取对于观察有很大的影响。

单单通过图形化数据无法得出我们想要的准确分析以及结果，我们需要进行下一步计算。

绘图代码：

#选取第2行和第3行
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1], datingDataMat[:,2],\
          15.0*array(datingLabels), 15.0*array(datingLabels))
#选取第1行和第2行
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,1],\
          15.0*array(datingLabels), 15.0*array(datingLabels))

3.归一化数值

特征值之间的数字差值会对计算结果产生很大的影响，差值越大影响越大。比如我们有两个特征值分别是 飞行距离：1300 ，玩ps游戏所占时间百分比： 0.2 。很显然，飞行距离对计算结果的影响是很大的，这时候就需要对数据进行归一化，将取值范围统一到 0到1 之间。

计算公式：newValue = （oldValue - min）/（max - min）

即是（特征值与最小特征值）之间的差值 与 （最大特征值与最小特征值）之间的差值 的（比值）。

def autoNorm(dataSet):
    minValue = dataSet.min(0) #参数0是从列选取最小值，返回一个数组
    maxValue = dataSet.max(0)
    ranges = maxValue - minValue #max - min
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0] #获取行总数
    normDataSet = dataSet - tile(minvalue,(m,1)) #oldValue - min
    normDataSet = normDataSet/tile(ranges,(m,1)) 
    return normDataSet,ranges,minvalue

4.测试算法

使用错误率来检验算法。

def datingclassTest(filename):
    hoRatio=0.10 #测试比例
    datingDataMat,datingLabels = file2matrix(filename)
    normMat, ranges, minvalue = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount=0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:],\
                                    datingLabels[numTestVecs:m], 3)
        print('the classifier came back with: %d, the real answer is: %d'\
             %(classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]):
            errorCount += 1.0
    print("the total error rate is: %f"%(errorCount/float(numTestVecs)))

在 m = normMat.shape[0] 这一步，便决定来用来测试和训练的样本集的数量。

可以改变hoRatio的值 以及变量 k 的值来检测错误率是否随着变量值变化而增加。

5.使用算法

使用算法时便根据具体的运用编写具体的代码。

参考资料：机器学习实战