Data Mining. Concepts and Techniques, 3rd Edition

HAN

10-ch03-083-124-9780123814791

2011/6/1

3:16

Page 99

#17

3.4 Data Reduction

99

the purchaser’s name and address instead of a key to this information in a purchaser

database, discrepancies can occur, such as the same purchaser’s name appearing with

different addresses within the purchase order database.

3.3.4

Data Value Conflict Detection and Resolution

Data integration also involves the detection and resolution of data value conflicts. For

example, for the same real-world entity, attribute values from different sources may dif-

fer. This may be due to differences in representation, scaling, or encoding. For instance,

a weight attribute may be stored in metric units in one system and British imperial

units in another. For a hotel chain, the price of rooms in different cities may involve

not only different currencies but also different services (e.g., free breakfast) and taxes.

When exchanging information between schools, for example, each school may have its

own curriculum and grading scheme. One university may adopt a quarter system, offer

three courses on database systems, and assign grades from A+ to F, whereas another

may adopt a semester system, offer two courses on databases, and assign grades from 1

to 10. It is difficult to work out precise course-to-grade transformation rules between

the two universities, making information exchange difficult.

Attributes may also differ on the abstraction level, where an attribute in one sys-

tem is recorded at, say, a lower abstraction level than the “same” attribute in another.

For example, the total sales in one database may refer to one branch of All Electronics,

while an attribute of the same name in another database may refer to the total sales

for All Electronics stores in a given region. The topic of discrepancy detection is further

described in Section 3.2.3 on data cleaning as a process.

3.4

Data Reduction

Imagine that you have selected data from the AllElectronics data warehouse for analysis.

The data set will likely be huge! Complex data analysis and mining on huge amounts of

data can take a long time, making such analysis impractical or infeasible.

Data reduction techniques can be applied to obtain a reduced representation of the

data set that is much smaller in volume, yet closely maintains the integrity of the original

data. That is, mining on the reduced data set should be more efficient yet produce the

same (or almost the same) analytical results. In this section, we first present an overview

of data reduction strategies, followed by a closer look at individual techniques.

3.4.1

Overview of Data Reduction Strategies

Data reduction strategies include dimensionality reduction, numerosity reduction, and

data compression.

Dimensionality reduction is the process of reducing the number of random variables

or attributes under consideration. Dimensionality reduction methods include wavelet

---

HAN

10-ch03-083-124-9780123814791

2011/6/1

3:16

Page 100

#18

100

Chapter 3 Data Preprocessing

transforms (Section 3.4.2) and principal components analysis (Section 3.4.3), which

transform or project the original data onto a smaller space. Attribute subset selection is a

method of dimensionality reduction in which irrelevant, weakly relevant, or redundant

attributes or dimensions are detected and removed (Section 3.4.4).

Numerosity reduction techniques replace the original data volume by alternative,

smaller forms of data representation. These techniques may be parametric or non-

parametric. For parametric methods, a model is used to estimate the data, so that

typically only the data parameters need to be stored, instead of the actual data. (Out-

liers may also be stored.) Regression and log-linear models (Section 3.4.5) are examples.

Nonparametric methods for storing reduced representations of the data include his-

tograms (Section 3.4.6), clustering (Section 3.4.7), sampling (Section 3.4.8), and data

cube aggregation (Section 3.4.9).

In data compression, transformations are applied so as to obtain a reduced or “com-

pressed” representation of the original data. If the original data can be reconstructed

from the compressed data without any information loss, the data reduction is called

lossless. If, instead, we can reconstruct only an approximation of the original data, then

the data reduction is called lossy. There are several lossless algorithms for string com-

pression; however, they typically allow only limited data manipulation. Dimensionality

reduction and numerosity reduction techniques can also be considered forms of data

compression.

There are many other ways of organizing methods of data reduction. The computa-

tional time spent on data reduction should not outweigh or “erase” the time saved by

mining on a reduced data set size.

3.4.2

Wavelet Transforms

The discrete wavelet transform (DWT) is a linear signal processing technique that,

when applied to a data vector X, transforms it to a numerically different vector, X , of

wavelet coefficients. The two vectors are of the same length. When applying this tech-

nique to data reduction, we consider each tuple as an n-dimensional data vector, that

is, X = (x

1

, x

2

,

...,x

n

), depicting n measurements made on the tuple from n database

attributes.

3

“How can this technique be useful for data reduction if the wavelet transformed data are

of the same length as the original data?” The usefulness lies in the fact that the wavelet

transformed data can be truncated. A compressed approximation of the data can be

retained by storing only a small fraction of the strongest of the wavelet coefficients.

For example, all wavelet coefficients larger than some user-specified threshold can be

retained. All other coefficients are set to 0. The resulting data representation is therefore

very sparse, so that operations that can take advantage of data sparsity are computa-

tionally very fast if performed in wavelet space. The technique also works to remove

noise without smoothing out the main features of the data, making it effective for data

3

In our notation, any variable representing a vector is shown in bold italic font; measurements depicting

the vector are shown in italic font.

---