Machine Learning
Module-4
K-means Clustering Algorithm
Basic Algorithm:
Step 0: select K
Step 1: randomly select initial cluster seeds
Step 2: An initial cluster seed represents the “mean value” of its cluster
Step 3: Calculate distance from each object to each cluster seed.
• What type of distance should we use?
• Squared Euclidean distance
Step 4: Assign each object to the closest cluster
Step 5: Compute the new centroid for each cluster
Step 6: Iterate
• Calculate distance from objects to cluster centroids.
• Assign objects to closest cluster
• Recalculate new centroids
Step 7: Stop based on convergence criteria
• No change in clusters
• Max iterations
Example
Cluster the following eight points (with (x, y) representing locations) into three clusters:
A1(2, 10), A2(2, 5), A3(8, 4), A4(5, 8), A5(7, 5), A6(6, 4), A7(1, 2), A8(4, 9)
Initial cluster centers are: A1(2, 10), A4(5, 8) and A7(1, 2).
The distance function between two points a = (x1, y1) and b = (x2, y2) is defined as - Ρ(a, b) = |x2 – x1| + |y2 – y1|
Point Distance from C1 Distance from C1 Distance from C1 Cluster
centroid centroid centroid
A1(2,10) 0 5 9 C1
A2(2,5) 5 6 4 C3
A3(8, 4) 12 7 9 C2
A4(5, 8) 5 0 10 C2
A5(7, 5) 10 5 9 C2
A6(6, 4) 10 5 7 C2
A7(1, 2) 9 10 0 C3
A8(4, 9) 3 2 10 C2
Contd…
New centroids of the clusters: C1 (2, 10), C2(6, 6), C3(1.5, 3.5)
Distance from Distance from Distance from
Point belongs to
Given Points center (2, 10) of center (6, 6) of center (1.5, 3.5) of
Cluster
Cluster-01 Cluster-02 Cluster-03
A1(2, 10) 0 8 7 C1
A2(2, 5) 5 5 2 C3
A3(8, 4) 12 4 7 C2
A4(5, 8) 5 3 8 C2
A5(7, 5) 10 2 7 C2
A6(6, 4) 10 2 5 C2
A7(1, 2) 9 9 2 C3
A8(4, 9) 3 5 8 C1
New centroids of the clusters: C1 (3, 9.5), C2(6.5, 5.25), C3(1.5, 3.5)
Self Organizing Map
• Each input node is
connected to all output
nodes
• Every SOM has two
layers
• There is no connectivity
between the output
nodes
Grid topology can be square, hexagonal, etc.
• It is an unsupervised neural network that is trained using an
unsupervised learning techniques to produce discretized
representation from the input space known as a map.
• SOM’s are very different from other ANN as they apply competitive
learning techniques instead of error correction learning methods such
as backpropagation with SGD.
• It also uses a neighborhood function to preserve all the topological
properties of the input space.
SOM Algorithm
• Let’s say an input data of size (m, n) where m is the number of training examples and n is the number of
features in each example. Let C be the number of clusters.
• First, create a network with two layers, as specified earlier and initialize the weights randomly.
• Then iterating over the input data, for each training example, update the winning vector (weight vector with
the shortest distance (e.g Euclidean distance) from training example).
• Weight updation rule is given by : wij = wij(old) + alpha(t) * (xik - wij(old)) where alpha is a learning rate at
time t, j denotes the winning vector and all vectors within a specific neighborhood of j, i denotes the ith
feature of training example and k denotes the kth training example from the input data.
• After training the SOM network, trained weights are used for clustering new examples.
• A new example falls in the cluster of winning vectors.
Learning Vector Quantization
• LVQ classification is based on the Euclidian distance as
a measure of how similar the given data is to the so-
called prototypes.
• The prototypes are determined during the training
procedure using a labeled dataset.
• The idea is to start with some initial positions of the
prototypes in the feature space, and then improve
them in such way that in the end they represent the
labeled data in a best possible way.
• Attractive feature of LVQ is that it can be easily
applied to a multi-class problem.
• Depending on the complexity of the labeled data, we
choose the number of prototypes that are involved in
representation of each class.
• This number can vary from only a single prototype per Each test point is labeled based on the label of
class (if class separations are simple) to a large the closest prototype
number of prototypes per class (if class separations
are complex).
• Also, different classes can involve different number of
prototypes depending on their distribution in space.
LVQ Contd…
• Vector Quantization is a technique that exploits the underlying structure of input vectors for the purpose of
data compression.
• An input space is divided in a number of distinct regions and for each region a representative is defined.
• When the quantizer is presented with a new input vector, the region in which the vector lies is first
determined, and is then represented by the reproduction vector for this region.
• The collection of all possible reproduction vectors is called the code book of the quantizer and its members
are called code words.
• A vector quantizer with minimum encoding distortion is called
Voronoi or nearest-neighbour quantizer, since the Voronoi
cells about a set of points in an input space correspond to a
partition of that space according to the nearest-neighbour
rule based on the Euclidean metric.
• An example with an input space divided to four cells and their
associated Voronoi vectors is shown in the adjoining figure:
The Algorithm
Let us denote {wj}j=1l the set of Voronoi vectors, and let {xi}i=1N be the ALGORITHM SUMMARY
set of input vectors. We assume that N >> l
The LVQ algorithm proceeds as follows: 1. An input vector x is picked at
random from the input space.
The initial prototypes are chosen at random from some training data. 2. If the class labels of the input vector
Then for each input data point xi and a Voronoi vector w agree, the
Voronoi vector is moved in the
If the prototype wc is the closest to the input vector xi. direction of the input vector x.
and if Cwc and Cxi denote the class labels associated with wc 3. If, on the other hand, the class labels
and xi respectively of the input vector and the Voronoi
vector disagree, the Voronoi vector
Then the prototype wc is adjusted as follows: w is moved away from the input
If Cwc = Cxi then Wc(n+1)= wc(n) + an[xi- wc(n)], vector x.
If Cwc Cxi then Wc(n+1)= wc(n) - an[xi- wc(n)]
where 0< an <1
The other prototypes are not modified. an is gradually decreased.
After several passes through the input data the prototypes converge.
LVQ by SOM
Example
(x1, x2, x3, x4) C For correct classification wnew = wold + 0.1(x - w)
1100 1 For wrong classification wnew = wold - 0.1(x - w)
0001 2
Input D1 D2 Correct / New weights
0011 2 Wrong
1000 1 0011 4 1 Correct P2= 0.1,0.1,0.1,1.1
0110 2 1000 1 2.2 Correct P1 = 1.1,1.1,0.1,0.1
0110 2 3 Wrong P1 = 0.9,0.9,0.1,0.1
Initialization: Results after iteration number 1
P1: 1100
P2: 0001
𝛼=0.1
LVQ2
LVQ2.1