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

第五章数据分类SLIQ:一种快速可扩展的分类算法SPRINT:数据挖掘中一种可扩展的并行分类器基本内容SLIQ:一种快速可扩展的分类算法SPRINT:数据挖掘中一种可扩展的并行分类器基本内容分类算法存在一个问题——不能进行扩展数据量在急剧增长，训练样本达到数百万是非常普遍的，由于内存及CPU时间的限制，原有的许多算法已经无法处理这些数据。因此，必须寻找新的方法来解决大数据集的分类问题。SLIQ:一种快速可扩展的分类算法可扩展：对应于分类算法评估尺度中的伸缩性。伸缩性：指对磁盘驻留数据的处理能力，即对大数据量有效构造模型的能力。SLIQ算法提出的意义：为了解决一般算法无法解决的可伸缩性问题。扩展性问题决策树的构造分为两个阶段：1.树的构建对每个属性分支计算最优分支选择。使用最优的分支生成划分。2.树的修剪修剪策略有基于代价复杂度的修剪，悲观修剪，和最小描述长度MDL修剪。一般决策树分类方法决策树的构造分为两个阶段：1.树的构建对每个属性分支计算最优分支选择。使用最优的分支生成划分。2.树的修剪修剪策略有基于代价复杂度的修剪，悲观修剪，和最小描述长度MDL修剪。一般决策分类方法最优分支的选择依据于分支指标，分支指标用来给属性的可选分支确定“优良程度”。分支指标：熵（ID3和C4.5）最小Gini指标（CART，SLIQ和SPRINT）。最优分支的选择问题SLIQ使用Gini指标作为分支指标定义：对数据集包含n个类的数据集S，Gini(S)定义为：，Pj是S中第j类数据的频率。如果集合S分成两部分S1andS2。那么这个分割的Gini就是：提供最小Ginisplit就被选择作为分割的标准。21()1njjGiniSP1212()()()splitnnSGiniGiniGiniSSnn式中，n1，n2分别是S1，S2的记录数。连续属性的分支选择操作：采用的二叉分支的方法。第一步，与C4.5的处理方法类似，即根据将要分支的属性取值对训练样本进行排序。设属性取值排序后的结果为v1，v2……，vn，vi和vi+1之间一般取中间点(vi+vi+1)/2作为分支点，这样需确定n-1个可能的分支。因为每次计算都需要排序，所以这项操作的代价极大。解决：SLIQ在树的构建阶段是用预排序技术以减少计算连续属性的代价。Av离散属性的分支选择测试：设S（A）为离散属性A的所有值的集合，则分支测试就是具有的形式，其中为S产生的子集。有n个取值的属性所产生的子集数量为个。因此对最优子集的搜索的代价将是十分昂贵的。解决：若属性A所有可能值的集合S的笛卡尔乘积小于一个阈值MAXSETSIZE，则直接计算S的所有子集。否则使用贪心算法。ASS2n贪心算法：即先将一个集合C置为空集，另一个集合D包含所有的值，然后反复地从D中选取一个值移至C中，直到没有合适的值可以选取。选择移动的值应满足条件：移动后导致Gini值减小并且与移动其它值相比其Gini值是最小的。修剪阶段要选出拥有最小已估计错误比率的子树。估计错误比率的方法：使用原始训练样本集，如交叉验证等。对于大数据集不可用，因构建一个决策树代价很大。使用独立的数据集，如何确定测试数据集的大小，及导致精度降低。解决：SLIQ使用基于最小描述长度（MDL）方法来修剪决策树。树的修剪1.用预排序技术来减少计算连续属性的代价。2.利用贪心算法来确定离散属性的分支。3.使用MDL算法修剪树。SLIQ使用如下技术提高可扩展性SLIQ使用若干驻留磁盘的属性表和单个驻留内存的类表。属性表：有两个字段，①属性值，②指向类表的索引。类表：也有两个字段，①类的标号，②决策树叶节点的指针。SLIQ中预排序所需的数据结构天气索引晴0多云1…………类型叶点适合N1不适合N1…………首先，对训练数据扫描一次后，为每一个非类别属性建立一个属性表，每一个属性值都对应着相应的类表索引。类表的所有叶指针字段都指向决策树的根节点。连续属性的属性表独立地进行排序。预排序过程预排序举例agesalaryclass3065G2315B4075G5540B55100G4560Gagerid232301403456555554salaryrid1524046066517531005classleafGN1BN1GN1BN1GN1GN1预排序后123456驻留磁盘的属性表驻留内存的类表训练数据集预排序后最佳分割包括两个内容：属性的最佳分割点，最佳的分割属性。为了计算节点中属性的分支指标Gini，在每个叶节点对应的数据划分中需使用类的频率分布。分布通过附加在每一个叶节点上的类矩形表累计。计算最佳分割类矩形表类矩形表(histogram)：位于决策树的每个节点内，存放每个节点当前的类分布信息——左、右子树的每个类各拥有多少条记录。对于连续属性，矩形表由形如类，频率的若干对组成。对于离散属性，矩形表有形如属性值，类，频率的若干三元组组成。当前属性是连续属性时，每次做遍历时，类矩形表亦随之改变，随时表征以当前属性A的当前值v做分割点时对叶子的分裂状况。并由类矩形表计算出某个分裂方案的Gini值。完成对属性A的遍历后，Gini值最低的A的值就是用属性A分裂的最佳值。新方案可以存入决策树节点。计算连续属性最佳分割当前属性是离散属性时，遍历过程中，记录下每个属性值对应的类的分布信息。遍历完成后，利用贪心算法得到Gini最小的离散属性A的子集。即为所求的用A的分裂方案。新方案可以存入决策树节点。计算离散属性最佳分割分支计算举例如图，假设在属性age上使用分支对数据已初始化。当前待分裂属性Salary，右边为类矩形图的变化过程。属性表从上往下扫描。12345635agesalaryrid1524046066517531005classleafGN2BN2GN3BN3GN3GN3N1N2N3001100131001001310011003初始矩形表更新类矩形表及计算N2第一个分支节点(salary≤15)更新类矩形表及计算N3第一个分支节点(salary≤40)BGBGBGBGBGBGLRLRLRLRLRLR35age最佳分割求解出后，信息已存放在节点中，算法的下一步便是创建子节点、更新类表。这一步的主要任务是对应该分裂的类表进行更改。选择分支属性生成子节点并更新类表Updatelables()for在分支中使用的每一个属性Ado遍历A的属性表for属性表中的每一个值vdo找到类表中的对应位置（比如说e）通过在从e指向的节点上进行分支测试找到v所属的新类c将e的类标号更新到c更新在e中引用的节点到与类c对应的子节点endend类表的更新算法类表更新举例agerid232301403456555554salaryrid1524046066517531005classleafGN2BN4GN3BN3GN3GN3N1N2N3N4N5N6N7123456N6Age≤35Salary≤50Salary≤40属性表类表属性表MDL(MinimumDescriptionLength)思想：遵循最简单的解就是最期望的。编码的总代价为：Cost(M,D)=cost(D/M)+cost(M)其中,cost(D/M)：给定模型M后对数据编码的比特数。cost(M)：对模型M编码的代价。MDL目标：就是修剪决策树以使Cost(M,D)最小。SLIQ采用MDL修剪算法的控制结构是一个队列。这个队列存放当前的所有叶子节点，这是为了控制搜索的结束。当队列为空时，说明所有的叶子节点都已经被处理完毕，这时建树算法可以结束。算法流程算法流程举例设训练样本数据集如下：agesalaryclass3065G2315B4075G5540B55100G4560GSLIQ的执行过程创建根节点N1创建并排序属性表，创建类表：属性表属性表类表123456年龄表工资表类表agerid232301403456555554salaryrid1524046066517531005N1classleafGN1BN1GN1BN1GN1GN1预排序SLIQ的执行过程创建空队列queue，并将N1入队fr队列queue的队头元素出队，及N1出队计算出刚出队的元素N1所对应节点Ginisplit①计算属性age的Ginisplitage对应节点N1的取值有：23、30、40、45、55、55分别计算N1splitsplitsplitsplitsplit2330304040454555ini23iniiniiniini2222GGGGG、、、、、splitini55GAge中Gini值的计算对于即的计算方法如下：首先构造节点N1的类矩形表，如图（a）；其次根据age的属性确定类矩形表中元素的值，结果如图（b）；最后根据图（b）计算即：同理可以求出、、splitini35Gsplit3040ini2GBGLR（a）BGLR1113（b）splitini35Gsplit21111411335ini35110.42622226444412Gsplit4555ini0.422Gsplitini230.44Gsplit2330ini0.62Gsplit4045ini0.62Gsplitini550.44Gsalary中Gini值的计算②计算属性salary的GinisplitSalary属性中取值有：15、40、60、65、75、10同样以计算出值分别为0.44、0.27、0.22、0.33、0.4、0.44。由上可知，属性salary的最小，那么N1引出两个孩子节点N2和N3，将N2和N3入队，并将salary属性表的第一和第二个记录（salary=50）的Index值在类表中对应的leaf值改为N2，类表中其余的改为N3，如下图表示。frsplitsplitsplitsplit154040606065ini15iniiniini222GGGG、、、、splitsplit657575100iniini22GG、split4060ini2GN2N3类表更新agerid232301403456555554classleafGN3BN2GN3BN2GN3GN3N1N2N3salary≤50属性表类表123456年龄表类表队列queue的队头元素N2出队计算刚出队元素N2所对应的节点的Ginisplit。此时只需考虑age属性，由属性表可知age对应的节点N2取值有：23、55，再由类表可知对于这两条记录都属于B类，所以不需要计算gini值，节点N2不再分解。队列queue的队头元素N3出队计算N3所对应的节点的Ginisplit。此时只需考虑age属性，由属性表可知age对应的节点N3取值有：30、40、45、55，由类属性表可知其都属于G类，故也无需计算gini值，N3也不再分解，作为叶节点。队列queue为空，整个过程结束。对应的决策树如图。N1N2N3salary≤50SLIQ采用二分查找树结构，对每个节点先计算最佳分裂方案，然后再执行分裂。SLIQ使用新的数据结构以利于树的构造：若干驻留磁盘的属性表和单个驻留内存的类表。SLIQ算法总结优点：1、可处理磁盘常驻的大型数据集。2、使用预排序技术，提高了运算速度。3、可处理离散属性和连续属性。缺点：由于类表需要常驻内存，因此限制了SLIQ算法可处理的数据记录规模。SLIQ算法的优缺点SLIQ:一种快速可扩展的分类算法SPRINT:数据挖掘中一种可扩展的并行分类器基本内容SPRINT串行算法SPRINT并行算法SPRINT:一种可扩