决策树是一种树形结构，为人们提供决策依据，决策树可以用来回答yes和no问题，它通过树形结构将各种情况组合都表示出来，每个分支表示一次选择（选择yes还是no），直到所有选择都进行完毕，最终给出正确答案。决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。在实际构造决策树时，通常要进行剪枝，这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种：先剪枝——在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。后剪枝——先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。

今天去面试算法岗位，被问到了一个问题，分享给大家，希望对大家有帮助：决策树对缺失值是如何处理的?决策树处理缺失要考虑以下三个问题： 1、当开始选择哪个属性来划分数据集时，样本在某几个属性上有缺失怎么处理：（1）忽略这些缺失的样本。 （2）填充缺失值，例如给属性A填充一个均值或者用其他方法将缺失值补全。 （3）计算信息增益率时根据缺失率的大小对信息增益率进行打折，例如计算属性A的信息增益率，若属性 A的缺失率为0.9，则将信息增益率乘以0.9作为最终的信息增益率。 2、一个属性已经被选择，那么在决定分割点时，有些样本在这个属性上有缺失怎么处理？ （1）忽略这些缺失的样本。 （2）填充缺失值，例如填充一个均值或者用其他方法将缺失值补全。 把缺失的样本，按照无缺失的样本被划分的子集样本个数的相对比率，分配到各个子集上去，至于那 些缺失样本分到子集1，哪些样本分配到子集2，这个没有一定准则，可以随机而动。（3）把缺失的样本分配给所有的子集，也就是每个子集都有缺失的样本。（4）单独将缺失的样本归为一个分支。 3、决策树模型构建好后，测试集上的某些属性是缺失的，这些属性该怎么处理？（1）如果有单独的缺失值分支，依据此分支。 （2）把待分类的样本的属性A分配一个最常出现的值，然后进行分支预测。 （3）待分类的样本在到达属性A结点时就终止分类，然后根据此时A结点所覆盖的叶子节点类别状况为其 分配一个发生概率最高的类。我面试的时候，回答了一些，没有答全，但是一定考虑到上述三种情况。希望大家下次再碰到这种面试题时，不要漏答了。大家还有什么要补充的吗

避免决策树过分拟合的策略有那些？

    可能是因为我数学功底比较差，那些公式都看不懂是什么意思，但是复习数学又不知道从哪里开始，如果全部复习的话又太耽误时间，如果我需要学习机器学习，数学里面的那些知识点是重点啊，有没有大佬说一下。

机器学习经典算法之一决策树算法常用的有哪些呢，目前学到了一个ID3最大信息增益，可是对概念还是一知半解，希望论坛热心的小伙伴来解答一下，跪谢！

常用机器学习模型1.朴素贝叶斯模型　　朴素贝叶斯模型是一个简单却很重要的模型，它是一种生成模型，也就是它对问题进行联合建模，利用概率的乘法法则，我们可以得到：　　由于上述形式复杂，因此朴素贝叶斯作出一个假设，也就是在给定y的条件下，x1,...,xn之间的生成概率是完全独立的，也就是：　　注意此处并不是说x1,...,xn的生成概率是相互独立的，而是在给定y的条件下才是独立的，也就是这是一种”条件独立”。了解概率图模型的同学，下面的图模型就可以很好地阐述这个问题：　　既然我们说朴素贝叶斯是一种生成模型，那它的生成过程是怎样的呢？对于邮件垃圾分类问题，它的生成过程如下：　　首先根据p(y)采用得到y，从而决定当前生成的邮件是垃圾还是非垃圾　　确定邮件的长度n，然后根据上一步得到的y，再由p(xi|y)采样得到x1,x2,...,xn　　这就是朴素贝叶斯模型。显然，朴素贝叶斯的假设是一种很强的假设，实际应用中很少有满足这种假设的的情况，因为它认为只要在确定邮件是垃圾或者非垃圾的条件下，邮件内容地生成就是完全独立地，词与词之间不存在联系。　　朴素贝叶斯模型优、缺点　　优点：对小规模的数据表现很好，适合多分类任务，适合增量式训练。　　缺点：对输入数据的表达形式很敏感。2.决策树模型　　决策树模型是一种简单易用的非参数分类器。它不需要对数据有任何的先验假设，计算速度较快，结果容易解释，而且稳健性强　　　　在复杂的决策情况中，往往需要多层次或多阶段的决策。当一个阶段决策完成后，可能有m种新的不同自然状态发生；每种自然状态下，都有m个新的策略可选择，选择后产生不同的结果并再次面临新的自然状态，继续产生一系列的决策过程，这种决策被称为序列决策或多级决策。此时，如果继续遵循上述的决策准则或采用效益矩阵分析问题，就容易使相应的表格关系十分复杂。决策树是一种能帮助决策者进行序列决策分析的有效工具，其方法是将问题中有关策略、自然状态、概率及收益值等通过线条和图形用类似于树状的形式表示出来。　　决策树模型就是由决策点、策略点(事件点)及结果构成的树形图，一般应用于序列决策中，通常以最大收益期望值或最低期望成本作为决策准则，通过图解方式求解在不同条件下各类方案的效益值，然后通过比较，做出决策。　　决策树模型优、缺点　　优点：浅层的(Shallow)决策树视觉上非常直观，而且容易解释；是对数据的结构和分布不需作任何假设；是可以捕捉住变量间的相互作用(Interaction)。　　缺点：深层的(Deep)决策树视觉上和解释上都比较困难；决策树容易过分微调于样本数据而失去稳定性和抗震荡性；决策树对样本量(Sample Size)的需求比较大；处理缺失值的功能非常有限。3.KNN算法　　KNN即最近邻算法，核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。其主要过程为：　　1.计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；　　2. 对上面所有的距离值进行排序；　　3. 选前k个最小距离的样本；　　4. 根据这k个样本的标签进行投票，得到最后的分类类别；　　如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取，比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。　　近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。　　KNN算法优、缺点　　优点：简单，易于理解，易于实现，无需估计参数，无需训练；理论成熟，既可以用来做分类也可以用来做回归；可用于非线性分类；适合对稀有事件进行分类；准确度高，对数据没有假设，对outlier不敏感。　　缺点：计算量大；样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；需要大量的内存；可理解性差，无法给出像决策树那样的规则。4.SVM算法　　SVM(Support Vector Machine)指的是支持向量机，是常见的一种判别方法。在机器学习领域，是一个有监督的学习模型，通常用来进行模式识别、分类以及回归分析。　　SVM的主要思想可以概括为两点：　　1.它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。　　2.它基于结构风险最小化理论之上在特征空间中构建最优超平面，使得学习器得到全局最优化，并且在整个样本空间的期望以某个概率满足一定上界。　　SVM算法优、缺点　　优点：可用于线性/非线性分类，也可以用于回归；低泛化误差；容易解释；计算复杂度较低。　　缺点：对参数和核函数的选择比较敏感；原始的SVM只比较擅长处理二分类问题。5.logistic回归模型　　logistic回归又称logistic回归分析，是一种广义的线性回归分析模型，常用于数据挖掘，疾病自动诊断，经济预测等领域。例如，探讨引发疾病的危险因素，并根据危险因素预测疾病发生的概率等。以胃癌病情分析为例，选择两组人群，一组是胃癌组，一组是非胃癌组，两组人群必定具有不同的体征与生活方式等。因此因变量就为是否胃癌，值为“是”或“否”，自变量就可以包括很多了，如年龄、性别、饮食习惯、幽门螺杆菌感染等。自变量既可以是连续的，也可以是分类的。然后通过logistic回归分析，可以得到自变量的权重，从而可以大致了解到底哪些因素是胃癌的危险因素。同时根据该权值可以根据危险因素预测一个人患癌症的可能性。Logistic回归模型的适用条件：　　1.因变量为二分类的分类变量或某事件的发生率，并且是数值型变量。但是需要注意，重复计数现象指标不适用于Logistic回归。　　2.残差和因变量都要服从二项分布。二项分布对应的是分类变量，所以不是正态分布，进而不是用最小二乘法，而是最大似然法来解决方程估计和检验问题。　　3.自变量和Logistic概率是线性关系　　4.各观测对象间相互独立。　　Logistic回归实质：发生概率除以没有发生概率再取对数。就是这个不太繁琐的变换改变了取值区间的矛盾和因变量自变量间的曲线关系。究其原因，是发生和未发生的概率成为了比值 ，这个比值就是一个缓冲，将取值范围扩大，再进行对数变换，整个因变量改变。不仅如此，这种变换往往使得因变量和自变量之间呈线性关系，这是根据大量实践而总结。所以，Logistic回归从根本上解决因变量要不是连续变量怎么办的问题。还有，Logistic应用广泛的原因是许多现实问题跟它的模型吻合。例如一件事情是否发生跟其他数值型自变量的关系。　　logistic回归模型优、缺点　　优点：实现简单；分类时计算量非常小，速度很快，存储资源低。　　缺点：容易欠拟合，一般准确度不太高；能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分。

【Python算法分类与预测】——决策树1.决策树定义　　决策树方法在分类、预测、规则提取等领域有着广泛的应用。20 世纪 70 年代后期和 80 年代初期，机器学习研究者 J.Ross Quinlan 提出了 ID3 算法以后，决策树就在机器学习与数据挖掘领域取得了巨大的发展。Quinlan 后来又提出了 C4.5，这成为了新的监督学习算法。1984年，几位统计学专家提出了 CART 分类算法。ID3 和 CART 算法几乎同时被提出，但都是采用的类似的方法从训练样本中学习决策树。决策树是一种树状结构，它的每个叶节点对应一个分类，非叶节点对应着在某个属性上的划分，根据样本在该属性上的不同值将其划分成若干个子集，而对于非纯的叶节点，多数类的标号给出到达这个节点的样本所属的类。构造决策树的核心的问题是在每一步中如何选择适当的属性对样本进行拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树其实是一个自上而下，分而治之的过程。2.常用决策树算法　　常用的决策树算法有三种，分别是 ID3 算法、C4.5 算法、CART 算法三种。　　(1) ID3 算法：此算法的核心在于决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所应采取的合适属性；　　(2) C4.5 算法：此决策树生成算法相对于 ID3 算法的重要改进是使用信息增益率来选择节点属性，此算法可以克服ID3算法的不足。ID3算法只使用于离散的描述属性，而 C4.5 算法既能够处理离散的描述属性，又能够处理连续的描述属性；　　(3) CART 算法：CART 决策树是一种十分有效的非参数分类和回归方法，它通过构建树、修剪树、评估树来构建一个二叉树，当终结点是连续变量时，该树为回归树；当终结点是分类变量时，该树为分类树。3.决策树基本思想及内容　　决策树的基本思想是，迭代式的根据字段的不同值将数据分成不同的组，再评估分组后组内的同性值，如果需要则继续分成不同的组。此方法的优点特别明显，它有较好的可解释性，并且在非线性环境下性能较好。但它也有缺点，如果缺少修剪或者交叉验证很容易过拟合。4.决策树的使用基本流程　　(1) 将所有数据放在同一个组中；　　(2) 找出最佳的字段分割（split）；　　(3) 将数据在这个分割（称为节点）上分成两组（称为叶子）；　　(4) 继续上两步直到组包含的样本过少或者组内差异已经足够小。4.决策树计算公式及语法　　决策树有几个衡量分组内差异性的常用指标，包括基尼系数（Gini index）、差异（deviance） 或信息增量（information gain）。基尼系数的计算公式如下，在使用此计算公式时，若结果为 0 则表示发分组绝对同质，若为 0.5 则表示该分组绝对异质：差异或信息增益的计算公式如下，在使用此计算公式时，若结果为 0 则表示该分组绝对同质，若为 1 则表示该分组绝对异质：决策树的方法即可用于分类也可用于回归，本实验主要介绍的是决策树分类。5.实验操作    5.1.操作系统　　操作机：Linux_Ubuntu　　操作机默认用户：root    5.2.实验工具        5.2.1.python　　Python是一种计算机程序设计语言。是一种动态的、面向对象的脚本语言，最初被设计用于编写自动化脚本(shell)，随着版本的不断更新和语言新功能的添加，越来越多被用于独立的、大型项目的开发。Python已经成为最受欢迎的程序设计语言之一。自从2004年以后，python的使用率呈线性增长。2011年1月，它被TIOBE编程语言排行榜评为2010年度语言。      由于Python语言的简洁性、易读性以及可扩展性，在国外用Python做科学计算的研究机构日益增多，一些知名大学已经采用Python来教授程序设计课程。例如卡耐基梅隆大学的编程基础、麻省理工学院的计算机科学及编程导论就使用Python语言讲授。      众多开源的科学计算软件包都提供了Python的调用接口，例如著名的计算机视觉库OpenCV、三维可视化库VTK、医学图像处理库ITK。而Python专用的科学计算扩展库就更多了，例如如下3个十分经典的科学计算扩展库：NumPy、SciPy和matplotlib，它们分别为Python提供了快速数组处理、数值运算以及绘图功能。因此Python语言及其众多的扩展库所构成的开发环境十分适合工程技术、科研人员处理实验数据、制作图表，甚至开发科学计算应用程序。        5.2.2.Numpy　　NumPy系统是Python的一种开源的数值计算扩展。这种工具可用来存储和处理大型矩阵，比Python自身的嵌套列表（nested list structure)结构要高效的多（该结构也可以用来表示矩阵（matrix））。　　NumPy（Numeric Python）提供了许多高级的数值编程工具，如：矩阵数据类型、矢量处理，以及精密的运算库。专为进行严格的数字处理而产生。多为很多大型金融公司使用，以及核心的科学计算组织如：Lawrence Livermore，NASA用其处理一些本来使用C++，Fortran或Matlab等所做的任务。        5.2.3.scikit-learn      scikit-learn，Python 中的机器学习，简单高效的数据挖掘和数据分析工具，可供大家使用，可在各种环境中重复使用，建立在 NumPy，SciPy 和 matplotlib 上开放源码，可商业使用 - BSD license。        5.2.4.Matplotlib       Matplotlib 是一个 Python 的 2D绘**，它以各种硬拷贝格式和跨平台的交互式环境生成出版质量级别的图形。通过 Matplotlib，开发者可以仅需要几行代码，便可以生成绘图，直方图，功率谱，条形图，错误图，散点图等。        5.2.5.pandas        Python Data Analysis Library 或 pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。Pandas 纳入了大量库和一些标准的数据模型，提供了高效地操作大型数据集所需的工具。pandas提供了大量能使我们快速便捷地处理数据的函数和方法。你很快就会发现，它是使Python成为强大而高效的数据分析环境的重要因素之一。    5.3导入所需要的库:numpy,matplotlib.pyplot,pandas代码如下:# Importing the libraries import numpy as np import matplotlib.pyplot as plt import pandas as pd    5.4.加载数据集代码如下：# Importing the dataset dataset = pd.read_csv('数据集路径') X = dataset.iloc[:, [2, 3]].values y = dataset.iloc[:, 4].values注意：实验中以数据集的实际地址为准。      实验中已经带有相应数据集，点击左下“数据”标识，对数据集的地址进行查看复制。我们直接将地址复制并放入上述代码中进行加载就可以了。注意：如果在自己的实际生产中，要以自己的数据地址为准。       如下给出数据，可将数据创建响相应的数据集用于字日常训练，也可在实验平台中数据集模块下的的“社交网络测试数据集”中进行查看。其具体数据内容如下：见附件！！！    5.5.将数据集分割为训练集和测试集代码如下：# Splitting the dataset into the Training set and Test set from sklearn.model_selection import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.25, random_state = 0)    5.6.特征缩放代码如下：# Feature Scaling from sklearn.preprocessing import StandardScaler sc = StandardScaler() X_train = sc.fit_transform(X_train) X_test = sc.transform(X_test)    5.7.使用决策树对数据进行处理代码如下：# Fitting the Decision Tree to the Training set from sklearn.tree import DecisionTreeClassifier classifier = DecisionTreeClassifier(criterion = 'entropy', random_state = 0) classifier.fit(X_train, y_train)    5.8.对测试集进行分类：代码如下：# Predicting the Test set results y_pred = classifier.predict(X_test)    5.9.制造混淆矩阵来评估分类器性能：代码如下：# Making the Confusion Matrix from sklearn.metrics import confusion_matrix cm = confusion_matrix(y_test, y_pred)    5.10.绘制训练数据分类结果：# Visualising the Training set results from matplotlib.colors import ListedColormap X_set, y_set = X_train, y_train X1, X2 = np.meshgrid(np.arange(start = X_set[:, 0].min() - 1, stop = X_set[:, 0].max() + 1, step = 0.01),                      np.arange(start = X_set[:, 1].min() - 1, stop = X_set[:, 1].max() + 1, step = 0.01)) plt.contourf(X1, X2, classifier.predict(np.array([X1.ravel(), X2.ravel()]).T).reshape(X1.shape),              alpha = 0.75, cmap = ListedColormap(('red', 'green'))) plt.xlim(X1.min(), X1.max()) plt.ylim(X2.min(), X2.max()) for i, j in enumerate(np.unique(y_set)):     plt.scatter(X_set[y_set == j, 0], X_set[y_set == j, 1],                 c = ListedColormap(('orange', 'blue'))(i), label = j) plt.title('Classifier (Training set)') plt.xlabel('Age') plt.ylabel('Estimated Salary') plt.legend() plt.show()训练数据分类结果如下：    5.11.绘制测试数据分类结果：# Visualising the Test set results from matplotlib.colors import ListedColormap X_set, y_set = X_test, y_test X1, X2 = np.meshgrid(np.arange(start = X_set[:, 0].min() - 1, stop = X_set[:, 0].max() + 1, step = 0.01),                      np.arange(start = X_set[:, 1].min() - 1, stop = X_set[:, 1].max() + 1, step = 0.01)) plt.contourf(X1, X2, classifier.predict(np.array([X1.ravel(), X2.ravel()]).T).reshape(X1.shape),              alpha = 0.75, cmap = ListedColormap(('red', 'green'))) plt.xlim(X1.min(), X1.max()) plt.ylim(X2.min(), X2.max()) for i, j in enumerate(np.unique(y_set)):     plt.scatter(X_set[y_set == j, 0], X_set[y_set == j, 1],                 c = ListedColormap(('orange', 'blue'))(i), label = j) plt.title('Classifier (Test set)') plt.xlabel('Age') plt.ylabel('Estimated Salary') plt.legend() plt.show()测试数据分类结果如下：

作者|程哥本文主要为机器学习第三部分，这部分我们重点来探讨一下决策树算法，主要分2部分来解说分别是：决策树、sklearn，欢迎大家一起交流学习。机器学习第三部分：决策树算法.pdf( 预览 )