The decision tree output of Quinlan's ID3 algorithm is one of its major weaknesses. Not only can it be incomprehensible and difficult to manipulate, but its use in expert systems frequently demands irrelevant information to be supplied. This report argues that the problem lies in the induction algorithm itself and can only be remedied by radically altering the underlying strategy. It describes a new algorithm, PRISM which, although based on ID3, uses a different induction strategy to induce rules which are modular, thus avoiding many of the problems associated with decision trees. Considerable effort has recently been devoted to the development of efficient knowledge acquisition techniques for expert systems, with rule induction algorithms coming under the scrutiny of a substantial number of researchers. Particular attention has been paid to Ross Quinlan's ID3 algorithm (Quinlan, 1979a (Quinlan, , 1979b (Quinlan, , 1983a which, having performed well in the domain of chess end-games, was soon adopted for use in a number of commercial applications. However, despite this apparent success, some major limitations to the ID3 algorithm have been identified (Bundy, Silver & Plummer, 1984; Cendrowska, 1984; Hart, 1985; O'Rorke, 1982) , which makes its use unsuitable for many domains. The algorithm's inability to deal with noisy input data is an area for much current research and new improved variants of ID3 are constantly being reported in the technical press (A-Razzak, Hassan & Pettipher, 1985; Hart, 1985; Lavrac et al. 1986; Michie, 1983; Quinlan, 1983b ), but concern has been shown about the way in which the results of the induction process are expressed. This report discusses the second of these two limitations. ID3 produces its output in the form of a decision tree, which can be incomprehensible (to humans), difficult to manipulate (by humans and computers) and complicates the provision of explanations (by computers for humans). In addressing this subject, it is argued that current research aimed at modifying the decision tree output of ID3 is misplaced, that the decision tree output is an inherent weakness in the algorithm itself and that this can only be remedied by radically altering the underlying induction strategy. The first part of this report explains the problem in more detail, highlighting it by means of a simple example which is introduced in Section 2. Section 3 describes how ID3 tackles the induction task using an information theoretic approach, and the inherent weaknesses of this approach are discussed in Section 4. The subsequent sections describe how the induction strategy can be changed to avoid some of these problems and outline a proposal for a new algorithm, PRISM which, although based 349
It is also argued in REF that the existence of replicated sub-trees could result in the need of a complete traversal of a decision tree in the worst case for extraction of rules about a single classification, leading to an increased difficulty in the manipulation of expert systems.
PRISM: an algorithm for inducing modular rules
Int J ManMachine Studies
Computer Science