Data Mining_ Concepts and Techniques - Jiawei Han [144]
Supporting OLAP roll-up and drill-down operations on a prediction cube is a computational challenge requiring the materialization of cell values at many different granularities. For simplicity, we can consider only full materialization. A na ve way to fully materialize a prediction cube is to exhaustively build models and evaluate them for each cell and granularity. This method is very expensive if the base data set is large. An ensemble method called Probability-Based Ensemble (PBE) was developed as a more feasible alternative. It requires model construction for only the finest-grained cells. OLAP-style bottom-up aggregation is then used to generate the values of the coarser-grained cells.
The prediction of a predictive model can be seen as finding a class label that maximizes a scoring function. The PBE method was developed to approximately make the scoring function of any predictive model distributively decomposable. In our discussion of data cube measures in Section 4.2.4, we showed that distributive and algebraic measures can be computed efficiently. Therefore, if the scoring function used is distributively or algebraically decomposable, prediction cubes can also be computed with efficiency. In this way, the PBE method reduces prediction cube computation to data cube computation.
For example, previous studies have shown that the naïve Bayes classifier has an algebraically decomposable scoring function, and the kernel density–based classifier has a distributively decomposable scoring function. 8 Therefore, either of these could be used to implement prediction cubes efficiently. The PBE method presents a novel approach to multidimensional data mining in cube space.
8Naïve Bayes classifiers are detailed in Chapter 8. Kernel density–based classifiers, such as support vector machines, are described in Chapter 9.
5.4.2. Multifeature Cubes: Complex Aggregation at Multiple Granularities
Data cubes facilitate the answering of queries as they allow the computation of aggregate data at multiple granularity levels. Traditional data cubes are typically constructed on commonly used dimensions (e.g., time, location, and product) using simple measures (e.g., count(), average(), and sum()). In this section, you will learn a newer way to define data cubes called multifeature cubes. Multifeature cubes enable more in-depth analysis. They can compute more complex queries of which the measures depend on groupings of multiple aggregates at varying granularity levels. The queries posed can be much more elaborate and task-specific than traditional queries, as we shall illustrate in the next examples. Many complex data mining queries can be answered by multifeature cubes without significant increase in computational cost, in comparison to cube computation for simple queries with traditional data cubes.
To illustrate the idea of multifeature cubes, let's first look at an example of a query on a simple data cube.
A simple data cube query
Let the query be “Find the total sales in 2010, broken down by item, region, and month, with subtotals for each dimension.” To answer this query, a traditional data cube is constructed that aggregates the total sales at the following eight different granularity levels: {(item, region, month), (item, region), (item, month), (month, region), (item), (month), (region), ()}, where () represents all. This data cube is simple in that it does not involve any dependent aggregates.
To illustrate what is meant by “dependent aggregates,” let's examine a more complex query, which can be computed with a multifeature cube.
A complex query involving dependent aggregates
Suppose the query is “Grouping by all subsets of {item, region, month}, find the maximum price in 2010 for each group and the total sales among all maximum price