日志分析往往是商業智能的基礎，而日益增長的日志資訊條目使得大規模資料處理平台的出現成為必然。mapreduce 處理資料的有效性為日志分析提供了可靠的後盾。
本文将以對通路網頁使用者的日志進行分析，進而挖掘出使用者興趣點這一完整流程為例，詳細解釋 mapreduce 模型的對應實作，涵蓋在 mapreduce 程式設計中對于特殊問題的處理技巧，比如機器學習算法、排序算法、索引機制、連接配接機制等。文章分三部分展開：首先介紹 mapreduce 程式設計模型，對其原理、對任務處理流程以及适用情況進行介紹；接下來描述了日志分析的例子 – 使用者興趣點挖掘的處理流程；最後對處理流程的幾個子產品分别進行了 mapreduce 的實作。本文的目的在于通過 mapreduce 在日志分析領域的具體實作，使讀者對 mapreduce 對實際問題的處理有較為形象的認識。
随着資訊化的進一步加深，在各個領域，如電信、交通、金融、零售、航天、醫藥等，資料量級都呈現快速增長趨勢。如何高效并且無誤地存儲、分析、了解以及利用這些大規模資料，成為一個關鍵性問題。
為了應對大規模資料處理的難題，mapreduce 程式設計模型應運而生。google 提出的這一模型，由于良好的易用性和可擴充性，得到了工業界和學術界的廣泛支援。hadoop，mapreduce 的開源實作，已經在 yahoo!, facebook, ibm, 百度 , 中國移動等多家機關中使用。
mapreduce 以函數方式提供了 map 和 reduce 來進行分布式計算。map 相對獨立且并行運作，對存儲系統中的檔案按行處理，并産生鍵值（key/value）對。reduce 以 map 的輸出作為輸入，相同 key 的記錄彙聚到同一 reduce，reduce 對這組記錄進行操作，并産生新的資料集。所有 reduce 任務的輸出組成最終結果。形式化描述如下：
map： (k1,v1) -> list(k2,v2)
reduce：(k2,list(v2)) ->list(v3)
mapreduce 對任務的處理流程如圖 1 所示。主要分為幾步：
使用者送出 mapreduce 程式至主要節點，主要節點将輸入檔案劃分成若幹分片（split）。主要節點 master 和工作節點 worker 啟動相應程序；
主要節點根據工作節點實際情況，進行 map 任務的配置設定；
被配置設定到 map 任務的節點讀取檔案的一個分片，按行進行 map 處理，将結果存在本地。結果分成 r 個分片進行存儲，r 對應的是 reduce 數目；
map 節點将存儲檔案的資訊傳遞給 master 主要節點，master 指定 reduce 任務運作節點，并告知資料擷取節點資訊；
reduce 節點根據 master 傳遞的資訊去 map 節點遠端讀取資料。因為 reduce 函數按分組進行處理，key 相同的記錄被一同處理，在 reduce 節點正式處理前，對所有的記錄按照 key 排序；
reduce 将處理結果寫入到分布式檔案系統中。
由于 mapreduce 程式設計模型是對輸入按行順次處理，它更适用于對批量資料進行處理。由于良好的可擴充性，mapreduce 尤其适用于對大規模資料的處理。
但是，對搜尋等隻是需要從大量資料中選取某幾條特别的操作，mapreduce 相對于具有完善索引的系統而言，不再具有優勢。因為它需要對每條資料進行比對，并與搜尋條件相比對的資料提取出來。而如果采用索引系統，并不需要周遊所有的資料。
另外，由于每次操作需要周遊所有資料，mapreduce 并不适用于需要實時響應的系統。相反地，對于搜尋引擎的預處理工作比如網頁爬蟲、資料清洗，以及日志分析等實時性要求不高的背景處理工作，mapreduce 程式設計模型是足以勝任的。
網際網路或者大型應用系統中，日志的産生和記錄是非常重要的事情。日志分析則是進行資料挖掘進而推進下一步工作的基礎。比如，在購物網站，針對使用者通路網頁的資訊，可以挖掘出使用者的興趣點，進而進行物品推薦；又比如，在應用系統中，通過分析使用者對系統部件的使用情況，可以挖掘出該系統中的熱點部件，進而采取相應的措施加強管理；典型地，對于一個醫療衛生系統，根據醫生對不同病情開處方的日志記錄，可以挖掘出某種病情和藥品的對應關系，進而建立一個專家推薦系統等。
随着網際網路行業的壯大和應用系統規模的擴充，記錄相應資訊的日志數量級也在急劇擴充。傳統的單機版分析程式已經不能滿足日志分析的需求，為此，大規模資料處理平台成為日志分析的理想平台。另一方面，日志分析并沒有很高的實時性要求，mapreduce 程式設計模型由于易用性強、處理資料規模大，成為日志分析的利器。
本文下面部分會以使用者通路網頁日志為例，闡述如何利用 mapreduce 來分析日志，進而挖掘出相應資訊。
一般而言 , 使用者每通路網頁時 , 系統日志中會存儲一條記錄 : 使用者 + url + 通路時間。使用者通路的一系列網頁記錄即是推斷使用者興趣點的基礎，即：使用者 + urlset。
如何根據使用者通路的系列 url 資訊來推測使用者興趣點？一般而言，由以下幾個步驟構成：
單一網頁資訊挖掘。根據 url 得到網頁内容資訊，并對網頁内容進行處理，得到代表此網頁的幾個關鍵詞，一般要借助機器學習算法或者專家經驗來攫取較有價值的詞。
使用者通路關鍵詞資訊彙總。彙總使用者通路的各個 url 中的所有關鍵詞資訊，進而得到使用者關注的關鍵詞清單。每個關鍵詞均有不同權重，視該詞在 url 中出現的次數而定。
關鍵詞擴充及歸約。對使用者關注關鍵詞清單進行一定的擴充或歸約操作，得到更加具有普遍意義的詞資訊，以更好地表征使用者的興趣點。
從 url 得到該網頁中有價值的詞資訊，首先要對 url 進行重新爬取，以得到其對應的網頁内容。從網頁中提取關鍵詞，則需要一定的算法支援。在一篇網頁中，不同詞因為在不同位置或者以不同的格式出現，對應影響程度也不同。比如，在網頁的标題或者網頁内容每一自然段段首或者段尾的詞可能更為重要；在網頁中有特定格式，比如加粗或者字型較大或者标記顔色的詞可能更為重要。
而給定一個詞，如何标記其重要性或者對網頁的價值？可以将每個詞用向量的形式來進行描述，向量中每一次元 d 表示不同的衡量标準，比如 tf（在該網頁中出現的次數）、df（在所有網頁中出現的次數）、是否在标題中出現、是否在段首 / 段尾出現、是否在句首 / 句尾出現、顔色有無差別其它詞、詞的詞性是名詞 / 動詞 / 形容詞 / 助詞，等等。形如 w = (v1, v2, v3, v4, … )，每個次元 v 對詞是網頁關鍵詞的決定程度不同，這個影響因子可以通過機器學習算法訓練而得。即：由事先指定關鍵詞的網頁來進行訓練，得到特征權重。
得到特征權重後，對于網頁中的每個詞，可以通過 w = sum(vi*fi) 的方式來得到其作為關鍵詞的比例。從網頁中選取能代表其内容的幾個詞，應對所有計算出權重的詞按權重從大到小依次排序，選取前幾名或者大于某個門檻值的詞即可。
解決思路如圖 3 所示。
得到每個網頁的代表關鍵詞後，對于使用者通路的關鍵詞，即可通過彙總使用者通路的所有網頁的關鍵詞得到。簡單而言，使用者通路每個詞的次數可以作為該詞為使用者關注詞的權重。因為後面還要進行進一步的關鍵詞擴充 / 歸約，為防止數值過大的情況，可以對權重進行歸一化。當然，也可以再加入其它政策，對詞的權重進行進一步調整，比如通過黑名單或者詞的共現頻率等方式将垃圾詞（對描述使用者興趣點無作用的詞，比如“網易”、“淘寶”等）位置後調，此處不再詳加展開。
關鍵詞擴充
上一步得到的結果是使用者在日志所記錄的時間内通路的關鍵詞彙總，而詞與詞之間往往是互相關聯的。比如，使用者通路了“籃球”這個詞，那實際上該使用者也很有可能對“球星”這個詞感興趣，因為“籃球”和“球星”兩詞存在一定關聯。可以通過關鍵詞擴充，推斷出使用者對“球星”一詞也感興趣。
如何得到兩個詞之間的相關度？一般而言，同時在一個網頁元資訊（meta）的 keyword 域裡的詞很大程度是相關的。是以，統計 meta 中詞，就可以統計出來詞與詞的相關度資訊。因為使用者通路的詞與詞之間并不是孤立完全無關的，而是有一定關聯的。把 meta 中詞與詞的相關性資訊加入到使用者對各個詞的關注度中，可以更好地展現使用者的關注方面。加入 meta 相關詞資訊後，便得到了更加精确的使用者對詞的關注度清單。
網頁 meta 中 keyword 區域放置的往往是該網頁的分類資訊 ( 導航類網頁 )，或者是該網頁的關鍵詞（正文類網頁）。如果是前者，meta 中的詞往往相關度較大。而不同網站的 meta 内容是什麼，是由網站的編輯決定的。是以把不同網站的 meta 裡面共現的詞提取出來并彙總到一起，其實是彙聚了各個網站編輯們的集體智慧。這些詞的共現資訊應該能夠很好地表現出詞與詞之間的相關性。如果兩個詞總在一起出現，它們極有可能是相關的。
具體流程為：首先，統計 meta 中共同出現的詞對以及它們共同出現的次數；然後，統計這些共現的詞對中的詞每個詞出現的次數；最後，應用公式進行共現頻率的計算，得到的就是詞與詞之間的相關度。計算公式為
其中，pij表示詞 i 和詞 j 的相關度，mi、mj、mij分别表示詞 i、詞 j 以及詞 i 和 j 共同在網頁元資訊（meta）的 keyword 中出現的次數。
圖 4 描述了将詞之間的相關度加入使用者通路關鍵詞清單中的流程：首先得到所有詞對之間的相關度資訊，并以索引形式存儲；然後，對之前得到的使用者通路關鍵詞清單中的每個詞，查找索引得到相關的詞，如果該詞未被使用者通路過，直接将其加入到使用者通路清單中；否則，對兩個詞的權重都需進行調整。
關鍵詞歸約
與關鍵詞擴充相對應的是關鍵詞歸約。使用者通路的網頁中挖掘出的關鍵詞往往是具體的，比如使用者關注的網頁中提取出的詞是“足球”、“籃球”，而這些詞在劃分的時候都屬于體育類，通過關鍵詞歸約，可以推測出該使用者對”體育”比較感興趣。
而分類标準應該如何獲得呢？在各大門戶網站如新浪、網易的首頁，都有諸如天氣、新聞、教育、軍事等各大類，在每一大類裡又有各小類；在淘寶、易趣等網上交易平台，更是有對商品的多級詳細分類。關鍵詞歸約，就是根據使用者通路的關鍵詞追溯到使用者對哪些類别的内容感興趣。
無論是關鍵詞擴充還是歸約，都會得到更加精确的使用者通路關鍵詞清單，對所有詞按權重由大到小進行排列，描述的即是使用者的興趣點。
上一部分介紹了使用者興趣點挖掘的流程，本部分将針對各個子產品進行 mapreduce 的實作。整個應用的輸入是使用者通路網頁記錄組成的檔案，檔案每行表示使用者通路網頁的一條記錄，形為：
“使用者 url”。期望輸出為使用者的興趣點檔案，檔案每行存儲每個使用者的興趣點，形為：
“使用者 詞 1 權重 1 詞 2 權重 2 詞 3 權重 3 ”。
下面會對三個步驟分别講解 mapreduce 實作。
單一網頁資訊挖掘的目的是選取出網頁中相對重要的關鍵詞。政策為每個詞賦予權重，并選取權重較大的詞。詞的權重擷取公式 v = sum(vi*fi) 由兩部分決定：該詞在每個特征上的取值和該特征的權重。
每個特征的權重，可由訓練得到，輸入為給出關鍵詞的系列網頁。特征權重訓練通常有特定的算法，比如 scgis 算法，因為訓練集相對于整體的輸入集較小，而算法通常也較複雜，并不适合并行化，可在 mapreduce 任務開始之前進行特征權重訓練。
而詞在每個特征次元上對應的取值，視特征的不同，難易程度也不同。比如詞的出現位置、大小寫、詞性等，在對網頁進行掃描時，可以立即獲得。而 tf( 詞在網頁中出現的次數 )、df（詞在所有網頁中出現的次數）等特征并不能随詞出現時立即擷取，但由于每個詞處理的程式都相同，是以可以使用 mapreduce 程式設計模型并行化。下面進行具體講述。
單一網頁資訊挖掘部分的 mapreduce 流程如圖 5 所示。
tf 詞在網頁中出現次數資訊統計
map：輸入為使用者 +url 清單，對于單條記錄，進行 url 爬蟲和分詞，得到使用者通路的該網頁中包含所有詞的資訊。每遇到一個詞，map 進行一次輸出，key 為使用者 + 網頁 + 詞，value 為 1。當然，此時 map 還可以統計其它資訊，比如詞性（名詞 / 動詞）等，為簡化描述，此處不再詳加展開。
reduce：map 輸出結果中 key 相同的彙聚到一起，reduce 對每組統計其包含記錄條數，将使用者 + 網頁 + 詞仍然作為 key 進行輸出，将每組中記錄條數作為 value 進行輸出。
這樣，reduce 的輸出結果檔案每行對應記錄為“ 使用者 + 網頁 + 詞 詞的 tf”。
如果網頁中内容足以在記憶體中處理，也可以隻在 map 階段完成對每個詞 tf 的統計，這樣可以省去 map 和 reduce 之間大量資料傳輸的時間消耗。具體處理思路為：采用一個資料結構 hashmap<string, value>，map 的每行輸入仍為使用者 +url 資訊，對 url 網頁爬蟲的結果，每遇到一個詞，将其資訊加入到 hashmap 中，key 為詞，value 為原來 value+1，與此同時，還可以統計該詞的其餘特征值，比如詞性等。因為 map 階段即可完成 tf 統計，可以将 reduce 數目設為 0。
df 詞在所有網頁中出現次數資訊統計
map 輸入為 tf 計算階段輸出，key 為使用者 + 網頁 + 詞，value 為詞的 tf。map 階段處理，将網頁資訊去除，輸出 key 為使用者 + 詞，輸出 value 為 1。
reduce 以 map 輸出為輸入，使用者通路詞相同的會被同一個 reduce 處理，reduce 中統計該組包含記錄的數目，即是詞的 df。由于在計算每個詞權重時，需要得到各個特征的值，而在計算 tf 的時候可以得到該詞除 df 外其它特征的資訊，是以需要額外地擷取 df 資訊。為友善查詢 df 的資訊，應将 reduce 階段的輸出以索引檔案的形式進行輸出。lucene 是可在 mapreduce 開源架構 hadoop 上部署的索引機制，可在 reduce 輸出時采用，key 為使用者 + 詞，value 為 df。
在清單 3 中出現的 lucenedocumentwrapper 和 luceneoutputformat 均是為在 mapreduce 上使用 lucene 索引檔案作為 map/reduce 輸出添加的類，兩者分别繼承自 writablecomparable 和 fileoutputformat。清單 4 提供了兩者的定義。
網頁關鍵詞計算
獲得 df 資訊後，即可在一個新的 map 過程中對網頁中每個詞計算其權重，即成為網頁關鍵詞的機率，此處可以指定一個門檻值，若機率大于該門檻值，認為該詞可以代表網頁，将其輸出；否則忽略。
在使用者關鍵詞彙總子產品，一共需要兩個完整的 reduce，流程圖如圖 6 所示。
使用者通路詞次數彙總
經過單一網頁資訊挖掘子產品的處理，對每個網頁處理完畢，輸出的記錄形為“使用者 + 網頁關鍵詞”，是以隻需經過一個 reduce 就能統計出使用者通路每個詞的次數。為友善後續對每個使用者的關注詞進行彙總處理，本 reduce 的輸出 key 為使用者，value 為詞 + 使用者通路該詞的次數。
使用者通路詞按次數排序
第二個 reduce 的輸入為第一個 reduce 的輸出，在本 reduce 中，同一使用者通路的詞會被彙聚到一起，為了更好地描述使用者的興趣點，應對所有詞按通路次數進行從大到小進行排序，可以通過 reduce 内部對成熟排序算法，比如快速排序的調用來實作。
詞權重歸一化
因為不同詞的通路次數可能差距較大，比如最常見詞通路 20 次，而次常見詞可能通路 10 次，如此大的差距并不利于對詞權重的進一步調整。是以采用資料挖掘領域常見的歸一化政策來對詞權重進行調整，将其調整到 [0，1] 區間内。最簡單的政策是将最常見詞的通路次數去除通路每個詞的次數。weight（w）=times（w）/times（max）。這個權重歸一化的過程同樣可以在第二個 reduce 過程中完成。
mapreduce 自身對排序的支援
實際上，mapreduce 本身的機制也可以實作排序功能。資料從 map 方法輸出到 reduce 方法輸入是要經過幾個步驟的，包括：map 端根據 reduce 數目對本地輸出進行分組；map 和 reduce 之間的資料傳輸 shuffle；reduce 端對來自多個 map 的資料按 key 進行排序并分組，每組傳入給 reduce 方法進行處理。
從這個過程可以看出，同一個 reduce 處理的資料實際上是按照 key 排序的，如果将 reduce 數目設為 1(job.setreducenum(1))，并将排序基準字段在 map 方法中設為 key，就可以實作資料的全局排序。
關鍵詞擴充和歸約對使用者通路詞清單進行的兩個不同方向的調整，本節詳細介紹一個方向，對關鍵詞擴充進行展開。
詞與詞相關度資訊擷取
關鍵詞擴充的關鍵是得到詞與詞的相關度，并基于此相關度對使用者通路詞清單進行調整。詞與詞之間相關度的計算公式已在前面小節列出。
圖 7 展示了 mapreduce 計算 pij的流程。
統計詞對共現次數
map：以使用者通路 url 資訊為輸入，在 map 内部進行網頁爬蟲，并隻爬取網頁的 meta 中 keyword 域的詞資訊，每個網頁中對應的詞兩兩組成詞對進行輸出，詞對中第一個詞的拼音序 / 字母序要優于第二個詞。輸出 key 為詞 1+ 詞 2，value 為 1。
reduce 統計詞 i 和詞 j 共同出現的次數 mij，在 reduce 内部統計每組包含記錄的數目，仍然以詞 1+ 詞 2 作為 key，将共現次數作為 value 進行輸出。
統計單個詞出現次數
為計算詞與詞的相關度，除獲得兩詞共現次數外，還應獲得每個詞的出現次數。可以通過一個額外的 map/reduce 來進行統計。其中，map 以第一個 reduce 的輸出為輸入，對每個詞對 i 和 j，輸出兩條記錄，key 分别為詞 i 和詞 j，value 均為兩詞共現次數 ;reduce 完成詞次數的統計。
計算詞對相關度
現在有兩個檔案：一個檔案中記錄的是單個詞出現的次數；另一檔案記錄的則是詞對出現的次數。如何從這兩個檔案得到詞與詞的相關度？最直覺的思路是将單個詞出現次數作為索引檔案輸出，key 為詞，value 為詞的次數；再執行一個 map，以第詞對共現次數檔案為輸入，在處理每條記錄時，查詢索引檔案兩次，然後按照共現頻率公式計算得到結果。
mapreduce 中的連接配接 — 合并資料集的政策
當詞資訊檔案較大，查詢 lucene 索引檔案的效率也會降低，因為對每個詞對，都要查找兩次詞的索引檔案，是以查找索引檔案的次數量級在 o（n2），查詢代價也會相對較大。可以用另外一種政策完成詞對相關度的計算。将兩個檔案同時作為 map 的輸入，在 map 内部判斷記錄來自于哪個檔案，進行對應處理，在 reduce 中完成資料集的合并。圖 8 展示了對應流程。
第 1 個 map-reduce 合并單個詞次數檔案和詞對次數檔案。
map 輸入來自兩個不同檔案：單個詞次數檔案和詞對共現次數檔案。map 内部對來自兩個檔案的記錄進行不同操作，最後拼成相同格式進行輸出。輸出的 key 為單個詞，value 形如 “第二個詞 + 共現次數 \t 單個詞次數”。沒有的部分，以空字元補齊。這樣，對于第一種情況，value 中以 \t 相隔的第一部分就是空字元；而對于第二種情況，value 中以 \t 相隔的第二部分為空字元。
reduce 周遊疊代器中記錄，對第一部分為空字元的，将 key 詞對應次數提取出來，否則，記錄對應的是與該詞相關的其他詞及共現次數資訊，把這些資訊放到一個數組。周遊完畢，對數組中每個元素，進行輸出，輸出 key 為詞 1+ 詞 2+ 共現次數 ( 字典序在前的詞在前 )，value 為 reduce 輸入 key 詞（詞 1 或者詞 2）的次數資訊。
第 2 個 map-reduce 計算共現頻率。
含有一個 reduce，輸入為上一 map-reduce 的輸出，key 為詞 1+ 詞 2+ 共現次數，value 為單個詞的次數。疊代器裡分别得到兩個詞的次數資訊，然後運用共現頻率公式計算兩個詞的相關度。reduce 的輸出 key 為詞 1+ 詞 2，value 為兩個詞的共現頻率。
第 3 個 map-reduce 建立詞相關度資訊索引檔案。
第 3 個 map-reduce 得到每個詞的相關詞資訊，并建立索引檔案。lucene 索引檔案的兩個域分别為“word”和“corrinfo”。
map 的輸入 key 為詞 1+ 詞 2，value 為相關度。map 将詞 1 和詞 2 拆開進行輸出。輸出 key 為詞 1，value 為詞 2+ 相關度；輸出 key 為詞 2，value 為詞 1+ 相關度。
reduce 把 key 相同的彙聚到一起，并把疊代器中的詞及關注度資訊拼在一起，形成一個字元串，作為 corrinfo 域的内容。
使用者通路詞清單調整
獲得詞對相關度後，即可以對使用者通路關鍵詞清單進行擴充。如圖 9 所示，隻需一個 map 即可完成操作。map 以使用者通路詞清單為輸入，key 為使用者，value 為關鍵詞清單。對于關鍵詞清單中的每個詞 a，都會查找詞相關度索引檔案，得到與詞 a 相關的詞清單 al。周遊 al，如果 al中的詞 b 也被使用者通路過，那麼要将使用者通路詞 b 的值× a 和 b 的相關度的結果加入到 a 的舊值上；如果 al中的詞 c 使用者沒有通路過，則要把詞 c 加入到使用者通路詞清單中，并将詞 a 的舊值× a 和 c 的相關度加入到詞 c 值上。map 的輸出 key 仍為使用者，value 為使用者通路的詞清單及對應的新的關注度值。
mapreduce 程式設計模型由于其強大的計算能力、良好的可擴充性和易用性，在工業界和學術界得到了廣泛使用。對大規模資料批量處理的特點，使得 mapreduce 尤其适用于日志分析類應用。mapreduce 程式設計模型的基礎是 map 和 reduce 函數，如何将應用全部或者部分轉換到這兩類計算模式，即将應用并行化，是有一定技巧的。本文對使用者興趣點挖掘應用進行 mapreduce 的實作，除在資料挖掘領域提出見解，mapreduce 的實作方式也為使用者進行應用并行化提供了參考。
轉自：http://www.ibm.com/developerworks/cn/java/java-lo-mapreduce/