Affiliations: Department of Computer Science, University of Regina, Regina, Saskatchewan, Canada S4S 0A2. E-mail: [email protected], [email protected]
Abstract: When mining a large database, the number of patterns discovered can easily exceed the capabilities of a human user to identify interesting results. To address this problem, various techniques have been suggested to reduce and/or order the patterns prior to presenting them to the user. In this paper, our focus is on ranking summaries generated from a single dataset, where attributes can be generalized in many different ways and to many levels of granularity according to taxonomic hierarchies. We theoretically and empirically evaluate twelve diversity measures used as heuristic measures of interestingness for ranking summaries generated from databases. The twelve diversity measures have previously been utilized in various disciplines, such as information theory, statistics, ecology, and economics. We describe five principles that any measure must satisfy to be considered useful for ranking summaries. Theoretical results show that the proposed principles define a partial order on the ranked summaries in most cases, and in some cases, define a total order. Theoretical results also show that seven of the twelve diversity measures satisfy all of the five principles. We empirically analyze the rank order of the summaries as determined by each of the twelve measures. These empirical results show that the measures tend to rank the less complex summaries as most interesting. Finally, we analyze the distribution of the index values generated by each of the twelve diversity measures. Empirical results, obtained using synthetic data, show that the distribution of index values generated tend to be highly skewed about the mean, median, and middle index values. Finally, we demonstrate a technique, based upon our principles, for visualizing the relative interestingness of summaries. The objective of this work is to gain some insight into the behaviour that can be expected from our principled approach in practice.
Keywords: data mining, diversity measures, theory of interestingness, statistics and probability, visualization
