机器学习之K近邻算法（KNN）

发表于 | 分类于 | 浏览 次
| 字数统计: 1,376 字 | 阅读时长 ≈ 6 分钟

“近朱者赤，近墨者黑”

监督学习、多分类/回归、判别模型

没有显式的学习过程，K 最近邻算法使用整个数据集作为训练集，而非将数据集分割为一个数据集和一个测试集。

优点：

简单，精度高，无数据输入假定，对outlier不敏感，分类与回归均可操作，可用于非线性分类

缺点：

计算复杂度高，空间复杂度高，K需预先设定，对大小不平衡的数据易偏向大容量数据

适用数据范围：

数值型、标称型

常用算法：

kd树：

对x的K个特征，一个一个做切分，使得每个数据最终都在切分点上（中位数），对输入的数据搜索kd树，找到K近邻

1. 概念

  • KNN的三个基本要素

    K值的选择，距离度量、分类决策规则

    ​

2. 基本思路

2.1 工作原理

  1. 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
  2. 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
    1. 计算新数据与样本数据集中每条数据的距离。
    2. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
    3. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
  3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。

2.2 实现kd树

  • kd树

    是一种对k维空间中实例点进行储存以便对其进行快速检索的树形数据结构。

    是二叉树，表示对k维空间的一个划分。

  • 构造kd树

2.3 对偶形式

  • 基本想法

    将w和d表示为实例x和标记y的线性组合的形式，通过求解其系数求得w和b

  • 对偶形式迭代是收敛的，存在多个解

3. 使用

3.1 一般流程

收集数据：可以使用任何方法

准备数据：距离计算所需要的数值，最好是结构化的数据格式

分析数据：可以使用任何方法

训练算法：此步骤不适用于KNN算法

测试算法：计算错误率

使用算法：首先需要输入样本数据接结构化输出结果，然后运行KNN算法判定输入数据属于哪个分类，最后应用对计算出的分类执行后续处理。

3.2 调参

  • 距离度量

    使用距离为欧式距离

    更一般的距离为Lp距离和曼哈顿距离

  • K值的选择

    K值较小时，近似误差会减小，估计误差会变大。

    K值较大时，估计误差减小，近似误差越大。

    K=N时，无论实例输入什么，都简单地预测为训练实例中最多的一类。

    实际应用中，K值一般取一个比较小的数值。通常采用交叉验证选取最优K值

  • 分类决策规则

    多数表决规则 等价于 经验风险最小化

4. 代码实现

4.1 算法核心

1
2
3
4
5
6
7
8
9
10
11
12
13
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

4.2 sklearn实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import numpy as np
import matplotlib.pyplot as plt
from numpy import *
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets

n_neighbors = 3

# 导入一些要玩的数据
# iris = datasets.load_iris()
# X = iris.data[:, :2]  # 我们只采用前两个feature. 我们可以使用二维数据集避免这个丑陋的切片
# y = iris.target

# print 'X=', type(X), X
# print 'y=', type(y), y

X = array([[-1.0, -1.1], [-1.0, -1.0], [0, 0], [1.0, 1.1], [2.0, 2.0], [2.0, 2.1]])
y = array([0, 0, 0, 1, 1, 1])

# print 'X=', type(X), X
# print 'y=', type(y), y

h = .02  # 网格中的步长

# 创建彩色的地图
# cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
# cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])

cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00'])

for weights in ['uniform', 'distance']:
    # 我们创建了一个knn分类器的实例，并适合数据。
    clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
    clf.fit(X, y)

    # 绘制决策边界。为此，我们将为每个分配一个颜色
    # 来绘制网格中的点 [x_min, x_max]x[y_min, y_max].
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

    # 将结果放入一个彩色图中
    Z = Z.reshape(xx.shape)
    plt.figure()
    plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

    # 绘制训练点
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold)
    plt.xlim(xx.min(), xx.max())
    plt.ylim(yy.min(), yy.max())
    plt.title("3-Class classification (k = %i, weights = '%s')"
              % (n_neighbors, weights))

plt.show()

4.3 《机器学习实战》（python3.x）

​ 第二章 k-近邻算法

5. 补充

  • 精度高（小于最优贝叶斯最有分类器的2倍。证明：周志华《机器学习》）
  • 算法的收敛性（证明：李航《统计学习方法》P31）
  • 墙裂推荐：https://github.com/apachecn/MachineLearning
-------------感谢阅读-------------
0%