【机器学习】最邻近规则分类算法KNN

【机器学习】最邻近规则分类算法KNN(K-Nearst Neighbor)算法

1 综述

1. Cover和Hart在1968年提出了最初的临近算法
2. 分类（classfication)算法
3. 输入基于实例的学习（instance-based learning)，懒惰学习(lazy learning)

2 实例

根据前面的描述与分类结果来预测未知的电影类型是爱情片还是动作片。

3 算法详述

3.1 步骤：

通过坐标画出来，特征值为坐标，结果为分类，预测的未知的看与之前的哪个类最近，或是最邻近的数量最多，就判别它为哪一类。

1. 为了判断未知实例的类别，以所有已知类别作为参照
2. 选择参数K
3. 计算未知实例与所有已知实例的距离
4. 选择最近K个已知实例
5. 根据少数服从多数的投票法则(majority-voting),让未知实例归类为K个最邻近样本中最多数的类别

3.2 细节：

关于K
关于距离的衡量方法：

3.3 代码

# -*- coding:utf-8 -*-
import math

def ComputeEuclideanDistance(x1, y1, x2, y2):
    d = math.sqrt(math.pow((x1-x2), 2) + math.pow((y1-y2), 2))
    return d

d_ag = ComputeEuclideanDistance(3, 104, 18, 90)
d_bg = ComputeEuclideanDistance(2, 100, 18, 90)
d_cg = ComputeEuclideanDistance(1, 81, 18, 90)
d_dg = ComputeEuclideanDistance(101, 10, 18, 90)
d_eg = ComputeEuclideanDistance(99, 5, 18, 90)
d_fg = ComputeEuclideanDistance(98, 2, 18, 90)

print("d_ag: ", d_ag)
print("d_bg: ", d_bg)
print("d_cg: ", d_cg)
print("d_dg: ", d_dg)
print("d_eg: ", d_eg)
print("d_fg: ", d_fg)

结果

离爱情片数据更近，未知电影为爱情片。

4 算法的优缺点

4.1 算法优点

1. 简单
2. 易于理解
3. 容易实现
4. 通过对K的选择可具备丢噪音数据的健壮性

4.2 算法缺点

1. 需要大量空间储存所有已知实例
2. 算法复杂度高（需要比较所有已知实例与要分类的实例）
3. 当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例并不接近目标样本。

5 改进

考虑距离，根据距离加上权重
比如：1/d(d:距离)

6 KNN应用代码

先下载数据loadDataset

# -*- coding:utf-8 -*-
import csv
import random
import math
import operator


def loadDataset(filename, split, trainingSet=[], testSet=[]):
    with open(filename, 'rb') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        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):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)


def getNeigh bors(trainingSet, testInstance, k):


distances = []
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.iteritems(), 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():
    trainingSet = []
    testSet = []
    split = 0.7
    loadDataset(r'D:\iris.txt', split, trainingSet, testSet)
    print("Train set:" + repr(len(trainingSet)))
    print("Test set: " + repr(len(testSet)))

    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("Acurracy:" + repr(accuracy) + "%")


main()