线性/树型分类器的纯理论分析

纯理论分析

---

Preface

​ 周志华老师的《机器学习》看到了第五章，可总感觉看得太快了（可惜起步太晚了，大三下才系统地学ML）。个人认为走马观花地看完全没有用处，最好是能自己将所有碰到的轮子都写一遍（理想情况），但人的精力毕竟有限，开学了时间也比较紧张，实现这一步就先跳过吧，而细致的理论分析与理解是完全必要的。LDA之前实现过Github Algorithm-Plus🔗，决策树倒是连理论都没怎么细看，只调过库。为了不当调库侠，有写轮子的能力，个人将对这两章进行一下梳理，写一下自己的理解。

Figure 1. 西瓜

​ LDA（消歧义：Linear Discriminant Analysis，不是Latent Dirichlet Allocation）和决策树都是两个非常简单但是又很优雅的分类器。

---

LDA的数学推导

​

同类样本的类内方差最小，而不同类样本的类间方差最大

​ LDA是给定标签下的有监督降维方式，希望找到更低维度上的投影，可以满足上述属性。而对于高维而言，协方差是描述样本关系的指标。协方差的定义如下（大二下学的，回忆一下）：描述n维随机变量$X=(X_1,X_2,...X_n)$每个分量之间存在的关系，协方差可以定义为： $$\begin{array}{}\text{(1)}& C=\left(\begin{array}{cccc}{c}_{11}& c_{12}& ...& c_{1n}\\ c_{11}& c_{12}& ...& c_{1n}\\ ⋮& ⋮& \ddots & ⋮\\ c_{n1}& c_{n2}& ...& c_{nn}\end{array}\right)\end{array}$$ ​ 其中，$c_{ij}$是两个分量$X_i,X_j$的协方差$Cov(X_i,X_j)=E[(X_i-E_i)(X_j-E_j)]$。协方差存在一些性质，比如说： $$\begin{gathered} \begin{array}{}\text{(2)}& \text{let }Cov(X)=\mathrm{\Sigma } \\ Cov(AX+b)=A\mathrm{\Sigma }{A}^T\end{array} \end{gathered}$$ ​ 证明就省略了，根据期望的性质，推导还是比较简单的。

二分类

​ 假设有两类样本，$D_1$以及$D_2$，$D_1$的样本中心（根据矩法可以求出来）为${\mu }_1$，对应地$D_2$有${\mu }_2$，那么假设存在一个低维过原点的超平面（由于是平行投影，是否过原点不影响结果，但原点较好讨论），这个超平面方程为：$w^{T}x=0$，那么投影在这个超平面上的数据点应该有什么形式？中心点应该有什么形式？协方差是否改变？$w^{T}x=0$确实是降了1维（因为有一个约束方程），但如何使用$w$进行投影？

​ 实际上，每个样本点$x_i$都在：$w^{T}x+b_i=0$ 这个超平面上，去掉这个相对原点的偏移，就可以得到每一个样本点在低维上的投影。实际是这样操作的：设$x_i$是超平面$w^{T}x=0$外一点，那么显然，$x_i$可以表示为超平面上的投影点$x_i^{\prime }$与法向量$w$的加权组合（因为已经构成基了），比如： $$\begin{array}{}\text{(3)}& x_i=x_i^{\prime }+{\lambda }_{i}w\end{array}$$ ​ 那么${\lambda }_i$显然就是$x_i$在单位法向量$w_e$上的投影，那么可以知道： $$\begin{array}{}\text{(4)}& x_i^{\prime }=x_i-\frac{w^T{x}_{i}w}{\Vert w{\Vert }^2}\end{array}$$ ​ 但这是个什么呢？样本中心间的距离又是什么？可以求出样本中心应该在： $$\begin{array}{}\text{(5)}& x_c^{\prime }=\frac{1}{N}\sum _{i=1}^N(x_i-\frac{w^T{x}_{i}w}{\Vert w{\Vert }^2})\end{array}$$ ​ 显然公式$\text{(5)}$是可以进行化简的，对于内积部分（后半部分），需要将内积展开为累加，进行累加次序交换： $$\begin{array}{}\text{(6)}& \begin{array}{l}\frac{1}{N}\sum _{i=1}^N\frac{w^T{x}_{i}w}{\Vert w{\Vert }^2}=\frac{1}{N\Vert w{\Vert }^2}\sum _{i=1}^N\left(\sum _{j=1}^n{w}_j{x}_{ij}\right)w\\ =\frac{1}{\Vert w{\Vert }^2}\sum _{j=1}^n\frac{1}{n}\sum _{i=1}^N{w}_j{x}_{ij}w\\ =\frac{w}{\Vert w{\Vert }^2}\sum _{j=1}^n{w}_j{\mu }_i=\frac{w^T\mu w}{\Vert w{\Vert }^2}\end{array}\end{array}$$ ​ 前半部分的化简十分简单。那么投影后的两个集合中心的差向量应该是： $$\begin{array}{}\text{(7)}& dd={\mu }_1-{\mu }_2-\frac{w^T({\mu }_1-{\mu }_2)w}{\Vert w{\Vert }^2}\end{array}$$ ​ 实际上，Fisher的处理方法与我的处理方法完全不同，我是真的求了一个这样的投影，但不管是Fisher还是西瓜书上的推导，均值全部都是：$w^T\mu$，这让我觉得很奇怪，如果是这样的话，均值的维度不就是1了吗？但实际上维度只应该减1啊？以上都是我看了第一部分产生的想法，但实际上二分类LDA并不是投影到n-1维空间中（特征分量数为n），二分类的LDA直接投影到一维空间上。二分类只需要在一条直线上找到数据的投影即可，在这条直线上判定投影后的新数据离哪一类数据中心最近。

​ 由于这是一下从n维降到1维，所以几何直观上并不好理解。个人觉得这样的降维跨度太大了。

为什么要投影到一条直线上？

​ 由于二分类输出的指示结果为 $p_1,p_2,\text{ where }{p}_1+p_2=1$，也就是说分为两个类，落在两个类内的概率满足一个归一约束，那么输出就相当是在一条直线上。也就是说，LDA认为：输出在不同类上的概率实际上是所有输入特征经过$w$映射的线性组合，二分类问题只需要得到直线上的一个值，就能根据归一约束求出分属于两个类的概率。那么：

• 三分类问题只需要求得在二维空间上的一个点，就能求出一个样本分属于三个类的概率。也即线性组合输出了一个二维的点
• 四分类问题只需求出三维空间中的一个点，就能求出一个样本分属于四个类的概率...
• M分类问题只需要求出M-1为空间中的一个点，就能求出一个样本分属于M个类的概率。

​ 要注意特征空间（n维）和概率空间（M维）的不同。LDA实际上就是在正态分布以及同方差的假设下，认为只要线性组合n个特征，就能求出M维空间中的一个概率解。这也就解释了，为什么我一开始的理解是有问题的。问题的关键就在于：输出分类的概率是输入特征的线性组合。不能简单地想着投影，而要想为什么要这样投影，这样投影如何帮助求得分类概率。

​ 那么数学上就比较好理解了：给定一条直线$y=w^{T}x$，说是要投影到直线上，实际上要做的是根据$w$对样本的不同属性进行线性组合：$w^{T}x$。那么也就有： $$\begin{array}{}\text{(center of projected class 1)}& & {\mu }_1^{\prime }=w^T{\mu }_1\text{(center of projected class 2)}& & {\mu }_2^{\prime }=w^T{\mu }_2\text{(projected within-class cov 1)}& & {\sigma }_1=w^T{\mathrm{\Sigma }}_{1}w\text{(projected within-class cov 2)}& & {\sigma }_2=w^T{\mathrm{\Sigma }}_{2}w\end{array}$$ ​ 那么根据类内方差最小，类间方差最大的思想： $$\begin{array}{}\text{(8)}& \text{max }\frac{\Vert w^T{\mu }_1-w^T{\mu }_2{\Vert }^2}{w^T({\mathrm{\Sigma }}_1+{\mathrm{\Sigma }}_2)w}\end{array}$$ ​ 分子展开维转置乘积之后，可以定义两个散度矩阵： $$\begin{array}{}\text{(within-class scattermatrix)}& & S_b=({\mu }_1-{\mu }_2)({\mu }_1-{\mu }_2{)}^T& \text{(between scatter matrix)}& & S_w={\mathrm{\Sigma }}_1+{\mathrm{\Sigma }}_2& \end{array}$$ ​ 使用这两个散度矩阵，定义问题$\text{(8)}$带有广义瑞利商的形式。解问题$\text{(8)}$就可以得到最优的$w$。由于$w$的长度是不影响结果的（看的就是方向），不妨令分母为1，最大化分子，进一步化简为： $$\begin{array}{}\text{(9)}& \begin{array}{l}\text{min }-w^T{S}_{b}w\\ \text{s.t. }{w}^T{S}_{w}w=1\end{array}\end{array}$$ ​ 请Lagrange坐到主席台上来。根据增加了一项乘子项的优化问题$\text{(9)}$，KKT条件梯度为0，得到： $$\begin{array}{}\text{(10)}& S_{b}w=\lambda S_{w}w\to ({\mu }_1-{\mu }_2)=S_{w}w\end{array}$$ ​ 等式$\text{(10)}$可以化简得原因是：$S_b=({\mu }_1-{\mu }_2)({\mu }_1-{\mu }_2{)}^T$，也就是说，$S_{b}w$实际方向就是${\mu }_1-{\mu }_2$，根据$w$尺度任意性，直接令$S_{b}w=\lambda ({\mu }_1-{\mu }_2)$省事。根据$\text{(10)}$，进行SVD分解（数值上会比较稳定）就可以得到$w$

多分类

​ 从上述理解中已经可以知道LDA的“降维分类”方式，实际上是通过原特征的线性组合，将特征空间直接变换到“概率空间”（或者是可以被变换为概率的空间）。当分类数量为M时，只需要知道M-1个类上的概率或者等价概率值就可以求出所有类上的“概率输出”值。

​ 也就是说：LDA的降维过程实际上是由n维特征空间变换为M-1维分类空间的过程。回顾二分类的情况，M = 2，也就是将所有样本投影到一维（直线）上：$y=w^{T}x$，直线上的值显然是一维的。这是由于参与线性组合的函数实际上是一个标量值函数（$w^{T}x$映射），要想输出高维的向量，只需要更改$w$为一个矩阵$W$即可。对于需要优化得到的结果，推导有些不同： $$\begin{array}{}\text{(11)}& S_t=\sum _{i=1}^m(x_i-{\mu }_t)(x_i-{\mu }_t{)}^T\end{array}$$ ​ 定义公式$\text{(11)}$为全局散度，也就是每个样本点到所有样本的平均点的散度和。个人认为，由于类间差异在大多数情况下都会大于类内差异，所以$S_t$相当于就是一个类间方差的表征（不同类的均值点到整体均值点的散度）。由于不同于二分类问题，类内散度需要重新定义了。显然类内的散度可以用类内样本与本类均值的差异来衡量： $$\begin{array}{}\text{(12)}& S_w=\sum _{j=1}^N(x_{ij}-{\mu }_i)(x_{ij}-{\mu }_i{)}^T\end{array}$$ ​ 但是至于为什么西瓜书上要使用$\text{(12)}-\text{(11)}$作为最后的类间散度矩阵，我不是很清楚。甚至我觉得，$\text{(12)}$的定义是多余的。类间散度实际上可以根据：

​ 类内散度通常小于类间散度，在最优投影取得的情况下就更是这样了。所以每个样本，在类间散度很大的情况下，可以看作一个十分接近类内均值的点（如下图所示）。那么每个样本点都可以近似地被类内均值取代。

Figure 2. 样本与均值的近似性

​ 那么很自然，类间散度可以定义为（每个样本（近似）与全局均值的散度和） $$\begin{array}{}\text{(13)}& S_b=\sum _{i=1}^M{m}_i({\mu }_i-\mu )({\mu }_i-\mu {)}^T\end{array}$$ ​ 优化目标也需要更改，因为实际的输出式已经变成了如下式所示的多维线性组合矩阵$W$，输出是多维的，那么可以简单地使用迹进行实现。 $$\begin{array}{}\text{(14)}& \frac{W^T{S}_{b}W}{W^T{S}_{b}W}\to \text{ max }\frac{tr(W^T{S}_{b}W)}{tr(W^T{S}_{b}W)}\end{array}$$ ​ 对于上式，继续根据拉格朗日乘子法可以得到： $$\begin{array}{}\text{(15)}& S_{b}W=\lambda S_{w}W\to {S_w}^{-1}{S}_{b}W=\lambda W\end{array}$$ ​ 可知，$W$是一个(n * M-1)维矩阵，而显然$\text{(15)}$中$W$的每个列向量分量都是矩阵${S_w}^{-1}{S}_b$的一个特征向量（符合特征向量定义，当然可能是广义特征向量），那么$\left(\begin{array}{c}N-1\\ n\end{array}\right)$种不同的情况，究竟是哪N-1个特征向量组合成了最终的解$W$？从公式$\text{(15)}$种可以看出，$\lambda$越大越好（对应最大化$\text{(14)}$）。那么只需要选择${S_w}^{-1}{S}_b$最大的N-1个特征值（或者广义特征值）的特征向量组成解即可。

---

树型 - 决策树

树越是向往高处的光亮,它的根就越要向下,向泥土,向黑暗的深处。—尼采

​ emmm。这句话只因为有个“树”字就被我拿出来镇一镇文章了。决策树，利用一个个不相互影响的特征（或者我们认为影响不太大的特征，实际上有影响也是可以通过某些操作进行转化的）进行层层分类。正如猜物游戏，每次只能问一个答案只有“是”和“否”的问题，通过答案产生的分支进行推测。通过对待分类样本的层层分解可以获得最终的分类推测。本节只讨论其相关的数学原理，对于具体的生成 / 剪枝算法将不会涉及（因为这没有吸引到我）。

信息论相关

​ 回顾一下信息熵的两个定义： $$\begin{array}{}\text{(16)}& Ent(x)=-\sum _{i=1}^n{p}_{i}log(p_i)\text{ or }Ent(x)=-\int p(x)log(p(x))dx\end{array}$$ ​ 左边为常见的离散型随机变量熵的定义，而右边则为连续变量在其PDF意义下的熵。在讲KL散度的时候已经说过了，熵是用于衡量信息编码的一个概念。一个随机事件的不确定性越大，代表信息量越大，编码这个事件所需要的二进制位数也相应越大。

​ 在决策树一章中，《西瓜书》提到：

"信息熵" (information entropy) 是度量样本集合纯度最常用的一种指标。

​ 为什么这么说呢？集合样本纯度又是指什么？纯度在此处指：同一个划分中，由于划分集合内的元素都存在相应的label，如果集合内的label越趋于一致，那么这个集合的纯度也就越高。如果用比例$p_k$表示划分集合中，第k类样本所占的比例，那么这个集合的信息熵（纯度）表示如下： $$\begin{array}{}\text{(17)}& Ent(D)=-\sum _{i=1}^n{p}_{i}log(p_i)\end{array}$$ ​ 可以看出，公式$\text{(17)}$定义的纯度，当某一类完全占据整个集合时熵取得最小值0。为什么要讨论信息熵或者是纯度？处于决策树的生成考虑，我们使用很多特征生成一棵决策树，但在决策树中，不同的特征地位也是不相同的，naive的情况下，每次分支只选择其中一个特征，那么要选哪一个特征作为本结点向下分支的特征？需要进行优选，优选的指标就是纯度。

​ 显然，如果一种划分模式可以划分出纯度较高的子结点（样本子集合），那么：

• 全纯结点（只有一类）可以避免进一步分支，减小树结构复杂度
• 子集合越纯，说明分类效果越好（因为原集合是无序的，熵大，分类可以看作熵减过程）

​ 由此我们定义信息增益：对于公式$\text{(17)}$定义的“纯度”，个人认为应该叫做“杂度”更好，实际上我看Wikipedia称这个为“impurity”，很显然嘛，值越大杂度越高。那么原集合的杂度为$Ent(D)$，如何选取划分才能使得系统的杂度下降最大呢？假设我们选取的属性$a$存在$v$个不同的值（也就是$v$分支），那么每个分支（a属性的每种可能取值）都会有一定样本（可以为0），记为$D^v$。对应地，$Ent(D^v)$指的是总体为$D^v$时，分类的杂度。那么根据$|D^v|/|D|$ 也即每个属性样本的占比对杂度进行加权，划分后的系统杂度为： $$\begin{array}{}\text{(18)}& G(D,a)=Ent(D)-\sum _{j=1}^v\frac{|D^j|}{|D|}Ent(D^j)\end{array}$$ ​ 公式$\text{(18)}$是原系统的杂度 减去 划分后的系统杂度。这也就是分类，这个熵减过程到底让系统的熵减了多少。这被称为信息增益（information gain），实际上衡量的就是分类使系统熵减少的量。显然我们希望，熵减越大越好。那么每次从属性集合中计算 / 选择信息增益最大的属性进行分支即可。

互信息

​ 信息论中，如果需要衡量两个随机变量之间的关系，可以计算 一个随机变量携带的信息包含另一个随机变量信息的量大小，这被定义为互信息（mutual information）。可以这样认为：两个有关联的变量，给定其中一个变量的信息，另一个变量的不确定性随之减小： $$\begin{array}{}\text{(19)}& I(X;Y)=D_{KL}(P_{XY}||P_X\otimes P_Y),\text{ where }x\in \mathcal{X},y\in \mathcal{Y}\end{array}$$ ​ 上式说的是：x是空间$\mathcal{X}$中的随机变量，y是空间$\mathcal{Y}$中的随机变量，那么互信息是联合分布$P_{XY}$与边缘分布$P_X\text{ and }{P}_Y$的外积的KL散度。多维空间不好理解的话，讨论一维变量： $$\begin{array}{}\text{(20)}& I(X;Y)={\int }_y{\int }_{x}p(x,y)log\left(\frac{p(x,y)}{p(x)p(y)}\right)dxdy\end{array}$$ ​ 为什么这样可以描述相关程度呢？因为显然，X与Y独立时的联合分布为$p(x)p(y)$，此处衡量的即是真实联合分布$p(x,y)$与独立时的联合分布的差别。

​ 互信息和信息增益是存在关系的[1]。在划分时，如果对属性集合A（也就是$a$所在的集合）取上一个期望，那么会有什么发现？也即对公式$\text{(18)}$定义的信息增益取A的期望，为了方便数学变换，我们将$\text{(18)}$展开： $$\begin{array}{}\text{(21)}& G(D,a)=-\sum _{k=1}^J{p}_{k}lo{g}_2{p}_k-\sum _{v=1}^V\frac{|D^v|}{|D|}(-\sum _{k=1}^J{p}_{D^v,k}lo{g}_2{p}_{D^v,k})\end{array}$$ ​ 显然公式$\text{(21)}$可以被表示为（原系统熵 - 给定划分下的新集合熵） $$\begin{array}{}\text{(22)}& G(D,a)=Ent(D)-Ent(D|a)\end{array}$$ ​ 进行期望的求取可以得到： $$\begin{array}{}\text{(23)}& E_A(G(D,a))=Ent(D)-Ent(D|A)\end{array}$$ ​ 下面证明一个有关互信息的简单结论： $$\begin{array}{}\text{(24)}& I(X;Y)=Ent(X)-Ent(X|Y)\end{array}$$ ​ 怎么说呢。推了好长时间没有推出来的原因就是：没有学过信息论，概念不清楚。比如$\text{(24)}$右边的第二项，条件信息熵，定义为： $$\begin{array}{}\text{(25)}& Ent(X|Y)=\sum _{x\in \mathcal{X},y\in \mathcal{Y}}p(x,y)log(p(x|y)),\text{ but not }\sum _{x\in \mathcal{X}}p(x|y)log(p(x|y))\end{array}$$ ​ 那么$\text{(24)}$可以展开为： $$\begin{array}{}\text{(26)}& I(X;Y)=-\sum _{y\in \mathcal{Y}}\sum _{x\in \mathcal{X}}p(x,y)log(p(x))+\sum _{y\in \mathcal{Y}}\sum _{x\in \mathcal{X}}p(x,y)log\left(\frac{p(x,y)}{p(y)}\right)\end{array}$$ ​ 化简可以得到公式$\text{(24)}$成立。那么可以知道，增益率对于A的期望（也就是对于属性集的概率平均）就是决策树结点与属性集的互信息。

增益率

​ 实际上，纯使用信息增益并不太好。假设某个分支结点只有一个样本，那么显然分支纯度最大（杂度最小），那么假如有一个属性分支极多，可能一下就将所有的样本分到不同结点上了（比如《西瓜书》上提到的，样本序号），这样容易产生过拟合的分支属性是没有意义的，但是只用信息增益的话实际就会选择这个分支方法。所以使用一个因子来限定分支数的影响： $$\begin{array}{}\text{(27)}& IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}log\left(\frac{|D^v|}{|D|}\right)\end{array}$$ ​ 可以发现，当分支数越多，这个值越大（不会出现单分支）。这个值称为：固有值（intrinsic value），只需要使用这个值对增益进行惩罚即可（除以此值）。

基尼指数

​ 针对CART决策树的，而以上所说的决策树使用信息增益作为划分属性选择的度量。基尼指数（Gini impurity）指的是：

Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset.[1]

​ 翻译很简单：从集合中随机选择一个元素，再根据这个集合中的类别概率分布随机给这个元素进行分类，分类的错误概率就是基尼指数。 $$\begin{array}{}\text{(28)}& Gini(D)=\sum _{i=1}^{|\mathcal{Y}|}{p}_i\sum _{k\ne i}{p}_k=1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2\end{array}$$ ​ 显然，纯度越高的集合，内部随机取元素随机分类错误的概率（期望）越小。

变量缺失处理的理解

​ 在贝叶斯决策论中提到：

• 某一属性组合的变量可能根本不在样本中出现，但是不能直接认为这样的样本不存在。

​ 而在决策树中，我们更多针对的问题是：当某一个样本某个属性值是未知的，如何处理这样的样本？丢弃是显然不可取的，这样可能损失太多的有效信息。而直接使用确实也不是办法，少掉一个属性要如何继续分支？《西瓜书》上将问题总结地很不错：

我们需解决两个问题: (1) 如何在属性值缺失的情况进行划分属性选择 ? (2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分 ?

​ 第一个问题我开始并没有什么很好的想法。而对于第二个问题，个人开始认为，假设已经知道了划分属性，可以根据其他完好样本来估计本样本在这个缺失属性上的分布，进行分布加权（事实上，这个想法类似《西瓜书》上提供的方法）。

​ 问题一实际上比较容易，我想得太复杂了。由于划分属性只考虑一个属性与分类结果的关系，那么完全用不着考虑多属性关系，只需要取出这个属性下对应没有缺失的样本，利用这些样本估计【属性】对【分类结果】的影响即可。以信息增益法为例，考虑$\text{(18)}$定义的信息增益。假设我们讨论属性$a$，由于有些样本属性是缺失的，在计算时将这些样本剔除再计算新集合$\tilde{D}$的信息增益$\tilde{G}(\tilde{D},a)$。注意，此信息增益计算出来后需要加权： $$\begin{array}{}\text{(29)}& \tilde{G}(\tilde{D},a)\times \rho ,\text{ what is ρ?}\end{array}$$ ​ 其中的$\rho$是加权因子，是什么权重呢？假设属性a在集合中有$|\tilde{D}|$个未缺失样本，那么$\rho =|\tilde{D}|/|D|$，也就是说，样本缺失越少，信息增益计算越可信。

​ 问题2实际上是将“让同一个样本以不同的概率划入到不同的子结点中去”（《西瓜书》言）。也可以使用没有缺失属性a的样本信息，假设某一分支分到属性a的v取值$a^v$上： $$\begin{array}{}\text{(30)}& \widetilde{r_v}=\frac{\sum _{x\in {\tilde{D}}_v}{w}_x}{\sum _{x\in \tilde{D}}{w}_x}\end{array}$$ ​ 也就是没有缺失属性a的样本中，有$\widetilde{r_v}$比例样本在本属性上取值为v，那么当每个样本权重为$w_x$时，可以按照比例将缺失样本分配给不同分支（相当于按照概率（比例）割裂一个缺失样本）。

Kernelization

​ 普通决策树的分类边界都是垂直于某个轴的（因为决策树是一种“非黑即白”的分类方法）。在某个属性（某个维度）上，只有固定的几种分法：

Figure 3. 决策树在单一维度上的分类边界总是垂直于轴的

​ 啊这？太过于“一维”了，甚至连简单的线性可分分类都需要经过如下的艰难操作：

Figure 4. 决策树扭来扭去

​ 一个简单的想法就是：不适用原属性进行分类，我们可以像PCA那样，使用属性的线性组合形成抽象属性，在这个抽象属性对应的新空间中，虽然分类边界仍然垂直于新的空间轴，但在原空间看起来，就成为一般线性分类器了。而进一步地，如果使用其他的非线性特征组合方法，也就是引入某些 kernel，甚至可以通过决策树达到任意分类边界生成的效果。

---

Reference

[1] Wikipedia, Decision tree learning