ID3算法有很多的优点,总结如下:(1)搜索空间是完全的假设空间,目标函数必在搜索空间只能,不存在无解的危险;(2)全部使用训练数据,而不是像候选剪除算法逐个考虑训练例子,这样做可以利用全部的训练例子的统计性质进行决策,从而抵抗噪声;(3)可以生成容易理解的IF-THEN分类规则,即使建立一棵包含几百个属性的大规模复杂决策,也可以较清晰地理解每一条从根节点到叶子节点路径所描述的含义;(4)擅长处理非数值型数据。ID3算法也存在着许多的缺点:(1)ID3偏向于选择取值较多的属性,而在很多情况下取值较多的属性并不是最优的属性。关于这个问题,后续会用增益比率的方法,它将每个属性取值的概率都考虑在内(2)当训练集增加时,ID3决策树也随之变化,决策树对训练集变化的敏感性引起了决策树算法的不稳定性问题,这种不稳定性的现象也使分类中知识发现的过程更加复杂;(3)同多数决策树模型一样,随着重复地将数据划分成越来越小的部分,ID3决策树模型面临着较为严重的碎片问题(碎片是指一个给定分支中的样本数太小而失去统计意义引)。碎片问题带来的最直接的影响就是决策树模型的健壮性降低,并最终降低分类的准确性。一棵健壮的决策树所表现出来的特征之一是较少的叶子节点,即每个叶子节点都有较多的样本数。(4)对噪音比较敏感,不容易取出噪声,也就是特征值错误或类别错误(5)缺乏伸缩性。由于要进行深度优先搜索,所以算法受到内存大小的限制,难以处理大训练集。2.4ID3算法分析算法实现中一般的处理方法是扫描一遍数据库(实际中保存在本地文件中),直接复制数据集到内存,这种做法对内存的消耗很大。若一棵树的深度k,原始数据集数据量为n,每个数据的维数为m,当数据本身为大数据时,m可能很大,则整棵决策树总的空间复杂度为O(n*k*m)(最坏情况为深度为k的满树,即所有叶子节点都在最下面一层,此时每一层为整个数据集的一个划分)。
全文预览
