数据挖掘：决策树、聚类与商业系统应用

# 数据挖掘：决策树、聚类与商业系统应用 ## 1. 树结构规则的优势 树结构规则因其易于解释而广受欢迎。在数据挖掘中，结果能被非专业人员理解至关重要，而树结构规则恰好满足这一需求。研究表明，尽管其结构存在一定限制，但准确性很高。而且，有高效的算法可从大型数据库中构建树结构规则。接下来，我们将重点探讨决策树的构建算法。 ## 2. 决策树的基本概念 ### 2.1 决策树的定义与结构 决策树是分类规则集合的图形化表示。对于给定的数据记录，它会引导记录从根节点到叶子节点。树的每个内部节点都标有一个预测属性，也称为分裂属性，数据会基于该属性的条件进行“分裂”。内部节点的出边标有涉及该分裂属性的谓词，进入该节点的每个数据记录必须恰好满足一条出边的谓词。分裂属性和出边谓词的组合信息称为节点的分裂准则。没有出边的节点是叶子节点，每个叶子节点都标有一个依赖属性的值。这里我们主要考虑内部节点有两条出边的二叉树，不过更高阶的树也是可行的。 例如，假设有如下决策树：根节点的分裂属性是“age”，根节点左子节点的分裂属性是“cartype”。根节点左出边的谓词是“age ≤ 25”，右出边的谓词是“age > 25”。 ### 2.2 决策树与分类规则的关联 我们可以为树中的每个叶子节点关联一个分类规则。具体方法是，考虑从树的根节点到叶子节点的路径，该路径上的每条边都标有一个谓词，所有这些谓词的合取构成规则的左边；叶子节点上依赖属性的值构成规则的右边。因此，决策树代表了一组分类规则，每个叶子节点对应一条规则。 ### 2.3 决策树的构建阶段 决策树的构建通常分为两个阶段： - **生长阶段**：构建一个过大的树，该树能非常准确地表示输入数据库中的记录。例如，树可能包含输入数据库中单个记录的叶子节点。 - **剪枝阶段**：确定树的最终大小。生长阶段构建的树所代表的规则通常过于专业化，通过减小树的大小，我们可以生成数量更少、更通用的规则，这些规则比大量非常专业化的规则更好。不过，树剪枝算法不在本文讨论范围内。 ### 2.4 分类树算法的构建方式 分类树算法采用贪心的自顶向下方式构建树，具体步骤如下： 1. 在根节点，检查数据库并计算局部“最佳”分裂准则。 2. 根据根节点的分裂准则，将数据库划分为两部分，分别用于左子节点和右子节点。 3. 对每个子节点递归执行上述步骤。 以下是其算法的伪代码： ```plaintext Input: node n, partition D, split selection method S Output: decision tree for D rooted at node n Top-Down Decision Tree Induction Schema: BuildTree(Node n, data partition D, split selection method S) (1) Apply S to D to find the splitting criterion (2) if (a good splitting criterion is found) (3) Create two children nodes n1 and n2 of n (4) Partition D into D1 and D2 (5) BuildTree(n1, D1, S) (6) BuildTree(n2, D2, S) (7) endif ``` ### 2.5 分裂准则的确定 节点的分裂准则通过应用分裂选择方法来确定。分裂选择方法是一种算法，它以（部分）关系作为输入，输出局部“最佳”分裂准则。例如，分裂选择方法会检查“cartype”和“age”等属性，选择其中一个作为分裂属性，然后选择分裂谓词。目前已经开发出许多不同且非常复杂的分裂选择方法。 ### 2.6 大数据库下决策树的构建算法 当输入数据库能装入主内存时，我们可以直接遵循上述分类树归纳模式。但当输入关系大于主内存时，上述算法的第一步会失败，因为输入数据库无法装入内存。不过，我们可以对分裂选择方法进行一个重要观察，这有助于减少主内存需求。 分裂选择方法在检查节点的分区后需要做出两个决策：选择分裂属性和选择出边的分裂谓词。选择节点的分裂准则后，算法会递归应用于该节点的每个子节点。实际上，分裂选择方法并不需要完整的数据库分区作为输入。 对于计算涉及单个预测属性的分裂准则的分裂选择方法，会单独评估每个预测属性。由于每个属性是单独检查的，我们可以为分裂选择方法提供数据库的聚合信息，而不是将完整的数据库加载到主内存中。如果选择正确，这些聚合信息能让我们计算出与检查完整数据库相同的分裂准则。 我们将预测属性的聚合信息称为该属性的AVC集。节点n处预测属性X的AVC集是n的数据库分区在X和依赖属性上的投影，其中依赖属性域中各个值的计数被聚合。例如，对于如下的`InsuranceInfo`关系： | age | cartype | highrisk | | --- | --- | --- | | 23 | Sedan | false | | 30 | Sports | false | | 36 | Sedan | false | | 25 | Truck | true | | 30 | Sedan | false | | 23 | Truck | true | | 30 | Truck | false | | 25 | Sports | true | | 18 | Sedan | false | 根节点对于预测属性“age”的AVC集是以下数据库查询的结果： ```sql SELECT R.age, R.highrisk, COUNT (*) FROM InsuranceInfo R GROUP BY R.age, R.highrisk ``` 根节点左子节点对于预测属性“cartype”的AVC集是以下查询的结果： ```sql SELECT R.cartype, R.highrisk, COUNT (*) FROM InsuranceInfo R WHERE R.age <= 25 GROUP BY R.cartype, R.highrisk ``` 根节点的两个AVC集如下表所示： | highrisk | Car type | true | false | | --- | --- | --- | --- | | | Sedan | 0 | 4 | | | Sports