8. 非度量方法

如何构建决策树

这个过程的目标是选择一个特征进行划分，使得划分后的数据不确定性（熵）下降得最多，也就是信息增益最大。

1. 目标：在决策树的每个节点，找出"最佳"的划分特征。
2. 核心度量：
   • 信息熵 (Entropy)：衡量一个数据集的混乱或不纯度。熵越高，不确定性越大。
   其中 是第 类样本的比例， 是类别数。 - 纯净集（只有一类）的熵为 0。 - 均匀混合集（各类数量相等）的熵最大。
   • 信息增益 (Information Gain)：衡量使用一个特征进行划分后，信息熵降低的程度。
   我们选择信息增益最大的特征。
3. 计算步骤： a. 计算当前数据集（父节点）的整体信息熵。 b. 对每一个候选特征，计算其划分后的信息增益。 c. 比较所有特征的信息增益，选择值最大的那个作为本节点的划分标准。

---

举例：单次划分计算

1. 示例数据

我们使用一个新数据集，包含2个类别（a, b），共4个样本。

样本ID	特征1 (F1)	特征2 (F2)	类别 (Y)
1	0	0	a
2	0	1	b
3	1	0	a
4	1	1	b

2. 计算过程

A. 计算根节点（整个数据集D）的熵

• 数据构成：2个'a'，2个'b'。
• （这是熵的最大值，表示数据非常混乱）

B. 尝试按"特征1 (F1)"划分，并计算信息增益

• 子集 F1=0：{样本1, 样本2} -> (1个'a', 1个'b')
• 子集 F1=1：{样本3, 样本4} -> (1个'a', 1个'b')
• 计算信息增益 Gain(D, F1)：

（信息增益为0，说明这个特征对于划分数据毫无帮助）

C. 尝试按"特征2 (F2)"划分，并计算信息增益

• 子集 F2=0：{样本1, 样本3} -> (2个'a', 0个'b')
  • 这是一个纯净集。
• 子集 F2=1：{样本2, 样本4} -> (0个'a', 2个'b')
  • 这也是一个纯净集。
• 计算信息增益 Gain(D, F2)：

（信息增益为1，表示这个特征完美地划分了数据）

3. 比较与决策

因为 ，所以我们选择特征2 (F2) 作为根节点的划分标准。这次划分将数据完美地分成了两个纯净的子集，决策树的构建也因此完成。

问题：异常数据在用决策树分类时的得到的类别距离树根是很远还是很近？为什么？"early exit"是什么？"isolation forest"是如何利用上述特性进行异常检测的？

异常数据在使用决策树分类时，其得到的类别距离树根很近。

• 为什么？ 因为异常数据"稀有且不同"，决策树在追求"纯度"的分裂过程中，仅需一两次划分就能轻易地将这些特殊个体从大量正常数据中分离出来。而正常数据彼此相似，需要更多次划分才能区分，因此路径更长。
• "early exit"是什么？ "early exit"指的就是异常数据在决策树中只需经过很短的路径就到达叶子节点，从而提前"退出"了继续向下遍历的过程。
• "isolation forest"如何利用该特性？ 孤立森林（Isolation Forest）算法正是基于此原理。它构建大量随机树来"孤立"每个数据点。异常点因为更容易被孤立，所以它们在森林中的平均路径长度显著短于正常点。通过计算这个平均路径长度，算法就能高效地识别出异常数据。