图2-1 第一对簇更“紧密”
2.1.2 相对紧密度（Relative Closeness,RC）
簇 和 间的相对紧密度被定义为用簇 和 的内部紧密度规格化簇 和 间的绝对紧密度。度量两个簇的紧密度的方法是取簇 和 间连接边的平均权重。具体计算公式如下：
 
式中， 为簇 和 间的绝对紧密度，通过簇 和 的连接边的平均权重来度量，即 ， 是内部紧密度，通过簇 内连接边的平均权重来度量，即 。
RI和RC可以用多种不同的方法组合，以产生自相似性（self-similarity）的总度量。 Chameleon使用的是合并最大化 的簇对，其中 是用户指定的参数，通常大于1。
2.1.3 Chameleon算法关键步骤
Chameleon算法由三个关键步骤组成：稀疏化，图划分和子图合并，如图2-2所示。
图2-2  Chameleon算法聚类步骤
Chameleon算法具体描述如下：
＜1＞ 构建稀疏图：由数据集构造成K-最近邻图集合 。
＜2＞多层图划分：通过一个多层图划分算法将图 划分成大量的子图，每个子图代表一个初始子簇。
＜3＞合并子图：合并关于相对连接度和相对紧密度而言，最好的保持了簇的自相似性的簇。
＜4＞重复步骤＜3＞，直至不再有可以合并的簇或者用户指定停止合并时簇的个数。
三个关键步骤进一步说明如下
1.构建稀疏图：图的表示基于K-最近邻方法，节点表示数据项，边表示数据项间的相似度，节点v,u之间的边表示节点v在节点u的k个最相似点中，或节点u在节点v的k个最相似点中，或节点u在节点v的k个最相似点中。使用图的表示有以下优点：
①距离很远的数据项，完全不相连。
②边的权重代表了潜在的空间密度信息。
③在密集和稀疏区域的数据项都是同样能建模。
④表示的稀疏便于使用高效的算法。
2.多层图划分：基于得到的稀疏图，使用如HMETIS等有效的多层图划分算法来划分数据集，划分步骤如下：
＜1＞从得到的稀疏图开始。
＜2＞二分当前最大的子图。
＜3＞直到没有一个簇多于MIN—SIZE个点（MIN—SIZE是用户指定的参数）。
3.合并子簇：采用凝聚层次聚类方法合并子簇。合并子簇有以下两种方法。
方法一：设阀值，预先设定两个阀值，只TRI和TRC只有满足条件
RI{ ， }≥TRI且RC{ ， }≥TRC 时，子簇才会被合并。
方法二：簇间的相似度采用函数 ，即取相对互连性和相对近似性之积最大者合并。
Chameleon算法能够有效的聚类空间数据，能识别具有不同形状，大小和密度的簇，对噪声和异常数据不敏感。Chameleon算法的时间复杂度为 ，因此使用Chameleon算法对中小规模数据集的聚类分析是个很好的选择，但对于在大规模数据集其应用受到了限制。
2.2 K-means算法
2.2.1 算法简介
为了便于与Chameleon算法对比，我们简单介绍下K-means算法：K-means算法是1967年由MacQueen首次提出来的一种经典算法，迄今为止，很多聚类任务都选择该算法。K-means聚类算法的处理流程如下：首先，随即选择K个对象，每个对象代表一个簇的初始均值或中心；对于剩余的每个对象，根据其与各簇中心的距离，将他指派到最近（或最相似）的簇，然后计算每个簇的新均值，得到更新后的簇中心；不断重复，直到准则函数收敛。通常，采用平方误差准则，即对于每个簇中的每个元素，求对象到其中心距离的平方和，这个准则试图使生成的K个结果簇尽可能的紧凑和独立。
K-means聚类算法分形式化描述如下：
---------------------------------------------------------------------
算法：K-means 基于图的聚类算法研究+文献综述(4):http://www.youerw.com/jisuanji/lunwen_6341.html