Python

2018-07-13

Explain

Author : Benjamin142857

Content

Basics

math

re
Machine Learning

numpy

pandas

scipy

matplotlib

sklearn
Deep Learning

tensorflow

keras

pytorch

展开全文 >>

Regression Analysis Model

2018-07-10

Regression Analysis Model（Regression Analysis）

Author : Benjamin142857

回归分析（Regression Analysis）：一种统计学上分析数据的方法，目的在于了解两个或多个变数间是否相关、相关方向与强度，并建立数学模型以便观察特定变数来预测研究者感兴趣的变数。

难度评估：:star::star:

回归分析主要算法：

线性回归(Linear Regression)

局部加权线性回归(Locally weighted linear regression)

多项式回归(Polynomial Regression)

逐步回归(Step Regression)

岭回归(Ridge Regression)

套索回归(Lasso Regression)

弹性网回归(ElasticNet)

常用于：回归，预测标签为连续数值的数据

线性回归（Linear Regression, LR）

普通线性回归较为简单，就是用一个线性函数来拟合数据分布，比如对于一个一维的样本，即用 $y = θ_0+θ_1x$ （直线）来拟合数据点分布，对于一个二维样本，即用$z = θ_0+θ_1x + θ_2y$ （平面）来拟合数据点分布，高维的样本 $y = θ_0+θ_1x_1 + θ_2x_2 + …. + θ_nx_n$ 以此类推，但高维的样本无法完全可视化数据点的分布情况，所以较难直观理解。

线性回归虽然简单基础，但其思想很重要！！！

方法：

梯度下降法

最小二乘法

LR-梯度下降法

我们要求得线性回归模型

$h_θ(x) = θ_0+θ_1x_1 + θ_2x_2 + …. + θ_nx_n$

对于每个样本点 $(i)$ 如下，前面的1是为了矩阵相乘方便形成$θ_0$

$x^{(i)}$ = $$\left[\begin{matrix}1& x_1& x_2&\dots & x_n\end{matrix}\right]$$

回归系数

$θ$ = $$\left[\begin{matrix}θ_0& θ_1& θ_2&\dots & θ_n\end{matrix}\right]$$

对于每一个样本，预测值与实际值的差就是

$h_θ(x^{(i)}) - y^{(i)} $

$h_θ(x) = θx^T = θ_0+θ_1x_1 + θ_2x_2 + …. + θ_nx_n$

现在我们就是要求每个样本点 “预测值与实际值的差” 的总和要尽可能的小（设这里为m个样本），那我们就要构造一个以 $θ$ 为自变量的损失函数（注意此时是以 $θ$ 为自变量），设纬度为$n+1$。

其实损失函数就是均方误差MSE，而乘个 $\frac{1}{2}$ 是为了后面的求偏导方便平方的消去。

$J(θ) = \frac{1}{2m}\sum_{i=1}^m(h_θ(x^{(i)}) - y^{(i)})^2$

假设二维下的损失函数长这样

我们随机取一个点 $(θ_0, θ_1, …., θ_n)$作为我们的起点。为什么要随机取？这样说吧，梯度下降的过程就像在一副地图内寻宝，先随机一个初始地方，然后在这个地方附近慢慢寻找宝藏，而要找的宝藏就是藏在最底最深的部分（就是我们要求的最小值）。

对于二维损失函数，假设我们取到了如图的黑点处 $(θ_0, θ_1)$，但显然他对应的损失函数值不是我们最想要的点，我们想要能使损失函数最小的点应该是红色那个，那要如何从我们现在的随机起点（黑点）去到红点的呢？

先补充一下，上述我们说到 “寻宝” 一般只能在初始点附近找，但其实如果仅进行这一次“寻宝” （梯度下降），一般只能找到 “这地图里这一块区域的宝藏” （局部最优解），而未必能那么幸运一下就找到 “地图的最大宝藏” (全局最优解)，因为你不能保证你的是在出生点在哪的，所以我们要进行很多次“寻宝”，“寻宝”的次数越多越有可能找到最终宝藏（全局最优解），因为都把地图挖个遍了，具体区别请看BGD 与 SGD 。
那对于每次梯度下降，我们先需要求得该点的梯度，若对梯度概念不太清楚，请看梯度。对损失函数的每个$θ_j$进行求偏导, 其实就是损失函数降次，消去1/2，并提出对应的$x_j$系数：

$\frac{\partial J}{\partial θj} = \frac{1}{m}\sum{i=1}^m(h_θ(x^{(i)})-y^{(i)})x_j^{(i)}$

现在求出的梯度是个向量！是个向量！是个向量！对于我们例子中的二维样本，其梯度就是一个二维向量（$\frac{\partial J}{\partial θ_0} $, $\frac{\partial J}{\partial θ_1} $），大概直观的感觉就是如图的箭头（emmm画功不好，但其实它是平行于xoy平面的，自行脑补一下），从黑点指向此点坡度最大的方向。

梯度下降就是我们逆着这个梯度，就是沿梯度的反方向走，所以我们要对整组回归系数进行更新，就是要用对应的上一个回归系数减去对应梯度的量，其实就是减它的偏导，更新公式如下。

$θ{j(new)} = θ{j(old)} - α · \frac{\partial J}{\partial θ_j}$

式子中的 $α$ 是指“学习率”，大致的意思是限制一下你往梯度反方向走的步距。我们都知道用求偏导求出来的梯度是个长短不一的向量，其实我们只需要它的方向，它的长度是不定的。所以我们给这个方向梯度向量乘上一个$α$，其实就相当于改变这个向量的长度，而方向是不变的。

从图中可看出，如果这个梯度过大，很可能会直接越过那个“凹槽”，跳到对岸，然后下一步又是这样，就会在那里跳来跳去，半天都不下降一点。

所以一般学习率 $α$ 会很低从而让它慢慢慢慢往下走，但如果太低的话，计算量又会非常大，因为迭代很久都没有下降一点

对于例子中的回归系数，更新如下

$θ0$方向: $θ{0(new)} = θ_{0(old)} - α · \frac{\partial J}{\partial θ_0}$

$θ1$方向: $θ{1(new)} = θ_{1(old)} - α · \frac{\partial J}{\partial θ_1}$

假如更新了一次后，我们新的点($θ{0}$, $θ{1}$)从黑色点走到了粉色的点，再更新一次，从粉色的点走到了黄色，然后一直这样迭代下去，最终会里凹槽的最低点越来越近，也就是我们想要的损失函数最优解（局部最优或全局最优）的回归系数($θ{0}$, $θ{1}$)
那迭代应该什么时候结束呢？一般有三个参照，任选其一即可：
1. 迭代直到 $θ_j$ 的变化幅度不大
2. 迭代直到 $ \frac{\partial J}{\partial θ_j} $足够小
3. 迭代次数足够多

用最终求得的那组回归系数$θ$ = $$\left[\begin{matrix}θ_0& θ_1& θ_2&\dots & θn\end{matrix}\right]$$，就能构建我们想要的线性回归模型$hθ(x) = θ_0+θ_1x_1 + θ_2x_2 + …. + θ_nx_n$，代入数据点就可以进行回归预测了。

附python代码实现梯度下降线性回归

LR-最小二乘法

1
2
。。。。。

LR-梯度下降 VS 最小二乘

局部加权线性回归（Locallly Weights Linear Regression, LWLR）

普通线性回归较为简单，就是用一个线性函数来拟合数据分布，比如对于一个一维的样本，即用 $y = θ_0+θ_1x$ （直线）来拟合数据点分布，对于一个二维样本，即用$z = θ_0+θ_1x + θ_2y$ （平面）来拟合数据点分布，高维的样本 $y = θ_0+θ_1x_1 + θ_2x_2 + …. + θ_nx_n$ 以此类推，但高维的样本无法完全可视化数据点的分布情况，所以较难直观理解。

方法：

梯度下降法

最小二乘法

展开全文 >>

Information Theory Note

2018-07-10

Information Theory Note

Author : Benjamin142857

C.Shannon 在早期为研究信道通信提出了信息论，现代世界的发展很大贡献都源自信息论。

Content

Entropy

Information Gain

Information Gain Ratio

Entropy - 熵

1948 年，香农提出了信息熵的概念，才解决了对信息的量化度量问题。

一条信息的信息量大小和它的不确定性有直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，我们不需要太多的信息就能把它搞清楚。所以，从这个角度，我们可以认为，信息量的度量就等于不确定性的多少。

香农熵的定义是一种比较Heuristic的思想。

我们最开始是先来研究怎么区分信息间信息量大小。

假如我们用H来代表信息量的大小，那信息量的大小H和什么有关？举了例子：我们联想这样一个问题：

一个同学接到了一个电话，是他妈打过来的，和他说天气转冷，记得穿秋裤。（然后问这个同学，电话包含的信息量是多少？显然现在比较难准确回答）

然后这个同学又接到一个电话，是他导师打过来的，和他说他的论文被一所国外的知名大学选中了，现在获得了出国留学的名额（很明显，现在这个电话和第一个电话相比，信息量就感觉大很多）

由上述可知，第一通电话的概率很大，因为妈妈会经常打来电话给予关心，是比较规律性的行为，会让人觉得很平常，信息量较少。而第二通电话的概率一般是很小的，总会让人很意外，觉得突如其来的信息量很大，需要消化一下。

所以信息量的大小H就此和概率P有了联系，那我们就是要找一个函数来构建 H 与 P 的关系 H(P)，它们需满足以下规则：

概率越大的事件所带来的信息量越小，所以H与P是成反比关系。

信息之间可以说是独立的，所以满足可加性。比如包含两个信息信息量的$H(P_1, P_2)$ 要等价于两个包含一个信息的信息量的叠加。即$H(P_1, P_2) = H(P_1) + H(P_2)$

信息量大小是非负的，$H(P) ≥ 0$

综上规则，香农就把H(p)定义为以下关系：

$H(P) = -log_2(P)$

这个关系同时能满足：

因为加了负号，H与P成反比关系

符合叠加，对于对数函数，$H(P_1P_2) = H(P_1) + H(P_2)$

$P∈[0, 1], H ∈ [0, +∞]$

那现在定义了 信息量大小H 与 信息概率P 之间的关系$H = -log_2(P)$后，我们要研究一个含有多个信息 的 信息系统 的 信息混乱程度，那我们只需就求这个信息系统的期望值即可，即HP

$E(H) = P_1H_1 + P_2H_2 + … +P_nH_n = \sum{(PH)} = \sum{(P · -log_2P)}$

这就是著名的香农熵Entropy:

$Entropy = -\sum_{i=1}^n[P(x_i)·log_2P(x_i)]$

附：Decision Tree 番外篇（一）- Entropy 与 IG 在DT中的意义Decision Tree 番外篇(一).md)

Information Gain - 信息增益

在概率论和信息论中，信息增益是非对称的，用以度量两种概率分布P和Q的差异。信息增益描述了当使用Q进行编码时，再使用P进行编码的差异。通常P代表样本或观察值的分布，也有可能是精确计算的理论分布。Q代表一种理论，模型，描述或者对P的近似。

展开全文 >>

Decision Tree 番外篇(一) - Entropy 与 IG 在DT中的意义

2018-07-10

Decision Tree 番外篇(一) - Entropy 与 IG 在DT中的意义

Author : Benjamin142857

我们都知道在决策树ID3算法中选择特征之间的根节点顺序是用计算 $IG$ ，选取 $IG$ 值最大的特征作为根节点。但可能比较多的人都不知道为何要 $IG$ 最大值， $IG$ 最大值的意义是什么，而单个特征的 $IG$ 其实就是$Entropy_{总} - Entropy_{本特征}$ ，所以本质还是探讨 $Entropu$ 的意义，本文就在此比较通俗地简述一下 $Entropy$ 和 $IG$ 在DT中的意义。

Content:

单个特征的 $Entropy$

单个特征的 $IG$

单个特征的 $Entropy$

熵计算公式： $H_{x} = -\sum_{i=1}^{(x的划分区域数)}\sum_{j=1}^{(y的总标签类数)}[P_i(x_j)·log_2P_i(x_j)]$

公式解释：

$x的划分区域数$：就是这个特征是怎么划分的，如这个特征$x$是性别，则我们的划分就是(男，女)，划分区域数就是2。如这个特征$x$是星期几，则我们的划分就是(周一，周二，…，周日)，则$x的划分区域数$就是7

$y的总标签类数$：就是这组样本中的所有标签一共有几类，比如我们要做的是新闻热度的分类，要分为(冷，一般，热)，这里的标签类数就是3。如要做垃圾邮件分类，分为（垃圾，非垃圾），这里就是2.

$P_j(x_i)$: 就是在$x$特征的 $i$ 区域下，样本点的标签是 $j$ 的概率

若对熵公式的来源不太理解，请阅读最下方的附录 “Information Theory Note”

熵是用来度量信息混乱程度的（因为熵是信息量大小期望值），所以一般来讲信息的熵是越小越好，代表信息混乱程度低，信息比较 “整齐”。

对于决策树中特征的熵值计算也是，该特征值熵越小，说明该该特征的 “单个特征分类能力” 最好。

什么意思？就是当我们排去其他特征，只看这个特征 $x_i$ 与标签 $y$ 的关系时，特征 $x_i$ 最有代表性，分出来的 $y$ 错误率最低，类别越整齐，有序，清晰。

举个栗子:chestnut:

现在有这样一组数据，分别是一个人连续9天根据两个特征，打不打球（室外）的情况：

$x_1$ - 下雨？	$x_2$ - 天气热?	$y$ - 打不打球？
下雨	热	×
下雨	不热	√
下雨	不热	×
下雨	不热	×
不下	不热	√
不下	热	√
下雨	热	×
下雨	不热	×
不下	热	√

如果以两个特征划分，样本点的分布如下：
若只以特征 $x_1$ - “下不下雨” 进行划分：

我们来计算一下 $x_1$ 的熵：

$H_{x1} = [(-\frac{4}{5}log\frac{4}{5}) + (-\frac{1}{5}log\frac{1}{5})] + [(-\frac{3}{4}log\frac{3}{4}) + (-\frac{1}{4}log\frac{1}{4})]$

     *[下雨红点      +    下雨绿点 ] + [ 不下雨绿点 +  不下雨红点  ]*

= 1.5332

若只以特征 $x_2$ - “热不热” 进行划分：

我们来计算一下 $x_2$ 的熵：

$H_{x2} = [(-\frac{1}{2}log\frac{1}{2}) + (-\frac{1}{2}log\frac{1}{2})] + [(-\frac{3}{5}log\frac{3}{5}) + (-\frac{2}{5}log\frac{2}{5})]$

[热红点 + 热绿点 ] + [ 不热红点 + 不热绿点 ]

= 1.9709

$H_{x1} < H_{x2}$，$x_1$的熵更小，所以 $x_1$的特征更具代表性，更能把种类分整齐。其实从日常经验和图我们都能很直观感受到，“下不下雨” 这一特征更能决定 “去不去打球” 。决策树中选根节点的原理也类似如此。

此外，Entropy对于连续数值型特征的分箱，多离散型数值特征的剪枝也有很重要的意义，具体请看Decision Tree番外篇（二）- 连续数值的分箱与剪枝

单个特征的 $IG$

信息增益计算公式：

好了，如果能明白上面 “单个特征的 $Entropy$” ，接下来单个特征的 $IG$ 就容易理解多了。我们都知道选特征是选它的 $IG$ 最大值，而上文说 “单个特征分类能力最好” 的特征是熵最小。那根据 $IG$ 计算公式：

$IG= Entropy_{总} - Entropy_{特征} $

可知二者是等价的，$Entropy_总$都是一样的，所以算 $IG$ 最大，本质就是算 $Entropy_{特征}$ 最小。那就行了，讲完~~

接下来循例举个DT中信息增益的栗子:chestnut:

还是这个例子：

在保留所有特征的情况下，我们把样本点分成四块，每一块都算它的熵即可

$H_总 = [(-1log1)] + [(-\frac{1}{3}log\frac{1}{3}) + (-\frac{2}{3}log\frac{2}{3})] + [(-\frac{1}{4}log\frac{1}{4}) + (-\frac{3}{4}log\frac{3}{4})] + [(-1log1)]$

左上方块右上方块左下方块右下方块

$=1.7295$

$IG_{x1} = H_总 - H_{x1} = 1.7295 - 1.5332 = 0.1963$

$IG_{x2} = H_总 - H_{x2} = 1.7295 - 1.9709 = -0.2414$

选出$IG$最大的~~

附录：

Information Theory NoteInformation Theory .md)

(-)Decision Tree番外篇（二）- 连续数值的分箱与剪枝

展开全文 >>

Decision Tree

2018-07-10

Decision Tree

Author : Benjamin142857

决策树（Decision Tree）：一种统计学上分析数据的方法，目的在于了解两个或多个变数间是否相关、相关方向与强度，并建立数学模型以便观察特定变数来预测研究者感兴趣的变数。

难度评估：⭐️⭐️:star:

决策树主要算法：

迭代二叉树 - 3代 (ID3)

C4.5 和 C5.0

分类与回归树 (CART)

卡方自动交互检测 (CHAID)

快速无偏有效统计树 (QUEST)

常用于：分类

阅读前建议先看：Information Theory NoteInformation Theory .md)

ID3 (Iterative Dichotomiser 3) - 迭代二叉树三代

ID3：ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法,即Iterative Dichotomiser3，迭代二叉树三代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法。

核心思想：以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。

目录：

奥卡姆剃刀

信息增益

算法过程

Occam’s razor - 奥卡姆剃刀

奥卡姆剃刀是机器学习里的一个重要哲学，核心思想就是 “化繁为简” ，对在模型学习时遇到的under-fitting与overfitting现象有重要意义。在决策树ID3算法中，基础就是上面提到的奥卡姆剃刀原理，因为决策树很容易过拟合，所以往往越是小型的树，就越优于大型的树，就有了ID3中的 “D” - Dichotomiser(叉状二分法)的概念，就是每个结点尽可能的取两个分支。

Occam’s Razor 的更详细内容请看”Machine Learing 番外篇 (一) - 机器学习的哲学 - 机器学习的哲学.md)”

Information Gain - 信息增益

$IG$ 计算公式：$IG_{特征} = Entropy_{总} - Entropy_{特征}$

$= -\sum_{k=1}^n\sum_{q=1}^{y_{typenum}}[P_k(x_q)·log_2P_k(x_q)] -\sum_{i=1}^{x_{typenum}}\sum_{j=1}^{y_{typenum}}[P_i(x_j)·log_2P_i(x_j)]$

公式说明：

$n$ : 所有样本的总类数

$ x_{typenum}$ : 此特征的（分箱/区域）数

$y_{typenum}$: 对应所属区域的标签类数

计算信息增益的作用：为了确定哪个特征作为相应节点，计算其信息增益可以知道该特征的重要程度（该特征单独作用对分类的影响大小），信息增益越大的特征，越重要，所以选最大的作为节点。

信息增益在DT的更详细内容请看 “Decision Tree 番外篇（一）- Entropy 与 IG 在DT中的意义 - Entropy&GI在DT中的意义.md)”

ID3算法过程

如果了解了信息增益的计算，那么ID3的算法过程就很简单。

我们的第一个根节点就是选所有特征中的 $IG_{max}$ 特征。然后延这个根节点分出2~3个支（根据奥卡姆剃刀，这里的根不要太支，就是在计算特征间IG之前，要对特征内区域的划分（即连续数值型特征的分箱，多离散型数值特征的剪枝）选出最优划分法，剪枝更详细

C4.5 和C5.0 （Classification 4.5&5.0）

待补

CART (Classification & Regression Tree) - 分类与回归树

待补

CHAID (CHi-squared Automatic Interaction Detector) - 卡方自动检验

待补

QUEST (Quick Unbiased Efficient Statistical Tree ) - 快速无偏有效统计树

待补

Entrory
ID3
IG
set DT
Discretization
1. Multi-way split
2. Binary split
Gini Index
1. CART
2. Gini split
Misclassification Error

附录：

Decision Tree 番外篇（一）- Entropy 与 IG 在DT中的意义 - Entropy&GI在DT中的意义.md)

(-)Decision Tree番外篇（二）- 连续数值的分箱与剪枝

Machine Learing 番外篇 (一) - 机器学习的哲学 - 机器学习的哲学.md)

(-)Python代码实现决策树

(-)Matplotlib画树图