| As one of the most important algorithm of classification, decision tree is being widely adopted in many fields for its advantages of convenience for getting apparent rules, smaller calculation workload and higher classification correctness. ID3 algorithm is one of the most important algorithm in decision tree, the essential idea is:Forming a decision tree and acquiring classification rules by choosing the attribute with largest information gain as test attribute to divide sample data set on every decision tree's nodes.Based on introduce common algorithms of classification, the thesis discusses the basic ideas of some important algorithms of decision tree, and analyses the shortcoming of ID3 algorithm such as: over-fitting, multi-value bias etc. The research work of this thesis mainly focuses on:(1)Reform the formula of information entropy by using logarithm character, and propose a method of decreasing workload of logarithm calculation by storing limited logarithm values in array. The effectiveness of this method has been proved by simulation test.(2)Discuss the over-fitting problem caused by absence of important attribute and analyse it's influence to accuracy of classification. Create the notion of pre-test prediction accuracy rate, and select the best one by experiment as the model of classification evaluation from three hypothetic mathematic model between Pre-test Prediction Accuracy Rate and information gain, and provide a method to solve the over-fitting problem caused by absence of important attribute.(3)Apply ID3 algorithm into stock analysis. Establish classification model based on the comparison of changing rate of single stock future income and changing rate of stock market by choosing the attributes which could reflect the basic finance information of a stock. Validate the effectiveness of the classification model by experimenting in weka, an open-source software in data mining. Finally distill the common rules acquired by ID3 and C4. 5 algorithm as final conclusion. |
