Database Reference
In-Depth Information
is the distance between the two centroids of the clusters containing the two
instances that should be together. If a cannot-link constraint is violated then
the penalty is the distance between the cluster centroid the two instances are
assigned to and its (the centroid's) distance to the nearest cluster centroid.
These two penalty types give rise to a new objective function which is termed
the Constrained Vector Quantization Error (CVQE) shown in Equation 7.6
where g ( x ) returns the cluster index that instance x belongs to.
1
2
D ( μ j ,x i ) 2
CVQE j =
+
(7.6)
x i ∈μ j
1
2
D ( μ j g ( x a ) ) 2
x i
μ j , ( x i ,x a )
C = ,g ( x i )
= g ( x a )
1
2
D ( μ j h ( g ( x a )) ) 2
x i ∈μ j , ( x i ,x a ) ∈C = ,g ( x i )= g ( x a )
These penalties were found by experimentation to be useful and others (39)
(see next section) have improved upon these.
The first step of the constrained KMeans algorithm must minimize the new
constrained vector quantization error. This is achieved by assigning instances
so as to minimize the new error term. For instances that are not part of
constraints, this involves performing a nearest cluster centroid calculation as
before in regular KMeans. For pairs of instances in a constraint, for each
possible combination of cluster assignments, the CVQE is calculated and the
instances are assigned to the clusters that minimally increases the CVQE .
This is shown in Equation 7.7 and requires at most O ( k 2 ) calculations per
assignment where δ is the Kronecker Delta function.
argmin j D ( x i j ) 2
x i /
C =
C = :
(7.7)
C = : argmin i,j D ( x a i ) 2 + D ( x b j ) 2 +
D ( μ j i ) 2
( x a ,x b )
¬
δ ( a, b )
C = : argmin i,j D ( x a i ) 2 + D ( x b j ) 2 + δ ( a, b )
D ( μ j h ( μ j )) 2
( x a ,x b )
The second step is to update the cluster centroids so as to minimize the
constrained vector quantization error. To achieve this we take the first order
derivative of the error, set to zero, and solve. By setting the appropriate
values of m l we can derive the update rules for the must-link and cannot-
link constraint violations. Solving for μ j ,wegettheupdateruleshownin
Equation 7.8.
μ j =
x i ∈π j x i + ( x i ,x a ) ∈C = ,g ( x i ) = g ( x a ) μ g ( x a ) + ( x i ,x a ) ∈C = ,g ( x i )= g ( x a ) μ h ( g ( x a ))
|
+ x i ∈μ j , ( x i ,x a ) ∈C = ,g ( x i ) = g ( x a ) 1+ s i ∈π j , ( x i ,x a ) ∈C = ,g ( x i ) = g ( x a ) 1
(7.8)
μ j |
Search WWH ::




Custom Search