機器學習_學習筆記系列(86)：利用層次方法的平衡迭代規約和聚類(Balanced Iterative Reducing and Clustering using Hierarchies)
前兩回我們見紹了兩個重要的Clustering 演算法DBSCAN和OPTICS。而今我們要繼續延續clustering主題，介紹新的演算法「BIRCH」
Balanced Iterative Reducing and Clustering using Hierarchies
對於這個演算法其縮寫就是上面所提到的BIRCH(看吧！把演算法縮寫還可以成為一個單字才跟得上ML潮流)。
對於BIRCH其是由U of Wisconsin的Tian Zhang、Raghu Ramakrishnan和Miron Livny所提出。其論文名稱叫做
BIRCH: An Efficient Data Clustering Method for Very Large Databases
而我們可以從論文名稱和BIRCH全名看到
其演算法最主要是解決大數據中clustering的問題，而BIRCH所用的屬於hierarchical的概念，透過建構Clustering Feature Tree對每個clusters來儲存小量的資料達到動態更新cluster的功能。
Clustering Feature Tree
對於CF Tree這種資料結構，其node主要儲存三個資訊
第一個為node為底下所有資料的數量N
第二個為node底下所有資料的linear sum(LS)，也就是所有資料的全部加總
第三個為node底下所有資料的square sum(SS)，也就是所有資料平方的全部加總。
我們可以看到利用上述的方法，若我們要合併兩個cluster，對於合併後的N、LS、SS只要將兩邊相加就可以。
CF Tree 建立
而對於CF Tree的建構流程，我們會在一開始規範我們CF Tree中
每個node的分支數量，以及一個Radius Neighbor半徑
然後以下面的的例子，我們設我們的分支數量限制為2。
在第一回中，我們輸入我們的第一筆資料A，所以我們就在root底下建立一個CF Node然後把A點放進去。
第二回當中，我們輸入資料B，而我們發現B和A的距離小於我們設定的Radius Neighbor半徑，所以B可以直接放在CF Node 1底下。
在第三回中，我們加入C點，而我們發現C點離A點的距離大於Radius Neighbor半徑，所以我們就在root底下接一個CF Node 2把C點放進去。
在第四回中，加入D點，但是D點離A點的距離和C點的距離都大於Radius Neighbor半徑，而且root底下的分支已經兩個了，不能直接加入CF Node 3。所以在這裡我們必須將CF Node做「split」，在這裡我們就會比較原本上一張圖當中，CF Node 1(包含A和B)、CF Node 2(包含C)，和新加入的CF Node(包含D)，哪兩個CF Node的centroid相差最遠。
而在這個例子中，我們發現CF Node 1和CF Node 2的centroid相差最遠，所以我們就把我們的tree多長一層出來，原本的CF Node 1放左邊變成CF Node 1–1，而原本的CF Node 2放右邊變成CF Node 2–1。而最後新加入的CF Node(包含D)，我們就看他的centroid離現在的CF Node 1–1還是CF Node 2–1比較近，而這個例子是離CF Node 1–1比較近，所以我們把新加入的CF Node加到現在的CF Node 1底下。
在第五回中，加入E點，我們發現他離CF Node 1比較近，但是E點到A點和D點的距離都大於Radius Neighbor半徑，且CF Node 1底下已經有兩個CF Node了，所以必須再split。
所以現在我們看原本的CF Node 1–1(包含A和B)、CF Node 1–2(包含D)，以及新的CF Node(包含E)，哪兩個CF Node距離最遠。而在這個例子我們發現CF Node 1–1(包含A和B)和CF Node 1–2(包含D)的centroid相差最遠，而E點離CD Node 1–2最近，所以我們現在總共有三個Node連在root底下，一個為CF Node A底下連著CF Node 1–1、一個為CF Node B底下連CF Node 1–2和包含E的CF Node，而最後一個就是剛剛沒碰到過的CF Node 2。
但是顯然root底下三個Node違反規則，所以我們必須要再split，所以這裡我看CF Node A、CF Node B和CF Node 2哪兩個的centroid相差最遠，而這裡我們發現CF Node A和CF Node B相差最遠，所以我們把兩個Node獨立分開，上層各自加上一層CF Node 1(連結CF Noda A=CF Node 1–1)和CF Node 2(連接CF Node CF Node 2–1)，而剩下原本的CF Node 2(包含C)其離CF Node A也就是CF Node 1–1比較近，所以舊的CF Node 2就安插在CF Node 1底下名稱更改為CF Node 1–2。
Algorithms
對於演算法的流程和步驟，大部分在網路上都是看到，隨便丟個理論，然後sample code也只是form sklearn.#%&* import &*#$@。基本上沒有講解如何實現演算法
所以在這裡我們直接研究sklearn Birch的開源程式碼，讓大家能夠清楚了解，整個流程。
P.S. 以下的演算法非原本sklearn原始碼，其是有經過我簡化改編的！
首先對於Birch，我們剛開始會設定三個參數
threshold：Radius Neighbor半徑大小
branching factor：node底下分支的數量限制
n_clusters，我們最後想要幾個cluster。
而在接下來的步驟我們會從葉子端開始建立我們的整個CF Tree，所以我們一開始會執行以下code
第一行和第二行代表的就是我們會先建立我們的CF Node，而因為我們是從底層的樹葉建立到樹的根，所以這個CF Node就是樹的葉子(is_leaf=Ture)。而第三行和第四行的意思就是指，我們把root當作，dummy leaf的下一片葉子，反過來說就是，root的前一片葉子就是dummy_leaf。
而接下我們來看之後我們會用到的兩個class：CF_Node和CF_Subcluster。
CF_Node:
對於CF_Node我們可以看到，多了以下參數，分別是
CF Node底下的子群(subclusters)
CF Node底下每個分支中每個feature的中心點(init_centroids)
CF Node底下每個分支的泛數平方(init_sq_norm)。
P.S. subclusters底下有數個subcluster，
append_subcluster
對於這個方程式，我們做的事情就是把輸入的subcluster加入CF Node的subclusters群中，然後我們會把這個subcluster的資訊，像是中心點(centroid)和泛數平方(sq_norm)，也存入這個CF_Node底下。
update_split_subclusters
對於這個方程式，最主要做的事情就是當我們做split的時候更新我們的subclusters，而這裡的subcluster代表舊的subcluster。
insert_cf_subcluster
而這個方程式，就是把我們的subcluster加入到subclusters中。而前面if所代表的就是，如果CF Node底下沒有任何subcluster的話，就直接加進subclusters。
而在接下來的code中，我們可以看到其計算了dist_matrix，也就是subcluster的centroid和當前SF Node底下所有subcluster centroid的距離，不過在這邊其使用的並不是直接計算歐幾里得距離，而是使用similarity，然後把離輸入的subcluster最近的subcluster標記為closest subcluster。
OK當我們確定好closest subcluster後，我們會先檢查其底下是否還有其他的subcluster，如果有我們就繼續往下找，然後看其closest subcluster是否底下還有subcluster，就這樣以遞迴的方式重複上述步驟直到我們達到樹的末端，即底下沒有cluster了。即最後一次遞迴時closest_subcluster.child =None
所以當closest_subcluster.child =None，我們現在會跳到else的區塊執行，我們可以看到剛開始他會執行merge_subcluster(底下會介紹)，把closest subcluster和subclusterg嘗試合併起來，如果他們subcluster centroid到closest subcluster centroid的距離還是大於我們定義的threshold，代表其超出範圍merged=False，若小於則merged=True。
而merged=True代表我們可以直接把這個subcluster加到closest_subcluster中，並更新init_centroids、init_sq_norm和回傳False。
另外還有一種情況就是merged=False，但是我們這個CF Node底下的分支數量還沒超過branching factor那我們可以直接把他加進這個CF Node底下，並回傳False。
而最後的情況就是當前的Node底下已經不能再加入任何subcluster，我們必須把現有的subcluster分開來放入這筆subcluster，所以這裡回傳True代表需要split，我們就會回到遞迴的上一層。
現在我們回到當初這邊，如果
split_child=False
代表我們不需要split，我們已經確定要把新的subcluster加到closest_subcluster底下，所以這裡就會直接執行update方程式更新closest_subcluster，也就是把這筆新的subcluster加入，然後把init_centroid和init_sq_norm也一起更新，最後回傳False。
OK如果接下來我們又回到上一層insert_cf_cluster，所以這裡的split_childu也等於False，我們又會做一樣的事情把每一層的closest_subcluster、init_centroid和init_sq_norm更新過一遍。然後這個步驟會執行到我們的遞迴回到最一剛開始呼叫的那一層停止。
但是如很不幸的CF Node底下的分支滿了，需要拆開subcluster，我們就會執行split_node把它拆成new_subcluster1和new_subcluster2，並執行update_split_subcluster把這兩個新的subcluster加進去。
而在這裡如果我們最後把這兩個subcluster加進去後，小於我們的branching factor，也就是CF Node底下的還能夠放，就會回傳False，然後回到遞迴上一層厚就會到if的條件判斷式，執行update了。
但如果把兩個新的subcluster放進去還是超出branching factor，我們就會回傳Ture並回到上一層遞迴中，把上面一層的closest_subcluster底下的subcluster拆成兩組new_subcluster，而這個步驟回執行到我們的CF Node底下的subcluster數量不超過branching factor。
CF Subcluster
OK接下來我們要來講還沒提到的CF Subcluster
對於他的初始參數，我們可以看到其儲存了subcluster裡面資料的數量、中心點和總和平方。並將其child設為None，所以這邊所代表的就是樹最底層也就是葉片的CF Subcluster。
update
而在update這個方程式，他做的事情就和我們上面所說的合併方法概念相同。
merge_subcluster
而merge_subcluster方程式，他做的事情就是確認我們想要合併的subcluster，合併之後，subcluster的半徑是否小於threshold，如果小於的話就回傳true，並更新所有subcluster的參數(n_samples、linear_sum等等)。如果大於threshold則回傳False代表沒辦法合併。
split_node
在前面的地方我們也提到split node方程式，也就是拆成兩個subcluster的方程式。我們可以看到以下code
他一開始所做的事情就是先建立兩個CF Subcluster，和兩個CF Node。並把CF Node接到CF Subcluster底下。這個動作就像我們上面理論部分講的，把整個tree多加一層。
如果原本的這個CF Node本來就是葉子，我們會我們就把新的兩個node從中間串接起來。
接下來我們要做的事情就是現計算node底下每個分支的centroid互相的距離，然後取距離差最遠的index為farthest_idx。而這裡farthest_indx會有兩個值，其代表距離最遠的兩個centorid的index。
所以現在我們有了這兩個index，就是把subclusters裡面的cluster全部跑一遍，看誰離哪一個subcluster比較近，就放到哪個cluster中，最後就回傳我們兩個新的subcluster。
所以現在回到BIRCH
我們會進入for迴圈，把所有X的資料點跑過一次，也就是我們的sample會隨著迴圈等於X[0]、X[1]、X[2]…..。
接下來就是創建我們的CF Subcluster，然後我們可以看到他做的事情就是把剛剛創建的CF Subcluster加入到我們創建的root底下，而上面我們提到過有可能會出現所謂的超過threshold和branching factor的問題。所以insert_cf_subcluster會確認有沒有出現上述問題，如果有的話，我們就必須把原本的cluster重新分開。
所以接下來我們可以看到如果需要分開，我們就會進入if底下的code，然後我們可以看到split_node會把原本root底下的subcluster分成兩個subcluster，然後再把原本的root刪掉，創建一個新的CF Node，把這兩個cluster加進去裡面。
最後我們做的事情，就是把所有的leaf的centroid連接起來，放到subcluster的centers中，並計算X的gobale_clustering。
而這邊get_leave的意思就像linked-list的概念，把所有葉片串接在一起，leaf_ptr就代表指標，其會指向像一片葉片，所以我們在while迴圈做的事情，就是把所有的葉片串接起來回傳。
global clustering做的事情，就是我們會把subcluster_centers(每片葉子的centroid)丟進Ward Agglomerative Clustering運算，得到我們初步的subcluster_labels。
最後我們就是預測我們資料的類別，這裡我們就把每筆資料離他最近距離的資料編號，帶入剛剛的suncluster_labels，就可以得到我們的BIRCH預測的結果。
Example
接下來我們看BIRCH在MNIST的表現
我們可以看到其表現相當的不錯，所以對於BIRCH其很常拿來用在大數據分析中的clustering。
Python Sample Code:
Github:
Reference:
[1] Zhang, T., Ramakrishnan, R., & Livny, M. (1996). BIRCH: an efficient data clustering method for very large databases. ACM sigmod record, 25(2), 103–114.
[2] Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825–2830, 2011.
