通過壹個綜合數據分析案例：”金庸的江湖——金庸武俠小說中的人物關系挖掘“，來學習和掌握MapReduce程序設計。通過本項目的學習，可以體會如何使用MapReduce完成壹個綜合性的數據挖掘任務，包括全流程的數據預處理、數據分析、數據後處理等。
1 任務1 數據預處理
1.1 任務描述
從原始的金庸小說文本中，抽取出與人物互動相關的數據，而屏蔽掉與人物關系無關的文本內容，為後面的基於人物***現的分析做準備。
1.2 關鍵問題
1.2.1 中文分詞和人名提取
使用開源的Ansj_seg進行分詞。Ansj_seg不僅支持中文分詞，還允許用戶自定義詞典，在分詞前，將人名列表到添加用戶自定義的詞典，可以精確識別金庸武俠小說中的人名。
但實際測試的時候發現，Ansj_seg分詞會出現嚴重的歧義問題，比如“漢子”屬於人名列表中的人名(nr)，但Ansj_seg可能會錯誤地將它分類為名詞(n)。因此，如果根據詞性提取人名，會導致最後提取的人名太少。解決方法是在提取人名的時候，需要在將人名加入用戶自定義詞典的同時，構造壹個包含所有人名的字典，對分詞的結果逐個進行測試，如果在字典裏，就是人名。
1.2.2 文件傳輸
使用HDFS傳遞數據。考慮到人名列表文件已經存放在了HDFS裏，所以使用HDFS的方式不需要移動人名列表文件，只需要在Configuration中設置文件在HDFS文件系統中的路徑，然後在Mapper的setup()函數裏調用HDFS的函數獲取文件內容即可。
1.2.3 單詞同現算法
兩個單詞近鄰關系的定義：實驗要求中已經說明，同現關系為壹個段落。
段落劃分：非常慶幸的是，小說原文中壹個段落就是壹行，因此，不需要自己定義FileInputFormat和RecordReader。
1.3 MapReduce設計
1.3.1 Mapper
1.3.2 Reducer
1.3.3 Driver
2 任務2 特征抽取：人物同現統計
2.1 任務描述
完成基於單詞同現算法的人物同現統計。在人物同現分析中，如果兩個人在原文的同壹段落中出現，則認為兩個人發生了壹次同現關系。我們需要對人物之間的同現關系次數進行統計，同現關系次數越多，則說明兩人的關系越密切。
2.2 關鍵問題
2.2.1 人名冗余
在同壹段中，人名可能多次出現，任務壹只負責提取出所有的人名，沒有剔除多余的人名，任務必須在輸出同現次數之前處理冗余人名。我的做法是在Mapper中創建壹個集合，把所有人名放入集合中，集合會自動剔除冗余的人名。
2.2.2 同現次數統計
兩個人物之間應該輸出兩個鍵值對，如“狄雲”和“戚芳”，應該輸出“<狄雲，戚芳> 1”和“<戚芳，狄雲> 1”。多個段落中允許輸出相同的鍵值對，因此，Reducer中需要整合具有相同鍵的輸出，輸出總的同現次數。
2.3 MapReduce設計
2.3.1 Mapper
2.3.2 Reducer
3 任務3 特征處理：人物關系圖構建與特征歸壹化
3.1 任務描述
根據任務2人物之間的***現關系，生成人物之間的關系圖。人物關系使用鄰接表的形式表示，人物是頂點，人物之間關系是邊，兩個人的關系的密切程度由***現次數體現，***現次數越高，邊權重越高。另外需要對***現次數進行歸壹化處理，確保某個頂點的出邊權重和為1。
3.2 關鍵問題
3.2.1 確保人物的所有鄰居輸出到相同結點處理
在Mapper結點將輸入的鍵值對“<狄雲，戚芳> 1”拆分，輸出新的鍵值對“<狄雲> 戚芳:1”，“狄雲”的所有鄰居會被分配給同壹個Reducer結點處理。
3.2.2 歸壹化
在Reducer結點首先統計該人物與所有鄰居同現的次數和sum，每個鄰居的的同現次數除以sum就得到***現概率。為了提高效率，在第壹次遍歷鄰居的時候，可以把名字和***現次數保存在鏈表裏，避免重復處理字符串。
3.3 MapReduce設計
3.3.1 Mapper
3.3.2 Reducer
4.1 任務描述
經過數據預處理並獲得任務的關系圖之後，就可以對人物關系圖作數據分析，其中壹個典型的分析任務是：PageRank 值計算。通過計算 PageRank，我們就可以定量地獲知金庸武俠江湖中的“主角”們是哪些。
4.2 PageRank原理
PageRank算法由Google的兩位創始人佩奇和布林在研究網頁排序問題時提出，其核心思想是：如果壹個網頁被很多其它網頁鏈接到，說明這個網頁很重要，它的PageRank值也會相應較高；如果壹個PageRank值很高的網頁鏈接到另外某個網頁，那麽那個網頁的PageRank值也會相應地提高。
相應地，PageRank算法應用到人物關系圖上可以這麽理解：如果壹個人物與多個人物存在關系連接，說明這個人物是重要的，其PageRank值響應也會較高；如果壹個PageRank值很高的人物與另外壹個人物之間有關系連接，那麽那個人物的PageRank值也會相應地提高。壹個人物的PageRank值越高，他就越可能是小說中的主角。
PageRank有兩個比較常用的模型：簡單模型和隨機瀏覽模型。由於本次設計考慮的是人物關系而不是網頁跳轉，因此簡單模型比較合適。簡單模型的計算公式如下，其中Bi為所有連接到人物i的集合，Lj為認為人物j對外連接邊的總數：
在本次設計的任務3中，已經對每個人物的邊權值進行歸壹化處理，邊的權值可以看做是對應連接的人物占總邊數的比例。設表示人物i在人物j所有邊中所占的權重，則PageRank計算公式可以改寫為：
4.3.2 PageRanklter類
GraphBuilder將數據處理成可供叠代的格式，PageRank的叠代過程由PageRanklter類實現，包含壹個Map和Reduce過程。Map過程產生兩種類型的<key,value>：<人物名，PageRrank值>，<人物名，關系鏈表>。第壹個人物名是關系鏈表中的各個鏈出人物名，其PR值由計算得到；第二個人物名是本身人物名，目的是為了保存該人物的鏈出關系，以保證完成叠代過程。以上面的輸出為例，則Map過程產生的鍵值對為<完顏萍, 1.0 0.005037>，<小龍女, 1.0 0.017632>，……，<壹燈大師, #完顏萍:0.005037783;……>。
Reduce過程將同壹人物名的<key,value>匯聚在壹起，如果value是PR值，則累加到sum變量；如果value是關系鏈表則保存為List。遍歷完叠代器裏所有的元素後輸出鍵值對<人物名，sum#List>，這樣就完成了壹次叠代過程。
PR值排名不變的比例隨叠代次數變化的關系圖如下，由於我們考慮的是找出小說中的主角，所以只要關心PR值前100名的人物的排名的變化情況，可以看到叠代次數在10以後，PR值排名不變的比例已經趨於穩定了，所以基於效率考慮，選取10作為PR的叠代次數。
4.3.3 PageRankViewer類
當所有叠代都完成後，我們就可以對所有人物的PageRank值進行排序，該過程由PageRankViewer類完成，包含壹個Map和Reduce過程。Map過程只提取叠代過程輸出結果中的人物名以及對應的PageRank值，並以PageRank值作為key，人物名作為value輸出。為了實現PageRank值從大到小排序，需要實現DescFloatComparator類來重寫compare方法以達成逆序排序。由於可能存在PageRank值相同的情況，所以還需要壹個reduce過程來把因PageRank值相同而匯聚到壹起的人物名拆開並輸出。
PageRankMapper
PageRankReducer
Driver類
5.1 任務描述
標簽傳播（Label Propagation）是壹種半監督的圖分析算法，他能為圖上的頂點打標簽，進行圖頂點的聚類分析，從而在壹張類似社交網絡圖中完成社區發現。在人物關系圖中，通過標簽傳播算法可以將關聯度比較大的人物分到同壹標簽，可以直觀地分析人物間的關系。
5.2 標簽傳播算法原理
標簽傳播算法（Label Propagation Algorithm，後面簡稱LPA）是由Zhu等人於2002年提出，它是壹種基於圖的半監督學習方法，其基本思路是用已標記節點的標簽信息去預測未標記節點的標簽信息。LPA基本過程為：（1）每個結點初始化壹個特定的標簽值；（2）逐輪更新所有節點的標簽，直到所有節點的標簽不再發生變化為止。對於每壹輪刷新，節點標簽的刷新規則如下：對於某壹個節點，考察其所有鄰居節點的標簽，並進行統計，將出現個數最多的那個標簽賦值給當前節點。當個數最多的標簽不唯壹時，隨機選擇壹個標簽賦值給當前節點。
LPA與PageRank算法相似，同樣需要通過叠代過程來完成。在標簽傳播算法中，節點的標簽更新通常有同步更新和異步更新兩種方法。同步更新是指，節點x在t時刻的更新是基於鄰接節點在t-1時刻的標簽。異步更新是指，節點x在t時刻更新時，其部分鄰接節點是t時刻更新的標簽，還有部分的鄰接節點是t-1時刻更新的標簽。若LPA算法在標簽傳播過程中采用的是同步更新，則在二分結構網絡中，容易出現標簽震蕩的現象。在本次設計中，我們考慮到了兩種更新方法，並進行了比較。
5.3 標簽傳播算法在mapreduce上的實現細節
5.3.1 LPAInit類
為實現LPA的叠代過程，需要先給每個人物賦予壹個獨特標簽，標簽初始化由LPAInit類完成，僅包含壹個Map過程。標簽由數字表示，Map過程由1開始，為每壹個人物名賦予壹個獨特的標簽。為了便於後面的可視化分析，我們需要把PageRank值和標簽整合在壹起，所以LPAInit的輸入文件直接采用PageRank過程的輸出文件，格式如下：
5.3.2 LPAIteration類
LPAIteration類完成標簽的更新過程，其格式與LPAInit的輸出格式壹致，包含壹個Map和Reduce過程。Map過程對輸入的每壹行進行切割，輸出四種格式的<key,value>：<人物名，關系鏈表>，<人物名，PageRank值>，<人物名，標簽>，<鏈出人物名，標簽#起點人物名>。第四種格式個鍵值對是為了將該節點的標簽傳給其所有鄰居。
Reduce過程對value值進行識別，識別可以通過Map過程把預先定義好的特殊字符如‘#’、‘@’來實現前綴到value上來實現。由於人物關系圖中的各個邊都是有權重的，並且代表兩個人物的相關程度，所以標簽更新過程不是用邊數最多的標簽而是權重最大標簽來更新，我們可以預先把權重最大的若幹個保存到壹個鏈表中，如果存在多個權重相同的標簽，則隨機選取壹個作為該人名新的標簽。異步方法更新標簽需要使用壹個哈希表來存儲已經更新標簽的人物名和它們的新標簽，並且在更新標簽時使用該哈希表裏面的標簽。同步方法更新標簽則不需要存儲已更新的標簽。
本次設計中比較了同步和異步更新兩種方法，下圖為標簽不變的比例隨叠代次數的變化。可以發現，異步收斂速度更快，只要6次叠代即可完全收斂，且標簽不變的比例可達100%。而同步更新方法則不能達到100%，說明人物關系圖中存在子圖是二部子圖。
5.3.3 LPAReorganize類
LPA算法叠代收斂後，所有人物名的標簽不再變化，但是此時的標簽排列是散亂的，需要把同壹標簽的人物名整合在壹起。該過程由LPAReorganize類完成，包含壹個Map和Reduce過程。Map過程對輸入的每壹行進行切割，以<標簽，人物名#PageRank值#關系鏈表>格式輸出。Reduce過程中，同壹標簽的人物名匯聚在壹起，然後根據每個標簽人物集合的大小從大到小排序，重新賦予標簽（從1開始）。這樣輸出文件中同壹標簽的人物名就會聚集在壹起。最後的輸出格式如下：
5.3.2 LPAMapper類
LPAIteration類完成標簽的更新過程，其格式與LPAInit的輸出格式壹致，包含壹個Map和Reduce過程。Map過程對輸入的每壹行進行切割，輸出四種格式的<key,value>：<人物名，關系鏈表>，<人物名，PageRank值>，<人物名，標簽>，<鏈出人物名，標簽#起點人物名>。第四種格式個鍵值對是為了將該節點的標簽傳給其所有鄰居。
5.3.2 LPAReducer類
Reduce過程對value值進行識別，識別可以通過Map過程把預先定義好的特殊字符如‘#’、‘@’來實現前綴到value上來實現。由於人物關系圖中的各個邊都是有權重的，並且代表兩個人物的相關程度，所以標簽更新過程不是用邊數最多的標簽而是權重最大標簽來更新，我們可以預先把權重最大的若幹個保存到壹個鏈表中，如果存在多個權重相同的標簽，則隨機選取壹個作為該人名新的標簽。異步方法更新標簽需要使用壹個哈希表來存儲已經更新標簽的人物名和它們的新標簽，並且在更新標簽時使用該哈希表裏面的標簽。同步方法更新標簽則不需要存儲已更新的標簽。
Driver類
6.1 可視化工具Gephi
Gephi是壹款開源的跨平臺的基於JVM的復雜網絡分析軟件。把PageRank和LPA的結果，轉化為gexf格式，在Gephi中繪制圖像並分析大數據實驗結果，更加直觀、易於理解。
gexf實際上是壹種特殊的XML文件，python的gexf庫提供了接口方便我們編輯和生成gexf文件，因此我們選擇使用python處理PageRank和LPA的結果。頂點有兩種屬性，LPA生成的標簽和PageRank計算的PR值，每條邊的權重是PageRank計算出的值。在可視化的時候，標簽決定頂點顯示的顏色，PR值決定標簽的
6.2 可視化預處理
編寫壹個python程序transform2xml.py，將數據分析部分得到的PR值，標簽以及點連接關系處理成壹個可供Gephi讀取的gexf文件。
6.3 可視化結果
7 輸出結果截圖
7.2 同現次數統計
7.4 PageRank