Optimized Substructure Discovery for Semi-structured Data
Lecture notes in computer sciencePublished 1 January 2002Open access
Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki Arimura, Setsuo Arikawa
Citations120
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An efficient algorithm is presented that discovers the best labeled ordered trees that optimize a given statistical measure, such as the information entropy and the classification accuracy, in a collection of semi-structured data.
Abstract
In this paper, we consider the problem of discovering interesting substructures from a large collection of semi-structured data in the framework of optimized pattern discovery. We model semi-structured data and patterns with labeled ordered trees, and present an efficient algorithm that discovers the best labeled ordered trees that optimize a given statistical measure, such as the information entropy and the classification accuracy, in a collection of semi-structured data. We give theoretical analyses of the computational complexity of the algorithm for patterns with bounded and unbounded size. Experiments show that the algorithm performs well and discovered interesting patterns on real datasets.
Keywords
Computer Science
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
Series on software engineering and knowledge engineeringData Structures and Algorithms
2,131 Citations2003
The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.
Machine LearningVery Simple Classification Rules Perform Well on Most Commonly Used Datasets
1,798 Citations1993Robert C. Holte
On most datasets studied, the best of very simple rules that classify examples on the basis of a single attribute is as accurate as the rules induced by the majority of machine learning systems.
Efficiently mining long patterns from databases
1,297 Citations1998Roberto J. Bayardo
A pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern, compared with previous algorithms that scale exponentially with longest pattern length.
Lecture notes in computer scienceAn Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
1,029 Citations2000Akihiro Inokuchi, Takashi Washio +1 more
A novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set through the extended algorithm of the basket analysis is proposed.
Efficiently mining frequent trees in a forest
467 Citations2002Mohammed J. Zaki
This work presents TREEMinER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list, and finds that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties.
Efficient Substructure Discovery from Large Semi-structured Data
363 Citations2002Tatsuya Asai, Kenji Abe +4 more
Toward efficient agnostic learning
347 Citations1992Michael Kearns, Robert E. Schapire +1 more
Data mining using two-dimensional optimized association rules
267 Citations1996Takeshi Fukuda, Yasukiko Morimoto +2 more
This work discusses data mining based on association rules for two numeric attributes and one Boolean attribute, which implies that bank customers whose ages and balances fall in a planar region P tend to use card loan with a high probability.
Transversing itemset lattices with statistical metric pruning
200 Citations2000Shinichi Morishita, Jun Sese
A method of estimating a tight upper bound on the statistical metric associated with any superset of an itemset, as well as the novel use of the resulting information of upper bounds to prune unproductive supersets while traversing itemset lattices is presented.
Kyushu University Institutional Repository (QIR) (Kyushu University)Efficient Substructure Discovery from Large Semi-structed Data
183 Citations2001Tatsuya Asai, 達哉 浅井 +10 more
Lirias (KU Leuven)Finding frequent substructures in chemical compounds
171 Citations1999Luc De Raedt, Hannu Toivonen +1 more
This paper applies data mining to the problem of predicting chemical carcinogenicity, and presents a knowledge discovery method for structured data, where patterns reflect the one- to-many and many-to-many relationships of several tables.
IEEE Transactions on Knowledge and Data EngineeringDiscovering structural association of semistructured data
139 Citations2000Ke Wang, Huiqing Liu
The discovery task is affected by structural features of semistructured data in a nontrivial way and traditional data mining frameworks are inapplicable.
Lecture notes in computer scienceOptimized Substructure Discovery for Semi-structured Data
120 Citations2002Kenji Abe, Shinji Kawasoe +3 more
An efficient algorithm is presented that discovers the best labeled ordered trees that optimize a given statistical measure, such as the information entropy and the classification accuracy, in a collection of semi-structured data.
ACM SIGMOD RecordData mining using two-dimensional optimized association rules
103 Citations1996Takeshi Fukuda, Yasukiko Morimoto +2 more
This work discusses data mining based on association rules for two numeric attributes and one Boolean attribute, for example, in a database of bank customers, "Age" and "Balance" are two numerical attributes that are associated with each other.
Mining optimized association rules with categorical and numeric attributes
82 Citations2002R. Rastogi, Kyuseok Shim
The generalized association rules enable us to extract more useful information about seasonal and local patterns involving multiple attributes and present effective techniques for pruning the search space when computing optimized association rules for both categorical and numeric attributes.
Efficient agnostic PAC-learning with simple hypothesis
54 Citations1994Wolfgang Maass
The algorithms that are introduced in this paper make it feasible to compute optimal hypotheses of this type for a training set of several hundred examples, and an approximation algorithm is exhibited that can compute nearly optimal hypotheses for much larger datasets.
Lecture notes in computer scienceDiscovery of Frequent Tree Structured Patterns in Semistructured Web Documents
48 Citations2001Tetsuhiro Miyahara, Takayoshi Shoudai +3 more
An algorithm for finding all maximally frequent tag tree patterns in semistructured data such as Web documents is presented and some experimental results on XML documents are reported by using the algorithm.
New Generation ComputingEfficient discovery of optimal word-association patterns in large text databases
33 Citations2000Shinichi Shimozono, Hiroki Arimura +1 more
An algorithm is presented that finds alld-stringsk-proximity word-association patterns that maximize the number of texts whose matching agree with their labels, and it runs in expected time complexityO(kd−1n logdn) with the total lengthn of texts, if texts are uniformly random strings.
Lecture notes in computer scienceA Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases
24 Citations1998Hiroki Arimura, Atsushi Wataki +2 more
This work considers a data mining problem in a large collection of unstructured texts based on association rules over subwords of texts and presents an e cient algorithm for computing frequent patterns that optimize theence with respect to a given collection of texts.
Journal of Computer and System SciencesOn the difficulty of approximately maximizing agreements
18 Citations2003Shai Ben-David, Nadav Eiron +1 more
For a variety of common concept classes, it is proved that, unless P=NP, there is no polynomial time approximation scheme for finding a member in the class that approximately maximizes the agreement with a given training sample.
Lecture notes in computer scienceDiscovering Unordered and Ordered Phrase Association Patterns for Text Mining
13 Citations2000Ryoichi Fujino, Hiroki Arimura +1 more
This paper considers the problem of finding all frequent phrase association patterns in a large collection of unstructured texts, and presents efficient algorithms, called Levelwise-Scan, based on the sequential counting technique of Apriori algorithm, which uses the generalized suffix tree and the pattern matching automaton.
Text data mining: discovery of important keywords in the cyberspace
8 Citations2000Hiroki Arimura, Jair Minoro Abe +4 more
A class of simple combinatorial patterns over phrases, called proximity phrase association patterns, are introduced, and the problem of finding the patterns that optimize a given statistical measure within the whole class of patterns in a large collection of unstructured texts is considered.