# Improvement of ID3 Algorithm Based on Simplified Information Entropy and Coordination Degree
## 2 ID3 Algorithm Description  
ID3 algorithm, the traditional decision tree classification algorithm, was presented by [PERSON] [31] in 1986. ID3 makes use of information gain as an attribute selection method. The main structure of building a decision tree based on ID3 algorithm is summarized in Algorithm 1.  
Let us introduce some notations. Information entropy and information gain are defined by:  
\[Ent(D)=-\sum_{d=1}^{|\kappa|}p_{k}\text{log}_{2}p_{k}, \tag{1}\]  
\[Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{\left|D^{V}\right|}{\left|D\right|},Ent(D^{ V}) \tag{2}\]  
where \(D=\{(x_{1},y_{1}),\,(x_{2},y_{2}),\cdots,(x_{m},\,y_{m})\}\) stands for the training sample set, and \(\left|D\right|\) represents the number of training samples. \(A=\{a_{1},\,a_{2},\cdots,a_{d}\}\) denotes the attribute set of \(\left|D\right|\), and \(d=\{1,\,2,\cdots,\left|\kappa\right|\}\). \(p_{k}(k=1,\,2,\cdots,\left|D\right|)\) stands for the probability that a tuple in the training set \(S\) belongs to class \(Ci\). A homogenous data set consists of only one class. In a homogenous data set, \(p_{k}\) is \(1\), and \(log_{2}(p_{k})\) is zero. Hence, the entropy of a homogenous data set is zero. Assuming that there are \(V\) different values (\(V=\{a^{1},\,a^{2},\cdots,a^{V}\}\)) in an attribute \(a_{i}\), \(D^{i}\) represents sample subsets of every value, and \(\left|D^{i}\right|\) represents the number of current samples.  
The decision tree model, a tree chart depicted in Figure 1, can be acquired with the ID3 method described in Algorithm 1, and the decision tree model generally includes one root node, a number of internal nodes and some leaf nodes, where the root node represents the whole sample set, an internal node represents an attribute, and a leaf node represents a class label. The path from root node to every leaf node corresponds to a determine sequence.  
There are many advantages [32] to classify a mass of data by using the ID3 algorithm, such as strong intuitive nature, easy decomposability and so on, but the ID3 algorithm also has some disadvantages, for example:  
1. When using the information gain as attribute selection method, ID3 tends to choose the attribute that has more values [33] because the value of the information gain equation of this type of attribution will be larger than that of others.
2. As is known to all, if the logarithmic expression and the four arithmetic operations are the two equivalent expressions of one function, the running time of the four arithmetic operations is faster than that of the logarithmic expression [34]. In the ID3 method, there are many logarithmic computations in the optimal attribution selection process, which will waste much time to calculate the information gain. If the logarithmic expression is changed by the four arithmetic operations, the running time in the whole building tree process will improve rapidly.
3. It is hard to control the tree size in the process of building a decision tree. At present, most improved methods take pruning methods [35] to avoid over-fitting phenomena, which will lead to the whole process of building decision tree models finished in two steps (i.e., modeling and pruning). If a concise decision tree is built in one step, this will save much time.  
The intent of the paper is to solve the drawbacks that are mentioned above and propose an improved method to build the decision tree model. The improved ID3 algorithm is designed to generate a more concise decision tree model in a shorter time, and to choose a more reasonable optimal attribute in every internal node.