IMPROVING THE EFFICIENCY OF GRAPH-BASED DATA MINING WITH APPLICATION TO PUBLIC HEALTH DATA
Yan Zhang · 2007
by Yan Zhang, M.S. Washington State University December 2007 Chair: Lawrence B. Holder Relational data are most naturally represented as a graph, with the entities as nodes and the relations between them as edges. Graph-based data mining looks for patterns that can best compress and represent the dataset and thus extract useful information from the data. An important topic in graph-based relational learning is its efficiency. A suitable search algorithm can largely improve the efficiency of substructure mining by finding better patterns in less time. In the thesis, performance of different search algorithms for graph-based relational pattern learning is studied. A complete graph space search algorithm, an efficient depth-limited search, and heuristic searches including beam search, hill climbing, stochastic hill-climbing, and simulated annealing (SA) are designed and implemented for pattern search in graph-based space. We also designed two new algorithms, SA-Greedy and Hill-Climbing with Stochastic Escape (HCSE). All seven algorithms are evaluated and compared by running with several depth limits on several datasets with Subdue, a graph-based data mining tool. The experimental results show that SA-Greedy finds best substructures in less time than the other search algorithms.