# Improvement of ID3 Algorithm Based on Simplified Information Entropy and Coordination Degree
## Improved ID3 Algorithm
### The Solution of Simplification of Information Gain  
#### 3.1.1 The Derivation Process of Simplifying Information Entropy  
The choice of the optimal attribute in ID3 algorithm is based on Equation (2), but the logarithm algorithm increases the complexity of the calculation. If we can find a simpler computing formula, \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Number** & **Colour** & **Body Shape** & **Hair Type** & **Characteristic** \\ \hline
1 & black & big & poodle & danger \\
2 & brown & big & smooth & danger \\
3 & brown & medium & poodle & safe \\
4 & black & small & poodle & safe \\
5 & brown & medium & smooth & danger \\
6 & black & big & smooth & danger \\
7 & brown & small & poodle & danger \\
8 & brown & small & smooth & safe \\
9 & brown & big & poodle & danger \\
10 & black & medium & poodle & safe \\
11 & black & medium & smooth & safe \\
12 & black & small & smooth & safe \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The data sample that determines the risk of dogs. Figure 1: The tree chart of a decision tree. the speed of building a decision tree would be faster. The process of simplification is organized as follows:  
As is known to all, in two equivalent expressions, the running speed of the logarithmic expression is slower than that of the four arithmetic operations. If the logarithmic expression in Equation (2) is replaced by the four arithmetic operation, the running speed of the whole process to build the decision tree will improve rapidly. According to the differentiation theory in advanced mathematics, the meaning of Taylor formula can simplify complex functions. The Taylor formula is an expanded form at any point, and the Maclaurin formula is a function that can be expanded into [PERSON]'s series at point zero. The difficulty in computation of the information entropy about the ID3 algorithm can be reduced based on an approximation formula of Maclaurin formula, which is helpful to build a decision tree in a short period of time. The Taylor formula is given by:  
\[f(x)=f(x_{0})+f^{(1)}(x_{0})(x-x_{0})+o(x-x_{0}). \tag{3}\]  
Under circumstances of \(x\) = 0, Equation (3) is changed into the following form (also called Maclaurin formula):  
\[f(x)=f(0)+f^{(1)}(0)x+\frac{f^{(2)}(0)}{2!}x^{2}+,\cdots,+\frac{f^{(n)}(0)}{n! }x^{n}+R(x), \tag{4}\]  
where  
\[R(x)=\frac{f^{(n+1)}(x)}{(n+1)!}(x-x_{0})^{n+1}. \tag{5}\]  
For easy calculation, the final equation applied in this paper will be:  
\[f(x)=f(0)+f^{(1)}(0)x+\frac{f^{(2)}(0)}{2!}x^{2}+,\cdots,+\frac{f^{(n)}(0)}{n! }x^{n}. \tag{6}\]  
Assuming that there are \(n\) counter examples and \(p\) positive examples in sample set \(D\), the information entropy of \(D\) can be written as:  
\[Ent(D)=-\frac{p}{p+n}{\rm log}_{2}\frac{p}{p+n}-\frac{n}{p+n}{\rm log}_{2} \frac{n}{p+n}. \tag{7}\]  
Assuming that there are \(V\) different values included in the attribute \(a_{i}\) of \(D\), and every value contains \(n_{i}\) counter examples and \(p_{i}\) positive examples, the information gain of the attribute \(a_{i}\) can be written as:  
\[Gain(D,a_{i})=Ent(D)-\sum_{i=1}^{V}\frac{p_{i}+n_{i}}{p+n}Ent(D^{V}), \tag{8}\]  
where  
\[Ent(D^{V}) =-\frac{p_{i}}{p_{i}+n_{i}}{\rm log}_{2}\frac{p_{i}}{p_{i}+n_{i}} \tag{9}\] \[-\frac{n_{i}}{p_{i}+n_{i}}{\rm log}_{2}\frac{n_{i}}{p_{i}+n_{i}}.\]  
In the process of simplification, if the formula \(\ln(1+x)\approx x\) is true in the situation of very small variable \(x\) and the constant included in every step can be ignored based on Equation (6), Equation (7) can be rewritten as:  
Figure 1:0 Figure 1:1 Figure 1:2Similarly, the expression \(\sum\limits_{i=1}^{V}\frac{p_{i}+n_{i}}{p+n}Ent(D^{V})\) can be rewritten as:  
\[ \begin{split}&\sum\limits_{i=1}^{V}\frac{p_{i}+n_{i}}{p+n}Ent(D^{V}) \\ &=\sum\limits_{i=1}^{V}\frac{p_{i}+n_{i}}{(p+n)\ln 2}\left[\frac{p_{i}n_{i }}{(p_{i}+n_{i})^{2}}+\frac{n_{i}p_{i}}{(p_{i}+n_{i})^{2}}\right]\\ &=\sum\limits_{i=1}^{V}\frac{p_{i}+n_{i}}{(p+n)\ln 2}\cdot\frac{2p_{i}n _{i}}{(p_{i}+n_{i})^{2}}\\ &=\sum\limits_{i=1}^{V}\frac{2p_{i}n_{i}}{p_{i}+n_{i}}.\end{split}