A decision tree is a graph-like structure in which internal node represents a “test” on an attribute, each branch represents the outcome of the test and
each leaf node represents a class label.
The classification rules are formed by the path selected from the root node to the leaf. To divide each input data, first the root node is chosen as it is the
most prominent attribute to separate the data. The tree is constructed by identifying attributes and their associated values which will be used to analyze the input data at each intermediate node of the tree. After the tree is formed, it can prefigure newly coming data by traversing, starting from a root node to the leaf node visiting all the internal nodes in the path depending upon the test conditions of the attributes at each node. The main issue in constructing decision tree is, which value is chosen for splitting the node of the tree.
Decision trees can analyze data and identify significant characteristics in the network that indicate malicious activities. It can add value to many real-time security systems by analyzing large set of intrusion detection data. It
can recognize trends and patterns that support further investigation, the development of attack signatures, and other activities of monitoring. The main advantage of using decision trees instead of other classification techniques is that they provide a rich set of rules that are easy to understand, and can be effortlessly integrated with real-time
Advantages of Decision Trees
- Are simple to understand and interpret. People are able to understand decision tree models after a brief explanation.
- Have value even with little hard data. Important insights can be generated based on experts describing a situation (its alternatives, probabilities, and costs) and their preferences for outcomes.
- Help determine worst, best and expected values for different scenarios.
- Use a white box model. If a given result is provided by a model.
- Can be combined with other decision techniques.
Disadvantages of decision trees:
- They are unstable, meaning that a small change in the data can lead to a large change in the structure of the optimal decision tree.
- They are often relatively inaccurate. Many other predictors perform better with similar data. This can be remedied by replacing a single decision tree with a random forest of decision trees, but a random forest is not as easy to interpret as a single decision tree.
- For data including categorical variables with different number of levels, information gain in decision trees is biased in favor of those attributes with more levels.
- Calculations can get very complex, particularly if many values are uncertain and/or if many outcomes are linked.
Decision Tree Classification Example
Decision Tree Algorithm Decision Tree Algorithm – ID3
Decide which attribute (splitting ‐point) to test at node N by determining the “best” way to separate separate or partition partition the tuples in D into
The splitting splitting criteria criteria is determined determined so that,
ideally, the resulting partitions at each branch are as “pure ” as possible possible.
A partition is pure if all of the tuples in it belong to the same class.
What is Entropy?
The entropy is a measure of the uncertainty associated with a random variable. As uncertainty and or randomness increases for a result set so does the entropy. Values range from 0 – 1 to represent the entropy
Information gain is used as an attribute selection measure. Pick the attribute that has the highest Information Gain.
The attribute attribute age has the highest highest information information gain and therefore therefore becomes becomes the splitting attribute at the root node of the decision tree. Branches are grown for each outcome of age. The tuples are shown partitioned accordingly.
A decision tree for the concept buys_computer, indicating whether a customer at AllElectronics is likely to purchase a computer. Each internal (nonleaf) node represents a test on an attribute. Each leaf node represents a class ( either buys_computer = yes or buy_computers = no.