Behavior-based clustering and analysis of interestingness measures for association rule mining

A number of studies, theoretical, empirical, or both, have been conducted to provide insight into the properties and behavior of interestingness measures for association rule mining. While each has value in its own right, most are either limited in scope or, more importantly, ignore the purpose for which interestingness measures are intended, namely the ultimate ranking of discovered association rules. This paper, therefore, focuses on an analysis of the rule-ranking behavior of 61 well-known interestingness measures tested on the rules generated from 110 different datasets. By clustering based on ranking behavior, we highlight, and formally prove, previously unreported equivalences among interestingness measures. We also show that there appear to be distinct clusters of interestingness measures, but that there remain differences among clusters, confirming that domain knowledge is essential to the selection of an appropriate interestingness measure for a particular task and business objective.     

What makes patterns interesting in knowledge discovery systems

One of the central problems in the field of knowledge discovery is the development of good measures of interestingness of discovered patterns. Such measures of interestingness are divided into objective measures-those that depend only on the structure of a pattern and the underlying data used in the discovery process, and the subjective measures-those that also depend on the class of users who examine the pattern. The focus of the paper is on studying subjective measures of interestingness. These measures are classified into actionable and unexpected, and the relationship between them is examined. The unexpected measure of interestingness is defined in terms of the belief system that the user has. Interestingness of a pattern is expressed in terms of how it affects the belief system. The paper also discusses how this unexpected measure of interestingness can be used in the discovery process     

Knowledge discovery in distributed databases using evidence theory

Distributed databases allow us to integrate data from different sources which have not previously been combined. The Dempster–Shafer theory of evidence and evidential reasoning are particularly suited to the integration of distributed databases. Evidential functions are suited to represent evidence from different sources. Evidential reasoning is carried out by the well‐known orthogonal sum. Previous work has defined linguistic summaries to discover knowledge by using fuzzy set theory and using evidence theory to define summaries. In this paper we study linguistic summaries and their applications to knowledge discovery in distributed databases. © 2000 John Wiley & Sons, Inc.     

A multi-objective model for discovering high-quality knowledge based on data quality and prior knowledge

Discovering knowledge from data means finding useful patterns in data, this process has increased the opportunity and challenge for businesses in the big data era. Meanwhile, improving the quality of the discovered knowledge is important for making correct decisions in an unpredictable environment. Various models have been developed in the past; however, few used both data quality and prior knowledge to control the quality of the discovery processes and results. In this paper, a multi-objective model of knowledge discovery in databases is developed, which aids the discovery process by utilizing prior process knowledge and different measures of data quality. To illustrate the model, association rule mining is considered and formulated as a multi-objective problem that takes into account data quality measures and prior process knowledge instead of a single objective problem. Measures such as confidence, support, comprehensibility and interestingness are used. A Pareto-based integrated multi-objective Artificial Bee Colony (IMOABC) algorithm is developed to solve the problem. Using well-known and publicly available databases, experiments are carried out to compare the performance of IMOABC with NSGA-II, MOPSO and Apriori algorithms, respectively. The computational results show that IMOABC outperforms NSGA-II, MOPSO and Apriori on different measures and it could be easily customized or tailored to be in line with user requirements and still generates high-quality association rules.     

Ranking discovered rules from data mining with multiple criteria by data envelopment analysis

In data mining applications, it is important to develop evaluation methods for selecting quality and profitable rules. This paper utilizes a non-parametric approach, Data Envelopment Analysis (DEA), to estimate and rank the efficiency of association rules with multiple criteria. The interestingness of association rules is conventionally measured based on support and confidence. For specific applications, domain knowledge can be further designed as measures to evaluate the discovered rules. For example, in market basket analysis, the product value and cross-selling profit associated with the association rule can serve as essential measures to rule interestingness. In this paper, these domain measures are also included in the rule ranking procedure for selecting valuable rules for implementation. An example of market basket analysis is applied to illustrate the DEA based methodology for measuring the efficiency of association rules with multiple criteria.     

Ranking discovered rules from data mining with multiple criteria by data envelopment analysis

In data mining applications, it is important to develop evaluation methods for selecting quality and profitable rules. This paper utilizes a non-parametric approach, Data Envelopment Analysis (DEA), to estimate and rank the efficiency of association rules with multiple criteria. The interestingness of association rules is conventionally measured based on support and confidence. For specific applications, domain knowledge can be further designed as measures to evaluate the discovered rules. For example, in market basket analysis, the product value and cross-selling profit associated with the association rule can serve as essential measures to rule interestingness. In this paper, these domain measures are also included in the rule ranking procedure for selecting valuable rules for implementation. An example of market basket analysis is applied to illustrate the DEA based methodology for measuring the efficiency of association rules with multiple criteria.     

Two novel interestingness measures for gene association rule mining

Recent research has shown that association rules are useful in gene expression data analysis. Interestingness measure plays an important role in the association rule mining on small sample size, high dimensionality, and noisy gene expression data. This work introduces two interestingness measures by exploring prior knowledge contained in open biological databases. They are Max-Pathway-Distance (MaxPD), which explores the gene’s relativity in Kyoto encyclopedia of genes and genomes Pathway, and Max-Chromosomal-Distance (MaxCD), which makes use of the distance among genes in the chromosome. The properties of our proposed interestingness measures are also explored to mine the interesting rules efficiently. Experimental results on four real-life gene expression datasets show the effectiveness of MaxPD and MaxCD in both classification accuracy and biological interpretability.     

From data properties to evidence

The problem of making decisions among propositions based on both uncertain data items and arguments which are not certain is addressed. The primary knowledge discovery issue addressed is a classification problem: which classification does the available evidence support? The method investigated seeks to exploit information available from conventional database systems, namely, the integrity assertions or data dependency information contained in the database. This information allows ranking arguments in terms of their strengths. As a step in the process of discovering classification knowledge, using a database as a secondary knowledge discovery exercise, latent knowledge pertinent to arguments of relevance to the purpose at hand is explicated. This is called evidence. Information is requested via user prompts from an evidential reasoner. It is fed as evidence to the reasoner. An object-oriented structure for managing evidence is used to model the conclusion space and to reflect the evidence structure. The implementation of the evidence structure and an example of its use are outlined     

Maximum entropy models and subjective interestingness: an application to tiles in binary databases

Recent research has highlighted the practical benefits of subjective interestingness measures, which quantify the novelty or unexpectedness of a pattern when contrasted with any prior information of the data miner (Silberschatz and Tuzhilin, Proceedings of the 1st ACM SIGKDD international conference on Knowledge discovery and data mining (KDD95), 1995; Geng and Hamilton, ACM Comput Surv 38(3):9, 2006). A key challenge here is the formalization of this prior information in a way that lends itself to the definition of a subjective interestingness measure that is both meaningful and practical. In this paper, we outline a general strategy of how this could be achieved, before working out the details for a use case that is important in its own right. Our general strategy is based on considering prior information as constraints on a probabilistic model representing the uncertainty about the data. More specifically, we represent the prior information by the maximum entropy (MaxEnt) distribution subject to these constraints. We briefly outline various measures that could subsequently be used to contrast patterns with this MaxEnt model, thus quantifying their subjective interestingness. We demonstrate this strategy for rectangular databases with knowledge of the row and column sums. This situation has been considered before using computation intensive approaches based on swap randomizations, allowing for the computation of empirical p-values as interestingness measures (Gionis et al., ACM Trans Knowl Discov Data 1(3):14, 2007). We show how the MaxEnt model can be computed remarkably efficiently in this situation, and how it can be used for the same purpose as swap randomizations but computationally more efficiently. More importantly, being an explicitly represented distribution, the MaxEnt model can additionally be used to define analytically computable interestingness measures, as we demonstrate for tiles (Geerts et al., Proceedings of the 7th international conference on Discovery science (DS04), 2004) in binary databases.     

Data Mining in Large Databases Using Domain Generalization Graphs

Attribute-oriented generalization summarizes the information in a relational database by repeatedly replacing specific attribute values with more general concepts according to user-defined concept hierarchies. We introduce domain generalization graphs for controlling the generalization of a set of attributes and show how they are constructed. We then present serial and parallel versions of the Multi-Attribute Generalization algorithm for traversing the generalization state space described by joining the domain generalization graphs for multiple attributes. Based upon a generate-and-test approach, the algorithm generates all possible summaries consistent with the domain generalization graphs. Our experimental results show that significant speedups are possible by partitioning path combinations from the DGGs across multiple processors. We also rank the interestingness of the resulting summaries using measures based upon variance and relative entropy. Our experimental results also show that these measures provide an effective basis for analyzing summary data generated from relational databases. Variance appears more useful because it tends to rank the less complex summaries (i.e., those with few attributes and/or tuples) as more interesting.     

数据挖掘中关联规则的有趣性研究

关联规则挖掘是数据挖掘研究中的一个重要方面，而其中一个重要问题是对挖掘出的规则的兴趣度的评估，过去的研究发现，在实际应用中往往很容易从数据源中挖掘出大量的规则，但这些规则中的大部分对用户来说是不感兴趣的，本文对规则的兴趣度度量的两个方面作了讨论：一个是主观兴趣度度量，另一个是客观兴趣度度量，最后介绍了如何利用模板进行挖掘有趣的规则。     

影响关联规则挖掘的有趣性因素的研究

关联规则挖掘是数据挖掘研究中的一个重要方面,而其中一个重要问题是对挖掘出的规则的感兴趣程度的评估。实际应用中可从数据源中挖掘出大量的规则,但这些规则中的大部分对用户来说是不一定感兴趣的。关联规则挖掘中的有趣性问题可从客观和主观两个方面对关联规则的兴趣度进行评测。利用模板将用户感兴趣的规则和不感兴趣的规则区分开,以此来完成关联规则有趣性的主观评测;在关联规则的置信度和支持度基础上对关联规则的有趣性的客观评测增加了约束。     

Mining Pareto-optimal rules with respect to support and confirmation or support and anti-support

In knowledge discovery and data mining many measures of interestingness have been proposed in order to measure the relevance and utility of the discovered patterns. Among these measures, an important role is played by Bayesian confirmation measures, which express in what degree a premise confirms a conclusion. In this paper, we are considering knowledge patterns in a form of “if…, then…” rules with a fixed conclusion. We investigate a monotone link between Bayesian confirmation measures, and classic dimensions being rule support and confidence. In particular, we formulate and prove conditions for monotone dependence of two confirmation measures enjoying some desirable properties on rule support and confidence. As the confidence measure is unable to identify and eliminate non-interesting rules, for which a premise does not confirm a conclusion, we propose to substitute the confidence for one of the considered confirmation measures in mining the Pareto-optimal rules. We also provide general conclusions for the monotone link between any confirmation measure enjoying the desirable properties and rule support and confidence. Finally, we propose to mine rules maximizing rule support and minimizing rule anti-support, which is the number of examples, which satisfy the premise of the rule but not its conclusion (called counter-examples of the considered rule). We prove that in this way we are able to mine all the rules maximizing any confirmation measure enjoying the desirable properties. We also prove that this Pareto-optimal set includes all the rules from the previously considered Pareto-optimal borders.     

Exploration of Ordinal Data Using Association Rules

The discovery of association rules is a very efficient data mining technique that is especially suitable for large amounts of categorical data. This paper shows how the discovery of association rules can be of benefit for numeric data as well. Based on a review of previous approaches we introduce Q2, a faster algorithm for the discovery of multi-dimensional association rules over ordinal data. We experimentally compare the new algorithm with the previous approach, obtaining performance improvements of more than an order of magnitude on supermarket data. In addition, a new absolute measure for the interestingness of quantitative association rules is introduced. It is based on the view that quantitative association rules have to be interpreted with respect to their Boolean generalizations. This measure has two major benefits compared to the previously used relative interestingness measure; first, it speeds up rule extraction and evaluation and second, it is easier to interpret for a user. Finally we introduce a rule browser which supports the exploration of ordinal data with quantitative association rules.     

挖掘所关注规则的多策略方法研究

通过数据挖掘,从大型数据库中发现了大量规则,如何选取所关注的规则,是知识发现的重要研究内容。该文研究了利用领域知识对规则的主观关注程度进行度量的方法,给出了一个能够度量规则的简洁性和新奇性的客观关注程度的计算函数,提出了选取用户关注的规则的多策略方法。     

Levelwise Search and Pruning Strategies for First-Order Hypothesis Spaces

The discovery of interesting patterns in relational databases is an important data mining task. This paper is concerned with the development of a search algorithm for first-order hypothesis spaces adopting an important pruning technique (termed subset pruning here) from association rule mining in a first-order setting. The basic search algorithm is extended by so-called requires and excludes constraints allowing to declare prior knowledge about the data, such as mutual exclusion or generalization relationships among attributes, so that it can be exploited for further structuring and restricting the search space. Furthermore, it is illustrated how to process taxonomies and numerical attributes in the search algorithm.Several task settings using different interestingness criteria and search modes with corresponding pruning criteria are described. Three settings serve as test beds for evaluation of the proposed approach. The experimental evaluation shows that the impact of subset pruning is significant, since it reduces the number of hypothesis evaluations in many cases by about 50%. The impact of generalization relationships is shown to be less effective in our experimental set-up.     

概念指导的关联规则的挖掘

关联规则是数据依赖关系泊有效描述方法,是知识发现研究的重要内容,传统的关联规则挖掘算法缺少挖掘的针对性,挖掘速度慢,挖掘效果难于理解,挖掘析数量巨大,需要进行大量的筛选以便抽取出有用规则,文中提出了将概念融入挖掘过程中,提高挖掘的效率和挖掘的针对性的方法,给出了概念指导的关联规则挖掘算法ＣＧＡＲＭ和大数据库中概念的交互式生成方法。算法ＣＧＡＲＭ是对基于分类的挖掘算法的拓展。实验结果表明,算法ＣＧＡ     

Database summarization using fuzzy ISA hierarchies

Summary discovery is one of the major components of knowledge discovery in databases, which provides the user with comprehensive information for grasping the essence from a large amount of information in a database. In this paper, we propose an interactive top-down summary discovery process which utilizes fuzzy ISA hierarchies as domain knowledge. We define a generalized tuple as a representational form of a database summary including fuzzy concepts. By virtue of fuzzy ISA hierarchies where fuzzy ISA relationships common in actual domains are naturally expressed, the discovery process comes up with more accurate database summaries. We also present an informativeness measure for distinguishing generalized tuples that delivers much information to users, based on Shannon's information theory.     

Database summarization using fuzzy ISA hierarchies

Summary discovery is one of the major components of knowledge discovery in databases, which provides the user with comprehensive information for grasping the essence from a large amount of information in a database. We propose an interactive top down summary discovery process which utilizes fuzzy ISA hierarchies as domain knowledge. We define a generalized tuple as a representational form of a database summary including fuzzy concepts. By virtue of fuzzy ISA hierarchies where fuzzy ISA relationships common in actual domains are naturally expressed, the discovery process comes up with more accurate database summaries. We also present an informativeness measure for distinguishing generalized tuples that delivers much information to users, based on C. Shannon's (1948) information theory.