边缘提取算法读后感集锦(4)

1.2.2 ID3算法
1) 随机选择C的一个子集W (窗口)；
2) 调用CLS生成W的分类树DT(强调的启发式标准在后)；
3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子)；
4) 组合W与已发现的意外，形成新的W；
5) 重复2)到4)，直到无例外为止。
启发式标准：
只跟本身与其子树有关，采取信息理论用熵来量度。
熵是选择事件时选择自由度的量度，其计算方法为：P=freq(Cj,S)/|S|；INFO(S)=-SUM(P*LOG(P))；SUM()函数是求j从1到n的和。Gain(X)=Info(X)-Infox(X)；Infox(X)=SUM( (|Ti|/|T|)*Info(X)；
为保证生成的决策树最小，ID3算法在生成子树时，选取使生成的子树的熵(即Gain(S))最小的特征来生成子树。
ID3算法对数据的要求：
1) 所有属性必须为离散量；
2) 所有的训练例的所有属性必须有一个明确的值；
3) 相同的因素必须得到相同的结论且训练例必须唯一。
1.3 C4.5算法
由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：
产生的分类规则易于理解，准确率较高。
C4.5算法有如下缺点：
在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。