HAN
10-ch03-083-124-9780123814791
2011/6/1
3:16
Page 105
#23
3.4 Data Reduction
105
1.
Stepwise forward selection: The procedure starts with an empty set of attributes as
the reduced set. The best of the original attributes is determined and added to the
reduced set. At each subsequent iteration or step, the best of the remaining original
attributes is added to the set.
2.
Stepwise backward elimination: The procedure starts with the full set of attributes.
At each step, it removes the worst attribute remaining in the set.
3.
Combination of forward selection and backward elimination: The stepwise for-
ward selection and backward elimination methods can be combined so that, at each
step, the procedure selects the best attribute and removes the worst from among the
remaining attributes.
4.
Decision tree induction: Decision tree algorithms (e.g., ID3, C4.5, and CART) were
originally intended for classification. Decision tree induction constructs a flowchart-
like structure where each internal (nonleaf) node denotes a test on an attribute, each
branch corresponds to an outcome of the test, and each external (leaf) node denotes a
class prediction. At each node, the algorithm chooses the “best” attribute to partition
the data into individual classes.
When decision tree induction is used for attribute subset selection, a tree is con-
structed from the given data. All attributes that do not appear in the tree are assumed
to be irrelevant. The set of attributes appearing in the tree form the reduced subset
of attributes.
The stopping criteria for the methods may vary. The procedure may employ a threshold
on the measure used to determine when to stop the attribute selection process.
In some cases, we may want to create new attributes based on others. Such attribute
construction
6
can help improve accuracy and understanding of structure in high-
dimensional data. For example, we may wish to add the attribute
area based on the
attributes height and width. By combining attributes, attribute construction can dis-
cover missing information about the relationships between data attributes that can be
useful for knowledge discovery.
3.4.5
Regression and Log-Linear Models: Parametric
Data Reduction
Regression and log-linear models can be used to approximate the given data. In (simple)
linear regression, the data are modeled to fit a straight line. For example, a random
variable, y (called a response variable), can be modeled as a linear function of another
random variable, x (called a predictor variable), with the equation
y = wx + b,
(3.7)
where the variance of
y is assumed to be constant. In the context of data mining,
x and
y
are numeric database attributes. The coefficients, w and b (called regression coefficients),
6
In the machine learning literature, attribute construction is known as feature construction.
HAN
10-ch03-083-124-9780123814791
2011/6/1
3:16
Page 106
#24
106
Chapter 3 Data Preprocessing
specify the slope of the line and the y-intercept, respectively. These coefficients can
be solved for by the method of least squares, which minimizes the error between the
actual line separating the data and the estimate of the line. Multiple linear regression
is an extension of (simple) linear regression, which allows a response variable, y, to be
modeled as a linear function of two or more predictor variables.
Log-linear models approximate discrete multidimensional probability distributions.
Given a set of tuples in n dimensions (e.g., described by n attributes), we can con-
sider each tuple as a point in an n-dimensional space. Log-linear models can be used
to estimate the probability of each point in a multidimensional space for a set of dis-
cretized attributes, based on a smaller subset of dimensional combinations. This allows
a higher-dimensional data space to be constructed from lower-dimensional spaces.
Log-linear models are therefore also useful for dimensionality reduction (since the
lower-dimensional points together typically occupy less space than the original data
points) and data smoothing (since aggregate estimates in the lower-dimensional space
are less subject to sampling variations than the estimates in the higher-dimensional
space).
Regression and log-linear models can both be used on sparse data, although their
application may be limited. While both methods can handle skewed data, regression
does exceptionally well. Regression can be computationally intensive when applied to
high-dimensional data, whereas log-linear models show good scalability for up to 10 or
so dimensions.
Several software packages exist to solve regression problems. Examples include SAS
(www.sas.com), SPSS (www.spss.com), and S-Plus (www.insightful.com). Another useful
resource is the book Numerical Recipes in C, by Press, Teukolsky, Vetterling, and Flannery
[PTVF07], and its associated source code.
3.4.6
Histograms
Histograms use binning to approximate data distributions and are a popular form
of data reduction. Histograms were introduced in Section 2.2.3. A histogram for an
attribute, A, partitions the data distribution of A into disjoint subsets, referred to as
buckets or
bins. If each bucket represents only a single attribute–value/frequency pair, the
buckets are called singleton buckets. Often, buckets instead represent continuous ranges
for the given attribute.
Example 3.3
Histograms. The following data are a list of AllElectronics prices for commonly sold
items (rounded to the nearest dollar). The numbers have been sorted: 1, 1, 5, 5, 5,
5, 5, 8, 8, 10, 10, 10, 10, 12, 14, 14, 14, 15, 15, 15, 15, 15, 15, 18, 18, 18, 18, 18,
18, 18, 18, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 25, 25, 25, 25, 25, 28, 28, 30,
30, 30.
Figure 3.7 shows a histogram for the data using singleton buckets. To further reduce
the data, it is common to have each bucket denote a continuous value range for
the given attribute. In Figure 3.8, each bucket represents a different $10 range for
price.