Implementation of certificate for k-means optimality based on algorithm from paper: Probably certifiably correct k-means clustering. https://arxiv.org/pdf/1509.07983v2.pdf
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.DS_Store
certify_clusters.m
figure3_center.m
figure3_left.m
figure3_right.m
kmeans_certificate_balls.m
power_iteration_certification.m
readme
spectral_kmeans_clustering.m

readme

Probably certifiably correct kmeans clustering
*****
Authors: Takayuki Iguchi, Dustin G. Mixon, Jesse Peterson, and Soledad Villar.
contact: mvillar@math.utexas.edu
*****
This code contains the algorithms described in [1]. In particular the function
certify_clusters receives a set of clusters as input and constructs the dual 
certification described in [1]. If the certification succeeds it means that it
constructed a proof of the clustering’s optimality, and the algorithm returns 1.

See certify_clusters.m description for more information.

*****
Example
>> Phi= horzcat(rand(2,10), rand(2,11)+2*ones(2,11), rand(2,8)-2*ones(2,8));
>> certify_clusters(Phi, [10,11,8])
ans=1 

>> Phi2= horzcat(randn(2,10), randn(2,11)+2*ones(2,11), randn(2,8)-2*ones(2,8));
>> certify_clusters(Phi, [10,11,8])
ans=0
*****

 References:
[1] Iguchi, Mixon, Peterson, Villar. Probably certifiably correct kmeans 
clustering.