A novel application of Hoeffding's inequality to decision trees construction for data streams

摘要: Decision trees are the commonly applied tools in task of data stream classification. The most critical point decision tree construction algorithm is choice splitting attribute. In majority algorithms existing literature criterion based on statistical bounds derived for split measure functions. this paper we propose a totally new kind criterion. We derive arguments function instead deriving it itself. This approach allows us to properly use Hoeffding's inequality obtain required bounds. Based theoretical results Trees Fractions Approximation (DTFA). exhibits satisfactory classification accuracy numerical experiments. It also compared with other methods, demonstrating noticeably better performance.