【手写算法实现】 之 KNN K近邻算法
k-近邻(k-Nearest Neighbors) 的思想是给定测试样本，基于某种距离度量(⼀般使⽤欧⼏⾥德距离) 找出训练集中与其最靠近的k kk 个训练样本，然后基于这k kk 个“邻居” 的信息来进⾏预测(“物以类聚”)。
算法步骤：
根据给定的距离度量，在训练集中找出与x 最近邻的k 个点，涵盖这k kk 个点的x 的邻域记作N k ( x ) 在N k ( x ) 中根据分类决策规则，如多数表决决定x 的类别y。
可见，决定了k kk 近邻模型的三个基本要素——距离度量、k 值的选择、分类决策规则。
距离度量
在KNN中，使用不同的距离度量，所得到的最近邻点是不一样的。
⼀般使⽤欧⼏⾥德距离
相关度(如⽪尔逊相关系数)
曼哈顿距离**(Manhattan Distance) **
k 值的选择
当选择⽐较⼩的k 值的时候，表⽰使⽤较⼩领域中的样本进⾏预测，训练误差会减⼩，但是会导致模型变得复杂，容易导致过拟合。
当选择较⼤的k 值的时候，表⽰使⽤较⼤领域中的样本进⾏预测，训练误差会增⼤，同时会使模型变得简单，容易导致⽋拟合。
分类决策规则
- 多数表决法：每个邻近样本的权重是⼀样的，最终预测的结果为出现类别最多的那个类。
其中 I 是指示函数
加权多数表决法：每个邻近样本的权重是不⼀样的，⼀般情况下采⽤权重和距离成反⽐的⽅式来计算，最终预测结果是出现权重最⼤的那个类别。
手写自定义实现
########-----KNN------######### class KNN(): def __init__(self, k=10): self._k = k def fit(self, X, y): self._unique_labels = np.unique(y) self._class_num = len(self._unique_labels) self._datas = X self._labels = y.astype(np.int32) # 多数表决法 def predict(self, X): # 欧式距离计算 dist = np.sum(np.square(X), axis=1, keepdims=True) - 2 * np.dot(X, self._datas.T) dist = dist + np.sum(np.square(self._datas), axis=1, keepdims=True).T # 取最大距离的k个 dist = np.argsort(dist)[:,:self._k] return np.array([np.argmax(np.bincount(self._labels[dist][i])) for i in range(len(X))]) # 得到score，也就是准确率 accuracy def score(self, X, y): y_pred = self.predict(X) accuracy = np.sum(y == y_pred, axis=0) / len(y) return accuracy
iris数据集测试
def create_data(): iris = load_iris() df = pd.DataFrame(iris.data, columns=iris.feature_names) df['label'] = iris.target df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label'] data = np.array(df.iloc[:100, :]) return data[:,:-1], data[:,-1]
用自定义 KNN 模型
# 用自定义 KNN 模型 model = KNN() model.fit(X_train, y_train) # 测试数据 print(model.score(X_test, y_test))
1.0
从sklearn 包中调用neighbors 测试
# 从sklearn 包中调用neighbors 测试 from sklearn import neighbors skl_model = neighbors.KNeighborsClassifier() # 训练数据集 skl_model.fit(X_train, y_train) # 测试数据 print(skl_model.score(X_test, y_test))
1.0
完整代码
import numpy as np import pandas as pd from sklearn.model_selection import train_test_split from sklearn.datasets import load_iris ########-----KNN------######### class KNN(): def __init__(self, k=10): self._k = k def fit(self, X, y): self._unique_labels = np.unique(y) self._class_num = len(self._unique_labels) self._datas = X self._labels = y.astype(np.int32) # 多数表决法 def predict(self, X): # 欧式距离计算 dist = np.sum(np.square(X), axis=1, keepdims=True) - 2 * np.dot(X, self._datas.T) dist = dist + np.sum(np.square(self._datas), axis=1, keepdims=True).T # 取最大距离的k个 dist = np.argsort(dist)[:,:self._k] return np.array([np.argmax(np.bincount(self._labels[dist][i])) for i in range(len(X))]) # 得到score，也就是准确率 accuracy def score(self, X, y): y_pred = self.predict(X) accuracy = np.sum(y == y_pred, axis=0) / len(y) return accuracy def create_data(): iris = load_iris() df = pd.DataFrame(iris.data, columns=iris.feature_names) df['label'] = iris.target df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label'] data = np.array(df.iloc[:100, :]) return data[:,:-1], data[:,-1] if __name__ == '__main__': # iris 数据集测试 X, y = create_data() X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3) print(X_train[0], y_train[0]) # 用自定义 KNN 模型 model = KNN() model.fit(X_train, y_train) # 测试数据 print(model.score(X_test, y_test)) # 从sklearn 包中调用neighbors 测试 from sklearn import neighbors skl_model = neighbors.KNeighborsClassifier() # 训练数据集 skl_model.fit(X_train, y_train) # 测试数据 print(skl_model.score(X_test, y_test))
