Introduction to Data Analytics

MCA-3282
Open Elective – 6th sem B.Tech
Topic - Grouping
Rohini R. Rao
Dept of Computer Applications
Jan 2020
(Slide set 3 out of 5)
 Contents
Introduction to grouping
Clustering
Categories of clustering algorithms
Distance measures
K-means clustering
Agglomerative clustering
Frequent Patterns
Associative Rules
Measures of Pattern Interestingness
Apriori
Types of Association Rules
Case Studies
Case study 3 : Crime & Hot spot analysis
Case study 4: Amazon – recommender systems
References

2 Introduction to Data Analytics - Rohini R. Rao

 Steps in data analysis projects
●
Objectives

Problem Definition
●
Deliverables
●
Roles and responsibilities
●
Current situation
●
Timeline
●
Costs and benefits

●
Pull together data table

Data Preparation
●
Categorize the data
●
Clean the data
●
Remove unnecessary data
●
Transform the data
●
Partition the data

●
Summarizing the data
Implementation of the Analysis ●
Finding hidden relationships
●
Making prediction

Plan and execute deployment based on the definition in step 1

Deployment
●

●
Measure and monitor performance
●
Review the project

3 Introduction to Data Analytics - Rohini R. Rao

 Grouping
Dividing a data set into smaller subsets of related observations or groups
Reasons include
Finding hidden relationships
Becoming familiar with the data
Segmentation
Grouping Approaches
Supervised versus unsupervised
Type of variables
Data set size limit
Interpretable and actionable
Overlapping groups
Simplest grouping method – Grouping by values or range
Query 1: All cars where Horsepower is greater than or equal to 160 AND
Weight is greater than or equal to 4000.

4 Introduction to Data Analytics - Rohini R. Rao

 Clustering
A good clustering method will produce high
quality clusters with
high intra-class similarity
low inter-class similarity
Unsupervised learning
Clustering Methods include
Partitioning
Hierarchical
Others - Density based, grid based, model based etc.

5 Introduction to Data Analytics - Rohini R. Rao

 Categorization of Major Clustering Methods
 Partitioning methods
 Given D , a data set of n objects and k, the number of clusters to
form
 Partition algorithm organizes the objects into k partitions where each
partition represents a cluster.
 Centroid Based Technique
 k_Means Method
 k-Medoids Method
 Popular techniques include PAM , CLARA , CLARANS
 Hierarchical methods
 Creates hierarchical decomposition of the given set of data objects
 Agglomerative or bottom-up approach
 Divisive or top-down approach
 Popular techniques include CHAMELEON and BIRCH
6 Introduction to Data Analytics - Rohini R. Rao
 Categorization of Major Clustering Methods
 Density-based methods
 results in non-spherical shaped clusters also
 Instead continue growing the given cluster as long as the density in
the neighborhood exceeds some threshold
 Popular techniques include DBSCAN , DENCLUE and OPTICS
 Grid-based methods
 Quantize the object space into a finite number of cells that form a
grid structure.
 All clustering performed on the grid structure
 Fast processing time
 Popular techniques include STING and WAVECLUSTER
 Model-based methods
 Hypothesize a model for each of the cluster and find the best fit of
the data to the given model
 Popular techniques include EM, COBWEB and SOM

7 Introduction to Data Analytics - Rohini R. Rao

 Distance Measures for numeric attributes
Euclidean Distance
X = ( x ,x ,…x ) and X = (x ,x ..x ) is
1 11 12 1n 2 21 22 2n
dist(X ,X ) = √Σ n (x – x )2
1 2 1=1 1i 2i

Manhattan or City Block Distance

dist(i , j ) = | xi1 – x j1| + | xi2 – xj2| +… | xin – xjn|

Minkowski Distance
dist(i,j) = (| xi1 – x j1|p + | xi2 – xj2| p+… | xin – xjn|p) 1/p

8 Introduction to Data Analytics - Rohini R. Rao

 Distance measures for partitioning based
clustering

9 Introduction to Data Analytics - Rohini R. Rao

 Data Matrix

Three observations
5 variables

10 Introduction to Data Analytics - Rohini R. Rao

 Distance between observations with 5
variables

11 Introduction to Data Analytics - Rohini R. Rao

 Similarity measures between binary vectors

12 Introduction to Data Analytics - Rohini R. Rao

 Nominal Variables
A generalization of the binary variable in that it can take
more than 2 states, e.g., red, yellow, blue, green
Method 1: Simple matching
m: # of matches, p: total # of variables

d (i, j)  p 
p
m

Method 2: use a large number of binary variables

creating a new binary variable for each of the M nominal states

13 Introduction to Data Analytics - Rohini R. Rao

 K-Means Clustering
 Choose the number of clusters, k.
 Randomly generate k clusters and determine the cluster centers, or directly
generate k random points as cluster centers.
 Assign each point to the nearest cluster center.
 Recompute the new cluster centers.
 Repeat the two previous steps until some convergence criterion is met (usually
that the assignment hasn't changed).
 Example: The data set has three dimensions and the cluster has two points: X =
(x1, x2, x3) and Y = (y1, y2, y3). Then the centroid Z becomes Z = (z1, z2, z3),
where z1 = (x1 + y1)/2 and z2 = (x2 + y2)/2 and z3 = (x3 + y3)/2.
 Within cluster variation - Square-error criterion E = ∑ i=1k ∑p ЄCi│p - mi│2
 Advantages:
 Simplicity and speed
 Disadvantages :
 Does not yield the same result with each run, since the resulting clusters
depend on the initial random assignments.
 Sensitive to outliers

14 Introduction to Data Analytics - Rohini R. Rao

 Hierarchical Clustering
Works by grouping data objects into a tree of clusters
Can be classified depending on whether decomposition
is
Agglomerative -bottom-up or Merging
Divisive – top down or Splitting
Quality of clusters not good because once merge or split
decision is made – no back tracking
normally limited to small data sets (often less than
10,000 observations)
speed to generate the hierarchical tree can be slow for
higher numbers of observations
15 Introduction to Data Analytics - Rohini R. Rao
 Agglomerative Clustering
Given a set of N items to be clustered, and an NxN distance (or similarity)
matrix, the basic process hierarchical clustering is this:
1.Start by assigning each item to its own cluster, so that if you have N
items, you now have N clusters, each containing just one item. Let the
distances (similarities) between the clusters equal the distances (similarities)
between the items they contain.
2.Find the closest (most similar) pair of clusters and merge them into a
single cluster, so that now you have one less cluster.
3.Compute distances (similarities) between the new cluster and each of the
old clusters.
4.Repeat steps 2 and 3 until all items are clustered into a single cluster of
size N or until certain termination condition.
• Terminating condition : desired number of clusters or the diameter of each
cluster is within a certain threshold.
• Merging Criterion – Single Linkage Approach - Cluster C1 & C2 are merged if
any object in C1 and any object in C2 form a minimum euclidean distance
between any two objects from different clusters
16 Introduction to Data Analytics - Rohini R. Rao
 Hierarchical Clustering
 These method does not require the number of clusters k as an input, but needs a termination
condition
 AGNES – Agglomerative Nesting
 DIANA – Divisive Analysis

Step 0 Step 1 Step 2 Step 3 Step 4

agglomerative
(AGNES)
a ab
b abcde
c
cde
d
de
e
divisive
17 Step
Step 4to Data
Introduction 3 Step
Analytics 2 R.
- Rohini Step
Rao 1 Step 0 (DIANA)
 A Dendrogram Shows How the
Clusters are Merged Hierarchically

Decompose data objects into a several levels of nested

partitioning (tree of clusters), called a dendrogram.

A clustering of the data objects is obtained by cutting the

dendrogram at the desired level, then each connected
component forms a cluster.

18 Introduction to Data Analytics - Rohini R. Rao

 Computing Distances
• Single-link clustering
• Consider the distance between one cluster and another cluster to be equal to
the shortest distance from any member of one cluster to any member of the
other cluster.
•Complete-link clustering
• Consider the distance between one cluster and another cluster to be equal to
the longest distance from any member of one cluster to any member of the
other cluster.
•Average-link clustering :
• Consider the distance between one cluster and another cluster to be equal to
the average distance from any member of one cluster to any member of the
other cluster.

19 Introduction to Data Analytics - Rohini R. Rao

 Clustering under different linkage rules

20 Introduction to Data Analytics - Rohini R. Rao

 392 cars – Agglomerative clustering
Euclidean distance & average linkage

21 Introduction to Data Analytics - Rohini R. Rao

 Result - Summary of Cluster 1

22 Introduction to Data Analytics - Rohini R. Rao

 Result - Summary of Cluster 2

23 Introduction to Data Analytics - Rohini R. Rao

 Clustering the same data set
using k-means clustering
Euclidean distance

24 Introduction to Data Analytics - Rohini R. Rao

 Case study 3- Crime & Hot spot analysis
Crime hot spots is an area where the number of criminal events or disorder is higher than in
any other places particular environments that attract drug trading and crimes in larger-than-
expected concentrations, so-called crime generators
Hot spots defined by attributes such as
Location – latitude & longitude
particular activities such as drug trading, use of firearms , weapons
specific concentrations of land uses- hotels , bars
interactions between activities and land uses, such as thefts at transit stations or bus stops
Techniques that can be used
Partitioning method – k-mode clustering
Density based method – Single Kernel Density method
Interpretation of clusters
The area of highest crime rate is where many shops, banks and people hang out.
Another cluster is the neighborhood of the city, where residents have a high purchasing
power
the number of crimes using firearms was very large
Case study

25 Introduction to Data Analytics - Rohini R. Rao

 Crime & Hot spot analysis

26 Introduction to Data Analytics - Rohini R. Rao

 Frequent Patterns
Frequent pattern mining searches for
recurring relationships in a given sets.
Frequent Patterns
Are patterns that appear in the data set
frequently
A subsequence that appears frequently is a
frequent sequential pattern
If a sub structure occurs frequently it is
called a frequent structured pattern

27 Introduction to Data Analytics - Rohini R. Rao

 Frequent Patterns

28 Introduction to Data Analytics - Rohini R. Rao

 Market Basket Analysis
 Analyzes customer buying habits by finding associations between
different items that customers place in their shopping baskets
 Leads to the discovery of associations and correlations among items in
large transactional or relational data sets.
 “Which groups or sets of items are customers likely to purchase on a
given trip to the store ?”
 Helps in business decision making process, such as
 catalog design,
 cross-marketing
 customer shopping behavior analysis.
 Can be used to plan different store layouts.
 Place them together
 Place them far apart
 Decide which item to put on sale.
 Patterns can be represented in the form of Association rules

29 Introduction to Data Analytics - Rohini R. Rao

 Association Rules

Marketing and Sales Promotion:

Let the rule discovered be
{Bagels, … }  {Potato Chips}
Potato Chips as consequent => Can be used to determine what should be done
to boost its sales.
Bagels in the antecedent => Can be used to see which products would be
affected if the store discontinues selling bagels.
Bagels in antecedent and Potato chips in consequent => Can be used to see
what products should be sold with Bagels to promote sale of Potato chips!
30 Introduction to Data Analytics - Rohini R. Rao
 Associative Rules
Each item has a boolean variable representing the presence or
absence of that item.
Each basket can be represented by a Boolean vector of values
assigned to these variables.
These patterns are then represented as a Boolean Association Rule
buys(X,”computer”) =>buys(X,”antivirus_software “)
[support = 2%, confidence = 60 % ]
 Measures of pattern interestingness can be
 Subjective – useful, previously unknown
 Objective
Support of 2 % of all transactions have computers and anti virus
software purchased together
Confidence of 60 % means that 60 % of all customers who
purchased a computer also bought the software.
Minimum support and confidence set by domain expert

31 Introduction to Data Analytics - Rohini R. Rao

 Association Rule Mining
Steps involved
 Find all frequent items sets – each of these item sets
will occur at least as frequently as a pre determined
minimum support count
Generate strong association rules from the frequent
item sets – rules should satisfy minimum support and
confidence.
Association rules can be generated as follows
 For each frequent itemset l, generate all nonempty subsets of l
 For every nonempty subset s of l , output the rule s=> (l-s)
 If support_count(l)/support_count(s) >= min_conf
 Where min_conf is the minimum confidence threshold

32 Introduction to Data Analytics - Rohini R. Rao

 Apriori Algorithm
 Seminal algorithm proposed by R. Agarwal and R.Srikant in 1994 for
mining frequent itemsets for Boolean association rules.
 Employs an iterative , bottom-up approach known as level-wise search ,
where k-itemsets are used to explore (k+1) itemsets
 Based on Apriori property :
 All nonempty subsets of a frequent itemset must also be frequent
 Antimonotone – if a set cannot pass a test then all its supersets will fail
the same test as well
 Two step process of the Apriori algorithm are
 Join Step
 To find L , a set of candidate k-itemsets is generated by joining L with itself.
k k-1
This set of candidates is denoted Ck
 Prune Step
 C is the superset of L , its members may or may not be frequent but all of the
k k
frequent k-itemsets are included in Ck
 A scan of the database to determine the count of each candidate in C will result
k
in Lk
 To reduce the size of C the apriori property is used . Any (k-1) itemset that is not
k
33 frequent cannot be a subset
Introduction to Data Analytics of R.
- Rohini a frequent
Rao k-itemset .
 Frequent Item sets
 Let T = { I ,I , I ….I } be a set of items
1 2 3 m
 Each transaction has a T_id
 An association is an implication of the form
 A=> B where A C T , B C T and A Π B = Ø
 Support (A => B) = P ( A U B)
 Confidence( A => B) = P ( B/A)
 A set of items is called as an item set
 The set { computer , anti_virus} is called 2 item set
 The occurrence frequency of an item set is the number of transactions that
contain the item set.
 This is also known as frequency , support count or count of the item set.
 Confidence(A=> B) = P ( B/A) = support (A U B ) / support (A)
A  B, A,B – Set of items.
 Support : Count (A U B )
 Confidence : support Count (A U B )
support Count (A)

34 Introduction to Data Analytics - Rohini R. Rao

 Types of patterns mined
 Multilevel Association rules
 buys(X,”computer”) => buys(X,”HP-printer”)
 buys(X,”lap-top-computer”) => buys(X,”HP-printer”)
 Multidimensional Association rules
 age(X,”30..39”) П income(X,”42K..48K”) => buys(X,”high resolution TV)
 Association rules or correlation rules
 Strong Gradient relationships – “The average sales from Sony digital
camera increases over 16 % when sold together with Sony laptop”
 Sequential Pattern Mining
 which searches for frequent subsequences in a sequence data set.
 Ex : customer first buys PC followed by digital camera and then memory
card.
 Structured Pattern Mining which looks for frequent substructures
 Recommender systems
 which recommend information items (e.g., books, movies, web pages)
that are likely to be of interest to the user based on similar users’
patterns.
35 Introduction to Data Analytics - Rohini R. Rao
 Pros & Cons of Apriori
Characteristics of Apriori Algorithm:
 Simple, user friendly algorithm
 No. of database scans = k, if (k-1)-large item sets are possible
 Discovers all possible large item sets
 Robust algorithm
 Ranking of rules required
Disadvantages of Apriori Algorithm
In general a data set that contains k items can potentially generate up
to 2K – 1 frequent item sets
Generation of candidate item sets is expensive (in both space and
time)
Support counting is expensive
Subset checking (computationally expensive)
Multiple Database scans (I/O)

36 Introduction to Data Analytics - Rohini R. Rao

 Other important Algorithms
 Partitioning Algorithm
 Transactions in D are divided into n partitions
 Phase 1 : Find the frequent item sets local to each partition
 Phase 1 : Combine all local Frequent Item sets to form candidate item set.
 Phase 2 : Find global frequent item sets among the candidates
 Phase 2 : Frequent item sets in D

 Frequent Pattern Growth Algorithm

 Allows frequent item set discovery without candidate item set generation.
 Two step approach:
 Step 1: Build a compact data structure called the FP-tree, built using 2 passes over the data-set.
 Step 2: Extracts frequent items ets directly from the FP-tree by traversal through FP-Tree
Advantages of FP-Growth
 only 2 passes over data-set
 no candidate generation
 much faster than Apriori
Disadvantages of FP-Growth
 FP-Tree may not fit in memory!!
 FP-Tree is expensive to build

37 Introduction to Data Analytics - Rohini R. Rao

 From Association Mining to Correlation
Analysis
 Even strong association rules can be uninteresting and
misleading.
 So support-confidence framework needs be supplemented.
 Suppose there is an association rule
 buys(X,”computer games”) => buys(X,”videos”)
[ support = 40 % , confidence = 66 % ]

 Rule is misleading because the probability of purchasing

videos is 75% which is even larger than 66 %
 Actually computer games and videos could be negatively
associated
 Confidence which is conditional probability does not
measure strength of the correlation and implications
between antecendent and consequent.
38 Introduction to Data Analytics - Rohini R. Rao
 Correlation rules
 A => B [support, confidence, correlation]

 The occurrence of itemset A is independent of the occurrence of itemset B if

P(AUB) = P(A)P(B) otherwise itemsets A and B are dependent and correlated
as events.
 Lift :
 between the occurrence of A and B can be measured by computing
 Lift(A,B) = P(AUB)/P(A)P(B)
 Also written as Lift(A,B) = conf(A=>B)/ supp(B)
 If the resulting value
 <1 then the occurrence of A is negatively correlated with occurrence of B
 >1 then A and B are positively correlated
 =1 then A and B are independent and there is no correlation between them.

 Ex: P({game,video})/P({game}) * P({video}) = 0.40 / (0.60 * 0.75) = 0.89

 Because it is less than 1 video and game are negatively correlated

39 Introduction to Data Analytics - Rohini R. Rao

 Associative rules
Advantages:
 Easy to interpret: The results are presented in the form of a rule that is
easily understood.
 Actionable: It is possible to perform some sort of action based on the
rule.
Large data sets: It is possible to use this technique with large numbers of
observations.
Limitations :
 Only categorical variables: or to convert continuous variable to
categorical variables.
Time-consuming: There are ways to make the analysis run faster but they
often compromise the final results.
Rule prioritization: The method can generate many rules that must be
prioritized and interpreted.

40 Introduction to Data Analytics - Rohini R. Rao

 Data Mining and Recommender Systems
Personalization of shopping experience
Considers a set, C, of users and a set, S, of items.
u is a utility function that measures the usefulness of an item, s, to a user, c.
The utility is represented by a rating and is initially defined only for items
previously rated by users.
False positive are irritation to customer, false negative is loss of revenue

Content-based approach
recommends items that are similar to items the user preferred or queried in
the past.
Collaborative approach
consider a user’s social environment.
It recommends items based on the opinions of other customers who have
similar tastes or preferences as the user.

41 Introduction to Data Analytics - Rohini R. Rao

 Case study 4- Amazon – recommender systems
Challenges
large retailer might have huge amounts of data, customers and catalog items.
Amazon.com has more than 29 million customers and several million catalog items.
results set to be returned in real time
New customers typically have extremely limited information or product ratings.
Older customers can have a glut of information,
Customer data is volatile
Item-to-Item Collaborative Filtering
scales to massive data sets and produces high-quality recommendations in real time
creates the expensive similar-items table offline
Rather than matching the user to similar customers, item-to-item collaborative filtering
matches each of the user’s purchased and rated items to similar items, then combines those
similar items into a recommendation list
This computation is very quick, depending only on the number of items the user purchased
or rated.
Works better than search based or collaborative recommendation
Case study

42 Introduction to Data Analytics - Rohini R. Rao

 Summary of grouping methods

43 Introduction to Data Analytics - Rohini R. Rao

 References
Text book
Glenn J. Myatt, Making Sense of Data: A Practical Guide
to Exploratory Data Analysis and Data Mining, John
Wiley, November 2006.
References
I.H. Witten, E. Frank, M. A. Hall, Data Mining: Practical
Machine Learning Tools and Techniques, Morgan
Kaufmann, 2011
Pang-Ning Tan, Michael Steinbach, Vipin Kumar,
Introduction to Data Mining, Pearson Addison Wesley,
May, 2005.

44 Introduction to Data Analytics - Rohini R. Rao