机器学习算法—K近邻（一文看懂KNN）

2019-08-17 本文已影响40人皮皮大

本篇札记对机器学习中K近邻算法（KNN）的基础、原理、实例、超参数以及scikit-learn中的使用和调参等各种知识进行汇总，学习完本篇札记基本上会了KNN算法。

机器学习算法—K近邻（一文看懂KNN）

KNN基础

k-近邻算法（k-nearest neighbor, k-NN）是一种基本分类和回归（预测具体的数值，比如房价、成绩等）的算法，可以解决多分类问题。k近邻算法中的输入为实例的特征向量，输出为实例的类别，类别可以有多类。算法主要思想：

给定一个训练集的数据，实例的类别已定
对于新的实例，根据k个最近邻的训练实例的类别，经投票表决等方式进行预测
算法不具有显式的学习过程，实际上利用训练集对特征向量空间进行划分

KNN三要素

k的选择：k值如何选择？越大越好吗？奇偶性如何？经验值是多少？
距离度量：选择什么距离来进行度量新实例和训练集上点的距离？
分类决策规则：选择怎样的规则来对距离进行分类，从而判断新实例属于哪个类？

距离

特征空间中两个实例点的距离是两个实例点相似度的反应。k近邻模型的特征空间一般是n维实数向量空间 $R^n$ 。一般使用的欧式距离，也可以是其他距离，如： $L_p$ 距离，或者Minkowski距离。

假设特征空间 $X$ 是n维实数向量空间 $R^n$ ， ${x_i,x_j}\in X$ ，其中 $x_i=(x_i^{(1)},x_i^{(2)},....,x_i^{(n)}$ ，
$x_j=(x_j^{(1)},x_j^{(2)},....,x_j^{(n)}$

$x_i,x_j$ 的 $L_p$ 的距离定义为 $L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p}$

规定： $p\geq1$

当 $p=2$ 时，即为欧式距离，即： $L_2(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2)^\frac{1}{2}$
当 $p=1$ 时，即曼哈顿距离，即： $L_1(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|$
当 $p$ 趋于无穷，它是各个坐标距离的最大值： $L_{\infty}(x_i,x_j)=\mathop {max}\limits_{l}|x_i^{(l)}-x_j^{(l)}|$

算法思想

直观解释：给定一个训练数据集，对于新输入的实例，在训练集数据中找出和该实例最邻近的k个实例。这k个实例中的多数属于某个类，就将新实例划分为这个类别。
输入训练数据集：
$T=\{(x_1,y_1),(x_2,y_2),...(x_i,y_i)....(x_N,y_N)\}$
其中，x_i为实例特征向量，y_i为实例的类别；i=1,2,3,...N。
输出：实例x所属的类别y

根据给定的距离度量，在训练集T中找出与x最近邻的k个点，涵盖这个k个点的x的邻域记作：N_k(x)
在邻域N_k(x)中根据分类规则决定x的类别y
$y = \mathop{argmax}\limits_{c_j}\sum_{x_i\in{N_k(x)}}I(y_i=c_j), i=1,2...,N;j=1,2,...K$

上式中，I为指示函数，即当：y_i=c_j是为1，不等则为0

k=1称之为最近邻算法。对于输入的新实例，将训练集中离x最近点的所属类作为x的类别

手写KNN算法

import numpy as np
from math import sqrt
from collections import Counter
from metrics import accuracy_score   # 直接封装的方法进行调用


class KNNClassifier:
    def __init__(self, k):
        # 构造函数：初始化KNN分类器，传入k值；
        # 将样本定义为私有属性None，外部无法变动
        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
        assert X_train.shape[0] == y_train.shape[0], \
            "the size of X_train and y_train must be same."
        # k <= 总样本数（x的shape属性第一个代表样本总数；第二个代表样本属性的个数）
        assert self.k <= X_train.shape[0], \
            "the feature number of x must be equal to X_train"

        # 传入已知训练数据(X_train, y_train)，并且返回
        self._X_train = X_train
        self._y_train = y_train
        return self
    
    def predict(self, X_predict):
        # 给定待预测数据集X_predict, 返回表示预测X_predict的结果向量
        
        # 传入样本(_X_train, _y_train)都不能是空值，fit函数中已经赋值
        assert self._X_train is not None and self._y_train is not None, \
        "must fit before predict"
        # 样本数不限制，预测数据的属性和训练X_train的属性个数必须相同
        assert X_predict.shape[1] == self._X_train.shape[1], \
        "the feature number of X_predict  must be equal to X_train"
        
        # _predict对一个向量进行预测
        y_predict = [self._predict(x) for x in X_predict]
        return np.array(y_predict)
    
    def _predict(self, x):
        # 给出需要预测的数据的特征数量等于原来的特征数量，返回x预测的结果
        # 单个待预测数据的shape属性第一个值即为训练数据X_train的特征属性个数
        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_predict，再和y_test传入准确率的函数中：'''
        y_predict = self.predict(X_test)
        return accuracy_score(y_test, y_predict)
    
    def __repr__(self):
        return "KNN(k={})".format(self.k)

准确率计算

def accuracy_score(y_true, y_predict):
    '''准确率的封装：计算y_true和y_predict之间的准确率'''
    assert y_true.shape[0] == y_predict.shape[0], \
    "the size of y_true must be equal to the size of y_predict"

    return sum(y_true ==y_predict) / len(y_true)

训练测试分离_TTS

def train_test_split(X, y, test_ratio=0.2, seed=None):
    """
    将数据X和y按照test_ratio分成X_train, X_test, y_train, y_test
    """
    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)
    
    # 将X数组的长度随机排列
    shuffled_indexes = np.random.permutation(len(X))
    test_size = int(len(X) * test_ratio)
    test_indexes = shuffled_indexes[:test_size]
    train_indexes = shuffled_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

数据归一化

归一化思想

处理将所有的数据映射到同一个尺度上。需要注意的是：测试数据的归一化需要使用训练数据集的均值和方差

机器学习算法—K近邻（一文看懂KNN）

两种方法

最值归一化：数据映射到0-1上面
- 适合分布明显边界的情况：比如考试分数，像素边界
- 缺点：受outlier影响，比如收入没有边界
- 使用方法

image.png

查看均值和方差

image.png

均值方差归一化standardization：数据分布在均值为0，方差为1中
- 数据分布没有明显边界
- 可能存在极端数据
- 使用方法如下

image.png

代码实现

import numpy as np

class StandScaler:
    # 初始化过程；注意在这个类中方差用scale_表示
    def __init__(self):
        self.mean_ = None
        self.scale_ = None
    
    # 根据传进来的X来获得均值和方差；处理2维数据
    def fit(self, X):
        assert X.ndim == 2, "The dimension of X must be 2"
        # i：表示第i个属性，即第i列；shape[1]：列属性的个数；有多少个特征属性循环多少次
        self.mean_ = np.array([np.mean(X)[:, i] for i in range(X.shape[1])])
        self.scale_ = np.array([np.std(X)[:, i] for i in range(X.shape[1])])
        
        return self
    
    # 方差和均值归一化过程
    def transform(self, X):
        assert X.ndim ==2 , "the dimension of X must be 2"
        assert self.mean_ is not None and self.scale_ is not None, \
            "must fit before transform"
        assert X.shape[1] == len(self.mean_), \
            "the feature number of X must be equal to mean_ and std_"
        
        resX = np.empty(shape=X.shape, dtype=float)
        for col in range(X.shape[1]):
            resX[:, col] = (X[:, col] - self.mean_[col]) / self.scale_[col]
        return resX

网格搜索及调参

参数

KNN算法中的调参问题主要是：

距离的权重weights：有些实例可能取值小，但是更靠近需要预测实例
n_neighbors：即需要选择几个近邻的点
p：距离的选择，通过参数p来控制选择欧式距离还是其他距离
n_jobs：电脑核数，默认是1，加快运行速度
verbose：显示每种参数的输出结果，默认是2

image.png

手写寻找参数

image.png

best_method = ""
best_score = 0.0
best_k = -1
for method in ["uniform", "distance"]:
    for k in range(1, 11):
        knn_clf = KNeighborsClassifier(n_neighbors=k, weights=method)
        knn_clf.fit(X_train, y_train)
        score = knn_clf.score(X_test, y_test)
        if score > best_score:
            best_k = k
            best_score= score
            best_method = method
print("best_k = ", best_k)
print("best_score = ", best_score)
print("best_method = ", method)

搜索明科夫斯基距离对应的p

%%time

# method 固定为distance
best_p = -1
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_k = k
            best_score= score
            best_p = p
            
print("best_k = ", best_k)
print("best_score = ", best_score)
print("best_p = ",best_p)

网格搜索

网格搜索是指将需要调节的参数放入一个类似的网格中，对每种参数方案进行逐步检验，选择出最好效果的参数。

多个参数是以列表的形式
注意：参数p只有在参数weights为distance的情况下才有效

sklearn中KNN使用

在sklearn中使用KNN算法的一般过程是：

导入数据，清洗数据
进行TTS
均值归一化Scaler
通过内置的KNN类，进行fit、predict方法进行拟合和预测，最后计算准确率

如何导入数据和查看数据的信息

from sklearn import datasets
# 手写数字的数字集
digits = datasets.load_digits()
# 查看数据集的具体信息
digits.keys()   # dict_keys(['data', 'target', 'target_names', 'images', 'DESCR'])

# 查看样本信息
X = digits.data
X.shape

# 查看输出实例信息
y = digits.target
y.shape

# 查看输出的具体信息
digits.target_names

如何调用各种类和方法

# 分类的类
from sklearn.neighbors import KNeighborsClassifier

### TTS的导入
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=666)

# 调用预处理中用于均值归一化的类
from sklearn.preprocessing import StandardScaler

# 用于交叉验证的类
from sklearn.model_selection import GridSearchCV
grid_search = GridSearchCV(knn_clf, param_grid)     # 创建实例并传入参数

缺点

最大的特点：效率低下
- 如果训练集中m个样本，n个特征，预测每个新的数据，时间复杂度为O(m*n)
- 计算新数据和每个样本的距离，每次计算距离需要考虑n个特征
结果高度数据相关，对outlier更敏感。比如样本周边有两个错误值，错误明显
预测结果不具有解释型：结果只表示属于某个类别，没有具体的解释
维数灾难：看似相近的两个点之间的距离越来越大

kd树（了解）

k近邻算法最简单的实现方式线性扫描 linear scan。需要计算每个输入实例和每个训练实例之间的距离；当样本量很大的时候，非常耗时。考虑使用特殊的树形结构：kd树来较少距离的计算。

构造平衡kd树

kd树是一种对k维空间中的实例点进行存储以便快速查找数据的数据结构。

kd树是一种二叉树，表示对k维空间的划分。
不断地用垂直于坐标轴的超平面将k维空间切分，形成一些列的k维超矩形区域。
kd树的每个节点对应一个k维超矩形区域。
具体步骤：
- 对于给定的数据集T，构造根节点，根节点包含k维空间中所有实例点的矩形区域
- 选取 $x^{(1)}$ 为坐标轴，以T中的所有 $x^{(1)}$ 坐标的中位数为切分点，生成子节点，不断划分k维空间
- 在超矩形区域上选择一个坐标轴和此坐标轴上的切分点，确定一个超平面
- 超平面将矩形区域分为左右两个区域（子区域），实例就被划分到两个区域中
- 重复上述过程直到子区域内没有实例的时候终止：对于深度为j的结点，选择 $x^{(l)}$ 为切分的坐标轴， $l=j(mod k)+1$
切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面来实现

搜索kd树

以k=1为例，通过k最近邻方法来进行搜索：

给定一个目标点，首先找到包含目标点的叶结点；
包含目标点的叶结点对应包含目标点的最小矩形区域。以此叶结点的实例点为当前最近点
目标点的最近邻一定在以目标点为中心并且通过当前最近点的超球体的内部。
从该叶节点出发，回退到父节点
不断查找与目标点最近邻的节点，当存在不可能更近的点时终止

关于二叉树

二叉查找树是一种树形结构，采用了图的树形结构。每个节点最多两个子节点

平衡二叉树：修正不均衡的树，保持均衡状态，提高查找效率
B树：每个节点不止一个子节点，可以多个；MySQL中用到了B树

特点

每个节点的值均大于其左子树上任意一个节点的值：大于左边
每个节点的值均小于其右子树上任意一个节点的值：小于右边

机器学习算法—K近邻（一文看懂KNN）

KNN基础

KNN三要素

距离

算法思想

手写KNN算法

准确率计算

训练测试分离_TTS

数据归一化

归一化思想

两种方法

代码实现

网格搜索及调参

参数

手写寻找参数

网格搜索

sklearn中KNN使用

如何导入数据和查看数据的信息

如何调用各种类和方法

缺点

kd树（了解）

构造平衡kd树

搜索kd树

关于二叉树

猜你喜欢

热点阅读