- 浏览: 230510 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
清林小篆:
引用[/col[size=xx-small][/size]or ...
tomcat ssl配置以及CAS单点登录探究 -
cyxy99:
u012534143 写道我用同样的方法,同样的节点关系,为什 ...
PageRank算法java实现版本 -
cyxy99:
schaha123 写道楼主还有一个问题想请教一下,下面这2段 ...
PageRank算法java实现版本 -
njthnet:
Participle 和 IkParticiple 这2个类找 ...
贝叶斯文本分类 java实现 -
u012534143:
我用同样的方法,同样的节点关系,为什么的得到的结果与您不一样呢 ...
PageRank算法java实现版本
在介绍最小生成树算法(MST)之前,简单说一下平均链接算法(average-link)的实现过程,平均链接聚类算法和单链接类似,多了计算聚类之间距离矩阵的步骤
实现步骤如下:
MST算法比较有意思点,不仅用于聚类,还可以解决最短铺路成本这类问题。
我们假设一个场景:现在想在多个城市之间铺网络,怎样才是最短距离?每个城市当作一个数据点,每个点间的距离称为一个边,最短距离实际上就是求得每个点都能连成边,但是又不会回路的情况。
实现过程如下:
1,首先建立城市类和边类,如下
2,MST核心类,Edge类表示一个边的两点和距离,
找最短距离的边的过程是:不断的纳入最短边,并且再根据这些已知的最短边的两端寻找最短边(md 这句话我也感觉绕口 但应该是最通俗的了)
第一步肯定是算出临近距离矩阵
3,测试一下
By 阿飞哥 转载请说明
腾讯微博:http://t.qq.com/duyunfeiRoom
新浪微博:http://weibo.com/u/1766094735
实现步骤如下:
- 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
发表评论
-
招Java培训老师(还是论坛招人靠谱)
2015-05-10 13:39 556好久没来坛子了,一来就搞这么有目的的事儿。。。 好吧, ... -
动手开发自己的mvc-3----容器该帮我们做什么?(非常的重点)
2013-01-22 13:55 1782注解注入 我们知道,Spring只有一个角色:工厂。这个工厂可 ... -
动手开发自己的mvc-2----完善控制层,提供自动注入和注解上传等功能
2013-01-22 13:44 2502当表单提交的内容过多 ,让懒惰的程序员一个个getPara ... -
动手开发自己的mvc-1----实现初步的控制层,实现各种配置和资源获取
2013-01-22 13:28 2741mvc框架最基础的功能就是跳转,struts2支持注 ... -
动手开发自己的mvc (系列)
2013-01-22 14:08 1890到年尾了,整理了一下我Evernote藏的各种文档,打算把ys ... -
整合了一个小的爬取流程框架
2013-01-08 13:04 1270弄了一个小的爬取流程框架,把之前工作中用到的一些小经验 ... -
Mahout各种推荐器的主要特点
2012-12-06 15:17 2927Mahout有很多推荐的实现,各有特点,在这里一并记录 ... -
怎样通过词频得到这个词频的排序?
2012-12-03 14:35 2038在大规模检索中,我们怎样通过已经的词频得到词频的排序 ... -
drools实现自定义业务规则
2012-10-12 11:49 2789最近做财务相关的积分规则,由于这个功能以后涉及到方方面面 ... -
贝叶斯文本分类 java实现
2012-09-25 15:15 12623昨天实现了一个基于贝叶斯定理的的文本分类,贝叶斯定理假 ... -
前段时间做了一个小型的MVC
2012-07-20 13:23 0前端时间做了一个小型的MVC,麻雀虽小,五脏俱全,目前实现的功 ... -
聚类算法之单链接算法java实现
2012-07-05 10:09 4247聚类算法中基于链接的算法大致有三种:单链接算法(s ... -
朴素贝叶斯分类器
2012-05-20 15:25 0NaiveBayes分类器的优点是能得到已知Y的条件下X的 ... -
PageRank算法java实现版本
2012-05-16 16:03 17242PageRank算法是Google的核心搜索算法,在所有 ... -
聚类算法之kmeans算法java版本
2012-04-22 21:34 20803聚类的意思很明确,物以类聚,把类似的事物放在一起。 ... -
昨天做了个小工具DB转pojo,html,sql
2012-03-21 13:15 1707做dbutils时为了方便就做了个小工具,省点小事儿吧。 -
我这儿的讨论(项目小组)区可以进来了
2012-02-28 10:38 150java项目小组群,前几天清了几个破坏气氛者,和不发言 ... -
智能web探究群组建立了
2011-11-24 12:10 1532最近群组已申请成功 ,地址是http://web.gr ... -
Cas https方式改为http方式
2011-09-24 13:02 2289最近项目要测试,来不及申请等待证书,所以先把项目改为http的 ... -
jdk6原生态webservice
2011-06-30 13:38 8886近期做cas 单点登录的时候由于要同步用户信息,所以准备在 ...
相关推荐
基于MST-单连接聚类算法C++实现,数据挖掘中单连接聚类算法基于最小生成树c++实现,有谁写出更好的,就上传给大家分享。
基于密度的最小生成树聚类算法,将最小生成树理论与基于密度的方法相结合,不仅体现了基于密度聚类方法的优点,而且聚类结果不依赖于用户参数的选择,聚类结果更合理,特别是对大数据集,算法非常有效。因此,本文在基于...
该算法通过MST维护空间数据的基本空间结构特征,通过打断MST中最不一致的边形成MST聚类,不仅具有密度的聚类方法能够聚集非球状簇和分布不均的数据集的特点,而且聚类结果不依赖于用户参数的选择,因此,离群挖掘结果更...
针对传统的应用于基因表示的最小生成树(MST)聚类算法在时间复杂度和聚类质量上的不足,提出了一种 新的应用于数据处理的改进最小生成树(IMST)的聚类算法 。该算法在提高构造最小生成树的效率的同时,通过对 初步划分的...
mst 用最小生成树聚类
目前经典的聚类算法在内存空间有限的情况下,聚类受到时间、空间等各方面的限制,提出一种基于代表点的快速聚类算法FCBRP (fast clustering based representative points ) .首先,判定数据集中所有节点的属性,当节点的...
第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络...
LDPMST_OPT.m包括LDP-MST算法(手稿的算法3),LDP_Searching.m包括算法1和算法2。LMSTCLU_OPT.m用于对局部簇进行聚类基于MST的聚类算法计算密度峰值。 drawcluster2用于绘制聚类结果。 综合数据集pacake包括我们在...
基于最小生成树的半监督聚类算法,霍萌萌,刘阳阳,已知的多数半监督聚类算法依赖成对约束的方法提出。这些算法通常使用先验知识提高聚类精度。本文使用另一种叫做标签传播的半监督
当提供不适当的参数或将其应用于由具有不同形状,大小和密度的聚类组成的数据集时,大多数聚类算法将变得无效。 为了缓解这些不足,我们提出了一种新颖的拆分合并层次聚类方法,其中采用最小生成树(MST)和基于MST...
与传统聚类算法中特征矩阵的向量化不同,本文针对MTS样本提出了一种基于矩阵数据的无监督模式识别方案。 为了减少计算量和时间消耗,首先设计了一种新颖的基于变量的主成分分析(VPCA)来降低MTS样本的维数。 然后...
针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim,PP)算法,基于此提出了前端驱动的并行MST算法——PB(PP Bor(u)vka)算法,并论证了PB算法的正确性。...
该工具箱包括使用以下聚类算法在ERP和自发(例如静止状态)EEG上运行微状态分析的功能: K-均值。 修正的K均值。 雾化和聚集层次聚类(AAHC) 地形雾化和聚集层次聚类(TAAHC) 变态微状态 请参阅我们的指南(或代码...
我们的自适应图聚类算法将图像分为不同的聚类,而具有高相关性的图像则保留在同一组中。 强/弱生成树(ST)条件增强了群集之间的连通性,并使多点云对齐更加可靠。 在所有群集中完成本地SfM之后,设计了精心设计的...
职能深度优先搜索 (dfs) 广度优先搜索(bfs) 连接组件(scomponents) 最大权重二分匹配 (bipartite_matching) Dijkstra 的最短路径 (dijkstra) Prim 的最小生成树 (mst_prim) 聚类系数(clustercoeffs) 有向聚类...
为了解决这个问题,本文提出了一种在协作自组织网络中基于协作聚类的功率分配(CCPA)算法。 在CCPA中,没有CC则无法连接网络。 首先我们对网络进行群集,然后使群集通过CC相互通信,然后使用MST减少群集之间的冗余...
Category_Topic_Hierarchy 维基百科类别的主题层次结构要运行此项目,您应该首先将 Obe.Util.common.PropertiesUtils.java line:36 修改为您的项目路径。 然后修改config.properties... Obe.Dao.Incre 是增量聚类算法。
问题:Bag(背包),Qap(二次指派),Tsp(旅行商),Mst(最小生成树),Target(目标函数),Tzs(图着色),Decode(解密),Cluster(聚类) 算法:Ga(遗传),Ts(禁忌),Sa(模拟退火),Aca(蚁群),Pso(粒子...
借助进化方法,找到斯坦纳树的MST(最小生成树) 第2季度:借助进化,找到Eggholder函数的全局最大值模糊FCM:模糊c均值算法,在几个数据集上运行FkNN:在相同数据集上运行的模糊k最近邻算法(指示聚类的边界)神经...