KNN（k-Nearest Neighbor）算法原理

KNN（k-Nearest Neighbor）算法是一种基于实例的学习方法，常用于分类和回归问题。下面是KNN算法的原理和步骤，以及欧式距离和曼哈顿距离的计算原理：

1. 原理

KNN算法基于一个假设：与一个样本最相似的其他k个样本的类别可以用来预测该样本的类别。KNN算法将所有的训练数据看作一个点集，根据他们与新样本之间的距离进行分类。

2. 步骤

KNN算法的实现步骤如下：

• 计算测试数据与训练数据之间的距离（可以使用欧式距离或曼哈顿距离）。
• 选取距离测试数据最近的k个点。
• 统计k个点中各类别出现的次数。
• 将出现次数最多的类别作为测试数据的预测结果。

3. 欧式距离计算原理

欧式距离,也称L2距离，是一种常用的距离度量方式，其计算公式为：

$$d(x,y)=sqrt(sum(xi-yi{)}^2)$$

其中，x和y是两个向量，xi和yi分别表示向量中的第i个元素。

简单来说，欧式距离就是把两个点的各个坐标分别相减后平方再相加，最后再取平方根。

4. 曼哈顿距离计算原理

曼哈顿距离,也称L1距离，也叫城市街区距离，其计算公式为：

$$d(x,y)=sum(|xi-yi|)$$

其中，x和y是两个向量，xi和yi分别表示向量中的第i个元素。

简单来说，曼哈顿距离就是把两个点的各个坐标分别相减后取绝对值再相加。

KNN（K-Nearest Neighbors，K近邻算法）是一种基本的分类和回归算法，它的原理非常简单直观，即通过计算待分类数据点与已有数据集中所有数据点的距离，选择其中距离最小的K个数据点（最近邻），并把它们的类别作为待分类数据点的类别进行分类。

以下是KNN算法的代码实现示例：

import numpy as np
from collections import Counter

def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2)**2))

class KNN:
    def __init__(self, k=3):
        self.k = k
        
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
        
    def predict(self, X):
        y_pred = [self._predict(x) for x in X]
        return np.array(y_pred)
    
    def _predict(self, x):
        #Compute distances between x and all examples in the training set
        distances = [euclidean_distance(x, x_train) for x_train in self.X_train]
        #Sort by distance and return indices of the first k neighbors
        k_idx = np.argsort(distances)[:self.k]
        #Extract the labels of the k nearest neighbor training samples
        k_neighbor_labels = [self.y_train[i] for i in k_idx]  
        #Return the most common class label
        most_common = Counter(k_neighbor_labels).most_common(1)
        return most_common[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

这个代码实现的KNN类可以接受一个超参数K和训练数据集（X_train，y_train），并且能够对给定的测试数据集X做出预测。可以使用以下代码进行测试：

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

data = datasets.load_iris()
X = data.data
y = data.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=123)

knn = KNN(k=3)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)

print("Accuracy:", accuracy_score(y_test, y_pred))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这个示例使用Iris数据集进行分类，随机选择了20%的数据作为测试集。结果将打印出测试集上的准确度分数。