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 喜欢就加个鸡腿吧! Appreciate the author 支付宝微信