Unit-II

Data Mining Techniques

 These techniques not only require specific types of data structures, but also
imply certain types of algorithmic approaches
 Parametric models describe the relationship between input and output
through the use of algebraic equations where some parameters are not
specified
 Nonparametric techniques are more appropriate for data mining applications.
A nonparametric model is one that is data-driven
 Parametric methods require more knowledge about the data before the
modelling process, the nonparametric technique requires a large amount of
data as input to the modelling process itself
 Nonparametric techniques include neural networks, decision trees, and
genetic algorithms

A Statistical Perspective on data mining

Statistical concepts data mining techniques are:

1. Point Estimation
2. Models Based on Summarization
3. Bayes Theorem
4. Hypothesis Testing
5. Regression and Correlation

Point Estimation

 Refers to the process of estimating a population parameter Ꙫ by an

estimate of the parameter .
 An estimator technique may also be used to estimate (predict) the value of
missing data.
 The bias of an estimator is the difference between the expected value of
the estimator and the actual value:

 An unbiased estimator is one whose bias is 0.
 While point estimators for small data sets may actually be unbiased, for
larger database applications we would expect that most estimators are
biased.
 One measure of the effectiveness of an estimate is the mean squared error
(MSE), which is defined as the expected value of the squared difference
between the estimate and the actual value:

 The squared error is often examined for a specific prediction to

measure accuracy rather than to look at the average difference
Example,
If the true value for an attribute was 10 and the prediction was 5, the
squared error would be (5 - 10)2 = 25.
 To determine a range of values within which the true parameter value
should is called a confidence interval.
 The root mean square (RMS) may also be used to estimate error or
as another statistic to describe a distribution.
 Given a set of n values X = {x1 , ... , xn}, the RMS is defined by

 The root mean square error (RMSE) is found by taking the square
root of the MSE.
 A popular estimating technique is the jackknife estimate. With this
approach, the estimate of a parameter, Ӫ, is obtained by omitting one
value from the set of observed values.
 Suppose that there is a set of n values X = {x1, . . . , Xn}. An
estimate for the mean would be
Here the subscript (i) indicates that this estimate is obtained by omitting the i th
value. Given a set of jackknife estimates, Ӫ(i) , these can in tum be used to obtain
an overall estimate

Another technique for point estimation is called the maximum likelihood estimate
(MLE). Likelihood can be defined as a value proportional to the actual probability
that with a specific distribution the given sample exists.

The likelihood function, L, is thus defined as

The value of Ꙫ that maximizes L is the estimate chosen.

The expectation-maximization (EM) algorithm is an approach that solves the
estimation problem with incomplete data.

The EM algorithm finds an MLE for a parameter using a two-step process:

estimation and maximization

The expectation part of the algorithm estimates the missing values using the current estimates of
Ꙫ. This can initially be done by finding a weighted average of the observed data
Models Based on Summarization

 There are many basic concepts that provide an abstraction and

summarization of the data as a whole.
 The basic well-known statistical concepts such as mean, variance, standard
deviation, median, and mode are simple models of the underlying
population. Fitting a population to a specific frequency distribution provides
an even better model of the data.
 There are also many well-known techniques to display the structure of the
data graphically. For example, a histogram shows the distribution of the
data.
 A box plot is a more sophisticated technique that illustrates several different
features of the population at once.

Figure 3.1 shows a sample box plot.

Another visual technique to display data is called Scatter diagram. This is a graph
on a two-dimensional axis of points representing the relationships between x and y
values. By plotting the actually observable (x, y) points as seen in a sample, a
visual image of some derivable functional relationship between the x and y values
in the total population may be seen. Figure 3.2 shows a scatter diagram that plots
some observed values.

Bayes Theorem
With statistical inference, information about a data distribution are inferred by examining data that
follow that distribution.

Given a set of data X = {x1, ... , x11 }, a data mining problem is to uncover properties of the distribution
from which the set comes.

Bayes rule, defined in Definition

Example
Example

Hypothesis Testing

 Hypothesis testing attempts to find a model that explains the observed data
by first creating a hypothesis and then testing the hypothesis against the
data.
 The hypothesis usually is verified by examining a data sample.
 Given a population, the initial (assumed) hypothesis to be tested, Ho, is
called the null hypothesis.
 Rejection of the null hypothesis causes another hypothesis, H1 , called the
alternative hypothesis, to be made.
 One technique to perform hypothesis testing is based on the use of the chi-
squared statistic.
 chi squared procedures can be used to test the association between two
observed variable values and to determine if a set of observed variable
values is statistically significant.
 A hypothesis is first made, and then the observed values are compared
based on this hypothesis.
 Assuming that O represents the observed data and E is the expected values
based on the hypothesis, the chi-squared statistic, x2 , is defined as:

When comparing a set of observed variable values to determine statistical

significance, the values are compared to those of the expected case.

Example

Suppose that there are five schools being compared based on students' results on a set of
standardized achievement tests.
Total score for the schools is 375, so the expected result would be that each school has
an average score of 75.
The actual average scores from the schools are: 50, 93, 67, 78, and 87.
The chi-squared measure here is

Examining a chi-squared significance table, it is found that tltis value is significant. With
a degree of freedom of 4 and a significance level of 95%, the critical value is 9.488.
Thus, the administrators observe that the variance between the schools' scores and the
expected values cannot be associated with pure chance.

Figure illustrates the more general use of linear regression with one input
value.

The line generated by the linear regression technique is shown in the fig.
 To use the generated linear model to predict an output value given an input
value.

Correlation is the problems of determining how much alike the two variables
actually are. One standard formula to measure linear correlation is the
correlation coefficient r. Given two variables, X and Y, the correlation
coefficient is a real value r € [- 1, 1]. A positive number indicates a positive
correlation, whereas a negative number indicates a negative correlation.
Here negative correlation indicates that one variable increases while the
other decreases in value. The closer the value of r is to 0, the smaller the
correlation. A perfect relationship exists with a value of 1 or -1, whereas no
correlation exists with a value of 0.

The value for r is defined as

SIMILARITY MEASURES

The objective is to define the similarity mapping such that documents that are more
alike have a higher similarity value
The following are desirable characteristics of a good similarity measure:

For IR example. Each IR query provides the class definition in the form of the IR
query itself. So the classification problem then becomes one of determining
similarity not among all tuples in the database but between each tuple and the
query. This makes the problem an O (n) problem rather than an O (n 2 ) problem.
Here are some of the more common similarity measures used in traditional IR
systems and more recently in Internet search engines:

In these formulas it is assumed that similarity is being evaluated between two

vectors ti= (ti1, . . . , tik) and tj = {tj1, ... , tjk ), and vector entries usually are
assumed to be nonnegative numeric values.
Distance or dissimilarity measures are often used instead of similarity measures.
As implied, these measure how "unlike" items are. Traditional distance measures
may be used in a two-dimensional space. These include

To compensate for the different scales between different attribute values, the
attribute values may be normalized to be in the range [0, 1].

DECISION TREE
A decision tree is a predictive modeling technique used in classification, clustering,
and prediction tasks. Decision trees use a "divide and conquer" technique to split
the problem search space into subsets.

DEFINITION.
A decision tree (DT) is a tree where the root and each internal node is labeled with
a question. The arcs emanating from each node represent each possible answer to
the associated question. Each leaf node represents a prediction of a solution to the
problem under consideration.
A decision tree (DT) model is a computational model consisting of three parts:
1. A decision tree as defined in Definition
2. An algorithm to create the tree.
3. An algorithm that applies the tree to data and solves the problem under
consideration.

Example:

This tree has as the root the first question asked. Each subsequent level in the tree
consists of questions at that stage in the game. Nodes at the third level show
questions asked at the third level in the game.
Leaf nodes represent a successful guess as to the object being predicted. This
represents a correct prediction.
 Example
Suppose that students in a particular university are to be classified as short, tall, or
medium based on their height.
A female who is 1.95 m in height is considered as tall, while a male of the same
height may not be considered tall. Also, a child 10 years of age may be tall if he or
she is only 1.5 m. Since this is a set of university students, we would expect most
of them to be over 17 years of age. We thus decide to filter out those under this age
and perform their classification' separately

Figure: Decision Tree Example

NEURAL NETWORKS
 Neural networks (NN), often referred to as artificial neural networks (ANN)
to distinguish them from biological neural networks, are modeled after the
workings of the human brain
 The NN, then, is structured as a directed graph with many nodes (processing
elements) and arcs (interconnections) between them. The nodes in the graph
are like individual neurons, while the arcs are their interconnections.
 The NN approach, like decision trees, requires that a graphical structure be
built to represent the model and then that the structure be applied to the data.

The NN can be viewed as a directed graph with source (input), sink (output),
and internal (hidden) nodes.
 The input nodes exist in a input layer, while the output nodes exist in an
output layer. The hidden nodes exist over one or more hidden layers
 To perform the data mining task, a tuple is input through the input nodes and
the output node determines what the prediction is.

Example

Each node is labeled with a function that indicates its effect on the data coming
into that node. At the input layer, functions f1 and f2 simply take the
corresponding attribute value in and replicate it as output on each of the arcs
coming out of the node. The functions at the hidden layer, f3 and f4, and those
at the output layer, f5, f6 and f7, perform more complicated functions. The arcs
are all labeled with weights, where Wij is the weight between nodes i and j.
During processing, the functions at each node are applied to the input data to
produce the output. For example, the output of node 3 is
 where h and g are the input height and gender values.
A neural network in two parts: one for the data structure and one for the
general approach used, including the data structure and the algorithms
needed to use it.

A neural network (NN) model is a computational model consisting of three parts:

1. Neural network graph that defines the data structure of the neural
network.
2. Learning algorithm that indicates how learning takes place.
3. Recall techniques that determine how information is obtained from the
network.

Artificial NNs can be classified based on the type of connectivity and learning.
Figure shows a sample node, i, in a neural network. Here there are k input arcs
coming from nodes 1, 2, .... , k. with weights of W 1i, …., Wki and input values of x1i
, . . . , xki. The values that flow on these arcs are shown on dashed arcs because they
do not really exist as part of the graph itself. There is one output value yi produced.

The activation function, fi, is applied to the inputs, which are scaled by applying
the corresponding weights.

The structure of the NN may also be viewed from the perspective of matrices.
Input and weight on the arcs into node i are

There is one output value from node i, y; , which is propagated to all output
arcs during the propagation process. Using summation to combine the inputs, then,
the output of a node is

Here fi is the activation function.

Overfitting occurs when the NN is trained to fit one set of data almost
exactly. The error that occurs with the given training data is quite small; however,
when new data are examined, the error is very large.

To avoid overfitting, smaller NNs are advisable. Another approach that can
be used to avoid overfitting is to stop the learning process early. Using a larger
training set also helps.

Activation Function

The output of each node i in the NN is based on the definition of a function f i,

activation function, associated with it. An activation function is sometimes called a
processing element function or a squashing function. The function is applied to the
set of inputs coming in on the input arcs.

There have been many proposals for activation functions, including

  Threshold
 Sigmoid
 symmetric sigmoid
 Gaussian.

An activation function may also be called a firing rule, relating it back to the
workings of the human brain. When the input to a neuron is large enough, it fires,
sending an electrical signal out on its axon (output link).

When dealing only with binary output, the output is either 0 or 1, depending
on whether the neuron should fire. Some activation functions use -1 and 1 instead,
while still others output a range of values.

• Linear:

A linear activation function produces a linear output value based on the

input. The following is a typical activation function

Here c is a constant positive value.

• Threshold or step:
 The output value is either a 1 or 0, depending on the sum of the products of
the input values and their associated weights

The linear threshold function, also called a ramp function or a piecewise

linear function, the value of the activation function increases gradually from the
low value to the high value. One such function is

Here the linear increase is between T1 and T2. As with the regular threshold
function, the value may be between -1 and 1 or 0 and 1.

• Sigmoid:

An "S"-shape d curve with output values between -1 and 1 (or 0 and 1), and
which is monotomcally increasing.

A common one is the logistic function

Here c is a constant positive value that changes the slope of the function.

• Hyperbolic tangent:

A variation of the sigmoid function is the hyperbolic tangent function shown here

This function has an output centered at zero, which may help with learning.

• Gaussian:
The Gaussian function is a bell-shaped curve with output values in the range [0, 1].
A typical Gaussian function is

Here s is the mean and v is the predefined positive variance of the function.

GENETIC ALGORITHMS
In data mining, genetic algorithms may be used for clustering, prediction, and even
association rules.

When using genetic algorithms to solve a problem, the first thing, and perhaps the
most difficult task, that must be determined is how to model the problem as a set of
individuals. An individual typically is viewed as an array or tuple of values.

In genetic algorithms, reproduction is defined by precise algorithms that indicate

how to combine the given set of individuals to produce new ones. These are called
crossover algorithms.
One of the most important components of a genetic algorithm is determining how
to select individuals. A fitness function, f, is used to determine the best individuals
in a population.

Here Pli is the probability of selecting individual li . This type of selection is called
roulette ' wheel selection’.

A genetic algorithm (GA) is a computational model consisting of five parts:

1. Starting set of individuals, P.

2. Crossover technique.
3. Mutation algorithm.
4. Fitness function.
5. Algorithm that applies the crossover and mutation techniques to P iteratively
using the fitness function to determine the best individuals in P to keep.
Algorithm outlines the steps performed by a genetic algorithm. Initially, a
population of individuals, P, is created. Although different approaches can be used
to perform this step, they typically are generated randomly. From this population, a
new population, P', of the same size is created. The algorithm repeatedly selects
individuals from whom to create new ones. These parents, i1, i2, are then used to
produce two offspring, o1, o2 , using a crossover process. Then mutants may be
generated. The process continues until the new population satisfies the termination
condition.

Genetic algorithms have been used to solve most data mining problems, including
classification, clustering, and generating association rules. Typical applications of
genetic algorithms include scheduling, robotics, economics, biology, and pattern
recognition.
The major advantage to the use of genetic algorithms is that they are easily
parallelized. There are, however, many disadvantages to their use:
• Genetic algorithms are difficult to understand and to explain to end users.
• The abstraction of the problem and method to represent individuals is quite
difficult.
• Determining the best fitness function is difficult.
• Determining how to do crossover and mutation is difficult