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


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


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: