HAN
10-ch03-083-124-9780123814791
2011/6/1
3:16
Page 107
#25
3.4 Data Reduction
107
5
10
10
9
8
7
6
5
4
3
2
1
0
15
20
25
30
price
($)
count
Figure 3.7
A histogram for price using singleton buckets—each bucket represents one price–value/
frequency pair.
1–10
11–20
21–30
price
($)
count
25
20
15
10
5
0
Figure 3.8
An equal-width histogram for price, where values are aggregated so that each bucket has a
uniform width of $10.
“How are the buckets determined and the attribute values partitioned?” There are
several partitioning rules, including the following:
Equal-width: In an equal-width histogram, the width of each bucket range is
uniform (e.g., the width of $10 for the buckets in Figure 3.8).
Equal-frequency (or equal-depth): In an equal-frequency histogram, the buckets are
created so that, roughly, the frequency of each bucket is constant (i.e., each bucket
contains roughly the same number of contiguous data samples).
HAN
10-ch03-083-124-9780123814791
2011/6/1
3:16
Page 108
#26
108
Chapter 3 Data Preprocessing
Histograms are highly effective at approximating both sparse and dense data, as
well as highly skewed and uniform data. The histograms described before for single
attributes can be extended for multiple attributes. Multidimensional histograms can cap-
ture dependencies between attributes. These histograms have been found effective in
approximating data with up to five attributes. More studies are needed regarding the
effectiveness of multidimensional histograms for high dimensionalities.
Singleton buckets are useful for storing high-frequency outliers.
3.4.7
Clustering
Clustering techniques consider data tuples as objects. They partition the objects into
groups, or clusters, so that objects within a cluster are “similar” to one another and “dis-
similar” to objects in other clusters. Similarity is commonly defined in terms of how
“close” the objects are in space, based on a distance function. The “quality” of a cluster
may be represented by its diameter, the maximum distance between any two objects in
the cluster. Centroid distance is an alternative measure of cluster quality and is defined
as the average distance of each cluster object from the cluster centroid (denoting the
“average object,” or average point in space for the cluster). Figure 3.3 showed a 2-D plot
of customer data with respect to customer locations in a city. Three data clusters are
visible.
In data reduction, the cluster representations of the data are used to replace the actual
data. The effectiveness of this technique depends on the data’s nature. It is much more
effective for data that can be organized into distinct clusters than for smeared data.
There are many measures for defining clusters and cluster quality. Clustering meth-
ods are further described in Chapters 10 and 11.
3.4.8
Sampling
Sampling can be used as a data reduction technique because it allows a large data set to
be represented by a much smaller random data sample (or subset). Suppose that a large
data set, D, contains N tuples. Let’s look at the most common ways that we could sample
D for data reduction, as illustrated in Figure 3.9.
Simple random sample without replacement (SRSWOR) of size s: This is created
by drawing s of the N tuples from D (s
<
N), where the probability of drawing any
tuple in D is 1
/N, that is, all tuples are equally likely to be sampled.
Simple random sample with replacement (SRSWR) of size s: This is similar to
SRSWOR, except that each time a tuple is drawn from D, it is recorded and then
replaced. That is, after a tuple is drawn, it is placed back in
D so that it may be drawn
again.
Cluster sample: If the tuples in
D are grouped into
M mutually disjoint “clusters,”
then an SRS of s clusters can be obtained, where s
<
M. For example, tuples in a
database are usually retrieved a page at a time, so that each page can be considered
HAN
10-ch03-083-124-9780123814791
2011/6/1
3:16
Page 109
#27
3.4 Data Reduction
109
Cluster sample
Startified sample
Figure 3.9
Sampling can be used for data reduction.
a cluster. A reduced data representation can be obtained by applying, say, SRSWOR
to the pages, resulting in a cluster sample of the tuples. Other clustering criteria con-
veying rich semantics can also be explored. For example, in a spatial database, we
may choose to define clusters geographically based on how closely different areas are
located.
Stratified sample: If D is divided into mutually disjoint parts called strata, a stratified
sample of D is generated by obtaining an SRS at each stratum. This helps ensure a