本節書摘來自華章計算機《mahout算法解析與案例實戰》一書中的第3章，第3.1節,作者：樊 哲，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
3.1.1 canopy算法簡介
在生活中，我們可以使用聚類解決很多問題，就像本章開始提到的幾個例子一樣。傳統的聚類算法對于一般的應用問題（基本都是小資料量）都是可以解決的，但是當資料變得很大的時候，就有點“力不從心”了。這裡的資料變得很大指的是：①資料的條目很多，整個資料集包含的樣本資料向量很多；②針對①中的每個樣本資料向量其次元很大，即包含多個屬性；③要聚類的中心向量很多。當我們所要應用聚類算法的資料是上面所述情況時，傳統的聚類方法應用起來就會相當棘手，這時就要采取另外的途徑，即改進的聚類算法。本節介紹的canopy算法就是聚類算法發展到一定階段，andrew mccallum、kamal nigam、lyle h.ungar根據前人經驗加上自己的想法提出來的一種改進算法。
canopy算法的主要思想是把聚類分為兩個階段：階段一，通過使用一個簡單、快捷的距離計算方法把資料分為可重疊的子集，稱為“canopy”；階段二，通過使用一個精準、嚴密的距離計算方法來計算出現在階段一中同一個canopy的所有資料向量的距離。這種方式和之前的聚類方式不同的地方在于使用了兩種距離計算方式，同時因為隻計算了重疊部分的資料向量，是以達到了減少計算量的目的。
具體來說，階段一，使用一個簡單距離計算方法來産生具有一定數量的可重疊的子集。canopy就是一個樣本資料集的子集，子集中的樣本資料是通過一個粗糙的距離計算方法來計算樣本資料向量和canopy的中心向量的距離，設定一個距離門檻值，當計算的距離小于這個門檻值的時候，就把樣本資料向量歸為此canopy。這裡要說明的是，每個樣本資料向量有可能存在于多個canopy裡面，但是每個樣本資料向量至少要包含于一個canopy中。canopy的建立基于不存在于同一個canopy中的樣本資料向量彼此很不相似，不能被分為同一個類的這樣的觀點考慮的。由于距離計算方式是粗糙的，是以不能夠保證性能（計算精确度）。但是通過允許存在可疊加的canopy和設定一個較大的距離門檻值，在某些情況下可以保證該算法的性能。
圖3?1是一個canopy的例子，其中包含5個資料中心向量。
圖3?1 canopy聚類圖
圖3-1中資料向量用同樣灰階值表示的屬于同一個聚類。聚類中心向量a被随機選出，然後以a資料向量建立一個canopy，這個canopy包括所有在其外圈（實線圈）的資料向量，而内圈（虛線）中的資料向量則不再作為中心向量的候選名單。
那麼針對一個具體的canopy應該如何建立呢？下面介紹建立一個普通的canopy算法的步驟。
1）原始資料集合list按照一定的規則進行排序（這個規則是任意的，但是一旦确定就不再更改），初始距離門檻值為t1、t2，且t1 ＞ t2（t1、t2的設定可以根據使用者的需要，或者使用交叉驗證獲得）。
2）在list中随機挑選一個資料向量a，使用一個粗糙距離計算方式計算a與list中其他樣本資料向量之間的距離d。
3）根據第2步中的距離d，把d小于t1的樣本資料向量劃到一個canopy中，同時把d小于t2的樣本資料向量從候選中心向量名單（這裡可以了解為就是list）中移除。
4）重複第2、3步，直到候選中心向量名單為空，即list為空，算法結束。
圖3?2為建立canopy算法的流程圖。
階段二，可以在階段一的基礎上應用傳統聚類算法，比如貪婪凝聚聚類算法、k均值聚類算法，當然，這些算法使用的距離計算方式是精準的距離計算方式。但是因為隻計算了同一個canopy中的資料向量之間的距離，而沒有計算不在同一個canopy的資料向量之間的距離，是以假設它們之間的距離為無窮大。例如，若所有的資料都簡單歸入同一個canopy，那麼階段二的聚類就會退化成傳統的具有高計算量的聚類算法了。但是，如果canopy不是那麼大，且它們之間的重疊不是很多，那麼代價很大的距離計算就會減少，同時用于分類的大量計算也可以省去。進一步來說，如果把canopy算法加入到傳統的聚類算法中，那麼算法既可以保證性能，即精确度，又可以增加計算效率，即減少計算時間。
canopy算法的優勢在于可以通過第一階段的粗糙距離計算方法把資料劃入不同的可重疊的子集中，然後隻計算在同一個重疊子集中的樣本資料向量來減少對于需要距離計算的樣本數量。
3.1.2 mahout中canopy算法實作原理
在mahout中，canopy算法用于文本的分類。實作canopy算法包含三個mr，即三個job，可以描述為下面4個步驟。
1）job1：将輸入資料處理為canopy算法可以使用的輸入格式。
2）job2：每個mapper針對自己的輸入執行canopy聚類，輸出每個canopy的中心向量。
3）job2：每個reducer接收mapper的中心向量，并加以整合以計算最後的canopy的中心向量。
4）job3：根據job2的中心向量來對原始資料進行分類。
其中，job1和job3屬于基礎操作，這裡不再進行詳細分析，而主要對job2的資料流程加以簡要分析，即隻對canopy算法的原理進行分析。
首先來看圖3?3，可以根據這個圖來了解job2的map/reduce過程。
圖3?3 canopy的map/reduce過程圖
圖3-3中的輸入資料可以産生兩個mapper和一個reducer。每個mapper處理其相應的資料，在這裡處理的意思是使用canopy算法來對所有的資料進行周遊，得到canopy。具體如下：首先随機取出一個樣本向量作為一個canopy的中心向量，然後周遊樣本資料向量集，若樣本資料向量和随機樣本向量的距離小于t1，則把該樣本資料向量歸入此canopy中，若距離小于t2，則把該樣本資料從原始樣本資料向量集中去除，直到整個樣本資料向量集為空為止，輸出所有的canopy的中心向量。reducer調用reduce過程處理map過程的輸出，即整合所有map過程産生的canopy的中心向量，生成新的canopy的中心向量，即最終的結果。
3.1.3 mahout的canopy算法實戰
1．輸入資料
$hadoop_home/bin/hadoop fs –copyfromlocal /home/mahout/mahout_data/synthetic_control.data input/synthetic_control.data
上傳後在檔案系統監控界面檢視此檔案，如圖3?4所示。
圖3?4 synthetic_control.data檔案
這裡隻針對job2的任務進行實戰：job2的輸入要求使用的資料是序列化的，同時要求輸入資料要按照一定的格式，是以，編寫代碼清單3?1對原始資料進行處理。
代碼清單 3?1 原始資料處理代碼
把上面的代碼編譯打包成clusteringutils.jar并放入/home/mahout/mahout_jar目錄下，然後在hadoop根目錄下運作下面的指令：
指令運作成功後可以在檔案監控系統檢視轉換後的輸入資料，如圖3?5所示。
圖3?5 轉換後的輸入資料
由圖3-5方框中的内容可以看出，資料已經被轉換為vectorwritable的序列檔案了。經過上面的步驟，輸入資料的準備工作就完成了。
提
示 在hadoop中運作編譯打包好的jar程式，可能會報下面的錯誤：
exception in thread "main" java.lang.noclassdeffounderror:
org/apache/mahout/common/abstractjob
這時需要把mahout根目錄下的相應的jar包複制到hadoop根目錄下的lib檔案夾下，同時重新開機hadoop即可。
2．參數意義
canopy算法在mahout中的使用方式如下：
其中[]包含的兩個參數是可選的，下面具體介紹一下。
generic options參數選項如下：
-archives ：在叢集中被解壓的壓縮檔案選項，以逗号隔開每個壓縮檔案。
-conf ：應用所需要的配置檔案選項。
-d ：為特定的變量指派的選項。
-files ：在叢集中使用到的檔案選項，以逗号隔開每個檔案。
-fs ：選擇namenode的選項。
-jt ：選擇job tracker 的選項。
-libjars ：需要被包含到classpath中的jar檔案選項，逗号隔開每個jar檔案。
-tokencachefile ：設定符号的檔案選項。
job-specific options參數選項如下：
--input (-i ) input：任務的輸入檔案選項，必選。
--output (-o) output：任務的輸出檔案的選項，必選。
--distancemeasure (-dm) distancemeasure：距離計算的類名稱，預設為square-euclidean，即歐氏距離平方，可選。
--t1 (-t1) t1：t1門檻值，可選。
--t2 (-t2) t2：t2門檻值，可選。
--t3 (-t3) t3：reducer中用到的t1門檻值，可選。
--t4 (-t4) t4：reducer中用到的t2門檻值，可選。
--clusterfilter (-cf,-clusterfilter) clusterfilter：限制mapper中比較小的canopies産生，可選。
--overwrite (-ow)：如果出現，則對輸出路徑進行重寫，可選。
--clustering (-cl)：如果出現，則對資料進行分類，可選。
--method (-xm) method：選擇使用的計算方式，單機或叢集，預設為叢集，可選。
--outlierthreshold (-outlierthreshold) outlierthreshold：異常值門檻值，可選。
--help (-h)：列印此參數幫助資訊，可選。
--tempdir tempdir：臨時檔案所存放的地方，可選。
--startphase startphase：開始要運作算法的階段，可選。
--endphase endphase：最後要運作算法的階段，可選。
3．運作
進入mahout的根目錄下，運作下面的指令：
其中輸入檔案使用的是轉換後的序列檔案；距離計算方式使用的是歐式距離；t1和t3設定為80，t2和t4設定為55；--clustering選項表示最後對原始資料進行分類。
4．結果分析
運作上面的指令後，可以在終端中檢視到圖3?6所示的輸出資訊（隻列出了部分資訊）。
圖3?6 canopy算法終端輸出資訊
在圖3-6的方框中可以看到輸入有600條記錄，map的輸出有25條記錄，即map産生了25個canopy，然後reduce接收了全部25個canopy，輸出6個canopy，符合原始資料的6個類。
在檔案監控系統可以看到運作本次算法産生的檔案，如圖3?7所示。
圖3?7 canopy算法産生檔案
由圖3-7可以看出，clusteredpoints中是已經分好的類，clusters-0-final中存儲的是最後的reduce輸出，即6個中心向量。由于上面的檔案同樣是序列檔案，是以要把上面的檔案轉換為文本，友善使用者檢視。
首先檢視中心向量的序列檔案，可以看到其類名稱（要根據此類名稱進行轉換），如圖3?8所示。
圖3?8 中心向量序列檔案
可以看到其輸出類名為clusterwritable，編寫下面的代碼清單 3?2。
代碼清單3?2 轉換canopy聚類中心向量代碼
把上面的代碼編譯打包放入/home/mahout/mahout_jar目錄下，運作下面的指令：
在檔案監控系統可以檢視到轉換後的聚類中心點，如圖3?9所示。
圖3?9 canopy聚類中心轉換後的結果
3.1.4 canopy算法小結
本節通過分析canopy算法的應用背景、算法原理以及在mahout中的實作、實戰，可以讓讀者對canopy算法有一個更加深入的了解，同時對在mahout中如何使用該算法來解決實際問題提供了參考。本節所給出的兩個代碼清單：代碼清單3-1和代碼清單 3?2，具有一定的通用性，涉及檔案在序列檔案和文本檔案之間的轉換，在本章的其他小節還會用到。