典型聚类算法

基于划分的方法

代表：kmeans算法

基于层次的方法

代表：CURE算法

基于网格的方法

代表：STING算法

将数据集合X划分多层网格结构，从某一层开始计算查询该层网格间的属性值，计算属性值与阈值的关系，判定网格间的相关情况，不相关的网格不作考虑如果网格相关，则进入下一层的相关区域继续第二步，直到下一层为最底层返回相关网格结果

基于密度的方法

代表：DBSCAN算法

输入数据集合X，随机选取一点，并找出这个点的所有高密度可达点遍历此点的所有 ε 邻域内的点，并寻找这些密度可达点，判定某点 ε− 邻域内的点，并寻找这些点密度可达点，判定某点的 ε− 邻域内的点数是否超过阈值点数，超过则构成核心点扫描数据集，寻找没有被聚类的数据点，重复第二步输出划分的类，并输出异常值点（不和其他密度相连）

神经网络的方法

代表：SOM算法

基于图的聚类方法

代表：谱聚类算法

聚类算法的评价指标

一个好的聚类方法可以产生高品质簇，是的簇内相似度高，簇间相似度低。一般来说，评估聚类质量有两个标准，内部质量评价指标和外部评价指标。

内部质量评价标准

内部评价指标是利用数据集的属性特征来评价聚类算法的优劣。通过计算总体的相似度，簇间平均相似度或簇内平均相似度来评价聚类质量。评价聚类效果的高低通常使用聚类的有效性指标，所以目前的检验聚类的有效性指标主要是通过簇间距离和簇内距离来衡量。这类指标常用的有CH（Calinski-Harabasz）指标等

CH指标

CH指标定义为：

簇的凝聚度

簇内点对的平均距离反映了簇的凝聚度，一般使用组内误差平方（SSE）表示：

簇的邻近度

簇的邻近度用组间平方和（SSB）表示，即簇的质心 C_i 到簇内所有数据点的总平均值 c 的距离的平方和

外部质量评价标准

外部质量评价指标是基于已知分类标签数据集进行评价的，这样可以将原有标签数据与聚类输出结果进行对比。外部质量评价指标的理想聚类结果是：具有不同类标签的数据聚合到不同的簇中，具有相同类标签的数据聚合相同的簇中。外部质量评价准则通常使用熵，纯度等指标进行度量。

熵：

簇内包含单个类对象的一种度量。对于每一个簇，首先计算数据的类分布，即对于簇 i ，计算簇 i 的成员属于类 j 的概率

其中m_i表示簇 i 中所有对象的个数，而 m_ij 是簇 i中类 j 的对象个数。使用类分布，用标准公式：

计算每个簇 i 的熵，其中K是类个数。簇集合的总熵用每个簇的熵的加权和计算即：

其中K是簇的个数，而 m 是簇内数据点的总和

纯度：

簇内包含单个类对象的另外一种度量。簇 i 的纯度为

，而聚类总纯度为：