Module-2

Data Mining Techniques and Algorithms

Data mining is the process of discovering useful patterns and insights from
large amounts of data, combining methods from statistics, artificial intelligence,
and machine learning. It involves several steps, including data cleaning,
integration, transformation, and finally, applying specific techniques and
algorithms to extract knowledge.

Mining Techniques:
1. Classification
2. Clustering &
3. Association

1. Classification:
Classification is a forms of data analysis that can be used to extract models
describing important data classes or to predict future data trends.
Classification predicts categorical (discrete, unordered) labels.
For example, we can build a classification model to categorize bank loan
applications as either safe or risky.
Many classification methods have been proposed by researchers in machine
learning, pattern recognition, and statistics.
Most algorithms are memory resident, typically assuming a small data size.
Recent data mining research has built on such work, developing scalable
classification and prediction techniques capable of handling large disk-
resident data.
Classification by Decision Tree Induction:
Decision tree induction is the learning of decision trees from class - labeled
training tuples.
A decision tree is a flowchart-like tree structure, where
1. Each internal noded notes a test on an attribute.
2. Each branch represents an outcome of the test.
3. Each leaf node holds a class label.
[Link] topmost node in a tree is the root node.

The construction of decision tree classifiers does not require any domain
knowledge or parameter setting, and therefore I appropriate for exploratory
knowledge discovery.
Decision trees can handle high dimensional data. Their representation of
acquired knowledge in tree form is intuitive and generally easy to assimilate
by humans.
The learning and classification steps of decision tree induction are simple
and fast. In general, decision tree classifiers have good accuracy.
Decision tree induction algorithms have been used for classification in many
application areas, such as medicine, manufacturing and production,
financial analysis, astronomy, and molecular biology.
 The algorithm is called with three parameters:
o Data partition
o Attribute list
o Attribute selection method

• The parameter attribute list is a list of attributes describing the tuples.

• Attribute selection method specifies a heuristic procedure for selecting
the attribute that best discriminates the given tuples according to class.
• The tree starts as a single node, N, representing the training tuples in D.
• If the tuples in D are all of the same class, then node N becomes a leaf
and is labelled with that class .
• All of the terminating conditions are explained at the end of the
algorithm. Otherwise, the algorithm calls Attribute selection method to
determine the splitting criterion.
• The splitting criterion tells us which attribute to test at node N by
determining the ―best‖ way to separate or partition the tuples in D into
individual classes.

There are three possible scenarios.

Let A be the splitting attribute. A has v distinct values,
{a1, a2, … , av}, based on the training data.
A is discrete-valued:
In this case, the outcomes of the test at node N correspond directly to the
known values of A.
A branch is created for each known value, aj, of A and labeled with that value.
A need not be considered in any future partitioning of the tuples.
A is continuous-valued:
In this case, the test at node N has two possible outcomes, corresponding to
the conditions
A <=split point and A >split point, respectively
Where split point is the split-point returned by Attribute selection method as
part of thesplitting criterion.
A is discrete-valued and a binary tree must be produced:
The test at node N is of the form―A€SA?‖.
SA is the splitting subset for A, returned by Attribute selection method as part
of the splitting criterion. It is a subset of the known values of A.

Naïve Bayesian Classification:

The naïve Bayesian classifier, or simple Bayesian classifier, works as follows:
[Link] D be a training set of tuples and their associated class labels. As usual,
each tuple is represented by an n-dimensional attribute vector, X = (x1, x2,
…,xn), depicting n measurements made on the tuple from n attributes,
respectively, A1, A2, …, An.
2. Suppose that there are m classes, C1, C2, …, Cm. Given a tuple, X, the
classifier willpredict that X belongs to the class having the highest posterior
probability, conditioned on X.
That is, the naïve Bayesian classifier predicts that tuple X belongs to the class Ci
if and only if

Thus we maximize P(CijX). The class Ci for which P(CijX) is maximized is called
the maximum posteriori hypothesis.
By Bayes’ theorem

3 .As P(X) is constant for all classes, only P(X|Ci)P(Ci) need be maximized. If the
class prior probabilities are not known, then it is commonly assumed that the
classes are equally likely, that is, P(C1) = P(C2) = …= P(Cm), and we would
therefore maximize P(X|Ci).
Otherwise, we maximize P(X|Ci)P(Ci).
4 .Given data sets with many attributes, it would be extremely computationally
expensive to compute P(X|Ci). In order to reduce computation in evaluating
P(X|Ci), the naive assumption of class conditional independence is made. This
presumes that the values of the attributes are conditionally independent of
one another, given the class label of the tuple. Thus,

We can easily estimate the probabilities P(x1|Ci), P(x2|Ci), : : : , P(xn|Ci) from

the training tuples. For each attribute, we look at whether the attribute is
categorical or continuous-valued. For instance, to compute P(X|Ci), we
consider the following:
➢ If Akis categorical, then P(xk|Ci) is the number of tuples of class Ciin D
having the value x k for Ak, divided by |Ci,D| the number of tuples of
class Ciin D.
➢ If Akis continuous-valued, then we need to do a bit more work, but the
calculation is pretty straightforward.
A continuous-valued attribute is typically assumed to have a Gaussian
distribution with a mean μ and standard deviation , defined by
[Link] order to predict the class label of X, P(XjCi)P(Ci) is evaluated for each class
Ci.
The classifier predicts that the class label of tuple X is the class Ci if and only i

k-Nearest-Neighbor Classifier:
➢ Nearest-neighbor classifiers are based on learning by analogy, that is, by
comparing a given test tuple with training tuples that are similar to it.

➢ The training tuples are described by n attributes. Each tuple represents a

point in an n dimensional space. In this way, all of the training tuples are
stored in an n-dimensional pattern space. When given an unknown
tuple, a k-nearest-neighbor classifier searches the pattern space for the k
training tuples that are closest to the unknown tuple. These k training
tuples are the k nearest neighbors of the unknown tuple.
➢ Closeness is defined in terms of a distance metric, such as Euclidean
distance.
➢ The Euclidean distance between two points or tuples, say, X1 = (x11, x12,
… , x1n) and X2 = (x21, x22, … ,x2n), is

In other words, for each numeric attribute, we take the difference between the
corresponding values of that attribute in tuple X1and in tuple X2, square this
difference, and accumulate it.
The square root is taken of the total accumulated distance count.
Min-Max normalization can be used to transform a value v of a numeric
attribute A to v0 in the range [0, 1] by computing where min A and max A are
the minimum and maximum values of attribute A
For k-nearest-neighbor classification, the unknown tuple is assigned the most
common class among its k nearest neighbors.

• For k-nearest-neighbor classification, the unknown tuple is assigned the

most commonclass among its k nearest neighbors.
• When k = 1, the unknown tuple is assigned the class of the training tuple
that is closest to it in pattern space.
• Nearestneighbor classifiers can also be used for prediction, that is, to
return a real-valued prediction for a given unknown tuple.
• In this case, the classifier returns the average value of the real-valued
labels associated with the k nearest neighbors of the unknown tuple.
Cluster Analysis:
• The process of grouping a set of physical or abstract objects into classes
of similar objects is called clustering.
• A cluster is a collection of data objects that are similar to one another
within the same cluster and are dissimilar to the objects in other
clusters.
• A cluster of data objects can be treated collectively as one group and so
may be considered as a form of data compression.
• Cluster analysis tools based on k-means, k-medoids, and several methods
have also been built into many statistical analysis software packages or
systems, such as S-Plus, SPSS, and SAS.

[Link] K-Means Method:

The k-means algorithm takes the input parameter, k, and partitions a set
of n objects into k clusters so that the resulting intra cluster similarity is
high but the inter cluster similarity is low.
Cluster similarity is measured in regard to the mean value of the objects
in a cluster, which can be viewed as the cluster’s centroid or center of
gravity.
The k-means algorithm proceeds as follows.
• First, it randomly selects k of the objects, each of which initially
represents a cluster mean or center.
• For each of the remaining objects, an object is assigned to the
cluster to which it is the most similar, based on the distance
between the object and the cluster mean.
• It then computes the new mean for each cluster. This process
iterates until the criterion function converges.
Typically, the square-error criterion is used, defined as

Where E is the sum of the square error for all objects in the data set
P is the point in space representing a given object mi is the mean of
cluster Ci.
The k-means partitioning algorithm:
The k-means algorithm for partitioning, where each cluster’s center is
represented by the mean value of the objects in the cluster.
[Link] Methods:
A hierarchical method creates a hierarchical decomposition of the given
set of data objects. A hierarchical method can be classified as being
either agglomerative or divisive, based on how the hierarchical
decomposition is formed.
❖ The agglomerative approach, also called the bottom-up approach, starts
with each object forming a separate group. It successively merges the
objects or groups that are close to one another, until all of the groups are
merged into one or until a termination condition holds.
❖ The divisive approach, also called the top-down approach, starts with all
of the objects in the same cluster. In each successive iteration, a cluster
is split up into smaller clusters, until eventually each object is in one
cluster, or until a termination condition holds.
Hierarchical methods suffer from the fact that once a step (merge or split) is
done, it can never be undone. This rigidity is useful in that it leads to smaller
computation costs by not having to worry about a combinatorial number of
different choices.
There are two approaches to improving the quality of hierarchical clustering:
❖ Perform careful analysis of object ―linkages‖ at each hierarchical
partitioning, such as in Chameleon, or
❖ Integrate hierarchical agglomeration and other approaches by first using
a hierarchical agglomerative algorithm to group objects into micro
clusters, and then performing macro clustering on the micro clusters
using another clustering method such as iterative relocation.
Association Rule Mining:
Association rule mining is a popular and well researched method for
discovering interesting relations between variables in large databases.
It is intended to identify strong rules discovered in databases using different
measures of interestingness.
Based on the concept of strong rules, Rakesh Agrawal et al. introduced
association rules.
[Link] basket analysis:
This process analyzes customer buying habits by finding associations between
the different items that customers place in their shopping baskets. The
discovery of such association scan help retailers develop marketing strategies
by gaining insight into which items are frequently purchased together by
customers. For instance, if customers are buying milk, how likely are they to
also buy bread (and what kind of bread) on the same trip to the supermarket.
Such information can lead to increased sales by helping retailers do selective
marketing and plan their shelf space.
[Link] Algorithm
✓ Apriori is a seminal algorithm proposed by R. Agrawal and R. Srikant in
1994 for mining frequent item sets for Boolean association rules.
✓ The name of the algorithm is based on the fact that the algorithm uses
prior knowledge of frequent itemset properties.
✓ Apriori employs an iterative approach known as a level-wise search,
where k-itemsets are used to explore (k+1)-item sets.
✓ First, the set of frequent 1-itemsets is found by scanning the database to
accumulate the count for each item, and collecting those items that
satisfy minimum support.
✓ The resulting set is denoted [Link], L1 is used to find L2, the set of
frequent 2-itemsets, which is used to find L3, and so on, until no more
frequent k-item sets can be found.
✓ The finding of each Lkrequires one full scan of the database.
✓ A two-step process is followed in Apriori consisting of join and prune
action.
Steps:
1. In the first iteration of the algorithm, each item is a member of the
set of candidate1- itemsets, C1. The algorithm simply scans all of the
transactions in order to countthe number of occurrences of each
item.

2. Suppose that the minimum support count required is 2, that is, min
sup = 2. The set of frequent 1-itemsets, L1, can thenbe determined. It
consists of the candidate 1-itemsets satisfying minimum [Link] our
example, all of the candidates in C1 satisfy minimum support.

3. To discover the set of frequent 2-itemsets, L2, the algorithm uses the
join L1 on L1 togenerate a candidate set of 2-itemsets, [Link] candidates
are removed fromC2 during the prune step because each subset of
thecandidates is also frequent.

4. Next, the transactions inDare scanned and the support count of each
candidate itemsetInC2 is accumulated.

5. The set of frequent 2-itemsets, L2, is then determined, consisting of

those candidate2- itemsets in C2 having minimum support.
 6. The generation of the set of candidate 3-itemsets,C3, Fromthejoin
step, we first getC3 =L2x L2 = ({I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3,
I4},{I2, I3, I5}, {I2, I4, I5}. Based on the Apriori property that all subsets of
a frequentitemsetmust also be frequent, we can determine that the four
latter candidates cannotpossibly be frequent.

7. The transactions in D are scanned in order to determine L3, consisting

of those candidate 3-itemsets in C3 having minimum support.

8. The algorithm uses L3x L3 to generate a candidate set of 4-itemsets,

C4.
 3 Frequent Pattern Mining:
Frequent patternmining can be classified in various ways, based on the
following criteria:
1. Based on the completeness of patterns to be mined:
• We can mine the complete set of frequent itemsets, the closed frequent
itemsets, and the maximal frequent itemsets, given a minimum support
threshold.
• We can also mine constrained frequent itemsets, approximate frequent
itemsets,nearmatch frequent itemsets, top-k frequent itemsets and so
on.

2. Based on the levels of abstraction involved in the rule set:

Some methods for associationrule mining can find rules at differing levels of
abstraction. For example, supposethat a set of association rules mined
includes the following rules where X is a variablerepresenting a customer:
buys(X, ―computer‖))=>buys(X, ―HP printer‖) (1)
buys(X, ―laptop computer‖)) =>buys(X, ―HP printer‖) (2)
In rule (1) and (2), the items bought are referenced at different levels
ofabstraction (e.g., ―computer‖ is a higher-level abstraction of ―laptop
computer‖).
3. Based on the number of data dimensions involved in the rule:
• If the items or attributes in an association rule reference only one
dimension, then it is a single-dimensional association rule.
buys(X, ―computer‖))=>buys(X, ―antivirus software‖)

• If a rule references two or more dimensions, such as the dimensions

age, income, and buys, then it is amultidimensional association rule.
The following rule is an exampleof a multidimensional rule:
age(X, ―30,31…39‖) ^ income(X, ―42K,…48K‖))=>buys(X, ―high resolution
TV‖)
4. Based on the types of values handled in the rule:

• If a rule involves associations between the presence or absence of items,

it is a Boolean association rule.
• If a rule describes associations between quantitative items or attributes,
then it is a quantitative association rule.

5. Based on the kinds of rules to be mined:

• Frequent pattern analysis can generate various kinds of rules and

other interesting relationships.
• Association rule mining can generate a large number of rules, many of
which are redundant or do not indicate a correlation relationship
among itemsets.
• The discovered associations can be further analyzed to uncover
statistical correlations, leading to correlation rules.

6. Based on the kinds of patterns to be mined:

• Many kinds of frequent patterns can be mined from different kinds
of data sets.
• Sequential pattern mining searches for frequent sub sequences in
a sequence data set, where a sequence records an ordering of
events.
• For example, with sequential pattern mining, we can study the
order in which items are frequently purchased.
• For instance, customers may tend to first buy a PC, followed by a
digital camera,and then a memory card.
• Structured pattern mining searches for frequent sub structures in
a structured data set.
• Single items are the simplest form of structure. Each element of
an itemset may contain a subsequence, a subtree, and so on.
• Therefore, structured pattern mining can be considered as the
most general form of frequent pattern mining.
Evaluation Methods
Evaluating the performance of data mining models is crucial to ensure their
effectiveness .

1. Confusion Matrix

• Confusion matrix creates a N X N matrix, where N is the number of

classes or categories that are to be predicted. Here we have N = 2,
so we get a 2 X 2 matrix.
• Suppose there is a problem with our practice which is a binary
classification. Samples of that classification belong to either Yes or
No. So, we build our classifier which will predict the class for the
new input sample. After that, we tested our model with 165
samples and we get the following result.

2. Precision

➢ It measures how many of the positive predictions made by the model are
actually correct. It's useful when the cost of false positives is high such as
in medical diagnoses where predicting a disease when it’s not present
can have serious consequences.
TP
Precision =
TP + FP
Where:
• TP = True Positives
• FP = False Positives
Precision helps ensure that when the model predicts a positive outcome, it’s
likely to be correct.
3. Recall
Recall or Sensitivity measures how many of the actual positive cases were
correctly identified by the model. It is important when missing a positive case
(false negative) is more costly than false positives.
TP
Recall =
TP + FN
Where:
• FN = False Negatives
In scenarios where catching all positive cases is important (like disease
detection), recall is a key metric.

ROC Curve
It is a graphical representation of the True Positive Rate (TPR) vs the False
Positive Rate (FPR) at different classification thresholds. The curve helps us
visualize the trade-offs between sensitivity (TPR) and specificity (1 - FPR) across
various thresholds. Area Under Curve (AUC) quantifies the overall ability of the
model to distinguish between positive and negative classes.
• AUC = 1: Perfect model (always correctly classifies positives and
negatives).
• AUC = 0.5: Model performs no better than random guessing.
• AUC < 0.5: Model performs worse than random guessing (showing that
the model is inverted).
ROC Curve for Evaluation of Classification Models