Hadoop大作業(yè)

1、網(wǎng)絡(luò)大數(shù)據(jù)課程作業(yè)目錄1 實(shí)驗(yàn)環(huán)境部署11.1 主機(jī)環(huán)境11.2虛擬機(jī)環(huán)境12 方法介紹12.1 文本聚類12.2 主要的聚類方法22.3 K-means算法32.4 Hadoop實(shí)現(xiàn)42.5 Spark實(shí)現(xiàn)73 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)84 對兩個平臺上實(shí)現(xiàn)方法的對比85 收獲與建議9附錄10網(wǎng)絡(luò)大數(shù)據(jù)課程作業(yè)1 實(shí)驗(yàn)環(huán)境部署1.1 主機(jī)環(huán)境 處理器Intel(R) Core(TM)2 Duo CPU 2.80GHz內(nèi)存8.00GB操作系統(tǒng)WIN7SP1 64bit1.2虛擬機(jī)環(huán)境VMware® Workstation 10.0.2 build-1744117處理器2Core內(nèi)存4GB操作系統(tǒng)

2、Ubuntu12.04 LTS Desktop 32bitHadoop與Spark環(huán)境在之前的練習(xí)中已經(jīng)搭好。2 方法介紹2.1 文本聚類文本聚類（Text clustering）主要是依據(jù)著名的聚類假設(shè)：同類的文檔相似度較大，而不同類的文檔相似度較小。作為一種無監(jiān)督的機(jī)器學(xué)習(xí)方法，聚類由于不需要訓(xùn)練過程，以及不需要預(yù)先對文檔手工標(biāo)注類別，因此具有一定的靈活性和較高的自動化處理能力，已經(jīng)成為對文本信息進(jìn)行有效地組織、摘要和導(dǎo)航的重要手段。文本聚類可以用于生成一篇簡明扼要的摘要文檔；對搜索引擎返回的結(jié)果進(jìn)行聚類，使用戶迅速定位到所需要的信息；對用戶感興趣的文檔（如用戶瀏覽器cache中的網(wǎng)頁）聚

3、類，從而發(fā)現(xiàn)用戶的興趣模式并用于信息過濾和信息主動推薦等服務(wù)；數(shù)字圖書館服務(wù)；文檔集合的自動整理等等。2.2 主要的聚類方法（1）基于劃分的方法基于劃分的聚類算法（Partitioning Method）是文本聚類應(yīng)用中最為普遍的算法。方法將數(shù)據(jù)集合分成若干個子集，它根據(jù)設(shè)定的劃分?jǐn)?shù)目k選出k個初始聚類中心，得到一個初始劃分，然后采用迭代重定位技術(shù)，反復(fù)在k個簇之間重新計(jì)算每個簇的聚類中心，并重新分配每個簇中的對象，以改進(jìn)劃分的質(zhì)量。使得到的劃分滿足“簇內(nèi)相似度高，簇間相似度小”的聚類原則。典型的劃分聚類方法有K-means算法和K-medoids算法，兩者的區(qū)別在于簇代表點(diǎn)的計(jì)算方法不同。前

4、者使用所有點(diǎn)的均值來代表簇，后者則采用類中某個數(shù)據(jù)對象來代表簇。為了對大規(guī)模的數(shù)據(jù)集進(jìn)行聚類，以及處理復(fù)雜形狀的聚類，各類改進(jìn)的劃分算法逐漸增多?；趧澐址椒ǖ膬?yōu)點(diǎn)是運(yùn)行速度快，但該方法必須事先確定k的取值。算法容易局部收斂，且不同的初始聚類中心選取對聚類結(jié)果影響較大。為此，應(yīng)用最廣泛的k-means算法有很多變種，他們可能在初始k個聚類中心的選擇、相似度的計(jì)算和計(jì)算聚類中心等策略上有所不同，最終實(shí)現(xiàn)聚類結(jié)果改進(jìn)的目標(biāo)。（2）基于層次的方法基于層次的聚類算法（Hierarchical Method）又叫“分級聚類算法”或“樹聚類”，它通過分解給定的數(shù)據(jù)對象集來創(chuàng)建一個層次。這種聚類方法有兩種基

5、本的技術(shù)途徑：一是先把每個對象看作一個簇，然后逐步對簇進(jìn)行合并，直到所有對象合為一個簇，或滿足一定條件為止；二是把所有對象看成一類，根據(jù)一些規(guī)則不斷選擇一個簇進(jìn)行分解，直到滿足一些預(yù)定的條件，如類的數(shù)目達(dá)到了預(yù)定值，或兩個最近簇的距離達(dá)到閾值等。前者稱為自下而上的凝聚式聚類，后者稱為自上而下的分裂式聚類。（3）基于密度的方法絕大多數(shù)劃分算法都是基于對象之間的距離進(jìn)行聚類，這類方法只能發(fā)現(xiàn)圓形或球狀的簇，較難發(fā)現(xiàn)任意形狀的簇。為此，提出了基于密度的聚類算法（Density-Based Clustering Method），其主要思想是：只要鄰近區(qū)域的對象或數(shù)據(jù)點(diǎn)的數(shù)目超過某個閾值，就繼續(xù)聚類。即

6、對給定類中的每個數(shù)據(jù)點(diǎn)，在一個給定范圍的區(qū)域中至少包含某個數(shù)目的點(diǎn)，這樣就能很好的過濾掉“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。其基本出發(fā)點(diǎn)是，尋找低密度區(qū)域分離的高密度區(qū)域。（4）基于網(wǎng)格的方法基于網(wǎng)格的算法（Grid-Based Clustering Method）把對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)絡(luò)結(jié)構(gòu)。所用的聚類操作都在整個網(wǎng)絡(luò)結(jié)構(gòu)即量化的空間上進(jìn)行。這種方法的一個突出的優(yōu)點(diǎn)就是處理速度很快，其處理時間獨(dú)立于數(shù)據(jù)對象的數(shù)目，只與量化空間中的每一維的單元數(shù)目有關(guān)。（5）基于模型的方法基于模型的算法（Model-Based Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)

7、模型之間的適應(yīng)性。這樣的算法經(jīng)常是基于這樣的假設(shè)，數(shù)據(jù)是根據(jù)潛在的概率分布生成的。它通過為每個聚類假設(shè)一個模型來發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對象。根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動確定聚類個數(shù)，從而得到魯棒性較好的聚類方法。基于模型的算法主要有兩類，分別為統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。2.3 K-means算法K-means算法接受數(shù)據(jù)集和參數(shù)k，經(jīng)過若干次迭代，將輸入的n個數(shù)據(jù)對象（以m維向量形式表示）劃分為k個聚類，使得所獲得的聚類滿足：1、 同一聚類中的數(shù)據(jù)對象的相似度較高（或距離最近）；2、 不同聚類中的數(shù)據(jù)對象的相似度較低（或距離最遠(yuǎn)）。算法流程：1、 適當(dāng)選擇k個初

8、始中心；2、 在第i次迭代中，對任意一個樣本數(shù)據(jù)，求其到k個中心的距離，然后將該樣本數(shù)據(jù)歸到距離最短的中心所在的類；3、 對于每個類，利用求均值等方法更新該類的中心值；4、 對于所有的k個聚類中心，如果經(jīng)過2、3的某次迭代法更新后，值保持不變，則迭代結(jié)束，否則繼續(xù)迭代。2.4 Hadoop實(shí)現(xiàn)本次作業(yè)的實(shí)驗(yàn)數(shù)據(jù)為大量的中文短文本，包含未分詞和已分詞兩種模式，而對于大規(guī)模的中文網(wǎng)站聚類，其流程見下圖：圖1 中文聚類分析根據(jù)這一完整的流程，我們先在hadoop下實(shí)現(xiàn)聚類，共有七個源文件：（1）WordFrequenceInDocument.java提取中文、分詞、去停用詞、統(tǒng)計(jì)詞頻 （2

9、）WordCountsInDocuments.java統(tǒng)計(jì)每個網(wǎng)頁的單詞數(shù)目    （3）WordsInCorpusTFIDF.java統(tǒng)計(jì)單詞在多少個網(wǎng)頁出現(xiàn)，計(jì)算TFIDF，建立詞表    （4）DocumentVetorBuid.java建立網(wǎng)頁向量，隨機(jī)選取K個網(wǎng)頁作為中心點(diǎn)    （5）Kmeans.java判斷網(wǎng)頁屬于哪一類，更新中心點(diǎn)，最后輸出網(wǎng)頁所屬中心標(biāo)號    （6）KmeansDriver.java控制 Mapreduc的Job順序，以及K-means迭代流程，設(shè)置參數(shù)   

10、; （7）DocTool.java根據(jù)網(wǎng)頁向量以及所有中心點(diǎn)向量輸出網(wǎng)頁所屬的中心編號在處理中文文本的過程中，三個主要的mapreduce過程如下：表1 WordFrequenceInDocument表2 WordCountsInDocuments表3 WordsInCorpusTFIDF網(wǎng)頁向量以及初始中心點(diǎn)的選取在Mapreduce 中的過程為：表4 DocumentVectorBuildDocTool簡化了Kmeans過程中的代碼，將計(jì)算網(wǎng)頁向量與中心點(diǎn)向量之間的余弦距離，并根據(jù)最大的余弦距離判斷網(wǎng)頁屬于哪一類的方法抽象出來， Kmeans 的迭代過程中可以直接在調(diào)用，簡化了 Kmean

11、s 主類的代碼復(fù)雜度。 Kmeans主類由兩個Mapreduce 組成，一個是在迭代過程中更新中心點(diǎn)，一個是生成最后的結(jié)果，這兩個 Mapreduce 的 Mapper 和 Reducer 如下：表5 Kmeans聚類2.5 Spark實(shí)現(xiàn)Spark平臺中的實(shí)現(xiàn)不需要分別編寫Map方法和Reduce方法，而是按照串行程序的正常邏輯順序來編寫。具體實(shí)現(xiàn)過程如下：（1）輸入的文件使用Hadoop實(shí)現(xiàn)中預(yù)處理之后的文件，即樣本文本特征向量集合，可以直接進(jìn)行KMeans聚類的處理；（2）隨機(jī)生成k個（k=10）向量（維度和取值范圍都與樣本文本的特征向量一致）作為初始的k個中心；（3）使用ma

12、p操作將每個樣本文本特征向量與其所屬的類別映射到一起（需要調(diào)用方法來計(jì)算每個樣本文本特征向量到每個中心的距離，返回最近的中心ID）；（4）使用reduce操作按照映射到的中心ID來匯合，匯合的過程中，特征向量每個維度上數(shù)值都將累加，計(jì)數(shù)器也隨之增長。然后再使用map操作，計(jì)算平均值，即可得到新的k個中心；（5）計(jì)算新的k個中心與舊的k個中心的距離和，若為0（或小于某一閾值）則停止迭代，輸出聚類結(jié)果，程序結(jié)束，否則繼續(xù)迭代，重復(fù)3、4、5。代碼見附錄。3 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)經(jīng)統(tǒng)計(jì)，一共12142條樣本文本，聚類到k=10類，其中分類是09的分別為542、2172、1652、2698、30、2386、3

13、03、506、976、877條。Hadoop的結(jié)果：圖2 Hadoop結(jié)果Spark的結(jié)果：圖3 Spark結(jié)果4 對兩個平臺上實(shí)現(xiàn)方法的對比（1）Hadoop的各項(xiàng)時間的統(tǒng)計(jì)信息如下（單位ms）：reading files and creating dict time: 73441generating vectors time: 7133total iteration: 10first iter time: 832246average iter time: 540034total time: 5204791（2）Spark的各項(xiàng)時間的統(tǒng)計(jì)信息如下（單位ms）：reading files ti

14、me: 321total iteration: 8first iter time: 30428average iter time: 15000total time: 120132列表如下：單位：ms 讀文件時間迭代次數(shù)首次迭代時間平均迭代時間總時間 Hadoop73441108322465400345204791 Spark32183042815000120132表6 Hadoop與Spark對比不難看出Spark平臺的效率和速度都要比Hadoop平臺高出很多。5 收獲與建議通過本學(xué)期“網(wǎng)絡(luò)大數(shù)據(jù)管理理論和應(yīng)用”的學(xué)習(xí)，我了解到關(guān)于大數(shù)據(jù)、分布式平臺、語義計(jì)算等比較前沿的知識。比如在學(xué)習(xí)過程中

15、，我了解到通過大數(shù)據(jù)分析處理用戶行為模式，向用戶推薦廣告，然后通過銷量的變化來判斷廣告推薦系統(tǒng)的好壞這樣一種算法，對于這種算法我就比較感興趣，所以通過課程的學(xué)習(xí)我拓展了自身的視野。通過老師和助教的指導(dǎo)，我們還搭建了hadoop和spark平臺，進(jìn)行了基本的mapreduce編程，為以后深入學(xué)習(xí)打下了基礎(chǔ)。在學(xué)習(xí)過程中，我們還鍛煉了做報告的能力，分享了自學(xué)的心得。至于建議方面，我覺得做報告的環(huán)節(jié)，是否可以限定在相關(guān)領(lǐng)域的核心期刊或會議論文上，這樣學(xué)術(shù)性會更好，更能鍛煉大家的學(xué)習(xí)和報告能力。附錄object SparkKMeans /String轉(zhuǎn)Vector def parseVector(li

16、ne: String): Vector = return new Vector(line.split(' ').map(_.toDouble) /計(jì)算最近中心點(diǎn) def closestCenter(p: Vector, centers: ArrayVector): Int = var bestIndex = 0 var bestDist = p.squaredDist(centers(0) /差平方之和 for (i <- 1 until centers.length) val dist = p.squaredDist(centers(i) if (dist < b

17、estDist) bestDist = dist bestIndex = i return bestIndex /主方法 def main(args: ArrayString) val sc = new SparkContext("local", "SparkKMeans") System.out.println("reading files start.") val t1 = System.currentTimeMillis() val lines = sc.textFile("/home/fabkxd/Documents

18、/kmeans_data/inputfile.txt") val points = lines.map(parseVector(_).cache() /文本中每行代表一個樣本，轉(zhuǎn)換為Vector val t2 = System.currentTimeMillis() System.out.println("reading files done.n") val dimensions = 5100 /節(jié)點(diǎn)的維度 val k = 10 /聚類個數(shù) System.out.println("initial centers start.") / 隨機(jī)初始化

19、k個中心節(jié)點(diǎn) val rand = new Random(42) var centers = new ArrayVector(k) for (i <- 0 until k) centers(i) = Vector(dimensions, _ => rand.nextDouble) System.out.println("initial centers done.n") System.out.println("kmeans iterations start.") var first: Long = 0 val to1 = System.curr

20、entTimeMillis() var iter: Int = 1 var over: Int = 1for (i <- 1 to iterations) if (over = 1) System.out.println("titeration " + i + " start.") var ti1 = System.currentTimeMillis() /對每個點(diǎn)計(jì)算距離其最近的中心點(diǎn) val mappedPoints = points.map p => (closestCenter(p, centers), (p, 1) val newC

21、enters = mappedPoints.reduceByKey case (sum1, count1), (sum2, count2) => (sum1 + sum2, count1 + count2) /(向量相加, 計(jì)數(shù)器相加) .map case (id, (sum, count) => (id, sum / count) /根據(jù)前面的聚類，用平均值算法重新計(jì)算中心節(jié)點(diǎn)的位置 .collect var cdist: Double = 0 / 計(jì)算收斂距離并更新中心節(jié)點(diǎn) for (id, value) <- newCenters) cdist += value.squaredDist(centers(id) cente