近似譜聚類算法描述

二、近似譜聚類算法描述本節(jié)論文闡述基于相似矩陣稀疏化方法稀疏化后離群點的優(yōu)化處理，并將該處理步驟應用于譜聚類算法中?；谏鲜龇治鼋谱V聚類算法整體流程總結描述如表3.2所示。表3.2近似譜聚類算法（ASCA）算法：近似譜聚類算法（ASCA）輸入：數(shù)據(jù)點，待聚類數(shù)目輸出：聚類使用公式，（其中，是的個最近鄰按距離排序后第個鄰居，同理，），構建相似矩陣；使用稀疏化矩陣獲得半正定矩陣，找出矩陣對稱位置不一致的相似度，并將對稱元素設置為0，調(diào)整為對稱半正定矩陣；使用優(yōu)化公式對矩陣進行離群點調(diào)優(yōu)；計算對稱半正定拉普拉斯矩陣；計算的特征向量分解，找出第k個最小非零特征特征量，并按列排列k個特征向量構建特征向量矩陣；計算標準化矩陣（）；使用粗糙集模型選擇k-means初始化聚類中心位置并對矩陣進行k-means聚類,把其聚類成k組（）?；诮谱V聚類算法整體步驟描述，為進行近似譜聚類算法Matlab輔助實驗鋪墊，繪制近似譜聚類算法流程示意圖如圖3.1所示。Matlab輔助實驗主要是將示意圖3.1中的所示的算法與正交化Nystrom低階子矩陣抽樣近似相似矩陣譜聚類算法（ONSP:OrthogonalizationNystromSpectralClustering）和最近鄰稀疏化近似相似矩陣譜聚類算法（tNNSC:SpectralClustering）進行對比，并驗證其聚類效果。圖3.1近似譜聚類算法流程示意圖三、近似譜聚類算法時間復雜度分析現(xiàn)對基于相似矩陣稀疏化方法離群點優(yōu)化的近似譜聚類算法時間復雜度簡單分析，步驟1：使用高斯函數(shù)公式構建相似矩陣的時間復雜度是，其中表示數(shù)據(jù)點數(shù)目、表示數(shù)據(jù)維數(shù)，計算數(shù)據(jù)點和之間的相似度的時間復雜度是，則計算整個數(shù)據(jù)集的時間復雜度是；步驟2：使用稀疏化矩陣獲得半正定矩陣并調(diào)整為對稱半正定矩陣借助于最大堆，其時間復雜度是，其中是最近鄰數(shù)；步驟3：優(yōu)化離群點步驟是非確定性多項式困難問題NP-hard（NondeterministicPloynomialHard）問題，其時間復雜度隨近似相似度矩陣維數(shù)按指數(shù)增長；步驟4與步驟5：計算對稱半正定拉普拉斯矩陣并找出k個最小非零特征值的特征向量的時間復雜度在論文第二章第二節(jié)中已經(jīng)詳細分析過，即；步驟6：計算標準化矩陣的時間復雜度是；步驟7：執(zhí)行k-means聚類時間復雜度是：，其中表示k-means聚類過程迭代的次數(shù)，指待聚類數(shù)目。第三節(jié)近似譜聚類算法實驗分析一、近似譜聚類算法輔助實驗（1）Matlab輔助實驗環(huán)境描述為驗證表3.2所示近似譜聚類算法與正交化Nystrom低階子矩陣抽樣近似相似矩陣譜聚類算法和最近鄰稀疏化近似相似矩陣譜聚類算法的性能，鑒于HadoopMapReduce并行實驗對比的工作量過大，故僅設計基于Matlab的對比性實驗。Matlab輔助實驗環(huán)境：近似譜聚類算法（ASC）的Matlab輔助性驗證以及其與正交化Nystrom低階子矩陣抽樣近似相似矩陣譜聚類算法和最近鄰稀疏化近似相似矩陣譜聚類算法的對比。實驗所使用的Matlab版本是：MatlabR2011a，運行Matlab的服務器是：WindowsServer2008R2Datacenter，系統(tǒng)處理器：Intel（R）CPUE5-2600@2.30GHz（2處理器），其內(nèi)存（RAM）32.0GB，系統(tǒng)類型：64位操作系統(tǒng)。（2）Matlab輔助實驗數(shù)據(jù)集描述輔助性實驗使用的經(jīng)典文本分類數(shù)據(jù)集是路透社語料庫卷I:RCV1（ReutersCorpusVolumeI）[64]，其具體描述見表3.3所示。表3.3實驗數(shù)據(jù)集描述數(shù)據(jù)集類別數(shù)樣本數(shù)特征維數(shù)數(shù)據(jù)集規(guī)模是否歸一化來自領域RCV1103193844 1441.23MB是工業(yè)界術語（ECAT）（3）ASCMatlab實驗和對比實驗本實驗主要是驗證所提出的基于稀疏相似矩陣優(yōu)化的譜聚類算法（ASC），圖3.2顯示分別構造RCV1數(shù)據(jù)集的稀疏化相似矩陣（t=10,20，30，40，50，100，200，300，400，500），計算相似矩陣離群點優(yōu)化時間、ASC算法計算總時間、SVD計算時間和k-means計算時間，以及聚類質(zhì)量（包括NMI得分和聚類精確值，聚類精確值計算介紹參見論文第五章第三節(jié)實驗評估標準），NMI標準化交互信息量（NormalizedMutualInformation）,NMI是主要的聚類質(zhì)量評估標準，NMI值越大，表明近似譜聚類算法質(zhì)量越高。其用于實際的聚類標識CAT（Categorylabel）與實驗結果獲得的聚類標識CLS（Clusterlabel），定義如下：（3.8）（3.9）其中，與熵分別表示CAT與CLS的交互信息量、標準化在范圍內(nèi)。、與分別表示實際的聚類的數(shù)據(jù)點數(shù)、實驗結果獲得的聚類的數(shù)據(jù)點數(shù)和既屬于實際的聚類又屬于實驗結果獲得的聚類的數(shù)據(jù)點數(shù)。圖3.2ASC計算時間和聚類質(zhì)量圖3.2中可以得出論文提出的ASC算法在優(yōu)化相似矩陣離群點上的計算時間最耗時，但使用RCV1數(shù)據(jù)集實驗所得的聚類精確度非常高，基于這樣的原因，本文研究設計并實現(xiàn)基于HadoopMapReduce并行近似譜聚類算法。圖3.3ONSC計算時間和聚類質(zhì)量圖3.3展示論文第二章第三節(jié)所介紹的Nystrom低階子矩陣抽樣法近似譜聚類算法實驗結果，目的是作為參照與所提出的ASC譜聚類實驗進對比。該實驗構建相似矩陣所使用的最近鄰分別是t=20，30，40，50，100，200，300，400，500，1000，1500， 2000，圖中分別顯示計算Euclidean距離矩陣與構建相似矩陣的時間，以及SVD計算時間、k-means計算時間和ONSC計算的總時間，相對于所提出的ASC聚類，ONSC計算的總時間要小很多，但是其聚類精確度不高。圖3.4tNNSC計算時間和聚類質(zhì)量圖3.4描述論文第二章第三節(jié)所介紹的稀疏化矩陣法近似譜聚類算法實驗結果，目的也是作為參照與所提出的ASC譜聚類實驗進行對比。該實驗構建相似矩陣所使用的最近鄰分別是t=5，15，30，40，50，100，150，200，250，300，350，400，450，500，圖中分別顯示計算Euclidean距離矩陣的時間，以及SVD計算時間、k-means計算時間和tNNSC計算的總時間，相對于所提出的ASC聚類以及ONSC聚類,tNNSC計算的總時間最少,但是其聚類精確度也不高。二、ASCMatlab實驗結果對比分析根據(jù)并行算法研究方法學中復雜性標準和性能評估，設計并行算法時，重要的是考慮算法的時空復雜性，此外，還需要考慮算法的加速比、可擴展性等其它性能參數(shù)［65］。論文驗證所提出的基于稀疏相似矩陣優(yōu)化的譜聚類算法(ASC)旨在分析其計算時間和聚類質(zhì)量，圖3.5更加直觀的對比顯示優(yōu)化的ASC算法、ONSC和tNNSC算法的總的計算時間，以及它們各自的SVD計算時間、k-means計算時間；優(yōu)化的ASC算法、ONSC和tNNSC算法聚類質(zhì)量，包括聚類的精確值和標準化交互信息量NMI。圖3.5Matlab輔助實驗計算時間和聚類質(zhì)量對比論文鑒于構建優(yōu)化的ASC算法近似相似矩陣的優(yōu)化步驟時間、SVD計算時間、k-means計算時間，考慮ASC算法聚類精確度，研究設計并實現(xiàn)基于Hadoop的并行近似譜聚類算法，以期借助MapReduce并行編程框架達到在保證聚類精確度的前提下顯著減少處理大規(guī)模高維數(shù)據(jù)的計算時間。第四章MapReduce并行計算近似譜聚類算法研究與設計第一節(jié)并行算法設計Hadoop分布式集群系統(tǒng)MapRedue并行計算編程模型框架下，基于相似矩陣稀疏化方法離群點優(yōu)化的近似譜聚類算法并行設計目的是在確保聚類質(zhì)量的前提下聚類大規(guī)模高維數(shù)據(jù)。論文基于此目的與MapReduce并行計算編程模型設計并驗證第三章所提出的近似譜聚類算法。一、 MapReduce并行算法設計理念HadoopMapReduce并行近似譜聚類算法設計與分析依賴于MapReduce并行計算模型。MapReduce并行算法應用程序是同時執(zhí)行并發(fā)作業(yè)Task的集合，Task作業(yè)集相互通信并同步協(xié)調(diào)，達到對近似譜聚類的并行求解。MapReduce并行近似譜聚類并行算法執(zhí)行分三個函數(shù)階段設計：(1)map()函數(shù)：map()函數(shù)隸屬于Mapper類，Mapper類繼承JobConfigurable接口中的MapReduceBase類，接口中的configure方法按照MapReduce應用程序中定義的JobConf參數(shù)初始化Mapper類。MapReduce應用程序使用InputFormat接口的RecordReader類調(diào)用InputSplit接口中的getRecordReader方法讀取對，Mapper類中重寫map()函數(shù)并行處理對，main()函數(shù)使用Mapper類中的run方法調(diào)用MapReduce應用程序中map()函數(shù)。 (2)combine。函數(shù)：combine()函數(shù)實際的功能是“本地的reduce()函數(shù)”屬于MapReduce并行計算算法設計中性能優(yōu)化函數(shù)，它隸屬于Combiner類，Combiner類繼承JobConfigurable接口中的MapReduceBase類并實現(xiàn)Reducer類，重寫reduce()函數(shù):reduce(IntWritablekey,Iterator<Text>values,OutputCollectorvIntWritable,Text〉output,Reporterreporter)實現(xiàn)本地map()函數(shù)中間結果值合并，減少網(wǎng)絡通信對算法性能的影響。由于combine()函數(shù)階段中間值對合并操作可以減少MapReduce應用程序中ReduceTask遠程拷貝多個MapTask本地數(shù)據(jù)量(中間值)，因此，如果并行近似譜聚類算法中間步驟忽略網(wǎng)絡通信對并行算法計算時間的影響，則不考慮combine()函數(shù)對并行算法設計的性能優(yōu)化。(3)reduce()函數(shù)：reduce()函數(shù)類繼承JobConfigurable接口中的MapReduceBase類并實現(xiàn)Reducer類，reduce()函數(shù)與combine()函數(shù)的不同之處在于，ReduceTask合并并傳輸Hadoop集群中不同節(jié)點的MapTask輸出結果，在MapReduce應用程序中需重寫reduce()函數(shù)。二、 MapReduce并行算法中依賴步驟的分解目前，HadoopMapReduce迭代式并行計算處于研究初期，受MapReduce并行計算模型支持抽象度計算所限，Hadoop1.2.1版本中MapReduce并行編程框架只能并行算法中不存在相互依賴的步驟，即不能顯式地支持并行算法中迭代式的操作，但是，表3.2近似譜聚類算法中涉及多次迭代編程計算，如步驟7中k-means聚類算法聚類中心迭代更新，即聚類中心更新依賴于上次迭代的結果。在此情況下，怎樣分解近似譜聚類算法中存在依賴關系的步驟的每次迭代以及何時終止迭代(可行的方法如：combine()函數(shù)對ReduceTask結果進行歸并，MapReduce應用程序根據(jù)判定條件決定迭代是否終止，倘若不滿足終止條件，則combine()函數(shù)再次將歸并的結果數(shù)據(jù)傳輸給MapTask開始新一輪的迭代)、怎樣優(yōu)化處理MapTask和ReduceTask重新創(chuàng)建時所引起的資源浪費、怎樣存儲每次迭代過程中ReduceTask歸并的數(shù)據(jù)結果是基于HadoopMapReduce并行近似譜聚類算法設計的難點，也是論文設計的重點。論文重點分析近似譜聚類算法中可用于MapTask獨立計算的任務及其之間依賴性。論文所設計的MapReduce并行計算map()與reduce()函數(shù)都依據(jù)并行計算功能分解MapReduce應用程序。MapReduce并行近似譜聚類算法中依賴步驟的分解將在本章第二節(jié)給出詳細的設計及并行策略，并在第五章第四節(jié)實驗過程中給出并行近似譜聚類算法設計的實驗驗證。第二節(jié)近似譜聚類算法HadoopMapReduce并行分析與設計本節(jié)基于HadoopMapReduce分析并設計稀疏化離群點優(yōu)化相似矩陣的近似譜聚類算法，首先，詳細論述所提出的近似譜聚類算法步驟中時間復雜度較高的三個階段：稀疏化近似相似矩陣、特征向量分解、k-means及其初始化聚類中心并行策略；其次，分別設計上述三個階段的Mapper類與Reducer類以及Combiner類；最后，分析所設計基于HadoopMapReduce三個階段時間復雜度。一、稀疏化近似相似矩陣MapReduce并行策略與設計(1)MapReduce稀疏化近似相似矩陣并行策略構建相似矩陣過程、使用近似法稀疏化相似矩陣過程以及對稱半正定矩陣進行離群點調(diào)優(yōu)過程中不存在迭代步驟也不相互依賴，故可設計上述三個過程的MapReduce并行計算的map()和reduce()函數(shù)。首先計算每個數(shù)據(jù)點到所有數(shù)據(jù)點的距離，以找出該數(shù)據(jù)點的個最近鄰，設為Hadoop集群中slaves機器數(shù)目，對于的輸入文件，理想情況下，每臺機器分配個數(shù)據(jù)點。在使用Euclidean距離計算本地個數(shù)據(jù)點彼此之間的距離(distance)，為減少計算的時間，首先提前計算除外每臺機器分配個數(shù)據(jù)點的值。當本地本地個數(shù)據(jù)點個數(shù)據(jù)點的距離計算完成后，按距離排序找出第數(shù)據(jù)點作為的個最近鄰的中位數(shù)，進而根據(jù)計算(gammal)和(gamma2),使用最大堆保持本地數(shù)據(jù)點的個最近鄰，按照公式把距離矩陣轉(zhuǎn)化成相似矩陣。最后，由于可能存在數(shù)據(jù)點是的最近鄰，但不是的最近鄰調(diào)整成對稱相似矩陣。(2)Mapper階段設計稀疏化近似矩陣MapReduce的Mapper階段設計中，輸入是數(shù)據(jù)集.txt文件，輸出是(key,value)對，其中key表示每臺機器上的個數(shù)據(jù)點距離矩陣或相似矩陣標識符行標識符，value表示與之對應的距離矩陣或相似矩陣的元素值。Mapper類設計偽代碼表示如下：Mapper類：map(Textkey,Textinput)Input:數(shù)據(jù)集.txt文件Output:輸出(key,value)對ClassMapperMethodmap()/*設置輸入分布式文件的格式與數(shù)據(jù)類型*/conf.setInputFormat();conf.setOutputKeyClass();6./*創(chuàng)建標識符，使得每臺機器上的個數(shù)據(jù)點有相同的key*/intindex,localIndex=index/num,tNearestNeighbor;doublevalue;/*使用Euclidean距離計算本地個數(shù)據(jù)點彼此之間的距離*/compute。;//并行計算Euclidean距離distance和平均值以便計算gammal和gamma2/*按照第三章表3.2近似譜聚類算法步驟1計算相似度,使用最大堆，保持本地數(shù)據(jù)點的個最近鄰*/distanceToSimilarity();//Euclidean距離矩陣轉(zhuǎn)換為相似矩陣，且在原位置//存儲行稀疏化后的數(shù)據(jù)點similarity=exp(-distance*distance/(2*gammal*gamma2))/*調(diào)整相似矩陣為對稱矩陣*/similarityToSymmetry();/*按照第三章表3.2近似譜聚類算法步驟3對離群點進行調(diào)優(yōu)*/ifdooutlierIndx=；//outlierIndx表示離群點下標//調(diào)優(yōu)相似矩陣//行Emitoutput.collect(IntWritable(index),Text(outString))as(key,value)pair;〃輸出(key,value)對，key近似相似矩陣標識符,value近似相似矩陣元素值(3)Reducer階段設計稀疏化近似矩陣MapReduce的Reducer設計目的是歸并Mapper階段個機器上計算所得的本地相似矩陣部分值，最終獲得并存儲整個數(shù)據(jù)集的近似相似矩陣。Reducer類設計偽代碼表示如下：Reducer類：reduce(IntWritablekey,Iterator<Text>values)Input:Mapper類階段輸出的分布式文件中(key,value)對Output:輸出近似相似矩陣(key',value'))對ClassReducerMethodreduce()intindex;Sring[]partialValues;Doublevalues;repeatwhile(values.hasNext())dopartialValues=values.next().toString().split();for(inti=0;i<partialValues.length-l;i++)dosimilarity.array[i]+=Double.parseDouble(partialValues[i]);endforendwhileendEmitoutput.collect(IntWritable(index),Text(outString))as(key,value')pair;〃輸出(key',l4. //value')對（4）MapReduce并行稀疏化并行近似相似矩陣并行時間復雜度分析HadoopMapReduce并行前構建和之間相似矩陣的時間復雜度是：，使用稀疏化矩陣獲得半正定矩陣并調(diào)整為對稱半正定矩陣，其時間復雜度是：，則HadoopMapReduce并行前構建基于近似法相似矩陣的時間復雜度是：。在Hadoop集群中理想情況下，假設并行計算稀疏化近似相似矩陣均勻分布到slaves上執(zhí)行且不考慮優(yōu)化離群點步驟是非確定性多項式困難問題NP-hard的計算時間，則HadoopMapReduce并行后計算稀疏化近似相似矩陣的時間復雜度是：（其中指Hadoop集群中slaves機器數(shù)目），表4.1給出HadoopMapReduce并行前后計算稀疏化近似相似矩陣的時間復雜度對比。表4.1MapReduce稀疏化近似相似矩陣并行時間復雜度分析稀疏化近似矩陣HadoopMapReduce并行前HadoopMapReduce并行后時間復雜度二、拉普拉斯特征向量分解的MapReduce并行策略與設計（1）MapReduce特征向量分解并行策略MapReduce并行計算并存儲近似相似矩陣后，首先，計算獲得對稱半正定近似拉普拉斯矩陣（）；其次，在PaulG.Constantine等人［58］與AustinR.Benson等人［66］研究的基于MapRedcueQR矩陣分解基礎上計算的SVD,最后，設計基于MapReduce并行計算編程模型的近似矩陣Mapper類和Reducer類求解其特征向量。為避免MapReduce只能并行處理相互依賴的步驟,MapRedcueQR矩陣分解（是正交矩陣，是上三角矩陣）使用2個map（）函數(shù)和1個reduce（）函數(shù)并行求解和矩陣，如圖4.1所示步驟一和步驟三中是map（）函數(shù)，步驟二中是reduce函數(shù)。其中步驟一只是用MapTask計算本地QR矩陣分解，返回的Q、R矩陣分別存儲在不同的HDFS文件中；步驟二中僅使用于一個ReduceTask，其中，輸入是步驟一中矩陣分解計算所得的R矩圖4.1MapReduce并行計算QR示意圖陣集，該過程根據(jù)R矩陣計算Q矩陣并作為values鍵值輸出，歸并后的R矩陣即是所求矩陣分解中的上三角矩陣；步驟三中只使用一個MapTask，其輸入是步驟一中計算所得的Q矩陣集，輸出是與步驟二計算所得的Q矩陣集的乘積，其結果是矩陣分解中的正交矩陣。為使用MapReduce并行編程框架計算近似矩陣特征向量分解，現(xiàn)對上述基于MapRedcueQR矩陣分解進行修改計算的SVD，步驟二的過程中增加計算則的特征向量分解為（其中、、是正交矩陣；是上三角矩陣；是半正定對角矩陣）。根據(jù)譜定理和半正定矩陣可知：的SVD與其特征分解存在相同特征空間［67］［68］。通過上述方法可以避免因MapRedcue不能迭代計算Arnoldi求解特征向量的難題。最后通過第二章公式（2.11）計算近似矩陣的k個近似特征值與特征向量。（2）Mapper階段設計MapReduce解析近似相似矩陣分布式文件為（key,value）對，其中key指近似相似矩陣分布式文件行標識符（包括矩陣的列數(shù)和當前行數(shù)）；value指近似相似矩陣分布式文件對應key的值。Mapper類設計偽代碼表示如下：Mapper類：map（TypedBytesWritablekey,TypedBytesWritablevalues）Input:近似相似矩陣分布式文件Output:(key,values)對ClassMapperMethodmap()

intnumColumns,currentRow；〃近似相似矩陣文件列數(shù)、當前行數(shù)DenseMatrix;/*設置輸入分布式文件的格式與數(shù)據(jù)類型*/conf.setInputFormat();conf.setOutputKeyClass();SubMethodcompress()beginQRqr=QR.factorize(); 〃對近似相似矩陣進行QR矩陣分解UpperTriangDenseMatrixR=qr.getR(); //獲得矩陣的上三角矩陣EIGeig=EIG.eigsolver(R);EIGeig=EIG.eigsolver(R);DiagonalMatrix=eig.get();NormalizedMatrixQU=eig.getQU();TransposedMatrixV=eig.getV();/*復制上三角矩陣R*/.set(i,j,R.get(i,j));currentRow=numColumns;endnumColumns=row.length;repeatif(currentRow>=.numRows())〃對上三角矩陣R進行特征分解〃獲得矩陣R的特征向量〃獲得矩陣R的左特征向量〃獲得矩陣R的右特征向量〃記錄矩陣R的當前行號//獲得矩陣的總行數(shù)docompress();endifendEmitoutput.collect(TypedBytesWritable(key),TypedBytesWritable(values))as(key,values)pair;//輸出(key,values)對，key指近似相似矩陣分布式文件行標識符；values指QR分解28. 〃修改后步驟二中矩陣與UQ矩陣(3)Reducer階段設計Reducer設計目的是歸并Mapper階段相同key的values鍵值，Reducer類設計偽代碼表示如下：Reducer類：reduce(TypedBytesWritablekey,Iterator<TypedBytesWritable>values)Input:Mapper類階段輸出的(key,(values)對Output:輸出歸并后的(key',values'))對ClassReducerMethodreduce()/*ReduceTask歸并Mapper類階段輸出的(key,(values)X^*/repeatwhile(values.hasNext())docollect(key,values.next());endpair;Emitoutput.collect(key,TypedBytesWritable(values))asthenew(key',values'pair;4)MapReduce特征向量分解時間并行復雜度分析HadoopMapReduce并行前計算的k個最小非零特征特征量的時間復雜度是：，在Hadoop集群中理想情況下，假設計算新k個最小非零特征特征量均勻分布到slaves上執(zhí)行，則HadoopMapReduce并行后計算的k個最小非零特征特征量的時間復雜度是：(其中指Hadoop集群中slaves機器數(shù)目)，表4.2給出HadoopMapReduce并行前后計算的k個最小非零特征特征量的時間復雜度對比。表4.2MapReduce特征向量分解并行時間復雜度分析特征向量分解HadoopMapReduce并行前HadoopMapReduce并行后時間復雜度三、k-means及其初始化聚類中心MapReduce并行策略與設計MapReducek-means及其初始化聚類中心并行策略根據(jù)MapReduce并行計算編程模型依賴步驟分解k-means及其初始化聚類中心：使用計算聚類中心時，計算所有數(shù)據(jù)點對的閾值：；以及每個數(shù)據(jù)點的內(nèi)聚度：耗時步驟設計并行計算；使用k-means聚類算法聚類近似相似矩陣的特征向量時，每個數(shù)據(jù)點與方法得到的k個聚類中心相互之間距離計算是互不依賴的問題求解，故設計MapReducek-means及其初始化聚類中心并行計算。Mapper階段設計MapReduce默認解析方法得到的聚類中心文件為(key,value)對，其中key指數(shù)據(jù)點相對于中心文件起始點的偏移量；value指數(shù)據(jù)點各維信息字符串。Mapper類設計偽代碼表示如下：Mapper類：map(Textkey,Textinput)Input:方法得到的聚類中心文件Output:(key,value)對ClassMapperMethodmap()/*Calculatethecentersusingmethodandloadthemfromtheconf.get().split();Calculatethedistancesbetweeneachpairofpointsandbetweenthispointsandallotherpointsaswellastheneighborhoodofeachpoint;Calculatethecohesionofeachpointandfindoutthefirstcenterwhichisthegreatestcohesionanddeterminethenextmostcohesionpoint,andreturnthecenters*/minDist=Double.MAX_VALUE,minIndex=0;index=1; //minIndex數(shù)據(jù)點距k個聚類中心最近的中心下標repeat 〃計算數(shù)據(jù)點與k個聚類中心最相似的中心并記錄其下標作為keyforeach(center:centers)dodist=.getDistance(point,centers[i]);ifdist<minDistdominDist=dist;minIndex=index;endifendendEmitoutput.collect(IntWrita