一、基本凝聚层次聚类
凝聚是指，算法初始时，将每个点作为一个簇，每一步合并两个最接近的簇。步骤如下：
a)计算邻近度矩阵
b)Repeat
c)合并最接近的两个簇
d)更新邻近性矩阵，以反映新的簇与原来的簇之间的邻近性
e)Until仅剩下一个簇
1.定义簇之间的邻近性
算法的关键操作是计算两个簇之间的邻近度，并且因不同的邻近性，需要定义讨论不同的凝聚层次技术。常用的邻近性定义如下：
Ø单链(MIN):定义簇的邻近度为不同两个簇的两个最近的点之间的距离。
Ø全链(MAX):定义簇的邻近度为不同两个簇的两个最远的点之间的距离。
Ø组平均：定义簇的邻近度为取自两个不同簇的所有点对邻近度的平均值。
凝聚的层次聚类并没有类似基本K均值的全局目标函数，没有局部极小问题或是很难选择初始点的问题。合并的操作往往是最终的，一旦合并两个簇之后就不会撤销。当然其计算存储的代价是昂贵的。
2.层次聚类的主要问题
①缺乏全局目标函数
凝聚层次聚类不能视为全局优化目标函数。
②处理不同大小簇的能力
如何处理待合并的簇对的相对大小。
有两种方法：
Ø加权方法平等地对待所有的簇。
Ø非加权方法考虑每个簇的点数。
③合并决策时最终的
凝聚层次聚类算法趋向于做出好的局部决策。因为它们所有点的逐对相似度信息。这种方法阻碍了局部最优变成全局最优。
二、DBSCAN
一种简单的，基于密度的聚类算法。这里介绍基于中心的方法。
1.传统的基于中心的方法
在基于中心的方法中，每个数据点的密度通过对以该点为中心以边长为2*EPs的网格（邻域）内的其他数据点的个数来度量。根据数据点的密度分为三类：
核心点：稠密区域内部的点；
边界点：稠密区域的边缘点；
噪音点：稀疏区域中的点。
2.算法过程
Ø将所有点标记为核心点、边界点、噪声点。
Ø删除噪声点。
Ø为距离在Eps之内的所有核心点之间赋予一条边。
Ø每组连通的核心点形成一个簇。
Ø将每个边界点指派到一个与之关联的核心点的簇中。
3.优缺点
优点：
基于密度，是相对噪声的，能够处理任意形状和大小的簇。
可以发现K均值不能发现的许多簇。
缺点：
当簇的密度变化太大时，处理容易产生问题。
对高维数据，密度定义比较困难。
xp]�6�!Y
网友评论