UNIT-III

Introduction to Data Mining Approaches: Supervised and Unsupervised

Learning
Classification: Applications of classification and prediction. Issues regarding
Classification and prediction, Classification methods: Decision tree induction,
Naïve Bayesian Classification,
Association Rule Mining: Application of Association Rule Mining,
Frequent Item sets, Mining Association rules from Transactional Databases
using Apriori and FP Growth, finding relevant rule using Support, Confidence
and Lift ratio.
 Supervised and Unsupervised Learning
• Supervised learning (classification)
• Supervision: The training data (observations,
measurements, etc.) are accompanied by labels indicating
the class of the observations
• New data is classified based on the training set
• Unsupervised learning (clustering)
• The class labels of training data is unknown
• Given a set of measurements, observations, etc. with the
aim of establishing the existence of classes or clusters in the
data
2
WHAT IS CLASSIFICATION & PREDICTION?
There are two forms of data analysis that can be used for extracting models
describing important classes or to predict future data trends. These two forms
are as follows −
• Classification
• Prediction
• Classification : Predicts categorical class labels (discrete or nominal)
• Classifies data (constructs a model) based on the training set and the values
(class labels) in a classifying attribute and uses it in classifying new data
• Prediction : Model or a predictor will be constructed that predicts a
continuous-valued-function or ordered value.
 Applications of classification and prediction
• Credit/loan approval
• Medical diagnosis: if a tumor is cancerous or benign
• Fraud detection: if a transaction is fraudulent
• Web page categorization: which category it is

4
ISSUE REGARDING CLASSIFICATION & PREDICTION

The major issue is preparing the data for Classification and Prediction.
Preparing the data involves the following activities −
• Data Cleaning − Data cleaning involves removing the noise and
treatment of missing values. The noise is removed by applying
smoothing techniques and the problem of missing values is solved by
replacing a missing value with most commonly occurring value for
that attribute.
• Relevance Analysis − Database may also have the irrelevant
attributes. Correlation analysis is used to know whether any two
given attributes are related.
• Data Transformation and reduction − The data can be transformed by
any of the following methods.
• Normalization − The data is transformed using normalization.
Normalization involves scaling all values for given attribute in
order to make them fall within a small specified range.
Normalization is used when in the learning step, the neural
networks or the methods involving measurements are used.
• Generalization − The data can also be transformed by
generalizing it to the higher concept. For this purpose we can
use the concept hierarchies.
 Classification—A Two-Step Process
❖ With the help of the bank loan application that we have discussed above, let us understand the
working of classification. The Data Classification process includes two steps −
➢ Building the Classifier or Model
➢ Using Classifier for Classification
❖ Building the Classifier or Model
➢ This step is the learning step or the learning phase.
➢ In this step the classification algorithms build the classifier.
➢ The classifier is built from the training set made up of database tuples and their
associated class labels.
➢ Each tuple that constitutes the training set is referred to as a category or class. These
tuples can also be referred to as sample, object or data points.

7
Learning: Training data are analyzed by a classification [Link],the class label attribute is
loan decision, and the learned model or classifier is represented in the form of classification rules.
In this step, the classifier is used for classification. Here the test data is used to estimate
the accuracy of classification rules. The classification rules can be applied to the new
data tuples if the accuracy is considered acceptable.
Decision Tree Induction: An Example
age income student credit_rating buys_computer
<=30 high no fair no
 Training data set: Buys_computer <=30 high no excellent no
 The data set follows an example of 31…40 high no fair yes
>40 medium no fair yes
Quinlan’s ID3 (Playing Tennis) >40 low yes fair yes
 Resulting tree: >40 low yes excellent no
31…40 low yes excellent yes
age? <=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
<=30 overcast
31..40 >40 31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no

student? yes credit rating?

no fair excellent
yes

no yes no yes
10
 Algorithm for Decision Tree Induction
• Basic algorithm (a greedy algorithm)
• Tree is constructed in a top-down recursive divide-and-conquer
manner
• At start, all the training examples are at the root
• Attributes are categorical (if continuous-valued, they are
discretized in advance)
• Examples are partitioned recursively based on selected
attributes
• Test attributes are selected on the basis of a heuristic or
statistical measure (e.g., information gain)
• Conditions for stopping partitioning
• All samples for a given node belong to the same class
• There are no remaining attributes for further partitioning –
majority voting is employed for classifying the leaf
• There are no samples left
11
Algorithm: Generate decision tree. Generate a decision tree from the training tuples of data partition, D.

create a node N;
if tuples in D are all of the same class, C, then
return N as a leaf node labeled with the class C;
if attribute list is empty then
return N as a leaf node labeled with the majority class in D; // majority voting
apply Attribute selection method(D, attribute list) to find the “best” splitting criterion;
label node N with splitting criterion;
if splitting attribute is discrete-valued and
multiway splits allowed then // not restricted to binary trees
attribute list attribute list - splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion
// partition the tuples and grow subtrees for each partition
let Dj be the set of data tuples in D satisfying outcome j; // a partition
if Dj is empty then
attach a leaf labeled with the majority class in D to node N;
else attach the node returned by Generate decision tree(Dj , attribute list) to node N;
endfor
return N;
 Attribute Selection Measure:
Information Gain (ID3/C4.5)
 Select the attribute with the highest information gain
 Let pi be the probability that an arbitrary tuple in D belongs to
class Ci, estimated by |Ci, D|/|D|
 Expected information (entropy) needed to classify a tuple in D:
m
Info(D)    pi log 2 ( pi )
i1
 Information needed (after using A to split D into v partitions) to
classify D: v | D |
Info A (D)   j
 Info(D j )
j 1 | D |
 Information gained by branching on attribute A

Gain(A)  Info(D) InfoA(D)

13
 Attribute Selection: Information Gain
 Class P: buys_computer = “yes” 5 4
Infoage (D)  I (2,3)  I (4,0)
 Class N: buys_computer = “no” 14 14
9 9 5 5 5
Info(D)  I (9,5)   log 2( )  log 2( ) 0.940  I (3,2)  0.694
14 14 14 14 14
age pi ni I(pi, ni) 5
I (2,3)means “age <=30” has 5 out of 14
<=30 2 3 0.971 14 samples, with 2 yes’es and 3 no’s.
31…40 4 0 0
Hence
>40 3 2 0.971
age
<=30
income
high
student
no
credit_rating
fair
buys_computer
no
Gain(age)  Info(D)  Info age (D)  0.246
<=30 high no excellent no
31…40 high no fair yes Similarly,
>40 medium no fair yes
>40 low yes fair yes

Gain(income)  0.029
>40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30
>40
low
medium
yes
yes
fair
fair
yes
yes
Gain(student)  0.151
Gain(credit _ rating)  0.048
<=30 medium yes excellent yes
31…40 medium no excellent yes
14 31…40 high yes fair yes
>40 medium no excellent no
 Computing Information-Gain for
Continuous-Valued Attributes
• Let attribute A be a continuous-valued attribute
• Must determine the best split point for A
• Sort the value A in increasing order
• Typically, the midpoint between each pair of adjacent values is
considered as a possible split point
• (ai+ai+1)/2 is the midpoint between the values of ai and ai+1
• The point with the minimum expected information
requirement for A is selected as the split-point for A
• Split:
• D1 is the set of tuples in D satisfying A ≤ split-point, and D2 is
the set of tuples in D satisfying A > split-point
15
Gain Ratio for Attribute Selection
• Information gain measure is biased towards attributes with a
large number of values
• C4.5 (a successor of ID3) uses gain ratio to overcome the
problem (normalization to information gain)
v | Dj | | Dj |
SplitInfo A(D)    log 2 ( )
j 1 |D| |D|
• GainRatio(A) = Gain(A)/SplitInfo(A)
• Ex.

• gain_ratio(income) = 0.029/1.557 = 0.019

• The attribute with the maximum gain ratio is selected as the
splitting attribute
16
Gini Index
• If a data set D contains examples from n classes, gini index,
gini(D) is defined as n
gini(D) 1 2
 p j
j 1
where pj is the relative frequency of class j in D
• If a data set D is split on A into two subsets D1 and D2, the gini
index gini(D) is defined as
| D1 | |D 2 |
gini A (D)  gini( D 1)  gini( D 2 )
• Reduction in Impurity: |D| |D|
gini(A)  gini(D)  giniA(D)
• The attribute provides the smallest ginisplit(D) (or the largest
reduction in impurity) is chosen to split the node

17
Computation of Gini Index
• Ex. D has 9 tuples in buys_computer = “yes” and 5 in “no”
9 5
2 2
gini(D)  1       0.459
14  14 
• Suppose the attribute income partitions D into 10 in D1: {low,
medium} and 4 in D 2 giniincome{low,medium} (D)  10 Gini(D1)   4 Gini(D 2 )
 14   14 

Gini{low,high} is 0.458; Gini{medium,high} is 0.450. Thus, split on the

{low,medium} (and {high}) since it has the lowest Gini index
• All attributes are assumed continuous-valued
• May need other tools, e.g., clustering, to get the possible split
values
• Can be modified for categorical attributes 18
 Other Attribute Selection Measures
• CHAID: a popular decision tree algorithm, measure based on χ2 test for
independence

• C-SEP: performs better than info. gain and gini index in certain cases
• G-statistic: has a close approximation to χ2 distribution
• MDL (Minimal Description Length) principle (i.e., the simplest solution is
preferred):
• The best tree as the one that requires the fewest # of bits to both (1) encode
the tree, and (2) encode the exceptions to the tree

• Multivariate splits (partition based on multiple variable combinations)

• CART: finds multivariate splits based on a linear comb. of attrs.
• Which attribute selection measure is the best?
• Most give good results, none is significantly superior than others
19
 Overfitting and Tree Pruning
• Overfitting: An induced tree may overfit the training data
• Too many branches, some may reflect anomalies due to
noise or outliers
• Poor accuracy for unseen samples
• Two approaches to avoid overfitting
• Prepruning: Halt tree construction early ̵ do not split a node if
this would result in the goodness measure falling below a
threshold
• Difficult to choose an appropriate threshold
• Postpruning: Remove branches from a “fully grown” tree—
get a sequence of progressively pruned trees
• Use a set of data different from the training data to decide which is
the “best pruned tree”

20
 Enhancements to Basic Decision Tree Induction

• Allow for continuous-valued attributes

• Dynamically define new discrete-valued attributes that
partition the continuous attribute value into a discrete set of
intervals
• Handle missing attribute values
• Assign the most common value of the attribute
• Assign probability to each of the possible values
• Attribute construction
• Create new attributes based on existing ones that are
sparsely represented
• This reduces fragmentation, repetition, and replication
21
 Classification in Large Databases
• Classification—a classical problem extensively studied by
statisticians and machine learning researchers
• Scalability: Classifying data sets with millions of examples and
hundreds of attributes with reasonable speed
• Why is decision tree induction popular?
• relatively faster learning speed (than other classification
methods)
• convertible to simple and easy to understand classification
rules
• can use SQL queries for accessing databases
• comparable classification accuracy with other methods

22
 Scalability Framework for RainForest
"Random Forest is a classifier that contains a number of decision
trees on various subsets of the given dataset and takes the
average to improve the predictive accuracy of that dataset."
• Separates the scalability aspects from the criteria that determine the
quality of the tree

• Builds an AVC-list: AVC (Attribute, Value, Class_label)

• AVC-set (of an attribute X )
• Projection of training dataset onto the attribute X and class label
where counts of individual class label are aggregated
• AVC-group (of a node n )
• Set of AVC-sets of all predictor attributes at the node n
23
Rainforest: Training Set and Its AVC Sets
Training Examples AVC-set on Age AVC-set on income
age income student redit_ratin _com Age Buy_Computer income Buy_Computer

<=30 high no fair no yes no

<=30 high no excellent no yes no
high 2 2
31…40 high no fair yes <=30 2 3
31..40 4 0 medium 4 2
>40 medium no fair yes
>40 low yes fair yes >40 3 2 low 3 1
>40 low yes excellent no
31…40 low yes excellent yes
AVC-set on
<=30 medium no fair no AVC-set on Student
credit_rating
<=30 low yes fair yes
student Buy_Computer
>40 medium yes fair yes Buy_Computer
Credit
<=30 medium yes excellent yes yes no rating
yes no
31…40 medium no excellent yes
31…40 high yes fair yes yes 6 1 fair 6 2

>40 medium no excellent no no 3 4 excellent 3 3

25
BOAT (Bootstrapped Optimistic
Algorithm for Tree Construction)
• Use a statistical technique called bootstrapping to create
several smaller samples (subsets), each fits in memory
• Each subset is used to create a tree, resulting in several
trees
• These trees are examined and used to construct a new
tree T’
• It turns out that T’ is very close to the tree that would
be generated using the whole data set together

• It requires only two scans of DB.

26
Visual Mining for Decision Tree Induction
Interactive Visual Mining by Perception-Based Classification (PBC)

27
Data Mining: Concepts and Techniques
Naïve Bayes Classifier
• A probabilistic framework for solving classification problems
• Let D be a training set of tuples and their associated class labels,
and each tuple is represented by an n-D attribute vector X = (x1,
x2, …, xn)
• Suppose there are m classes C1, C2, …, Cm.
• Classification is to derive the maximum posteriori, i.e., the
maximal P(Ci|X)
• This can be derived from Bayes’ theorem P(X|C )P(C )
i i
P(Ci | X) 
P(X)

• Since P(X) is constant for all classes, only

P(Ci | X)  P(X|Ci)P(Ci)
needs to be maximized
28
Cont..
• A simplified assumption: attributes are conditionally
independent (i.e., no dependence relation between attributes):
n
P(X | Ci)   P(x | Ci)  P(x | Ci)  P(x | Ci) ... P(x | Ci)
k 1 2 n
k 
• This greatly reduces the computation cost: Only counts the class
1
distribution
• If Ak is categorical, P(xk|Ci) is the # of tuples in Ci having value xk
for Ak divided by |Ci, D| (# of tuples of Ci in D)
• If Ak is continous-valued, P(xk|Ci) is usually computed based on
Gaussian distribution with a mean μ and standard deviation σ
( x   )2
1 
g (x,  ,  )  2 2

and P(xk|Ci) is e
2 

P(X| Ci)  g(xk , Ci ,Ci )

29
 Naïve Bayes Classifier: Training Dataset
age income student redit_rating_com
<=30 high no fair no
Class: <=30 high no excellent no
C1:buys_computer = ‘yes’ 31…40 high no fair yes
C2:buys_computer = ‘no’ >40 medium no fair yes
>40 low yes fair yes
Data to be classified: >40 low yes excellent no
31…40 low yes excellent yes
X = (age <=30,
<=30 medium no fair no
Income = medium,
<=30 low yes fair yes
Student = yes >40 medium yes fair yes
Credit_rating = Fair) <=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no
30
 Naïve Bayes Classifier: An Example age i nc om e s t udent redit_rating _com
<=30 high no fair no
<=30 high no excellent no
31…40 high no fair yes
• P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643 >40
>40
medium
low
no
yes
fair
fair
yes
yes
>40 low yes excellent no
P(buys_computer = “no”) = 5/14= 0.357 31…40
<=30
low
medium
yes
no
excellent
fair
yes
no
<=30 low yes fair yes

• Compute P(X|C i) for each class >40

<=30
medium
medium
yes
yes
fair
excellent
yes
yes
31…40 medium no excellent yes
P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222 31…40
>40
high
medium
yes
no
fair
excellent
yes
no

P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6

P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444
P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4
P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667
P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2
P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667
P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4
• X = (age <= 30 , income = medium, student = yes, credit_rating = fair)
P(X|Ci) : P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044
P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019
P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028
P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007
31 Therefore, X belongs to class (“buys_computer = yes”)
Avoiding the Zero-Probability Problem
• Naïve Bayesian prediction requires each conditional prob. be
non-zero. Otherwise, the predicted prob. will be zero
n
P( X | Ci)   P(xk | Ci)
k 1
• Ex. Suppose a dataset with 1000 tuples, income=low (0),
income= medium (990), and income = high (10)
• Use Laplacian correction (or Laplacian estimator)
• Adding 1 to each case
Prob(income = low) = 1/1000
Prob(income = medium) = 991/1000
Prob(income = high) = 11/1000

32
 Naïve Bayes Classifier: Comments
• Advantages
• Easy to implement
• Good results obtained in most of the cases
• Disadvantages
• Assumption: class conditional independence, therefore loss of
accuracy
• Practically, dependencies exist among variables
• E.g., hospitals: patients: Profile: age, family history, etc.
Symptoms: fever, cough etc., Disease: lung cancer,
diabetes, etc.
• Dependencies among these cannot be modeled by Naïve Bayes
Classifier

33
Association Analysis
• Association mining aims to extract interesting correlations, frequent patterns, associations or casual structures
among sets of items or objects in transaction databases, relational database or other data repositories.
Examples:
Buys (X, “Computer”) ->Buys (X, “Software”) [Support =40%, confidence= 50%]

Association rule:
• Given: (1) database of transaction
(2) each transaction is a list of items (purchased by a customer in visit)
• Find: all rules that correlate the presence of one set of items with that of another set of items.
Example 1: 98% of people who purchase tires and auto accessories also get done.
Example 2: Market Basket Analysis process analyzes customer buying habits by finding associations
between the different items that customers place in their “Shopping Baskets”. The discovery of
such associations can help retailers develop marketing strategies by gaining insight into which
items are frequently purchased together by customer.
Application of Association Rule Mining
• Market basket analysis: Helps retailers understand customer purchasing patterns,
such as which products are often bought together.
• Customer segmentation: Groups customers based on their purchasing habits.
• Fraud detection: Finds patterns in transactions that may indicate fraudulent
activity.
• Recommendation systems: Suggests items to customers based on their browsing
history or past purchases.
• Product clustering and store layout: Groups products together based on
common attributes to help retailers optimize store layout.
• Catalog design: Uses customer purchase history to inform how products are
presented and where they are placed in catalogs.
• Healthcare and research: Helps identify correlations between drug interactions
or different symptoms in medical research.
Association Rule:
• An association rule is an implication
expression of the form X->Y, where X
and Y are disjoint itemsets, i.e., X ∩ Y
= ∅. The strength of an association
rule can be measured in terms of its
support and confidence. Support
determines how often a rule is
applicable to a given data set, while
confidence determines how frequently
items in Y appear in transactions that
contain X. The formal definition of
these metrics are,
• Support, s(X->Y) = (𝑋∪Y)
𝑁
• Confidence, c(X->Y) = (𝑋∪Y)
𝜎(𝑋)
• Support is an important measure because a rule that has very low support
may occur simply by chance. A low support rule is also likely to be
uninteresting from a business perspective because it may not be profitable
to promote items that customers seldom buy together. For these reasons,
support is often used to eliminate uninteresting rules.
• Confidence, on the other hand, measures the reliability of the inference
made by a [Link] a given rule (𝑋∪Y), the higher the confidence, the more
likely it is for Y to be present in transactions that contain X. Confidence also
provides an estimate of the conditional probability of Y given X.
• Therefore, a common strategy adopted by many association rule mining
algorithms is to decompose the problem into two major subtasks:
1. Frequent Itemset Generation, whose objective is to find all the item- sets
that satisfy the minsupthreshold. These itemsets are called frequent
itemsets.
2. Rule Generation, whose objective is to extract all the high-confidence
rules from the frequent itemsets found in the previous step. These rules
are called strong rules.
Frequent Itemset Generation:
• A lattice structure can be used to enumerate the list of all possible
itemsets. Above Figure shows an itemset lattice for I = {a, b, c, d, e}.
In general, a data set that contains k items can potentially generate up
to 2k − 1 frequent itemsets, excluding the null set. Because k can be
very large in many practical applications, the search space of itemsets
that need to be explored is exponentially large.
• To find frequent itemsets we have two algorithms,
a) Apriori Algorithm
b) FP-Growth
Apriori Algorithm:
• Apriori is a seminal algorithm proposed by R. Agrawal and R. Srikant in
1994 for mining frequent itemsets 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)-itemsets.
• 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 by L1.
• Next, 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-itemsets can be found.
• The finding of each Lk requires one full scan of the database.
• To improve the efficiency of the level-wise generation of frequent itemsets,
an important property called the Apriori property is used to reduce the
search space.
Apriori property: All nonempty subsets of a frequent itemset must also be
frequent.
• The Apriori property is based on the following observation. By definition, if
an itemset I does not satisfy the minimum support threshold, min sup, then I
is not frequent, that is,P(I)< min sup. If an item A is added to the itemset I,
then the resulting itemset (i.e.,IUA) cannot occur more frequently than I.
Therefore, IUA is not frequent either, that is, P(IUA)< min sup.
• This property belongs to a special category of properties called
antimonotonicity in the sense that if a set cannot pass a test, all of its
supersets will fail the same test as well. It is called antimonotonicity
because the property is monotonic in the context of failing a test.
• A two-step process is followed, consisting of join and prune actions.
1. The join step: To find Lk, a set of candidate k-itemsets is generated by
joining Lk-1 with itself. This set of candidates is denoted Ck.
2. The prune step: Ck is a superset of Lk, that is, its members may or may
not be frequent, but all of the frequent k-itemsets are included in Ck. A
database scan to determine the count of each candidate in Ck would
result in the determination of Lk.
Generating Association Rules from Frequent
Itemsets:
• Once the frequent itemsets from transactions in a database D have
been found, it is straightforward to generate strong association rules
from them.
FP-Growth
• FP-growth (finding frequent itemsets without candidate generation). We
reexamine
• the mining of transaction database, D, of Table in previous Example using the
frequent pattern growth approach.
• The first scan of the database is the same as Apriori, which derives the set of
frequent items (1-itemsets) and their support counts (frequencies). Let the
minimum support count be
• Secondly the set of frequent items is sorted in the order of descending support
count. This resulting set or list is denoted by L. Thus, we have L = {{I2:7}, {I1:6},
{I3:6}, {I4:2},{I5:2}}
• An FP-tree is then constructed as follows. First, create the root of the tree, labeled
with “null.” Scan database D a second time. The items in each transaction are
processed in L order (i.e., sorted according to descending support count), and a
branch is created for each transaction.
• The FP-tree is mined as follows. Start from each frequent length-1 pattern (as an initial suffix pattern), construct its
conditional pattern base (a “sub-database,”which consists of the set of prefix paths in the FP-tree co-occurring with the
suffix pattern), then construct its (conditional) FP-tree, and perform mining recursively on the tree. The pattern growth is
achieved by the concatenation of the suffix pattern with the frequent patterns generated from a conditional FPtree.
From Association Mining to Correlation
Analysis using Lift Ratio
• A correlation measure can be used to augment the support-confidence framework for association rules. This leads to correlation rules of the form
A=>B [support, confidence, correlation]
• That is, a correlation rule is measured not only by its support and confidence but also by the correlation between itemsetsA and B. There are many
different correlation measures from which to choose. In this section, we study various correlation measures to determine which would be good for
mining large data sets.
• Lift is a simple correlation n measure that is given as follows. The occurrence of itemset A is independent of the occurrence of itemsetB if
= P(A)P(B); otherwise, itemsetsA and B are dependent and correlated as events. This definition can easily be extended to more than two
itemsets.
• The lift between the occurrence of A and B can be measured by computing

• If the lift(A,B) is less than 1, then the occurrence of A is negatively correlated with the occurrence of B.
• If the resulting value is greater than 1, then A and B are positively correlated, meaning that the occurrence of one implies the occurrence of the other.
• If the resulting value is equal to 1, then A and B are independent and there is no correlation between them.
• Because this value is less than 1, there is a negative correlation
between the occurrence of {gameg}and {video}.