1005
技術社區[雲棲]
《Hadoop與大數據挖掘》一2.5.3 Hadoop K-Means算法實現思路
本節書摘來華章計算機《Hadoop與大數據挖掘》一書中的第2章 ，第2.5.3節，張良均 樊 哲 位文超 劉名軍 許國傑 周 龍 焦正升 著 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
2.5.3 Hadoop K-Means算法實現思路
針對K-Means算法，本節給出兩種實現思路。思路1相對比較直觀，但是效率較低；思路2在實現上需要自定義鍵值類型，但是效率較高。下麵是對兩種思路的介紹。
思路1
如圖2-47所示，算法描述如下：
1）根據原始文件生成隨機聚類中心向量（需指定聚類中心向量個數k），指定循環次數；
2）在map階段，setup函數讀取並初始化聚類中心向量；在map函數中讀取每個記錄，計算當前記錄到各個聚類中心向量的距離，根據到聚類中心向量最小的聚類中心id判斷該記錄屬於哪個類別，輸出所屬聚類中心id和當前記錄；
3）在reduce階段，reduce函數接收相同聚類中心id的數據；把這些數據的每列進行求和，並記錄每列的個數；計算新的聚類中心向量（每列的和除以每列的個數），然後輸出聚類中心id和新的聚類中心向量；
4）判斷前後兩次聚類中心向量之間的誤差是否小於某閾值；如果小於，則跳轉到步驟5），否則跳轉到步驟2）；
5）針對最後一次生成的聚類中心向量對原始數據進行分類，得到每個記錄的類別。
其MR數據流如圖2-48所示。
思路2
如如圖2-49所示，算法描述如下：
1）根據原始文件生成隨機聚類中心向量（需指定聚類中心向量個數k），指定循環次數。
2）在map階段，setup函數讀取並初始化聚類中心向量，同時初始化聚類中心向量和；在map函數中讀取每個記錄，計算當前記錄到各個聚類中心向量的距離，根據到聚類中心向量最小的聚類中心id判斷該記錄屬於哪個類別，然後把所屬的類別加入到聚類中心向量和中（需要記錄個數及和，即需要自定義類型）；在cleanup函數中輸出所屬聚類中心id和其對應的聚類中心向量和。
3）在reduce階段，reduce函數接收相同聚類中心id的數據；把這些數據的每列進行求和，並記錄每列的個數；計算新的聚類中心向量（每列的和除以每列的個數），然後輸出聚類中心id和新的聚類中心向量。
4）判斷前後兩次聚類中心向量之間的誤差是否小於某閾值；如果小於，則跳轉到步驟5），否則跳轉到步驟2）。
5）針對最後一次生成的聚類中心向量對原始數據進行分類，得到每個記錄的類別。
其MR數據流如圖2-50所示。
最後更新：2017-06-26 10:32:37