Change Dir

          先知cd——熱愛(ài)生活是一切藝術(shù)的開(kāi)始

          統(tǒng)計(jì)

          留言簿(18)

          積分與排名

          “牛”們的博客

          各個(gè)公司技術(shù)

          我的鏈接

          淘寶技術(shù)

          閱讀排行榜

          評(píng)論排行榜

          聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)

           

          1.    層次聚類(lèi)

          層次聚類(lèi)算法與之前所講的順序聚類(lèi)有很大不同,它不再產(chǎn)生單一聚類(lèi),而是產(chǎn)生一個(gè)聚類(lèi)層次。說(shuō)白了就是一棵層次樹(shù)。介紹層次聚類(lèi)之前,要先介紹一個(gè)概念——嵌套聚類(lèi)。講的簡(jiǎn)單點(diǎn),聚類(lèi)的嵌套與程序的嵌套一樣,一個(gè)聚類(lèi)中R1包含了另一個(gè)R2,那這就是R2嵌套在R1中,或者說(shuō)是R1嵌套了R2。具體說(shuō)怎么算嵌套呢?聚類(lèi)R1={{x1,x2},{x3},{x4,x5}嵌套在聚類(lèi)R2={{x1,x2,x3},{x4,x5}}中,但并不嵌套在聚類(lèi)R3={{x1,x4},{x3},{x2,x5}}中。

          層次聚類(lèi)算法產(chǎn)生一個(gè)嵌套聚類(lèi)的層次,算法最多包含N步,在第t步,執(zhí)行的操作就是在前t-1步的聚類(lèi)基礎(chǔ)上生成新聚類(lèi)。主要有合并和分裂兩種實(shí)現(xiàn)。我這里只講合并,因?yàn)榍耙浑A段正好課題用到,另外就是合并更容易理解和實(shí)現(xiàn)。當(dāng)然分裂其實(shí)就是合并的相反過(guò)程。

          g(Ci,Cj)為所有可能的X聚類(lèi)對(duì)的函數(shù),此函數(shù)用于測(cè)量?jī)蓚€(gè)聚類(lèi)之間的近鄰性,用t表示當(dāng)前聚類(lèi)的層次級(jí)別。通用合并算法的偽碼描述如下:

          1.       初始化:

          a)         選擇Â0={{x1},…,{xN}}

          b)        t=0

          2.       重復(fù)執(zhí)行以下步驟:

          a)         t=t+1

          b)        Ât-1中選擇一組(Ci,Cj),滿(mǎn)足

          c)         定義Cq=CiÈCj,并且產(chǎn)生新聚類(lèi)Ât=(Ât-1-{Ci,Cj})È{Cq}

          直到所有向量全被加入到單一聚類(lèi)中。

                 這一方法在t層時(shí)將兩個(gè)向量合并,那么這兩個(gè)向量在以后的聚類(lèi)過(guò)程中的后繼聚類(lèi)都是相同的,也就是說(shuō)一旦它們走到一起,那么以后就不會(huì)再分離……(很專(zhuān)一哦O(_)O~)。這也就引出了這個(gè)算法的缺點(diǎn),當(dāng)在算法開(kāi)始階段,若出現(xiàn)聚類(lèi)錯(cuò)誤,那么這種錯(cuò)誤將一直會(huì)被延續(xù),無(wú)法修改。在層次t上,有N-t個(gè)聚類(lèi),為了確定t+1層上要合并的聚類(lèi)對(duì),必須考慮(N-t)(N-t-1)/2個(gè)聚類(lèi)對(duì)。這樣,聚類(lèi)過(guò)程總共要考慮的聚類(lèi)對(duì)數(shù)量就是(N-1)N(N+1)/6,也就是說(shuō)整個(gè)算法的時(shí)間復(fù)雜度是O(N3)

          舉例來(lái)說(shuō),如果令X={x1, x2, x3, x4, x5},其中x1=[1, 1]T, x2=[2, 1]T, x3=[5, 4]T, x4=[6, 5]T, x5=[6.5, 6]T。那么合并算法執(zhí)行的過(guò)程可以用下面的圖來(lái)表示。

                        P(X)是不相似矩陣

          該算法從核心過(guò)程上來(lái)講,就是先計(jì)算出數(shù)據(jù)集中向量之間的距離,記為距離矩陣(也叫不相似矩陣)。接著通過(guò)不斷的對(duì)矩陣更新,完成聚類(lèi)。矩陣更新算法的偽碼描述如下:

          1.       初始化:

          a)         Â0={{x1},…,{xN}}

          b)        P0=P(X) (距離矩陣)

          c)         t=0

          2.       重復(fù)執(zhí)行以下步驟:

          a)         t=t+1

          b)        合并CiCjCq,這兩個(gè)聚類(lèi)滿(mǎn)足d(Ci,Cj)=minr,s=1,…,N,rsd(Cr,Cs)

          c)         刪除第ij行,第ij列,同時(shí)插入新的行和列,新的行列為新合并的類(lèi)Cq與所有其他聚類(lèi)之間的距離值

          直到將所有向量合并到一個(gè)聚類(lèi)中

                 大家可以看到,層次聚類(lèi)算法的輸出結(jié)果總是一個(gè)聚類(lèi),這往往不是我們想要的,我們總希望算法在得到我們期望的結(jié)果后就停止。那么我們?nèi)绾慰刂颇兀砍S玫淖龇ň褪菫樗惴ㄏ拗埔粋€(gè)閾值,矩陣更新過(guò)程中,總是將兩個(gè)距離最近的聚類(lèi)合并,那么我們只要加入一個(gè)閾值判斷,當(dāng)這個(gè)距離大于閾值時(shí),就說(shuō)明不需要再合并了,此時(shí)算法結(jié)束。這樣的閾值引入可以很好的控制算法結(jié)束時(shí)間,將層次截?cái)嘣谀骋粚由稀?/span>

          2. 算法實(shí)現(xiàn)

                 MATLAB實(shí)現(xiàn)了層次聚類(lèi)算法,基本語(yǔ)句如下:

          1= [1 2;2.5 4.5;2 2;4 1.5;4 2.5] ;
          2= pdist(X,'euclid'); 
          3= linkage(Y,'single'); 
          4= cluster(Z,'cutoff',cutoff);


          MATLAB還有一個(gè)簡(jiǎn)化的層次聚類(lèi)版本,一句話搞定

          1= clusterdata(X,cutoff)

           

          Java實(shí)現(xiàn)的版本:

           

            1package util;
            2
            3import java.util.*;
            4
            5public class Clusterer {
            6    private List[] clusterList;
            7    DisjointSets ds;
            8    private static final int MAX = Integer.MAX_VALUE;
            9    private int n;
           10    private int cc;
           11
           12    // private double ori[] = {1,2,5,7,9,10};
           13
           14    public Clusterer(int num) {
           15        ds = new DisjointSets(num);
           16        n = num;
           17        cc = n;
           18        clusterList = new ArrayList[num];
           19        for (int i = 0; i < n; i++)
           20            clusterList[i] = new ArrayList();
           21    }

           22
           23    public List[] getClusterList() {
           24        return clusterList;
           25    }

           26
           27    public void setClusterList(List[] clusterList) {
           28        this.clusterList = clusterList;
           29    }

           30
           31    public void output() {
           32        int ind = 1;
           33        for (int i = 0; i < n; i++{
           34            clusterList[ds.find(i)].add(i);
           35        }

           36        for (int i = 0; i < n; i++{
           37            if (clusterList[i].size() != 0{
           38                System.out.print("cluster " + ind + " :");
           39                for (int j = 0; j < clusterList[i].size(); j++{
           40                    System.out.print(clusterList[i].get(j) + " ");
           41                }

           42                System.out.println();
           43                ind++;
           44            }

           45        }

           46    }

           47
           48    /**
           49     * this method provides a hierachical way for clustering data.
           50     * 
           51     * @param r
           52     *            denote the distance matrix
           53     * @param n
           54     *            denote the sample num(distance matrix's row number)
           55     * @param dis
           56     *            denote the threshold to stop clustering
           57     */

           58    public void cluster(double[][] r, int n, double dis) {
           59        int mx = 0, my = 0;
           60        double vmin = MAX;
           61        for (int i = 0; i < n; i++// 尋找最小距離所在的行列
           62            for (int j = 0; j < n; j++{
           63                if (j > i) {
           64                    if (vmin > r[i][j]) {
           65                        vmin = r[i][j];
           66                        mx = i;
           67                        my = j;
           68                    }

           69                }

           70            }

           71        }

           72        if (vmin > dis) {
           73            return;
           74        }

           75        ds.union(ds.find(mx), ds.find(my)); // 將最小距離所在的行列實(shí)例聚類(lèi)合并
           76        double o1[] = r[mx];
           77        double o2[] = r[my];
           78        double v[] = new double[n];
           79        double vv[] = new double[n];
           80        for (int i = 0; i < n; i++{
           81            double tm = Math.min(o1[i], o2[i]);
           82            if (tm != 0)
           83                v[i] = tm;
           84            else
           85                v[i] = MAX;
           86            vv[i] = MAX;
           87        }

           88        r[mx] = v;
           89        r[my] = vv;
           90        for (int i = 0; i < n; i++// 更新距離矩陣
           91            r[i][mx] = v[i];
           92            r[i][my] = vv[i];
           93        }

           94        cluster(r, n, dis); // 繼續(xù)聚類(lèi),遞歸直至所有簇之間距離小于dis值
           95    }

           96
           97    /**
           98     * 
           99     * @param r
          100     * @param cnum
          101     *            denote the number of final clusters
          102     */

          103    public void cluster(double[][] r, int cnum) {
          104        /*if(cc< cnum)
          105            System.err.println("聚類(lèi)數(shù)大于實(shí)例數(shù)");*/

          106        while (cc > cnum) {// 繼續(xù)聚類(lèi),循環(huán)直至聚類(lèi)個(gè)數(shù)等于cnum
          107            int mx = 0, my = 0;
          108            double vmin = MAX;
          109            for (int i = 0; i < n; i++// 尋找最小距離所在的行列
          110                for (int j = 0; j < n; j++{
          111                    if (j > i) {
          112                        if (vmin > r[i][j]) {
          113                            vmin = r[i][j];
          114                            mx = i;
          115                            my = j;
          116                        }

          117                    }

          118                }

          119            }

          120            ds.union(ds.find(mx), ds.find(my)); // 將最小距離所在的行列實(shí)例聚類(lèi)合并
          121            double o1[] = r[mx];
          122            double o2[] = r[my];
          123            double v[] = new double[n];
          124            double vv[] = new double[n];
          125            for (int i = 0; i < n; i++{
          126                double tm = Math.min(o1[i], o2[i]);
          127                if (tm != 0)
          128                    v[i] = tm;
          129                else
          130                    v[i] = MAX;
          131                vv[i] = MAX;
          132            }

          133            r[mx] = v;
          134            r[my] = vv;
          135            for (int i = 0; i < n; i++// 更新距離矩陣
          136                r[i][mx] = v[i];
          137                r[i][my] = vv[i];
          138            }

          139            cc--;
          140        }

          141    }

          142
          143    public static void main(String args[]) {
          144        double[][] r = 014689 }103578 },
          145                430245 }652023 },
          146                874201 }985310 } }
          ;
          147        Clusterer cl = new Clusterer(6);
          148        //cl.cluster(r, 6, 1);
          149        cl.cluster(r, 3);
          150        cl.output();
          151    }

          152
          153}

          154


          3. 小結(jié)

                 層次聚類(lèi)算法是非常常用的聚類(lèi)算法,同時(shí)也是被廣泛研究的聚類(lèi)算法。層次聚類(lèi)本身分為合并和分裂兩種實(shí)現(xiàn),在合并算法中,又分基于矩陣?yán)碚摰暮喜⒑突趫D論的合并。本文只是初學(xué)聚類(lèi)的一點(diǎn)體會(huì),因此只實(shí)現(xiàn)了基于矩陣?yán)碚摰乃惴ǎ瑫r(shí),用于大數(shù)據(jù)集合的層次算法如CUREROCKChameleon算法都沒(méi)有涉及,這些算法如果以后有時(shí)間,會(huì)整理發(fā)布。還有截?cái)帱c(diǎn)的選擇,最佳聚類(lèi)數(shù)的確定都是可以研究的問(wèn)題。

          4. 參考文獻(xiàn)及推薦閱讀

          [1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas

          [2]模式識(shí)別第三版, Sergios Theodoridis, Konstantinos Koutroumbas, 李晶皎, 王愛(ài)俠, 張廣源等譯



          PS,第四第五節(jié)的內(nèi)容的代碼地址:

          http://www.kuaipan.cn/index.php?ac=fileview&dirid=50160446308614332


          posted on 2010-03-19 20:08 changedi 閱讀(13756) 評(píng)論(23)  編輯  收藏 所屬分類(lèi): 聚類(lèi)分析

          評(píng)論

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-03-20 10:40 路人甲

          哈哈,我這幾天也在學(xué)聚類(lèi),樓主的博客寫(xiě)的不錯(cuò)!  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-03-22 15:53 changedi

          @路人甲
          大家可以共同探討~~  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-04-22 00:00 劉賀

          你好,能給我發(fā)一份源碼嗎?拜托!hebeigeng@126.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-04-22 12:50 changedi

          @劉賀
          已發(fā)送,附帶并查集的實(shí)現(xiàn)。  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2010-05-02 10:35 緣來(lái)如此

          我現(xiàn)在正在學(xué)習(xí)聚類(lèi)算法,能發(fā)一份到我的郵箱嗎?謝謝。dowell_2008@live.cn  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-06-15 16:25 Meccas

          麻煩您可以發(fā)一份源碼給我嗎?我的郵箱是zhaozeyu1@yahoo.cn,最近在寫(xiě)聚類(lèi)算法的論文,但是苦于手中沒(méi)有源碼,看到您的文章,寫(xiě)的太好了。不知可以嗎?  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-06-21 18:50 王虎虎

          @changedi
          您好,請(qǐng)問(wèn)您可以給我發(fā)個(gè)完整的源碼么,您給出的這個(gè)代碼里面沒(méi)有DisjointSets類(lèi)的實(shí)現(xiàn),我自己想寫(xiě)出來(lái),可惜不行,呵呵,我擅長(zhǎng)c/c++,對(duì)java不很了解,哎,最近一直在研究層次聚類(lèi)算法,謝謝您!  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-06-21 18:54 王虎虎

          您好!
          能否給我發(fā)一份您完整的源代碼,您上面給出的那個(gè)代碼缺少DisjointSets類(lèi)的實(shí)現(xiàn),我自己補(bǔ)寫(xiě)了好幾天還是沒(méi)搞定,擺脫您了,我的郵箱是tjnuwanghu@163.com,
          tel:13752311612。
          謝謝您!  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-06-22 14:22 王虎虎

          @劉賀
          您好!
          您那有樓主給的層次聚類(lèi)的java實(shí)現(xiàn)代碼么?我也最近在做這方面的研究,生物信息方向的,我對(duì)java不是很了解,想看看,完了后轉(zhuǎn)成c++的。謝謝您啊!

          請(qǐng)您給我也發(fā)一份吧:
          Email:tjnuwanghu@163.com
          TEL:137+5231+1612
            回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-06-25 23:08 王虎虎

          @王虎虎
          package util;
          /**
          * 并查集簡(jiǎn)單實(shí)現(xiàn)
          * @author Jia Yu
          *
          */
          public class DisjointSets
          {
          public DisjointSets( int numElements )
          {
          s = new int [ numElements ];
          for( int i = 0; i < s.length; i++ )
          s[ i ] = -1;
          }

          public void union( int root1, int root2 )
          {
          assertIsRoot( root1 );
          assertIsRoot( root2 );
          if( root1 == root2 )
          throw new IllegalArgumentException( "Union: root1 == root2 " + root1 );

          if( s[ root2 ] < s[ root1 ] )
          s[ root1 ] = root2;
          else
          {
          if( s[ root1 ] == s[ root2 ] )
          s[ root1 ]--;
          s[ root2 ] = root1;
          }
          }

          public int find( int x )
          {
          assertIsItem( x );
          if( s[ x ] < 0 )
          return x;
          else
          return s[ x ] = find( s[ x ] );
          }

          private int [ ] s;


          private void assertIsRoot( int root )
          {
          assertIsItem( root );
          if( s[ root ] >= 0 )
          throw new IllegalArgumentException( "Union: " + root + " not a root" );
          }

          private void assertIsItem( int x )
          {
          if( x < 0 || x >= s.length )
          throw new IllegalArgumentException( "Disjoint sets: " + x + " not an item" );
          }

          }
            回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2010-07-06 07:46 馬雷

          劉賀,你好!
          您那有層次聚類(lèi)的java實(shí)現(xiàn)代碼嗎?我也最近在做這方面的學(xué)習(xí),請(qǐng)你給我發(fā)送一份吧,郵箱793125322@qq.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2011-08-09 13:32 jiajia

          樓主,您好。
          我也最近在做這方面的研究,對(duì)java不是很了解,方便發(fā)一份完整代碼么,謝謝。
          278164822@qq.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2011-10-03 15:31 www

          你好,最近剛學(xué)習(xí)聚類(lèi),能發(fā)送一份java源碼嗎?謝謝。wwwsd@live.cn  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2012-08-06 17:34 smallmood

          樓主,你好!層次聚類(lèi)總結(jié)的真好,最近在研究chameleon,想問(wèn)一下,有沒(méi)有關(guān)于chameleon的資料,如果有的話,能給我發(fā)一份嗎?算法、matlab實(shí)現(xiàn)等等都可以,謝啦!sjiezz@163.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2012-10-24 17:16 changedi

          我把代碼發(fā)鏈接出來(lái),需要的下載就好http://www.kuaipan.cn/index.php?ac=fileview&dirid=50160446308614332  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2012-12-10 21:09 香草可樂(lè)

          樓主,你寫(xiě)的好棒,你發(fā)布的那個(gè)連接沒(méi)有下載的文件喔,能發(fā)給我一份源代碼么,萬(wàn)分感謝!!420164881@qq.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2013-01-14 16:53 白樺林

          樓主你好 能給我發(fā)份完整的代碼嗎 感激不盡 1028122036@qq.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2013-01-14 16:54 白樺林

          對(duì)不起 郵箱寫(xiě)錯(cuò)了 是1028142036@qq.com  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2013-02-27 17:26 笑笑

          不知問(wèn)您一下 您的這個(gè)代碼可以進(jìn)行短文本聚類(lèi)嗎?或者是詞聚類(lèi)  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2013-02-27 17:50 笑笑

          你知道是否能對(duì)短文本聚類(lèi)呢?@香草可樂(lè)
            回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)[未登錄](méi) 2013-02-28 09:22 changedi

          當(dāng)然可以,詞匯作為空間節(jié)點(diǎn),詞匯相似度作為相似測(cè)度(節(jié)點(diǎn)距離)@笑笑
            回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2013-07-25 10:40 zack

          看了一下 這貨不是貪心么 跟哈弗曼樹(shù)差不多啊  回復(fù)  更多評(píng)論   

          # re: 聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi) 2013-10-22 17:27 歲月的帆

          貌似進(jìn)不去啊@changedi
          麻煩發(fā)給我郵件吧 872651253@qq.com 謝謝  回復(fù)  更多評(píng)論   

          主站蜘蛛池模板: 上虞市| 龙江县| 抚顺市| 桓台县| 宁远县| 类乌齐县| 固原市| 育儿| 龙游县| 寻乌县| 尤溪县| 丰镇市| 陈巴尔虎旗| 黄骅市| 巴楚县| 宜章县| 鄂尔多斯市| 新蔡县| 兴安盟| 东方市| 衡南县| 行唐县| 五指山市| 北票市| 邵东县| 三穗县| 江山市| 龙海市| 思南县| 东台市| 宣城市| 郓城县| 绿春县| 玉田县| 佛教| 旬阳县| 盐池县| 内黄县| 崇明县| 牡丹江市| 徐汇区|