Chameleon算法及Matlab实现

Chameleon（变色龙）算法

——使用动态建模的多阶段层次聚类

一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度。

算法思想：

首先由数据集构造一个 k-最近邻图 Gk；
再通过一种图的划分算法，将Gk图划分成大量较小的子图，每个子图代表一个初始的子簇；
最后使用凝聚层次聚类算法，基于子簇的相似度反复合并子簇。

**为引出**Chameleon变色龙算法的一些定义，先说一下以往的聚类算法的不足之处：

忽略簇与簇之间的互联性

互联性：簇间距离较近的数据对之间的数量，即临接区域的大小。
忽略簇与簇之间的近似性

近似性：簇间数据对的相似度，即不同簇的对象间最近距离。

如图4所示：如果只看最近邻的链接，即只看近似性，则算法会倾向于合并c和d而不是a和b，但实际上a、b的临接区域较大，距离也不远（相对于a、b内部），即互连性更好，所以应该属于同一个cluster簇。
Chameleon算法及Matlab实现
如图5所示：另一种情况，就是过分强调临接区域的大小，倾向于合并a、c，而不是a、b。

Chameleon算法就是努力保持这两种情况之间平衡，即考虑最近邻节点的靠近程度，也考虑临接区域的大小。

Chameleon算法的聚类步骤：

第一阶段：图划分算法，将数据对象划分成大量子簇；
第二阶段：凝聚层次聚类算法，合并子簇。

3个关键知识点：

1. k-最近邻图Gk的构造（第一阶段）

Gk图中的每个点，表示数据集中的一个数据点。对于数据集中的每一个数据点找出它的所有k-最近邻对象，然后分别在它们之间加带权边。
如何找k-最近邻对象呢？？即找离该对象最近的k个对象点，
（定义：若点ai到另一个点bi的距离值是所有数据点到bi的距离值中k个最小值之一，则称ai是bi的k-最近邻对象。）
若一个数据点是另一个数据点的k-最近邻对象之一，则在这两点之间加一条带权边，边的权值表示这两个数据点之间的相似度，即距离越大边权值越小，则近似度越小。

2. 划分k-最近邻图Gk（得到初始子簇）

目的：把Gk图划分为大量的无连接的子图，每一个子图就是第二阶段层次聚类的初始子簇。
划分步骤：首先把图Gk划分成两个近似的等大小的子图，使分区的边的总权重和最小，即（割边最小化）；我个人觉得它就是最小二分法。也就是说，簇C划分为两个子簇Ci和Cj时需要割断的边的加权和最小。割边用Ec（Ci，Cj）表示，用于评估簇Ci和Cj之间的绝对互连性。然后把每个子图看成一个初始的子图，重复上述过程直至生成每一个子图中节点数量达到一定标准。

3. 合并成最终的簇（第二阶段）

Chameleon算法根据每对簇Ci和Cj的 相对互连度 RI（Ci,Cj）和 相对接近度
RC（Ci,Cj）来决定两个簇之间的相似度。

两个簇Ci和Cj之间的 相对互连度 RI（Ci,Cj）定义为Ci和Cj之间的绝对互连度关于两个簇Ci和Cj之间的内部互连度的规范化：

绝对互连性：连接子簇Ci和Cj之间的边的权重之和。
相对互连性：一个子簇Ci做最小截断时需要去掉的边的权重和。
两个簇Ci和Cj的的 相对接近度 RC（Ci，Cj）定义为Ci和Cj之间的绝对接近度关于两个簇Ci和Cj的内部接近度的规范化，定义如下：

相对近似度：一个子簇Ci做最小截断时需要去掉的边的平均权重。
绝对近似度：连接子簇Ci和Cj之间的边的平均权重。