Image Processing Reference

In-Depth Information

cluster validity indices (Rutkowski, 2008). In general, three distinctive approaches to clus-

ter validity are possible. The first approach relies on external criteria that investigate the

existence of some predefined structure in clustered data set. The second approach makes

use of internal criteria and the clustering results are evaluated by quantities describing the

data set such as proximity matrix etc. Approaches based on internal and external criteria

make use of statistical tests and their disadvantage is high computational cost. The third

approach makes use of relative criteria and relies on finding the best clustering scheme that

meets certain assumptions and requires predefined input parameters values. Most com-

monly used indices are Dunn index, Davies-Bouldin index, S Dbw index and Quantization

Error.

Quantitative Measure: β-index

The β-index measures the ratio of the total variation and within-class variation. Define

n
i
as the number of objects in the i-th (i = 1, . . . , k) cluster from segmented image. Define

X
ij
as the value of j-th data object (j = 1, . . . , n
i
) in the cluster i and X
i
the mean of n
i

values of the i-th cluster. The β-index is defined in the following way

β-index =
P
i=1
P
n
i

(X
ij
−X)
2

j

=1

P
i=1
P
n
i

(X
ij
−X
i
)
2

j

=1

where X represents the mean value of all universe objects attributes. This index defines

the ratio of the total variation and the within-class variation. In this context, important

notice is the fact that β-index value increases as the increase of k number of cluster centers.

Davies-Bouldin index

The Davies-Bouldin index minimizes the average similarity between each cluster. It is

defined as the the ratio of the sum of within-cluster scatter to between-cluster separation.

The objective is to minimize this index. The Davies-Boludin index is defined as follows:

k

X

1

k

max
j=1,...,k,i6=j
(
diam(C
i
) + diam(C
j
)

d(C
i
, C
j
)

DB =

)

i=1

where d(u, w) represents the Euclidean distance between u and w and diam(C) is the

diameter of a cluster which can be defined as

diam(C) = max

u,w∈C

d(u, w)

Dunn index

The Dunn index is a well known validity index, proposed by (Bezdek and Pal, 1995)

that recognizes compact and well separated clusters by means of considering five different

measures of distance between clusters and three different measures of cluster diameter. The

value of the Dunn index should be maximized and is defined in the following way

n
min
j=i+1,...,k

o

dist(C
i
,C
j
)

max
a=1,...,i
diam

D =

min

i=1,...,k

(

C
a
)

where dist(C
k
, C
p
) represents the dissimilarity function between two clusters C
k
and C
p

calculated as

Search WWH ::

Custom Search