k-邻近算法概述

kNN 采用测量不同特征值之间的距离方法进行分类。

工作原理：输入训练数据，即带标签的样本数据集，接着输入没有标签的新数据，将新数据的每个特征与样本集中数据对应的特征比较，选出特征最相似（最邻近）的数据的分类标签，一般只选择数据集中相似度最高的前k个数据，（k<=20)，选择k个最相似数据中分类标签出现最多的那一个作为新数据的分类标签

代码实现（附每一步的解释）

import operator
from numpy import *


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):
    # shape 可以获取矩阵的形状,获取的结果是一个元组，输出行数和列数，shape[0]是行数,应为4
    dataSetSize = dataSet.shape[0]

    # tile 返回的是数组类型，第一个A本身是一个4行2列的数组，reps的第一个数代表行数重复，后一个数代表列数重复
    # 复制测试集，产生与样本数据集相同个数测试用于与每一个样本数据计算距离
    diffMat = tile(inX, (dataSetSize, 1))-dataSet

    # 矩阵各个元素值的平方/开平方
    sqDiffMat = diffMat ** 2

    # 默认的axis=0 就是普通的相加 而当加入axis = 1以后就是将一个矩阵的每一行向量相加
    sqDistances = sqDiffMat.sum(axis=1)

    # 再开根号
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()  # argsort函数返回的是数组值从小到大的索引值

    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]  # 取出前k组中第i个对应的标签

        # dict.get(key, default=None) key 字典中要查找的键 default 如果指定键的值不存在时，返回该默认值。
        # 建立字典，对应的标签+1 统计出最多的一个标签
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # sorted(需要排序的数组, 依据数组的某一列为排序依据, 是否逆序)
    # 在Python 3.x 里面，iteritems()方法已经废除了。在3.x里用 items()替换iteritems()
    # operator模块提供的itemgetter函数用于获取对象的哪些维的数据
    # 对字典进行排序
    sortedClassCount = sorted(classCount.items(),
                              key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


group, labels = createDataSet()
result = classify0([0, 0], group, labels, 3)
print(result)

解析数据

利用上述算法，我们可以改进约会网站，但是需要首先解析一份txt的训练数据：

def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    # 返回来一个给定形状和类型的用0填充的数组；(行数为numberOfLines，列数为3)
    returnMat = zeros((numberOfLines, 3))
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()  # 截取掉所有回车字符
        listFromLine = line.split('\t')  # 用制表符tab将上一行得到的数据分割成一个元素列表
        returnMat[index, :] = listFromLine[0:3]  # index 代表第几行，每行取前三列
        classLabelVector.append(int(listFromLine[-1]))  # 取标签
        index += 1
    return returnMat, classLabelVector

得到对应的数据文本和标签

归一化

由距离计算公式可得
在项目中会发现飞行里程数和其他相差数个数量级，对结果本身造成的影响较大，会覆盖掉其他数据的影响，因此采用(value-min)/(max-min)来对数据进行归一化处理，使三部分权重相同，排除较大数据的影响：

def autoNorm(dataSet):
    minVals = dataSet.min(0)  # 参数0代表从列中取而不是从行中取最小值
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet/tile(ranges, (m, 1))
    return normDataSet, ranges, minVals

预测

有了上述的准备，我们便可以对未来的数据进行预测

def classifyPerson():
    resultList = ['没感觉', '一点点感觉', '很有感觉']
    percentTats = float(input("看游戏视频的时间"))
    # For Python 3.x, use input(). For Python 2.x, use raw_input(). Don't forget you can add a prompt string in your input() call to create one less print statement. input("GUESS THAT NUMBER!").
    ffMiles = float(input("每年飞行常客旅行公里数"))
    iceCream = float(input("每周冰淇淋的公斤数"))
    datingDataMat, datingLabels = file2matrix('ch02\\ch2dataing.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
    classifierResult = classify0(
        (inArr-minVals)/ranges, normMat, datingLabels, 3)
    print("你对他：", resultList[classifierResult-1])