A new decision-tree classification algorithm for machine learning

Abstract

This paper presents a new decision-tree classification algorithm for machine learning. Although the decision-tree classification algorithms have been widely used as the machine learning theory in artificial intelligence, there has been little research toward evaluating the performance or quality of the current classification algorithms, and investigating the time and computational complexity of constructing the smallest size decision tree which best distinguishes characteristics of multiple distinct groups. We use a known NPcomplete problem, 3-exact cover, to prove that this problem is NP-complete. One prevalent classification algorithm in machine learning, ID3, is evaluated. The greedy search procedure used by ID3 is found to create anomalous behaviors with inferior decision trees on a lot of occasions. We also present a new decision-tree classification algorithm, intelligent decision-tree algorithm (IDA), that not only overcomes these anomalies with better classification performance but also is more computationally efficient than ID3. A time analysis shows that IDA is more computationally efficient than ID3 and a simulation study indicates that IDA has outperformed ID3.