SPRINT: A Scalable Parallel Classifier for Data Mining

ID3之后的决策树分类算法

分裂指数

分裂指数是用来度量属性分裂规则优劣程度的一个量度。gini指数(gini index)是一种能够有效地搜索极佳分裂点的分裂指数，在SPRINT算法中就是采用了gini指数。

PS: gini指数
Gini指数(Gini Index)是从Gini系数(Gini Coefficient)演算而来，是20世纪初意大利统计学家Corrado Gini所发明的指标，用来判断地区所得分配与贫富差距程度。Gini系数介于0与1之间，愈接近0表示贫富差距程度愈低，愈接近1则表示贫富差距程度愈高。Gini指数则是将Gini系数乘以100后所得数据。
小值表示平均，大值表示悬殊。

数据集S有n条记录，分别属于c个互不相关的类，则：
其中Pj = m/n，m为S中属于类 j 的记录个数。

使用分裂规则cond 将S 划分为两个子集 S1, S2，则该规则的度量值为：
这个值越小，这个分裂规则越好。

SPRINT算法思想

采用贪心方法，用自上而下的递归方式生成二叉树。
创建阶段：对每个属性找到最佳分裂；比较各个属性的最佳分裂，选择一个最佳的。
剪枝阶段：采用了最小描述长度（MDL）原则。

结论

SPRINT算法是IBM提出的一种决策树分类算法，在可伸缩性和并行性方面是潜力股，其应用是分类。


转载本文请联系原作者获取授权，同时请注明本文来自唐李洋科学网博客。
链接地址：https://blog.sciencenet.cn/blog-425672-319846.html

上一篇：Force.com的多租户架构理解（五）
下一篇：动态数据挖掘