手写KNN分类算法

文章目录

1. 1. KNN算法简介
   1. 1.1. 优点
   2. 1.2. 缺点
   3. 1.3. 经验
   4. 1.4. 应用
2. 2. KNN算法实现
3. 3. 参考

近朱者赤，近墨者黑，看一个人经常跟什么人来往，就可以大致推算出这个人的水平。在机器学习领域，有一个采用类似思想实现的算法，那便是KNN(K-Nearest Neighbor)，即K近邻算法，其中K是关键参数。该算法比较简单，本文简单介绍如何从零开始实现这个算法，以便加深对算法的理解。

KNN算法简介

KNN算法的主要实现步骤如下：

• 算距离：对于给定的一条测试数据，计算它与训练集中每个样本的距离（一般采用欧式距离）
• 找邻居：找到距离这条测试数据最近的K个训练样本
• 做决策：根据这K个训练样本的标签，投票决定测试数据的预测值。对于分类问题，一般取出现次数多的标签，即少数服从多数；对于回归问题，一般取这K个标签的平均值

优点

• 简单，易实现
• 只有一个超参数K，参数调优方便快捷
• 特别适合多分类问题

缺点

• 惰性算法，在预测时，需要遍历所有的训练样本，内存开销大，性能差
• 可解释性差，无法给出明确的预测规则

经验

• K选择：一般来说K值越大，决策边界越平滑，模型越稳定，但是不代表K越大越好。一般采用交叉验证来确定K值。K的取值范围是[1, 训练样本数的平方根]，并且最好是奇数
• 距离选择：对于文本来说，夹角余弦比欧式距离更合适，其他场景还是用欧式距离
• 特征工程：涉及到距离计算的算法，在特征工程阶段，最好进行标准化或者归一化

应用

• 客户流失预测
• 欺诈侦测
• 推荐

KNN算法实现

import numpy as np
from collections import Counter

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

class KNNClassifier(object):
    def __init__(self, k=3):
        """
        构造方法，只有一个参数k，最小值为1，默认为3。最好是奇数。
        k: 邻居数，int型
        """
        assert k >= 1, "k must be integer and larger than 0"
        
        self.k = k
        self.X = None
        self.y = None
 
    def fit(self, X, y):
        """
        训练，KNN无训练过程，因此只做赋值。同时要求以下两点：
        1、X和y的维度要一致
        2、k要小于X的训练样本个数，否则没有意义
        
        X: 训练样本，array型
        y: 训练标签，array型
        """
        assert X.shape[0] == y.shape[0], "the shape of X and y must be match"
        assert self.k <= X.shape[0], "k must be smaller than shape of X"
        
        self.X = X
        self.y = y
 
    def _calc_euclidean_distance(self, array1, array2):
        """
        计算两个样本array1和array2之间的欧式距离
        array1: 第一个样本，array型
        array2: 第二个样本，array型
        """
        return np.linalg.norm(array1 - array2)
 
    def _vote(self, topk_y):
        """
        根据选出的k个标签，进行投票，少数服从多数
        topk_y: 选出的k个标签值，array型
        """
        return Counter(topk_y).most_common()[0][0]
 
    def predict(self, x):
        """
        预测，遍历测试样本，对于每个样本，分别与所有训练样本计算距离，然后选出距离最近的k个标签，进行决策
        x: 测试样本，维度要与训练样本X保持一致，array型
        """
        assert self.X is not None and self.y is not None , "must training before predict"
        assert x.shape[1] == self.X.shape[1]
        
        y_pred = []
        for i in range(len(x)):
            distances = [self._calc_euclidean_distance(x[i], self.X[j]) for j in range(len(self.X))]
            nearest_index = np.argsort(distances)
            topk_index = nearest_index[:self.k]
            y_pred.append(self._vote(self.y[topk_index]))
        return np.array(y_pred)


##############  以上是算法实现过程，下面对算法进行测试，以及与sklearn自带的KNN进行对比    ###############


# 导入iris数据
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=888)

# 使用我的算法进行预测，并给出准确率
knn_me = KNNClassifier(3)
knn_me.fit(X_train, y_train)
y_predict_me = knn_me.predict(X_test)
print("The accuracy of my knn is {}.".format(accuracy_score(y_test, y_predict_me)))

# 使用sklearn的算法进行预测，并给出准确率
knn_std = KNeighborsClassifier(n_neighbors=3)
knn_std.fit(X_train, y_train)
y_predict_std = knn_std.predict(X_test)
print("The accuracy of sklearn knn is {}.".format(accuracy_score(y_test, y_predict_std)))

执行上面代码，输出如下，可以看出，精度是一致的。当然，我的算法没有考虑各种异常，以及大数量下的性能优化，切不可应用在生产环境下。

The accuracy of my knn is 0.9473684210526315.
The accuracy of sklearn knn is 0.9473684210526315.

参考

• KNN算法理解