您的位置:

K 近邻法(K-Nearest Neighbor)

一、K 近邻法是什么?

K 近邻法是一种基本的分类和回归算法,它是一种最简单的机器学习算法之一。该算法通过计算一个点周围 K 个最近邻居的距离来确定该点的类别或值。基于 K 近邻法的分类和回归算法具有简单、直观、易于理解的特点。

二、K 近邻法的原理

K 近邻法的原理是基于距离度量的。当给定一个样本后, K 近邻算法会在训练集中寻找 K 个距离该样本最近的样本点,然后将这 K 个样本点的类别作为预测样本的类别。

其中,距离度量通常采用欧式距离或曼哈顿距离。在分类问题中,K 近邻法采用投票法来确定预测样本的类别。在回归问题中,K 近邻法采用简单平均法来确定预测样本的值。

三、K 近邻法的优缺点

1、优点

K 近邻法非常简单,易于理解和实现,在处理多分类时效果良好,对异常值不敏感。此外,它对于样本空间的默认分布实现文本分类的效果尤为突出。

2、缺点

在处理大规模数据时,计算距离会花费大量时间,而距离计算是 K 近邻算法最耗时的操作。此外,由于 K 近邻算法需要保存全部数据集,因此当数据集很大时,需要占用大量的存储空间。

四、K 近邻法的实现

1、数据准备

在使用 K 近邻法之前,需要先准备数据集。数据集通常包含多个特征和它们所对应的类别或标签。下面是一个简单的数据集示例(其中:X1 和 X2 是两个特征,Y 是类别):

X1	X2	Y
4.5	3.0	setosa
6.7	3.1	versicolor
5.3	2.3	virginica

2、计算距离

计算距离是 K 近邻算法的核心操作之一。常用的距离度量有欧式距离和曼哈顿距离。

以下是采用欧式距离计算样本点 A 与样本点 B 之间距离的示例代码:

import math
def euclidean_distance(point_A, point_B):
    distance = 0
    for i in range(len(point_A)):
        distance += pow((point_A[i] - point_B[i]), 2)
    return math.sqrt(distance)

3、K 近邻分类

在使用 K 近邻法进行分类时,需要计算测试样本点与数据集中所有样本点之间的距离。然后,根据距离排序选取离测试样本点最近的 K 个样本点。最后,根据这 K 个样本点的 class 进行投票,选出出现最多的 class。以下是 K 近邻分类算法的示例代码:

def knn_classification(X_train, y_train, X_test, k):
    distances = []
    for i in range(len(X_train)):
        dist = euclidean_distance(X_train[i], X_test)
        distances.append((dist, y_train[i]))

    distances.sort()
    neighbors = distances[:k]

    class_votes = {}

    for neighbor in neighbors:
        response = neighbor[1]
        if response in class_votes:
            class_votes[response] += 1
        else:
            class_votes[response] = 1

    sorted_votes = sorted(class_votes.items(), key=lambda x: x[1], reverse=True)

    return sorted_votes[0][0]

4、K 近邻回归

K 近邻回归与分类有所不同,它通过简单平均法来确定测试样本点的值。具体操作是:计算测试样本点与数据集中所有样本点之间的距离,并选取离测试样本点最近的 K 个样本点。然后,计算这 K 个样本点的平均值,作为测试样本点的预测值。以下是 K 近邻回归算法的示例代码:

def knn_regression(X_train, y_train, X_test, k):
    distances = []
    for i in range(len(X_train)):
        dist = euclidean_distance(X_train[i], X_test)
        distances.append((dist, y_train[i]))

    distances.sort()
    neighbors = distances[:k]

    avg = 0
    for neighbor in neighbors:
        avg += neighbor[1]

    return avg/k

五、总结

K 近邻法是一种基本的分类和回归算法,具有简单、直观、易于理解的特点。在处理大规模数据时,计算距离会花费大量时间,而距离计算是 K 近邻算法最耗时的操作。由于 K 近邻算法需要保存全部数据集,因此当数据集很大时,需要占用大量的存储空间。