Substructure Discovery in SUBDUE

Abstract

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. 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1988
Accession Number
ADA197050

Entities

People

  • Lawrence B. Holder

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Autonomy
  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Computer Science
  • Artificial Intelligence
  • Computations
  • Computer Languages
  • Computer Science
  • Computer Vision
  • Computers
  • Data Compression
  • Demographic Cohorts
  • Illinois
  • Learning
  • Lisp Programming Language
  • Machine Learning
  • Test And Evaluation
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Neural Network Machine Learning.