郭濤　丁祥武

摘 要 k-modes是一種代表性的分類數(shù)據(jù)的聚類算法。首先對k-modes聚類算法的實現(xiàn)過程進行了改進：通過在分配數(shù)據(jù)對象到簇時更新這個簇中各個屬性項的次數(shù)，使得在遍歷一次全部數(shù)據(jù)對象就能計算出新的簇中心。為了使k-modes能夠處理大規(guī)模分類數(shù)據(jù)，在Hadoop平臺上用MapReduce并行計算模型實現(xiàn)了k-modes算法。實驗表明：在處理大量數(shù)據(jù)時，并行k-modes比串行k-modes極大地縮短了聚類時間，取得了較好的加速比。

關鍵詞 分類數(shù)據(jù)；k-modes；并行聚類；MapReduce

中圖分類號： TP312 文獻標志碼： A 文章編號：2095-2163（2015）01-

Abstract k-modes is a representative categorical attribute oriented clustering algorithm. First， improve the implement process of k-modes： when allocating categorical objects to clusters， update the number of items of each attribute in clusters. so that can compute the new modes of clusters after read the whole dataset once. In order to make k-modes capable for large-scale categorical data， implement k-modes on Hadoop use MapReduce parallel computing model. Experiments show that， parallel k-modes achieve good speedup when dealing with large-scale categorical data.

Key words categorical data； k-modes； parallel clustering； MapReduce

0引言

聚類，屬于無監(jiān)督學習的范疇，是按照一定的相似性要求將數(shù)據(jù)對象集劃分成多個簇的過程，聚類結(jié)果即使得不同簇中的數(shù)據(jù)對象要盡可能相異，而同一簇中的數(shù)據(jù)對象則盡可能相似[1]。時下，分類數(shù)據(jù)[2]由非數(shù)值的屬性組成，且大規(guī)模、高維度的分類數(shù)據(jù)聚類也于近年來獲得了廣泛的關注。

Huang[3]在1998年提出的分類數(shù)據(jù)聚類算法k-modes[3]是對k-means[4]的擴展，其中采用0-1差異度來代替k-means算法中的距離，算法中差異度越小，就表示距離越小。一個樣本和一個聚類中心的差異度就是兩者中各個屬性不相同的個數(shù)，若不相同則記為“1”，統(tǒng)計結(jié)束所得“1”的個數(shù)總和就是某個樣本到某個聚類中心的差異度。各次比較分析后，該樣本將屬于差異度最小的聚類中心。

k-modes算法因其聚類簡單而得到大范圍應用，但是在如今這個大數(shù)據(jù)時代，并且隨著互聯(lián)網(wǎng)的發(fā)展，現(xiàn)實中的分類數(shù)據(jù)以海量規(guī)模存在并且正在呈現(xiàn)爆炸式增長，在單機上實現(xiàn)的串行k-modes已經(jīng)無法在有效時間內(nèi)取得聚類結(jié)果。Hadoop[5]作為一種流行的分布式系統(tǒng)架構(gòu)，也因其所具備的高可擴展性等諸多優(yōu)點而得到了可觀的發(fā)展及應用。為此，綜合以上探討研究，本文在Hadoop上基于并行編程模型MapReduce[6]實現(xiàn)了k-modes算法，并通過實驗比較了并行k-modes與串行k-modes的聚類速度。

0k-modes算法研究

k-modes算法是Huang[3]在k-means[4]算法的基礎上提出的，是對k-means算法的一種拓展。與k-means算法相比，k-modes主要表現(xiàn)了三點不同：（1）使用不同的相異度測試；（2）使用modes替換means；（3）使用一個基于頻率的方法更新modes。

0.1相異度測量

進一步地，W是一個的{0，1}矩陣，n表示集合X中對象的個數(shù)，k表示簇的個數(shù)，wil=1則表示第i個對象被劃分到第l個簇中。

對集合X的聚類的目標就是找到{Q1，Q2，…，Qk}使得目標函數(shù)E最小化。對應過程的基本步驟如下：

（1）隨機選擇k個對象作為初始的簇中心；

（2）應用匹配方法計算每個對象與簇中心的相異度，并將這個對象分配到與其相異度最小的簇中去。

（3）使用基于頻率的方法更新各簇的中心。

（4）重復（2）、（3）步驟，直至各簇不再變化。

1MapReduce研究

1.1MapReduce編程模型

MapReduce[6]是Google在2004年對外展示的其公司內(nèi)部使用的分布式編程模型。Apache旗下的開源項目Hadoop[5]則對MapReduce框架進行了設計實現(xiàn)，同時又進一步實現(xiàn)了分布式的文件系統(tǒng)HDFS[7- 8]。

概括來說，MapReduce對外提供5個組件（InputFormat、Mapper、Partitioner、Reducer和OutputFormat）全部屬于回調(diào)接口。具體地，MapReduce編程模型主要由兩部分組成，分別為Map和Reduce。對二者的功能將做如下闡述

（1）自己定義的Map類要繼承系統(tǒng)的Mapper類，而Mapper類中提供的四個方法則依次為：setup、map、cleanup和run。其中，setup和cleanup用于管理Mapper生命周期中的資源，相應地setup是在完成Mapper構(gòu)造，即將開始執(zhí)行map動作前調(diào)用，cleanup則在所有的map動作完成后進行調(diào)用。另外，map可用于處理一次輸入的key/value對。而run方法執(zhí)行了上面描述的過程，也就是調(diào)用setup，迭代所有的key/value對，再運行map，繼而調(diào)用cleanup。并且，run方法一般不需要重寫。map的輸出也是key/value，實際上會依據(jù)key值按照指定Partition規(guī)則分配到相應的Reduce進行處理。

（2）自己定義的Reduce類要繼承系統(tǒng)的Reducer類，Reducer類中提供的四個方法可逐一表示為：setup、reduce、cleanup和run。其中setup、cleanup和run方法的調(diào)用與Mapper類中的相似。而reduce方法即是將從map接收到的具有相同key值的value的集合進行一定處理。

1.2MapReduce的優(yōu)勢

MapReduce屬于數(shù)據(jù)并行模型，同時又能實現(xiàn)一定程度的共享變量和消息傳遞，將其與此外的并行計算模型（如MPI[9]、OpenMP[10]等）相比，可知其具有如下優(yōu)勢：

其一，通過MapReduce不僅能用于大規(guī)模數(shù)據(jù)處理，而且還能將很多繁瑣的細節(jié)隱藏起來，比如，自動并行化、負載均衡和災備管理等，這就極大地簡化了程序的開發(fā)；

其二，MapReduce的伸縮性非常好，每增加一臺服務器，就能將其計算能力接入到集群中，而過去的大多數(shù)分布式處理框架，在伸縮性方面都與MapReduce相差甚遠。

0并行k-modes算法設計

本文在不改變k-modes算法原理的基礎上，首先對k-modes聚類算法的實現(xiàn)過程實施了改進研發(fā)：通過在分配數(shù)據(jù)對象到簇時更新這個簇中各個屬性項的次數(shù)，使得僅是遍歷一次全部數(shù)據(jù)對象就能計算出新的簇中心。而后在Hadoop平臺上運用MapReduce并行計算模型實現(xiàn)了k-modes算法。改進后的并行k-modes就能夠?qū)Υ笠?guī)模的分類數(shù)據(jù)進行快速聚類。具體實現(xiàn)分為4個步驟，完整過程如下。

3.1 前期準備

從集合X中隨機選出k個對象作為初始的k個聚類簇的中心，對k個簇從0到k-1編號。定義FileInputFormat函數(shù)可根據(jù)Hadoop集群的計算能力將待聚類的數(shù)據(jù)對象集合X分為p個數(shù)據(jù)塊，從而產(chǎn)生p個Map任務并行執(zhí)行。并且，每個數(shù)據(jù)對象均是用一行文本的形式來存儲。過程中，用key表示數(shù)據(jù)對象所屬的簇，value表示數(shù)據(jù)對象的信息。

3.2 分配對象

每個Map任務的setup函數(shù)均從HDFS中初始化讀取k個聚類簇的中心，并在map函數(shù)中依次讀取相應塊內(nèi)的每個數(shù)據(jù)對象，其格式為<簇編號，數(shù)據(jù)對象>信息，計算這個對象與各個簇中心的差異度，再將其分配到差異度最小的簇中，同時進一步更新這個簇中屬性項出現(xiàn)的次數(shù)。Map函數(shù)的輸出的格式為<新的簇編號，數(shù)據(jù)對象>。而在cleanup函數(shù)中，將k個簇的信息寫回到HDFS，不同的Map任務寫回的簇信息可用Map任務的編號加以區(qū)分。

3.3 更新簇中心

將3.2中p個Map寫回到HDFS中的簇信息分別讀取出來，并按照對應的簇編號進行合并。在合并后的簇信息的每個簇中選出對應屬性項頻率最大的屬性作為當前簇的新中心的屬性項，再將新的簇中心的信息寫回到HDFS。

計算新的簇中心與原來簇中心的差異度，如果差異度小于一定閾值（由用戶設定），則聚類過程完成，將執(zhí)行下一步、即3.4，否則回到3.2繼續(xù)執(zhí)行。

3.4 輸出聚類結(jié)果

定義一個有p個Map任務k個Reduce任務的MapReduce程序?qū)?.2的生成的p個數(shù)據(jù)塊進行處理，每個Map讀取一個數(shù)據(jù)塊，并按照key值（也是簇編號）將每個數(shù)據(jù)對象分配至對應的Reduce來處理，Reduce處理完成后將會在HDFS上生成k個文件，并且每個文件中均包含一個簇的全部數(shù)據(jù)對象。

1實驗與分析

實驗使用Hadoop集群對并行k-modes算法進行了測試，而且又與單機上實現(xiàn)的串行k-modes的執(zhí)行時間進行了比較。

Hadoop集群中共有9臺機器，一臺作為Master，其余8臺作為Slave。每臺機器的硬軟件配置如表 1和表 2所示。

實驗采用美國人口普查數(shù)據(jù)集（US Census Data Set）（http：//dataferrett.census.gov），其中包含1990年美國人口普查公共使用數(shù)據(jù)樣本1%的數(shù)據(jù)。集合中共有數(shù)據(jù)記錄條數(shù)為2 458 285，大小345M，包括祖先、族群、拉美族裔來源、行業(yè)職業(yè)、語言、出生地等68個屬性。按照此數(shù)據(jù)格式，再隨機生成10G的實驗數(shù)據(jù)，通過逐漸增加數(shù)據(jù)量，研究所得的并行k-modes和串行k-modes的處理時間對比則如圖 1所示。

實驗顯示，當處理小量數(shù)據(jù)時，Hadoop集群并未表現(xiàn)出明顯優(yōu)勢；但是當數(shù)據(jù)量較大時，并行k-modes相比串行k-modes的處理時間則大大縮短，因而取得了較好的加速比。

2結(jié)束語

本文對k-modes聚類算法的實現(xiàn)過程展開了改進研究，同時為了使k-modes能夠處理大規(guī)模分類數(shù)據(jù)，又在Hadoop平臺上利用MapReduce并行計算模型實現(xiàn)了k-modes算法。實驗表明：在處理大量數(shù)據(jù)時，并行k-modes與串行k-modes相比，極大地縮短了聚類時間，并且取得了較好的加速比。

本文對k-modes的并行實現(xiàn)程序已經(jīng)發(fā)布到開源社區(qū)（https：//github.com/j2cms/dog）。

參考文獻

[1] Han J， Kamber M， Pei J. Data Mining： Concepts and Techniques[M]. Third Edition. Burlington： Morgan kaufmann， 2011.

[2] Agresti A. Categorical data analysis[M]. Hoboken： John Wiley & Sons， 2014.

[3] HUANG Z. A fast clustering algorithm to cluster very large categorical data sets in data mining[C]//Tucson： DMKD， 1997： 281--297.

[4] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the fifth Berkeley symposium on mathematical statistics and probability， Oakland： University of California Press， 1967： 281-297.

[5] SHVACHKO K， KUANG H， RADIA S， et al. The hadoop distributed file system[C]//Mass Storage Systems and Technologies （MSST）， 2010 IEEE 26th Symposium on， Incline Villiage： IEEE， 2010： 1-10.

[6] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[J]. Communications of the ACM， 2008， 51（1）： 107-113.

[7] GHEMAWAT S， GOBIOFF H， LEUNG S T. The Google file system[C]//ACM SIGOPS Operating Systems Review， New York： ACM， 2003： 29-43.

[8] CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： A distributed storage system for structured data[J]. ACM Transactions on Computer Systems （TOCS）， 2008， 26（2）： 4.

[9] Pacheco P S. Parallel programming with MPI[M]. Burlington： Morgan kaufmann， 1997.

[10] DAGUM L， MENON R. OpenMP： an industry standard API for shared-memory programming[J]. Computational Science & Engineering， IEEE， 1998， 5（1）： 46-55.