Database Reference
In-Depth Information
Proposition 8.7
Let
(
V
,
h
,
i
)
be an inner product space and S V. Then, for
all c
,
w
V
,
∈
h
c
;
w
i kk
min
v
∈
S
k
v c
k
max
v
∈
S
h
v
;
w
i c
h
;
w
i þ kk
max
v
∈
S
k
v c
k
Proof Taking maximums on both sides of the rightmost inequality of the above
Lemma yields
max
v
∈
S
h
v
;
w
i
max
v
∈
S
ð
h
c
;
w
i þ kkv c
k
k
Þ
max
v
∈
S
h
c
;
w
i þ
max
v
∈
S
ð
kkv c
k
k
Þ
¼ c
h
;
w
iþkk
max
v
∈
S
k
v c
k:
Similarly, by taking maximums in the left inequality, we obtain
max
v
∈
S
h
v
;
w
i
max
v
∈
S
ð
h
c
;
w
i þ kkv c
k
k
Þ
max
v
∈
S
h
c
;
w
i þ
min
v
∈
S
ð
kkv c
k
k
Þ
¼ c
h
;
w
iþkk
min
v
∈
S
k
v c
k:
□
This result equips us with a means to enclose the exact maximum inner product
between a vector in the considered cluster and a given vector, while the only
information that is required is the inner product between the given vector and the
cluster center and the maximum distance from the cluster center. The latter,
emerging as a side product of the foregoing clustering procedure, may safely be
regarded as readily available.
By virtue of our bound, we may retrofit our branching heuristic into a full-blown
branch-and-bound procedure which computes the exact result, though forfeiting a
large degree of efficiency. To balance the tradeoff between fast computation and
accuracy, we introduce a parameter
h
[0;1] to relax the bound.
Let
T
denote the refinement tree obtained from recursive k-means clustering of
the
x
i
, and let
children
(.) denote the functions that map a node of
T
to the set of its
children. We define for
t
∈
T
∈
u
h
ðÞ:¼ c
t
;
h
y
i þhkk
max
i
∈
C
t
k
x
i
c
t
k
,
l
h
ðÞ:¼ c
t
;
h
y
i hkk
min
i
∈
C
t
k
x
i
c
t
k
,
where
C
t
,
c
t
denote the cluster and cluster center corresponding to
t
,respectively.
Moreover, in the below-described algorithm,
select
_
node
(
) denotes some function
which judiciously picks the next node to be refined from a list of candidate nodes (one
may, e.g., choose the node
t
with the greatest upper bound
u
h
(
t
) among all nodes in
the list).
