典型的划分聚类算法分为两类：基于类中心的K-means、基于代表点的K-medoids。

数据集包含个数据点，式中为一个维的向量，K-medoids算法将该数据集划分成类，，使下列目标函数(Sum-of-Absolute-Errors)最小：

式中是类的代表点，表示与的相异度。

K-medoids算法包括如下几步：定义对象的相异矩阵，选取初始代表点，反复交换代表点与非代表点直至SAE不能减少。K-medoids由于不求类的均值，其相异矩阵的定义则可不使用欧氏距离。初始代表点通常随机选取，也可特别选择。确定一个非代表点是否可代替代表点，对于对象的重新划分可考虑4种情况：

①如果，且，那么分配给。

②如果，且，那么分配给。

③如果，，且，那么仍分配给。

④如果，，且，那么分配给。

K-medoids的典型实现是PAM（Partitioning Around Medoids），其算法描述如下：①在数据集中随机选择个数据点，作为个类的初始代表点。②反复执行交换操作，直到代表点保持不变：对每一个代表点与每一个非代表点，用替换，重新分配所有对象，并计算SAE，若其减少则确认交换，否则撤销交换。

PAM的改进算法CLARA将采样技术与PAM结合，以处理大数据集。它的缺点是某个采样得到的代表点可能不是最佳的代表点，此时将导致聚类效果变差。CLARANS则是CLARA的变种，它在搜索过程中随机采样，以一定程度上弥补CLARA的缺陷。

相对K-means算法，K-medoids对噪音点比较鲁棒，且易于处理非连续数据，但其时间复杂度较高。