目录
本文仅记录自身学习，本着知识分享的目的，放出来供大家参考交流，故请勿转载。文中若有错误，望不吝赐教。
决策树是基于树形结构来进行决策，通过给定训练数据集学得一个模型，用以对新示例进行分类。决策过程中提出的每个 判定问题 都是对某个属性的验证，每个验证的结果或者导出最终结论，或者导出进一步的判定问题。一般的，一棵决策树包含一个根节点，若干个内部节点和若干个叶节点；
决策树学习的关键在于如何选择最优划分属性，一般而言，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的 purity 越来越高。 那么该如何定量的刻画这个“纯度”呢？
我将首先介绍信源，简要列出信源的统计特性和数学模型，以及离散信源的信息测度-熵 及其性质。
信源是信息的来源，是产生消息或消息序列的源泉，信息是抽象的，而消息是具体的，他不是信息本身，却携带者信息。
假设我们仍一颗质地均匀的骰子，研究其落下后朝上一面的点数，每次实验结果必定是\(一点，二点\dots六点\)中的某一面朝上。
这种信源输出的消息是:
\[
\cdots\\alpha_i=\{朝上的面是\ i\ 点\}\ i=1,\cdots,6\\\cdots
\]
这六个不同的消息构成两两互不相容的基本事件集合，样本空间为符号集\(A=\{\alpha_1,\cdots,\alpha_6\}\)由大量实验表明，个消息都是等概率出现的为\(\frac{1}{6}\),因此，可以用一个离散型随机变量\(X\)，而\(X\)的概率分布就是个消息出现的先验概率，来描述这个信源输出的消息:
\[
\left[\begin{matrix}
X\ P(x)
\end{matrix}\right]=
\left[\begin{matrix}
\alpha_1 & \alpha_2&\alpha_3&\alpha_4&\alpha_5&\alpha_6\ \frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&\frac{1}{6}&
\end{matrix}\right]\\且满足，\sum_{i=1}^6P(\alpha_i)=1
\]
上式表明信源的概率空间必定是一个完备集。由上式可推广出最基本的离散信源模型如下：
\[
\left[\begin{matrix}
X\ P(x)
\end{matrix}\right]=
\left[\begin{matrix}
\alpha_1 & \alpha_2&\cdots&\alpha_q\ P(\alpha_1)&P(\alpha_2)&\cdots&P(\alpha_q)&
\end{matrix}\right]\\且满足，\sum_{i=1}^qP(\alpha_i)=1
\]
如果信源给定，其相应的概率空间也就给定，反之若概率空间给定，则相应信源相当于给定，所以概率空间能表征离散信源的统计特性，因此有时也把概率空间称为信源空间
同理可以定义连续信源空间
\[
\left[\begin{matrix}
X\ p(x)
\end{matrix}\right]=
\left[\begin{matrix}
(a,b)\ p(x)
\end{matrix}\right]\\且满足，\int_{a}^bp(x)=1
\]
平稳信源又分为无记忆信源和有记忆信源，在某些简单的离散平稳信源情况下，信源先后发出的一个个符号彼此是统计独立的，则\(N\)维随机矢量的联合概率分布满足：
\[
\begin{align*}
P(X)&=P(X_1\ X_2\cdots X_N)\&=P_1(X_1)P_2(X_2)\cdots P_N(X_N)\\&=\prod_{i=1}^NP(X_i)\\end{align*}
\]
即当不同时刻的离散随机变量又取自同一个符号集
\[
A：\{a_1,a_2,\cdots ,a_q\}，则有\P(x=\alpha_i)=\prod_{i_k=1}^qP(a_{i_k}),\alpha_i=(a_{i_1}\cdots a_{i_k})
\]
是N维随机矢量的一个取值.
由符号集\(A：\{a_1,a_2,\cdots ,a_q\}\)与概率测度\(\leq P(a_{i_k}\leq1(i_k=1,\cdots ,q)\)构成一个概率空间
\[ \left[\begin{matrix} X\ P(x) \end{matrix}\right]= \left[\begin{matrix} a_1 & a_2&\cdots&a_q\ P(\alpha_1)&P(\alpha_2)&\cdots&P(\alpha_q)& \end{matrix}\right]\\且满足，\sum_{i=1}^qP(a_i)=1 \]
我们称由信源空间\([X,P(x)]\)描述的信源\(X\)为 离散无记忆信源 。这种信源在不同时刻发出的符号之间是无依赖的，彼此统计独立的。我们把此信源X 所输出的随机矢量\(X\)所描述的信源称为 离散无记忆信源\(X\)的N次扩展信源。离散无记忆信源的N此扩展信源的数学模型是X信源空间的N重空间
\[
\left[\begin{matrix}
X^N\ P(\alpha_i)
\end{matrix}\right]=
\left[\begin{matrix}
\alpha_1 & \alpha_2&\cdots&\alpha_{q^N}\ P(\alpha_1)&P(\alpha_2)&\cdots&P(\alpha_{q^N})&
\end{matrix}\right]
\]
其中，\(\alpha_i=(a_{i_1}\cdots a_{i_k})\ \ \ \ (i_1,i_2,\cdots ,i_N=1,2,\cdots ,q)\)并满足\(0\leq P(\alpha_i) \leq 1\)且
\[
P(\alpha_i)=P(a_{i_1}a_{i_2}\cdots a_{i_N})=\prod_{i_k=1}^qP(a_{i_k})\\sum_{i=1}^{q^N}P(\alpha_i)=\sum_{i=1}^{q^N}\prod_{i_k=1}^qP(a_{i_k})=1
\]
原文：https://www.cnblogs.com/rrrrraulista/p/12240414.html