Parallel construction of decision trees with consistently non‐increasing expected number of tests
Irad Ben‐Gal, Chavazelet Trister · Applied Stochastic Models in Business and Industry · 2014
In recent years, with the emergence of big data and online Internet applications, the ability to classify huge amounts of objects in a short time has become extremely important. Such a challenge can be achieved by constructing decision trees (DTs) with a lowexpected number of tests(ENT). We address this challenge by proposing the ‘save favorable general optimal testing algorithm’ (SF‐GOTA) that guarantees, unlike conventional look‐ahead DT algorithms, the construction of DTs with monotonic non‐increasing ENT. The proposed algorithm has a lower complexity in comparison to conventional look‐ahead algorithms. It can utilize parallel processing to reduce the execution time when needed. Several numerical studies exemplify how the proposed SF‐GOTA generates efficient DTs faster than standard look‐ahead algorithms, while converging to a DT with a minimum ENT.