We present a survey of data exploration methods that extract multi-dimensional patterns from datasets consisting of dimension and measure attributes. These patterns are designed to summarize common properties of tuples associated with particular values of the measure attributes. We provide a categorization of the characteristics of patterns produced by various solutions to this problem, we point out the pros, cons and performance optimizations of existing methods, and we suggest directions for future research.
Data volumes have been growing rapidly in recent years. As a result, data-intensive methods are now common in many contexts, including business, science, and public governance. This motivates the need for tools that allow users who are not necessarily data management experts to explore large datasets. Such tools range from visualization and aggregation to flexible search interfaces such as keyword search in structured databases.
In this paper, we focus on the exploration of datasets containing dimension attributes and binary or numeric measure attributes. In traditional business datasets, dimension attributes often describe products or employees, and measure attributes indicate sales totals or salaries. In Internet-of-Things (IoT) and infrastructure monitoring, dimension attributes may describe device properties and measure attributes correspond to performance statistics. In Web datasets, dimension attributes may describe products, with user ratings as measure attributes. Additionally, in any of these applications, derived measure attributes may exist, e.g., a binary attribute denoting whether a given record was determined to be an outlier or to contain an error.
The data cube has traditionally been used to explore these
kinds of datasets, by allowing users to aggregate, roll-up and
drill-down using various subsets of group-by attributes. However,
in large-scale databases, the data cube may be very large and
may not immediately reveal interesting patterns and trends. This
motivates the need for more sophisticated exploration tools [
We observe that a large body of recent work on exploring multi-dimensional and OLAP datasets proposes methods to identify interesting fragments of the data, summarized using patterns over the values of the dimension attributes. We make the following contributions towards an understanding of these data exploration methods.
(1) We survey recent work on data exploration using multidimensional patterns and propose a categorization based on the properties of patterns suggested for exploration: coverage, contrast, and information. 2
We are given a dataset with a set of dimension attributes
and a set of measure attributes (also referred to as outcomes
in some prior work [
Table 1 shows a flight dataset that will serve as a running example. For each flight, the dataset includes a record id, followed by three dimension attributes, Day of the week, flight Origin and lfight Destination, as well as two measure attributes, a numeric attribute denoting how late the flight was and a binary attribute denoting whether the flight was full.
Let ( ) be the active domain of the th dimension
attribute. A pattern (referred to as a rule in some prior work [
Let () be the support of in , i.e., the number of tuples matching , and let () be the number of tuples matching and satisfying the predicate over the measure attributes. For example, (∗, ∗, ) = 4 and =0 (∗, ∗, ) = 1. Furthermore, let () = (()) , which is the fraction of tuples matching that also satisfy the predicate . For example, =1 (∗, ∗, ) = 43 .
Let () be the sum of the values of a measure attribute () be the sum of over all the tuples matching . Let the values of a measure attribute over all the tuples matching and satisfying the predicate over the measure attributes. For example, (∗, ∗, ) = 20 + 15 + 19 + 7 = 61 and =0 (∗, ∗, ) = 7.
We survey solutions to the following data exploration problem: given a dataset , produce a set or a list of patterns over the dimension attributes of , as defined above, that summarize common properties of tuples sharing the same values of the measure attribute(s). Users may then inspect the patterns and explore tuples covered by the patterns. They may then extract patterns corresponding to a smaller subset of the data that was found to be interesting during the earlier exploration step, and so on.
The number of patterns in should be limited to direct the user’s attention to the most important or interesting regions of the data. This limit may be set explicitly by the user (in terms of the maximum number of patterns in ) or implicitly by retrieving • Explaining the results of aggregate queries. Suppose a data analyst issues the following query over Table 1: SELECT SUM(Late) FROM S. Suppose the analyst wishes to understand why the result, of 145, is so high. Here, interesting patterns are those which cover tuples that make a significant contribution to the result, i.e., those with a high () such as (∗, ∗, ). The analyst may then zoom into flights landing in London and investigate potential reasons for the lengthy delays. • Analyzing outliers and data quality issues. Suppose we have a binary measure attribute denoting whether a given tuple contains an error or is an outlier. This attribute could be created manually by domain experts or automatically by identifying tuples that violate data quality rules or deviate from the expected distribution. We may wish to produce patterns that summarize the properties of erroneous tuples to help determine the root cause of data quality problems. • Feature selection and explainable AI. Before building prediction models, a data scientist may explore interesting patterns to understand which dimension attributes are related to the measure attribute that is to be predicted. Furthermore, suppose a data analyst wants to understand how a black-box model makes classification decisions. Here, the dimension attributes are the features given to the model as input, and, as the measure attribute, the analyst records the predictions made by the model. The analyst may then want to find interesting patterns that explain the prediction decisions. For example, in Table 1, the pattern (, ∗, ∗) is associated with tuples having = 0, suggesting that lfights scheduled on Mondays are usually not full 1.
In this section, we provide a categorization of previous work on data exploration using multi-dimensional patterns based on the pattern properties and ranking strategies used for pattern selection. We categorize these properties into three types: those 1Model explanations may be global (to summarize how classification decisions are made) or local (to explain why a specific record was classified in a particular way). The explanations discussed in this paper are examples of global explanations. focusing on coverage, contrast and information. Table 2 categorizes the surveyed methods and lists their motivating applications, as mentioned in the corresponding papers.
The goal of these methods is to identify patterns that cover tuples
with certain values of the measure attribute. We discuss three
coverage-based methods: Data Auditor [
Suppose we are interested in covering tuples having = 1 in Table 1, as a way to summarize the characteristics of full lfights. A simple coverage-oriented approach is to sort the patterns according to =1 () and output the top-ranking patterns. Ignoring (∗, ∗, ∗), which always covers everything but is not informative, the top candidates are (∗, ∗, ) and (∗, ∗, ), which cover three full flights each, followed by the following patterns that cover two such tuples each: (, ∗, ∗), (, ∗, ∗), (, ∗, ∗) and (∗, , ∗).
There are two problems with this simple approach: there may be many patterns with a nonzero =1 (), and some of these patterns may also cover tuples with other values of the measure attribute (here, = 0). To reduce the size of the output and to ensure that each pattern co-occurs with the specified value of the measure attribute, Data Auditor solves the following set cover problem. Continuing with our example, Data Auditor requires a minimum threshold for =1 (), i.e., the fraction of tuples covered by that correspond to full flights. Suppose we require () ≥ 0.75. This threshold defines the candidate sets for the set cover problem. The set cover objective is to select the fewest such patterns that together cover a specified fraction of tuples in having = 1. Suppose this coverage fraction, which would again be set by the user, is 0.5. The goal is then to find the fewest patterns, as defined above, to cover half the full flights.
The set cover problem is NP-hard, and Data Auditor uses the standard greedy heuristic that achieves a logarithmic approximation ratio in the size of the solution: it iteratively chooses the pattern that covers the most uncovered tuples (having the desired value of the measure attribute), until the desired fraction of such tuples has been covered. In our example, the first pattern added to is either (∗, ∗, ) and (∗, ∗, ) - they each cover three full flights and their =1 () values are 0.75 each. Suppose the set cover algorithm selects (∗, ∗, ). Since there are seven full flights in the dataset and our coverage threshold is 0.5, we need to cover one more full flight. In the next iteration, the pattern that (has =1 () ≥ 0.75 and) covers the most remaining full flights is (∗, ∗, ) and the algorithm terminates, with consisting of these two patterns.
The next method, MRI, finds patterns that cover a userspecified fraction of the data and satisfy additional properties related to the variance of the measure attribute within each pattern. The motivating example for MRI was to explain queries over product reviews, with the dimension attributes corresponding to information about the reviewers (such as their gender and age) and the numeric measure attribute corresponding to the average rating. Minimizing variance amounts to returning patterns (having high coverage and) describing reviewers with similar opinions. For example, when applying MRI to Table 1 with as the measure attribute, the pattern (∗, ∗, ) is preferred over (∗, ∗, ). Both patterns cover four tuples, but the former has a lower variance of the attribute within the covered tuples.
Smart Drilldown also combines coverage with additional
pattern properties. Smart Drilldown produces patterns. In every
iteration of the algorithm, the chosen pattern maximizes the
following objective: the number of tuples not yet covered multiplied
by the weight of the pattern corresponding to some measure of
interestingness. One simple weighting function proposed in [
3.1.1 Performance Optimizations. A performance bottleneck in general set cover problems results from having to keep track of the number of uncovered elements that can be covered by the candidate sets - this changes in every iteration, whenever a new set is added to the solution. Data Auditor relies on the hierarchical nature of patterns and does not generate all the patterns that serve as input to greedy set cover a priori. Instead, patterns are generated on-demand, only after all of their supersets have already been considered. For example, a pattern such as (, ∗, ) would only be generated after all of its supersets - including (, ∗, ∗) and (∗, ∗, ) - have already been considered. Until then, (, ∗, ) can be safely ignored: it cannot cover more elements than its supersets and therefore is guaranteed to not be selected by the greedy set cover heuristic at this time. This optimization can greatly reduce the number of generated patterns whose coverage (of uncovered elements) must be re-computed while constructing the solution.
3.1.2 Pros and Cons. One advantage of coverage-based methods is conciseness: by design, they identify the fewest possible patterns that cover the desired fraction of tuples of interest. On the other hand, in Data Auditor, some trial-and-error may be required on the user’s part to select good values for the two required thresholds. For example, a high value of will ensure that each pattern co-occurs mainly with the specified value of the measure attribute, but will disqualify more patterns from consideration. Similarly, MRI and Smart Drilldown require users to set parameters for coverage and other pattern properties. 3.2
This is the largest group of methods, consisting of CAPE [
One could argue that interpretable classifiers such as decision
trees and rule-based methods (see, e.g., [
Contrast-based methods can also explain the results of aggregate queries. Consider the following query over Table 1: SELECT SUM(Late) FROM S WHERE Full=1. Here, the measure attribute corresponding to the quantity being aggregated. We then set the binary measure attribute to one for all tuples that participate in the query (i.e., tuples that match the WHERE predicate), and we select patterns of tuples that contribute to the result of the query (but would not contribute had the query been issued against the other tuples in the dataset).
Below, we explain the pattern ranking strategies used by contrast-based methods, with Table 1 as a running example.
Risk ratio is used by Macrobase; a related metric called Diagnosis Cost is used by Data X-ray. It is the ratio of the following two probabilities: 1) the probability that a tuple with a particular value is covered by the given pattern, and 2) the probability that a tuple with this particular value occurs outside this pattern. In our example, =1 () = =1(∗,∗,∗)=−1()=1 () . For in(=1 (∗,∗,∗)−(=1 ())+(=0 (∗,∗,∗)−=0 ()) stance, =1 (∗, ∗, ) = 00..745 = 1.875, whereas =1 (∗, , ∗) = 00..55 = 1. This indicates that (∗, ∗, ) represents full flights better than (∗, , ∗).
Mean shift (supported by DIFF) computes the ratio of the mean of the measure attribute values co-occurring with the two values of the binary measure attribute. In our example, =1 () = ==01 (())//==01 (()) . For instance, =1 (∗, ∗, ) = 574//13 = 2.57, indicating that full ifghts to London have delays that are 2.57 times longer than non-full flights to London.
Intervention is used by RSExplain; a related metric called Inlfuence is used by Scorpion. It measures the ratio of contribution towards the numeric measure attribute for tuples occurring with the diferent values of the binary measure attribute. In our example, =1 () = ==01 ((∗∗,,∗∗,,∗∗))−−==01 (()) . For instance, =1 (∗, ∗, ) = 10387−−574 = 1.8. In other words, if flights to London were removed from the dataset then full flights would have delays on average 1.8 times longer than non-full flights. On the other hand, =1 (∗, , ∗) = 13078−−1325 = 2.92, meaning that removing flights departing from SF from the dataset would create a greater contrast between the delays of full and non-full flights.
We also point out CAPE, whose goal is to find patterns whose measure attribute values counterbalance those of the pattern given as input. For example, the average flight delay in Table 1 is 10.4, but it is only 5.2 for tuples covered by (, ∗, ∗). To counterbalance this low value, CAPE suggests related patterns such as (, ∗, ∗) and (, ∗, ∗), whose average delays are higher.
3.2.1 Performance Optimizations. Contrast-based methods
output patterns whose scores (e.g., risk ratios) are above a
usersupplied threshold. A general optimization used by DIFF is to also
require a minimum support threshold for the extracted patterns.
This enables pruning optimizations similar to those used by the
Apriori algorithm for frequent itemset mining [
3.2.2 Pros and Cons. By design, contrast-based methods are useful when exploring diferences between data subsets – something that coverage-based methods do not implicitly optimize for. On the other hand, these methods may not guarantee concise results. One exception is Data X-ray, which performs a set-coverlike operation on the extracted patterns as a post-processing step to eliminate redundant patterns. 3.3
Finally, we discuss three methods that select patterns based on the
information they provide about the distribution of the measure
attribute: Explanation Tables [
Table 3 shows an explanation table of size four (i.e., containing four patterns) for the binary measure attribute Full based on Table 1. In addition to values of the dimension attributes, each explanation table pattern also includes the fraction of matching tuples that have = 1. The first pattern in an explanation table is always the all-stars pattern, and, in this example, it also indicates that half the flights in the entire dataset are full. The next pattern suggests that no flights on Mondays are full, and the last two patterns indicate that three-quarters of flights to London and Frankfurt are full.
In Table 4, we show an explanation table of size four for the measure attribute Late based on Table 1. Here, each pattern includes the average value of Late across its matching tuples. Again, we start with the all-stars pattern, which states that flights are 10.4 minutes late on average. The next pattern indicates that lfights to London are 15.3 minutes late on average, and so on.
The greedy heuristic for constructing explanation tables used
in [
Returning to Table 3, the greedy algorithm starts by inserting the pattern (∗, ∗, ∗||0.5). At this point, knowing only this one piece of information, the maximum-entropy estimate of the distribution of is to assign = 0.5 to every tuple in Table 12. Next, it turns out that (, ∗, ∗||0) gives the greatest reduction in KL-divergence. Based on this new pattern, the maximumentropy estimate for tuples 10 through 14 in Table 1 changes to = 0. This revision causes the estimates of the first nine tuples to change (from 0.5 to 79 ) in order to maintain consistency with the first pattern, which asserts that = 0.5 on average over the entire table. Given the updated maximum-entropy estimate, the next pattern with the greatest reduction in KL-divergence is (∗, ∗, ||0.75), and so on.
Similar reasoning can explain how Table 4 was created. The ifrst pattern asserts that flights are late by 10.4 minutes on average. Given this estimate, (∗, ∗, ||15.3) provides the most information about the distribution of . The maximum-entropy estimate of is now updated accordingly, That is, tuples 1, 4, 6 and 11, corresponding to flights to London, receive an estimate of 15.3, and the remaining tuples receive an estimate of 8.4 to maintain consistency with the first pattern. The next most-informative pattern is then selected, and so on.
SURPRISE is a similar method, whose goal is to identify surprising fragments of a dataset where the distribution of the measure attribute is diferent than what the user has seen so far. Suppose the user queries Table 1 and finds out that flights are 10.4 minutes late on average. SURPRISE finds the most informative non-overlapping and contained patterns, i.e., those which lead to the greatest reduction in KL-divergence between the true distribution of Late and the maximum-entropy estimated distribution. Restricting the output to such patterns makes it easier to update the estimated distribution. In our example, the most informative pattern is (∗, ∗, ) and its most informative subset is (∗, , ).
Finally, we discuss Shrink, which produces non-overlapping
patterns that summarize the distribution of the measure attribute
with (approximately) minimal sum of squared errors. Shrink
allows patterns with disjunctions of values and dimension
hierarchies, and uses a greedy approach in which cells in the data cube
are merged to produce patterns with the smallest squared errors.
Table 5 shows an example of a summary with two patterns that
may be considered by Shrink based on Table 1. Given the average
values of the Late measure attribute reported by the summary,
the sum of squared errors is 77.1.
2 is a binary attribute that can only be zero or one. However, for the purpose
of measuring the divergence between the true and the estimated distributions, the
maximum-entropy estimates are allowed to be real numbers between zero and one.
3.3.1 Performance Optimizations. In contrast-based methods,
the “goodness” of a pattern usually remains static throughout the
execution of the algorithm. On the other hand, the “goodness”, i.e.,
information, of a candidate explanation table pattern is relative to
the current maximum-entropy estimate of the measure attribute.
This means that a previously un-informative pattern may
become informative as more patterns are added to the explanation
table. As a result, candidate patterns cannot be easily pruned.
Instead, the explanation table construction algorithm in [
3.3.2 Pros and Cons. By design, information-based methods produce informative patterns that highlight fragments of the data with surprising distributions of the measure attribute. However, these methods tend to be expensive, especially as the number of dimension attributes grows.
In this paper, we surveyed recent data exploration methods that extract interesting or informative fragments of the data, represented as patterns over the dimension attributes. We categorized these methods according to the properties of patterns they select. Below, we ofer suggestions for future work in this area.
Benchmarks: A performance comparison of contrast-based
methods implemented within the DIFF frameworks appears in
[
New applications: Popular motivating applications that guided
the development of prior work were outlier and data error
analysis, as well as query result explanation. Recent interest in
explainable AI motivates further studies on exploring the behaviour
of black-box machine learning models such as neural networks
using multi-dimensional patterns, as was suggested in [
Correlated measure attributes: Another characteristic of prior work is that it usually formulates exploration problems involving a single measure attribute. Pattern-based exploration of multiple measure attributes is an interesting area for future work.
Feature reduction: In terms of performance and scalability, the
large number of possible patterns remains a challenge for many
methods, especially those based on information which cannot
leverage Apriori-like pruning strategies. This is an important
challenge for interactive methods that allow users to
continuously issue new exploration tasks. As a result, some techniques
such as DIFF limit the number of dimension attributes for use
in patterns and discard redundant dimension attributes such as
those functionally determined by other attributes. Distributed
versions of some methods, including DIFF [
Bringing order to dimension attributes: Much of the previous
work considers categorical dimension attributes. However, there
exist methods for covering a multi-dimensional dataset using
hyper-rectangles corresponding to intervals over numeric
dimension attributes [
Exploring data evolution: Finally, recent work motivates the
need for tools to explore how data (and metadata) change over
time [