Stability and scalability in decision trees

Tree-based methods are statistical procedures for automatic learning from data, whose main applications are integrated into a data-mining environment for decision support systems. Here, we focus on two problems of decision trees: the stability of the rules obtained and their applicability to huge data sets. Since the tree-growing process is highly dependent on data, i.e. small fluctuations in data can cause big changes in the tree-growing process, we focused instead on the stability of the trees themselves. To this end we propose a series of data diagnostics to prevent internal instability in the tree-growing process before a particular split is made. Indeed, to be effective in actual managerial problems they must be applicable to massive amounts of stored data with maximum efficiency. For this reason we studied the theoretical complexity of such an algorithm. Finally, we present an algorithm that can cope with such problems, with linear cost upon the individuals, which can use a robust impurity measure as a splitting criterion.