Levelwise Search and Borders of Theories in Knowledge Discovery
Data Mining and Knowledge DiscoveryPublished 1 September 1997
Heikki Mannila, Hannu Toivonen
Citations865
SJR quartileQ1
SJR score1.02
SNIP1.88
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
The concept of the border of a theory, a notion that turns out to be surprisingly powerful in analyzing the algorithm, is introduced and strong connections between the verification problem and the hypergraph transversal problem are shown.
Abstract
One of the basic problems in knowledge discovery in databases (KDD) is the following: given a data set r, a class L of sentences for defining subgroups of r, and a selection predicate, find all sentences of L deemed interesting by the selection predicate. We analyze the simple levelwise algorithm for finding all such descriptions. We give bounds for the number of database accesses that the algorithm makes. For this, we introduce the concept of the border of a theory, a notion that turns out to be surprisingly powerful in analyzing the algorithm. We also consider the verification problem of a KDD process: given r and a set of sentences S $$ \subseteq $$ L determine whether S is exactly the set of interesting statements about r. We show strong connections between the verification problem and the hypergraph transversal problem. The verification problem arises in a natural way when using sampling to speed up the pattern discovery step in KDD.
Keywords
Computer Science
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
MIT Press eBooksKnowledge Discovery in Databases
1,758 Citations1991Gregory Piateski, William Frawley
Future Generation Computer SystemsMining generalized association rules
1,617 Citations1997Ramakrishnan Srikant, Rakesh Agrawal
A new interest-measure for rules which uses the information in the taxonomy is presented, and given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules.
An Efficient Algorithm for Mining Association Rules in Large Databases
1,598 Citations1995Ashoka Savasere, Edward Omiecinski +1 more
This paper presents an efficient algorithm for mining association rules that is fundamentally different from known algorithms and not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases.
Mining quantitative association rules in large relational tables
1,484 Citations1996Ramakrishnan Srikant, Rakesh Agrawal
This work deals with quantitative attributes by fine-partitioning the values of the attribute and then combining adjacent partitions as necessary and introduces measures of partial completeness which quantify the information lost due to partitioning.
Data Mining and Knowledge DiscoveryDiscovery of Frequent Episodes in Event Sequences
1,445 Citations1997Heikki Mannila, Hannu Toivonen +1 more
This work gives efficient algorithms for the discovery of all frequent episodes from a given class of episodes, and presents detailed experimental results that are in use in telecommunication alarm management.
An effective hash-based algorithm for mining association rules
1,412 Citations1995Jong Soo Park, Ming-Syan Chen⋆ +1 more
The number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck, and allows us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly.
Beyond market baskets
1,287 Citations1997Sergey Brin, Rajeev Motwani +1 more
This work develops the notion of mining rules that identify correlations (generalizing associations), and proposes measuring significance of associations via the chi-squared test for correlation from classical statistics, enabling the mining problem to reduce to the search for a border between correlated and uncorrelated itemsets in the lattice.
Sampling Large Databases for Association Rules
1,079 Citations1996Hannu Toivonen
New algorithms that reduce the database activity considerably by picking a Random sample, to find using this sample all association rules that probably hold in the whole database, and then to verify the results with the rest of the database.
Discovery of Multiple-Level Association Rules from Large Databases
920 Citations1995Jiawei Han, Yongjian Fu
A top-down progressive deepening method is developed for mining multiplelevel association rules from large transaction databases by extension of some existing association rule mining techniques.
North-Holland mathematical libraryHypergraphs - Combinatorics of Finite Sets
796 Citations1989
This chapter discusses Hypergraphs Generalising Bipartite Graphs, which are a collection of hypergraphs designed to solve the problem of Uniform Colourings in Matroids, and some of the properties of these graphs.
Finding interesting rules from large sets of discovered association rules
717 Citations1994Mika Klemettinen, Heikki Mannila +3 more
It is shown how a simple formalism of rule templates makes it possible to easily describe the structure of interesting rules, and how a visualization tool interfaces with rule templates.
Knowledge Discovery and Data MiningDiscovering Frequent Episodes in Sequences.
593 Citations1995Heikki Mannila, Hannu Toivonen +1 more
These two cases represent the only melanocytic neoplasms in Rhinoceridae reported in detail in the literature and are thought to be the first of their kind diagnosed in captivity.
Medical Entomology and ZoologyElements of Machine Learning
517 Citations1995Pat Langley
Elements of Machine Learning by Pat Langley examines the science of machine learning, methodology, and prospects for machine learning in the coming years.
Communications of the ACMA database perspective on knowledge discovery
470 Citations1996Tomasz Imieliński, Heikki Mannila
The concept of data mining as a querying process and the first steps toward efficient development of knowledge discovery applications are discussed.
SIAM Journal on ComputingIdentifying the Minimal Transversals of a Hypergraph and Related Problems
427 Citations1995Thomas Eiter, Georg Gottlob
Two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, are considered and their significance for several search problems in applied computer science is discussed.
Journal of AlgorithmsOn the Complexity of Dualization of Monotone Disjunctive Normal Forms
416 Citations1996Michael L. Fredman, Leonid Khachiyan
It is shown that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
Mining optimized association rules for numeric attributes
215 Citations1996Takeshi Fukuda, Yasuhido Morimoto +2 more
Given a huge database, the problem of finding rules for numeric attributes, such as(Balance # I)O(CardLoan=yes), is addressed, which implies that bank customers whose balances fall in a range I are likely to use card loan with a probability greater than p.
Data & Knowledge EngineeringAlgorithms for inferring functional dependencies from relations
194 Citations1994Heikki Mannila, Kari‐Jouko Räihä
Two algorithms with better best case behavior than the simple one are developed to solve the dependency inference problem of finding a cover of the set of functional dependencies that hold in a given relation.
Journal of Computer and System SciencesDesign by example: An application of Armstrong relations
154 Citations1986Heikki Mannila, Kari‐Jouko Räihä
This paper analyzes the use of Armstrong relations in database design with functional dependencies, and shows how they and the usual representation of dependencies can be used together.
Data mining, hypergraph transversals, and machine learning (extended abstract)
153 Citations1997Dimitrios Gunopulos, Heikki Mannila +2 more
This work analyzes two algorithms that have been previously used in data mining, proving upper bounds on their complexity, and relates them to the model of exact learning in computational learning theory, and uses the correspondence to derive some corollaries.
Data mining, hypergraph transversals, and machine learning
151 Citations1997Dimitrios Gunopulos, Roni Khardon +2 more
Artificial IntelligenceFirst-order jk-clausal theories are PAC-learnable
142 Citations1994Luc De Raedt, Sašo Džeroski
Positive PAC-learning results for the nonmonotonic inductive logic programming setting are presented and first-order range-restricted clausal theories that consist of clauses with up to k literals of size at most j each are shown to be PAC-learnable with one-sided error from positive examples only.
Discrete Applied MathematicsOn generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
124 Citations1999Vladimir Gurvich, Leonid Khachiyan
It is shown that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D′=D or C′=C, which provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time.
CWI's Institutional Repository (Centrum Wiskunde & Informatica)A Perspective on Databases and data mining
104 Citations1995Marcel Holsheimer, Martin Kersten +2 more
International Journal of Intelligent SystemsDiscovering functional and inclusion dependencies in relational databases
100 Citations1992Martti Kantola, Heikki Mannila +2 more
This article discusses the use of examples in the design of databases, and gives an overview of the complexity results and algorithms that have been developed for this problem.
Discrete Applied MathematicsOn the complexity of inferring functional dependencies
92 Citations1992Heikki Mannila, Kari‐Jouko Räihä
This work shows that this problem is solvable by a brute-force algorithm in Θ( n 2 2 n p log p ) time for a relation with p rows and n attributes, and proves two exponential lower bounds that hold even for the case where no explicit representation of the dependency set is needed.
Journal of Intelligent Information SystemsEfficient discovery of interesting statements in databases
48 Citations1995Willi Kl�sgen
This paper describes how Explora assesses interestingness and achieves computational efficiency, and describes strategies that reduce data accesses and speed up computation.
Compression-based evaluation of partial determinations
31 Citations1995Bernhard Pfahringer, Stefan Krämer
A measure based on the minimum description length (MDL) principle is proposed to evaluate partial determinations in databases and takes into account both the complexity and the correctness of a given partial determination, thus avoiding overfitting especially in the presence of noise.
Discovery and maintenance of functional dependencies by independencies
19 Citations1995Siegfried Bell
The main effort has been put into minimizing the number of database accesses, w.r.t. discovery and maintenance, by improving the inference of functional dependencies by using independencies and cardinality dependencies.