canopy(關于python中canopy算法的簡介)

Canopy是一種對“大數據”進行聚類的算法。亦即當聚類問題滿足以下條件時,Canopy算法相比于其他算法會非常有效:

·類簇的個數很多

·樣本數很多

·樣本的維度很高

算法簡介

Canopy算法的主要思想是:首先使用一種簡單的距離度量方法來將所有樣本劃分成許多個canopy,然后再在各個canopy之內使用其他的聚類算法進行聚類。第一步可以大幅度降低需要進行比較的次數,因為第二步只需要在劃分好的canopy內進行樣本的亮亮比較。

1.創建canopy

在第一步中,會使用一個簡單的距離度量方法來將所有的樣本快速的劃分到多個canopy中去。每個canopy是樣本的一個子集,包含了一個中心點以及所有到這個中心點的距離小于一定閥值的點。一個樣本有可能屬于多個canopy。

創建canopy的意圖在于,如果兩個樣本不屬于一個公共的canopy,那么這兩個樣本不可能聚類在一起。為了滿足這種性質,可以允許canopy之間有重合(亦即一個樣本可以屬于多個canopy),可以設置一個大一點的閥值,等等。

canopy的創建過程為:設置兩個距離閥值T_1和T_2,并且T_1 > T_2,令所有樣本的集合為S。從S中取出一個樣本S_i,計算其到所有其他樣本的距離(使用一種簡單的距離度量方法),所有距離小于T_1的點構成一個新的canopy(包括S_i),然后把所有距離S_i的距離小于T_2的點從S中移除。重復以上步驟直至S為空。上述步驟中將距離S_i的距離小于T_2的點移除的用意是,這些點距離S_i太近了,沒有必要以這些點為中心再去構造canopy,因為這些canopy和以S_i為中心點的canopy非常相似。

2.簡單的距離度量方法

對于文本文檔,可以使用倒排索引來加快距離計算。如果想要找到所有和一個查詢比較相關的文章,則只需要先通過倒排索引找到那些包含查詢中的關鍵詞的文章。如果我們使用兩個文章共同包含的詞的個數作為簡單距離度量方法,則使用倒排索引會很高效。

倒排索引的思想也可以用在實數域的特征,每個特征離散化成多個桶,然后每個樣本就轉換成包含多個桶(亦即"關鍵詞")的"文檔",然后就可以使用倒排索引了,如果想避免邊緣效應(edge effect,亦即如果把[0,1]劃分成[0,0.5],[0.5, 1]兩個桶,雖然0.49和0.51非常接近,但是還是屬于不同的桶),可以可以通過記錄相鄰的桶來解決這個問題。