(未完成，Reference未补)

决策树

什么是决策树?

• Tree
• if-then 规则的集合，该集合是决策树上的所有从根节点到叶节点的路径的集合
• 定义在特征空间与类空间上的条件概率分布，决策树实际上是将特征空间划分成了互不相交的单元，每个从根到叶的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中，哪个类别有较高的条件概率，就把该单元中的实例强行划分为该类别。

构建

• 递归过程
• 递归终止
  • 当前结点样本全部属于同一类别
  • 当前属性集合为空，或所有样本在所有属性上取值相同 （利用当前节点的后验分布）
  • 当前结点样本集合为空（利用父结点的样本分布作为先验分布）

优点？

• 数据预处理步骤少
• 解释性较强
• 分类速度快
• 对噪声数据不敏感

学习？

• 最小化损失函数
• 损失函数是正则化的极大似然函数
• 决策树的学习本质上就是从训练数据集中归纳出一组分类规则，使它与训练数据矛盾较小的同时具有较强的泛化能力。
• 基于训练数据集估计条件概率模型
• 只能通过启发式算法学习次最优解
• 过拟合（可通过剪枝解决）

步骤？

• 特征选择
• 模型生成
• 剪枝 (预、后)

特征选择

• 选择分类能力更好的特征

  • 信息增益
    表示得知特征 X 的信息而使得分类难度（不确定信息）减少的程度，信息增益越大越好。用信息增益去选择特征有一个问题，即偏向于选择取值较多的特征。解决思路就是对取值较多的特征进行适当的惩罚。如使用信息增益比。

    
    
    G(D, A) = H(D) - H(D|A)

    • 熵和条件熵
      熵越大，随机变量的不确定性就越大。当 p = 0 或者 p = 1 时可知，随机变量没有不确定性，所以熵为 0。

      
      
      H(p) = -\sum_{i}^{n}p_i logp_i
      
      
      H(Y|X) = -\sum_{i}^{n}p_i H(Y|X = x_i), p_i = P(X = x_i), i =1,2,...,n

  • 信息增益比
    特征 A 对数据训练集 D 的信息增益比为信息增益与训练数据集关于特征A的熵的比。

模型生成

• ID3
  在各个结点应用信息增益准则选择特征，递归构建，直到停止。停止条件可单独设立。信息增益准则对可取值数目较多的属性有偏好。
• C4.5
  和 ID3 使用信息增益不同，该算法使用信息增益比准则选择特征。停止条件可单独设立。信息增益比对可取值数目较少的属性有偏好。C4.5 算法使用了一个启发算法：先选择信息增益高于平均水平的属性，然后在其中选择信息增益比最大的属性。
• 总结
  C4.5 算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。另外，C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
  另外，无论是 ID3 还是 C4.5 最好在小数据集上使用，决策树分类一般只试用于小数据。当属性取值很多时最好选择 C4.5 算法，ID3 得出的效果会非常差，因为使用信息增益划分时它倾向于取值多的属性。

剪枝

• 预
  • 设置深度
  • 叶节点包含样本数最小值
• CART
  • 二叉树决策树算法

  • 使用 Gini 指数，Gini 指数越大，不纯度越大，越不容易区分。这一点类似于熵。

    
    
    Gini_A(D) = \frac{D_1}{D} Gini(D_1) + \frac{D_2}{D} Gini(D_2)

缺失值处理

对于某些采样数据，可能会缺少属性值。在这种情况下，处理缺少属性值的通常做法是赋予该属性的常见值，或者属性均值。另外一种比较好的方法是为该属性的每个可能值赋予一个概率，即将该属性以概率形式赋值。例如给定Boolean属性B，已知采样数据有12个B=0和88个B=1实例，那么在赋值过程中，B属性的缺失值被赋为B(0)=0.12、B(1)=0.88；所以属性B的缺失值以12%概率被分到False的分支，以88%概率被分到True的分支。这种处理的目的是计算信息增益，使得这种属性值缺失的样本也能处理。

聚类（Clustering）的本质是对数据进行分类，将相异的数据尽可能地分开，而将相似的数据聚成一个类别（簇），使得同一类别的数据具有尽可能高的同质性（homogeneity），类别之间有尽可能高的异质性（heterogeneity），从而方便从数据中发现隐含的有用信息。。聚类算法属于无监督学习。

聚类算法的应用
（1）其他数据挖掘任务的关键中间环节：用于构建数据概要，用于分类、模式识别、假设生成和测试；用于异常检测，检测远离群簇的点。
（2）数据摘要、数据压缩、数据降维：例如图像处理中的矢量量化技术。创建一个包含所有簇原型的表，即每个原型赋予一个整数值，作为它在表中的索引。每个对象用与它所在簇相关联的原型的索引表示。
（3）协同过滤：用于推荐系统和用户细分。
（4）动态趋势检测：对流数据进行聚类，检测动态趋势和模式。
（5）用于多媒体数据、生物数据、社交网络数据的应用。
基本方法
1）基于分层的聚类(hierarchical methods)：主要讲给定的数据集进行逐层分解，直到满足某种条件为止。具体可分为“自底向上”和“自顶向下”两种方案。在“自底向上”方案中，初始时每个数据点组成一个单独的组，在接下来的迭代中，按一定的距离度量将相互邻近的组合并成一个组，直至所有的记录组成一个分组或者满足某个条件为止。代表算法有：BIRCH，CURE，CHAMELEON等。
2）基于划分的聚类（partitioning methods）：给定包含N个点的数据集，划分法将构造K个分组，每个分组代表一个聚类，这里每个分组至少包含一个数据点，每个数据点属于且仅属于一个分组。对于给定的K值，算法先给出一个初始的分组方法，然后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案较前一次好，这里好的标准在于同一组中的点越近越好，不同组中的点越远越好。代表算法有：K-means，K-medoids，CLARANS。
3）基于密度的聚类（density-based methods）：基于密度的方法的特点是不依赖于距离，而是依赖于密度，从而克服基于距离的算法只能发现“球形”聚簇的缺点。其核心思想在于只要一个区域中点的密度大于某个阈值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。
（4）基于网格的聚类（gird-based methods）：这种方法通常将数据空间划分成有限个单元的网格结构，所有的处理都是以单个的单元为对象。这样做起来处理速度很快，因为这与数据点的个数无关，而只与单元个数有关。代表算法有：STING，CLIQUE，WaveCluster。
（5）基于模型的聚类（model-based methods）：基于模型的方法给每一个聚类假定一个模型，然后去寻找能很好的拟合模型的数据集。模型可能是数据点在空间中的密度分布函数或者其它。这样的方法通常包含的潜在假设是：数据集是由一系列的潜在概率分布生成的。通常有两种尝试思路：统计学方法和神经网络方法。其中，统计学方法有COBWEB算法、GMM(Gaussian Mixture Model)，神经网络算法有SOM(Self Organized Maps)算法。

聚类分析的要求
不同的聚类算法有不同的应用背景，有的适合于大数据集，可以发现任意形状的聚簇；有的算法思想简单，适用于小数据集。总的来说，数据挖掘中针对聚类的典型要求包括：

（1）可伸缩性：当数据量从几百上升到几百万时，聚类结果的准确度能一致。
（2）处理不同类型属性的能力：许多算法针对的数值类型的数据。但是，实际应用场景中，会遇到二元类型数据，分类/标称类型数据，序数型数据。
（3）发现任意形状的类簇：许多聚类算法基于距离（欧式距离或曼哈顿距离）来量化对象之间的相似度。基于这种方式，我们往往只能发现相似尺寸和密度的球状类簇或者凸型类簇。但是，实际中类簇的形状可能是任意的。
（4）初始化参数的需求最小化：很多算法需要用户提供一定个数的初始参数，比如期望的类簇个数，类簇初始中心点的设定。聚类的结果对这些参数十分敏感，调参数需要大量的人力负担，也非常影响聚类结果的准确性。
（5）处理噪声数据的能力：噪声数据通常可以理解为影响聚类结果的干扰数据，包含孤立点，错误数据等，一些算法对这些噪声数据非常敏感，会导致低质量的聚类。
（6）增量聚类和对输入次序的不敏感：一些算法不能将新加入的数据快速插入到已有的聚类结果中，还有一些算法针对不同次序的数据输入，产生的聚类结果差异很大。
（7）高维性：有些算法只能处理2到3维的低纬度数据，而处理高维数据的能力很弱，高维空间中的数据分布十分稀疏，且高度倾斜。
（8）可解释性和可用性：我们希望得到的聚类结果都能用特定的语义、知识进行解释，和实际的应用场景相联系。