数据挖掘150道面试题（三） 50-60题
53. 以下哪项关于决策树的说法是错误的 (C)A. 冗余属性不会对决策树的准确率造成不利的影响
B. 子树可能在决策树中重复多次
C. 决策树算法对于噪声的干扰非常敏感
D. 寻找最佳决策树是NP完全问题
55. 以下哪些算法是基于规则的分类器 (A)
A. C4.5
B. KNN
C. Na?ve Bayes
D. ANN
ID3算法 从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。 设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为： http://latex.codecogs.com/gif.latex?info(D)=-\sum%20^m_{i=1}p_ilog_2(p_i) 其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。 现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为： http://latex.codecogs.com/gif.latex?info_A(D)=\sum%20^v_{j=1}\frac{|D_j|}{|D|}info(D_j) 而信息增益即为两者的差值： http://latex.codecogs.com/gif.latex?gain(A)=info(D)-info_A(D) ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：
其中s、m和l分别表示小、中和大。 设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益。 http://latex.codecogs.com/gif.latex?info(D)=-0.7log_20.7-0.3log_20.3=0.7*0.51+0.3*1.74=0.879 http://latex.codecogs.com/gif.latex?info_L(D)=0.3*(-\frac{0}{3}log_2\frac{0}{3}-\frac{3}{3}log_2\frac{3}{3})+0.4*(-\frac{1}{4}log_2\frac{1}{4}-\frac{3}{4}log_2\frac{3}{4})+0.3*(-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3})=0+0.326+0.277=0.603 http://latex.codecogs.com/gif.latex?gain(L)=0.879-0.603=0.276 因此日志密度的信息增益是0.276。 用同样方法得到H和F的信息增益分别为0.033和0.553。 因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：http://images.cnblogs.com/cnblogs_com/leoo2sk/WindowsLiveWriter/34d255f282ae_B984/3_3.png 在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。 上面为了简便，将特征属性离散化了，其实日志密度和好友密度都是连续的属性。对于特征属性为连续值，可以如此使用ID3算法： 先将D中元素按照特征属性排序，则每两个相邻元素的中间点可以看做潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。C4.5算法 ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。 C4.5算法首先定义了“分裂信息”，其定义可以表示成： http://latex.codecogs.com/gif.latex?split\_info_A(D)=-\sum%20^v_{j=1}\frac{|D_j|}{|D|}log_2(\frac{|D_j|}{|D|}) 其中各符号意义与ID3算法相同，然后，增益率被定义为： http://latex.codecogs.com/gif.latex?gain\_ratio(A)=\frac{gain(A)}{split\_info(A)}
ANN简介：人工神经网络提供了一种普遍而且实用的方法从样例中学习实数、离散值或向量法函数。它适合具有以下特征的问题：>实例是用很多“属性-值”对表示的；>目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量;>训练数据可能包含错误；>可容忍长时间的训练；>可能需要快速求出目标函数值；>人类能否理解学到的目标函数并不重要。
页:
[1]