亞寵展、全球寵物產業風向標——亞洲寵物展覽會深度解析
1211
2022-12-28
本文目錄一覽:
通過一個綜合數據分析案例:”金庸的江湖——金庸武俠小說中的人物關系挖掘“,來學習和掌握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上來實現。由于人物關系圖中的各個邊都是有權重的,并且代表兩個人物的相關程度,所以標簽更新過程不是用邊數最多的標簽而是權重最大標簽來更新,我們可以預先把權重最大的若干個保存到一個鏈表中,如果存在多個權重相同的標簽,則隨機選取一個作為該人名新的標簽。異步方法更新標簽需要使用一個哈希表來存儲已經更新標簽的人物名和它們的新標簽,并且在更新標簽時使用該哈希表里面的標簽。同步方法更新標簽則不需要存儲已更新的標簽。
本次設計中比較了同步和異步更新兩種方法,下圖為標簽不變的比例隨迭代次數的變化??梢园l現,異步收斂速度更快,只要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
版權聲明:本文內容由網絡用戶投稿,版權歸原作者所有,本站不擁有其著作權,亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容,請聯系我們jiasou666@gmail.com 處理,核實后本網站將在24小時內刪除侵權內容。