Digital Signal Processing Reference
In-Depth Information
Based on [11-12], the objective function of K-means can be deduced into
the
f
ollowing form
J
=
max
Tr
(
TT
)
HXXH
(3)
k
×
HR
is a nonnegative indicator matrix and
∈
nK
where
1/
n
x C
∈
j
i
j
h
=
(4)
ij
0
otherwise
T
HH I
,
=
Tr
()
•
n
is the number
Clearly,
is the trace of corresponding matrix and
C
. Meanwhile, the objective function of spectral clustering can be
of points in
T
−
1/ 2
−
1/ 2
J
=
min
Tr
(
HLH
[13-14], where
)
LID WD
=−
expressed as
,
s
2
−−
xx
is a manually defined scale parameter.
D
is a
diagonal matrix whose entries are column sums of
W
, namely
w
=
exp(
)
σ ∈
R
i
j
,
ij
2
2
σ
.
d
=
w
ii
ij
j
Hence, Eq. (2) is equivalent to solve the following optimization problem
(
)
(
) (
)
−
1
T
T
T
max
Tr
HLH
HXXH
H
(5)
T
st
..
HH I
=
LX X
, and
T
Hence,
H
is composed by the largest
C
eigenvectors of the matrix
L
is the pseudo-inverse of
L
.
As we mentioned above, the full connected graph is used in the algorithm, then
the similarity between data pints is defined on it. Moreover, the frequently used KNN
graph is not an excellent approach to represent the relationship between all data
points. Hence, b-matching and sparse representation, the new two sparse graph con-
struction methods, will be used in this article to improve the KL clustering algorithm.
2.2
Sparse Graphs
2.2.1
-Matching
Every node in an adjacency graph constructed by b-matching algorithm has
b
neighbors. Construct an affinity graph for data sets by b-matching contains two steps:
graph sparsification and graph edge re-weighted.
Β
Graph Sparsification:
The objective of b-matching is to find a binary matrix to mi-
nimize the following optimization problem:
min
PS
P B
∈
ij
ij
ij
(6)
st
..
P b P
=
,
=
0,
P P
=
ij
ii
ij
ji
j
