近似譜聚類算法描述

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

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