HIERARCHICAL CONCEPTUAL CLUSTERING USING A 分层概念聚类.ppt

GRAPH-BASED HIERARCHICAL CONCEPTUAL CLUSTERING by Istvan Jonyer, Lawrence B. Holder and Diane J. Cook The University of Texas at Arlington Outline What is hierarchical conceptual clustering? Overview of Subdue Conceptual clustering in Subdue Evaluation of hierarchical clusterings Experiments and results Conclusions What is clustering? What is hierarchical conceptual clustering? Unsupervised concept learning Generating hierarchies to explain data Applications Hypothesis generation and testing Prediction based on groups Finding taxonomies Example hierarchical conceptual clustering The Problem Hierarchical conceptual clustering in discrete-valued structural databases Existing systems: Continuous-valued Discrete but unstructured We can do better! (Field under explored) Related Work Cobweb Labyrinth AutoClass Snob In Euclidian space: Chameleon, Cure Unsupervised learning algorithms The Solution Take Subdue and extend it! Overview of Subdue Data mining in graph representations of structural databases Overview of Subdue Iteratively searching for best substructure by MDL heuristic Overview of Subdue Compress using best substructure Overview of Subdue Fuzzy match Inexact matching of subgraphs Applications: Defining fuzzy concepts Evaluation of clusterings Conceptual Clustering with Subdue Use Subdue to identify clusters The best subgraph in an iteration defines a cluster When to stop within an iteration? Use –limit option Use –size option Use first minimum heuristic (new) The First Minimum Heuristic Use subgraph at first local minimum Detect it using –prune2 option The First Minimum Heuristic Not a greedy heuristic! Although first local minimum is usually the global minimum First local minimum is caused by a smaller, more frequently occurring subgraph Subsequent minima are caused by bigger, less frequently occurring subgraphs = First subgraph is more general The First Minimum Heuristic A multi-minimum search space: Lattice vs. Tree Previous work defined classifi