Mining Patterns from Structured Data by Beam-Wise Graph-Based Induction
Mining Patterns from Structured Data by Beam-Wise Graph-Based Induction
复制标题
通过基于 Beam-Wise 图的归纳从结构化数据中挖掘模式
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
T. Washio
中科院分区：
文献类型：
--
作者：
T. Matsuda;H. Motoda;Tetsuya Yoshida;T. Washio
一种称为基于图的归纳(GBI)的机器学习技术通过逐步对扩展(成对组块)从图形数据中提取典型模式。由于其贪婪的搜索策略，它的效率很高，但存在搜索不完全的问题。在不增加太多计算复杂度的情况下，通过1)结合波束搜索，2)使用不同的评价函数来提取比简单频繁出现的模式更具区分性的模式，以及3)采用规范标记来准确地列举相同的模式，从而在搜索能力上有所提高。这个新的算法，现在被称为波束式GBI，简称B-GBI，在来自UCI储存库的一个小DNA数据集上进行了测试，并被证明成功地提取了区分子结构。
A machine learning technique called Graph-Based Induction (GBI) extracts typical patterns from graph data by stepwise pair expansion (pairwise chunking). Because of its greedy search strategy, it is very efficient but suffers from incompleteness of search. Improvement is made on its search capability without imposing much computational complexity by 1) incorporating a beam search, 2) using a different evaluation function to extract patterns that are more discriminatory than those simply occurring frequently, and 3) adopting canonical labeling to enumerate identical patterns accurately. This new algorithm, now called Beam-wise GBI, B-GBI for short, was tested against a small DNA dataset from UCI repository and shown successful in extracting discriminatory substructures.