河南泥鳅SLIQ一种快速可伸缩分类器ManishMehta.pptVIP

SLIQ：一种快速可伸缩分类器Manish Mehta, Rakesh Agrawal, Jorma RissanenIBM Almaden Research Center, 1996 报告人：郭新涛 2003.03.29 内容摘要 决策树算法 SLIQ算法 数据结构 预排序与广度优先增长策略 种类型字段的最佳子集生成方法 MDL剪枝 SLIQ性能评估 1. 决策树算法 决策树算法 SLIQ算法 数据结构 预排序与广度优先增长策略 种类型字段的最佳子集生成方法 MDL剪枝 SLIQ性能评估 1. 决策树算法 什么是分类（Classification）？ 训练集 待测试样本集 可伸缩性（Scalability） 大多数分类算法面临的共同问题：训练集受内存容量的限制。 算法可伸缩性的优势：更高的准确性 设计目标：一个可伸缩的分类器 1. 决策树算法 什么是决策树（Decision Tree）？ 决策树的优点 与其他分类方法相比相对较快 容易转化为分类规则，也容易转化为SQL查询 近似的或者更好的准确度 1. 决策树算法 算法 建树阶段 MakeTree (Training Data T) Partition (T);Partition (Data S) if (all points in S are in the same class) then return; evaluate splits for each attribute A Use best split found to partition S into S1 and S2; Partition (S1); Partition (S2); 剪枝阶段 为什么剪枝：训练数据中的“噪声”影响最终模型的准确性。这些错误的枝条将导致利用模型时的分类错误。 剪枝的方法：去除那些导致错误的枝条，在可能的自述中挑选出错率最小的字树。 1. 决策树算法 可伸缩性问题研讨（1） 设计目标：一个可伸缩的、能够处理大数据集的决策树 以前的可伸缩性方案 数据采样 连续属性的离散化 数据分成若干小块，分别构建决策树，然后综合成一棵最终的树 面临的问题：降低了准确性 决策树算法 可伸缩性问题研讨（2） 建树阶段 关键：提高“确定最佳分裂（Best Split ）”的可伸缩性 分裂指标举例 ，计算开销不大 数值型字段，最佳分裂型如 ，开销主要是排序 种类型字段，最佳分裂型如 ，开销主要是寻找最佳的子集（遍历所有子集，时间复杂度为指数级）。 1. 决策树算法 可伸缩性问题研讨（3） 剪枝阶段 剪枝：选择导致最低错误率的子树 方案一：使用原有的测试数据 方案二：使用独立的数据集 取样困难 降低生成的模型的准确率 理想的剪枝方法：快速得到简洁而且准确的决策树 2. SLIQ算法 决策树算法 SLIQ算法 数据结构 预排序与广度优先增长策略 种类型字段的最佳子集生成方法 MDL剪枝 SLIQ性能评估 2. SLIQ算法 SLIQ的优异性能 可伸缩性良好 缩短学习时间 处理常驻磁盘的大数据集的能力：对训练数据的记录个数和训练样本的属性个数没有过多的限制 处理大数据集，带来结果的准确性 新的剪枝方法 更简洁、准确的结果 2. SLIQ算法 SLIQ的关键词 预排序 广度优先增长策略 常驻磁盘的数据集 快速寻找子集方法 MDL剪枝 2. SLIQ算法 数据结构 属性表（Attribute List） 每个属性有一个属性表 有必要的话，属性表可以写回磁盘 类表（Class List） 仅有一张类表，类表必须常驻内存 类表第n项，存放第n条记录的类标签。 2. SLIQ算法 数据结构 树结点 内部节点记录必要的分类信息 叶子节点代表训练集的一块数据，也就是一个类别 每个节点都有一个类直方图，用来统计分类所需的必要的类别分布的信息。 2. SLIQ算法 预排序与广度优先增长策略 预排序的例子 2. SLIQ算法 预排序与广度优先增长策略 计算最佳分割的算法EvaluateSplits() for each attribute A do traverse attribute list of A for each value v in the attribute list do find the corresponding entry in the class list, and hence the corresponding class