算法概述

• 工作原理：

给定一个样本数据集合，作为训练集，该数据集中每条数据都知道其对应的类别标签。输入一个没有标签的新数据，希望根据训练集的样本数据判断该输入数据的类别。

• 求解思想如下：

将输入数据与样本集中的所有数据计算特征距离（相似度），根据距离进行排序，选择距离最近的前k个样本，将该k个样本中出现次数最多的类别作为输入数据的类别。

• 算法特点
  • K近邻算法无需训练，直接计算特征距离即可
  • 优点：对异常值不敏感，精度高，没有假设条件
  • 缺点：计算复杂度高、空间复杂度高（knn算法必须保存所有的数据，如果训练机很大则需要消耗大量的存储空间；此外必须对数据集中的每条数据计算特征距离，实际计算也非常耗时；knn算法也无法给出数据的任何平均信息）

算法简单实现(分类器)

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


'''
knn算法：
1、首先计算输入向量与所有训练集样本之间的特征距离
2、然后根据距离选择距离最近的k个样本
3、k个样本中出现次数最多的类别作为输入向量的类别
'''


def classify0(inX, dataSet, labels, k):
    # 1、首先计算特征距离
    shape = dataSet.shape[0]
    diffSet = tile(inX, (shape, 1)) - dataSet
    disSet = sum(diffSet ** 2, axis=1) ** 0.5

    # 2、选取距离最近的k个样本
    sorteddisSet = argsort(disSet)
    topkDic = {}
    for i in range(k):
        label = labels[sorteddisSet[i]]
        topkDic[label] = topkDic.get(label, 0) + 1  # get(key,default=None)返回字典的某个键对应的值，如果该键不存在则返回默认值

    # 3、将k个样本中出现字数最多的类别作为输入的类别返回
    sortedtopkDic = sorted(topkDic.items(), key=lambda x: x[1], reverse=True)
    return sortedtopkDic[0][0]


# 按间距中的绿色按钮以运行脚本。
if __name__ == '__main__':
    data, labels = createDataSet()
    inX = [1, 1]
    print(classify0(inX, data, labels, 3))

输出：A

KNN实现约会情况预测

import numpy as np
from numpy import *
import operator
import matplotlib
import matplotlib.pyplot as plt


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


'''
knn算法：
1、首先计算输入向量与所有训练集样本之间的特征距离
2、然后根据距离选择距离最近的k个样本
3、k个样本中出现次数最多的类别作为输入向量的类别
'''


def classify0(inX, dataSet, labels, k):
    # 1、首先计算特征距离
    shape = dataSet.shape[0]
    diffSet = tile(inX, (shape, 1)) - dataSet
    disSet = sum(diffSet ** 2, axis=1) ** 0.5

    # 2、选取距离最近的k个样本
    sorteddisSet = argsort(disSet)
    topkDic = {}
    for i in range(k):
        label = labels[sorteddisSet[i]]
        topkDic[label] = topkDic.get(label, 0) + 1  # get(key,default=None)返回字典的某个键对应的值，如果该键不存在则返回默认值

    # 3、将k个样本中出现字数最多的类别作为输入的类别返回
    sortedtopkDic = sorted(topkDic.items(), key=lambda x: x[1], reverse=True)
    return sortedtopkDic[0][0]


def file2matrix(filename):
    '''
    读取文件函数
    :param filename:
    :return:
    '''
    # 1、读取文件
    fr = open(filename, 'r')
    arrayLines = fr.readlines()
    linenum = len(arrayLines)
    fr.close()
    # 2、定义存放文件内容的matrix
    dataMat = np.zeros((linenum, 3))
    labels = []
    index = 0
    # 3、解析文件内容
    for line in arrayLines:
        linesplit = line.strip().split('\t')
        dataMat[index, :] = linesplit[:3]
        labels.append(int(linesplit[-1]))
        index += 1
    return dataMat, labels


def dataNorm(data):
    '''
    对数据进行归一化，采用min-max方法
    :param data:
    :return:
    '''
    # 1、获取数据每列的min，max值
    minVals = data.min(0)
    maxVals = data.max(0)
    range = maxVals - minVals
    # 2、定义存储归一化后数据的数组
    normedData = np.zeros_like(data)
    # 3、进行归一化计算
    num = data.shape[0]
    normedData = data - np.tile(minVals, (num, 1))
    normedData = normedData / np.tile(range, (num, 1))
    return normedData, range, minVals


def datingClassTest():
    '''
    根据已有的约会数据对knn算法进行测试
    :return:
    '''
    # 1、读取数据并进行预处理
    ratio = 0.1
    data, labels = file2matrix('./datingTestSet2.txt')
    normdata, _, _ = dataNorm(data)
    # 2、划分数据集
    numTestval = int(normdata.shape[0] * ratio)
    # 3、计算错误率
    errorcount = 0
    for i in range(numTestval):
        result = classify0(normdata[i, :], normdata[numTestval:, :], labels[numTestval:], 3)
        print("对于第%d条数据，预测结果为 %d,实际结果为 %d" % (i + 1, result, labels[i]))
        if result != labels[i]:
            errorcount += 1

    errorratio = 0.1 * errorcount / numTestval
    print("总的错误率为:%f" % (errorratio))


def classfyPerson():
    '''
    定义使用函数，可以输入特征数据然后返回约会匹配结果
    :return:
    '''
    # 1、获取用户输入
    resultList = ['not at all', 'in small dose', 'in large dose']
    data1 = float(input("每年获得的飞行常客里程数？"))
    data2 = float(input("玩游视频游戏的时间百分比？"))
    data3 = float(input("每周消费的冰激凌公升数？"))
    inputdata = np.array([data1, data2, data3])
    # 2、读取训练集数据
    data, labels = file2matrix("./datingTestSet2.txt")
    normdata, range, minval = dataNorm(data)
    # 3、使用分类函数进行分类
    result = int(classify0((inputdata - minval) / range, normdata, labels, 3))
    print("匹配结果为：", resultList[result - 1])


if __name__ == '__main__':
    # data, labels = createDataSet()
    # inX = [1, 1]
    # print(classify0(inX, data, labels, 3))
    filename = './datingTestSet2.txt'
    data, labels = file2matrix(filename)
    print(data)
    print(labels)

    # 绘制散点图查看数据的分布情况
    # fig = plt.figure()
    # ax = fig.add_subplot(311)
    # ax.scatter(data[:, 1], data[:, 2],15.0*array(labels),15.0*array(labels))
    # ax2=fig.add_subplot(312)
    # ax2.scatter(data[:,0],data[:,1],15.0*array(labels),15.0*array(labels))
    # ax3 = fig.add_subplot(313)
    # ax3.scatter(data[:, 0], data[:, 2], 15.0 * array(labels), 15.0 * array(labels))
    # plt.show()

    # 进行数据归一化处理
    # normData, _, _ = dataNorm(data)
    # print(normData)

    # 进行测试
    # datingClassTest()

    # 使用函数进行输入计算
    classfyPerson()

KNN实现手写数字识别

import numpy as np
from os import listdir
from kNN import *


def img2vector(filename):
    """
    实现图像数据到一维向量的转换
    :param filename:
    :return:
    """
    # 1、先创建存放图像的一维数组
    vector = np.zeros((1, 1024))
    # 2、读取文件
    fr = open(filename)
    for i in range(32):
        line = fr.readline()
        for j in range(32):
            vector[0, i * 32 + j] = line[j]
    return vector


def handwritingClassTest():
    """
    该函数实现使用手写数字数据对knn算法进行测试，计算错误率
    :return:
    """
    # 1、首先读取数据
    trainfile = './trainingDigits'
    testfile = './testDigits'
    trainimg = listdir(trainfile)
    trainSet = np.zeros((len(trainimg), 1024))
    trainlabel = np.zeros(len(trainimg))
    for i in range(len(trainimg)):
        trainSet[i, :] = img2vector(trainfile + '/' + trainimg[i])
        trainlabel[i] = int(trainimg[i][0])
    testimg = listdir(testfile)
    testSet = np.zeros((len(testimg), 1024))
    testlabel = np.zeros(len(testimg))
    for i in range(len(testimg)):
        testSet[i, :] = img2vector(testfile + '/' + testimg[i])
        testlabel[i] = int(testimg[i][0])
    print(trainSet.shape)
    print(trainlabel.shape)
    print(testSet.shape)
    print(testlabel.shape)
    # 数据都是0,1因此无需进行归一化处理
    # 2、调用knn函数计算错误率
    errorcount = 0
    for i in range(len(testSet)):
        result = classify0(testSet[i], trainSet, trainlabel, 3)
        if result != testlabel[i]:
            errorcount += 1
        print("对于第%d张手写数字图像，实际数字为%d,预测结果为%d" % (i, testlabel[i], result))
    print("预测错误率为%f" % (errorcount / float(len(testlabel))))


if __name__ == '__main__':
    # 测试img2vector函数
    # filename='./trainingDigits/0_1.txt'
    # imgtest=img2vector(filename)
    # print(imgtest.shape)
    # print(imgtest)
    handwritingClassTest()