机器学习——k邻近算法和决策树算法

技术机器学习
k邻近算法, 决策树, 机器学习

前言

看理论教程时总是感觉太抽象了，所以经网友推荐开始看《机器学习实践》一书。到现在读了3章内容，发现这本书确实是很不错的机器学习的入门书。它从最简单的K邻近算法开始，以python为编程语言，编写实例代码，足步深入。本文便是对《机器学习实践》一书的中前两个分类算法的学习总结。

k邻近算法

在看到这个算法前，我真没有想到这样简单的算法也是机器学习算法的一种。有这样的感想是由于之前看理论的时被一大堆数据公式符号弄得头晕老涨，结果一来看实际的实例确是如此的简单，这巨大的反差让我很吃惊。不过这正式这本书非常好得一点，从浅入深，一开始并不一下子就涉及到那些复杂得理论和公式。

1. 原理

k邻近算法是分类算法得一种，它的个工作原理是：计算待分类数据与已知数据的距离，检测待测数据主要偏向哪一边，就将待测数据分向哪边。那么距离怎么求呢？使用待测数据的各个特征和已知数据的各个特征差的平方和开根号，公式如下：

2. 执行流程

整个算法的流程相当简单：

  1. 迭代整个数据集，计算每个数据点与输入数据的距离
  2. 选出与输入点距离最小的K个数据点
  3. 统计计算这K个数据不同类别的概率
  4. 概率高的类型作为输入数据的类型
3. 基本代码

整个分类器的Python代码量相当少，我这里就直接将书上的代码复制过来了，其中函数inX为待分类的数据，dataSet为已知数据集，labels为数据集对应的类型列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import numpy as np
def kNearestNeighborClassify(inX, dataSet, labels, k):
    dataSetSize = dataSetshape[0]
    # 将输入数据与每一个数据相减
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
    # 计算数据集的距离
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis = 1)
    distances = sqDistances**0.5
    # 找出距离最小的k个数据的所属类别的频数
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount = classCount.get(voteIlabel, 0) + 1
    sortedClassCount[voteIlabel] = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse = True)
    return sortedClassCount[0][0]
4. 优化——归一化原始数据

原始数据中的每个特征的取值范围有大有小，在使用上面代码分类时，就会导致特征值大的对结果的影响大，但是我们希望每一个特征都同等重要，所以我们需要将原始数据的做一次归一化操作，将每个特征值的范围都映射到0到1的范围内，归一化操作如下：

然后使用归一化的数据作为分类器的算法输入。

5. 优缺点
  • 优点：精度高、对异常值不敏感、无数据输入假定
  • 缺点：计算复杂度高、空间复杂度高

决策树

决策树是书中介绍的第二种分类算法，相比k邻近算法决策树的名号可是响亮得多，不过实际上决策树在使用上比k邻近算法还要简单、更容易理解的，它的难点是在于决策树的构建。

决策树本质上就是一个二叉树或多叉树，在其中的每一个非叶子节点上都会对特征进行分类判断，一般越重要的特征与靠近树的跟节点，也就是说越在前面被判断，通过这一层一层的判断来决定输入数据的最终分类。

1. 构造决策树原理

正如前面所说构建决策树，是决策树算法的难点和关键，书中是以ID3算法来划分数据集来构建决策树。ID3算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类，这里就不得不去理解下信息熵和信息增益的这类难懂的概念了。

信息熵：信息熵被定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

信息增益： 信息增益指的是划分前后信息熵的变化。

以ID3为划分标准的决策树，是通过计算分类系统的前后的信息增益，作为信息有序度的衡量标准，将信息增益最大的类型作为当前最优分类特征。

2. 构建决策树的步骤

构建决策数据一般会采用贪婪策略、利用递归的方法一次来构建整个决策树，其具体执行步骤如下：

  1. 对当前数据集求信息熵
  2. 尝试使用数据集种的每一个特征为标准进行分类，计算分类后的两个子系统信息熵的和
  3. 比较得到分类后信息增益最大的，作为当前的分类标准
  4. 在特征集种删除当前分类标准的特征
  5. 判断是否分类完成，如果没有，将未完成分类的数据递归重复所有操作

构建决策树的过程很费时，所以当决策树构建完成后，可以将其存储在文件中，使用时直接读取，反复使用。决策树的使用仅仅是需要做一些简单的比较就可以得到结果，相比每次分类都需要使用到使所有数据的K临近值算法，计算量极少。

3. 优缺点
  • 优点： 使用计算复杂度不高，输出结果容易理解，对中间值缺少不敏感
  • 缺点： 可能会产生过度匹配的问题
Compartir