Using closed itemsets in association rule mining with taxonomies

Petteri Sevon

doi:10.1117/12.381729

6 April 2000 Using closed itemsets in association rule mining with taxonomies

Petteri Sevon

Proceedings Volume 4057, Data Mining and Knowledge Discovery: Theory, Tools, and Technology II; (2000) https://doi.org/10.1117/12.381729
Event: AeroSense 2000, 2000, Orlando, FL, United States

Abstract

Taxonomies or item hierarchies are often useful in association rule mining. The most time consuming subtask in rule mining is the discovery of the frequent itemsets. A standard algorithm for frequent itemset discovery, such as Apriori, would however produce many redundant itemsets if taxonomies are used, because any two itemsets that share their most specific items always match the same set of transactions. An efficient algorithm must therefore chose a canonical representative for each equivalence class of itemsets. Srikant and Agrawal solved the problem of redundancy in their Cumulate and Stratify algorithms by not allowing an itemset to contain an item and its ancestor. In this paper I will present a new algorithm, Closed Sets, for finding frequent itemsets in the presence of taxonomies. The algorithm requires itemsets to be closed under the taxonomies. If an item is a member of a closed itemset, then all its ancestors also are. The algorithm makes fewer passes over the database than Stratify and it prunes the search space optimally. This is not the case with Cumulate, and not even with Stratify, if there are items in the taxonomy with multiple parents. Furthermore, only modest modifications to Apriori are needed.

Citation Download Citation

Petteri Sevon "Using closed itemsets in association rule mining with taxonomies", Proc. SPIE 4057, Data Mining and Knowledge Discovery: Theory, Tools, and Technology II, (6 April 2000); https://doi.org/10.1117/12.381729

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
8 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Taxonomy

Databases

Mining

Knowledge discovery

Statistical analysis

Binary data

Chlorine

Show All Keywords

Keywords/Phrases

Search In:

Publication Years