NingG +

1个月学习小结——代价敏感的数据流分类算法

最近几个月阅读论文都是“抄家底”的方式进行,即,认准一个作者,把他最近几年的论文看个遍,然后再看看自己有没有新的想法。

其中,第一个作者是西北农林科技的张阳教授,再一个就是针对cost-sensitive decision tree方向看了一些论文,值得说明的是找到一篇比较全面的综述,还是2011年左右的,不过这篇文章还没有详细去看。

Mountain-and-Sky-Twitter-Header

这一个多月内(从2012.10.12开题那一天算起),确定了这个月将围绕一个主题进行学习数据流、代价敏感、分类;基于这个主题,可以预想到的工作有:

  1. 研究现有的数据流data-stream中的classification;研究现有的cost-sensitive classification;
  2. 将cost-sensitive应用于data stream classification中(设计算法);
  3. 初期处理数据,改造实验平台(weka、MOA)进行试验;
  4. 小论文(EI)、毕业论文(中期、最终);

现在的进展:

  • data stream classification & cost sensitive classification都有有了一点了解;
  • 决定classification使用Decision tree进行;(在data streamcost sensitiveDecision-tree都有前人进行过较深入的研究工作)
  • 遇到第一个问题:2012年TKDE中有文章指出VFDT中使用的Hoeffding’s-bound不严格,而应改为使用McDiarmid’s-bound,针对这个自己很纠结,因为新提出的bound限定的n值更大,需要的训练instance更多,这对自己有什么影响吗?
  1. 需要更多的instance
  2. 或者,更换选择分裂属性的指标(可以使用Gini Index)
  3. 思考能否,重新描述“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)。(目标:最终可用)

参考文献

  1. ashish-mcdiarmid.pdf
  2. Decision trees for mining data streams based on the McDiarmid’s bound.pdf
  3. A Near-Optimal Algorithm for Computing the Entropy of a Stream.pdf
  4. Extensions to McDiarmid’s inequality when differences are bounded with high probability.pdf

结束语

问:世间此山最高?或者另有高处?

答:世间自有他山高此山,Open-mind比天高。

Top