最邻近规则分类KNN算法

本文介绍最邻近规则分类KNN算法–K-Nearest Neighbor。

综述

在1968年是Cover和Hart提出了最初的邻近算法。
属于分类(classification)算法。
输入基于实例的学习(instance-based learning), 懒惰学习(lazy learning)。因为是不建立模型，只通过归类，吧测试集中的实例和学习集中的进行对比。

算法详述

步骤：

为了判断未知实例的类别，以所有已知类别的实例作为参照。
选择参数K，通常不会选择很大，根据实验数据得出，看哪个k值是预测的精确度最高的。
将未知实例放置在空间中，计算未知实例与所有已知实例的距离。
选择最近K个已知实例。
根据少数服从多数的投票法则(majority-voting)，让未知实例归类为K个最邻近样本中最多数的类别。

关于距离的衡量方法

Euclidean Distance 定义实际是二点的坐标计算。
其他距离衡量：余弦值（cos）, 相关度（correlation）, 曼哈顿距离（Manhattan distance）
选择k的时候，要选择奇数，1,3,5等，因为要进行投票，少数服从多数，奇数可以更好的选择出。

案例

把上述的信息模拟成空间的点：把特征值抽象成一个具有多维的空间向量，特征值就是坐标，标记的归类值就是最终的目标。

对k值是很敏感的，比如上图，k为1时，未知为蓝色，k为4时红色，再扩大k值为9时，即为蓝色。所以对k值的选择尤为重要。

优缺点：

优点：

简单
易于理解
容易实现
通过对K的选择可具备丢噪音数据的健壮性
缺点：
需要大量空间储存所有已知实例
算法复杂度高（需要比较所有已知实例与要分类的实例）
当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本。上图中X的归类是比较明显的，可以归为红色。但是对于Y，因为蓝色样本的数量多，占据主导地位。但肉眼的观察，未知样本的是在红色区域更多。所以，容易错误的归类。

改进方法：
因为通过少数服从多数的方法选择会有失偏颇，所以加上对距离的考虑。根据距离加上权重。比如: 1/d (d: 距离）

KNN应用

调用sklearn库完成KNN算法：
from sklearn import neighbors
from sklearn import datasets # 数据库

knn = neighbors.KNeighborsClassifier  # 创建分类器

"""
这是内置好的一个数据集，包含了150个样例，返回的是字典格式，第1部分是
多维的样例数据，第2部分是一维的数据。
"""
iris = datasets.load_iris()  # 返回一个数据集
print(iris)
# fit方法很多地方都会定义，建立模型
# 传入的参数是数据集中的,
# 这里使用的是knn默认的参数，更多参数查看文档
knn.fit(iris.data, iris.target)
pr = knn.predict([[0.1, 0.2, 0.3, 0.4]])
print(pr)

以下是自行实现KNN算法：

import math
import random
import csv
import operator

# 装载数据集


# 实现euclideandistance


# 返回最近的k


# 返回预测的谁归类


# 预测的准确率


import csv
import random
import math
import operator


def loadDataset(filename, split, trainingSet=[], testSet=[]):
    with open(filename, 'r') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        # range(len(dataset) 得出一共多少行
        for x in range(len(dataset) - 1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                trainingSet.append(dataset[x])
            else:
                testSet.append(dataset[x])


def euclideanDistance(instance1, instance2, length):
    'length是维度，在每一维中进行差的运算， instance1, instance2实例'
    distance = 0
    for x in range(length):
        '计算每个维度的平方的和'
        distance += pow((instance1[x] - instance2[x]), 2)
    '开方'
    return math.sqrt(distance)


def getNeighbors(trainingSet, testInstance, k):
    'testInstance: 测试集中的一个实例'
    distances = []
    '维度减去1'
    length = len(testInstance) - 1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors


def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]


def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] == predictions[x]:
            correct += 1
    return (correct / float(len(testSet))) * 100.0


def main():
    # prepare data
    trainingSet = []
    testSet = []
    split = 0.8
    loadDataset(r'./iris.data.txt', split, trainingSet, testSet)
    # print
    # 'Train set: ' + repr(len(trainingSet))
    # print
    # 'Test set: ' + repr(len(testSet))
    # generate predictions
    predictions = []  # 存储将要预测出来的类别的值
    k = 3
    for x in range(len(testSet)):
        neighbors = getNeighbors(trainingSet, testSet[x], k)
        result = getResponse(neighbors)
        predictions.append(result)
        print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
    accuracy = getAccuracy(testSet, predictions)
    print('Accuracy: ' + repr(accuracy) + '%')


main()