k-Nearest Neighbors

• 思想极度简单
• 应用数学知识少（近乎为零）
• 效果好（缺点?）
• 可以解释机器学习算法使用过程中的很多细节问题
• 更完整的刻画机器学习应用的流程
• 天然可以解决多分类问题
• 思想简单，效果强大
• 可以解决回归问题
  • KNeighborsRegressor
  • http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsRegressor.html
• 缺点：
  • 效率低下
  • 如果训练集有m个样本，n个特征，则预测每一个新的数据，需要O（m*n)
  • 优化，使用树结构：KD-Tree,Ball-Tree
  • 缺点2：高度数据相关
  • 缺点3：预测结果不具有可解释性
  • 缺点4：维数灾难
    • 解决:降维
      

基本原理

from math import sqrt
distances = []
x = np.array([8.093607318, 3.365731514])
for x_train in X_train:
    d = sqrt(np.sum((x_train - x)**2)) 
    distances.append(d)
distances
nearest = np.argsort(distances) # 排序后返回所有元素的索引
k = 6 # K近邻算法，取最近的6个点
topK_y = [y_train[i] for i in nearest[:k]]  # 取最近的k个点的下表，对应着去y_train中把指定下标的元素取出来
# 下面对topk_y中的元素分布做一下统计
from collections import Counter
Counter(topK_y)
votes.most_common(2) # 找出票数最多的n个元素，2就是n的具体值

• 两个特征点之间的距离使用欧拉距离
  • 两个点对应维度的值相减再平方，平法和再开根号
    
  • 简写
  • 

python实现

import numpy as np
from math import sqrt

from collections import Counter


def kNN_classify(k, X_train, y_train, x):
    assert 1 <= k <= X_train.shape[0], "k must be valid"
    # numpy数组的shape[0]表示数组的行数
    assert X_train.shape[0] == y_train.shape[0], "the size of X_train must be equal to the size of y_train"
    # numpy数组的shape[1]表示数组的列数(在机器学习中，列一半作为特性，比如鸢尾花的花瓣的长、花瓣的宽、茎的高度、叶子形状等)
    assert X_train.shape[1] == x.shape[0], "the feature number of x must be equal to X_train"

    distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
    # 获取最近的几个点
    nearest = np.argsort(distances)
    # 获取最近的几个点在目标向量中对应的目标值(即结果是哪个)
    topK_y = [y_train[i] for i in nearest[:k]]
    votes = Counter(topK_y)

    return votes.most_common(1)[0][0]

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

使用scikit-learn中的kNN

from sklearn.neighbors import KNeighborsClassifier # 引入k近邻算法
kNN_classifier = KNeighborsClassifier(n_neighbors=6) # 选取6个距离最近的点
kNN_classifier.fit(X_train, y_train)
X_predict = x.reshape(1, -1) # 待预测点x转换成2维矩阵
y_predict = kNN_classifier.predict(X_predict)
y_predict[0] # 取出第一个预测结果

重构python代码

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 accuracy_score(y_test, y_predict)

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

训练数据集，测试数据集

• 分类的准确度 accuracy

超参数和模型参数

• 超参数：在算法运行前需要决定的参数
  • 调参就是调超参数
• 模型参数：算法过程中学习的参数
• KNN算法没有模型参数
• kNN算法中的k是典型的超参数
• 寻找最好的超参数：条件
  • 领域知识
  • 经验数值
  • 实验搜索
    
• 考虑距离的另一个好处是可以解决平票的情况

曼哈顿距离

%%time
best_p = "" # 明科夫斯基的最佳参数
best_score = 0.0
best_k = -1
for k in range(1, 11):
    for p in range(1, 6):
        knn_clf = KNeighborsClassifier(n_neighbors=k, weights="distance",p=p)
        knn_clf.fit(X_train, y_train)
        score = knn_clf.score(X_test, y_test)
        if score > best_score:
            best_p = p
            best_k = k
            best_score = score
print("best_p = ", best_p)        
print("best_k = ", best_k)
print("best_score = ", best_score) # 如果过大或者过小就应该适当扩大k的范围

Grid Search

# 先创建网格参数
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)]
    }
]
from sklearn.model_selection import GridSearchCV
grid_search = GridSearchCV(knn_clf, param_grid)
%%time
grid_search.fit(X_train, y_train)
knn_clf = grid_search.best_estimator_  # 选取最佳模型
%%time
# 并发进行模型获取
grid_search = GridSearchCV(knn_clf, param_grid, n_jobs=-1, verbose=2) # njobs代表用几个核。-1代表用所有的核.verbose代表信息输出的详细程度
grid_search.fit(X_train, y_train)

• 更多距离定义（两个样本之间的相似度）
• 向量空间余弦相似度Cosine Similarity

调整余玄相似度Adjusted Cosine Similarity

皮尔森相关系数Pearson Correlation Coefficient

Jaccard相似系数Jaccard Coefficient

数据归一化Feature Scaling

• 解决方案：将所有的数据映射到同一尺度
• 均值归一化：把所有数据映射到0-1之间
• 适用于分布有明显边界的情况；受outier影响较大
  • 解决方案：均值方差归一化 standardization
    • 数据分布没有明显的边界；有可能存在极端数据值
    • 均值方差归一化：把所有数据归一到均值为0方差为1的分布中

(x - np.min(x)) / (np.max(x) - np.min(x)) # 将x的所有元素都进行了归一化

对测试数据集如何归一化？

• 测试数据是模拟真实环境
• 真实环境很有可能无法得到所有测试
• 数据的均值和方差
• 对数据的归一化也是算法的一部分
• 要保存训练数据集得到的均值和方差
  • scikit-learn中使用Scaler
    

from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()
standardScaler.fit(X_train)  # 归一化
standardScaler.mean_
standardScaler.scale_ # std建议用scale替换
standardScaler.transform(X_train) # 对整个矩阵进行归一化，不会改变X_train
X_test_standard = standardScaler.transform(X_test)
from sklearn.neighbors import KNeighborsClassifier
knn_clf = KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(X_train, y_train)
knn_clf.score(X_test_standard, y_test) # 获取计算地准确率。训练数据集和测试数据集必须都进行归一化(transform)操作