CS8091 / Big Data Analytics

III Year / VI Semester

 Unit II - CLUSTERING AND
CLASSIFICATION
Advanced Analytical Theory and Methods: Overview of
Clustering - K-means - Use Cases - Overview of the
Method - Determining the Number of Clusters -
Diagnostics - Reasons to Choose and Cautions .-
Classification: Decision Trees - Overview of a Decision
Tree - The General Algorithm - Decision Tree
Algorithms - Evaluating a Decision Tree - Decision
Trees in R - Naïve Bayes - Bayes‘ Theorem - Naïve
Bayes Classifier.
 Clustering

 Clustering is the use of unsupervised techniques for

grouping similar objects.
 Clustering

 In machine learning, unsupervised refers to

the problem of finding hidden structure within

unlabeled data.
 The structure of the data describes the objects
of interest and determines how best to group
the objects.
 Clustering

 Example: customers could be divided into

three groups as follows:

Earn less than $10,000

Earn between $10,000 and $99,999

Earn $100,000 or more

 Clustering

 K – means:

 To find groups in the data, with the number of

groups represented by the variable K.
 The center is determined as the arithmetic average
(mean) of each cluster’s n-dimensional vector of
attributes
 Clustering: K – means

 Use Cases:
 Once the clusters are identified, labels can be
applied to each cluster to classify each group based
on its characteristics.
 To discover hidden structures of the data, possibly
as a introduction to more focused analysis or
decision processes
 Clustering: K – means

 Use Cases - Image Processing:

 Video is one example of the growing volumes of
unstructured data being collected.
 k-means analysis can be used to identify objects in the
video.
 For each frame, the task is to determine which pixels
are most similar to each other.
 Clustering: K – means

 Use Cases - Image Processing:

 The attributes of each pixel can include brightness,
color, and location, the x and y coordinates in the
frame.
 With security video images, for example, successive
frames are examined to identify any changes to the
clusters.
 Clustering: K – means

 Use Cases - Medical:

 Patient attributes such as age, height, weight,
systolic and diastolic blood pressures, cholesterol
level, and other attributes can identify naturally
occurring clusters.
 Clustering: K – means

 Use Cases - Medical:

 These clusters could be used to target individuals
for specific preventive measures or clinical trial
participation.
 Clustering: K – means

 Use Cases - Customer Segmentation:

 A wireless provider may look at the following
customer attributes: monthly bill, number of text
messages, data volume consumed, minutes used
during various daily periods, and years as a
customer.
 Clustering: K – means

 Use Cases - Customer Segmentation:

 Consider tactics to increase sales or reduce the
customer churn rate, the proportion of customers
who end their relationship with a particular
company.
 Clustering: K – means

 Overview of the Method:

 the point that corresponds to the cluster’s mean is
called a centroid.
 In mathematics, a centroid refers to a point that
corresponds to the center of mass for an object.
 Clustering: K – means

 Overview of the Method – Step 1:

 Choose the value of k and the k initial guesses for
the centroids.
 Clustering: K – means

 Overview of the Method – Steps 2:

 Compute the distance from each data point to each
centroid. Assign each point to the closest centroid.
This association defines the first k clusters.
 Euclidean distance:
 Clustering: K – means

 Overview of the Method – Steps 2:

 the points closest to a centroid are shaded the
corresponding color.
 Clustering: K – means

 Overview of the Method – Steps 3:

 Compute the centroid, the center of mass, of each
newly defined cluster from Step 2.

 the centroid (xc,yc ) of the m points in a k-means

cluster is calculated as:
 Clustering: K – means

 Overview of the Method – Steps 3:

 Compute the centroid, the center of mass, of each
newly defined cluster from Step 2.
 Clustering: K – means

 Overview of the Method – Steps 4:

 Repeat Steps 2 and 3 until the algorithm
converges to an answer.
 Assign each point to the closest centroid computed in
Step 3.
 Compute the centroid of newly defined clusters.

 Repeat until the algorithm reaches the final answer.

 Clustering: K – means

 Determining the Number of Clusters:

 The value of k can be chosen based on a
reasonable guess or some predefined requirement.
 Within Sum of Squares (WSS) metric: the sum of
the squares of the distances between each data
point and the closest centroid.
 Clustering: K – means

 Diagnostics:
 The heuristic using WSS can provide at least several
possible k values to consider.
 When the number of attributes is relatively small, a
common approach to further refine the choice of k is
to plot the data to determine how distinct the
identified clusters are from each other.
 Clustering: K – means

 Diagnostics:
 In general, the following questions should be
considered:
 Are the clusters well separated from each other?

 Do any of the clusters have only a few points?

 Do any of the centroids appear to be too close to each

other?
 Clustering: K – means

 Reasons to Choose and Cautions:

 K-means is a simple and straightforward method for
defining clusters.
 Once clusters and their associated centroids are
identified, it is easy to assign new objects (for
example, new customers) to a cluster based on the
object’s distance from the closest centroid.
 Clustering: K – means

 Reasons to Choose and Cautions:

 What object attributes should be included in the
analysis?
What unit of measure (for example, miles or
kilometers) should be used for each attribute?
 Clustering: K – means

 Reasons to Choose and Cautions:

Do the attributes need to be rescaled so that one
attribute does not have a disproportionate effect on
the results?
What other considerations might apply?
 Clustering: K – means

 Reasons to Choose and Cautions:

 Object Attributes:
 To understand what attributes will be known at
the time a new object will be assigned to a cluster.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Object Attributes:
 Information on existing customers’ satisfaction or
purchase frequency may be available, but such
information may not be available for potential
customers.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Object Attributes:
 Whenever possible and based on the data, it is best to
reduce the number of attributes to the extent possible.
 Too many attributes can minimize the impact of the
most important variables.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Object Attributes:
 Another option to reduce the number of attributes
is to combine several attributes into one measure.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Units of Measure:
 The algorithm will identify different clusters
depending on the choice of the units of measure.
 To cluster patients based on age in years and
height in centimeters.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Units of Measure:
 Clustering: K – means

 Reasons to Choose and Cautions:

 Units of Measure:
 But if the height was rescaled from centimeters to
meters by dividing by 100, the resulting clusters
would be slightly different.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Units of Measure:
 Clustering: K – means

 Reasons to Choose and Cautions:

 Rescaling:
 Attributes that are expressed in dollars are common in
clustering analyses and can differ in magnitude from
the other attributes.
 If personal income is expressed in dollars and age is
expressed in years.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Rescaling:
 Although some adjustments could be made by
expressing the income in thousands of dollars (for
example, 10 for $10,000).
 Clustering: K – means

 Reasons to Choose and Cautions:

 Additional Considerations:
 Euclidean distance function to assign the points to
the closest centroids.
 Other possible function choices include the cosine
similarity and the Manhattan distance functions.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Additional Considerations:
 The cosine similarity function is often chosen to
compare two documents based on the frequency of
each word that appears in each of the documents.
 Clustering: K – means

 Reasons to Choose and Cautions:

 Additional Considerations:
The Manhattan distance, d1, between p and q is
expressed as
 Clustering

 Additional Algorithms:
 Partitioning around Medoids: a medoid is a
representative object in a set of objects.
 In clustering, the medoids are the objects in each
cluster that minimize the sum of the distances from
the medoid to the other objects in the cluster
 Clustering

 Additional Algorithms:

 Hierarchical agglomerative clustering:

 each object is initially placed in its own cluster.

 The clusters are then combined with the most

similar cluster.
 In R, hclust() function is used.
 Clustering

 Additional Algorithms:

 Density-based clustering:
 the clusters are identified by the concentration of
points.
 In R, dbscan() function is used.
 Classification

 The primary task performed by classifiers is to

assign class labels to new observations.
 The set of labels for classifiers is predetermined,
unlike in clustering, which discovers the structure
without a training set and allows the data scientist
optionally to create and assign labels to the clusters.
 Classification

 Most classification methods are supervised

 Start with a training set of prelabeled

observations.
 used for prediction purposes

 Methods: Decision trees and naïve Bayes

 Classification - Decision Trees

 Tree structure to specify sequences of decisions

and consequences.
 The prediction can be achieved by constructing
a decision tree with test points and branches.
 At each test point, a decision is made to pick a
specific branch and traverse down the tree.
 Classification - Decision Trees

 A final point is reached, and a prediction can

be made.
 Each test point in a decision tree involves
testing a particular input variable (or attribute),
and each branch represents the decision being
made.
 Classification - Decision Trees

 The input values of a decision tree can be categorical

or continuous.
 A decision tree employs a structure of test points
(called nodes) and branches, which represent the
decision being made.
 A node without further branches is called a leaf node.
 Classification - Decision Trees

 The input values of a decision tree can be categorical

or continuous.
 A decision tree employs a structure of test points
(called nodes) and branches, which represent the
decision being made.
 A node without further branches is called a leaf node.
 Classification - Decision Trees

 A decision tree can be converted into a set of

decision rules.
 Decision trees have two varieties:
classification trees and regression trees
 Classification - Decision Trees

 Classification trees:
 apply to output variables that are categorical—
often binary—in nature.
 Example: yes or no, purchase or not purchase.
 Classification - Decision Trees

 Regression trees:
 apply to output variables that are numeric or
continuous.
 Example: the price of a house, or a patient’s
length of stay in a hospital.
 Classification - Decision Trees

 Regression trees:
 Classification - Decision Trees

 Overview of a Decision Tree

 Classification - Decision Trees

 Overview of a Decision Tree

 Branch - the outcome of a decision and is
visualized as a line connecting two nodes.
 Internal nodes are the decision or test points.

 The depth of a node is the minimum number of

steps required to reach the node from the root.
 Classification - Decision Trees

 Overview of a Decision Tree

 Leaf nodes are at the end of the last branches on
the tree.
 They represent class labels—the outcome of all
the prior decisions.
 Classification - Decision Trees

 Overview of a Decision Tree – Examples:

 to classify animals,

 a doctor’s evaluation of a patient

 to segment customers or predict response rates to

marketing and promotions
 Financial institutions - decide if a loan application
should be approved or denied
 Classification - Decision Trees

 Overview of a Decision Tree – Examples:

 By limiting the number of splits, a short tree can
be created. Short trees are often used as
components (also called weak learners or base
learners) in ensemble methods.
 Classification - Decision Trees

 Overview of a Decision Tree – Examples:

 The simplest short tree is called a decision stump,
which is a decision tree with the root immediately
connected to the leaf nodes.
 Classification - Decision Trees

 Example – Dataset:
Age Competition Type Profit
Old Yes Software Down
Old No Software Down
Old No Hardware Down
Mid Yes Software Down
Mid Yes Hardware Down
Mid No Hardware Up
Mid No Software Up
New Yes Software Up
New No Hardware Up
New No Software Up
 Classification - Decision Trees

 To find
 P, N

 Entropy

 Information Gain

 Gain
 Classification - Decision Trees

 Solution:
 P = 5 ( Possibility of getting Yes ( Here, Up))

 N = 5 ( Possibility of getting No ( Here, Down))

 Classification - Decision Trees
 Solution:
 Entropy:
 Information gain (IG) measures how much “information” a
feature gives us about the class.
 Entropy is the measures of impurity, disorder or uncertainty in a
bunch of examples. Entropy controls how a Decision Tree
decides to split the data. It actually effects how a Decision
Tree draws its boundaries.
 Classification - Decision Trees

 Algorithms - ID3 (Iterative Dichotomiser 3)

 ID3 (A, P, T)

 if

 return

 if all records in T have the same value for P

return a single node with that value
 Classification - Decision Trees

 Algorithms - ID3 (Iterative Dichotomiser 3)

 if

 return a single node with the most frequent value of P

in T
 Compute information gain for each attribute in A
relative to T
 Classification - Decision Trees

 Algorithms - ID3 (Iterative Dichotomiser 3)

 Pick attribute D with the largest gain
 Let {d1,d2..dm} be the values of attribute D
 Partition T into {T1,T2,..Tm } according to the
values of D
 return a tree with root D and branches labeled
d1,d2..dm going respectively to trees ID3(A-{D}, P,
T1), ID3(A-{D}, P, T2), … ID3(A-{D}, P, Tm)
 Classification - Decision Trees
 Algorithms - ID3 (Iterative Dichotomiser 3)
 It begins with the original set S as the root node.

 On each iteration of the algorithm, it iterates through

the very unused attribute of the set S and calculates
Entropy(H) and Information gain(IG) of this attribute.
 It then selects the attribute which has the smallest
Entropy or Largest Information gain.
 Classification - Decision Trees

 Algorithms - ID3 (Iterative Dichotomiser 3)

 The set S is then split by the selected attribute to

produce a subset of the data.
 The algorithm continues to recur on each subset,
considering only attributes never selected before.
 Classification - Decision Trees

 Algorithms - C4.5

 The C4.5 algorithm can handle missing data

 If the training records contain unknown attribute

values, the C4.5 evaluates the gain for an attribute
by considering only the records where the attribute
is defined.
 Classification - Decision Trees
 Algorithms - C4.5
 Both categorical and continuous attributes are supported
by C4.5.
 Values of a continuous variable are sorted and
partitioned.
 For the corresponding records of each partition, the gain
is calculated, and the partition that maximizes the gain is
chosen for the next split.
 Classification - Decision Trees

 Algorithms - C4.5
 The ID3 algorithm may construct a deep and
complex tree, which would cause overfitting.
 Bottom-up technique called pruning to simplify
the tree by removing the least visited nodes and
branches
 Classification - Decision Trees

 Algorithms – CART:

 Classification And Regression Trees

 CART can handle continuous attributes

 CART uses the Gini diversity index
 Classification - Decision Trees

 Algorithms – CART:

 CART constructs a sequence of subtrees

 Uses cross-validation to estimate the

misclassification cost of each subtree
 chooses the one with the lowest cost
 Classification - Evaluating a
Decision Tree
 Decision trees use greedy algorithms, in that they
always choose the option that seems the best available
at that moment.
 At each step, the algorithm selects which attribute to
use for splitting the remaining records.
 This selection may not be the best overall, but it is
guaranteed to be the best at that step.
 Classification - Evaluating a
Decision Tree
 First, evaluate whether the splits of the tree make sense.
Conduct sanity checks by validating the decision rules
with domain experts, and determine if the decision rules
are sound.
 Next, look at the depth and nodes of the tree.

 In overfitting, the model fits the training set well, but it

performs poorly on the new samples in the testing set.
Classification - Evaluating a
Decision Tree
 Classification - Evaluating a
Decision Tree
 The x-axis represents the amount of data, and the y
axis represents the errors.
 The blue curve is the training set, and the red curve
is the testing set.
 The left side of the gray vertical line shows that the
model predicts well on the testing set.
 Classification - Evaluating a
Decision Tree
 But on the right side of the gray line, the model
performs worse and worse on the testing set as more
and more unseen data is introduced.
 For decision tree learning, overfitting can be caused
by either the lack of training data or the biased data in
the training set
 Classification - Evaluating a
Decision Tree
 Two approaches can help avoid overfitting in
decision tree learning
 Stop growing the tree early before it reaches the point
where all the training data is perfectly classified
 Grow the full tree, and then post-prune the tree with
methods such as reduced-error pruning and rule-based post
pruning
 Naïve Bayes

 Naïve Bayes is a probabilistic classification method

based on Bayes’ theorem.
 Bayes’ theorem gives the relationship between the
probabilities of two events and their conditional
probabilities.
 Naïve Bayes

 The input variables are generally categorical, but

variations of the algorithm can accept continuous
variables.
 There are also ways to convert continuous variables
into categorical ones. This process is often referred to
as the discretization of continuous variables.
 Naïve Bayes

 Example – Income:
 Low Income: income < $10,000

 Working Class: $10,000 ≤ income < $50,000

 Middle Class: $50,000 ≤ income < $1,000,000

 Upper Class: income ≥ $1,000,000

 Naïve Bayes

 Applications:
 Spam filtering - to distinguish spam e-mail from

legitimate e-mail
 Fraud Detection – auto insurance
 Naïve Bayes

 Bayes’ Theorem:
 The conditional probability of event C occurring, given
that event A has already occurred, is denoted as P(C|A),
which can be found using the formula
 Naïve Bayes
 Bayes’ Theorem:
 some minor algebra and substitution of the conditional
probability

 Bayes’ theorem gives the relationship between the

probabilities of C and A, P(C) and P(A) , and the conditional
probabilities of C given A and A given C, namely P(C|A) and
P(A|C)
 Naïve Bayes

 Bayes’ Theorem:
 P(C|A) – Posterior Probability – The degree to which we
believe a given model accurately describes the situation
given available data and all of our prior information.
 Probability of event after event C is true.

 P(A|C) – Likelihood – how well the model predicts the

data.
 Naïve Bayes

 Bayes’ Theorem:
 P (C) – Prior Probability – The degree to which we believe
the model accurately describes reality based on all of our
prior information.
 Probability of event before event C

 P (A) – Normalizing constant – The posterior density

integrate to one.
 Naïve Bayes

 Advantages:
 Fast to predict a class of test data set

 Better compare to other models assuming independence

 It performs well in case of categorical input variables

 Naïve Bayes

 Disadvantages:
 Bad Estimator

 Independent predicator assumption

 Naïve Bayes

 Applications:
 Credit Scoring

 Medical

 Real time Prediction

 Text classification
 Naïve Bayes

 Smoothing:
 If one of the attribute values does not appear with one of
the class labels within the training set, the corresponding
P(C | A) will equal to zero.
 Laplace smoothing (or addone) technique that pretends to
see every outcome once more than it actually appears
 Naïve Bayes

 Diagnostics of Classifiers:
 A confusion matrix is a specific table layout that allows
visualization of the performance of a classifier.

Positive Negative
Positive True Positives (TP) True Negatives
(TN)
Negative False Positives (FP) False Negatives
(TN)
 Naïve Bayes

 Diagnostics of Classifiers:

 True Positive Rate (TPR) - shows what percent of

positive instances the classifier correctly identified.
 You projected positive and its turn out to be true. For
example, you had predicted that France would win
the world cup, and it won.
 Naïve Bayes

 Diagnostics of Classifiers:

 False Positive Rate (FPR) shows what percent of

negatives the classifier marked as positive. The FPR
is also called the false alarm rate or the type I error
rate.
 Naïve Bayes

 Diagnostics of Classifiers:

 Your prediction is positive, and it is false. You had

predicted that England would win, but it lost.
 Naïve Bayes

 Diagnostics of Classifiers:

 False Negative Rate (FNR) shows what percent of

positives the classifier marked as negatives. It is also
known as the miss rate or type II error rate.
 Naïve Bayes

 Diagnostics of Classifiers:

 Your prediction is negative, and result it is also false.

 You had predicted that France would not win, but it

won.
 Naïve Bayes

 Diagnostics of Classifiers:

 Accuracy: a metric defining the rate at which a

model has classified the records correctly. It is
defined as the sum of TP and TN divided by the total
number of instances.

Accuracy = TP + TN/ (TP + TN + FP + FN) * 100

 Naïve Bayes

 Accuracy Metrics:

 Precision is the percentage of instances marked

positive that really are positive.

Precision = TP / (TP + FP)

 Naïve Bayes

 Accuracy Metrics:

 Recall is the percentage of positive instances that

were correctly identified. Recall is equivalent to the
TPR.
 Naïve Bayes

 Receiver Operating Characteristic(ROC), a term used

in signal detection to characterize the trade-off
between hit rate and false-alarm rate over a noisy
channel.
 Additional Classification Methods
 Bagging: uses the bootstrap technique that repeatedly samples
with replacement from a dataset according to a uniform
probability distribution.
 “With replacement” means that when a sample is selected for a
training or testing set, the sample is still kept in the dataset and
may be selected again.