|
Analysis of the generalization ability of a full decision tree
I. E. Genrikhov Moscow State Pedagogical University, Malaya Pirogovskaya ul. 1, Moscow, 119991, Russia
Abstract:
Classification algorithms based on full decision trees are investigated. Due to the decision tree construction under consideration, all the features satisfying a branching criterion are taken into account at each special vertex. The generalization ability of a full decision tree is estimated by applying margin theory. It is shown on real-life problems that the construction of a full decision tree leads to an increase in the margins of the learning objects; moreover, the number of objects with a positive margin increases as well. It is shown that the empirical Rademacher complexity of a full decision tree is lower than that of a classical decision tree.
Key words:
precedent-based pattern recognition problem, full decision tree, margin, Rademacher complexity, iterative scheme.
Received: 01.08.2013
Citation:
I. E. Genrikhov, “Analysis of the generalization ability of a full decision tree”, Zh. Vychisl. Mat. Mat. Fiz., 54:6 (2014), 1033–1047; Comput. Math. Math. Phys., 54:6 (2014), 1046–1059
Linking options:
https://www.mathnet.ru/eng/zvmmf10056 https://www.mathnet.ru/eng/zvmmf/v54/i6/p1033
|
|