【商务智能】数据挖掘–聚类算法:Single Link、Complete Link、Average Link

一.前言

聚类算法的应用十分广泛,比如图像处理、搜索引擎、统计学等。

前面写了贝叶斯ID3C4.5CART四个分类算法,现在来谈谈聚类算法。对于分类和聚类的概念,请见之前的一篇文章:【商务智能】浅析数据挖掘的分类和聚类算法

聚类分为有很多种,包括层次聚类、分割聚类等。

下面将讲解和实现层次聚类中的Single Link(单链接算法)、Complete Link(全链接算法)、Average Link(平均链接算法)。

二.算法讲解

转载请注明出处:http://jasonhan.me/blog/?p=214

层次聚类的方式分为:Agglomerative(凝聚的层次聚类)、Divisive(分割的层次聚类)。

  • 凝聚层次聚类:是一个自底向上的过程,一开始将各个元素划分为一个Cluster(簇),根据提供的threshold(阈值),当X簇和Y簇距离<=threshold时,将他们合并为一个Cluster,把所有满足该条件的簇合并完之后,threshold递增,再一次进行合并,直到最终合并为一个Cluster(簇)。
  • 分割的层次聚类:是一个自顶向下的过程,和凝聚层次聚类正好相反,一开始将所有元素归为一个Cluster,然后根据threshold将Cluster进行分割,直到最终每个元素成为一个Cluster。

本文是基于凝聚层次聚类实现的。

对于聚类的过程,重点在于,如何确定两个Cluster之间的距离。在Single Link中,取两个Cluster中最短的元素距离作为这两个Cluster的距离;在Complete Link中,取两个Cluster中最远的元素距离作为这两个Cluster的距离;在Average Link中,去两个Cluster中两两元素的距离的平均值作为这两个Cluster的距离。

而对于threshold的取值,我们找表中的最小的距离赋给threshold。

假设我们现在有如下的数据:

A B C D E
A 0 1 2 2 3
B 1 0 2 4 3
C 2 2 0 1 5
D 2 4 1 0 3
E 3 3 5 3 0

下面是对于上面的数据集进行的3种凝聚层次聚类的结果:

clusterResult

凝聚层次聚类的算法就是这样简单,不像分类算法那样有复杂的计算。

下面是实现代码:

转载请注明出处:http://jasonhan.me/blog/?p=214

首先实现一个Cluster(簇)类:

import java.util.ArrayList;

/**
 * Cluster类,表示一个簇
 * @author Jason Han
 *
 */
public class Cluster
{
	public ArrayList<String> elements;//Cluster中的元素

	public Cluster(ArrayList<String> elements)
	{
		this.elements=elements;
	}

	/**
	 * 和另一个Cluster合并
	 * @param anotherCluster 另一个
	 */
	public void Union(Cluster anotherCluster)
	{
		this.elements.addAll(anotherCluster.elements);
	}

	/**
	 * 重写toString(),便于打印
	 */
	public String toString()
	{
		StringBuilder result=new StringBuilder();
		result.append("{");
		for(int i=0;i<this.elements.size();i++)
		{
			result.append(this.elements.get(i));
			if(i!=this.elements.size()-1)
				result.append(",");
		}
		result.append("}");
		return result.toString();
	}
}

下面实现一个Tuple(元组)类,我们定义一个元组为<threshold,Cluster个数,Cluster集>,例如,上面的案例中最底下的层为<0,  5, {A} {B} {C} {D} {E}>

import java.util.*;

/**
 * 元组类
 * @author Jason Han
 *
 */
public class Tuple
{
	public double threshold;
	public ArrayList<Cluster> clusterSet;

	public Tuple(double threshold)
	{
		this.threshold=threshold;
		this.clusterSet=new ArrayList<Cluster>();
	}

	/**
	 * 设置cluster集,这里是深拷贝而不是浅拷贝
	 * @param clusterSet cluster集
	 */
	public void SetClusterSet(ArrayList<Cluster> clusterSet)
	{
		for(Cluster c : clusterSet)
		{
			ArrayList<String> elements=new ArrayList<String>();
			elements.addAll(c.elements);
			Cluster newCluster=new Cluster(elements);
			this.clusterSet.add(newCluster);
		}
	}

	/**
	 * 将两个cluster进行合并
	 * @param cluster1
	 * @param cluster2
	 */
	public void Union(Cluster cluster1,Cluster cluster2)
	{
		String s1=cluster1.elements.get(0);//cluster1中的某个元素
		String s2=cluster2.elements.get(0);//cluster2中的某个元素

		//寻找s1和s2所在的cluster
		//这里这样做的原因是为了处理“A和B合并后又发现B和C需要合并”的情况
		int s1_index=0,s2_index=0;
		for(Cluster cluster : clusterSet)
		{
			if(cluster.elements.contains(s1))
				s1_index=this.clusterSet.indexOf(cluster);
			if(cluster.elements.contains(s2))
				s2_index=this.clusterSet.indexOf(cluster);
		}

		if(s1_index==s2_index)
			return;

		this.clusterSet.get(s1_index).Union(this.clusterSet.get(s2_index));//合并
		this.clusterSet.remove(s2_index);//移除被合并的Cluster
	}

	/**
	 * 重新toString,便于打印
	 * @return 结果
	 */
	public String toString()
	{
		StringBuilder result=new StringBuilder();
		result.append("< ");
		result.append(this.threshold+", ");
		result.append(this.clusterSet.size()+", ");
		for(Cluster c : this.clusterSet)
		{
			result.append(c.toString());
		}
		result.append(">");
		return result.toString();
	}
}

下面是最重要的HierarchicalCluster (层次聚类)类:

import java.util.ArrayList;

/**
 * 层次聚类Class
 * @author Jason Han
 *
 */
public class HierarchicalCluster
{
	//3种算法的枚举
	public static enum Type{SINGLE_LINK,COMPLETE_LINK,AVERAGE_LINK}

	private ArrayList<String>  elementNames;//元素名
	private double[][] origionDistanceMatrix;//距离矩阵
	ArrayList<Tuple> tupleList;//保存每个阈值对应的结果集

	/**
	 * 算法初始化
	 * @param distanceMatrix 距离矩阵
	 * @param elementNames 元素集
	 */
	public HierarchicalCluster(double[][] distanceMatrix,ArrayList<String> elementNames)
	{
		if(distanceMatrix.length<=0||distanceMatrix.length!=distanceMatrix[0].length||elementNames.size()!=distanceMatrix.length)
		{
			System.out.println("数据有误");
			return;
		}

		this.origionDistanceMatrix=distanceMatrix;
		this.elementNames=elementNames;

		this.tupleList=new ArrayList<Tuple>();

		//初始化距离阈值为0的情况
		ArrayList<Cluster> clusterSet=new ArrayList<Cluster>();//初始簇
		for(int i=0;i<elementNames.size();i++)
		{
			ArrayList<String> al=new ArrayList<String>();
			al.add(elementNames.get(i));
			clusterSet.add(new Cluster(al));
		}
		Tuple firstTuple=new Tuple(0);
		firstTuple.clusterSet=clusterSet;
		this.tupleList.add(firstTuple);
	}

	/**
	 * 进行聚类
	 * @param type 聚类的方式
	 */
	public void DoClustering(Type type)
	{
		//初始的cluster数量和距离矩阵
		int clusterCount=this.elementNames.size();
		double[][] distanceMatrix=this.origionDistanceMatrix;

		while(clusterCount>1)
		{
			//获取threshold
			double threshold=this.FindThreshold(distanceMatrix,clusterCount);

			Tuple tuple=new Tuple(threshold);//新的tuple
			ArrayList<Cluster> oldClusterSet=this.tupleList.get(this.tupleList.size()-1).clusterSet;//旧的Cluster集
			tuple.SetClusterSet(oldClusterSet);

			//遍历距离矩阵的右上角
			for(int i=0;i<clusterCount;i++)
			{
				for(int p=i+1;p<clusterCount;p++)
				{
					//如果两个cluster的距离小于threshold,则合并
					if(distanceMatrix[i][p]<=threshold)
						tuple.Union(oldClusterSet.get(i),oldClusterSet.get(p));
				}
			}

			this.tupleList.add(tuple);//添加tuple

			clusterCount=tuple.clusterSet.size();//更新簇数量
			distanceMatrix=new double[clusterCount][clusterCount];
			this.UpdateMatrix(distanceMatrix,tuple, type);//更新距离矩阵
		}
	}

	/**
	 * 重新计算距离矩阵
	 * @param distanceMatrix 需要更新的距离矩阵
	 * @param tuple 目前的tuple
	 * @param type 算法方式(Single Link等等)
	 */
	private void UpdateMatrix(double[][] distanceMatrix,Tuple tuple,Type type)
	{
		int clusterCount=tuple.clusterSet.size();//获取cluster的数量
		//遍历距离矩阵右上角
		for(int i=0;i<clusterCount;i++)
			for(int j=i+1;j<clusterCount;j++)
				distanceMatrix[i][j]=this.GetDistance(tuple.clusterSet.get(i), tuple.clusterSet.get(j), type);
	}

	/**
	 * 寻找最小距离作为距离阈值
	 * @param matrix 距离矩阵
	 * @return 最小阈值
	 */
	private double FindThreshold(double[][] matrix,int clusterCount)
	{
		double minDistance=Double.MAX_VALUE;
		for(int i=0;i<clusterCount;i++)
		{
			for(int j=i+1;j<clusterCount;j++)
			{
				if(matrix[i][j]<minDistance)
					minDistance=matrix[i][j];
			}
		}
		return minDistance;
	}

	/**
	 * 计算两个cluster之间的距离
	 * @param cluster1
	 * @param cluster2
	 * @param type 计算方式
	 * @return 距离
	 */
	private double GetDistance(Cluster cluster1,Cluster cluster2,Type type)
	{
		switch(type)
		{
			case SINGLE_LINK:
				return this.SLDistance(cluster1, cluster2);
			case COMPLETE_LINK:
				return this.CLDistance(cluster1, cluster2);
			case AVERAGE_LINK:
				return this.ALDistance(cluster1, cluster2);
		}
		return -1;
	}

	/**
	 * 以Single Link方式计算Cluster之间的距离
	 * @param cluster1
	 * @param cluster2
	 * @return 距离
	 */
	private double SLDistance(Cluster cluster1,Cluster cluster2)
	{
		double distance=Double.MAX_VALUE;
		for(String element1 : cluster1.elements)
		{
			int e1_index=this.elementNames.indexOf(element1);
			for(String element2 : cluster2.elements)
			{
				int e2_index=this.elementNames.indexOf(element2);
				double tempDistance=e1_index<e2_index?this.origionDistanceMatrix[e1_index][e2_index]
                                                     :this.origionDistanceMatrix[e2_index][e1_index];
				if(tempDistance<distance)
					distance=tempDistance;
			}
		}
		return distance;
	}

	/**
	 * 以Complete Link方式计算cluster之间的距离
	 * @param cluster1
	 * @param cluster2
	 * @return 距离
	 */
	private double CLDistance(Cluster cluster1,Cluster cluster2)
	{
		double distance=-1;
		for(String element1 : cluster1.elements)
		{
			int e1_index=this.elementNames.indexOf(element1);
			for(String element2 : cluster2.elements)
			{
				int e2_index=this.elementNames.indexOf(element2);
				double tempDistance=e1_index<e2_index?this.origionDistanceMatrix[e1_index][e2_index]
						                             :this.origionDistanceMatrix[e2_index][e1_index];
				if(tempDistance>distance)
					distance=tempDistance;
			}
		}
		return distance;
	}

	/**
	 * 以Average Link方式计算cluster之间的距离
	 * @param cluster1
	 * @param cluster2
	 * @return 距离
	 */
	private double ALDistance(Cluster cluster1,Cluster cluster2)
	{
		double sum=0;

		for(String element1 : cluster1.elements)
		{
			int e1_index=this.elementNames.indexOf(element1);
			for(String element2 : cluster2.elements)
			{
				int e2_index=this.elementNames.indexOf(element2);
				double tempDistance=e1_index<e2_index?this.origionDistanceMatrix[e1_index][e2_index]
						                             :this.origionDistanceMatrix[e2_index][e1_index];
				sum+=tempDistance;
			}
		}

		double count=cluster1.elements.size()*cluster2.elements.size();
		return sum/count;
	}

	/**
	 * 打印结果
	 */
	public void PrintResult()
	{
		for(Tuple tuple : this.tupleList)
		{
			System.out.println(tuple.toString());
		}
	}
}

对于上述案例,测试后的结果为:

testClusterResult

 

 

 

 

 

 

 

 

 

 

可见和之前的图片中的结果一致。

5 条评论

  1. 高大上,很有用! 掉渣天

  2. 好奇怪 在我弄完了商务智能的作业突然发现你这里有教程……= =
    =-= 数据结构各种不懂

  3. Thank a person for posting this, it has been unbelieveably instructional and helped me a lot

  4. I’m still learning from you, while I’m making my way to the top as well. I definitely love reading all that is written on your blog.Keep the tips coming. I loved it!

Miss Fan进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>