数据挖掘・第五章--数据分类.ppt

《数据挖掘・第五章--数据分类.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章数据分类SLIQ:一种快速可扩展的分类算法SPRINT:数据挖掘中一种可扩展的并行分类器基本内容SLIQ:一种快速可扩展的分类算法SPRINT:数据挖掘中一种可扩展的并行分类器基本内容分类算法存在一个问题——不能进行扩展数据量在急剧增长，训练样本达到数百万是非常普遍的，由于内存及CPU时间的限制，原有的许多算法已经无法处理这些数据。因此，必须寻找新的方法来解决大数据集的分类问题。SLIQ:一种快速可扩展的分类算法可扩展：对应于分类算法评估尺度中的伸缩性。伸缩性：指对磁盘驻留数据的处理能力，即对大数据量有效构造模型的能力。S

2、LIQ算法提出的意义：为了解决一般算法无法解决的可伸缩性问题。扩展性问题决策树的构造分为两个阶段：1.树的构建对每个属性分支计算最优分支选择。使用最优的分支生成划分。2.树的修剪修剪策略有基于代价复杂度的修剪，悲观修剪，和最小描述长度MDL修剪。一般决策树分类方法决策树的构造分为两个阶段：1.树的构建对每个属性分支计算最优分支选择。使用最优的分支生成划分。2.树的修剪修剪策略有基于代价复杂度的修剪，悲观修剪，和最小描述长度MDL修剪。一般决策分类方法最优分支的选择依据于分支指标，分支指标用来给属性的可选分支确定“优良程度”。分支

3、指标：熵（ID3和C4.5）最小Gini指标（CART，SLIQ和SPRINT）。最优分支的选择问题SLIQ使用Gini指标作为分支指标定义：对数据集包含n个类的数据集S，Gini(S)定义为：，Pj是S中第j类数据的频率。如果集合S分成两部分S1andS2。那么这个分割的Gini就是：提供最小Ginisplit就被选择作为分割的标准。式中，n1，n2分别是S1，S2的记录数。连续属性的分支选择操作：采用的二叉分支的方法。第一步，与C4.5的处理方法类似，即根据将要分支的属性取值对训练样本进行排序。设属性取值排序后的结果为v1，

4、v2……，vn，vi和vi+1之间一般取中间点(vi+vi+1)/2作为分支点，这样需确定n-1个可能的分支。因为每次计算都需要排序，所以这项操作的代价极大。解决：SLIQ在树的构建阶段是用预排序技术以减少计算连续属性的代价。离散属性的分支选择测试：设S（A）为离散属性A的所有值的集合，则分支测试就是具有的形式，其中为S产生的子集。有n个取值的属性所产生的子集数量为个。因此对最优子集的搜索的代价将是十分昂贵的。解决：若属性A所有可能值的集合S的笛卡尔乘积小于一个阈值MAXSETSIZE，则直接计算S的所有子集。否则使用贪心算法。

5、贪心算法：即先将一个集合C置为空集，另一个集合D包含所有的值，然后反复地从D中选取一个值移至C中，直到没有合适的值可以选取。选择移动的值应满足条件：移动后导致Gini值减小并且与移动其它值相比其Gini值是最小的。修剪阶段要选出拥有最小已估计错误比率的子树。估计错误比率的方法：使用原始训练样本集，如交叉验证等。对于大数据集不可用，因构建一个决策树代价很大。使用独立的数据集，如何确定测试数据集的大小，及导致精度降低。解决：SLIQ使用基于最小描述长度（MDL）方法来修剪决策树。树的修剪用预排序技术来减少计算连续属性的代价。利用贪心

6、算法来确定离散属性的分支。使用MDL算法修剪树。SLIQ使用如下技术提高可扩展性SLIQ使用若干驻留磁盘的属性表和单个驻留内存的类表。属性表：有两个字段，①属性值，②指向类表的索引。类表：也有两个字段，①类的标号，②决策树叶节点的指针。SLIQ中预排序所需的数据结构首先，对训练数据扫描一次后，为每一个非类别属性建立一个属性表，每一个属性值都对应着相应的类表索引。类表的所有叶指针字段都指向决策树的根节点。连续属性的属性表独立地进行排序。预排序过程预排序举例预排序后123456驻留磁盘的属性表驻留内存的类表训练数据集预排序后最佳分割

7、包括两个内容：属性的最佳分割点，最佳的分割属性。为了计算节点中属性的分支指标Gini，在每个叶节点对应的数据划分中需使用类的频率分布。分布通过附加在每一个叶节点上的类矩形表累计。计算最佳分割类矩形表类矩形表(histogram)：位于决策树的每个节点内，存放每个节点当前的类分布信息——左、右子树的每个类各拥有多少条记录。对于连续属性，矩形表由形如<类，频率>的若干对组成。对于离散属性，矩形表有形如<属性值，类，频率>的若干三元组组成。当前属性是连续属性时，每次做遍历时，类矩形表亦随之改变，随时表征以当前属性A的当前值v做分割点时

8、对叶子的分裂状况。并由类矩形表计算出某个分裂方案的Gini值。完成对属性A的遍历后，Gini值最低的A的值就是用属性A分裂的最佳值。新方案可以存入决策树节点。计算连续属性最佳分割当前属性是离散属性时，遍历过程中，记录下每个属性值对应的类的分布信息。遍历完成后，利