Substructure Discovery in SUBDUE
Lawrence B. Holder · 1988
TERMS (Continu* on reverse if necessary and identify by block num ber)SUBDUE, best-first search, ABSTRACT (Continue on reverse if necessary and identify by block num ber)This paper describes the substructure discovery method used in the SUBDUE system.The method involves a computationally constrained best-first search guided by four heuristics: cognitive savings, compactness, connectivity and coverage.The two main processes contained in this method are substructure generation and substructure selection.Substructure generation is the process by which new substructures are generated from previously considered substructures.The second process, substructure selection, chooses the best substructure among alternative substructures according to the four heuristics.Each of the four heuristics are described along with their role in the evaluation of a substructure.After the generation and selection processes are described, the substructure discovery algorithm is presented.Two examples demonstrate SUBDUE's ability to discover substructure and the advantages to be gained by other learning systems from the discovery of substructure concepts. 20.