编辑：bin~bin 审核校对：咪博士
一、基于划分的聚类算法
1、K-means 算法
K-means算法是划分方法中较为经典的聚类算法之一。由于该算法的效率高，所以广泛应用于大规划数据的聚类分析。该算法的目的是使各个样本与所在类均值的误差平方和达到最小（这也是评价K-means算法最后聚类效果的评价标准）
k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。
k-means算法的处理过程：
1）随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心；
2）对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；
3）然后重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛。
通常，采用平方误差准则，其定义如下：
这里E是数据库中所有对象的平方误差的总和，p是空间中的点，mi是簇Ci的平均值。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离,当然也可以用其他距离度量。
k-means聚类算法的算法流程：
输入：包含n个对象的数据库和簇的数目k,并在n中随机选取k个对象作为初始聚类中心；
输出：k个簇，使平方误差准则最小。
步骤：
1）任意选择k个对象作为初始的簇中心，设定迭代中止条件（例如最大循环次数或聚类中心收敛误差容限)；
2) 进行迭代；
3) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇；
4) 更新簇的平均值，即计算每个簇中对象的平均值；
5)重复步骤 2-4，直到不再发生变化。
举一个简单的例子来说明问题：
设有一组数据集n1=(2,1),n2=(1,3),n3=(6,7),n4=(4,7)
1)选取聚类中心，该中心可以任意选取，也可以通过直方图进行选取，还可以通过取前2个值进行选取,我们选择两个聚类中心；
2)计算每一个样本值到聚类中心的距离并划分新的聚类中心；
3)假设有k个数据源，i个聚类中心。mi为聚类中心。该公式的意思也就是将每个类中的数据与每个聚类中心做差的平方和，E最小，意味着分割的效果最好。
2、PAM算法
PAM（Partitioning Around Medoid ,围绕中心点的划分）算法是划分算法中一种很重要的算法，最早由Kaufman和Rousseevw提出，有时也称为k-中心点算法，是指用中心点来代表一个簇。
PAM算法的目的：
1）对成员集合D中的N个数据对象给出k个划分，形成k个簇；
2）在每个簇中随机选取1个成员设置为中心点；
3）然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点；
4）用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。
3、CLARANS算法
CLARANS（ A Clustering Algorithm based on Randomized Search ，基于随机选择的聚类算法）。
CLARANS将采样技术和PAM结合起来，CLARA在搜索的每个阶段有一个固定样本，CLARANS任何时候都不局限于固定样本，而是在搜索的每一步带一定随机性地抽取一个样本。
CLARANS算法的流程：
设定参数：num_local 表示抽样次数；
max_neighbor 表示任意一个节点与任意特定邻居节点比较的数目；i 表示已选样的次数；min_cost 为最小代价；current 为当前节点；j 为已经与当前节点进行比较的邻居个数。
CLARANS算法的步骤如图：