基于图的聚类算法研究+文献综述(3)
1.2.2 簇间距离的度量方法
在以上五种方法中，论文中经常作为研究对象的是基于划分的方法和基于层次的聚类方法。对于这两种聚类方法而言，出了算法框架外，另一个重要的地方是距离的度量标准。距离的计算方法大致可以分为以下三种：欧式距离、街区距离、基于密度的距离
1.2.2.1 欧式距离
欧式距离是聚类算法中最常用的度量标准，可以用如下公式表示，其中x、y是向量： 。欧式距离实际上就是计算两点之间的直线距离。这种度量方法简单直观，从聚类之后的结果来看，每个簇都容易被划分或者被聚集成类似圆形或球形。当我们希望的聚类形状以圆形或球形为主时，可以使用欧式距离作为度量标准。
1.2.2.2 街区距离
街区距离与欧式距离不同，它是非直线的距离，可以形象的理解为城市之中两点之间通过街道的路程。街区距离实际上就是两个向量之间每一文的差值之和。我们假设在同一空间内，有两个向量x、y，它们是 和 。x和y之间的街区距离可表示为
公式1.1）
这种距离的度量方法的应用不多见，仅满足某些特定的需要。
1.2.2.3 基于密度的距离
基于密度的距离的度量方法，是依靠簇中密度的变化情况来决定某一个数据点是否加入到这个簇中。这类方法比较多，像OPTICS方法中使用了核心距离和可到达距离这两个概念。OPTICS测算的是以簇的平均值点为圆心，核心距离和可到达距离为半径的两个密度。还有的基于网格的方法中，使用了若干个矩形范围内的点的个数作为密度。使用密度度量距离，可以由一定的抗噪声能力，提高聚类的精度。
1.2.3基于图聚类算法
基于图的聚类算法选取数据基于图的观点，其中，数据对象用结点表示，而两个数据对象之间的邻近度用对应结点之间的边的权值表示。主要步骤为：
1.2.3.1 稀疏化邻近度图
只保留对象与其最近邻之间的连接。这种稀疏化对于处理噪声和离群点是有用的。稀疏化也使得我们可以利用为稀疏化图开发的有效图划分的算法。
1.2.3.2基于共享的最近邻个数
定义两个对象之间的相似度度量，该方法基于这样一种观察，对象和它的最近邻通常属于同一个类。该方法有助于克服高文和变密度簇的问题。
1.2.3.3 定义核心对象，并构建环绕他们的簇
为了对基于图的聚类做这件事，需要引入邻近度图或稀疏化的邻近度图的基于密度的概念。
1.2.3.4使用邻近度图中的信息
提供两个簇是否应当合并的更复杂的评估。具体地，两个簇合并，仅当结果簇具有类似于原来的两个簇的特性。
2算法介绍
2.1Chameleon算法
Chameleon力求合并这样的一对簇，合并后产生的簇，用互连性和紧密性来度量时，其与原来的一对簇最相似。为了理解互连性和紧密性概念，需要用邻近图的观点，并且需要考虑簇内和簇间点之间的边数和这些边的强度。
2.1.1相对互连度（Relative Interconnectivity, RI）
簇 和 之间的绝对互连度是连接簇 和 中顶点的所有边的权重之和，其本质是同时包含簇 和 的边割（edge cut ,EC），用EC（ ， ）表示。簇 的内部互连度可以通过它的最小二分边割EC（ ）的大小（既将图划分成两个大致相等的部分的边的加权和）表示。簇 和 间的相对互连度RI（ ， ）定义为用簇 和 的内部互连度规格化 和 间的绝对互连度，计算公式如下：
这里，| |为绝对互连度，其值为“跨越两个簇的所有边的权重和”， | |表示内部互连度，其值为“簇 内所有边的权重和”。
图2-1解释了相对互连度的概念。两个圆形簇（c）和（d）比两个矩形簇（a）和（b）具有更多的连接，然而，合并（c）和（d）产生的簇具有非常不同于（c）和（d）的连接性。相比之下合并（a）和（b）产生的簇连接性与簇（a）和（b）非常类似。
上一篇：网络图像搜索中的图像摘要技术研究