Research on Algorithm of Tree Stream Classification Based on k-best Tree Pattern
Liming Wang · Journal of Chinese Computer Systems · 2013
The most existing methods to classify structured data are based on frequent substructure mining,then through the step of ordering and pruning frequent sub-structure,get structural rules which are correlated with corresponding class values.This paper proposes TSC,an effective algorithm for classifying tree stream based on significant tree pattern.First of all,this method uses correlation measures to find k most discriminative tree patterns correlating with the class values.During this process,TSC uses branch and bound technology to improve the search efficiency without mining the complete frequent patterns,on the other hand,updates the threshold to avoid the post-prune step,and allows classifying directly using the tree patterns.Meanwhile,compared to existing methods,TSC is a no heuristic algorithm and only need to choose the maximum size of the rule set.Then,TSC uses classical adwin method to deal with local concept drift in evolving tree stream.The experimental results demonstrate that compared with the previous methods,TSC is sample and efficient which generates less effective rules to reduce the testing time greatly,and fulfills less total running time with higher predictive accuracy rate.