类k-均值算法无法解决非簇状分布的数据聚类问题_一种新的原型聚类方法：K-multiple-means...

k-means很适合对簇状分布的数据聚类，同时可以得到每类数据的prototype，也就是均值点，用来做向量量化之类的任务。但k-means解决不了非簇状分布的数据聚类问题，所以也就没法给出非簇状数据的prototype。

谱聚类虽然可以很好的解决非簇状分布的数据聚类问题，但也没有办法给出每一类数据对应的prototype。

Multiple Prototype试图通过对每一类数据用多个prototype进行表示，解决非簇状分布数据的原型聚类问题。这个小问题的研究工作比较少。以前的工作往往采用自上而下的凝聚式策略进行聚类，运算时间很高。

K-Multiple-Means (KMM) 定义了一个显示的目标函数，在给定总的聚类数k和总的prototypes数m时，通过优化问题求解，自适应的把m个prototype以及n个原始数据点划分到k类中。K-Multiple-Means并不是不考虑n个原始数据点，仅仅对m个prototype进行聚类，而是迭代地划分prototype和原始数据形成的二部图，最终得到的二部图刚好划分为k类，聚类结果可以直接根据图的连通性得到。同时还会给出每个原始数据点和最近的j个prototype的连接概率（就是边的权重）。KMM 的计算复杂度是O(nm^2)，相对于n是线性，但对m是二次的。我们在理论上分析了 KMM 和k-means的联系。