程式扎記: [ Algorithm ] Hierarchy Clustering : Complete-link

標籤

2012年5月26日 星期六

[ Algorithm ] Hierarchy Clustering : Complete-link


前言 :
在 Hierarchical Agglomerative Clustering (HAC) 中通常會先建立 K 個 Clusters (K 需事先決定), 接著計算最接近的 cluster pair 合成新的 node, 並依此邏輯逐序形成 Hierarchical Clustering Tree. 示意圖如下 :


問題是怎麼決定 Cluster 的距離或相似程度? 通常有幾種方案 :
* Single-link
Similarity of the most cosine-similar (single-link). 即在兩個 Cluster 的集合中, 找出最接近的兩點. 當作兩個 Cluster 的相似程度.

* Complete-link
Similarity of the "furthest" points, the least cosinesimilar. 即在兩個 Cluster 的集合中, 找出最遠的兩點距離 d 當作兩個 Cluster 的相似程度. 這樣可以保證這兩個集合合併後, 任何一個 pair 的距離不會大於 d.

* Centroid
Clusters whose centroids (centers of gravity) are the most cosine-similar

* Average-link
Average cosine between pairs of elements.

這邊我們要來介紹 Complete-link 的演算法.

Complete-link 說明 :
在 Complete-link 計算兩個 Cluster 的相似程度或距離時, 取的是兩兩 Cluster (ci, cj) 形成的集合中最遠的兩點, 公式如下 :


當最近或最相似的兩個的兩個 Cluster ci, cj 找到後, 另外一個 Cluster ck 與這個合成的 Cluster 的距離則為 :


而這樣的方法會讓合成的 Cluster 更為緊密. 接著我們會來看一個簡單範例.

Complete-link 範例 :
考慮我們有 A-F 共 6 個 Clusters, 接著我們計算兩兩間個 Similarity 並依高到低排序如下表 :


Step1 : 從表中取出第一個 Pair AF, 因為是第一個 Pair 所以完成第一個 Node


Step2 : 從表中取出下一個 Pair AE, 因為 A 與 Node AF 有重疊故計算 Pair AE 與 Node AF 的 Similarity. 但 EF 還沒出現在 Touched Pairs 中 (可以知道 EF 的 Similarity 較目前所有 Touched Pairs 小) , 故不做任何處理.


Step3 : 從表中取出下一個 Pair BF, 因為 F 與 Node AF 有重疊故計算 Pair BF 與 Node AF 的 Similarity. 但 AB 還沒出現在 Touched Pairs 中, 不做處理.


Step4 : 從表中取出下一個 Pair BE, 因為沒有任何 Node 與之有重疊, 故將 BE 形成一個新的 Node.


Step5 : 從表中取出下一個 Pair AD, 因為 A 與 Node AF 有重疊故計算 Pair AD 與 Node AF 的 Similarity. 但 DF 還沒出現在 Touched Pairs, 不做處理.


Step6 : 從表中取出下一個 Pair AC, 因為 A 與 Node AF 有重疊故計算 Pair AD 與 Node AF 的 Similarity. 但 CF 還沒出現在 Touched Pairs, 不做處理.


Step7 : 從表中取出下一個 Pair BD, 因為 B 與 Node BE 有重疊故計算 Pair BD 與 Node BE 的 Similarity. 但 DE 還沒出現在 Touched Pairs, 不做處理.


Step8 : 從表中取出下一個 Pair CE, 因為 E 與 Node BE 有重疊故計算 Pair CE 與 Node BE 的 Similarity. 但 BC 還沒出現在 Touched Pairs, 不做處理.


Step9 : 從表中取出下一個 Pair BC, 因為 B 與 Node BE 有重疊故計算 Pair BC 與 Node BE 的 Similarity. 因為 BC 與 BE 的 Pairs 組合 (BC, BE, CE) 都已經出現在 Touched Pairs, 故將 C 加到 Node BE 中 :


Step10 : 從表中取出下一個 Pair DE, 因為 E 與 Node BCE 有重疊故計算 Pair DE 與 Node BCE 的 Similarity. 但 CD 還沒出現在 Touched Pairs, 不做處理.


Step11 : 從表中取出下一個 Pair AB, 因為 A 出現在 Node AF 中; B 出現在 Node BCE 中, 故計算 Node AF 與 Node BCE 的 Similarity. 但 EF 還沒出現在 Touched Pairs, 不做處理.


Step12 : 從表中取出下一個 Pair CD, 因為 C 出現在 Node BCE 中, 故計算 Pair CD 與 Node BCE 的 Similarity = min(BC=0.4, CE=0.5, BD=0.5, CD=0.3, DE=0.4) = 0.3 :


Step13 : 從表中取出下一個 Pair EF, 因為 F 出現在 Node AF 中; E 出現在 Node BCDE 中, 故計算 Node AF 與 Node BCDE 的 Similarity. 但 CF 還沒出現在 Touched Pairs, 不做處理.


Step14 : 從表中取出下一個 Pair CF, 因為 F 出現在 Node AF 中; C 出現在 Node BCDE 中, 故計算 Node AF 與 Node BCDE 的 Similarity. 但 DF 還沒出現在 Touched Pairs, 不做處理.


Step15 : 從表中取出下一個 Pair DF, 因為 F 出現在 Node AF 中; D 出現在 Node BCDE 中, 故計算 Node AF 與 Node BCDE 的 Similarity=0.1 (因為 DF 是最後一個 Pair=0.1).


範例代碼 :
底下為上述 Complete-link 演算法的實作, 提供參考 :
- CompleteLink.java :
  1. package john.cluster.hierarchical;  
  2.   
  3. import java.util.Comparator;  
  4. import java.util.HashSet;  
  5. import java.util.LinkedList;  
  6. import java.util.List;  
  7. import java.util.PriorityQueue;  
  8. import java.util.Set;  
  9. import java.util.TreeSet;  
  10. import john.cluster.hierarchical.proto.ILink;  
  11.   
  12. public class CompleteLink implements ILink{  
  13.     private PriorityQueue pcList = new PriorityQueue(10new PCComparator());  
  14.     private Node root = null;  
  15.   
  16.     public CompleteLink(){}  
  17.     public CompleteLink(PairClr... pcs){  
  18.         for(PairClr pc:pcs) pcList.add(pc);  
  19.     }  
  20.       
  21.     public void addPairCluster(String name, float sim)  
  22.     {  
  23.         pcList.add(new PairClr(name, sim));  
  24.     }  
  25.       
  26.     @Override  
  27.     public void compute(){  
  28.         Set touchPairSet = new HashSet();  
  29.         List nodeList = new LinkedList();  
  30.         while(pcList.size()>0)  
  31.         {  
  32.             PairClr pc = pcList.poll();  
  33.             //System.out.printf("\t[Info] Deal PairClr=%s=%f...\n", pc.name, pc.sim);  
  34.             touchPairSet.add(pc);  
  35.             if(nodeList.size()==0)  
  36.             {                 
  37.                 char chs[] = pc.toCharArray();  
  38.                 Node n1 = new Node(new Character(chs[0]));  
  39.                 //System.out.printf("\t[Info] Test n1 %d\n", n1.cls.size());  
  40.                 Node n2 = new Node(new Character(chs[1]));  
  41.                 //System.out.printf("\t[Info] Test n2 %d\n", n2.cls.size());  
  42.                 Node root = new Node(pc.sim);  
  43.                 root.addChildNode(n1); root.addChildNode(n2);  
  44.                 nodeList.add(root);  
  45.                 //System.out.printf("\t[Info] Test %d\n", root.cls.size());  
  46.             }  
  47.             else  
  48.             {  
  49.                 int vd = -1;  
  50.                 Node targetNode1 = null;  
  51.                 Node targetNode2 = null;  
  52.                 for(Node n:nodeList)  
  53.                 {  
  54.                     vd = n.validate(pc);  
  55.                     //System.out.printf("\t[Info] Node=%s ; PC=%s ; vd=%d\n", n , pc,  vd);  
  56.                     if(vd>0)  
  57.                     {  
  58.                         if(targetNode1==null) targetNode1 = n;  
  59.                         else {  
  60.                             targetNode2 = n;  
  61.                             break;  
  62.                         }  
  63.                     }  
  64.                     else if(vd==0)  
  65.                     {  
  66.                         break;  
  67.                     }  
  68.                     else continue;                    
  69.                 }  
  70.                   
  71.                 if(targetNode1!=null && targetNode2!=null)   
  72.                 {  
  73.                     // Two nodes involve  
  74.                     Set cls = new HashSet();  
  75.                     cls.addAll(targetNode1.cls);  
  76.                     cls.addAll(targetNode2.cls);  
  77.                     if(isCover(cls, touchPairSet))  
  78.                     {  
  79.                         Node root = new Node(pc.sim);  
  80.                         root.addChildNode(targetNode2);  
  81.                         root.addChildNode(targetNode1);  
  82.                         nodeList.remove(targetNode2);  
  83.                         nodeList.remove(targetNode1);  
  84.                         nodeList.add(root);  
  85.                     }  
  86.                 }  
  87.                 else if(targetNode1!=null)  
  88.                 {  
  89.                     // One node cover!  
  90.                     Set cls = new HashSet();  
  91.                     cls.addAll(targetNode1.cls);  
  92.                     for(Character c:pc.toCharArray()) cls.add(c);  
  93.                     if(isCover(cls, touchPairSet))  
  94.                     {  
  95.                         Node n = new Node(new Character((char)vd));  
  96.                         Node root = new Node(pc.sim);  
  97.                         root.addChildNode(n);  
  98.                         root.addChildNode(targetNode1);  
  99.                         nodeList.remove(targetNode1);  
  100.                         nodeList.add(root);  
  101.                     }  
  102.                 }  
  103.                 else if(targetNode2!=null)  
  104.                 {  
  105.                     // One node cover!  
  106.                     Set cls = new HashSet();  
  107.                     cls.addAll(targetNode2.cls);  
  108.                     for(Character c:pc.toCharArray()) cls.add(c);  
  109.                     if(isCover(cls, touchPairSet))  
  110.                     {  
  111.                         Node n = new Node(new Character((char)vd));  
  112.                         Node root = new Node(pc.sim);  
  113.                         root.addChildNode(n);  
  114.                         root.addChildNode(targetNode2);  
  115.                         nodeList.remove(targetNode2);  
  116.                         nodeList.add(root);  
  117.                     }  
  118.                 }  
  119.                 else  
  120.                 {  
  121.                     if(vd!=0// None node cover!  
  122.                     {  
  123.                         //System.out.printf("\t[Test] none node cover!\n");  
  124.                         char chs[] = pc.toCharArray();  
  125.                         Node n1 = new Node(new Character(chs[0]));  
  126.                         Node n2 = new Node(new Character(chs[1]));  
  127.                         Node root = new Node(pc.sim);  
  128.                         root.addChildNode(n1); root.addChildNode(n2);  
  129.                         nodeList.add(root);  
  130.                     }  
  131.                 }  
  132.             }  
  133.         }     
  134.         root = nodeList.get(0);  
  135.     }  
  136.       
  137.     /** 
  138.      * BD : Make sure the composition pair from Set as 'cls' all covered in touched Pairs as 'touchPC'. 
  139.      * @param cls 
  140.      * @param touchPC 
  141.      * @return 
  142.      */  
  143.     public boolean isCover(Set cls, Set touchPC)  
  144.     {  
  145.         Character cs[] = new Character[cls.size()];  
  146.         cls.toArray(cs);  
  147.         for(int i=0; i1; i++)  
  148.         {  
  149.             for(int j=i+1; j
  150.             {  
  151.                 if(!touchPC.contains(new PairClr(cs[i], cs[j]))) {                
  152.                     return false;  
  153.                 }  
  154.             }  
  155.         }  
  156.         return true;  
  157.     }  
  158.       
  159.     public class PairClr{  
  160.         public float sim = 0;  
  161.         public String name = null;        
  162.         public PairClr(String name, float sim){this.name = name; this.sim = sim;}  
  163.         public PairClr(Character c1, Character c2){this.name = String.format("%c%c", c1, c2); }  
  164.           
  165.         @Override    
  166.         public int hashCode() {    
  167.             char chs[] = this.toCharArray();  
  168.             int hash = 0;  
  169.             for(char ch:chs) hash+=ch;  
  170.             return hash;  
  171.         }  
  172.           
  173.         @Override  
  174.         public boolean equals(Object pc)  
  175.         {             
  176.             if(pc instanceof PairClr)  
  177.             {  
  178.                 PairClr pairClr = (PairClr)pc;  
  179.                 StringBuffer sb = new StringBuffer(pairClr.name);  
  180.                 //System.out.printf("\t[Test] name=%s ; Check %s and %s...\n", name, sb.toString(), sb.reverse().toString());  
  181.                 if(sb.toString().equals(name) || sb.reverse().toString().equals(name)) return true;               
  182.             }  
  183.             return false;  
  184.         }  
  185.         public char[] toCharArray(){return name.toCharArray();}  
  186.         @Override  
  187.         public String toString(){return name;}  
  188.     }  
  189.       
  190.     public class Node{  
  191.         public Set cls = new TreeSet();  
  192.         public float value = -1;  
  193.         public List childNodes = new LinkedList();  
  194.           
  195.         public Node(Character ch){cls.add(ch);}  
  196.         public Node(float value) {this.value = value;}  
  197.         public Node(float value, Character ch)  
  198.         {  
  199.             this(value); cls.add(ch);  
  200.         }  
  201.           
  202.         public void addChildNode(Node n){cls.addAll(n.cls); childNodes.add(n);}  
  203.           
  204.         public int validate(PairClr pc)  
  205.         {  
  206.             char chs[] = pc.name.toCharArray();  
  207.             if(cls.contains(chs[0]) && !cls.contains(chs[1]))  
  208.             {  
  209.                 return chs[1]; /*Has one*/  
  210.             }  
  211.             else if(cls.contains(chs[1]) && !cls.contains(chs[0]))  
  212.             {  
  213.                 return chs[0]; /*Has one*/  
  214.             }  
  215.             else if(cls.contains(chs[0]) && cls.contains(chs[1]))  
  216.             {  
  217.                 return 0/*Has two*/  
  218.             }  
  219.             else  
  220.             {  
  221.                 return -1/*Has none*/  
  222.             }  
  223.         }  
  224.           
  225.         @Override  
  226.         public String toString(){  
  227.               
  228.             StringBuffer sb = new StringBuffer("");  
  229.             for(Character ch:cls) sb.append(String.valueOf(ch));  
  230.             return sb.toString();  
  231.         }  
  232.     }  
  233.       
  234.     class PCComparator implements Comparator{  
  235.         @Override  
  236.         public int compare(PairClr o1, PairClr o2) {  
  237.             if(o1.sim> o2.sim) return -1;  
  238.             else if(o1.sim< o2.sim) return 1;  
  239.             else return 0;  
  240.         }         
  241.     }  
  242.       
  243.     protected void _showTree(Node n)  
  244.     {  
  245.         if(n.childNodes.size()==0) System.out.printf("\t[SingleLink] Node=%s is leaf node.\n", n);  
  246.         else  
  247.         {  
  248.             for(Node cn:n.childNodes)  
  249.             {  
  250.                 System.out.printf("\t[SingleLink] Node=%s(%f) has child node=%s...\n", n, n.value, cn);  
  251.             }  
  252.             for(Node cn:n.childNodes)  
  253.             {  
  254.                 _showTree(cn);  
  255.             }  
  256.         }  
  257.     }  
  258.       
  259.     public void showTree()  
  260.     {  
  261.         if(root!=null)  
  262.         {  
  263.             _showTree(root);  
  264.         }  
  265.         else  
  266.         {  
  267.             System.out.printf("\t[SingleLink] root is null!\n");  
  268.         }  
  269.     }  
  270.       
  271.     public static void main(String[] args) {      
  272.         // Initialize CompleteLink  
  273.         CompleteLink link = new CompleteLink();  
  274.         link.addPairCluster("AF", (float)0.9);  
  275.         link.addPairCluster("AE", (float)0.8);  
  276.         link.addPairCluster("AD", (float)0.6);  
  277.         link.addPairCluster("AC", (float)0.5);  
  278.         link.addPairCluster("AB", (float)0.3);  
  279.         link.addPairCluster("BF", (float)0.8);  
  280.         link.addPairCluster("BE", (float)0.7);  
  281.         link.addPairCluster("BD", (float)0.5);  
  282.         link.addPairCluster("BC", (float)0.4);  
  283.         link.addPairCluster("CE", (float)0.5);  
  284.         link.addPairCluster("CD", (float)0.3);  
  285.         link.addPairCluster("CF", (float)0.2);  
  286.         link.addPairCluster("DE", (float)0.4);  
  287.         link.addPairCluster("DF", (float)0.1);  
  288.         link.addPairCluster("EF", (float)0.3);  
  289.           
  290.         // Compute Hierarchy Clustering  
  291.         link.compute();  
  292.           
  293.         // Show Hierarchy Tree.  
  294.         link.showTree();  
  295.     }  
  296. }  
執行結果如下 :


補充說明 :
[ Java Essence ] 記憶中的那個東西 : 要怎麼參考呢 (物件相等性)
JDK 6.0 > java.util.PriorityQueue
使用在儲存 Cluster Pair, 讓我們可以由較高的 Similarity 依序取出 Cluster Pair 進行處理...


沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!