Title:	DISCOVERY OF TREE STRUCTURED PATTERNS USING MARKOV CHAIN MONTE CARLO METHOD
Author(s):	Yasuhiro Okamoto, Kensuke Koyanagi, Takayoshi Shoudai, Osamu Maruyama
ISBN:	978-989-8704-04-7
Editors:	Philip Powell, Miguel Baptista Nunes and Pedro Isaías
Year:	2014
Edition:	Single
Keywords:	Knowledge discovery, tree-structured pattern, binary classification, probabilistic method, Markov chain Monte Carlo method, glycan structure data.
Type:	Full Paper
First Page:	95
Last Page:	102
Language:	English
Cover:
Full Contents:	click to dowload
Paper Abstract:	A tree contraction pattern (TC-pattern) is an unordered tree-structured pattern which can express a tree-structure common to given unordered trees. A TC-pattern has some special vertices, called contractible vertex, into which every uncommon connected substructure is merged by edge contractions. In this paper, we propose a probabilistic method for computing a binary classification problem on tree-structured data. Given a positive set P and a negative set N of unordered trees with vertex labels on a finite alphabet, the problem is to find meaningful and optimal TC-patterns that classify P and N with high statistical measures. We formalize this problem as a multiple optimization problem, and propose a probabilistic method for computing it by employing enumeration algorithms for TC-patterns and Markov chain Monte Carlo method. In addition, as a theoretical aspect of this problem, we show the hardness of approximability of it. Finally, we show the experimental results of our method on glycan structure data.
	Go Back