层次聚类法(最小距离)

     聚类有k-means聚类与本文介绍的层次聚类法。k-means在以前的文章(http://www.highersoft.net/html/notice/notice_566.html)中介绍过，需要输入一个k作为聚类的数量。而层次聚类法，不需要输入k。它是通过形成一个关联树，然后，最上层就是距离最近的两点，这样，断1条线会形成两个类，断2条形成3个类,断n条形成n+1个类。

先给一算法描述:
    假设有n个对象进行聚类，初始时每个单个对象被看做一个簇；接着，将最相似的两个簇合并为一个簇，共产生(n-1)个簇;然后继续合并最相似的两个簇，直至所有对象被合并到一个簇中。
    簇之间地的相似度有多种算法，我目前只学会了最小距离法(另有最大距离、平均距离、质心距离),介绍下:
    最小距离,又称单链接(Single Link),是基于来自于两个簇中的结点之间的最小距离来衡量两个簇的相似度。合并最小距离最小的两个簇。

    下面的java代码是我计算的一个Example,但它并不是直接输出树图，而是给出两个点的最小距离升序排列，然后我们可根据这个排列，用笔画出这个树图来。


package net.highersoft.service.gather;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import lombok.Data;
import net.highersoft.service.apriori.PermutationCombination;

public class LayerGather {
	private static StringBuffer process=new StringBuffer();
	public static void main(String[] args) {
		List<LayerGatherPoint> points=new ArrayList<>();
		points.add(new LayerGatherPoint("A",1d,2d));
		points.add(new LayerGatherPoint("B",2d,1d));
		points.add(new LayerGatherPoint("C",3d,2.5d));
		points.add(new LayerGatherPoint("D",4d,4.6d));
		points.add(new LayerGatherPoint("E",4.5d,5d));
		points.add(new LayerGatherPoint("F",5d,4.5d));
		points.add(new LayerGatherPoint("G",6d,3d));
		points.add(new LayerGatherPoint("H",6d,4d));
		points.add(new LayerGatherPoint("I",7d,3.5d));
		points.add(new LayerGatherPoint("J",3d,4.8d));
		
		layerGather(points);
	}
	public static void layerGather(List<LayerGatherPoint> srcPoints) {
		List<LineNode> lineNodes=new ArrayList<>();
		List<List<LayerGatherPoint>> combs=PermutationCombination.combinationObj(srcPoints, 2);
		
		for(List<LayerGatherPoint> comb:combs) {
			double x=comb.get(0).getC1()-comb.get(1).getC1();
			double y=comb.get(0).getC2()-comb.get(1).getC2();
			double dist=Math.sqrt(x*x+y*y);
			LineNode lineNode=new LineNode(comb.get(0),comb.get(1),dist);
			lineNodes.add(lineNode);
			
		}
		List<Set<LineNode>>	realLayerList=new ArrayList<>();
		createLayer(lineNodes,realLayerList);
		System.out.println("聚类过程:\r\n"+process);
		/*
		for(Set<LineNode> l:realLayerList) {
			System.out.println("real:"+l);
		}
		*/
		
	}
	private static void addLineNode(List<Set<LineNode>>	realLayerList,LineNode node) {
		Set<LineNode> find=null;
		boolean isA=false;
		for(Set<LineNode> set:	realLayerList) {
			for(LineNode ln:set) {
				if(node.getNodeA().getName().equals(ln.getNodeA().getName())||
						node.getNodeA().getName().equals(ln.getNodeB().getName())) {
					find=set;
					isA=true;
					break;
				}
				if(node.getNodeB().getName().equals(ln.getNodeA().getName())||
						node.getNodeB().getName().equals(ln.getNodeB().getName())) {
					find=set;
					isA=false;
					break;
				}
			}
		}
		if(find!=null) {
			/*
			 * 找到类有几种情况,
			 * 1.两个分别在两个类里
			 * 2.两个在一个类里
			 * （现在已经确定一个在一个类里，那么另一个有两种情况。不在任何分类里,直接加入就好了。在某个分类里，与前者在不同分类则合并两个类，相同类，不用处理。）
			 */
			
			
			Set<LineNode> otherFind=null;
			for(Set<LineNode> set:	realLayerList) {
				for(LineNode ln:set) {
					if(isA) {
						if(node.getNodeB().getName().equals(ln.getNodeA().getName())||
								node.getNodeB().getName().equals(ln.getNodeB().getName())) {
							otherFind=set;
							break;
						}
					}else {
						if(node.getNodeA().getName().equals(ln.getNodeA().getName())||
								node.getNodeA().getName().equals(ln.getNodeB().getName())) {
							otherFind=set;
							break;
						}
					}
					
				}
			}
			if(otherFind!=null) {
				if(find.equals(otherFind)) {
					System.out.print("两点在相同类,把["+node.getNodeA().getName()+","+node.getNodeB().getName()+"]加入类:");
					System.out.println(printClass(find));
					find.add(node);
				}else {
					System.out.println("两点在不同类，合并类:");
					Set<LineNode> newClass=new HashSet<LineNode>();
					newClass.addAll(find);
					newClass.addAll(otherFind);
					realLayerList.remove(find);
					realLayerList.remove(otherFind);
					realLayerList.add(newClass);
					System.out.println(printClass(newClass));
					process.append(print(realLayerList)+"\r\n");
					
				}
			}else {
				
				System.out.print("只有一点在类，把["+node.getNodeA().getName()+","+node.getNodeB().getName()+"]加入类:");
				System.out.println(printClass(find));
				find.add(node);
				process.append(print(realLayerList)+"\r\n");
				
			}
			
			
		}else {
			realLayerList.add(new HashSet<>(Arrays.asList(node)));
			System.out.println("添加新类:"+node.getNodeA().getName()+","+node.getNodeB().getName());
			process.append(print(realLayerList)+"\r\n");
			
		}
	}
	private static String printClass(Set<LineNode>	find) {
		if(find==null) {
			return "";
		}
		Set<String> nodeName=new HashSet<>();
		for(LineNode ln:find) {
			nodeName.add(ln.getNodeA().getName());
			nodeName.add(ln.getNodeB().getName());
		}
		return nodeName.toString();
	}
	private static String print(List<Set<LineNode>>	realLayerList) {
		StringBuffer sb=new StringBuffer();
		
		
		for(Set<LineNode> set:realLayerList) {
			Set<String> nodeName=new HashSet<>();
			for(LineNode ln:set) {
				nodeName.add(ln.getNodeA().getName());
				nodeName.add(ln.getNodeB().getName());
			}
			sb.append(nodeName);
			
		}
		return sb.toString();
		
	}
	
	private static void createLayer(List<LineNode> lineNodes,List<Set<LineNode>>	realLayerList) {
		
		
		
		Double minDist=null;
		LineNode realLayer=null;
		int minIndex=0;
		Map<LineNode,Integer> eqNodes=new HashMap<>();
		for(int i=0;i<lineNodes.size();i++) {
			LineNode lineNode=lineNodes.get(i);
			if(minDist==null) {
				minIndex=i;
				minDist=lineNode.getDist();
				realLayer=lineNode;
				eqNodes.put(lineNode,i);
			}else if(lineNode.getDist()<minDist) {
				minIndex=i;
				minDist=lineNode.getDist();
				realLayer=lineNode;
				eqNodes.clear();
				eqNodes.put(lineNode,i);
			}else if(minDist.equals(lineNode.getDist())) {
				//如果当前两点距离与最小的距离相同，则取数量最小的聚为一类
				eqNodes.put(lineNode,i);
				
			}
		}
		if(eqNodes.size()==1) {
			addLineNode(realLayerList,realLayer);
		}else {
			
			
			
			Set<LineNode> minMember=null;
			for(Entry<LineNode,Integer> eqNode: eqNodes.entrySet()) {
				for(Set<LineNode> c:realLayerList) {
					for(LineNode realNode:c) {
						if(realNode.getNodeA().getName().equals(eqNode.getKey().getNodeA().getName())||
								realNode.getNodeA().getName().equals(eqNode.getKey().getNodeB().getName())||
								realNode.getNodeB().getName().equals(eqNode.getKey().getNodeA().getName())||
								realNode.getNodeB().getName().equals(eqNode.getKey().getNodeB().getName())) {
							if(minMember==null) {
								minMember=c;
								minIndex=eqNode.getValue();
							}else if(c.size()<minMember.size()) {
								minMember=c;
								minIndex=eqNode.getValue();
							}
						}
					}
				}
			}
			
			System.out.print("相同的距离结点:");
			for(Entry<LineNode,Integer> eqNode: eqNodes.entrySet()) {
				System.out.print("["+eqNode.getKey().getNodeA().getName()+" "+eqNode.getKey().getNodeB().getName()+"] ");
			}
			System.out.println();
			System.out.println("取数量最小类作为聚类:"+printClass(minMember)+"将["+lineNodes.get(minIndex).getNodeA().getName()+","+lineNodes.get(minIndex).getNodeB().getName()+"]聚类");
			addLineNode(realLayerList,lineNodes.get(minIndex));
		}
		System.out.println("当前聚类:"+print(realLayerList));
		lineNodes.remove(minIndex);
		if(lineNodes.size()>0) {
			createLayer(lineNodes,realLayerList);
		}
		
		
	}

}

里面用了一个工具类(组合):http://www.highersoft.net/html/notice/notice_553.html

然后就可以画树图了:

这里要注意下，上例子中有10个数，C(10,2)的数量大于上面图里的线条数，为什么？

比如，先有DE,形成了一个簇(类),又发现DF是比较近的，所以像上面这样画形成簇(DEF)，又经过n个组合后发现，EF出现了，而刚才的（DEF）已经包含了(EF),所以不画了。

注意第2点，AB的连线比别的"高",为什么？因为这两距离较远。

有了这个图，想分成几类就分几类了。

所有两点的距离，可用笔算:


下面是控制台打印记录:

添加新类:D,E
当前聚类:[D, E]
只有一点在类，把[E,F]加入类:[D, E]
当前聚类:[D, E, F]
添加新类:G,H
当前聚类:[D, E, F][G, H]
两点在相同类,把[D,F]加入类:[D, E, F]
当前聚类:[D, E, F][G, H]
只有一点在类，把[D,J]加入类:[D, E, F]
当前聚类:[D, E, F, J][G, H]
相同的距离结点:[F H] [G I] [H I] 
取数量最小类作为聚类:[G, H]将[F,H]聚类
两点在不同类，合并类:
[D, E, F, G, H, J]
当前聚类:[D, E, F, G, H, J]
相同的距离结点:[G I] [H I] 
取数量最小类作为聚类:[D, E, F, G, H, J]将[G,I]聚类
只有一点在类，把[G,I]加入类:[D, E, F, G, H, J]
当前聚类:[D, E, F, G, H, I, J]
两点在相同类,把[H,I]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J]
添加新类:A,B
当前聚类:[D, E, F, G, H, I, J][A, B]
两点在相同类,把[E,J]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J][A, B]
相同的距离结点:[F G] [B C] [E H] 
取数量最小类作为聚类:[A, B]将[B,C]聚类
只有一点在类，把[B,C]加入类:[A, B]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
相同的距离结点:[F G] [E H] 
取数量最小类作为聚类:[D, E, F, G, H, I, J]将[F,G]聚类
两点在相同类,把[F,G]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
两点在相同类,把[E,H]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
两点在相同类,把[F,J]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
两点在相同类,把[A,C]加入类:[A, B, C]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
两点在相同类,把[D,H]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
两点在相同类,把[F,I]加入类:[D, E, F, G, H, I, J]
当前聚类:[D, E, F, G, H, I, J][A, B, C]
两点在不同类，合并类:
[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[C,D]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[E,G]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[D,G]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[C,F]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
相同的距离结点:[E I] [C E] 
取数量最小类作为聚类:[A, B, C, D, E, F, G, H, I, J]将[E,I]聚类
两点在相同类,把[E,I]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[C,E]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[C,G]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[H,J]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[D,I]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[C,H]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[A,J]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[G,J]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,J]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[A,D]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,D]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[C,I]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[I,J]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,G]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
相同的距离结点:[A E] [B F] 
取数量最小类作为聚类:[A, B, C, D, E, F, G, H, I, J]将[A,E]聚类
两点在相同类,把[A,E]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,F]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
相同的距离结点:[A F] [B E] 
取数量最小类作为聚类:[A, B, C, D, E, F, G, H, I, J]将[A,F]聚类
两点在相同类,把[A,F]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,E]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,H]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[A,G]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[A,H]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[B,I]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
两点在相同类,把[A,I]加入类:[A, B, C, D, E, F, G, H, I, J]
当前聚类:[A, B, C, D, E, F, G, H, I, J]
聚类过程:
[D, E]
[D, E, F]
[D, E, F][G, H]
[D, E, F, J][G, H]
[D, E, F, G, H, J]
[D, E, F, G, H, I, J]
[D, E, F, G, H, I, J][A, B]
[D, E, F, G, H, I, J][A, B, C]
[A, B, C, D, E, F, G, H, I, J]


参考资料:

《商务智能方法与应用》刘红岩 编著

  https://wenku.baidu.com/view/7b46291533687e21af45a959.html

文/程忠 浏览次数：0次   2020-01-01 20:31:57

相关阅读

评论:
点击刷新

↓ 广告开始-头部带绿为生活 ↓
↑ 广告结束-尾部支持多点击 ↑