Query: Decision Tress Algorithms

Candidate papers:

abstract: The use of Decision Trees to analyze data is discussed as an approach to solving problems of Yield excursions in semiconductor manufacturing. The relation to equipment commonality is discussed along with some of the pitfalls of incautious use of general probability estimates. The paper introduces a Mixing Diagram to help visualize commonality issues, it introduces work around methods for resolving ambiguities in the commonality, it reviews Decision Trees algorithms, and it ends with a discussion of current limitations of the method along with recommendations for future research.
author_names: Peter Waksman
title: Isolating causes of yield excursions with decision tress and commonality
venue: SPIE Advanced Lithography
year: 2002

abstract: Work safety control and analysis of accidents during the construction performance are some of the most important issues of the construction management. The paper focuses on the post accident absence as an element of the occupational safety management. The occurrence of the post accident absence of workers can be then treated as an indicator of building performance safety. The ability to estimate its length can also facilitate works planning and scheduling in case of the accident. The paper attempts to answer the question whether it is possible and how to use decision trees and their ensembles to predict the severity of the post accident absence and which classification algorithm is the most promising to solve the prediction problem. The paper clarifies the model of the prediction problem, introduces 5 different decision tress and different aggregation algorithms in order to build the model. Thanks to the use of aggregation methods it is possible to build classifiers that predict precisely and do not require any initial data treatment, which simplifies the prediction process significantly. To identify the most promising classifier or classifier ensemble the prediction accuracy measures of selected classification algorithms were analyzed. The data to build the model was gathered on national (Polish) construction sites and was taken from literature. Models obtained within simulations can be used to build advisory or safety management systems allowing to detect threats while construction works are being planned or carried out.
author_names: Anna Krawczynska-Piechna
title: Predicting the Length of a Post Accident Absence in Construction with Decision Trees and Their Ensembles
year: 2020

abstract: We study the problem of finding a universal (image agnostic) perturbation to fool machine learning (ML) classifiers (e.g. neural nets, decision tress) in the hard label black box setting. Recent work in adversarial ML in the white box setting (model parameters are known) has shown that many state of the art image classifiers are vulnerable to universal adversarial perturbations: a fixed human imperceptible perturbation that, when added to any image, causes it to be misclassified with high probability Kurakin et al. [2016] Szegedy et al. [2013] Chen et al. [2017a] Carlini and Wagner [2017] This paper considers a more practical and challenging problem of finding such universal perturbations in an obscure (or black box) setting. More specifically, we use zeroth order optimization algorithms to find such a universal adversarial perturbation when no model information is revealed except that the attacker can make queries to probe the classifier. We further relax the assumption that the output of a query is continuous valued confidence scores for all the classes and consider the case where the output is a hard label decision. Surprisingly, we found that even in these extremely obscure regimes, state of the art ML classifiers can be fooled with a very high probability just by adding a single human imperceptible image perturbation to any natural image. The surprising existence of universal perturbations in a hard label black box setting raises serious security concerns with the existence of a universal noise vector that adversaries can possibly exploit to break a classifier on most natural images.
author_names: Thomas A Hogan

Bhavya Kailkhura
title: Universal Decision Based Black Box Perturbations: Breaking Security Through Obscurity Defenses
venue: ArXiv
year: 2018

abstract: Current state of the art decision tree algorithms, such as Classification and Regression Trees (CART) build the decision tree using a recursive approach based on a greedy heuristic. We study the benefits of an optimal decision tree approach, which creates the entire decision tree at once using Mixed Integer Optimization (MIO) While such problems are known to be hard to solve for large instances, we leverage modern solver techniques that are able to obtain near optimal solutions in a reasonable amount of time. The methodology is able to handle both single feature splits, as in CART, and also hyperplane splits that use multiple features. We test optimal regression trees on a host of synthetic datasets and optimal classification tress on a novel application concerning the usage of CT imagining to diagnose head injuries in children. Our results demonstrate that optimal trees lead to a significantly greater accuracy than CART.
author_names: Dimitris Bertsimas

Jack Dunn

Aris Paschalidis
title: Regression and classification using optimal decision trees
venue: 2017 IEEE MIT Undergraduate Research Technology Conference (URTC)
year: 2017

abstract: Cardiotocography is one of the most widely used technique for recording changes in fetal heart rate (FHR) and uterine contractions. Assessing cardiotocography is crucial in that it leads to iden tifying fetuses which suffer from lack of oxygen, i.e. hypoxia. This situation is defined as fetal dis tress and requires fetal intervention in order to prevent fetus death or other neurological disease caused by hypoxia. In this study a computer based approach for analyzing cardiotocogram in cluding diagnostic features for discriminating a pathologic fetus. In order to achieve this aim adaptive boosting ensemble of decision trees and various other machine learning algorithms are employed.
author_names: Esra Mahsereci Karabulut

Turgay Ibrikci
title: Analysis of Cardiotocogram Data for Fetal Distress Determination by Decision Tree Based Adaptive Boosting Approach
year: 2014

abstract: Classification is an important data mining task which facilitates list of decision rules that helps us to predict class of an unseen instance. Various traditional techniques like Decision tress, Neural Networks, SVMs have been used in past for rule mining. Nature Inspired Algorithms (NIAs) are class of algorithms that mimic natural processes and are capable of mining comprehensible and accurate rules. It is interesting to investigate Nature Inspired Algorithms (NIAs) exclusively GA and ACO, in context of rule mining. Classification model usually represents obvious information in form of decision rules and an unseen instance is liable to be misclassified if the model created using any of the above techniques do not account for exceptions present in the dataset. Instances having low support count and deviating from obvious behavior are termed as exceptions and they are less likely to be discovered using the usual rule discovery measures that account for generality of the discovered knowledge. In this paper we have investigated use of NIAs in rule mining and exception mining and we have also suggested possible modification in existing cAntMinerpb algorithm for mining exceptions.
author_names: Amarnath Pathak

Jyoti Vashistha
title: Classification Rule and Exception Mining Using Nature Inspired Algorithms
year: 2015

abstract: Decision tree learning is among the most popular machine learning techniques used for ecological modelling. Decision trees can be used to predict the value of one or several target (dependent) variables. They are hierarchical structures, where each internal node contains a test on an attribute, each branch corresponding to an outcome of the test, and each leaf node giving a prediction for the value of the class variable. Depending on whether we are dealing with a classification (discrete target) or a regression problem (continuous target) the decision tree is called a classification or a regression tree, respectively. The common way to induce decision trees is the so called Top Down Induction of Decision Tress (TDIDT) In this chapter, we introduce different types of decision trees, present basic algorithms to learn them, and give an overview of their applications in ecological modelling. The applications include modelling population dynamics and habitat suitability for different organisms (e.g. soil fauna, red deer, brown bears, bark beetles) in different ecosystems (e.g. aquatic, arable and forest ecosystems) exposed to different environmental pressures (e.g. agriculture, forestry, pollution, global warming)
author_names: Marko Debeljak

Saso Dzeroski
title: Decision Trees in Ecological Modelling
year: 2011

abstract: To find out the evidence of crime related evidence and association rules among massive data, the classic decision tree algorithms such as ID3 for classification analysis have appeared in related prototype systems. So how to make it more suitable for computer forensics in variable environments becomes a hot issue. When selecting classification attributes, ID3 relies on computation of information entropy. Then the attributes owning more value are selected as classification nodes of the decision tress. Such classification is unrealistic under many cases. During the process of ID3 algorithm there are too many logarithms, so it is complicated to handle with the dataset which has various classification attributes. Therefore, contraposing the special demand for computer crime forensics, ID3 algorithm is improved and a novel classification attribute selection method based on Maclaurin Priority Value First method is proposed. It adopts the foot changing formula and infinitesimal substitution to simplify the logarithms in ID3. For the errors generated in this process, an apposite constant is introduced to be multiplied by the simplified formulas for compensation. The idea of Priority Value First is introduced to solve the problems of value deviation. The performance of improved method is strictly proved in theory. Finally, the experiments verify that our scheme has advantage in computation time and classification accuracy, compared to ID3 and two existing algorithms
author_names: Y Wang

Xinguang Peng

Jing Bian
title: Computer Crime Forensics Based on Improved Decision Tree Algorithm
venue: J. Networks
year: 2014

abstract: Decision tress have long been popular in classification as they use simple and easy to understand tests at each node. Most variants of decision trees test a single attribute at a node, leading to axis parallel trees, where the test results in a hyperplane which is parallel to one of the dimensions in the attribute space. These trees can be rather large and inaccurate in cases where the concept to be learned is best approximated by oblique hyperplanes. In such cases, it may be more appropriate to use an oblique decision tree, where the decision at each node is a linear combination of the attributes. Oblique decision trees have not gained wide popularity in part due to the complexity of constructing good oblique splits and the tendency of existing splitting algorithms to get stuck in local minima. Several alternatives have been proposed to handle these problems including randomization in conjunction wiht deterministic hill climbing and the use of simulated annealing. In this paper, we use evolutionary algorithms (EAs) to determine the split. EAs are well suited for this problem because of their global search properties, their tolerance to noisy fitness evaluations, and their scalability to large dimensional search spaces. We demonstrate our technique on a synthetic data set, and then we apply it to a practical problem from astronomy, namely, the classification of galaxies with a bent double morphology. In addition, we describe our experiences with several split evaluation criteria. Our results suggest that, in some cases, the evolutionary approach is faster and more accurate than existing oblique decision tree algorithms. However, for our astronomical data, the accuracy is not significantly different than the axis parallel trees.
author_names: Erick Cantu-Paz

Chandrika Kamath
title: Combining evolutionary algorithms with oblique decision trees to detect bent double galaxies
venue: SPIE Optics Photonics
year: 2000

abstract: We address the problem of computing various types of expressive tests for decision tress and regression trees. Using expressive tests is promising, because it may improve the prediction accuracy of trees. The drawback is that computing an optimal test could be costly. We present a unified framework to approach this problem, and we revisit the design of efficient algorithms for computing important special cases. We also prove that it is intractable to compute an optimal conjunction or disjunction.
author_names: Shinichi Morishita
title: On Classification and Regression
venue: Discovery Science
year: 1998