Solution 3 Computational Intelligence Lab 2012

Aus VISki
Wechseln zu: Navigation, Suche

Adapted from CIL 2012 Master solution.

1. Convergence of the K-Means algorithm

(Convergence of the K-Means Algorithm) The K-means algorithm converges since at each iteration it either reduces or keeps the same the value of the objective function J, where

with the constraint

Step 2

When initialising the algorithm we set

where

This makes the value of minimal considering that we have to assign the value to one and only one and to all others.

Step 3

We note that the centroids are updated with this equation:

The derivative of the constraint with respect to yields:

which can be reformulated to:

which then yields the equation for the centroid update step.

Computing the second derivative of results in .

Considering the argument in step 1 and 2 convergence guaranteed for the cost function:

2. Recasting K-Means into a Matrix Factorisation Problem

Part 2

We note that step 2 of K-means minimises

with the constraint and the values being either or . Which yields:

thus is minimised with .

Part 3

Computing the derivative of

yields:

since is either 0 or 1 we can conclude that the 3rd step solves

It follows that K-means minimises the objective matrix factorisation problem given by: