k近邻算法
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
K近邻算法的思想：
“近朱者赤，近墨者黑“
“物以类聚，人以群分”
如上图所示，红、绿为两类问蓝色点属于哪一类呢？
我们可以通过测量蓝色点距离红绿两类所有点之间的距离进行分类。
这样我们就把分类问题转移到求点与点之间的距离的问题上来了；
根据我们中学所学的两点之间的距离公式计算：
上图第一行是普通的两点间两个维度上的距离的公式，第二行推广到三个维度 第三多个维度 维度也就是特征
K近邻算法实现步骤如下：
1.计算输入x与训练集各点的距离distance
2.按distance排序，取distance最近的k个点（k为超参）
3.对k个点的类别归类计数，x归为多数类（多数表决）或者对k个点的类别按1/distance权重归类计数，x归为计数大的类（加权表决）
K近邻算法实现代码如下：
import numpy as np
from math import sqrt
from collections import Counter
from .metrics import accuracy_score
class KNNClassifier:
def __init__(self, k):
"""初始化kNN分类器"""
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):
"""根据训练数据集X_train和y_train训练kNN分类器"""
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 X_train must be at least k."
self._X_train = X_train
self._y_train = y_train
return self
def predict(self, X_predict):
"""给定待预测数据集X_predict，返回表示X_predict的结果向量"""
assert self._X_train is not None and self._y_train is not None, \
"must fit before predict!"
assert X_predict.shape[1] == self._X_train.shape[1], \
"the feature number of X_predict must be equal to X_train"
y_predict = [self._predict(x) for x in X_predict]
return np.array(y_predict)
def _predict(self, x):
"""给定单个待预测数据x，返回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):
"""根据测试数据集 X_test 和 y_test 确定当前模型的准确度"""
y_predict = self.predict(X_test)
return np.sum(y_test == y_predict) / len(y_test)
def __repr__(self):
return "KNN(k=%d)" % self.k
sklearn中k近邻算法的实现
# 引入sklearn包中的knn类
from sklearn.neighbors import KNeighborsClassifier
# 取得knn分类器，并使用内置参数调整KNN三要素
knn=KNeighborsClassifier(weights="distance",n_neighbors=5)
# 使用knn.fit()对训练集进行训练
knn.fit(x_train, y_train)
# 调用knn.predict()预测新输入的类别
y_predict=knn.predict(x_test)
# 调用knn.predict_proba()，显示每个测试集样本对应各个分类结果的概率
knn.predict_proba(x_test)
# 调用knn.score()计算预测的准确率
score=knn.score(x_test, y_test, sample_weight=None)
K近邻处理回归问题的思路
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的某些属性做一定的处理（例如取平均值）赋给该样本，就可以得到该样本对应属性的值。
距离度量拓展
衡量特征空间中两个实例点的距离，度量方法一边用Lp距离，p取不同值时，分别有不同的名称，常用欧氏距离作为距离度量。
Lp距离：
欧氏距离(p=2)
曼哈顿距离(p=1)
p无穷
不同的距离度量，得到的实例点之间的距离是不同的。
K近邻算法优缺点
优点：
1、KNN可以处理分类问题，同时天然可以处理多分类问题。
2、简单，易懂，同时也很强大，对于手写数字的识别，鸢尾花这一类问题来说，准确率很高。
3、KNN还可以处理回归问题。
缺点：
1、效率低，因为每一次分类或者回归，都要把训练数据和测试数据都算一遍，如果数据量很大的话，需要的算力会很惊人，但是在机器学习中，大数据处理又是很常见的一件事。
2、对训练数据依赖度特别大，虽然所有机器学习的算法对数据的依赖度很高，但是KNN尤其严重，因为如果我们的训练数据集中，有一两个数据是错误的，刚刚好又在我们需要分类的数值的旁边，这样就会直接导致预测的数据的不准确，对训练数据的容错性太差。
3、维数灾难，KNN对于多维度的数据处理也不是很好。
例：[0, 0, 0, ...0]和[1, 1, 1,...1]，按欧拉定理计算，元素个数越多，两点距离越大
