机器学习基本算法概述☞监督学习——分类代码在这，基于python3（原书代码是python2）

这里只是一个总结，原书已经讲解很清楚了，不清楚的直接看代码，或者李航的统计学习方法也有公式推导。

目录1

• 1.k-近邻算法（kNN）
• 2.决策树（ID3）
• 3.基于概率论的分类方法：朴素贝叶斯
• 4.Logistic回归
• 5.支持向量机（SVM）
• 6.Adaboost元算法提高分类性能
• 7.非均衡分类问题
  

==========================

一、k-近邻算法（kNN）1.概述

k-NN算法是最简单的分类算法，主要的思想是计算待分类样本与训练样本之间的差异性，并将差异按照由小到大排序，选出前面K个差异最小的类别，并统计在K个中类别出现次数最多的类别为最相似的类，最终将待分类样本分到最相似的训练样本的类中。与投票(Vote)的机制类似。
k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数
据。

• 优点：精度高，对异常值不敏感，无数据输入假定
• 缺点：时间和空间复杂度高，无法获取样本特征
• 数据：数值型和标称型
  

2.算法介绍

• 训练算法：此步骤不适用于k-临近算法
• 测试算法：计算错误率
• 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-临近算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续处理。
  

##2.1 错误率

error_rate=分错的样本数量 / 总样本数量

##2.2 归一化

newvalue=(oldvalue-min) / (mx-min)

3.伪代码

对未知类别属性的数据集中的每个点依次执行以下操作：
(1)计算已知类别数据集中的点与当前点之间的距离；
(2)按照距离递增次序排序；
(3)选取与当前点欧氏距离最小的k个点；
(4)确定前k个点所在类别的出现频率；
(5)返回前k个点出现频率最高的类别作为当前点的预测分类。

4.实例1、约会网站配对案例

某人将对象分为三类人，不喜欢的人，魅力一般的人，极具魅力的人。
这里实现的过程是，给定一个人的数据，进行打分预测属于哪类人，从而帮助用户是否选择相亲进行决策。

2、手写数字识别实战案例5.存在的问题及解决方法、总结

算法小结：
（1）如果我们改变训练样本的数目，调整相应的k值，都会对最后的预测错误率产生影响，我们可以根据错误率的情况，对这些变量进行调整，从而降低预测错误率

（2）k近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k近邻算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离，实际使用时也可能会非常耗时
（3）此外，k近邻算法无法给出数据的基础结构信息，因此我们无法知道平均实例样本和典型实例样本具有怎样的特征。

1、计算复杂度的问题
　　在K-NN算法中，每一个预测样本需要与所有的训练样本计算相似度，计算量比较大。比较常用的方法有K-D树，局部敏感哈希等等

2、K-NN的均匀投票
　　在上述的K-NN算法中，最终对标签的选择是通过投票的方式决定的，在投票的过程中，每一个训练样本的投票的权重是相等的，
　　(1)可以对每个训练样本的投票加权，以期望最相似的样本有更高的决策权。
　　(2)归一化。

===============================================================

二、决策树ID31.概述

　　k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。

　　决策树算法是从数据的属性（或者特征）出发，以属性作为基础，划分不同的类。
　　实现决策树的算法有很多种，有ID3、C4.5和CART等算法。

• 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
• 缺点：可能会产生过度匹配问题。
• 数据：数值型和标称型
  

2.算法介绍

• 训练算法：构造树的数据结构。
• 测试算法：使用经验树计算错误率。
• 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据
  的内在含义。
  

2.1 ID3算法

　　ID3算法是由Quinlan首先提出的，该算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。
(1) 在ID3算法中，选择信息增益最大的属性作为当前的特征对数据集分类。
(2) 判断划分结束,第一种为划分出来的类属于同一个类，第二种为遍历完所有划分数据集的属性。

2.2 信息增益

　　 ID3算法是以信息熵和信息增益作为衡量标准的分类算法。
　　熵的概念主要是指信息的混乱程度，变量的不确定性越大，熵的值也就越大，熵定义为信息的期望值。
符号<span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="xi" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-; min-height: 0px; border: 0px; word-break: break-all; position: relative;">xixi的信息定义为:

[color=rgba(0, 0, 0, 0.75)]l(xi)=−log2p(xi)(1)(1)l(xi)=−log2⁡p(xi)

[color=rgba(0, 0, 0, 0.75)]　　其中[color=rgba(0, 0, 0, 0.75)]p(xi)p(xi)[color=rgba(0, 0, 0, 0.75)]是选择该分类的概率。
[color=rgba(0, 0, 0, 0.75)]　　为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

[color=rgba(0, 0, 0, 0.75)]H=−∑i=1np(xi)log2p(xi)(2)(2)H=−∑i=1np(xi)log2⁡p(xi)

[color=rgba(0, 0, 0, 0.75)]　　划分数据集的大原则是：将无序的数据变得更加有序。在划分数据集之前之后信息发生的变化称为信息增益，，获得信息增益最高的特征就是最好的选择。
3.伪代码

对未知类别属性的数据集中的每个点依次执行以下操作：
(1)选择特征
(2)划分数据集——寻找划分数据集的最好特征，创建分支节点
(3)满足终止条件
(4)满足就结束，不满足则回到(1)

4.实例4.1 预测眼镜蛇类型

存在过度匹配问题

5.存在的问题及解决方法

1、过度匹配数据集

   裁剪决策树，合并相邻无法产生大量信息增益的叶节点，消除过度匹配问题。

• 1
  

　　当决策树的复杂度较大时，很可能会造成过拟合问题。此时，我们可以通过裁剪决策树的办法，降低决策树的复杂度，提高决策树的泛化能力。比如，如果决策树的某一叶子结点只能增加很少的信息，那么我们就可将该节点删掉，将其并入到相邻的结点中去，这样，降低了决策树的复杂度，消除过拟合问题。

===============================================================