2.最邻近规则分类KNN算法(K-Nearest Neighbor)

书诚小驿2025/05/17算法知识库Algorithm

一、概述

1、综述

Cover 和 Hart 在 1968 年提出了最初的邻近算法
分类(classification)算法
输入基于实例的学习(instance-based learning), 懒惰学习(lazy learning)

2、算法详述

步骤：

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

2、细节:

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

Euclidean Distance 定义：

其他距离衡量：余弦值（cos）, 相关度（correlation）, 曼哈顿距离（Manhattan distance）

3、举例

4、算法优缺点

优点：

简单，易于理解，易于实现，无需估计参数，无需训练
适合对稀有事件进行分类
特别适合于多分类问题(multi-modal,对象具有多个类别标签)
适合于对数据分布不了解的情况
无数据输入假定
可以给出数据集的总体模型

缺点：

计算复杂度高，空间复杂度高，需要大量空间储存所有已知实例
样本不平衡问题（majority class problem）
一般数值很小的类容易被忽略
可理解性差，无法给出像决策树那样的规则
无法给出数据的基础结构信息，无法知道数据内在的规律

5、算法改进

选择合适的 K 值
选择合适的距离衡量方法
选择合适的核函数
选择合适的分类决策规则
选择合适的分类器
选择合适的算法

二 2、算法实现

Knn 算法源码open in new window

1、数据集介绍：

虹膜：

萼片长度，萼片宽度，花瓣长度，花瓣宽度 (sepal length, sepal width, petal length and petal width)

150 条数据集:

类别： Iris setosa, Iris versicolor, Iris virginica.

2、利用 Python 的机器学习库 sklearn: `SkLearnExample.py`

from sklearn import neighbors
from sklearn import datasets

knn = neighbors.KNeighborsClassifier()

# 加载鸢尾花数据集

iris = datasets.load_iris()

# 保存数据
# f = open("iris.data.csv", 'wb')
# f.write(str(iris).encode('utf-8'))  # 将字符串编码为字节
# f.close()

# 加载鸢尾花数据集
print(iris)

# 使用鸢尾花数据集的特征和目标标签训练 KNN 模型。
knn.fit(iris.data, iris.target)
# 对一个新的样本 [6.3, 2.7, 4.9, 1.8] 进行预测，返回预测的类别标签。
predictedLabel = knn.predict([[6.3, 2.7, 4.9, 1.8]])
print("predictedLabel is:", predictedLabel) # [2]

三、`KNNImplementation.py`实现 Knn 算法

import csv
import random
import math
import operator


def loadDataset(filename, split, trainingSet=[], testSet=[]):
    with open(filename, 'r', encoding='utf-8') as csvfile:  # 使用 'r' 模式打开文件
        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 getNeighbors(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  # 将 return 放在循环外面


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.67
    loadDataset(r'D:\irisdata.csv', 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) + '%')

if __name__ == '__main__':
    main()

2.最邻近规则分类KNN算法(K-Nearest Neighbor)

目录