2020年的笔记，拿出来记录一下。
Introduction to Data Mining 1
相似性与相异性的度量
Metric 度量
非负性。 $$ d(x,y)\geq 0\quad\mbox{Only when } x = y,~d(x,y) = 0 $$
对称性。 $$ d(x,y) = d(y,x) $$
三角不等式。 $$ d(x,z)\leq d(x,y) + d(y,z) $$
相似度(Similarity)与相异度(Dissimilarity)
| Term | Range | Synonym |
|---|---|---|
| Similarity | [0,1] | |
| Dissimilarity | Usually [0,$\infty$] | Distance |
Distance
Euclidean Distance: $$ d(\textbf{x},\textbf{y}) = \sqrt{\sum_{k = 1}^{n}(x_k – y_k)^2} $$
Minkowski Distance: $$ d(\textbf{x},\textbf{y}) = \left(\sum_{k = 1}^{n}|x_k – y_k|^r\right)^{1/r} $$
Mahalanobis Distance: $$ d(\textbf x,\textbf y) = (\textbf x-\textbf y)\boldsymbol{\Sigma}^{-1}(\textbf x-\textbf y)^T $$
二元数据的相似性度量
一般值为1表明两个对象完全相似。值为0表明对象一点也不相似。
简单匹配系数(Simple Matching Coefficient)
$$ SMC = \frac{\mbox{值匹配的属性个数}}{\mbox{属性个数}} = \frac{f_{11} + f_{00}}{f_{01} + f_{10} + f_{11} + f_{00}} $$
Jaccard 系数(Jaccard Coefficient)
$$ J = \frac{\mbox{匹配的个数}}{\mbox{不涉及0-0匹配的属性个数}} = \frac{f_{11}}{f_{01}+f_{10} + f_{11}} $$
当0-0产品过多的时候，这会导致SMC总体值变化不够显著，因此剔除$f_{00}$。
余弦相似度
$$ \cos(\textbf{x},\textbf y) = \frac{\textbf x\cdot\textbf y}{\|\textbf x\|\|\textbf y\|} $$
Bregman Divergence
Bregman散度是损失或失真函数。$\textbf y$是原来的点，而$\textbf{x}$是它的某个失真或近似。例如$\textbf{x}$可能是添加了一些随机噪声到$\textbf{y}$上产生的。正式定义如下：
Bregman 散度 给定一个严格凸函数$\phi$ ，由该函数生成的Bregman散度$D(\textbf x,\textbf y)$通过以下公式给出： $$ D(\textbf x,\textbf y) = \phi(\textbf x)-\phi(\textbf y) – \left<\nabla\phi(\textbf y),(\textbf x-\textbf y)\right> $$ 其中，$\nabla\phi(\textbf y)$ 是在$\textbf y$上计算的$\phi$ 梯度，$\textbf x – \textbf y$ 与$\textbf x$与$\textbf y$ 的向量差，$\left<\nabla\phi(\textbf y),(\textbf x-\textbf y)\right>$ 是内积。
Kullback-Leibler Divergence
$$ D_{KL}(p||q) = \int_xp(x)\ln\frac{p(x)}{q(x)}\text dx $$
F-divergence
KL-divergence 的坏处在于它是无界的。事实上KL-divergence 属于更广泛的f-divergence中的一种。
常用的F-divergence有 Hellinger distance, Total Variation Distance. $$ D_f(p||q) = \int_xq(x)f\left(\frac{p(x)}{q(x)}\right)\text d x $$ 如果取$f(t) = t\log t$或者$f(t) = -\log t$就能得到KL散度。
分布的相似度用什么模型比较好
Wasserstein distance
入门举例：假设你是一个做木材运输的，你要运送木材从若干个木材生产地到若干个木材需求地，假设每个生产地有固定数量的木材，每个需求地也有固定数量木材的需求，他们的总和（恰好）彼此相等，你要指定一个运输计划，把所有木材从生产地分别运送到需求地，使得供需刚好平衡，也就是每个生产地的木材都刚好运送走了，每个需求地都得到了预期的木材量。你将碰到这样一个问题：假设你事先已经计算好从每个生产地运送木材到每个需求地的单位木材运费，你该怎样合理的指定运输计划使得总开支最小呢？
wiki: Wasserstein metric
只讨论最简单的情况，定义， $$ W_2(p,q) = \sqrt{\min_{P_{XY}} E_{P_{XY}}\left[\|x-y\|^2_2\right]}\quad s.t. P_X\sim p,P_Y\sim q $$ 也就是说对于任意边缘分布为$p$和$q$的联合分布$P_{XY}$，我们可以求出$E_{P_{XY}}\left[\|x-y\|^2_2\right]$，而$p$和$q$的Wasserstein Distance则定义为$P_{XY}$取遍可能的分布时，这个期望的最小值的平方根。
可视化
各种图
散布图
Empirical CDF:
决策树
回归树
Three elements:
- Split process • Choose splitting variables and split points • Goodness of split criterion !(s, t) needed to evaluate any split s of any node t.
- Partition process • Partition the data into two resulting regions and repeat the splitting process on each region • Declare a node is terminal or to continue splitting it; need a stop-splitting rule
- Pruning Process • Collapse some branches back together
考虑我们有$M$个分割区域$R_1,R_2,\ldots,R_M$，对于每个区域的常数$c_m$，我们有： $$ f(x) = \sum_{m=1}^Mc_mI(x\in R_m) $$
对于一次剪枝步骤，不妨设两边左右孩子分别为 $$ R_1(j,s) = \lbrace\textbf X |X_j\leq s\rbrace,\quad\text{and}\quad R_2(j,s) = \lbrace\textbf X |X_j> s\rbrace $$
然后最小化: $$ \min_{j,s}[\phi_{R_1}+\phi_{R_2}] $$ 其中$\phi_{R_m}$是某种对于结点$R_m$的纯度测量。
选择最佳划分的度量
决定树的Size——Terminal points(Leaf points) 的个数。Cardinality
在二叉树中，叶结点的数量是分裂(split)结点+1.
定义$p(i|t)$表示给定结点$t$中属于类$i$的记录所占的比例。在二元问题中，我们任意结点的类分布都可以记作是$(p_0,p_1)$，其中$p_0+p_1 = 1$。
同时我们定义不纯性(大概是Impure)。(0,1)具有零不纯性，(0.5,0.5)具有最高的不纯性。回归中我们可以用RSS来衡量impurity。RSS高说明越不纯，RSS低说明纯。而其他情况(离散)的不纯性的度量我们利用以下方法： $$ \begin{eqnarray} \mbox{Entropy}(t) &=& -\sum_{i=0}^{c-1}p(i|t)\log_2p(i|t)\\ \mbox{Gini}(t) &=& 1-\sum_{i = 0}^{c-1}[p(i|t)]^2\\ \mbox{Classification error}(t) &=& 1-\max_\limits{i}[p(i|t)] \end{eqnarray} $$ 其中$c$是类的个数，并且在计算熵时，$O\log_20 = 0$。
为了确定测试条件的效果，我们需要比较父结点(划分前)的不纯程度和子女结点(划分后)的不纯程度，它们的差越大，测试条件的效果就越好。增益$\Delta$是一种可以用来确定划分效果的标准: $$ \Delta = I(\mbox{parent}) = \sum_{i = 1}^k\frac{N(v_j)}{N}I(v_j) $$ 其中，$I(\cdot)$是给定结点的不纯性度量，$N$是父结点上的记录总数，$k$是属性值的个数，$N(v_j)$是子女结点$v_j$相关联的记录个数。我们的目的就是为了最大化$\Delta$。也就是最小化子女结点的不纯性度量的加权值。
如果我们选择熵(entropy)作为我们的不纯性度量，则熵的差就是信息增益(information gain)$\Delta_{\mbox{info}}$。
一般我们都选择熵或者基尼来作为我们的增益函数。
补充：
对于样本D，个数为|D|，根据特征A的某个值a，把D分成|D1|和|D2|，则在特征A的条件下，样本D的基尼系数表达式为：这也就是多路分支的基尼指数计算方法 $$ Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) $$
我们这里举一个实例来解释计算方法：
工作性质的熵
稳定：8 = 6高+2低
一般：6 = 3高+3低
$$ Entropy(S_{wd}) = -\left(\frac 6 8\right)\log_2\frac 6 8-\left(\frac2 8\right)\log_2\frac 2 8 =0.811 $$
$$ Entropy(S_{yb}) = -\left(\frac 3 6\right)\log_2\frac 3 6-\left(\frac3 6\right)\log_2\frac 3 6 =1 $$
由“稳定”和“一般”的熵可求得的属性“工作性质”的熵为： $$ Entropy(S,\mbox{工作性质}) = \left(\frac 8 {14}\right)Entropy(S_{wd}) + \left(\frac 6{14}\right)Entropy(S_{yb}) = 0.892 $$ 高和低代表的是额度。
算法实现的关键点
Decision_tree.py 提供了离散情况的算法实现
三种常见的算法有C4.5、ID3、CART分类树。
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分类回归 | 二叉树 | 基尼系数 均方差 | 支持 | 支持 | 支持 |
ID3分类树的实践
Iterative Dichotmizer 3(ID3)
总流程：
选择决策树的根节点，选择标准：根据属性的信息增益，确定决策树的根结点 $$ Gain(S,A) = Entropy(S) – Entropy(S,A) $$
节点属性划分
对划分的子集按照上述过程进行反复迭代来获得树的所有内部节点
最后根据节点、内部节点以及叶节点间的关系构建决策树
注意：该过程需要反复迭代，也就是最基础的决策树算法。
C4.5分类树的实践
C4.5并不是一”件“算法而是一”套“算法——C4.5，C4.5-no-pruning和C4.5-rules。我们首先介绍基本的C4.5后面介绍特殊的C4.5。
C4.5一般选取Gain Ratio rather than Gain，用来纠正gain度量倾向于多输出test的方法。
Gain Ratio
From 维基百科：关于gain与gain ratio
可以看到gain与gain ratio的区别在于gain ratio = gain / intrinsic value(内在价值)。多了一个intrinsic value意义在于纠正gain作为test的度量时会出现的一个问题：举一个客户系统的例子，如果要对一个客户信息数据分类，其中有一项属性是每个客户的信用卡号，由于这和每个客户是一一对应的，可想而知，使用该属性的test必然获得最大的gain，因为对此属性分类后，每个子树对应的是唯一的一个样本，这显然不是 我们分类想要的结果，也不具有普适性。而当按照信用卡号做test分类时，intrinsic value同样是极大的，这可以看做是各个类数量分布的熵，这样就有效地抑制了选择信用卡号这样的test作为最佳test。
同时我们给出Gain Ratio的计算方式： $$ GainRatio(a) = \frac{Gain(a)}{Entropy(a)}=\frac{\Delta_{\mbox{info}}}{Split~Info} $$
这种情况下，有可能原先Gain中是最佳分支的属性，最终并不是最佳分支了。
讨论到此，应当指出决策树并不能以这种简单的方式为所有决策边界建模。例如，尽管它能模拟任何二值函数，最终的树可能是相当的复杂。比如在大量二值属性上建模XOR操作。在这种情况下每一条路径中都需要对所有属性做测试，这棵树的尺寸将会呈指数级规模。另一个难题是所谓的”m-of-n“函数，class只与n个属性中的m个有关，但是并不清楚是哪m个属性。倾斜决策树，将在后面介绍，能够克服这些缺陷。除了这些困难，C4.5生成的决策树还有一个问题是由于在属性选择时的贪心选择导致子树的重复。除了穷举搜索最佳属性来生长出一个完全决策树，这个问题通常别无他法。
C4.5对ID3算法的改进:
- 熵的改进,加上了子树的信息. Split_Infox(X)= – SUM( (|T|/|Ti| ) *LOG(|Ti|/|T|)) Gain ratio(X)= Gain(X)/Split_Infox(X)
- 在输入数据上的改进.
- 因素属性的值可以是连续量,C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进行处理,但结论属性的值必须是离散值.
- 训练例的因素属性值可以是不确定的,以 ? 表示,但结论必须是确定的
- 对已生成的决策树进行裁剪,减小生成树的规模
剪枝Tree Pruning
有多重剪枝的算法，
- cost-complexity pruning
- Reduced error pruning
- Pessimistic pruning
剪枝方法：
- pre-pruning. Has some drawbacks: A seemingly worthless split might lead to a very good split below it (short-sighted).
- post-pruning. Preferred approach.
Weakeast Link pruning procedure
- Successively collapse the internal node that produces the smallest per-node increase in $\sum_{m=1}^{|T|}N_mQ_m$ here $Q_m$ is the impurity measure of node $m$.
- Continue until we produce the single-node (root) tree.
We can obtain a finite sequence of sub trees.
For each subtree $T$, we measure its cost complexity by $$ C_\alpha(T) = \sum_{m=1}^{|T|}N_mQ_m+\alpha|T| $$ $|T|$ is Tree size. $\alpha$ governs a trade off between tree size and its goodness of data.
Every interval of some $\alpha$ values correspond to a subtree $T_{size}$.
CART分类树的实践
CART分类树算法每次仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。
基尼系数和熵之半的曲线非常接近，因此，基尼系数可以做为熵模型的一个近似替代。以追求更小的计算量。
算法从根节点开始，用训练集递归建立CART分类树。
(1)、对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，则返回决策子树，当前节点停止递归。
(2)、计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
(3)、计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和C4.5算法里描述的相同。
(4)、在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。
(5)、对左右的子节点递归的调用1-4步，生成决策树。
对生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。
CART分类树算法对连续特征和离散特征的处理
CART分类树算法对连续值的处理，思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。
具体思路：m个样本的连续特征A有m个，从小到大排列a1，a2，……，am，则CART取相邻两样本值的平均数做划分点，一共取m-1个，其中第i个划分点Ti表示为：Ti = (ai + ai+1)/2。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at，则小于at的值为类别1，大于at的值为类别2，这样就做到了连续特征的离散化。
注意的是，与ID3、C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性在后面还可以参与子节点的产生选择过程。
CART分类树算法对离散值的处理，采用的思路：不停的二分离散特征。
在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别A1,A2,A3，我们会在决策树上建立一个三叉点，这样决策树是多叉树。
CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3}，然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开，后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同，在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。