1个月学习小结——代价敏感的数据流分类算法
2013-01-03
最近几个月阅读论文都是“抄家底”的方式进行，即，认准一个作者，把他最近几年的论文看个遍，然后再看看自己有没有新的想法。
其中，第一个作者是西北农林科技的张阳教授，再一个就是针对cost-sensitive decision tree方向看了一些论文，值得说明的是找到一篇比较全面的综述，还是2011年左右的，不过这篇文章还没有详细去看。
这一个多月内（从2012.10.12开题那一天算起），确定了这个月将围绕一个主题进行学习数据流、代价敏感、分类；基于这个主题，可以预想到的工作有：
- 研究现有的数据流data-stream中的classification；研究现有的cost-sensitive classification；
- 将cost-sensitive应用于data stream classification中（设计算法）；
- 初期处理数据，改造实验平台（weka、MOA）进行试验；
- 小论文（EI）、毕业论文（中期、最终）；
现在的进展：
data stream classification&cost sensitive classification都有有了一点了解；- 决定classification使用
Decision tree进行；（在data stream和cost sensitive中Decision-tree都有前人进行过较深入的研究工作）- 遇到第一个问题：2012年TKDE中有文章指出
VFDT中使用的Hoeffding’s-bound不严格，而应改为使用McDiarmid’s-bound，针对这个自己很纠结，因为新提出的bound限定的n值更大，需要的训练instance更多，这对自己有什么影响吗？
- 需要更多的instance
- 或者，更换选择分裂属性的指标（可以使用Gini Index）
- 思考能否，重新描述“VFDT”中数学问题，并提出与McDiarmid’s-Bound并列的界限值（换个角度想），或者能否改进McDiarmid’s-Bound。
今天的进展：(2013/01/04)改进了[2]中针对Infomation-gain提出的McDiarmid’s-bound，将其值降低了18倍，但仍然不可用。如果能够再降低10倍，与“VFDT”中bound结果逼近，则可以在实际试验中使用参数info-gain。
目标：改进[2]中针对Infomation-gain提出的McDiarmid’s-bound
具体：重新审视McDiarmid’s_inequality，参考[1]中Hoeffding’s_inequality是一个特列。参考[3]中（Definition 1）empirical-entropy和entropy-norm之间关系，结合[2]中原始的McDiarmid’s bound重新计算info-gain的bound。
下一步打算：继续改进Infomation-gain提出的McDiarmid’s-bound，具体可以从[3][4]中获得想法（改进思路：决策树分裂属性的数学描述、信息增益的原始计算公式、熵、McDiarmid’s-inequality）。（目标：最终可用）
参考文献
- ashish-mcdiarmid.pdf
- Decision trees for mining data streams based on the McDiarmid’s bound.pdf
- A Near-Optimal Algorithm for Computing the Entropy of a Stream.pdf
- Extensions to McDiarmid’s inequality when differences are bounded with high probability.pdf
结束语
问：世间此山最高？或者另有高处？
答：世间自有他山高此山，Open-mind比天高。
原文地址：https://ningg.top/summary-of-20130103/