程式扎記

前言 :
在 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 :

view plaincopy to clipboardprint?
package john.cluster.hierarchical;  
  
import java.util.Comparator;  
import java.util.HashSet;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.PriorityQueue;  
import java.util.Set;  
import java.util.TreeSet;  
import john.cluster.hierarchical.proto.ILink;  
  
public class CompleteLink implements ILink{  
    private PriorityQueue pcList = new PriorityQueue(10, new PCComparator());  
    private Node root = null;  
  
    public CompleteLink(){}  
    public CompleteLink(PairClr... pcs){  
        for(PairClr pc:pcs) pcList.add(pc);  
    }  
      
    public void addPairCluster(String name, float sim)  
    {  
        pcList.add(new PairClr(name, sim));  
    }  
      
    @Override  
    public void compute(){  
        Set touchPairSet = new HashSet();  
        List nodeList = new LinkedList();  
        while(pcList.size()>0)  
        {  
            PairClr pc = pcList.poll();  
            //System.out.printf("\t[Info] Deal PairClr=%s=%f...\n", pc.name, pc.sim);  
            touchPairSet.add(pc);  
            if(nodeList.size()==0)  
            {                 
                char chs[] = pc.toCharArray();  
                Node n1 = new Node(new Character(chs[0]));  
                //System.out.printf("\t[Info] Test n1 %d\n", n1.cls.size());  
                Node n2 = new Node(new Character(chs[1]));  
                //System.out.printf("\t[Info] Test n2 %d\n", n2.cls.size());  
                Node root = new Node(pc.sim);  
                root.addChildNode(n1); root.addChildNode(n2);  
                nodeList.add(root);  
                //System.out.printf("\t[Info] Test %d\n", root.cls.size());  
            }  
            else  
            {  
                int vd = -1;  
                Node targetNode1 = null;  
                Node targetNode2 = null;  
                for(Node n:nodeList)  
                {  
                    vd = n.validate(pc);  
                    //System.out.printf("\t[Info] Node=%s ; PC=%s ; vd=%d\n", n , pc,  vd);  
                    if(vd>0)  
                    {  
                        if(targetNode1==null) targetNode1 = n;  
                        else {  
                            targetNode2 = n;  
                            break;  
                        }  
                    }  
                    else if(vd==0)  
                    {  
                        break;  
                    }  
                    else continue;                    
                }  
                  
                if(targetNode1!=null && targetNode2!=null)   
                {  
                    // Two nodes involve  
                    Set cls = new HashSet();  
                    cls.addAll(targetNode1.cls);  
                    cls.addAll(targetNode2.cls);  
                    if(isCover(cls, touchPairSet))  
                    {  
                        Node root = new Node(pc.sim);  
                        root.addChildNode(targetNode2);  
                        root.addChildNode(targetNode1);  
                        nodeList.remove(targetNode2);  
                        nodeList.remove(targetNode1);  
                        nodeList.add(root);  
                    }  
                }  
                else if(targetNode1!=null)  
                {  
                    // One node cover!  
                    Set cls = new HashSet();  
                    cls.addAll(targetNode1.cls);  
                    for(Character c:pc.toCharArray()) cls.add(c);  
                    if(isCover(cls, touchPairSet))  
                    {  
                        Node n = new Node(new Character((char)vd));  
                        Node root = new Node(pc.sim);  
                        root.addChildNode(n);  
                        root.addChildNode(targetNode1);  
                        nodeList.remove(targetNode1);  
                        nodeList.add(root);  
                    }  
                }  
                else if(targetNode2!=null)  
                {  
                    // One node cover!  
                    Set cls = new HashSet();  
                    cls.addAll(targetNode2.cls);  
                    for(Character c:pc.toCharArray()) cls.add(c);  
                    if(isCover(cls, touchPairSet))  
                    {  
                        Node n = new Node(new Character((char)vd));  
                        Node root = new Node(pc.sim);  
                        root.addChildNode(n);  
                        root.addChildNode(targetNode2);  
                        nodeList.remove(targetNode2);  
                        nodeList.add(root);  
                    }  
                }  
                else  
                {  
                    if(vd!=0) // None node cover!  
                    {  
                        //System.out.printf("\t[Test] none node cover!\n");  
                        char chs[] = pc.toCharArray();  
                        Node n1 = new Node(new Character(chs[0]));  
                        Node n2 = new Node(new Character(chs[1]));  
                        Node root = new Node(pc.sim);  
                        root.addChildNode(n1); root.addChildNode(n2);  
                        nodeList.add(root);  
                    }  
                }  
            }  
        }     
        root = nodeList.get(0);  
    }  
      
    /** 
     * BD : Make sure the composition pair from Set as 'cls' all covered in touched Pairs as 'touchPC'. 
     * @param cls 
     * @param touchPC 
     * @return 
     */  
    public boolean isCover(Set cls, Set touchPC)  
    {  
        Character cs[] = new Character[cls.size()];  
        cls.toArray(cs);  
        for(int i=0; i1; i++)  
        {  
            for(int j=i+1; j
            {  
                if(!touchPC.contains(new PairClr(cs[i], cs[j]))) {                
                    return false;  
                }  
            }  
        }  
        return true;  
    }  
      
    public class PairClr{  
        public float sim = 0;  
        public String name = null;        
        public PairClr(String name, float sim){this.name = name; this.sim = sim;}  
        public PairClr(Character c1, Character c2){this.name = String.format("%c%c", c1, c2); }  
          
        @Override    
        public int hashCode() {    
            char chs[] = this.toCharArray();  
            int hash = 0;  
            for(char ch:chs) hash+=ch;  
            return hash;  
        }  
          
        @Override  
        public boolean equals(Object pc)  
        {             
            if(pc instanceof PairClr)  
            {  
                PairClr pairClr = (PairClr)pc;  
                StringBuffer sb = new StringBuffer(pairClr.name);  
                //System.out.printf("\t[Test] name=%s ; Check %s and %s...\n", name, sb.toString(), sb.reverse().toString());  
                if(sb.toString().equals(name) || sb.reverse().toString().equals(name)) return true;               
            }  
            return false;  
        }  
        public char[] toCharArray(){return name.toCharArray();}  
        @Override  
        public String toString(){return name;}  
    }  
      
    public class Node{  
        public Set cls = new TreeSet();  
        public float value = -1;  
        public List childNodes = new LinkedList();  
          
        public Node(Character ch){cls.add(ch);}  
        public Node(float value) {this.value = value;}  
        public Node(float value, Character ch)  
        {  
            this(value); cls.add(ch);  
        }  
          
        public void addChildNode(Node n){cls.addAll(n.cls); childNodes.add(n);}  
          
        public int validate(PairClr pc)  
        {  
            char chs[] = pc.name.toCharArray();  
            if(cls.contains(chs[0]) && !cls.contains(chs[1]))  
            {  
                return chs[1]; /*Has one*/  
            }  
            else if(cls.contains(chs[1]) && !cls.contains(chs[0]))  
            {  
                return chs[0]; /*Has one*/  
            }  
            else if(cls.contains(chs[0]) && cls.contains(chs[1]))  
            {  
                return 0; /*Has two*/  
            }  
            else  
            {  
                return -1; /*Has none*/  
            }  
        }  
          
        @Override  
        public String toString(){  
              
            StringBuffer sb = new StringBuffer("");  
            for(Character ch:cls) sb.append(String.valueOf(ch));  
            return sb.toString();  
        }  
    }  
      
    class PCComparator implements Comparator{  
        @Override  
        public int compare(PairClr o1, PairClr o2) {  
            if(o1.sim> o2.sim) return -1;  
            else if(o1.sim< o2.sim) return 1;  
            else return 0;  
        }         
    }  
      
    protected void _showTree(Node n)  
    {  
        if(n.childNodes.size()==0) System.out.printf("\t[SingleLink] Node=%s is leaf node.\n", n);  
        else  
        {  
            for(Node cn:n.childNodes)  
            {  
                System.out.printf("\t[SingleLink] Node=%s(%f) has child node=%s...\n", n, n.value, cn);  
            }  
            for(Node cn:n.childNodes)  
            {  
                _showTree(cn);  
            }  
        }  
    }  
      
    public void showTree()  
    {  
        if(root!=null)  
        {  
            _showTree(root);  
        }  
        else  
        {  
            System.out.printf("\t[SingleLink] root is null!\n");  
        }  
    }  
      
    public static void main(String[] args) {      
        // Initialize CompleteLink  
        CompleteLink link = new CompleteLink();  
        link.addPairCluster("AF", (float)0.9);  
        link.addPairCluster("AE", (float)0.8);  
        link.addPairCluster("AD", (float)0.6);  
        link.addPairCluster("AC", (float)0.5);  
        link.addPairCluster("AB", (float)0.3);  
        link.addPairCluster("BF", (float)0.8);  
        link.addPairCluster("BE", (float)0.7);  
        link.addPairCluster("BD", (float)0.5);  
        link.addPairCluster("BC", (float)0.4);  
        link.addPairCluster("CE", (float)0.5);  
        link.addPairCluster("CD", (float)0.3);  
        link.addPairCluster("CF", (float)0.2);  
        link.addPairCluster("DE", (float)0.4);  
        link.addPairCluster("DF", (float)0.1);  
        link.addPairCluster("EF", (float)0.3);  
          
        // Compute Hierarchy Clustering  
        link.compute();  
          
        // Show Hierarchy Tree.  
        link.showTree();  
    }  
}  

執行結果如下 :

補充說明 :
* [ Java Essence ] 記憶中的那個東西 : 要怎麼參考呢 (物件相等性)
* JDK 6.0 > java.util.PriorityQueue

使用在儲存 Cluster Pair, 讓我們可以由較高的 Similarity 依序取出 Cluster Pair 進行處理...

程式扎記

標籤

2012年5月26日星期六

[ Algorithm ] Hierarchy Clustering : Complete-link

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2012年5月26日 星期六