Graphics Reference
In-Depth Information
initial choices of centroid seeds. hirdly, the algorithm may not be appropriate for
some data distributions where the metric is not uniformly defined, i.e., the idea of
“distance” has different meanings in different regions or for data belonging to differ-
ent labels.
Here we address these issues by introducing a different clustering approach,
namely support vector clustering, which allows hierarchical clusters with versatile
clustering boundaries. Below we briefly describe the idea behind SVC, as described
by Ben-Hur et al. (
). SVC was inspired by support vector machines and ker-
nelmethods.InSVC,datapointsaremappedfromthedataspace
X
to a high-
dimensional feature space
by a nonlinear transformation (
.
). his nonlinear
transformation is defined implicitly by a Gaussian kernel with
Z
Φ
(
x
)
,Φ
(
u
)
=
Z
κ
. he key idea behind SVC is to find the smallest sphere in the feature space
which encloses the data images
(
x,u
)
Φ
(
x
)
,...,Φ
(
x
n
)
. hat is, we aim to solve the
minimization problem
R
,subjectto
Z
R
,
min
a
Z
,R
Φ
(
x
j
)−
a
∀
j ,
(
.
)
where R is the radius of an enclosing sphere in
Z
.heLagrangianisintroducedto
solve the above optimization problem. Let
n
j
=
R
R
L
−
Φ
x
j
a
β
j
,
(
.
)
=
−
(
(
)−
)
where β
j
are the Lagrange multipliers. By differentiating L with respect to the
primal variables R and
a
respectively and setting the derivatives equal to zero, we
have
n
j
n
j
β
j
=
and
a
=
β
j
Φ
(
x
j
)
.
(
.
)
Moreover,thecorrespondingKarush-Kuhn-Tuckercomplementarityconditionsare
R
(
−
Φ
(
x
j
)−
a
)
β
j
=
,
∀
j .
(
.
)
Combining (
.
)and (
.
),we can eliminate the primal variables R and
a
and get
the following dual problem:
n
j
=
Φ
Z
max
β
W
(
β
)=
β
j
Φ
(
x
j
)−
(
.
)
s.t. Φ
=
j
β
j
Φ
(
x
j
)
,
β
j
=
andβ
j
.
j
hat is, the SVC algorithm aims to find a weighting scheme β so that the weighted
data spread W
β
is as wide as possible.
(
)
