`
AngelAndAngel
  • 浏览: 234720 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

聚类算法之MST算法 java实现版本

阅读更多
   在介绍最小生成树算法(MST)之前,简单说一下平均链接算法(average-link)的实现过程,平均链接聚类算法和单链接类似,多了计算聚类之间距离矩阵的步骤
   实现步骤如下:
    

         
  • 1,将元素各成一组,把这些组放入容器H
  •      
  • 2,循环元素距离数组,根据两层下标得到将要比较的两个元素A,B
  •      
  • 3,在H中分别查找含有A,B的组AH,BH。假如AH不等于BH(也就是A,B不同组),  AH和BH的距离累加A,B的距离。
  •      
  • 4,得到组间距离数组后,循环比较组间距离与阀值,小于阀值,则此两组合并成一组,合并之前把H中的两个作为比较的原始组删除。
  •    
       

   MST算法比较有意思点,不仅用于聚类,还可以解决最短铺路成本这类问题。
   我们假设一个场景:现在想在多个城市之间铺网络,怎样才是最短距离?每个城市当作一个数据点,每个点间的距离称为一个边,最短距离实际上就是求得每个点都能连成边,但是又不会回路的情况。
   实现过程如下:
  1,首先建立城市类和边类,如下
 
/**
 * 城市
 * 
 * @author duyf
 * 
 */
class City {

	private String name;
	// 经度
	private double x;

	// 纬度
	private double y;

	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public boolean equals(Object obj) {
		if (obj == null) {
			return false;
		}
		if (this == obj) {
			return true;
		}
		City other = (City) obj;
		if (this.getX() == other.getX() && this.getY() == other.getY()) {
			return true;
		}
		return false;
	}
}

/**
 * 边距 包含两端数据点(城市)的索引
 * @author duyf
 *
 */
class Edge {
    
    private int i;
    private int j;
    private double w;

    Edge(int i, int j, double w) {
        this.i = i;
        this.j = j;
        this.w = w;
    }

    public int getI() {
        return i;
    }

    public int getJ() {
        return j;
    }

    public double getW() {
        return w;
    }

}
  


2,MST核心类,Edge类表示一个边的两点和距离,
找最短距离的边的过程是:不断的纳入最短边,并且再根据这些已知的最短边的两端寻找最短边(md 这句话我也感觉绕口 但应该是最通俗的了)


public class MST {

	private List<City> data;
	
	private double[][] ds;
	
	public MST(List<City> data){
		this.data=data;
	}
	
	public List<Edge> compute(){
		// 距离矩阵
		ds = new double[data.size()][data.size()];

		for (int i = 0; i < data.size(); i++) {
			City city1 = data.get(i);
			for (int j = i + 1; j < data.size(); j++) {
				City city2 = data.get(j);
				ds[i][j] = getDistance(city1, city2);
				// 矩阵 对称性
				ds[j][i] = ds[i][j];
			}
			ds[i][i] = 0.0;
		}	

		boolean[] isMst=new boolean[data.size()];
		isMst[0]=true;
		Edge edge=null;
		List<Edge> edges=new ArrayList<Edge>();
        while((edge=findMinEdge(isMst))!=null){
        	edges.add(edge);	
        	
        	//标记为已知MST数据点
        	isMst[edge.getJ()]=true;
        }
		return edges;
		
	}
	
	//找出 和 已知的MST数据点 最小距离的点
	private Edge findMinEdge(boolean[] isMst){
		//初始化无限大
		double minds = Double.POSITIVE_INFINITY;
		int minI=-1;
		int minJ=-1;
		Edge edge=null;
		for(int i=0;i<ds.length;i++){
			if(isMst[i]==true){
				for(int j=0;j<ds.length;j++){
					if(isMst[j]==false){
					    if(minds>ds[i][j]){
					    	minds=ds[i][j];
					    	minI=i;
					    	minJ=j;
						}
					}
				}
			}
		}
		if(minI>-1){
			edge=new Edge(minI,minJ,minds);
		}
		return edge;
	}
	
	// 计算空间距离
	private double getDistance(City city1, City city2) {
		 double  distance=Math.pow(city1.getX()-city2.getX(),2)+Math.pow(city1.getY()-city2.getY(),2);
		 return Math.sqrt(distance);
		 
	}
	
	
}


第一步肯定是算出临近距离矩阵

3,测试一下
public static void main(String[] args) {
		List<City> citys = new ArrayList<City>();

		City city0 = new City();
		city0.setName("北 京");
		city0.setX(116.28);
		city0.setY(39.54);
		citys.add(city0);
		
		City city1 = new City();
		city1.setName("上 海");
		city1.setX(121.29);
		city1.setY(31.14);
		citys.add(city1);

		City city2 = new City();
		city2.setName("天 津");
		city2.setX(117.11);
		city2.setY(39.09);
		citys.add(city2);

		City city3 = new City();
		city3.setName("重 庆");
		city3.setX(106.32);
		city3.setY(29.32);
		citys.add(city3);

		City city4 = new City();
		city4.setName("哈尔滨");
		city4.setX(126.41);
		city4.setY(45.45);
		citys.add(city4);

		City city5 = new City();
		city5.setName("长 春");
		city5.setX(125.19);
		city5.setY(43.52);
		citys.add(city5);

		City city6 = new City();
		city6.setName("南 京");
		city6.setX(118.50);
		city6.setY(32.02);
		citys.add(city6);

		City city7 = new City();
		city7.setName("武 汉");
		city7.setX(114.21);
		city7.setY(30.37);
		citys.add(city7);

		City city8 = new City();
		city8.setName("台 北");
		city8.setX(121.31);
		city8.setY(25.03);
		citys.add(city8);

		City city9 = new City();
		city9.setName("香 港");
		city9.setX(114.10);
		city9.setY(22.18);
		citys.add(city9);
		
		MST mst=new MST(citys);
		List<Edge> edges=mst.compute();
		
		System.out.println("------------------线路最佳方案如下------------------");
		for(Edge edge:edges){
			City from=citys.get(edge.getI());
			City to=citys.get(edge.getJ());
			double length=edge.getW();
			System.out.println(edge.getI()+"========>"+edge.getJ());
			System.out.println(from.getName()+"到"+to.getName()+",全长"+length);
		}

	}




By 阿飞哥 转载请说明
腾讯微博:http://t.qq.com/duyunfeiRoom
新浪微博:http://weibo.com/u/1766094735
分享到:
评论

相关推荐

    基于MST-单连接聚类算法C++实现

    ### 基于MST-单连接聚类算法C++实现 #### 概述 本文将详细介绍一个在数据挖掘领域中应用广泛的聚类算法——基于最小生成树(Minimum Spanning Tree, MST)的单连接聚类算法,并通过C++语言进行实现。该算法主要应用...

    基于最小生成树的基因数据聚类算法及特征基因的选择算法ppt

    为了应对这些问题,研究者们提出了基于最小生成树(Minimum Spanning Tree, MST)的聚类算法。MST是一种图论概念,能够在保持数据间连接性的前提下,以最低总权重构建树形结构。在基因数据的聚类中,MST的优势在于其...

    C# ArcEngine实现基于图论的聚类算法

    在本文中,我们将深入探讨如何使用C#编程语言与Esri的ArcEngine库结合,来实现基于图论的聚类算法。ArcEngine是GIS(地理信息系统)开发的强大工具,它为开发者提供了创建、管理和分析地理数据的能力。聚类算法则是...

    基于网格的最小生成树聚类算法.pdf

    本文旨在介绍一种基于网格的最小生成树(Minimum Spanning Tree, MST)聚类算法,并探讨其在特定网格环境下的应用。 #### 网格技术与数据挖掘基础 网格技术是一种分布式计算模型,能够连接不同地理位置的资源(如...

    基于最小生成树的多层次k-Means聚类算法及其在数据挖掘中的应用.pdf

    为了克服这些问题,研究人员提出了基于最小生成树(Minimum Spanning Tree,MST)的多层次k-Means聚类算法。这种算法首先通过构建最小生成树对数据进行分层处理,再利用k-Means算法进行高效的聚类,从而提高挖掘效率...

    自动聚类算法确定cluster数目的方法.docx

    聚类算法的目标是将相似的数据分到同一组,即所谓的簇(cluster)。然而,一个关键的问题是确定合适的簇数量(K值),这直接影响着聚类结果的质量。以下是一些自动确定聚类数目的方法: 1. **交叉验证**:交叉验证...

    一种处理障碍约束的聚类算法_王小乐.pdf

    本文所介绍的是一篇关于“一种处理障碍约束的聚类算法”,该算法由王小乐等研究人员提出,旨在解决在存在障碍约束的情况下进行空间聚类的问题。论文通过引用图论的相关知识,设计出一种分阶段的基于图的聚类算法。 ...

    基于MST聚类的离群检测算法研究

    基于密度的最小生成树聚类算法,将最小生成树理论与基于密度的方法相结合,不仅体现了基于密度聚类方法的优点,而且聚类结果不依赖于用户参数的选择,聚类结果更合理,特别是对大数据集,算法非常有效。因此,本文在基于...

    分布式最小生成树聚类的设计与实现.pdf

    本文提出了一种基于最小生成树的分布式聚类算法,该算法结合了适合的相似度度量方法,针对海量数据的分析问题进行了优化设计,并实现了基于MapReduce编程模型的分布式处理。 首先,聚类算法在数据挖掘中扮演着核心...

    CAN_聚类_聚类论文_图构造_

    例如,最小生成树(MST)或谱聚类算法就是基于图论的方法,它们通过分析图的拓扑结构来划分簇。 五、CAN.m 文件 在提供的文件列表中,“CAN.m”很可能是一个MATLAB代码文件,包含了聂飞平老师所描述的自适应邻域...

    基于MST聚类的空间数据离群挖掘算法

    该算法通过MST维护空间数据的基本空间结构特征,通过打断MST中最不一致的边形成MST聚类,不仅具有密度的聚类方法能够聚集非球状簇和分布不均的数据集的特点,而且聚类结果不依赖于用户参数的选择,因此,离群挖掘结果更...

    mst:用最小生成树聚类

    通过Python的相应库,我们可以轻松地实现MST算法,并将其应用于各种实际问题中。在mst-master这个压缩包文件中,很可能包含了关于这个主题的代码示例或者教程,可以帮助进一步理解和应用最小生成树聚类方法。

    融入改进的K-means聚类的协同过滤算法的研究与应用.docx

    【摘要】:本文深入探讨了将改进的K-means聚类算法应用于协同过滤推荐系统中的研究与实践。针对传统用户基础协同过滤算法存在的问题,如数据稀疏性和冷启动问题,作者提出了一种融合改进K-means的新型个性化推荐算法...

    多维数据的改进最小生成树聚类算法 (2008年)

    针对传统的应用于基因表示的最小生成树(MST)聚类算法在时间复杂度和聚类质量上的不足,提出了一种 新的应用于数据处理的改进最小生成树(IMST)的聚类算法 。该算法在提高构造最小生成树的效率的同时,通过对 初步划分的...

Global site tag (gtag.js) - Google Analytics