Loading... ## 1. k-近邻算法 ### 1.1 简介 k近邻学习（kNN）是一种监督学习算法，它直接使用测试样本和训练样本，没有显式的训练过程，工作机制如下：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个邻居的信息来进行预测。通常，对于不同类型的任务，使用的预测方法不同： * 分类任务：投票法，选择k个样本中出现最多的类别标记作为预测结果 * 回归任务：平均法，将k个样本的实值输出标记的平均值作为预测结果 此外，还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。 <div class="tip inlineBlock success"> 优点：精度高、对异常值不敏感、无数据输入假定。 </div> <div class="tip inlineBlock warning"> 缺点：计算复杂度高、空间复杂度高。 </div> <div class="tip inlineBlock share"> 适用数据范围：数值型和标称型。 </div> ### 1.1 计算逻辑 图示：  绿色方块要被赋予哪个类别，五角星还是三角形？假定k等于5（虚线），蓝色三角形占比为3/5，大于五角星2/5，那么绿色方块将被赋予蓝色三角形那个类。如果k=10，则五角星所占比例6/10大于三角形所占比例4/10，那么绿色方块将被赋予五角星那个类。 > （1）给定测试对象，计算它与训练集中的每个对象的**距离**。 > （2）圈定距离**最近的k个**训练对象，作为测试对象的邻居。 > （3）根据这k个近邻对象所属的类别，找到**占比最高**的那个类别作为测试对象的预测类别。 影响KNN算法准确度的两个关键因素：K的选择和距离。 对于距离度量，一般使用两种计算公式：曼哈顿距离和欧式距离。 ### 1.2 一般流程 > （1）收集数据：可以使用任何方法 > （2）准备数据：距离计算所需要的数值，最好是结构化的数据格式 > （3）分析数据：可以使用任何方法 > （4）训练算法：此步骤不适用于k-近邻算法（kNN为懒惰学习的著名代表，此类学习在训练阶段仅仅是把训练样本保存起来，训练时间开销为0，待收到测试样本之后再进行处理。） > （5）测试算法：计算错误率 > （6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理 <button class="btn m-b-xs btn-success btn-addon" onclick='window.open("https://github.com/Anleeno-Xu/MLInAction/tree/master/chapter02","_blank")'><i class="iconfont icon-github-copy"></i>k-近邻算法代码</button> ## 2. 决策树 ### 2.1 简介 [决策树](https://baike.baidu.com/item/%E5%86%B3%E7%AD%96%E6%A0%91/10377049)(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法[ID3](https://baike.baidu.com/item/ID3), [C4.5](https://baike.baidu.com/item/C4.5)和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。 决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。 一个决策树包含三种类型的节点[[1]](https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91)： 1. 决策节点：通常用矩形框来表示 2. 机会节点：通常用圆圈来表示 3. 终结点：通常用三角形来表示 <div class="tip inlineBlock success"> 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。 </div> <div class="tip inlineBlock warning"> 缺点：可能会产生过度匹配的问题。 </div> <div class="tip inlineBlock share"> 适用数据范围：数值型和标称型。 </div> ### 2.2 一般流程 > （1）收集数据：可以使用任何方法 > （2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化 > （3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。 > （4）训练算法：构造树的数据结构 > （5）测试算法：使用经验树计算错误率 > （6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义 ### 2.3 一些概念 信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为$P_k(k=1,2,...,|y|)$，则D的信息熵定义为 $$ Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2p_k. $$ Ent(D)的值越小，则D的纯度越高。 假定离散属性a有V个可能的取值：$\left\{a^1 , a^2 , … , a^V \right\}$ ，若第v个分支结点包含了D中所有在属性a上取值为$a^v$的样本，记为$D^v$。每个分支节点的权重：$\dfrac{|D^v|}{|D|}$，即样本数越多的结点影响越大，于是属性a对样本集D进行划分所获得的信息增益为 $$ Gain(D,a)=Ent(D)-\sum^V_{v=1}\dfrac{|D^{v}|}{|D|}Ent(D^v). $$ 一般而言，信息增益越大，表示用属性a作为划分属性所获得的“纯度提升”越大。 信息增益[[2]](https://baike.baidu.com/item/%E4%BF%A1%E6%81%AF%E5%A2%9E%E7%9B%8A/8864911?fr=aladdin)[[3]](https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA))：书中简单来讲就是划分数据集之前之后信息发生的变化，用来描述一个属性区分数据样本的能力。 <button class="btn m-b-xs btn-success btn-addon" onclick='window.open("https://github.com/Anleeno-Xu/MLInAction/tree/master/chapter03","_blank")'><i class="iconfont icon-github-copy"></i>决策树代码</button> Last modification：November 10th, 2020 at 07:40 pm © 允许规范转载 Support 喜欢就加个鸡腿吧！ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
