Wednesday, September 07, 2011

The Hungarian algorithm in clustering evaluation

The Hungarian algorithm (aka Kuhn–Munkres algorithm or Munkres assignment algorithm) can solve the assignment problem in polynomial time O(n^3). It can be used to find the optimal mapping from discovered clusters to the ground-truth categories which serves as the basis for some performance measures of clustering.