pythonid3算法

A. python中的sklearn中决策树使用的是哪一种算法

要弄清楚这个问题，首先要弄懂决策树三大流行算法ID3、C4.5和CART的原理，以及sklearn框架下DecisionTreeClassifier的帮助文档。
3个算法的主要区别在于度量信息方法、选择节点特征还有分支数量的不同。
ID3，采用熵（entropy）来度量信息不确定度，选择“信息增益”最大的作为节点特征，它是多叉树，即一个节点可以有多个分支。
C4.5，同样采用熵（entropy）来度量信息不确定度，选择“信息增益比”最大的作为节点特征，同样是多叉树，即一个节点可以有多个分支。
CART，采用基尼指数（Gini index）来度量信息不纯度，选择基尼指数最小的作为节点特征，它是二叉树，即一个节点只分两支。
然后你认真阅读sklearn的DecisionTreeClassifier的帮助文档，可以发现，度量信息的方法默认是Gini，但可以改成entropy，请按需选择；构建的树是二叉树；可以通过设置max_deepth、max_leaf等来实现“剪枝”，这是根据CART的损失函数减少的理论进行的。
所以总结说，如果信息度量方法按照默认的设置，那么sklearn所用的决策树分类器就是CART，如果改成了entropy，那么只是使用了别的度量方法而已。其实两者差不多。

B. python中的sklearn中决策树使用的是哪一种算法

sklearn中决策树分为DecisionTreeClassifier和DecisionTreeRegressor，所以用的算法是CART算法，也就是分类与回归树算法(classification and regression tree,CART)，划分标准默认使用的也是Gini，ID3和C4.5用的是信息熵，为何要设置成ID3或者C4.5呢

C. ML - 决策树(decision tree)

机器学习中分类和预测算法的评估：

判定树是一个类似于流程图的树结构：其中，每个内部结点表示在一个 属性上的测试 ，每个分支代表一个 属性输出 ，而每个树叶结点代表 类或类分布 。树的最顶层是根结点。
机器学习中分类方法中的一个重要算法

信息和抽象，如何度量？

1948年，香农提出了 ”信息熵(entropy)“的概念

一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者

是我们一无所知的事情，需要了解大量信息==> 信息量的度量就等于不确定性的多少

例子：猜世界杯冠军，假如一无所知，猜多少次？

每个队夺冠的几率不是相等的

比特(bit)来衡量信息的多少

变量的不确定性越大，熵也就越大

3.1 决策树归纳算法 （ ID3 ）

1970-1980， J.Ross. Quinlan, ID3算法

选择属性（A为age时）判断结点

信息获取量(Information Gain) ：
Gain(A) = Info(D) - Infor_A(D)
Gain(A) =按yes/no分的熵 - 按A属性分类的熵

通过A来作为节点分类获取了多少信息

类似
Gain(income) = 0.029
Gain(student) = 0.151
Gain(credit_rating)=0.048
所以，选择age作为第一个根节点

重复。。。

算法：

*其他算法：

C4.5 : Quinlan

Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)

共同点：都是贪心算法，自上而下(Top-down approach)

区别：属性选择度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)

先剪枝

后剪枝

直观，便于理解，小规模数据集有效

处理连续变量不好（离散化，阈值选择对结果影响大）

类别较多时，错误增加的比较快

可规模性一般

1. Python

2. Python机器学习的库： scikit-learn

2.1： 特性：

简单高效的数据挖掘和机器学习分析

对所有用户开放，根据不同需求高度可重用性

基于Numpy, SciPy和matplotlib

开源，商用级别：获得 BSD许可

2.2 覆盖问题领域：

分类（classification), 回归（regression), 聚类（clustering), 降维(dimensionality rection)

模型选择(model selection), 预处理(preprocessing)

3. 使用用scikit-learn

安装scikit-learn: pip, easy_install, windows installer

安装必要package：numpy， SciPy和matplotlib， 可使用 Anaconda (包含numpy, scipy等科学计算常用package）

4. 例子：

文档： http://scikit-learn.org/stable/moles/tree.html

安装 Graphviz： http://www.graphviz.org/
配置环境变量
转化dot文件至pdf可视化决策树：dot -Tpdf iris.dot -o outpu.pdf

D. 决策树(decisionTree)

决策树(decisionTree)是一种基本的分类和回归方法。此文仅讨论用于分类方法的决策树。

决策树的学习通常分为3步：

决策树的学习的思想主要源于

定义决策树 ：

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点又分为内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
形如：

其中，圆表示内部结点，方框表示叶结点。

if-then规则，简单来说就是 ：

举例：对于一个苹果，外表是红色的是红苹果，外表是绿色的是青苹果。可以表示为：

if-then规则集合具有一个重要的性质：

这就是说每一个实例都被一条路径或规则覆盖，并且只被一条路径或规则覆盖。这里所谓的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。

给定数据集：

其中， 为输入实例（特征向量），含有 个特征， 为类标记， , 为样本容量。

目标 ：
根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确分类。

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。

如果我们利用某一个特征进行分类的结果与随机分类的结果没什么很大的差别的话，则称这个特征没有分类能力。

那么问题来了，怎么选择特征呢？

通常特征选择的准则是

下面通过例子来说明一下。

目标 ：
希望通过所给的训练集数据，学习一个贷款申请的决策树。当新的客户提出贷款申请的时候，根据申请人的特征利用决策树决定是否批准贷款申请。

可见这里共有4个特征可供选择。用特征选择的准则是 。接下来介绍 。

：
熵是表示随机变量不确定性的度量。

设 是一个取有限个值的随机变量，其概率分布为

则随机变量 的熵定义为

若 ，则定义 。通常对数取以2为底，或是以 为底，熵的单位分布为比特（bit）或是纳特（nat）。
由上式可知，熵只依赖 的分布，而已 的值无关，则 的熵还可记作 ，即

则从定义可知

当随机变量只取2个值的时候，例如 时， 的分布为

熵为

熵随概率变化的曲线为

当 或 时 ，随机变量完全没有不确定性，当 时 ，熵取值最大，随机变量不确定性最大。

设随机变量 ，其联合概率分布

条件熵 表示在已知随机变量 的条件下随机变量 的不确定性。随机变量 给定条件下随机变量 的条件熵(conditional entropy)，定义为 给定条件下 的条件概率分布的熵对 的数学期望

信息增益
特征 对训练集 的信息增益

根据信息增益准则的特征选择方法：对训练集 ，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征。

前期定义各个量：

信息增益的算法
输入：训练集 和特征 ；
输出：特征 对训练集 的信息增益

回看刚才的例子，

解 ：

这一次我很无聊的想用一下.csv文件类型。

所以训练数据集部分如下，我存在一个loan.csv文件里了。对.csv文件的各种处理一般由python的pandas模块完成。

第一步，导入相关模块

第二步，读入数据

若是使用jupyter，可以即刻查看一下数据，和数据标签。

可以看出，除了'ID'之外前4个标签 'age', 'work', 'own house', 'Credit conditions'为我们一直在说的特征 ，而最后一个标签'label'是我们所说的类 ，所以要处理一下这些标签，

第三步，计算训练集 的熵 ：

这里会用到pandas的一个统计数据的功能， groupby(by = [列]).groups ，将数据统计成字典的形式，这么说比较抽象，看下图，将我们用pandas读入的data，分为2类， ， Index 表示索引，即第0，1，4，5，6，14（python计数从0开始）个数据的 ，第2，3，7，8，9，10，11，12，13个数据的 .

那么计算训练集 的熵

第四步，计算特征 对数据集 的条件熵

第五步 ，计算信息增益

输入：训练集 和特征 和阈值 ；
输出：决策树
(1) 中所有实例都属于同一类 ，则 为单结点树，并将类 作为该结点的类标记，返回 ；
(2) 若 ，则 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(3)否则，按照上述信息增益的算法，计算 中各个特征对 的信息增益，选择信息增益最大的特征 ；
(4)如果特征 的信息增益小于阈值 ，将置 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(5)否则，对 的每一个可能值 ，依 将 分割为若干非空子集 ，将 中实例数最大的类 作为该结点的类标记，构建子结点，由结点及其子结点构成树 ，返回 ；
(6)对第 个子结点，以 为训练集，以 为特征集，递归的调用步骤(1)~步骤(5)，得到子树 ，返回 。

对上述表的训练集数据，利用ID3算法建立决策树。

解 ：

第一次迭代 ：

【特征：有自己的房子】将数据集 划分为2个子集 （有自己的房子）和 （没有自己的房子），观察一下 和 ：

：

由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。

：

对于 则需从特征 中选择新的特征。

第二次迭代 ：

将 看作新的数据集 。【特征：有工作】有2个可能值，划分为2个子集 （有工作）和 （没有工作），观察一下 和 ：

：

由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。

：

E. 人工智能到底是学些什么

从大的技术层面来看，人工智能的知识体系主要涉及到六个大的学习方向，包括自然语言处理、计算机视觉、机器学习（深度学习）、自动推理、知识表示和机器人学，这些方向各有体系且联系紧密。

人工智能是典型的交叉学科，涉及到数学、哲学、控制学、计算机、经济学、神经学和语言学等学科，同时学习人工智能还需要具有一定的实验环境，对于数据、算力和算法都有一定的要求，所以当前人工智能领域的人才培养依然以研究生教育为主。

简介

对于初学者来说，如果想入门人工智能领域，可以从机器学习入手，一方面机器学习的知识体系相对比较容易理解，另一方面机器学习的应用场景也比较多，机器学习也是大数据分析的两种常见方式之一。

机器学习的步骤涉及到数据收集、算法设计、算法实现、算法训练、算法验证和算法应用，这个过程需要学习编程语言、数据整理和算法设计这三大块内容。

编程语言可以从Python语言开始学起，目前Python语言在机器学习领域的应用也比较普遍，有大量的案例可以参考。在学习的初期完全可以采用一些公开的数据集，这样也方便做结果对比，而算法可以从基础的常见算法入手，比如决策树、朴素贝叶斯、支持向量机等等。

F. 如何将python生成的决策树利用graphviz画出来

#这里有一个示例，你可以看一下。
#http://scikit-learn.org/stable/moles/tree.html
>>>fromIPython.displayimportImage
>>>dot_data=tree.export_graphviz(clf,out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True,rounded=True,
special_characters=True)
>>>graph=pydotplus.graph_from_dot_data(dot_data)
>>>Image(graph.create_png())

G. 决策树（Decision Tree）

决策树是一种非参数有监督的机器学习方法，可以用于解决回归问题和分类问题。通过学习已有的数据，计算得出一系列推断规则来预测目标变量的值，并用类似流程图的形式进行展示。决策树模型可以进行可视化，具有很强的可解释性，算法容易理解，以决策树为基础的各种集成算法在很多领域都有广泛的应用。

熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，信息熵代表着一个事件或一个变量等所含有的信息量。 在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。

发生概率低的事件比发生概率高的事件具有更大的不确定性，需要更多的信息去描述他们，信息熵更高。

我们可以用计算事件发生的概率来计算事件的信息，又称“香农信息”（ Shannon Information ）。一个离散事件x的信息可以表示为：
h(x) = -log(p(x))
p() 代表事件x发生的概率， log() 为以二为底的对数函数，即一个事件的信息量就是这个事件发生的概率的负对数。选择以二为底的对数函数代表计算信息的单位是二进制。因为概率p(x)小于1，所以负号就保证了信息熵永远不为负数。当事件的概率为1时，也就是当某事件百分之百发生时，信息为0。

熵（ entropy ），又称“香农熵”（ Shannon entropy ），表示一个随机变量的分布所需要的平均比特数。一个随机变量的信息熵可以表示为：
H(x) = -sum(each k in K p(k)log(p(k)))
K表示变量x所可能具有的所有状态（所有事件），将发生特定事件的概率和该事件的信息相乘，最后加和，即可得到该变量的信息熵。可以理解为，信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是事件信息量的期望。

当组成该随机变量的一个事件的概率为1时信息熵最小，为0， 即该事件必然发生。当组成该随机变量的所有事件发生的概率相等时，信息熵最大，即完全不能判断那一个事件更容易发生，不确定性最大。

当一个事件主导时，比如偏态分布（ Skewed Probability Distribution ），不确定性减小，信息熵较低（low entropy）；当所有事件发生概率相同时，比如均衡分布（ Balanced Probability Distribution ），不确定性极大，信息熵较高（high entropy）。

由以上的香农信息公式可知，信息熵主要有三条性质：
- 单调性 。发生概率越高的事件，其所携带的信息熵越低。比如一个真理的不确定性是极低的，那么它所携带的信息熵就极低。
- 非负性 。信息熵不能为负。单纯从逻辑层面理解，如果得知了某个信息后，却增加了不确定性，这也是不合逻辑的。
- 可加性 。即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。

若两事件A和B同时发生，两个事件相互独立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那么信息熵为 H(A,B) = H(A) + H(B) 。但若两事件不相互独立，那么 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一个随机变量包含另一个随机变量信息量的度量。即已知X的情况下，Y的分布是否会改变。

可以理解为，两个随机变量的互信息度量了两个变量间相互依赖的程度。X 和 Y的互信息可以表示为：
I(X;Y) = H(X) - H(X|Y)
H(X)是X的信息熵，H(X|Y)是已知Y的情况下，X的信息熵。结果的单位是比特。
简单来说，互信息的性质为：
- I(X;Y)>=0 互信息永远不可能为负
- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是对称的
-当X，Y独立的时候， I(X;Y) = 0 互信息值越大，两变量相关性越强。
-当X，Y知道一个就能推断另一个的时候， I(X;Y) = H(Y) = H(X)

在数据科学中，互信息常用于特征筛选。在通信系统中互信息也应用广泛。在一个点到点的通信系统中，发送信号为X，通过信道后，接收端接收到的信号为Y，那么信息通过信道传递的信息量就是互信息 I(X,Y) 。根据这个概念，香农推导出信道容量（即临界通信传输速率的值）。

信息增益（ Information Gain ）是用来按照一定规则划分数据集后，衡量信息熵减少量的指数。

那数据集的信息熵又是怎么计算的呢？比如一个常见的0,1二分类问题，我们可以计算它的熵为：
Entropy = -(p(0) * log(P(0)) + p(1) * log(P(1)))
当该数据集为50/50的数据集时，它的信息熵是最大的（1bit）。而10/90的数据集将会大大减少结果的不确定性，减小数据集的信息熵（约为0.469bit）。

这样来说，信息熵可以用来表示数据集的纯度（ purity ）。信息熵为0就表示该数据集只含有一个类别，纯度最高。而较高的信息熵则代表较为平衡的数据集和较低的纯度。

信息增益是提供了一种可以使用信息熵计算数据集经过一定的规则（比如决策树中的一系列规则）进行数据集分割后信息熵的变化的方法。
IG(S,a) = H(S) - H(S|a)
其中，H(s) 是原数据集S的信息熵（在做任何改变之前），H(S|a)是经过变量a的一定分割规则。所以信息增益描述的是数据集S变换后所节省的比特数。

信息增益可以用做决策树的分枝判断方法。比如最常用CART树（ Classification and Regression Tree ）中的分枝方法，只要在python中设置参数 criterion 为 “entropy” 即可。

信息增益也可以用作建模前的特征筛选。在这种场景下，信息增益和互信息表达的含义相同，会被用来计算两变量之间的独立性。比如scikit-learn 中的函数 mutual_info_classiif()

信息增益在面对类别较少的离散数据时效果较好，但是面对取值较多的特征时效果会有 偏向性 。因为当特征的取值较多时，根据此特征划分得到的子集纯度有更大的可能性会更高(对比与取值较少的特征)，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。举一个极端的例子来说，如果一个特征为身份证号，当把每一个身份证号不同的样本都分到不同的子节点时，熵会变为0，意味着信息增益最大，从而该特征会被算法选择。但这种分法显然没有任何实际意义。

这种时候，信息增益率就起到了很重要的作用。
gR(D,A)=g(D,A)/HA(D)
HA(D) 又叫做特征A的内部信息，HA(D)其实像是一个衡量以特征AA的不同取值将数据集D分类后的不确定性的度量。如果特征A的取值越多，那么不确定性通常会更大，那么HA(D)的值也会越大，而1/HA(D)的值也会越小。这相当于是在信息增益的基础上乘上了一个惩罚系数。即 gR(D,A)=g(D,A)∗惩罚系数 。

在CART算法中，基尼不纯度表示一个随机选中的样本被分错类别的可能性，即这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本均为一种时（没有被分错的样本），基尼不纯度达到最低值0。

举例来说，如果有绿色和蓝色两类数据点，各占一半（蓝色50%，绿色50%）。那么我们随机分类，有以下四种情况：
-分为蓝色，但实际上是绿色（❌），概率25%
-分为蓝色，实际上也是蓝色（✔️），概率25%
-分为绿色，实际上也是绿色（✔️），概率25%
-分为绿色，但实际上是蓝色（❌），概率25%
那么将任意一个数据点分错的概率为25%+25% = 50%。基尼不纯度为0.5。

在特征选择中，我们可以选择加入后使数据不纯度减少最多的特征。

噪音数据简单来说就是会对模型造成误导的数据。分为类别噪声（ class noise 或 label noise ）和 变量噪声（ attribute noise ）。类别噪声指的的是被错误标记的错误数据，比如两个相同的样本具有不同的标签等情况。变量噪声指的是有问题的变量，比如缺失值、异常值和无关值等。

决策树其实是一种图结构，由节点和边构成。
-根节点：只有出边没有入边。包含样本全集，表示一个对样本最初的判断。
-内部节点：一个入边多个出边。表示一个特征或是属性。每个内部节点都是一个判断条件，包含数据集中从根节点到该节点所有满足条件的数据的集合。
-叶节点：一个入边无出边。表示一个类，对应于决策结果。

决策树的生成主要分为三个步骤：
1. 节点的分裂 ：当一个节点不够纯（单一分类占比不够大或者说信息熵较大）时，则选择将这一节点进行分裂。
2. 决策边界的确定 ：选择正确的决策边界（ Decision Boundary ），使分出的节点尽量纯，信息增益（熵减少的值）尽可能大。
3. 重复及停止生长 ：重复1，2步骤，直到纯度为0或树达到最大深度。为避免过拟合，决策树算法一般需要制定树分裂的最大深度。到达这一深度后，即使熵不等于0，树也不会继续进行分裂。

下面以超级知名的鸢尾花数据集举例来说明。
这个数据集含有四个特征：花瓣的长度（ petal length ）、花瓣的宽度( petal width )、花萼的长度( sepal length )和花萼的宽度( sepal width )。预测目标是鸢尾花的种类 iris setosa, iris versicolor 和 iris virginica 。

建立决策树模型的目标是根据特征尽可能正确地将样本划分到三个不同的“阵营”中。

根结点的选择基于全部数据集，使用了贪婪算法：遍历所有的特征，选择可以使信息熵降到最低、基尼不纯度最低的特征。

如上图，根节点的决策边界为' petal width = 0.8cm '。那么这个决策边界是怎么决定的呢？
-遍历所有可能的决策边界（需要注意的是，所有可能的决策边界代表的是该子集中该特征所有的值，不是以固定增幅遍历一个区间内的所有值！那样很没有必要的～）
-计算新建的两个子集的基尼不纯度。
-选择可以使新的子集达到最小基尼不纯度的分割阈值。这个“最小”可以指两个子集的基尼不纯度的和或平均值。

ID3是最早提出的决策树算法。ID3算法的核心是在决策树各个节点上根据 信息增益 来选择进行划分的特征，然后递归地构建决策树。
- 缺点 ：
（1）没有剪枝
（2）只能用于处理离散特征
（3）采用信息增益作为选择最优划分特征的标准，然而信息增益会偏向那些取值较多的特征(例如，如果存在唯一标识属性身份证号，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。)

C4.5 与ID3相似，但对ID3进行了改进：
-引入“悲观剪枝”策略进行后剪枝
-信息增益率作为划分标准
-将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
-可以处理缺失值

对于缺失值的处理可以分为两个子问题：
（1）在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
C4.5 中对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
（2）选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
C4.5 的做法是将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

（1）剪枝策略可以再优化；
（2）C4.5 用的是多叉树，用二叉树效率更高；
（3）C4.5 只能用于分类；
（4）C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
（5）C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

可以用于分类，也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型，计算复杂度更低。

CART 包含的基本过程有 分裂，剪枝和树选择 。
分裂 ：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
剪枝 ：采用“代价复杂度”剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
树选择 ：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

（1）C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
（2）C4.5 只能分类，CART 既可以分类也可以回归；
（3）CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
（4）CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
（5）CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

（1）决策树易于理解和解释，可以可视化分析，容易提取出规则
（2）可以同时处理分类型和数值型数据
（3）可以处理缺失值
（4）运行速度比较快（使用Gini的快于使用信息熵，因为信息熵算法有log）

（1）容易发生过拟合（集成算法如随机森林可以很大程度上减少过拟合）
（2）容易忽略数据集中属性的相互关联；
（3）对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向。

写在后面：这个专辑主要是本小白在机器学习算法学习过程中的一些总结笔记和心得，如有不对之处还请各位大神多多指正！（关于决策树的剪枝还有很多没有搞懂，之后弄明白了会再单独出一篇总结哒）

参考资料链接：
1. https://machinelearningmastery.com/what-is-information-entropy/
2. https://zhuanlan.hu.com/p/29679277
3. https://machinelearningmastery.com/information-gain-and-mutual-information/
4. https://victorzhou.com/blog/gini-impurity/
5. https://sci2s.ugr.es/noisydata
6. https://towardsdatascience.com/understanding-decision-trees-once-and-for-all-2d891b1be579
7. https://blog.csdn.net/weixin_36586536/article/details/80468426
8. https://zhuanlan.hu.com/p/85731206

H. 人工智能是学习什么

1、学习并掌握一些数学知识

高等数学是基础中的基础，一切理工科都需要这个打底，数据挖掘、人工智能、模式识别此类跟数据打交道的又尤其需要多元微积分运算基础。

线性代数很重要，一般来说线性模型是你最先要考虑的模型，加上很可能要处理多维数据，你需要用线性代数来简洁清晰的描述问题，为分析求解奠定基础。

概率论、数理统计、随机过程更是少不了，涉及数据的问题，不确定性几乎是不可避免的，引入随机变量顺理成章，相关理论、方法、模型非常丰富。很多机器学习的算法都是建立在概率论和统计学的基础上的，比如贝叶斯分类器、高斯隐马尔可夫链。

再就是优化理论与算法，除非你的问题是像二元一次方程求根那样有现成的公式，否则你将不得不面对各种看起来无解但是要解的问题，优化将是你的GPS为你指路。

以上这些知识打底，就可以开拔了，针对具体应用再补充相关的知识与理论，比如说一些我觉得有帮助的是数值计算、图论、拓扑，更理论一点的还有实/复分析、测度论，偏工程类一点的还有信号处理、数据结构。

2、掌握经典机器学习理论和算法

如果有时间可以为自己建立一个机器学习的知识图谱，并争取掌握每一个经典的机器学习理论和算法，我简单地总结如下：

1) 回归算法：常见的回归算法包括最小二乘法（OrdinaryLeast Square），逻辑回归（Logistic Regression），逐步式回归（Stepwise Regression），多元自适应回归样条（MultivariateAdaptive Regression Splines）以及本地散点平滑估计（Locally Estimated Scatterplot Smoothing）；

2) 基于实例的算法：常见的算法包括 k-Nearest Neighbor(KNN), 学习矢量量化（Learning Vector Quantization， LVQ），以及自组织映射算法（Self-Organizing Map ， SOM）；

3) 基于正则化方法：常见的算法包括：Ridge Regression， Least Absolute Shrinkage and Selection Operator（LASSO），以及弹性网络（Elastic Net）；

4) 决策树学习：常见的算法包括：分类及回归树（ClassificationAnd Regression Tree， CART）， ID3 (Iterative Dichotomiser 3)， C4.5， Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林（Random Forest）， 多元自适应回归样条（MARS）以及梯度推进机（Gradient Boosting Machine， GBM）；

5) 基于贝叶斯方法：常见算法包括：朴素贝叶斯算法，平均单依赖估计（AveragedOne-Dependence Estimators， AODE），以及Bayesian Belief Network（BBN）；

6) 基于核的算法：常见的算法包括支持向量机（SupportVector Machine， SVM）， 径向基函数（Radial Basis Function ，RBF)， 以及线性判别分析（Linear Discriminate Analysis ，LDA)等；

7) 聚类算法：常见的聚类算法包括 k-Means算法以及期望最大化算法（Expectation Maximization， EM）；

8) 基于关联规则学习：常见算法包括 Apriori算法和Eclat算法等；

9) 人工神经网络：重要的人工神经网络算法包括：感知器神经网络（PerceptronNeural Network）, 反向传递（Back Propagation）， Hopfield网络，自组织映射（Self-OrganizingMap, SOM）。学习矢量量化（Learning Vector Quantization， LVQ）；

10) 深度学习：常见的深度学习算法包括：受限波尔兹曼机（RestrictedBoltzmann Machine， RBN）， Deep Belief Networks（DBN），卷积网络（Convolutional Network）, 堆栈式自动编码器（Stacked Auto-encoders）；

11) 降低维度的算法：常见的算法包括主成份分析（PrincipleComponent Analysis， PCA），偏最小二乘回归（Partial Least Square Regression，PLS）， Sammon映射，多维尺度（Multi-Dimensional Scaling, MDS）, 投影追踪（ProjectionPursuit）等；

12) 集成算法：常见的算法包括：Boosting， Bootstrapped Aggregation（Bagging），AdaBoost，堆叠泛化（Stacked Generalization， Blending），梯度推进机（GradientBoosting Machine, GBM），随机森林（Random Forest）。

3、掌握一种编程工具，比如Python
一方面Python是脚本语言，简便，拿个记事本就能写，写完拿控制台就能跑；另外，Python非常高效，效率比java、r、matlab高。matlab虽然包也多，但是效率是这四个里面最低的。

4、了解行业最新动态和研究成果，比如各大牛的经典论文、博客、读书笔记、微博微信等媒体资讯。

5、买一个GPU，找一个开源框架，自己多动手训练深度神经网络，多动手写写代码，多做一些与人工智能相关的项目。

6、选择自己感兴趣或者工作相关的一个领域深入下去
人工智能有很多方向，比如NLP、语音识别、计算机视觉等等，生命有限，必须得选一个方向深入的钻研下去，这样才能成为人工智能领域的大牛，有所成就。

根据网络给的定义，人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的还能的理论、方法、技术及应用系统的一门新的技术科学。
网络关于人工智能的定义详解中说道：人工智能是计算机的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。
综上，从定义上讲，人工智能是一项技术。

I. 数据分析师—技术面试

数据分析师—技术面试
三月份开始找实习，到现在已经有半年的时间了，在这半年的时间中，该经历的基本上都已经经历，春招实习时候，拿到了7个offer，校招时候，成功的拿下一份心仪的工作，结束了我的秋招旅程。对于面试，技术层面即算法、软件等等，业务层面就是忽悠（毕竟没有做过完整的项目），但是也要有自己的逻辑和思考方式（这方面我也有很大的欠缺），下面将自己的面试经历梳理为技术层面和业务层面，来分享给大家。
技术面试
一、软件

1. R语言的文件读取：csv文件的读取方式（read.csv），txt文件的读取方式（read.table）
2. R语言中一些小函数的作用
①apply函数：1代表调用每一行的函数，0代表调用每一列的函数（注意其用法和Python的区别）
②runif函数：生成均匀分布的随机数
③sample（，return = TRUE）：随机有放回的抽样
3. Python中list列表和元组的最大区别：元组的值不可以改变，但是列表的值是可以改变的。
4.数据库中表的连接方式
①内部连接：inner join
②外部连接：outer join
③左连接：left join
注：对于数据分析，建议大家无论是R，Python，sql都有自己一套流程化的体系，这一体系可以很好的帮助你解决实际中的问题。
二、算法

对于算法（分类，聚类，关联等），更是建议大家有一套流程化的体系，在面试算法的时候，是一个依次递进的过程，不要给自己挖坑，相反，更要将自己的优势发挥的淋漓尽致，把自己会的东西全部释放出来。
下面我将自己的所有面试串联起来，给大家分享一下，仅供参考。
面试官：小张同学，你好，看了你的简历，对相关算法还是略懂一些，下面开始我们的面试，有这么一个场景，在一个样本集中，其中有100个样本属于A，9900个样本属于B，我想用决策树算法来实现对AB样本进行区分，这时会遇到什么问题：
小张：欠拟合现象，因为在这个样本集中，AB样本属于严重失衡状态，在建立决策树算法的过程中，模型会更多的偏倚到B样本的性质，对A样本的性质训练较差，不能很好的反映样本集的特征。
面试官：看你决策树应该掌握的不错，你说一下自己对于决策树算法的理解？
小张：决策树算法，无论是哪种，其目的都是为了让模型的不确定性降低的越快越好，基于其评价指标的不同，主要是ID3算法，C4.5算法和CART算法，其中ID3算法的评价指标是信息增益，C4.5算法的评价指标是信息增益率，CART算法的评价指标是基尼系数。
面试官：信息增益，好的，这里面有一个信息论的概念，你应该知道的吧，叙述一下
小张：香农熵，随机变量不确定性的度量。利用ID3算法，每一次对决策树进行分叉选取属性的时候，我们会选取信息增益最高的属性来作为分裂属性，只有这样，决策树的不纯度才会降低的越快。
面试官：OK，你也知道，在决策树无限分叉的过程中，会出现一种现象，叫过拟合，和上面说过的欠拟合是不一样的，你说一下过拟合出现的原因以及我们用什么方法来防止过拟合的产生？
小张：对训练数据预测效果很好，但是测试数据预测效果较差，则称出现了过拟合现象。对于过拟合现象产生的原因，有以下几个方面，第一：在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）；第二：在建模过程中使用了较多的输出变量，变量较多也容易产生过拟合；第三：样本中有一些噪声数据，噪声数据对决策树的构建的干扰很多，没有对噪声数据进行有效的剔除。对于过拟合现象的预防措施，有以下一些方法，第一：选择合理的参数进行剪枝，可以分为预剪枝后剪枝，我们一般用后剪枝的方法来做；第二：K-folds交叉验证，将训练集分为K份，然后进行K次的交叉验证，每次使用K-1份作为训练样本数据集，另外的一份作为测试集合；第三：减少特征，计算每一个特征和响应变量的相关性，常见的为皮尔逊相关系数，将相关性较小的变量剔除，当然还有一些其他的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等。
面试官：你刚刚前面有提到预剪枝和后剪枝，当然预剪枝就是在决策树生成初期就已经设置了决策树的参数，后剪枝是在决策树完全建立之后再返回去对决策树进行剪枝，你能否说一下剪枝过程中可以参考的某些参数？
小张：剪枝分为预剪枝和后剪枝，参数有很多，在R和Python中都有专门的参数来进行设置，下面我以Python中的参数来进行叙述，max_depth（树的高度），min_samples_split（叶子结点的数目），max_leaf_nodes（最大叶子节点数），min_impurity_split（限制不纯度），当然R语言里面的rpart包也可以很好的处理这个问题。
面试官：对了，你刚刚还说到了用决策树来进行特征的筛选，现在我们就以ID3算法为例，来说一下决策树算法对特征的筛选？
小张：对于离散变量，计算每一个变量的信息增益，选择信息增益最大的属性来作为结点的分裂属性；对于连续变量，首先将变量的值进行升序排列，每对相邻值的中点作为可能的分离点，对于每一个划分，选择具有最小期望信息要求的点作为分裂点，来进行后续的决策数的分裂。
面试官：你刚刚还说到了正则化，确实可以对过拟合现象来进行很好的调整，基于你自己的理解，来说一下正则化？
小张：这一块的知识掌握的不是很好，我简单说一下自己对这一块的了解。以二维情况为例，在L1正则化中，惩罚项是绝对值之和，因此在坐标轴上会出现一个矩形，但是L2正则化的惩罚项是圆形，因此在L1正则化中增大了系数为0的机会，这样具有稀疏解的特性，在L2正则化中，由于系数为0的机率大大减小，因此不具有稀疏解的特性。但是L1没有选到的特性不代表不重要，因此L1和L2正则化要结合起来使用。
面试官：还可以吧！正则化就是在目标函数后面加上了惩罚项，你也可以将后面的惩罚项理解为范数。分类算法有很多，逻辑回归算法也是我们经常用到的算法，刚刚主要讨论的是决策树算法，现在我们简单聊一下不同分类算法之间的区别吧！讨论一下决策树算法和逻辑回归算法之间的区别？
小张：分为以下几个方面：第一，逻辑回归着眼于对整体数据的拟合，在整体结构上优于决策树；但是决策树采用分割的方法，深入到数据内部，对局部结构的分析是优于逻辑回归；第二，逻辑回归对线性问题把握较好，因此我们在建立分类算法的时候也是优先选择逻辑回归算法，决策树对非线性问题的把握较好；第三，从本质来考虑，决策树算法假设每一次决策边界都是和特征相互平行或垂直的，因此会将特征空间划分为矩形，因而决策树会产生复杂的方程式，这样会造成过拟合现象；逻辑回归只是一条平滑的边界曲线，不容易出现过拟合现象。
面试官： 下面呢我们来聊一下模型的评估，算法进行模型评估的过程中，常用的一些指标都有哪些，精度啊？召回率啊？ROC曲线啊？这些指标的具体含义是什么？
小张：精度（precision），精确性的度量，表示标记为正例的元组占实际为正例的比例；召回率（recall），完全性的度量，表示为实际为正例的元组被正确标记的比例；ROC 曲线的横坐标为假阳性，纵坐标为真阳性，值越大，表示分类效果越好。
（to be honest，这个问题第一次我跪了，虽然说是记忆一下肯定没问题，但是当时面试的那个时候大脑是一片空白）
面试官：聚类分析你懂得的吧！在我们一些分析中，它也是我们经常用到的一类算法，下面你介绍一下K-means算法吧！
小张：对于K-means算法，可以分为以下几个步骤：第一，从数据点中随机抽取K个数据点作为初始的聚类中心；第二：计算每个点到这K个中心点的距离，并把每个点分到距离其最近的中心中去；第三：求取各个类的均值，将这些均值作为新的类中心；第四：重复进行步骤二三过程，直至算法结束，算法结束有两种，一种是迭代的次数达到要求，一种是达到了某种精度。
后记
面试的水很深，在数据分析技术面的时候问到的东西当然远远不止这些，因此在我们的脑子里面一定要形成一个完整的体系，无论是对某一门编程语言，还是对数据挖掘算法，在工作中都需要形成你的闭环，在面试中更是需要你形成闭环，如何更完美的包装自己，自己好好总结吧！
附录
R语言数据处理体系：数据简单预处理个人总结
1、数据简单查看
⑴查看数据的维度：dim
⑵查看数据的属性：colnames
⑶查看数据类型：str
注：有一些算法，比如说组合算法，要求分类变量为因子型变量；层次聚类，要求是一个距离矩阵，可以通过str函数进行查看
⑷查看前几行数据：head
注：可以初步观察数据是不是有量纲的差异，会后续的分析做准备
⑸查看因子型变量的占比情况：table/prop.table
注：可以为后续数据抽样做准备，看是否产生类不平衡的问题
2、数据缺失值处理
⑴summary函数进行简单的查看
⑵利用mice和VIM包查看数据缺失值情况，代表性函数： md.pattern、aggr
⑶caret包中的preProcess函数，可以进行缺失值的插补工作，有knn、袋装、中位数方法
⑷missForest包中的missForest函数，可以用随机森林的方法进行插补
⑸可以用回归分析的方法完成缺失值插补工作
⑹如果样本量很多，缺失的数据很少，可以选择直接剔除的方法
3、数据异常值处理
⑴summary函数进行简单的查看，比如：最大值、最小值等
⑵boxplot函数绘制箱线图
4、数据抽样
⑴sample函数进行随机抽样
⑵caret包中的createDataPartition()函数对训练样本和测试样本进行等比例抽样
⑶caret包中的createFold函数根据某一个指标进行等比例抽样
⑷DMwR包中SMOTE函数可以解决处理不平衡分类问题
注：比如决策树算法中，如果样本严重不平衡，那么模型会出现欠拟合现象
5、变量的多重共线性处理
⑴结合业务，先删除那些和分析无关的指标
⑵corrgram包的corrgram函数查看相关系数矩阵
⑶caret包中的findCorrelation函数查看多重共线性
⑷如果相关性太大，可以考虑删除变量；如果变量比较重要，可以考虑主成分/因子分析进行降维处理

J. 向大神求教！python写的决策树的ID3算法怎么一直提示bestfeat=labels[bestfeat_index]超出索引啊！

1、对当前训练集，计算各属性的信息增益（假设有属性A1,A2,…An）；
2、选择信息增益最大的属性Ak（1<=k<=n），作为根节点；
3、把在Ak处取值相同的例子归于同一子集，作为该节点的一个树枝，Ak取几个值就得几个子集；
4、若在某个子集中的所有样本都是属于同一个类型（本位只讨论正(Y)、反(N)两种类型的情况），则给该分支标上类型号作为叶子节点；
5、对于同时含有多种（两种）类型的子集，则递归调用该算法思路来完成树的构造。