机器学习笔记01. K-近邻算法

2022-12-10 16:18:38

1.1. K-近邻算法(KNN)概念

K Nearest Neighbor算法又叫KNN算法

定义：

如果一个样本在特征空间中的k个最相似(即特征空间中最近邻)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
距离公式：

两个样本的距离可以通过如下公式计算，又叫欧式距离
- 二维平面上点 \(a(x_1,y_1)\) 与点 \(b(x_2,y_2)\) 间的欧氏距离：
  
  \[d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]
- 三维空间上点 \(a(x_1,y_1,z_1)\) 与点 \(b(x_2,y_2,z_2)\) 间的欧氏距离：
  
  \[d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} \]
- n维空间上点 \(a(x_{11},x_{12},...,x_{1n})\) 与点 \(b(x_{21},x_{22},...,x_{2n})\) 间的欧氏距离：
  
  \[d_{12}=\sqrt{\sum_{k=1}^n{(x_{1k}-x_{2k})^2}} \]

1.2. 算法流程总结

计算已知类别数据集中的点与当前点的距离
按距离递增次序排序
选取与当前点距离最小的k个点
统计前k个点所在的类别出现的概率
返回前k个点出现频率最高的类别作为当前点的预测分类

2. K近邻算法api初步使用

2.1. Scikit-learn功能

分类、聚类、回归
特征工程
模型选择、调优

2.2. K-近邻算法API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)
- n_neighbors：int，可选（默认为5），k_neighbors查询默认使用的邻居数

2.3. 案例

2.3.1. 步骤分析

1. 获取数据集
1. 数据基本处理（暂时省略）
1. 特征工程（暂时省略）
1. 机器学习
1. 模型评估（暂时省略）

2.3.2. 代码过程

导入模块

from sklearn.neighbors import KNeighborsClassifier

构造数据集

x = [[0], [1], [2], [3]]
y = [0, 0, 1, 1]

机器学习 -- 模型训练

# 2.1.实例化一个估计器对象
estimator = KNeighborsClassifier(n_neighbors=1)

# 2.2.调用fit方法进行训练
estimator.fit(x, y)

# 3.数据预测
ret = estimator.predict([[100]])

3. 距离度量

3.1. 距离公式的基本性质

在机器学习过程中，对于函数 \(dist(.,.)\) ，若它是一“距离度量”(distance measure)，则需满足一些基本性质：

非负性： \(dist(X_i,X_j)>=0\) ；
同一性： \(dist(x_i,x_j)=0\) 。当且仅当 \(X_i=X_j\) ；
对称性： \(dist(x_i,x_j)=dist(x_j,x_i)\) ；
直递性： \(dist(x_i,x_j)<=dist(x_i,x_k)+dist(x_k,x_j)\) ；

直递性常被称为“三角不等式”。

3.2. 常见距离公式

3.2.1. 欧氏距离(Euclidean Distance)：

二维平面上点 \(a(x_1,y_1)\) 与点 \(b(x_2,y_2)\) 间的欧氏距离：

\[d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]
三维空间上点 \(a(x_1,y_1,z_1)\) 与点 \(b(x_2,y_2,z_2)\) 间的欧氏距离：

\[d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} \]
n维空间上点 \(a(x_{11},x_{12},...,x_{1n})\) 与 \(b(x_{21},x_{22},...,x_{2n})\) 间的欧氏距离：

\[d_{12}=\sqrt{\sum_{k=1}^n{(x_{1k}-x_{2k})^2}} \]

3.2.2. 曼哈顿距离(Manhattan Distance)：

二维平面两点 \(a(x_1,y_1)\) 与 \(b(x_2,y_2)\) 间的曼哈顿距离：

\[d_{12}=|x_1-x_2|+|y_1-y_2| \]
n维空间点 \(a(x_{11},x_{12},...,x_{1n})\) 与 \(b(x_{21},x_{22},...,x_{2n})\) 的曼哈顿距离：

\[d_{12}=\sum_{k=1}^{n}{|x_{1k}-x_{2k}|} \]

3.2.3. 切比雪夫距离(Chebyshev Distance)：

二维平面两点 \(a(x_1,y_1)\) 与 \(b(x_2,y_2)\) 间的曼哈顿距离：

\[d_{12}=\max{(|x_1-x_2|,|y_1-y_2|)} \]
n维空间点 \(a(x_{11},x_{12},...,x_{1n})\) 与 \(b(x_{21},x_{22},...,x_{2n})\) 的曼哈顿距离：

\[d_{12}=\max{|x_{1i}-x_{2i}|} \]

3.2.4. 闵可夫斯基距离(Minkowski Distance)：

闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。

两个n维变量 \(a(x_{11},x_{12},...,x_{1n})\) 与 \(b(x_{21},x_{22},...,x_{2n})\) 间的闵可夫斯基距离定义为：

\[d_{12}=\sqrt[p]{\sum_{k=1}^n{|x_{1k}-x_{2k}|^p}} \]

其中p是一个可变参数：

当p=1时，就是曼哈顿距离；
当p=2时，就是欧氏距离；
当p→∞时，就是切比雪夫距离。

缺点：

将各个分量的量纲(scale)，也就是“单位”相同的看待了；
未考虑各个分量的分布(期望、方差等)可能是不同的。

3.3. “连续属性”和“离散属性”的距离计算

若属性之间存在序关系，则可以将其转化为连续值，例如：身高属性“高”“中”“矮”，可转化为{1, 0.5, 0}。
- 闵可夫斯基距离可以用于有序属性。
若属性值之间不存在序关系，则通常将其转化为向量的形式，例如：性别属性“男”“女”，可转化为{(1, 0), (0, 1)}。

4. K值的选择

K值过小：容易受到异常点的影响

K值得减小就意味着整体模型变得复杂，容易发生过拟合
K值过大：容易遇到样本均衡问题

K值较大，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，K值的增大就意味着整体的模型变得简单，容易发生欠拟合

近似误差
- 对现有训练集的训练误差，关注训练集
- 如果近似误差过小可能会出现过拟合的现象
- 模型本身不是最接近最佳模型
估计误差
- 可以理解为对测试集的测试误差，关注测试集
- 估计误差小可以说明对未知数据的预测能力好
- 模型本身最接近最佳模型

5. kd树

实现K近邻算法时，主要的问题是如何对训练数据进行快速K近邻搜索。

K近邻算法最简单的实现是线性扫描（穷举搜索），即要计算输入实例与每一个训练实例的距离。计算并存储好以后，再查找K近邻。

5.1. kd树

为了避免每次都重新计算一遍距离，算法会把距离信息保存在一棵树里，这样在计算之前从树里查询距离信息，尽量避免计算。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。

这样优化后的算法复杂度可降低到 \(O(DN\log{(N)})\) 。

5.2. 构造方法

构造根节点，使根节点对应于K维空间中包含所有实例点的超矩形区域；
通过递归的方法，不断地对K维空间进行切分，生成子节点。
重复上述过程直到子区域内没有实例时终止（终止时的节点为叶节点）。

通常，循环选择坐标轴对空间切分，选择训练实例点在坐标轴上的中位数为切分点，这样得到的kd树是平衡的（平衡二叉树）。

kd树中每个节点是一个向量，和二叉树按照数的大小划分不同的是，kd树每层需要选定向量中的某一维，然后根据这一维按左小右大的方式划分数据。在构建kd树时，关键需要解决两个问题：

(1). 选择向量的哪一维进行划分；

可以随机选择某一维度或按顺序选择，但更好的方法应是在数据比较分散的那一维进行划分（分散的程度可以根据方差进行衡量）；

(2). 如何划分数据；

好的划分方法可以使构建的树比较平衡，可以选择中位数进行划分。

5.3. 案例分析

5.3.1. 树的建立

给定一个二维空间数据集：T={(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)}，构造一个平衡kd树。

第一维度(x)：2，5，9，4，8，7

排序：2，4，5，7，8，9

中位数：6
第二维度(y)：3，4，6，7，1，2

排序：1，2，3，4，6，7

中位数：3.5

由于x维度比较分散（方差较大），所以选择根据x维度进行划分，x维度的中位数为6，所以选择5和7 均可，这里选择7为例，所以将数据集以(7, 2)划分为左（(2, 3)，(4, 7)，(5, 4)）右（(8, 1)，(9, 6)）两块；

接着对左半部分进行按y维度划分，(2, 3)，(4, 7)，(5, 4)对应的y维度数据为3，4，7；中位数为4，对应的数据是(5, 4)，故将左半部分又划分为左（(2, 3)）右（(4, 7)）；

对右半部分进行按y维度划分，(8, 1)，(9, 6)对应的y维度数据为1，6；中位数3.5，距1和6相等，这里选择6即(9, 6)，此时(8, 1)被划分到左半部分。

6. 案例：鸢尾花种类预测-数据集介绍

6.1. 案例：鸢尾花种类预测

Iris数据集是常用的分类实验数据集，也称鸢尾花数据集，是一类多重变量分类分析的数据集。关于数据集的具体介绍：

特征值-4个：花瓣、花萼的长度、宽度
目标值-3个：setosa(山鸢尾)、vericolor(虹膜锦葵)、virginica(变色鸢尾)

6.2. scikit-learn中数据集介绍

6.2.1. scikit-learn数据集API介绍

sklearn.datasets
- 加载获取流行数据集
- datasets.load_*()
  - 获取小规模数据集，数据包含在datasets里
- datasets.fetch_*(data_home=None)
  - 获取大规模数据集，需要从网络上下载，函数的第一个参数是data_home，表示数据集的下载目录，默认是~/scikit_learn_data/

6.2.1.1. sklearn小数据集

sklearn.datasets.load_iris()

加载并返回鸢尾花数据集

名称数量

类别 3

特征 4

样本数量 150

每个类别数量 50

名称	数量
类别	3
特征	4
样本数量	150
每个类别数量	50

6.2.1.2. sklearn大数据集

sklearn.datasets.fetch_20newsgroups(data_home=None, subset='train')
- subset：'train'或者'test'，'all'，可选，选择要加载的数据集；
- 训练集的“训练”，测试集的“测试”，两者的“全部”

6.2.2. sklearn数据集返回值介绍

load和fetch返回的数据类型是datasets.base.Bunch（字典格式）

data：特征数据数组，是形状为[n_samples * n_features]的二维numpy.ndarray数组
target：标签数组，是n_sample的一维numpy.ndarray数组
DESCR：数据描述
feature_names：特征名，新闻数据，手写数字、回归数据在数据集中没有
target_name：标签名

from sklearn.datasets import load_iris

# 获取鸢尾花数据集
iris = load_iris()
print("鸢尾花数据集的返回值：\n", iris)
# 返回值是一个继承自字典的bunch
print("鸢尾花的特征值：\n", iris["data"])
print("鸢尾花的目标值：\n", iris.target)
print("鸢尾花的特征值名：\n", iris.feature_names)
print("鸢尾花的目标值名：\n", iris.target_names)
print("鸢尾花的描述：\n", iris.DESCR)

6.2.3. 查看数据分布

seaborn.lmplot()会在绘制二维散点图时，自动完成回归拟合
- x, y分别代表横纵坐标的列名
- data= 要关联的数据集
- hue= 代表按照species即花的类别分类展示
- fit_reg= 是否进行线性拟合

# 把数据转换成dataframe
iris_d = pd.DataFrame(data=iris.data, columns=["Sepal_Length", "Sepal_Width", "Petal_Length", "Petal_Width"])
iris_d["target"] = iris.target
# print(iris_d)

def iris_plot(data, col1, col2):
    sns.lmplot(x=col1, y=col2, data=data, hue="target", fit_reg=False)
    plt.title("鸢尾花数据显示")
    plt.show()

iris_plot(iris_d, "Sepal_Width", "Petal_Length")

6.2.4. 数据集的划分

训练数据：用于训练，构建模型
测试数据：在模型检验时使用，用于评估模型是否有效

划分比例一般为：

训练集	70%	80%	75%
测试集	30%	20%	25%

数据集划分api

sklearn.model_selection.train_test_split(arrays, *options)

参数：
- x - 数据集的特征值
- y - 数据集的标签值
- test_size - 测试集的大小，一般为float
- random_state - 随机数种子不同的种子会造成不同的随机采样结果，相同的种子采样结果相同。
返回值：
- x_train, x_test, y_train, y_test

x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=22)
print("训练集的特征值是：\n", x_train)
print("训练集的目标值是：\n", y_train)
print("测试集的特征值是：\n", x_test)
print("测试集的目标值是：\n", y_test)

print("训练集的目标值的形状是：\n", y_train.shape)
print("测试集的目标值的形状是：\n", y_test.shape)

7. 特征工程 - 特征预处理

7.1. 特征预处理

7.1.1. 定义

特征与处理是通过一些转换函数将特征数据转换成更加适合算法模型的特征数据过程。

为什么要进行归一化/标准化？

特征的单位或者大小相差较大，或者某特征值的方差相比其他的特征要大出几个数量级，容易影响（支配）目标结果，使得一些算法无法学习到其他的特征

7.1.2. 包含内容（数值型数据的无量纲化）

归一化
标准化

7.1.3. 特征预处理API

sklearn.preprocessing

7.2. 归一化

7.2.1. 定义

通过对原始数据进行变换把数据映射到(默认为[0,1])之间

7.2.2. 公式

\[{X}'=\frac{x-\min}{\max-\min} \]

\[{X}''={X}'*(\mathrm{mx}-\mathrm{mi})+\mathrm{mi} \]

作用于每一列，max为一列的最大值，min为一列的最小值，那么\({X}'\)为最终结果，\(\mathrm{mx}\)、\(\mathrm{mi}\)分别为指定区间，值默认分别为1和0

7.2.3. API

sklearn.preprocessing.MinMaxScaler(feature_range=(0,1)...)
- MinMaxScaler.fit_transform(X)
  - X：numpy.array格式的数据[n_samples, n_features]
  - 返回值：转换后的形状相同的array

7.2.4. 数据计算

要进行计算的数据如下，保存在dating.txt中：

milage,Liters,Consumtime,target
40920,8.326976,0.953952,3
14488,7.153469,1.673904,2
26052,1.441871,0.805124,1
75136,13.147394,0.428964,1
38344,1.669788,0.134296,1

实例化MinMaxScaler并通过fit_transform转换：

import pandas as pd
from sklearn.preprocessing import MinMaxScaler


def minmax_demo():
    """
    归一化演示
    :return: None
    """
    data = pd.read_csv("./dating.txt")
    print(data)
    # 1.实例化一个转换器类
    transfer = MinMaxScaler(feature_range=(2, 3))
    # 2.调用fit_transform
    transfer_data = transfer.fit_transform(data[["milage", "Liters", "Consumtime"]])
    print("最小值最大值归一化处理的结果：\n", transfer_data)

输出结果：

   milage     Liters  Consumtime  target
0   40920   8.326976    0.953952       3
1   14488   7.153469    1.673904       2
2   26052   1.441871    0.805124       1
3   75136  13.147394    0.428964       1
4   38344   1.669788    0.134296       1
最小值最大值归一化处理的结果：
 [[2.43582641 2.58819286 2.53237967]
 [2.         2.48794044 3.        ]
 [2.19067405 2.         2.43571351]
 [3.         3.         2.19139157]
 [2.3933518  2.01947089 2.        ]]

7.2.5. 归一化总结

由于最大值最小值非常容易受异常点影响，所以这种归一化方法的鲁棒性较差，只适合传统精确小数据场景。

7.3. 标准化

7.3.1. 定义

通过对原始数据进行变换把数据变换到均值为0，标准差为1的范围内

7.3.2. 公式

\[{X}'=\frac{x-\mathrm{mean}}{\sigma} \]

作用于每一列，\(\mathrm{mean}\)为平均值，\(\sigma\)为标准差

7.3.3. API

sklearn.preprocessing.StandardScaler()
- 处理之后每列的所有数据都聚集在均值0附近，标准差为1
- StandardScaler.fit_transform(X)
  - X：numpy.array格式的数据[n_samples, n_features]
- 返回值：转换后的形状相同的array

7.3.4. 数据计算

def standard_demo():
    """
    归一化演示
    :return: None
    """
    data = pd.read_csv("./dating.txt")
    print(data)
    # 1.实例化一个转换器类
    transfer = StandardScaler()  # 此时不需要传feature_range
    # 2.调用fit_transform
    transfer_data = transfer.fit_transform(data[["milage", "Liters", "Consumtime"]])
    print("标准化处理的结果：\n", transfer_data)
    print("每一列特征的平均值：\n", transfer.mean_)
    print("每一列特征的方差：\n", transfer.var_)

7.3.5. 标准化总结

在已有样本足够多的情况下比较稳定，适合现代嘈杂大数据场景。

8. 案例：鸢尾花种类预测 - 流程实现

8.1. 再识K-近邻算法API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, algorithm='auto')
- n_neighbors：
  - int，可选（默认=5），k_neighbors查询默认使用的邻居数
- algorithm：{'auto', 'ball_tree', 'kd_tree', 'brute'}
  - 快速K-近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法进行搜索。
  - 'brute'：暴力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。
  - 'kd_tree'：构造kd树存储数据以外对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个节点是一个超矩形，在维数小于20时效率高。
  - 'ball_tree'：是为了克服kd树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。

8.2. 案例：鸢尾花种类预测

8.2.1. 数据集介绍

实例数量：150（三个类各有50个）
属性数量：4（数值型，数值型，帮助预测的属性和类）
属性信息：
- sepal length — 萼片长度(cm)
- sepal width — 萼片宽度(cm)
- petal length — 花瓣长度(cm)
- petal width — 花瓣宽度(cm)
类信息：
- iris-Setosa — 山鸢尾
- iris-Versicolour — 变色鸢尾
- iris-Virginica — 维吉尼亚鸢尾

8.2.2. 步骤分析

获取数据集
数据基本处理
特征工程
机器学习（模型训练）
模型评估

8.2.3. 代码过程

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# 1.获取数据集
iris = load_iris()

# 2.数据基本处理
# 划分出训练集特征值、测试集特征值、训练集目标值、测试集目标值
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=22)

# 3.特征工程：标准化
transfer = StandardScaler()
# 训练集特征值标准化处理
x_train = transfer.fit_transform(x_train)
# 训练集目标值标准化处理
x_test = transfer.transform(x_test)

# 4.机器学习（模型训练）
# 实例化K-近邻算法分类器
estimator = KNeighborsClassifier(n_neighbors=5)
# 将训练集特征值和目标值用K-近邻算法进行训练
estimator.fit(x_train, y_train)

# 5.模型评估
# 将测试集特征值交给训练好的估计器去预测出目标值
y_predict = estimator.predict(x_test)

# 方法1：比较真实值与预测值
print("预测结果为：\n", y_predict)
# 将预测出的目标值与训练集的真实目标值进行比对
print("比对真实值和预测值：\n", y_predict == y_test)

# 方法2：直接计算准确率
# 将测试集的特征值和目标值交给估计器去计算准确率
score = estimator.score(x_test, y_test)
print("准确率为：\n", score)

9. KNN算法总结

9.1. K-近邻算法优缺点汇总

优点
- 简单有效
- 重新训练的代价低
- 适合类域交叉样本
  - KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域交叉或重叠较多的待分样本来说，KNN方法较其他方法更为适合。
- 适合大样本自动分类
  - 该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
缺点
- 惰性学习
  - KNN算法是懒散学习方法「Lazy Learning，基本上不学习」，一些积极的学习算法要快很多
- 类别评分而不是规格化
  - 不像一些通过概率评分的分类
- 输出可解释性不强
  - 例如决策树的输出可解释性就较强
- 对不均衡的样本不擅长
  - 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
- 计算量较大
  - 目前常用的解决方法是事先对已知的样本进行剪辑，事先去除分类作用不大的样本。

10. 交叉验证，网格搜索

10.1. 交叉验证(cross validation)

交叉验证：将拿到的训练数据分为训练集和验证集。数据分成x份就称为x折交叉验证。

目的：为了让被评估的数据更加准确可信。

10.2. 网格搜索(Grid Search)

通常情况下，有很多参数是需要指定的（如k-近邻算法中的k值），这种参数被称为超参数。但是手动过程繁杂，所以需要对模型预设几中超参数组合。每组超参数都采用交叉验证来进行评估，最后选中最优参数组合建立模型。

10.3. 交叉验证，网格搜索（模型选择与调优）API

sklearn.model_selection.GridSearchCV(estimator, param_grid=None, cv=None)
- 对估计器的指定参数进行详尽搜索
- estimator：估计器对象
- param_grid：dict，估计器参数，例如：{"n_neighbors": [1, 3, 5]}
- cv：指定几折交叉验证
estimator：
- fit：输入训练数据
- score：准确率
- 结果分析：
  - best_score_：交叉验证中得到的最好结果
  - best_estimator_：交叉验证中得到的最好的模型
  - cv_results_：每个参数得到的模型结果

码农公寓