Clustering and Classification
131
FD is simply defined as the DFT of the sequence z i , i = 0, 1,…, K − 1. Plotting the
magnitude of the FD would identify the existence of the high- and low-frequency
variations on the contour. The small energy of the high-frequency coefficients shows
that the contour is a smooth one. On the other hand, if the absolute value or energy
of the high-frequency coefficients is large, the contour has many jumps and discontinuities. The energy of the FD coefficients is sometimes used directly as a feature
in the classification process. This feature simply identifies the smoothness of the
contour quantitatively.
FDs are also used for compression of the contour data. Specifically, if the highfrequency jitters are not of any significance, one can express the contour using only
the low- and medium-frequency coefficients. This is an important technique that
helps the storage of the contour information in applications such as cell image processing, where the large number of cells often prevents the storage of all detailed
contour information.
Now that we know some of the practically important features in signal and image
processing, we can start describing some of the fundamental techniques in clustering
and classification.
7.4 K-MEANS: A SIMPLE CLUSTERING METHOD
K-means is one of the most popular techniques heavily used in biomedical signal
and image analysis. In K-means, it is assumed that there are “K” groups of patterns in the data and the algorithm attempts to find the optimal clusters based
on this assumption. Assume that n samples (patterns or examples) x 0 , x 1 ,…, x n−1
are given and K-means is to be used to create K clusters from the data. Each of
the clusters will have a cluster center, and each pattern will be assigned to one
of the clusters. The way K-means works is rather simple: iteratively find the best
centers of each cluster and then assign each pattern to the cluster whose center is
the closet to the pattern.
The training of K-means method can be described in the following steps:
Step 0: Randomly initialize the centers m 0 , m 1 ,…, m K−1 .
Step 1: Find the distance of all samples x 0 , x 1 ,…, x n−1 from all centers m 0 ,
m 1 ,…, m K−1 , i.e., for all i = 0,…, n − 1 and j = 0,…, K − 1 find
1
d x
ij ( ,
i m j ) = x i − m
2
j = ( (x i1 − m j1 ) + .+ (x ip − m jp )
2
)
2
(7.3)
Step 2: Form clusters j = 1, 2,…, K − 1 by assigning each sample to the closet
center, i.e., put together all examples whose distance to center j is minimal
to form class j.
Step 3: Find the new centers by finding the sample that is the closet sample
to the average of all samples in the class, i.e., new m j is the average of all
examples in class j.
131
FD is simply defined as the DFT of the sequence z i , i = 0, 1,…, K − 1. Plotting the
magnitude of the FD would identify the existence of the high- and low-frequency
variations on the contour. The small energy of the high-frequency coefficients shows
that the contour is a smooth one. On the other hand, if the absolute value or energy
of the high-frequency coefficients is large, the contour has many jumps and discontinuities. The energy of the FD coefficients is sometimes used directly as a feature
in the classification process. This feature simply identifies the smoothness of the
contour quantitatively.
FDs are also used for compression of the contour data. Specifically, if the highfrequency jitters are not of any significance, one can express the contour using only
the low- and medium-frequency coefficients. This is an important technique that
helps the storage of the contour information in applications such as cell image processing, where the large number of cells often prevents the storage of all detailed
contour information.
Now that we know some of the practically important features in signal and image
processing, we can start describing some of the fundamental techniques in clustering
and classification.
7.4 K-MEANS: A SIMPLE CLUSTERING METHOD
K-means is one of the most popular techniques heavily used in biomedical signal
and image analysis. In K-means, it is assumed that there are “K” groups of patterns in the data and the algorithm attempts to find the optimal clusters based
on this assumption. Assume that n samples (patterns or examples) x 0 , x 1 ,…, x n−1
are given and K-means is to be used to create K clusters from the data. Each of
the clusters will have a cluster center, and each pattern will be assigned to one
of the clusters. The way K-means works is rather simple: iteratively find the best
centers of each cluster and then assign each pattern to the cluster whose center is
the closet to the pattern.
The training of K-means method can be described in the following steps:
Step 0: Randomly initialize the centers m 0 , m 1 ,…, m K−1 .
Step 1: Find the distance of all samples x 0 , x 1 ,…, x n−1 from all centers m 0 ,
m 1 ,…, m K−1 , i.e., for all i = 0,…, n − 1 and j = 0,…, K − 1 find
1
d x
ij ( ,
i m j ) = x i − m
2
j = ( (x i1 − m j1 ) + .+ (x ip − m jp )
2
)
2
(7.3)
Step 2: Form clusters j = 1, 2,…, K − 1 by assigning each sample to the closet
center, i.e., put together all examples whose distance to center j is minimal
to form class j.
Step 3: Find the new centers by finding the sample that is the closet sample
to the average of all samples in the class, i.e., new m j is the average of all
examples in class j.