|
UWEETR-2006-0001 Author(s): Keywords: Abstract We show that Queyranne's algorithm for finding a non-trivial minimizer of a symmetric submodular function can be used as a clustering algorithm. For submodular clustering criterion, such as graph-cut or minimum description length based criteria, we can find the optimal clustering for 2 clusters, and near optimal clusterings for more than 2 clusters. Due to results by Rizzi and Nagamochi and Ibaraki, the algorithm can also be used for more general functions, allowing it to be used for various other criteria such as the single-linkage criterion. |