KNN

KNN算法英文全称为K-Nearest Neighbors,中文叫做K近邻算法。KNN算法思想极度简单，同时应用的数学知识几乎为0，非常适合入门机器学习。

下图中以二维平面可视化来演示KNN的思想。每个病人的肿瘤大小和时间构成了特征平面的一个点，假如新来了一个数据点(图中绿色的点)那么如何判断其是良性还是恶性肿瘤呢？假设K=3,那么对于每一个新的数据点，KNN算法做的事情是所有的这些点中寻找离这个新的点最近的3个点，红色：蓝色=3：0，因此新的点很可能是恶性肿瘤患者。

image-20250911122335318

上面这个例子我们首先就能发现KNN可以解决监督学习中的分类问题。

接下来先用一个简单的代码示例体验KNN的过程：

  • 构造伪数据，其中绿色点标签为0，红色点标签为1，蓝色点为一个新的数据点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
raw_data_X = [[3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343808831, 3.368360954],
              [3.582294042, 4.679179110],
              [2.280362439, 2.866990263],
              [7.423436942, 4.696522875],
              [5.745051997, 3.533989803],
              [9.172168622, 2.511101045],
              [7.792783481, 3.424088941],
              [7.939820817, 0.791637231]
             ]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

X_train = np.array(raw_data_X)
Y_train = np.array(raw_data_y)

x = np.array([8.093607318, 3.365731514])
plt.scatter(X_train[Y_train==0,0],X_train[Y_train==0,1],c="g")
plt.scatter(X_train[Y_train==1,0],X_train[Y_train==1,1],c='r')
plt.scatter(x[0],x[1],c='b')
plt.show()
  • 计算蓝色点与各个点之间的距离
1
2
3
4
from math import sqrt
distances = []
for x_train in X_train:
    distances.append(sqrt(np.sum((x_train-x)**2)))
  • 选取k=6，查看与蓝色点最近的6个点的标签情况
1
2
3
4
k = 6
nearest = np.argsort(distances)
topK_y = [ Y_train[neighbor].item() for neighbor in nearest[:k]]
print(topK_y) # [1,1,1,1,1，0]

可以发现与蓝色点最近的6个点中标签为1的有5个，标签为0的有1个，因此蓝色点应该属于红色标签类。

K近邻算法是非常特殊的，可以被认为是没有模型的算法。为了和其他算法统一，也可以认为训练数据集就是算法本身。

scikit-learn中的KNN

1
2
3
4
5
6
7
from sklearn.neighbors import KNeighborsClassifier

kNN_classifier = KNeighborsClassifier(n_neighbors=6)
kNN_classifier.fit(X_train,y_train)
x_predict = x.reshape(1,-1)
y_predict= kNN_classifier.predict(x_predict)
y_predict[0].item()

可以发现scikit-learn中先是加载算法、创建实例、然后fit 、最后predict，几乎scikit-learn中所有的算法都是按照上面的流程运行的。

封装自己的KNN

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import numpy as np
import matplotlib.pyplot as plt
from math import sqrt

from collections import Counter

class  KNNClassifier():
    def __init__(self, k):
        assert k>=1,"k must be valid"
        self.k = k
        self._X_train = None
        self._y_train = None
    
    def fit(self, X_train, y_train):
        assert X_train.shape[0] == y_train.shape[0],\
        "the size of X_train must be equal to the size of y_train"
        assert self.k <= X_train.shape[0],\
        "the size of k must be at least k"

        self._X_train = X_train
        self._y_train = y_train
        return self
    
    def predict(self, X_precit):
        assert self._X_train is not None and self._y_train is not None,\
        "must fit before predict"
        assert X_precit.shape[1]==self._X_train.shape[1],\
        "the feature number of X_predict must be equal to X_train"

        y_predcit = [self._predict(x) for x in X_precit]
        return np.array(y_predcit)
    
    def _predict(self, x):
        assert x.shape[0]==self._X_train.shape[1],\
        "the feature number of x must be equal to X_train"  

        distances = [sqrt(np.sum((x_train-x)**2)) for x_train in self._X_train]
        nearest = np.argsort(distances)

        topK_y = [self._y_train[i] for i in nearest[:self.k]]
        votes = Counter(topK_y)

        return votes.most_common(1)[0][0]
    
    def __repr__(self):
        return "KNN(k=%d)" % self.k

然后使用：

1
2
3
4
5
%run knn/knn.py
knn_clf = KNNClassifier(k=6)
knn_clf.fit(X_train,y_train)
y_predict = knn_clf.predict(X_precit=x_predict)
y_predict

测试算法性能

前面我们是用所有的数据训练一个模型来预测新的数据所属的类型，但是我们得到模型的意义是我们要在真实环境中使用这个模型。因此如果拿所有的数据训练模型比如一个股票预测模型，如果模型很差我们也没有机会调整模型，那会造成真实的损失。

改进这个问题的一个最简单的方法就是—Train test split ，通过测试数据直接判断模型好坏从而在模型进入真实环境前改进模型。

  • 封装Train_Test_Split函数
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
import numpy as np

def train_test_split(X, y, test_ratio=0.2, seed=None):
    assert X.shape[0] == y.shape[0],\
    "the size of X must be equal to the size of y"
    assert 0.0 <= test_ratio <= 1.0 ,\
    "test_ration must be valid"

    if seed:
        np.random.seed(seed)

    shuffle_indexes = np.random.permutation(len(X))

    test_size = int(len(X)*test_ratio)

    test_indexes = shuffle_indexes[:test_size]
    train_indexes = shuffle_indexes[test_size:]

    X_train = X[train_indexes]
    y_train = y[train_indexes]
    
    X_test = X[test_indexes]
    y_test = y[test_indexes]

    return X_train,  X_test, y_train, y_test
  • 测试准确率
1
2
3
4
5
6
7
8
9
from knn.model_selection import train_test_split
from knn.knn import KNNClassifier

X_train, X_test, y_train, y_test = train_test_split(X, y)
my_knn_clf = KNNClassifier(k=3)
my_knn_clf.fit(X_train, y_train)
y_predict = my_knn_clf.predict(X_test)

print(sum(y_predict==y_test).item()/len(y_test)) #0.966666666667

分类准确度

接着封装准确率函数

1
2
3
4
5
6
7
## metrics.py
import numpy as np

def accuracy_score(y_true, y_predcit):
    assert y_true.shape[0] == y_predcit.shape[0], \
    "the size of y_true must be equal to the size of y_predict"
    return sum(y_true==y_predcit)/len(y_true)

同时在knn代码中封装score函数，如下面：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import numpy as np
import matplotlib.pyplot as plt
from math import sqrt
from .metrics import accuracy_score

from collections import Counter

class  KNNClassifier():
    def __init__(self, k):
        assert k>=1,"k must be valid"
        self.k = k
        self._X_train = None
        self._y_train = None
    
    def fit(self, X_train, y_train):
        assert X_train.shape[0] == y_train.shape[0],\
        "the size of X_train must be equal to the size of y_train"
        assert self.k <= X_train.shape[0],\
        "the size of k must be at least k"

        self._X_train = X_train
        self._y_train = y_train
        return self
    
    def predict(self, X_precit):
        assert self._X_train is not None and self._y_train is not None,\
        "must fit before predict"
        assert X_precit.shape[1]==self._X_train.shape[1],\
        "the feature number of X_predict must be equal to X_train"

        y_predcit = [self._predict(x) for x in X_precit]
        return np.array(y_predcit)
    
    def _predict(self, x):
        assert x.shape[0]==self._X_train.shape[1],\
        "the feature number of x must be equal to X_train"  

        distances = [sqrt(np.sum((x_train-x)**2)) for x_train in self._X_train]
        nearest = np.argsort(distances)

        topK_y = [self._y_train[i] for i in nearest[:self.k]]
        votes = Counter(topK_y)

        return votes.most_common(1)[0][0]
    
    def score(self, X_test, y_test):
        y_predict = self.predict(X_test)

        return accuracy_score(y_test, y_predict)

    def __repr__(self):
        return "KNN(k=%d)" % self.k

测试：

超参数

我们在前面使用自己封装的KNN算法需要传入参数k，使用scikit-learn库同样需要传入n_neighbors。不过前面我们都是随机传入比如3或6，但是对于这个参数到底传入什么值最好呢？这就涉及了机器学习的超参数问题。

  • 超参数：在算法运行前需要决定的参数
  • 模型参数：算法过程中学习的参数

KNN算法没有模型参数，但其中的k是典型的超参数。我们常听说的调参指的就是调节超参数。

接着尝试用代码寻找KNN中最好的k ，数据集仍然采用手写数字数据集：

  • 首先加载数据集

image-20250912141609001

  • 寻找最好的超参数k

KNN算法其实不止k这一个超参数，还有距离这个参数

image-20250912160919317

  • 考虑加上距离这个超参数

image-20250912161249755

关于距离更多的定义

明可夫斯距离(Minkowski Distance):

image-20250917202225878

显然当p=1p=1 是即 曼哈顿距离；p=2p=2时 欧式距离

对p进行搜索，发现p=2时最好

image-20250912162148392

网格搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
param_grid = [
    {
        'weights':['uniform'],
        'n_neighbors':[i for i in range(1,11)]
    },
    {
        'weights':['distance'],
        'n_neighbors':[i for i in range(1,11)],
        'p':[i for i in range(1,6)]
    }
]

knn_clf = KNeighborsClassifier()
from sklearn.model_selection import GridSearchCV
grid_search = GridSearchCV(knn_clf, param_grid)

grid_search.fit(X_train, y_train)

grid_search.best_estimator_
grid_search.best_score_
grid_search.best_params_

knn_clf = grid_search.best_estimator_
knn_clf.score(X_test, y_test)

数据归一化

前面的分类任务其实少了很重要的一步就是 数据归一化(Feature Scaling)

看下面一组数据：

image-20250912170455645

而数据归一化作用就是 将所有的数据映射到同一尺度

  • 最值归一化：把所有数据映射到0-1之间

xscale=x−xminxmax−xminx_{scale} = \frac{x-x_{min}}{x_{max}-x_{min}}

适用于分布有明显边界(比如考试分数，像素点颜色范围0-255)的情况；受outlier影响较大

  • 均值方差归一化Standardization：把所有数据归一化到均值为0方差为1的分布中

xscale=x−xmeanSx_{scale}=\frac{x-x_{mean}}{S}

适用于数据没有明显边界的情况(收入分布)，有可能存在极端数据值

对测试集如何归一化？

原始数据集我们会拆分成 训练集 和 测试集，如果我要用归一化后的数据来训练模型，那么我们首先要对训练数据集进行归一化处理求得mean_train,std_trainmean\_train,std\_train ，训练后我们接着需要测试，此时测试集 需要用训练集的均值和方差归一化，而不是用本身测试集的均值和方差，即(x_test−mean_train)/std_train(x\_test-mean\_train)/std\_train

  • 测试数据是模拟真实环境，而真实环境中很有可能无法得到所有测试数据的均值和方差
  • 对数据的归一化也是算法的一部分

即 保存训练数据集得到的均值和方差

关于KNN的一些思考

KNN可以解决分类问题，并且天然可以解决多分类问题。同样KNN也可以解决回归问题，比如下图中可以根据距离最近几个点的值进行加权平均预测新数据点的值。

但KNN最大的一个缺点就是效率低下：

如果训练集有m个样本，n个特征，则预测每一个新的数据，需要O(m*n)

优化思路：使用数结构，KD-Tree,Ball-Tree

同时还有缺点是高度数据相关 、预测结果不具有可解释性 、维数灾难(随着维度的增加，“看似相近”的两个点之间的距离越来越大)

1维 0到1的距离 1
2维 (0,0)到(1,1)的距离 1.414
3维 (0,0,0)到(1,1,1)的距离 1.73
64维 (0,0,…,0)到(1,1,1,…,1)的距离 8
10000维 (0,0,…,0)到(1,1,1,…,1)的距离 100

解决方法：降维