Digital Signal Processing Reference
In-Depth Information
11.7.2
Splitting Criteria
C
(
k
)
c
Let us denote by
the cluster that can be tentatively split into two
subclusters. We use two statistics from the field of cluster analysis
38
,
63
(
n
−
1
)
that
(
)
=
rely on the sum of squared errors
J
e
g
,
g
1
,
2, to test the validity of the
following possibilities:
C
(
k
)
c
1. Cluster
(
n
−
1
)
is kept united
(
g
=
1
)
.
C
(
k
)
c
2. Cluster
(
n
−
1
)
is subdivided into two clusters
(
g
=
2
)
, say,
C
(
k
ζ
(
C
(
k
η
(
n
−
1
)
and
n
−
1
)
.
First let us define the sum of squared errors in cases (1) and (2) outlined above.
We have
x
j
x
j
∈C
(
k
)
c
2
m
(
k
)
c
−
(
n
−
1
)
for
g
=
1
(
n
−
1
)
J
e
(
g
)
=
(11.98)
x
j
γ
∈{
ζ
,
η
}
x
j
∈C
(
k
γ
(
n
−
1
)
2
m
(
k
γ
(
−
n
−
1
)
for
g
=
2
,
where
m
(
k
ζ
(
and
m
(
k
η
(
denote the sample mean vectors of the
resulting subclusters. In the sequel, we describe how a tentative splitting is
performed.
We determine the direction in which cluster
n
−
1
)
n
−
1
)
C
(
k
)
c
variation is greatest.
This is equivalent to finding the first principal component of the sample dis-
persion matrix (i.e., the eigenvector that corresponds to the largest eigenvalue
of
S
(
k
)
c
(
n
−
1
)
). Let us denote by
e
(
k
)
c
(
n
−
1
)
(
n
−
1
)
the first normalized principal eigen-
vector of
S
(
k
)
c
(
−
)
. Having determined
e
(
k
)
c
(
−
)
n
1
n
1
,weexamine the splitting
C
(
k
)
c
(
−
)
of cluster
n
1
with a hyperplane that is perpendicular to the direction
of
e
(
i
)
c
(
n
−
1
)
and passes through the sample mean
m
(
k
)
c
(
n
−
1
)
. Therefore, all
C
(
k
ζ
(
C
(
k
)
c
C
(
k
η
(
patterns in
(
n
−
1
)
are sorted into sets
n
−
1
)
and
n
−
1
)
as follows:
C
(
k
ζ
(
−
)
n
1
=
x
)
∈ C
(
k
)
c
:
e
(
k
)
c
T
x
e
(
k
)
c
T
m
(
k
)
c
(
n
−
1
)
(
n
−
1
)
≤
(
n
−
1
)
(
n
−
1
(11.99)
C
(
k
η
(
n
−
1
)
=
x
)
.
∈ C
(
k
)
c
:
e
(
k
)
c
T
x
e
(
k
)
c
T
m
(
k
)
c
(
n
−
1
)
(
n
−
1
)
>
(
n
−
1
)
(
n
−
1
As mentioned earlier, splitting any cluster into two subclusters will result in a
lower sum of squared errors, i.e.,
J
e
(
.Wedecide to consider as valid
any splitting that yields a statistically significant improvement (i.e., decrease)
in the sum of squared errors. To this end, a binary hypothesis-testing problem
is formulated as follows.
63
Under the null hypothesis we assume that there is exactly one cluster
present. Furthermore, it is assumed that all
z
(
k
)
c
2
)<
J
e
(
1
)
patterns come from
a multivariate distribution with mean
µ
and covariance matrix
(
n
−
1
)
2
I
.Inother
σ
Search WWH ::
Custom Search