《计算机科学》 2010年

部分摘要：指出了该算法的取指偏向性以及运算效率不高等缺点，在此基础上提出了改进的ID3算法，该算法通过引入先验知识度参数，有效克服ID3算法中的取值偏向性和运算效率不高等问题。

算法改进：针对传统的ID3算法的缺点与不足进行以下三点尝试性的改进。

（1）  引入权重因子m，设属性A有n种取值，那么m=1/n（可根据经验设定）；

则G(A)=[I(p,n)-E(A)]*m

（2）  定义函数H(p,1-p)=-p*log(p)-(1-p)log(1-p), 【其中logx以2为底】；

（3）  事后剪枝；自下而上检查内部节点，如果子树产生的错误大于叶节点表示代替它所产生的错误，就剪掉子树；

 

评价：

客户流失评价矩阵：

	预测流失	预测不流失	合计
实际流失	TP	FN	TP+FN
实际不流失	FP	TN	FP+TN
合计	TP+FP	FN+TN	TP+FN+FP+TN

TP(True Position);FP(False Position);

FN(False Negatives);TN(True Negatives)

预测命中率=*100%

预测覆盖率=*100%

预测命中率是描述模型精确度的指标（在本文中是预测流失中实际流失的比例）

预测覆盖率是描述模型普适性的指标（本文中是实际流失中预测正确的比例）

 

 

实验结果对比：

取2009年5月份前的历史数据，随机抽取2000条记录进行建模，预测模型对训练集的预测结果：

	预测流失	预测不流失	合计
实际流失	304	60	364
实际不流失	20	1616	1636
合计	324	1676	2000

预测命中率=*100%=93.33%

预测覆盖率=*100%=83.62%

取2009年5月份的历史数据，随机抽取2000条记录进行预测，则模型对测试集的预测结果：

	预测流失	预测不流失	合计
实际流失	252	98	348
实际不流失	106	1548	1652
合计	358	1642	2000

预测命中率=*100%=70.39%

预测覆盖率=*100%=72.41%

结果对比检验表明，模型的预测命中率与覆盖率比训练情况稍差，但依然保持了比较好的预测性能。

另外，为了验证改进算法的有效性，采用同样的数据集建模，在相同的计算机平台上将改进后的决策树算法的效率和原来ID3决策树算法的效率进行对比，其计算效率提高了23.5左右，这充分说明使用该改进算法能够以更高的效率和准确率构造决策树，基本达到了实验要求。

 

 

部分结束语：

结果表明，改进算法不仅能更快更高效地建立模型，而且可以提供更高的检测率和更低的误检率。改进的ID3算法的关键是引入调整因子，而调整因子如何确定是以后要进一步研究的工作。