为了减轻k均值算法对孤立点的敏感性，k中心点算法不采用簇中对象的平均值作为簇中心，而选用簇中离平均值最近的对象作为簇中心。

k中心算法的基本过程是:首先为每个簇随意选择一个代表对象，剩余的对象根据其与每个代表对象的距离分配给最近的代表对象所代表的簇；然后反复用非代表对象来代替代表对象，以优化聚类质量。聚类质量用一个代价函数来表示。当一个中心点被某个非中心点替代时，除了未被替换的中心点外，其余各点被重新分配。

算法如下:

输入:包含n个对象的数据库和簇数目k；

输出:k个簇

（1）随机选择k个代表对象作为初始的中心点

（2）指派每个剩余对象给离它最近的中心点所代表的簇

（3）随机地选择一个非中心点对象y

（4）计算用y代替中心点x的总代价s

（5）如果s为负，则用可用y代替x，形成新的中心点

(6) 重复(2)(3)(4)(5)，直到k个中心点不再发生变化.