Use of Decision Trees in Preventing Car Accidents

Introduction:

Juan de Oña, Griselda López, and Joaquín Abellán’s article Extracting Decision Rules from Police Accident Reports through Decision Trees explores the use of decision trees to identify the main factors that contribute to the severity of road accidents. The authors’ goal is to find ways to extract decision rules from the decision tree methodology that can be used by road safety analysts to address specific problems that contribute to severe car accidents in order to prevent crashes and in turn fatalities.  

Summary:

According to de Oña et al. (2013), “the term decision trees (DTs) encompasses a series of techniques for extracting processable knowledge, implicit in databases, which is based on artificial intelligence and statistical analysis” (p. 1151). DTs are easy to interpret given their presentation as a graphical hierarchal structure. DTs are particularly useful in studying traffic accidents because the technique allows for the extraction of decision rules of the “if-then” type and also helps observers to understand the events leading up to a crash and the variables that determine the severity of the accident.

The authors seek results that can be used for predictive purposed by assessing different algorithms used to build DTs including Classification and Regression Trees (CART), ID3, and C4.5 and taking the results from the best method. Their assessment is based on four quantifiable evaluations: accuracy, sensitivity, specificity, and receiver operating characteristic curve area. They transform the DT structure into if-then or X→Y rules where X is a set of statuses of several attribute variables, such as accident type and atmospheric condition, and Y is the status of the class variable, or the severity of the accident. The authors consider 19 attribute variables related to the driver, road, vehicle, and context, along with two class variables, slightly injured (SI), and killed or seriously injured (KSI).

Figure 1: Example of top nodes of decision tree built with CART.  This model combines the results for the variables Female and Unknown for simplicity.

  

The authors assess that ID3 gives the worst results, while the difference in quality between results from CART and C4.5 is insignificant. For this reason, the authors pinpoint decision rules resulting from the latter two methods. The two models produced significantly different quantities of nodes, 19 and 52 respectively. Through these nodes, the authors identify a combined total of 15 decision rules that meet minimum standards in terms of population, support, and probability. Furthermore, the authors identify the importance of variables in each model, in which 11 incidences of importance overlap between the two models.

Figure 2: Example of same variables in top nodes of decision tree built with C4.5. This model creates individual nodes for each variable, regardless of significance.

Conclusion and Critique:

The use of decision trees, particularly different models of decision trees, allows researchers to identify patterns in the accidents that occurred in Granada, Spain over a 7-year period and determine interactions of variables. Authorities can use these results to prioritize efforts to prevent severe crashes, especially given that most of the rules extracted from the DTs coincide with conventional problems found in the rural highways of developed countries. Specifically, the authors advise experts to address the question of why women, as opposed to men, significantly increase their risk of severity under driving conditions with insufficient light.  

While I agree that the decision rules can be used by authorities, I feel that the authors under-emphasize the utility of doing so. Despite having statistical data to support their findings, the authors did not attempt to estimate the number of  severe accidents that could be prevented or the number of variables that could feasibly be addressed by road safety experts. Additionally, the authors explain how the different models of DTs allow for pruning to present simple results, however, they do not address the process or explain why they prune their decision trees the way they do. This would be a valuable addition to the research, particularly for those readers with little familiarity with the methodology.

The methodology on a whole is useful for this type of research, supporting evidence of several factors known to contribute to accident severity as identified in previous studies. The various models of DTs allows for appropriate application to various situations, though it is important that researchers assess which is most appropriate for their research before drawing conclusions from the resulting decision rules. 

Source:

De Oña, J., López, G., and Abellán J. (2013). Extracting Decision Rules from Police Accident Reports through Decision Trees. Accident Analysis & Prevention, 50(2013), 1151-1160. Retrieved from http://www.sciencedirect.com/science/article/pii/S0001457512003132

Using Decision Tree Analysis to Identify Risk Factors for Relapse to Smoking

Introduction

In this study, authors Megan E. Piper, Wei-Yin Loh, Stevens S. Smith, Sandra J. Japuntich, and Timothy B. Baker used decision tree analysis to identify how variables linked to relapse of smoking interact with each other.  The researchers then used this information to identify subgroups of smokers at a higher risk for relapse, and compared the results to those found through traditional methods.

Summary

Researchers conducted the study by inserting 70 variables with a connection to relapse in smoking, such as predictors related to environmental factors, dependence, and smoking history, into a decision tree model. This model is designed to take into account the effects of multiple factors. The more traditional model, logistic regression analysis, is a good predictor of factors influential to large groups and was used in addition to decision trees in order to create a comparison between the methods. Previous studies that depended solely on linear or logistic regression techniques were unable to identify smaller subgroups.  Decision tree analysis allowed researchers to divide the data sets in order to look at the effects of certain factors on specific groups, such as men and women. 

This study used the GUIDE decision tree program to analyze results from 1,071 smokers.  The researchers designed models for one week after quitting, end of treatment, and six months postquit. The figure below shows the “pruned” decision tree of the question “How soon after you wake up do you smoke your first cigarette?” From the results of this question, taken one week postquit, the decision tree splits further to show the abstinence rates of smokers who did or did not receive treatment, and those who are or are not married. The study showed that people who smoke their first cigarette more than 30 minutes after waking are the most likely to quit smoking, and that it is important to give treatment to those whose first cigarette is less than 30 minutes after waking up.

The second figure shows how marital status, gender, and the age began daily smoking interacted to affect abstinence at the end of treatment. Household income, health status, and longest previous quit attempt were also significant factors identified to influence successful cessation of smoking. The results showed that it is important to consider environmental and contextual factors in addition to those related to dependence.

Although both the decision tree analysis and logistic regression technique used the same data, they produced significantly different results. According to the authors, the decision tree model was better suited to handling a large number of factors; however, they were not able to determine which method is more accurate.  Overall, decision tree analysis produced statistically significant results that will hopefully be replicated in subsequent studies.

Conclusion

This study is a very good example of how decision tree analysis can be applied in real world situations to predict human behavior. One important characteristic of decision trees is that although they are based on scientific calculations, they are easy to understand and could be shown to decision makers to help explain the results of the analysis.  Although this case study uses quantitative data, it would be interesting to see how decision trees can be translated for use with qualitative data more commonly used for intelligence analysis.

Source

Piper, M.E., Wei-Yin, L., Stevens, S.S., Japuntich, S.J., Baker, T.B. (2011). Using decision tree analysis to identify risk factors for relapse to smoking. Substance Use & Misuse 46, p. 492-510. doi: 10.3109/10826081003682222

Decision Trees in Intelligence Analysis

Introduction:

Written during the Cold War, Edwin Sapp’s article on decision trees begins by noting the large amount of information available to intelligence analysts, the sophistication and seriousness of the weapons available, and ever-shortening time span in which effective decisions must be made. Sapp advocates the decision tree as a competent method for processing large amounts of data, while at the same time communicating degrees of certainty to an extent which language cannot.

Summary:

Edwin Greenlaw Sapp begins his article entitled Decision Trees by discussing the nature of intelligence analysis. He identifies four major categories that intelligence requirements fall into:

1) places (geographic locations, physical resources);

2) people (strengths and attitudes);

3) organizations (what people form and belong to); and

4) objects (things people make and possess; cities and weapons systems

Information is collected in these categories in order to make forecasts about futures states of affair. In Sapp’s view, Kent’s words of estimative probability are both vague and incomplete. He finds the decision tree more favorable, as it serves to “organize sizeable amounts of data…and communicate the degree of certainty relating to possible outcomes or the likelihood of the occurrence of specific events at some given time in the future.”

Sapp goes on to explain the technique used to create decision trees with two examples. His first is a simplistic question displaying the use of probabilities and subjective value of the outcomes to determine whether or not to hold a dinner party outside given a 40 percent chance of rain. The second example uses the Biblical story of the spies sent into Canaan. Sapp illustrates the intelligence cycle and how a decision tree would have aided this cycle by linking all the collection requirements and ensuring that the important questions were answered first.

According to Sapp there are two types of decision trees: deterministic and probabilistic. Deterministic decision trees deal with situations where no probability needs to be calculated in order to solve the problem on hand. The other use for decision trees is probabilistic, allowing for the forecasting of future events with a measured degree of certainty. Sapp also believes this type of decision tree allows the analyst to communicate more clearly to the decision maker, in that it provides solid numbers instead of seemingly vague language. The article goes on to address the difficulty of including all alternatives within a decision tree that is seeking to forecast the future. While one can never be certain that all possibilities are addressed within a probabilistic decision tree, Sapp notes that it is a simple process to return to the original model and update it should any unplanned alternatives arise.

Critique:

Can decision trees really handle the large amounts of data that Sapp claims?

How accurate can assigning probabilities be when such probabilities are related to intelligence problems?

Source:

Sapp, E. G. (1974, Winter). Decision Trees. Intelligence Studies, pp. 45-57 (declassified).

Summary of Findings: Decision Trees (3 out of 5 stars)

Definition:
A visual representation exploring all possible courses of action and the resulting consequences to aid in the decision making process. Decision trees are comprised of nodes (decisions/consequences), branches (links between nodes), and probabilities. The resulting form resembles a tree.

How to:

1. Begin from the top or the left-hand side as outcomes may flow from either left-to-right, or from top-to-bottom.
2. Define the problem/original decision visually represent this by using a rectangle (or box) around the decision to be made. This original decision is referred to as the "decision node."
3. Identify all possible courses of action that stem from that decision. The courses of action must be mutually exclusive and exhaustive. Each course of action should have a "branch" stemming out from the decision node.
4. Identify "chance nodes" (represented with circles) that represent the possible outcomes of the courses of action. Different outcomes should stem out from this chance node.
5. Sometimes branches emanating from decision and chance nodes can lead to other decision nodes - repeat steps 2 & 3 if this occurs, this will effectively “overgrow” the tree.
6. Indicate the associated probability (likelihood) that a particular outcome stemming from a chance node will occur. Probabilities are quantified with a value ranging from zero to 1. Therefore a probability of 0.6 would be the equivalent of a 60% chance. Use your experience and knowledge, as well as any conclusions from literature or other supporting data to assign a probability value.
7. The sum of the probabilities of all outcome branches stemming from a single chance node must equal 1.
8. When final consequences are identified, use a filled-in circle to represent that consequence.
9. Start “pruning” the decision tree by eliminating leaves and branches that are not (or are less) probabilistic.
   

Strengths:

• Structured, allowing for transparent recognition and interpretation of the constructed model
• Visual representation – good tool for presenters and audiences
• Provides an audit trail for the decision maker
• Applicable to multiple disciplines
• Produces quantifiable estimates
• More organized than a mind map
  

Weaknesses:

• High volume of quantitative data requires high level of mathematics capability
• Risky when choosing the "correct" variable to subdivide data
• Susceptible to "blind spots"
• Assigning probabilities may entail guesswork
• Susceptible to bias
  

Experience:
In order to get a feel for decision tree analysis, the group, while sitting in the bar across from the intel building, decided to conduct a decision tree analysis on whether or not we should do a decision tree experience exercise. This was the general consensus of decision tree analysis based on that exercise.

• It was difficult to assign probabilities without prior data that specifies what the likelihood is
  
• It is subjective and open to analysts' bias
• Can get messy if using pen and paper
• Open to wild cards and cognitive blindspots
• Does make the analyst think through the decisions and think outside of the box
• The visual representation makes the choices and consequences clear
• It does produce an estimation
  

Risk Based Methodology For Scenario Tracking, Intelligence Gathering, and Analysis For Countering Terrorism

Horowitz, Barry M. and Haimes, Yacov Y.. Systems Engineering, Vol. 6, No. 3, 2003, p. 152-169, 17 p.

Summary:
The authors of the paper apply a variety of methods to the problem of countering terrorism. One of the methods they apply is the use of Multiple-Objective Decision Trees (MODT). The use of MODT allows the intelligence community to make informed decisions under conditions of uncertainty. The authors propose using the method as the final step in a process that utilizes other methodologies, such as Bayesian analysis. "Finally, a decision-making mechanism is needed that can utilize the added knowledge derived from newly-discovered intelligence and make use of Bayesian analysis. In particular, the noncommensurate objectives—effort (cost and time) and risk—must be addressed in the multiobjective tradeoff analysis. Follow-up actions could vary from calling for special new information, to calling in experts to further evaluate the data, to initiating interception of the anticipated terrorist activity."

The authors state that the problem with traditional decision trees as applied to intelligence analysis is that the problem of the intelligence analyst is often too broad to be effectively represented by a decision tree. "In particular, an optimum derived from a single-
objective mathematical model, including that derived from a decision tree, often may be far from
representing reality, and thereby may mislead analysts as well as decision-makers." Instead, the authors propose MODTs as a effective methodology to assess decision making when their are multiple objectives, such as countering terrorism (thwart a plot, interdict the terrorists, dismantle their finances, kill the terrorists, etc.). Through the use of the MODT, decision makers and analysts begin with all objectives formulated, and then make trade-offs based on which set of decisions is most desirable for the given situation.

Comment: This paper further demonstrates the mathematical equations of MODT as opposed to traditional single objective decision trees. I did not include the equations in this summary, please see the article for the mathematics behind the methodology, as well as introductions to other methodologies that the authors propose to better your counterterrorism analysis.

Decision Tree Analysis

Vanguard Software Corporation

Summary:
"Decision trees are used to select the best course of action in situations where you face uncertainty." Decision tree analysis allows the analyst to find the best solution to a problem, or come to an estimation, although he lacks some information.
As an example of such a situation, the site outlines a simple game. How much would you pay to bet on the outcome of a coin toss ? If the coin comes up heads, you win $100. If it comes up tails, you lose. The game would look like this:

From a business perspective, you choose the option with the highest Expected Monetary Value, or EMV. The EMV of this game is $50, due to the probabilistic value of the game, i.e. you would statistically win 50% of the time. The formula for the EMV is :

To complicate the decision, another layer is added. Suppose your friend offers you $40 not to play the game. What should you do?

Now we have our decision tree. The square represents the decision (to play or not to play), whereas the circle represents the event, or outcome. Through decision tree analysis, you would come to the conclusion that it would be worth it for you to play, as you would statistically win at least $50.
But what if you had to pay $40 to play? That would look something like this:

This decision tree now takes into account your net loss or gain for playing the game. As you can see, it would still pay to play, however you can only expect to profit $10 rather than $50. By using decision tree analysis, we can outline all the various outcomes of a set of decisions, and then choose which decision is the most desirable.

Comment: This site is for decision tree software, DecisionPro, which calculates decisions automatically using various formulas for economic data. Although the example was developed for the business model of decision tree analysis, the same principles can be applied to intelligence analysis in order to "reduce uncertainty for the decision maker."

Countering Terrorism: Integration of Practice and Theory

Countering Terrorism: Integration of Practice and Theory
An Invitational Conference
FBI Academy, Quantico, VA
Feb 28, 2002
Sponsored by the FBI Behavioral Science Unit

Summary:

The FBI's Behavioral Science Unit identifies decision tree techniques and data mining as "highly efficient methods for processing large volumes of data." However, they add that they need to be "tailored to the unique cultures in which they would be used," and that their use depends on a cooperative effort by those that design such methods with those who have to analyze them. The decision tree decision-making methodology is recognized by the FBI as one method to standardize responses to threats and to understand the seriousness of those threats.

After collaboration efforts to receive and organize incoming information have been established with a technical advisor and a decision tree has been created, using the decision tree can be broadly applied due to it's low technical skill demands. The FBI also adds that decision trees should serve only to report information to a decision maker, reinforcing the idea that decision trees should be suggestive - not to actually state the decision to be made.

Appendix 6 gives the most useful information regarding decision tree analysis. In this appendix, it defines decision trees as a tool to aid decision making. "The idea is to concretely identify the choice points and map the sequence of decisions from beginning to end."

Steps:

1. Started with a decision that must be made - the FBI uses the example of whether or not to arrest a suspect. Represent this decision with a square. This should be drawn on the left-most side of the paper/screen.
   
2. Using lines drawn outward and to the right, identify each possible solution. Write each solution on each line.
3. At the end of each line, the results are considered. Use a circle is drawn at the end of the line to identify if choices are available
   
4. If another decision is possible, draw a square with that decision listed.
   
5. If there is a final consequence, a solid dot is drawn with a filled-in circle at its end.

Evaluating the decisions:

The FBI identifies the procedure for choosing a decision as backward induction analysis. In order to do this first assign a number that represents the worth or utility of the final consequence (filled-in circle). Use a 0.0 to 1.0 scale to identify worth. Next, assign a sum to each event node (the circles) that represents the expected utility of the node - this is the weighted average utility for that event node. "Finally, each decision node is a assigned a number that is the maximum value of the nodes that branch out from it."

According to the Behavioral Science Unit the benefits of using decision tree analyses are: 1) that the possible choices are explicitly made; 2) the choices are evaluated by the importance of the outcome as well as quantified with the probability for that outcome; and, 3) displays communication flow.
The FBI, once again, states that "decision trees can be used to guide decisions, not make them. The final decision is left up to the operator."

Decision Tree Analysis: Drawing Some of the Uncertainty Out of Decision Making

Decision Tree Analysis: Drawing Some of the Uncertainty Out of Decision Making
by William E. Marsh, PhD

Summary:

This article was written primarily to describe the benefits and how-to's of using decision trees (which Marsh commonly refers to as 'decision analysis') to make decisions in the livestock business - particularly swine veterinary practice. Although Marsh's target audience is obviously for those who either own swines or practice medicine on them, his article draws out the basics information needed to conduct a decision tree analysis; and he does so in a easy-to-understand and practical manner. For the purposes of this blog post, and out of respect of my targeted audience, I will leave out all swine references, examples, and jokes.

Marsh essentially defines a decision tree as a visual representation that logically depicts a time-sequenced flow of events with the purpose of informing a decision maker with the probability of various outcomes. It is a structured approach to making decisions when uncertainty exists that helps us to quantify and "consider the effects of chance on the outcome of a given decision." Marsh bluntly states that, "In using decision analysis, it is important to understand that the objective is not to make a prediction...[but rather, it] uses probabilities...to provide a guide for what should be done."

Steps to conducting a decision tree analysis:

1. Define the problem - what is it that we are trying to make a decision about. This will be represented visually using a rectangle (or box) around the decision to be made. Marsh refers to this as the "decision node."
   
2. Identify a "mutually exclusive, exhaustive list of all possible courses of action to address the problem." Each course of action should have a "branch" stemming out from the decision node.
   
3. Create a "chance node" (represented with circles) that represent the possible outcomes of a course of action. Different outcomes should stem out from this chance node.
4. Sometimes branches emanating from decision and chance nodes can lead to other decision nodes - repeat steps 2 & 3 if this occurs.
5. Indicate the associated probability (likelihood) that a particular outcome stemming from a chance node will occur. Probabilities are quantified with a value ranging from zero to 1. Therefore a probability of 0.6 would be the equivalent of a 60% chance. Use your experience and knowledge, as well as any conclusions from literature or other supporting data to assign a probability value.
   
6. The sum of the probabilities of all outcome branches stemming from a single chance node must equal 1.

Marsh does not clearly identify any cons to conducting a decision tree analysis, however, it is quite obvious that he is a strong proponent of using this technique to strengthen the decisions he makes.