K-optimal pattern discovery: An efficient and effective approach to exploratory data mining

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review


Most data-mining techniques seek a single model that optimizes an objective function with respect to the data. In many real-world applications several models will equally optimize this function. However, they may not all equally satisfy a user's preferences, which will be affected by background knowledge and pragmatic considerations that are infeasible to quantify into an objective function. Thus, the program may make arbitrary and potentially suboptimal decisions. In contrast, methods for exploratory pattern discovery seek all models that satisfy user-defined criteria. This allows the user select between these models, rather than relinquishing control to the program. Association rule discovery [1] is the best known example of this approach. However, it is based on the minimum-support technique, by which patterns are only discovered that occur in the data more than a user-specified number of times. While this approach has proved very effective in many applications, it is subject to a number of limitations. It creates an arbitrary discontinuity in the interestingness function by which one more or less case supporting a pattern can transform its assessment from uninteresting to most interesting. Sometimes the most interesting patterns are very rare [3]. Minimum support may not be relevant to whether a pattern is interesting. It is often difficult to find a minimum support level that results in sufficient but not excessive numbers of patterns being discovered. It cannot handle dense data [2]. It limits the ability to efficiently prune the search space on the basis on constraints that are neither monotone nor anti-monotone with respect to support. K-optimal pattern discovery [4,5,11,14,15,17-20] is an exploratory technique that finds the k patterns that optimize a user-selected objective function while respecting other user-specified constraints. This strategy avoids the above problems while empowering the user to select between preference criteria and to directly control the number of patterns that are discovered. It also supports statistically sound exploratory pattern discovery [8]. Its effectiveness is demonstrated by a large range of applications [5-10,12,13].

Original languageEnglish
Title of host publicationAI 2005
Subtitle of host publicationAdvances in Artificial Intelligence - 18th Australian Joint Conference on Artificial Intelligence, Proceedings
Number of pages2
Publication statusPublished - 1 Dec 2005
EventAustralasian Joint Conference on Artificial Intelligence 2005 - Sydney, Australia
Duration: 5 Dec 20059 Dec 2005
Conference number: 18th
https://link.springer.com/book/10.1007/11589990 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3809 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceAustralasian Joint Conference on Artificial Intelligence 2005
Abbreviated titleAI 2005
Internet address

Cite this