3040233302

Data Warehouse and Data Mining

5: Classification and Clustering
SEMESTER: 5
PREPARED BY: Ms. Kiran Rajput
 Classification
• Classification and Cluster Analysis: Basic Concepts
– Basic Concepts of Classification
– What is Classification?
– General approach to Classification
– Decision Tree Induction
– Bayes Classification method
– Basic Concepts of Clustering
– What is Cluster Analysis?
– Requirements of Cluster Analysis
– Overview of Basic Clustering Methods
– Partitioning Methods
– K-Means: A centroid based technique
 Basic concepts of classification
• Classification is a form of data analysis that extracts
models describing important data classes.
• Such models, called classifiers, predict categorical (discrete,
unordered) class labels.
• For example,we can build a classification model to categorize
bank loan applications as either safe or risky.
• Such analysis can help provide us with a better understanding
of the data at large.
 Basic concepts of classification
• 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 amounts of disk-resident data.
• Classification has numerous applications, including fraud
detection, target marketing, performance prediction,
manufacturing, and medical diagnosis.
 What is classification
• A bank loans officer needs analysis of her data
to learn which loan applicants are “safe” and
which are “risky” for the bank.
• A marketing manager at AllElectronics needs
data analysis to help guess whether a customer
with a given profile will buy a new computer.
• A medical researcher wants to analyze breast
cancer data to predict which one of three
specific treatments a patient should receive..
 What is classification
• In each of these examples, the data analysis task is
classification, where a model or classifier is constructed
to predict class (categorical) labels,
– such as “safe” or “risky” for the loan application data;
– “yes” or “no” for the marketing data; or
– “treatment A,” “treatment B,” or “treatment C” for the medical
data.
• These categories can be represented by discrete values,
where the ordering among values has no meaning.
• For example, the values 1, 2, and 3 may be used to represent
treatments A, B, and C, where there is no ordering implied
among this group of treatment regimes.
General Approach to Classification
• “How does classification work?”
• Data classification is a two-step process,
consisting of a learning step (where a
classification model is constructed) and a
classification step (where the model is used to
predict class labels for given data).
• The process is shown for the loan application
data of Figure A. (The data are simplified for
illustrative purposes).
 Classification- 2 Step Process
• In the first step, a classifier is built describing a
predetermined set of data classes or concepts.
• This is the learning step (or training phase), where a
classification algorithm builds the classifier by
analyzing or “learning from” a training set made up of
database tuples and their associated class labels.
• A tuple, X, is represented by an n-dimensional
attribute vector, X D .x1, x2, : : : , xn/, depicting n
measurements made on the tuple from n database
attributes, respectively, A1, A2, : : : , An.1
 Classification- 2 Step Process
• Each tuple, X, is assumed to belong to a predefined
class as determined by another database attribute called
the class label attribute.
• The class label attribute is discrete-valued and
unordered. It is categorical (or nominal) in that each
value serves as a category or class.
• The individual tuples making up the training set are
referred to as training tuples and are randomly
sampled from the database under analysis.
• In the context of classification, data tuples can be
referred to as samples, examples, instances, data points,
or objects.
 Data Classification

The data classification process: (a) 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 formof classification rules. (b) Classification: Test data are used to estimate
the accuracy of the classification rules. If the accuracy is considered acceptable, the rules can
be applied to the classification of new data tuples.
 Data Classification

The data classification process: (a) 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 formof classification rules. (b) Classification: Test data are used to
estimate the accuracy of the classification rules. If the accuracy is considered acceptable,
the rules can be applied to the classification of new data tuples.
 Data Classification
• Because the class label of each training tuple is provided,
this step is also known as supervised learning (i.e., the
learning of the classifier is “supervised” in that it is told to
which class each training tuple belongs.
• It contrasts with unsupervised learning (or clustering), in
which the class label of each training tuple is not known,
and the number or set of classes to be learned may not be
known in advance.
• For example, if we did not have the loan decision data
available for the training set, we could use clustering to try
to determine “groups of like tuples,” which may correspond
to risk groups within the loan
• application data.
“What about classification accuracy?”
• In the second step (Figure b), the model is used for
classification.
• First, the predictive accuracy of the classifier is estimated.
• If we were to use the training set to measure the classifier’s
accuracy, this estimate would likely be optimistic, because
the classifier tends to overfit the data (i.e., during
learning it may incorporate some particular anomalies of
the training data that are not present in the general data set
overall).
• Therefore, a test set is used, made up of test tuples and
their associated class labels.
• They are independent of the training tuples, meaning that
they were not used to construct the classifier.
“What about classification accuracy?”
• The accuracy of a classifier on a given test set is the
percentage of test set tuples that are correctly classified
by the classifier. The associated class label of each test tuple
is compared with the learned classifier’s class prediction for
that tuple.
• If the accuracy of the classifier is considered acceptable, the
classifier can be used to classify future data tuples for which
the class label is not known. (Such data are also referred to
in the machine learning literature as “unknown” or
“previously unseen” data.)
• For example, the classification rules learned in Figure (a)
from the analysis of data from previous loan applications
canbe used to approve or reject new or future loan
applicants.
 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 each internal node (nonleaf
node) denotes a test on an attribute, each branch
represents an outcome of the test, and each leaf
node (or terminal node) holds a class label.
• The topmost node in a tree is the root node.
Decision Tree
 Decision Tree Induction
• A typical decision tree is shown in Figure below.
• It represents the concept buys computer, that is, it
predicts whether a customer at AllElectronics is
likely to purchase a computer.
• Internal nodes are denoted by rectangles, and leaf
nodes are denoted by ovals.
• Some decision tree algorithms produce only
binary trees (where each internal node branches to
exactly two other nodes), whereas others can
produce nonbinary trees.
 Decision Tree Induction

A decision tree for the concept buys computer, indicating whether an AllElectronics
customer is likely to purchase a computer.
Each internal (nonleaf) node represents a test on an attribute.
Each leaf node represents a class (either buys computer = yes or buys computer = no).
 How are decision trees used for
classification
• “How are decision trees used for classification?”
• Given a tuple, X, for which the associated class
label is unknown, the attribute values of the tuple
are tested against the decision tree.
• A path is traced from the root to a leaf node,
which holds the class prediction for that tuples.
• Decision trees can easily be converted to
classification rules.
• During tree construction, attribute selection
measures are used to select the attribute that best
partitions the tuples into distinct classes.
 Terminologies related to decision tree
• Root Node: Root node is from where the decision
tree starts. It represents the entire dataset, which
further gets divided into two or more
homogeneous sets.
• Leaf Node: Leaf nodes are the final output node,
and the tree cannot be segregated further after
getting a leaf node.
• Splitting: Splitting is the process of dividing the
decision node/root node into sub-nodes according
to the given conditions.
 Terminologies related to decision tree
• Branch/Sub Tree: A tree formed by splitting
the tree.
• Pruning: Pruning is the process of removing
the unwanted branches from the tree.
• Parent/Child node: The root node of the tree
is called the parent node, and other nodes are
called the child nodes.
 How does the Decision Tree
algorithm Work?
• In a decision tree, for predicting the class of
the given dataset, the algorithm starts from the
root node of the tree.
• This algorithm compares the values of root
attribute with the record (real dataset) attribute
and, based on the comparison, follows the
branch and jumps to the next node.
 How does the Decision Tree
algorithm Work?
• Step-1: Begin the tree with the root node, says S, which
contains the complete dataset.
• Step-2: Find the best attribute in the dataset
using Attribute Selection Measure (ASM).
• Step-3: Divide the S into subsets that contains possible
values for the best attributes.
• Step-4: Generate the decision tree node, which contains the
best attribute.
• Step-5: Recursively make new decision trees using the
subsets of the dataset created in step -3. Continue this
process until a stage is reached where you cannot further
classify the nodes and called the final node as a leaf node.
 Example:
• Example: Suppose there is a candidate who has a job offer
and wants to decide whether he should accept the offer or
Not.
• So, to solve this problem, the decision tree starts with the
root node (Salary attribute by ASM).
• The root node splits further into the next decision node
(distance from the office) and one leaf node based on the
corresponding labels.
• The next decision node further gets split into one decision
node (Cab facility) and one leaf node.
• Finally, the decision node splits into two leaf nodes
(Accepted offers and Declined offer).
• Consider the below diagram:
Example:
 Attribute Selection Measures
• Information Gain:
– Information gain is the measurement of changes in entropy
after the segmentation of a dataset based on an attribute.
– It calculates how much information a feature provides us
about a class.
– According to the value of information gain, we split the
node and build the decision tree.
– A decision tree algorithm always tries to maximize the
value of information gain, and a node/attribute having the
highest information gain is split first. It can be calculated
using the below formula:
– Information Gain= Entropy(S)-
[(Weighted Avg) *Entropy(each feature
 Attribute Selection Measures
• Entropy:
– Entropy is a metric to measure the impurity in a given
attribute. It specifies randomness in data. Entropy can be
calculated as:
Entropy(s)= -P(yes)log2 P(yes)- P(no) log2 P(no)

Where,
• S= Total number of samples
• P(yes)= probability of yes
• P(no)= probability of no
–
 Attribute Selection Measures
• Gini Index:
– Gini index is a measure of impurity or purity used
while creating a decision tree in the
CART(Classification and Regression Tree) algorithm.
– An attribute with the low Gini index should be
preferred as compared to the high Gini index.
– It only creates binary splits, and the CART algorithm
uses the Gini index to create binary splits.
– Gini index can be calculated using the below formula:
• Gini Index= 1- ∑jPj2
 Bayesian Classification Method
• A statistical classifier: performs probabilistic prediction, i.e.,
predicts class membership probabilities
• Foundation: Based on Bayes’ Theorem.
• Performance: A simple Bayesian classifier, naïve Bayesian
classifier, has comparable performance with decision tree and
selected neural network classifiers
• Incremental: Each training example can incrementally
increase/decrease the probability that a hypothesis is correct —
prior knowledge can be combined with observed data
• Standard: Even when Bayesian methods are computationally
intractable, they can provide a standard of optimal decision
making against which other methods can be measured
 Bayesian Theorem Basics
• Total probability Theorem:

• Bayes’ Theorem:

– Let X be a data sample (“evidence”): class label is unknown

– Let H be a hypothesis that X belongs to class C
– Classification is to determine P(H|X), (i.e., posteriori probability): the
probability that the hypothesis holds given the observed data sample X
– P(H) (prior probability): the initial probability
• E.g., X will buy computer, regardless of age, income, …
– P(X): probability that sample data is observed
– P(X|H) (likelihood): the probability of observing the sample X, given that
the hypothesis holds
• E.g., Given that X will buy computer, the prob. that X is 31..40,
medium income
 Prediction based on Bayes Theorem
• Given training data X, posteriori probability of a hypothesis H,
P(H|X), follows the Bayes’ theorem

P( H | X) = P(X | H ) P( H ) = P(X | H ) P( H ) / P(X)

P(X)
• Informally, this can be viewed as
posteriori = likelihood x prior/evidence
• Predicts X belongs to Ci iff the probability P(Ci|X) is the highest
among all the P(Ck|X) for all the k classes
• Practical difficulty: It requires initial knowledge of many
probabilities, involving significant computational cost
 Classification is to derive maximum
posteriori
• 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 )
P(C | X) = i i
i P(X)
• Since P(X) is constant for all classes, only
P(C | X) = P(X | C )P(C )
i i i
needs to be maximized
 Naïve Bayes Classifier-Data Set
age income studentcredit_rating
buys_compu
<=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
 Example
• P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643
P(buys_computer = “no”) = 5/14= 0.357
• Compute P(X|Ci) for each class
P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222
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
Therefore, X belongs to class (“buys_computer = yes”)
 Naïve Bayes Classifier
• 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
 Basic Concepts of Clustering
• Imagine that you are the Director of Customer
Relationships at AllElectronics, and you have
five managers working for you.
• You would like to organize all the company’s
customers into five groups so that each group can
be assigned to a different manager.
• Strategically, you would like that the customers in
each group are as similar as possible.
• Moreover, two given customers having very
different business patterns should not be placed in
the same group.
 Basic Concepts of Clustering
• Your intention behind this business strategy is
to develop customer relationship campaigns
that specifically target each group, based on
common features shared by the customers per
group.
• What kind of data mining techniques can help
you to accomplish this task?
 Basic Concepts of Clustering
• Unlike in classification, the class label (or
group ID) of each customer is unknown.
• You need to discover these groupings.
• Given a large number of customers and many
attributes describing customer profiles, it can be
very costly or even infeasible to have a human
study the data and manually come up with a way
to partition the customers into strategic groups.
• You need a clustering tool to help.
 Clustering
• Clustering is the process of grouping a set of
data objects into multiple groups or clusters so
that objects within a cluster have high
similarity, but are very dissimilar to objects in
other clusters.
• Dissimilarities and similarities are assessed based
on the attribute values describing the objects and
often involve distance measures.
• Clustering as a data mining tool has its roots in
many application areas such as biology, security,
business intelligence, and Web search.
 Cluster Analysis
• What is cluster Analysis:
• Cluster analysis or simply clustering is the
process of partitioning a set of data objects
(or observations) into subsets.
• Each subset is a cluster, such that objects in a
cluster are similar to one another, yet
dissimilar to objects in other clusters.
• The set of clusters resulting from a cluster
analysis can be referred to as a clustering.
 Cluster Analysis
• In this context, different clustering methods
may generate different clusterings on the same
data set.
• The partitioning is not performed by humans,
but by the clustering algorithm.
• Hence, clustering is useful in that it can lead to
the discovery of previously unknown groups
within the data.
 Application of Clustering
• Cluster analysis has been widely used in many
applications such as business intelligence, image
pattern recognition, Web search, biology, and
security.
• In business intelligence, clustering can be used
to organize a large number of customers into
groups, where customers within a group share
strong similar characteristics.
– This facilitates the development of business strategies
for enhanced customer relationship management.
 Application of Clustering
– To improve project management, clustering can
be applied to partition projects into categories
based on similarity so that project auditing and
diagnosis (to improve project delivery and
outcomes) can be conducted effectively.
– In image recognition, clustering can be used to
discover clusters or “subclasses” in handwritten
character recognition systems.
 Application of Clustering
– Clustering has also found many applications in Web
search.
• For example, a keyword search may often return a very large
number of hits (i.e., pages relevant to the search) due to the
extremely large number of web pages.
• Clustering can be used to organize the search results into
groups and present the results in a concise and easily
accessible way.
– Moreover, clustering techniques have been developed
to cluster documents into topics, which are
commonly used in information retrieval practice.
 Requirements for Cluster Analysis
• The following are typical requirements of
clustering in data mining.
• Scalability:
– Many clustering algorithms work well on small
data sets containing fewer than several hundred data
objects; however, a large database may contain
millions or even billions of objects, particularly in Web
search scenarios.
– Clustering on only a sample of a given large data set
may lead to biased results.
– Therefore, highly scalable clustering algorithms are
needed.
 Requirements for Cluster Analysis
• Ability to deal with different types of
attributes:
– Many algorithms are designed to cluster numeric
(interval-based) data.
– However, applications may require clustering
other data types, such as binary, nominal (categorical),
and ordinal data, or mixtures of these data types.
– Recently, more and more applications need clustering
techniques for complex data types such as graphs,
sequences, images, and documents.
 Requirements for Cluster Analysis
• Discovery of clusters with arbitrary shape:
– Many clustering algorithms determine clusters based on
Euclidean or Manhattan distance measures.
– Algorithms based on such distance measures tend to find
spherical clusters with similar size and density.
– However, a cluster could be of any shape. Consider
sensors, for example, which are often deployed for
environment surveillance. Cluster analysis on sensor
readings can detect interesting phenomena.
– We may want to use clustering to find the frontier of a
running forest fire, which is often not spherical.
– It is important to develop algorithms that can detect
clusters of arbitrary shape.
 Requirements for Cluster Analysis
• Requirements for domain knowledge to determine
input parameters:
– Many clustering algorithms require users to provide
domain knowledge in the form of input parameters such as
the desired number of clusters.
– Consequently, the clustering results may be sensitive to
such parameters.
– Parameters are often hard to determine, especially for
high-dimensionality data sets and where users have yet to
grasp a deep understanding of their data.
– Requiring the specification of domain knowledge not
only burdens users, but also makes the quality of
clustering difficult to control.
 Requirements for Cluster Analysis
• Ability to deal with noisy data:
– Most real-world data sets contain outliers and/or
missing, unknown, or erroneous data.
– Sensor readings, for example, are often noisy—some
readings may be inaccurate due to the sensing
mechanisms, and some readings may be erroneous due
to interferences from surrounding transient objects.
– Clustering algorithms can be sensitive to such noise
and may produce poor-quality clusters.
– Therefore, we need clustering methods that are robust
to noise.
 Requirements for Cluster Analysis
• Incremental clustering and insensitivity to input order:
– In many applications, incremental updates (representing newer
data) may arrive at any time.
– Some clustering algorithms cannot incorporate incremental
updates into existing clustering structures and, instead, have to
recompute a new clustering from scratch.
– Clustering algorithms may also be sensitive to the input data
order.
– That is, given a set of data objects, clustering algorithms may
return dramatically different clusterings depending on the order
in which the objects are presented.
– Incremental clustering algorithms and algorithms that are
insensitive to the input order are needed.
 Requirements for Cluster Analysis
• Capability of clustering high-dimensionality data:
– A data set can contain numerous dimensions or
attributes.
– When clustering documents, for example, each keyword
can be regarded as a dimension, and there are often
thousands of keywords.
– Most clustering algorithms are good at handling low-
dimensional data such as data sets involving only two or
three dimensions.
– Finding clusters of data objects in a highdimensional space
is challenging, especially considering that such data can be
very sparse and highly skewed.
Requirements for Cluster Analysis
• Constraint-based clustering:
– Real-world applications may need to perform
clustering under various kinds of constraints.
– Suppose that your job is to choose the locations for a
given number of new automatic teller machines
(ATMs) in a city.
– To decide upon this, you may cluster households while
considering constraints such as the city’s rivers and
highway networks and the types and number of
customers per cluster.
– A challenging task is to find data groups with good
clustering behavior that satisfy specified constraints.
 Requirements for Cluster Analysis
• Interpretability and usability:
• Users want clustering results to be
interpretable, comprehensible, and usable.
• That is, clustering may need to be tied in with
specific semantic interpretations and
applications.
• It is important to study how an application
goal may influence the selection of clustering
features and clustering methods.
Overview of basic Clustering Methods
• Partitioning Method-
– Given a set of n objects, a partitioning method
constructs k partitions of the data, where each
partition represents a cluster and k<= n.
– That is, it divides the data into k groups such that
each group must contain at least one object.
– In other words, partitioning methods conduct one-
level partitioning on data sets.
– The basic partitioning methods typically adopt
exclusive cluster separation.
Overview of basic Clustering Methods
• Hierarchical 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 close to one another, until
all the groups are merged into one (the topmost level of the
– hierarchy), or a termination condition holds.
– The divisive approach, also called the top-down approach, starts with
all the objects in the same cluster.
– In each successive iteration, a cluster is split into smaller clusters, until
eventually each object is in one cluster, or a termination condition
holds.
Overview of basic Clustering Methods
• Density-based methods:
– Most partitioning methods cluster objects based on the distance
between objects.
– Such methods can find only spherical-shaped clusters and encounter
difficulty in discovering clusters of arbitrary shapes.
– Other clustering methods have been developed based on the notion of
density.
– Their general idea is to continue growing a given cluster as long as the
density (number of objects or data points) in the “neighborhood”
exceeds some threshold.
– For example, for each data point within a given cluster, the
neighborhood of a given radius has to contain at least a minimum
number of points.
– Such a method can be used to filter out noise or outliers and discover
clusters of arbitrary shape.
– Density-based methods can divide a set of objects
Overview of basic Clustering Methods
• Grid-based methods:
– Grid-based methods quantize the object space into a finite number
of cells that form a grid structure.
– All the clustering operations are performed on the grid structure
(i.e., on the quantized space).
– The main advantage of this approach is its fast processing time,
which is typically independent of the number of data objects and
dependent only on the number of cells in each dimension in the
quantized space.
– Using grids is often an efficient approach to many spatial data
mining problems, including clustering.
– Therefore, grid-based methods can be integrated with other
clustering methods such as density-based methods and hierarchical
methods.
Overview of basic Clustering Methods
 Partitioning Methods
• The simplest and most fundamental version of
cluster analysis is partitioning, which
organizes the objects of a set into several
exclusive groups or clusters.
• To keep the problem specification concise, we
can assume that the number of clusters is given
as background knowledge.
• This parameter is the starting point for
partitioning methods.
 Partitioning Methods

• Formally, given a data set, D, of n objects, and k,

the number of clusters to form, a partitioning
algorithm organizes the objects into k
partitions .(k <= n), where each partition
represents a cluster.
• The clusters are formed to optimize an objective
partitioning criterion, such as a dissimilarity
function based on distance, so that the objects
within a cluster are “similar” to one another and
“dissimilar” to objects in other clusters in terms of
the data set attributes.
K-MEANS ALGORITHM - EXAMPLE

Section - 3
K-Means Algorithm - Example
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (185,7
1
4 179 68 2)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (170,5
6)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 62
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (185,7
1
4 179 68 2)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (170,5
6)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 63
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (185,7
1
4 179 68 2)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (169,
58)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 64
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (185,7
1
4 179 68 2)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (169,5
8)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 65
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (182,7
1
4 179 68 0)

5 182 72
6 188 77
7 180 71
K
8 180 70
(169,
2
9 183 84 58)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 66
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (182,7
1
4 179 68 0)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (169,5
8)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 67
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (182,7
1
4 179 68 1)

5 182 72
6 188 77
7 180 71
K
8 180 70
(169,
2
9 183 84 58)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 68
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (182,7
1
4 179 68 1)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (169,5
8)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 69
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (183,7
1
4 179 68 2)

5 182 72
6 188 77
7 180 71
K
8 180 70
(169,
2
9 183 84 58)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 70
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
3 168 60 (183,7
1
4 179 68 2)

5 182 72
6 188 77
7 180 71
K
8 180 70
2
9 183 84 (169,5
8)
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 71
K-Means Algorithm – Example Cont..
Sr. Heig Weig
ht ht
1 185 72
2 170 56 K
Cluster K1 = {1,4,5,6,7,8,9,10,11,12}
3 168 60 1
4 179 68
5 182 72
6 188 77
7 180 71
K
8 180 70
2 Cluster K2 = {2,3}
9 183 84
10 180 88
11 180 67
12 177 76
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 72
K-Means Algorithm Cont..
Let us assume two clusters, and each individual's scores include two
variables.
Step-1
⮩ Choose the number of clusters.
Step-2
⮩ Set the initial partition, and the initial mean vectors for each cluster.
Step-3
⮩ For each remaining individual...
Step-4
⮩ Get averages for comparison to the Cluster 1:
▪ Add individual's A value to the sum of A values of the individuals in Cluster 1, then
divide by the total number of scores that were summed.
▪ Add individual's B value to the sum of B values of the individuals in Cluster 1, then
divide by the total number of scores that were summed.

Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 73

K-Means Algorithm Cont..
Step-5
⮩ Get averages for comparison to the Cluster 2:
▪ Add individual's A value to the sum of A values of the individuals in Cluster 2, then
divide by the total number of scores that were summed.
▪ Add individual's B value to the sum of B values of the individuals in Cluster 2, then
divide by the total number of scores that were summed.
Step-6
⮩ If the averages found in Step 4 are closer to the mean values of Cluster 1, then this
individual belongs to Cluster 1, and the averages found now become the new mean
vectors for Cluster 1.
⮩ If closer to Cluster 2, then it goes to Cluster 2, along with the averages as new mean
vectors.
Step-7
⮩ If there are more individual's to process, continue again with Step 4.
Otherwise go to Step 8.
Step-8
⮩ Now compare each individual’s distance to its own cluster's mean vector, and
to that of the opposite cluster.
Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 74
K-Means Algorithm Cont..
Step-9
⮩ If any relocations occurred in Step 8, the algorithm must continue again with
Step 3, using all individuals and the new mean vectors.
⮩ If no relocations occurred, stop. Clustering is complete.

Prof. Naimish R Vadodariya #3160714 (DM) ⬥ Unit 5 – Cluster Analysis 75