算法介绍

本篇文章讲述的还是聚类算法，也是属于层次聚类算法领域的，不过与上篇文章讲述的分裂实现聚类的方式不同，这次所讲的Chameleon算法是合并形成最终的聚类，恰巧相反。Chamelon的英文单词的意思是变色龙，所以这个算法又称之为变色龙算法，变色龙算法的过程如标题所描绘的那样，是分为2个主要阶段的，不过他可不是像BIRCH算法那样，是树的形式。继续看下面的原理介绍。

算法原理

先来张图来大致了解整个算法的过程。

上面图的显示过程虽然说有3个阶段，但是这其中概况起来就是两个阶段，第一个是形成小簇集的过程就是从Data Set 到k最近邻图到分裂成小聚餐，第二个阶段是合并这些小聚簇形成最终的结果聚簇。理解了算法的大致过程，下面看看里面定义的一些概念，还不少的样子。

为了引出变色龙算法的一些定义，这里先说一下以往的一些聚类算法的不足之处。

1、忽略簇与簇之间的互连性。就会导致最终的结果形成如下：

2、忽略簇与簇之间的近似性。就会导致最终的聚类结果变成这样“：

?

为什么提这些呢，因为Chameleon算法正好弥补了这2点要求，兼具互连性和近似性。在Chameleon算法中定义了相对互连性，RI表示和相对近似性，RC表示，最后通过一个度量函数:

function value = RI( Ci, Cj)× RC( Ci, Cj)α，α在这里表示的多少次方的意思，不是乘法。

来作为2个簇是否能够合并的标准，其实这些都是第二阶段做的事情了。

在第一阶段，所做的一件关键的事情就是形成小簇集，由零星的几个数据点连成小簇，官方的作法是用hMetic算法根据最小化截断的边的权重和来分割k-最近邻图，然后我网上找了一些资料，没有确切的hMetic算法，借鉴了网上其他人的一些办法，于是用了一个很简单的思路，就是给定一个点，把他离他最近的k个点连接起来，就算是最小簇了。事实证明，效果也不会太差，最近的点的换一个意思就是与其最大权重的边，采用距离的倒数最为权重的大小。因为后面的计算，用到的会是权重而不是距离。

我们再回过头来细说第二阶段所做的事情，首先是2个略复杂的公式（直接采用截图的方式）：

相对互连性RI=

相对近似性RC=

Ci,Cj表示的是i,j聚簇内的数据点的个数，EC(Ci)表示的Ci聚簇内的边的权重和，EC(Ci,Cj)表示的是连接2个聚簇的边的权重和。

后来我在查阅书籍和一些文库的时候发现，这个公式还不是那么的标准，因为他对分母，分子进行了部分的改变，但是大意上还是一致的，标准公式上用到的是平均权重，而这里用的是和的形式，差别不大，所以就用这个公式了。

那么合并的过程如下：

1、给定度量函数如下minMetric,

2、访问每个簇，计算他与邻近的每个簇的RC和RI，通过度量函数公式计算出值tempMetric。

3、找到最大的tempMetric,如果最大的tempMetric超过阈值minMetric，将簇与此值对应的簇合并

4、如果找到的最大的tempMetric没有超过阈值，则表明此聚簇已合并完成，移除聚簇列表，加入到结果聚簇中。

4、递归步骤2，直到待合并聚簇列表最终大小为空。

算法的实现

算法的输入依旧采用的是坐标点的形式graphData.txt：

?

0 2 2
1 3 1
2 3 4
3 3 14
4 5 3
5 8 3
6 8 6
7 9 8
8 10 4
9 10 7
10 10 10
11 10 14
12 11 13
13 12 8
14 12 15
15 14 7
16 14 9
17 14 15
18 15 8

?

?

package DataMining_Chameleon;



/**
 * 坐标点类
 * @author lyq
 *
 */
public class Point{
	//坐标点id号,id号唯一
	int id;
	//坐标横坐标
	Integer x;
	//坐标纵坐标
	Integer y;
	//是否已经被访问过
	boolean isVisited;
	
	public Point(String id, String x, String y){
		this.id = Integer.parseInt(id);
		this.x = Integer.parseInt(x);
		this.y = Integer.parseInt(y);
	}
	
	/**
	 * 计算当前点与制定点之间的欧式距离
	 * 
	 * @param p
	 *            待计算聚类的p点
	 * @return
	 */
	public double ouDistance(Point p) {
		double distance = 0;

		distance = (this.x - p.x) * (this.x - p.x) + (this.y - p.y)
				* (this.y - p.y);
		distance = Math.sqrt(distance);

		return distance;
	}
	
	/**
	 * 判断2个坐标点是否为用个坐标点
	 * 
	 * @param p
	 *            待比较坐标点
	 * @return
	 */
	public boolean isTheSame(Point p) {
		boolean isSamed = false;

		if (this.x == p.x && this.y == p.y) {
			isSamed = true;
		}

		return isSamed;
	}
}

?

?