1、大數據的處理和分析大數據的處理和分析計算機科學導論第十講計算機科學導論第十講計算機科學技術學院計算機科學技術學院陳意云陳意云0551-課課 程程 內內 容容 課程內容課程內容（本次講座與下述內容關系不大）（本次講座與下述內容關系不大）圍繞學科理論體系中的模型理論圍繞學科理論體系中的模型理論, 程序理論和計算理論程序理論和計算理論1. 模型理論關心的問題模型理論關心的問題 給定模型給定模型m，哪些問題可以由模型，哪些問題可以由模型m解決；如何解決；如何比較模型的表達能力比較模型的表達能力2. 程序理論關心的問題程序理論關心的問題 給定模型給定模型m，如何用模型，如何用模型m解決問題解決問題 包括

2、程序設計范型、程序設計語言、程序設計、包括程序設計范型、程序設計語言、程序設計、形式語義、類型論、程序驗證、程序分析等形式語義、類型論、程序驗證、程序分析等3. 計算理論關心的問題計算理論關心的問題給定模型給定模型m和一類問題和一類問題, 解決該類問題需多少資源解決該類問題需多少資源講講 座座 提提 綱綱 大數據的魅力大數據的魅力 數據挖掘、大數據、大數據案例、大數據的特點數據挖掘、大數據、大數據案例、大數據的特點 大數據時代的思維變革大數據時代的思維變革 樣本和全體、精確性和混雜性、因果關系和相關樣本和全體、精確性和混雜性、因果關系和相關關系關系 大數據的處理大數據的處理 幾種主要處理方式、

3、幾種主要處理方式、mapreduce編程模型編程模型 大數據的分析大數據的分析 關鍵技術概述、關鍵技術概述、pagerank初步初步 數據挖掘數據挖掘 數據挖掘的定義數據挖掘的定義1. 從數據中提取出隱含的過去未知的有價值的潛從數據中提取出隱含的過去未知的有價值的潛在信息在信息2. 從大量數據或者數據庫中提取有用信息的科學從大量數據或者數據庫中提取有用信息的科學 相關概念：知識發現相關概念：知識發現1. 數據挖掘是知識發現過程中的一步數據挖掘是知識發現過程中的一步2. 粗略看：數據預處理粗略看：數據預處理數據挖掘數據挖掘數據后處理數據后處理預處理預處理: 將未加工輸入數據轉換為適合處理的形式將

4、未加工輸入數據轉換為適合處理的形式后處理后處理: 如可視化如可視化, 便于從不同視角探查挖掘結果便于從不同視角探查挖掘結果大數據的魅力大數據的魅力 數據挖掘數據挖掘 典型事例：購物籃分析典型事例：購物籃分析顧客顧客一次購買商品一次購買商品 1面包、黃油、面包、黃油、尿布尿布、牛奶牛奶 2咖啡、糖、小甜餅、鮭魚咖啡、糖、小甜餅、鮭魚 3面包、黃油、咖啡、面包、黃油、咖啡、尿布尿布、牛奶牛奶、雞蛋、雞蛋 4面包、黃油、鮭魚、雞面包、黃油、鮭魚、雞 5雞蛋、面包、黃油雞蛋、面包、黃油 6鮭魚、鮭魚、尿布尿布、牛奶牛奶 7面包、茶葉、糖、雞蛋面包、茶葉、糖、雞蛋 8咖啡、糖、雞、雞蛋咖啡、糖、雞、雞蛋

5、 9面包、面包、尿布尿布、牛奶牛奶、鹽、鹽10茶葉、雞蛋、小甜餅、茶葉、雞蛋、小甜餅、尿布尿布、牛奶牛奶經關聯分析，可發現顧客經常同時購買的商品：尿布經關聯分析，可發現顧客經常同時購買的商品：尿布牛奶牛奶大數據的魅力大數據的魅力 大數據大數據 大數據大數據，或稱海量數據或稱海量數據，指所涉及的數據量規模指所涉及的數據量規模巨大到無法通過人工，在合理時間內達到截取、巨大到無法通過人工，在合理時間內達到截取、管理、處理、并整理成為人類所能解讀的信息管理、處理、并整理成為人類所能解讀的信息 在總數據量相同的情況下，與個別分析獨立的小在總數據量相同的情況下，與個別分析獨立的小型數據集相比，將各個小型數

6、據集合并后進行分型數據集相比，將各個小型數據集合并后進行分析可得出許多額外的信息和數據關系性，可用來析可得出許多額外的信息和數據關系性，可用來察覺商業趨勢、避免疾病擴散、打擊犯罪、測定察覺商業趨勢、避免疾病擴散、打擊犯罪、測定實時交通路況或判定研究質量等實時交通路況或判定研究質量等 這樣的用途正是大型數據集盛行的原因這樣的用途正是大型數據集盛行的原因 數據挖掘則是探討用以解析大數據的方法數據挖掘則是探討用以解析大數據的方法大數據的魅力大數據的魅力 大數據案例大數據案例谷歌預測冬季流感的傳播谷歌預測冬季流感的傳播 2009年出現了一種稱為甲型年出現了一種稱為甲型h1n1的新流感病毒，的新流感病毒

7、，在短短幾周內迅速傳播開來，全球的公共衛生機在短短幾周內迅速傳播開來，全球的公共衛生機構都擔心一場致命的流行病即將來襲構都擔心一場致命的流行病即將來襲 美國也要求醫生在發現甲型美國也要求醫生在發現甲型h1n1病例時告知疾病病例時告知疾病控制與預防中心。但人們從患病到求醫會滯后，控制與預防中心。但人們從患病到求醫會滯后，信息傳到疾控中心也需要時間，因此通告新病例信息傳到疾控中心也需要時間，因此通告新病例往往有一兩周的延遲。而且疾控中心每周只進行往往有一兩周的延遲。而且疾控中心每周只進行一次數據匯總一次數據匯總 信息滯后兩周對一種飛速傳播的疾病是致命的，信息滯后兩周對一種飛速傳播的疾病是致命的，它

8、使得公共衛生機構在疫情爆發的關鍵時期難以它使得公共衛生機構在疫情爆發的關鍵時期難以有效發揮作用有效發揮作用大數據的魅力大數據的魅力 大數據案例大數據案例谷歌預測冬季流感的傳播谷歌預測冬季流感的傳播 在這種流感爆發的幾周前，谷歌的工程師在在這種流感爆發的幾周前，谷歌的工程師在自自然然雜志發表引人注目的論文，令公共衛生官員雜志發表引人注目的論文，令公共衛生官員和計算機科學家感到震驚和計算機科學家感到震驚 因為文章不僅預測了流感在全美的傳播，而且具因為文章不僅預測了流感在全美的傳播，而且具體到特定的地區和州體到特定的地區和州 谷歌是通過觀察人們在網上的搜索記錄來完成這谷歌是通過觀察人們在網上的搜索記

9、錄來完成這個預測的，這種方法以前一直是被忽略的個預測的，這種方法以前一直是被忽略的 谷歌保存了多年來所有的搜索記錄谷歌保存了多年來所有的搜索記錄, 每天有來自全每天有來自全球球30億條搜索指令億條搜索指令(僅谷歌有這樣的數據資源僅谷歌有這樣的數據資源),如如此龐大數據資源足以支撐和幫助它完成這項工作此龐大數據資源足以支撐和幫助它完成這項工作大數據的魅力大數據的魅力大數據的魅力大數據的魅力 大數據案例大數據案例谷歌預測冬季流感的傳播谷歌預測冬季流感的傳播 原理十分簡單原理十分簡單現在大家都有上網搜索信息的習慣，連頭痛感冒現在大家都有上網搜索信息的習慣，連頭痛感冒也上網搜索，谷歌流感趨勢項目通過記

10、錄搜索有也上網搜索，谷歌流感趨勢項目通過記錄搜索有關關“流感流感”詞條的地區和頻率，并分析其與流感詞條的地區和頻率，并分析其與流感在時間和空間上的傳播之間的聯系，追蹤到流感在時間和空間上的傳播之間的聯系，追蹤到流感廣泛傳播的地區，進而預測流感可能爆發的高危廣泛傳播的地區，進而預測流感可能爆發的高危地區。即當某地區在網上搜尋與流感有關信息的地區。即當某地區在網上搜尋與流感有關信息的人日益增多，很可能意味著該地區有許多人患上人日益增多，很可能意味著該地區有許多人患上流感類疾病流感類疾病 因為流感趨勢項目能夠近乎實時地估計流感活動因為流感趨勢項目能夠近乎實時地估計流感活動情況，故它比其他系統能夠更早

11、地發現流感疫情情況，故它比其他系統能夠更早地發現流感疫情大數據的魅力大數據的魅力 大數據案例大數據案例谷歌預測冬季流感的傳播谷歌預測冬季流感的傳播 谷歌把谷歌把5000萬條美國人最頻繁檢索的詞條與疾控萬條美國人最頻繁檢索的詞條與疾控中心在中心在2003年到年到2008年間季節性流感傳播期間的年間季節性流感傳播期間的數據進行比較，以確定相關檢索詞條，并總共處數據進行比較，以確定相關檢索詞條，并總共處理了理了4.5億億(?)個不同的數學模型個不同的數學模型 在把得出的預測與在把得出的預測與2007年和年和2008年美國疾控中心年美國疾控中心記錄的實際流感病例進行對比后，篩選了記錄的實際流感病例進行

12、對比后，篩選了45條檢條檢索詞條的組合，并把它們用于一個特定的數學模索詞條的組合，并把它們用于一個特定的數學模型后，其預測與官方數據相關性高達型后，其預測與官方數據相關性高達97% 因此當因此當2009年甲型年甲型h1n1流感爆發時，與滯后的官流感爆發時，與滯后的官方數據相比，谷歌成為一個更有效及時的指示者方數據相比，谷歌成為一個更有效及時的指示者大數據的魅力大數據的魅力 大數據案例大數據案例谷歌預測冬季流感的傳播谷歌預測冬季流感的傳播 這是當今社會所獨有的一種新型能力：以一種前這是當今社會所獨有的一種新型能力：以一種前所未有的方式，通過對海量數據的分析，獲得巨所未有的方式，通過對海量數據的分

13、析，獲得巨大價值的產品和服務，或深刻的洞見大價值的產品和服務，或深刻的洞見 大數據不僅會變革公共衛生，也會變革商業、變大數據不僅會變革公共衛生，也會變革商業、變革思維，改變政府與民眾關系的方法，革思維，改變政府與民眾關系的方法， ，開啟，開啟重大的時代轉型重大的時代轉型大數據的魅力大數據的魅力 大數據的特點大數據的特點 體量巨大體量巨大(volume) 數據集合的規模不斷擴大，數據集合的規模不斷擴大，已從已從gb(1024mb)到到tb(1024gb)再到再到pb級，甚至級，甚至已經開始以已經開始以eb和和zb來計數。至今，人類生產的來計數。至今，人類生產的所有印刷材料的數據量是所有印刷材料的

14、數據量是200pb。未來。未來10年，全年，全球大數據將增加球大數據將增加50倍，管理數據倉庫的服務器的倍，管理數據倉庫的服務器的數量將增加數量將增加10倍倍 類型繁多類型繁多(variety) 數據種類繁多，并且被分為結數據種類繁多，并且被分為結構化、半結構化和非結構化的數據。半結構化和構化、半結構化和非結構化的數據。半結構化和非結構化數據，包括傳感器數據、網絡日志、音非結構化數據，包括傳感器數據、網絡日志、音頻、視頻、圖片、地理位置信息等，占有量越來頻、視頻、圖片、地理位置信息等，占有量越來越大，已遠遠超過結構化數據越大，已遠遠超過結構化數據大數據的魅力大數據的魅力 大數據的特點大數據的特

15、點 價值密度低價值密度低(value)。 數據總體的價值巨大，但價數據總體的價值巨大，但價值密度很低。以視頻為例，在長達數小時連續不值密度很低。以視頻為例，在長達數小時連續不斷的視頻監控中，有用數據可能僅一二秒。另一斷的視頻監控中，有用數據可能僅一二秒。另一極端是各數據都有貢獻，但單個數據價值很低極端是各數據都有貢獻，但單個數據價值很低 速度快速度快(velocity)。 數據往往以數據流的形式動態數據往往以數據流的形式動態快速地產生，具有很強的時效性，用戶只有把握快速地產生，具有很強的時效性，用戶只有把握好對數據流的掌控才能有效利用這些數據。例如好對數據流的掌控才能有效利用這些數據。例如，一

16、天之內需要審查，一天之內需要審查500萬起潛在的貿易欺詐案件萬起潛在的貿易欺詐案件；需要分析；需要分析5億條日實時呼叫的詳細記錄，以預測億條日實時呼叫的詳細記錄，以預測客戶的流失率客戶的流失率大數據時代的思維變革大數據時代的思維變革數據采集和數據處理技術已經發生了翻天數據采集和數據處理技術已經發生了翻天覆地的變化，人們的思維和方法要跟得上這覆地的變化，人們的思維和方法要跟得上這個變化個變化大數據時代的精髓在于人們分析信息時的大數據時代的精髓在于人們分析信息時的三個轉變，這些轉變將改變人們決策的制定三個轉變，這些轉變將改變人們決策的制定和對表象的理解和對表象的理解大數據時代的思維變革大數據時代的

17、思維變革 變革一變革一 更多更多: 不是隨機樣本不是隨機樣本, 而是全體數據而是全體數據1. 隨機抽樣：用最少的數據獲得最多的信息隨機抽樣：用最少的數據獲得最多的信息 過去由于獲取和分析全體數據的困難，抽樣調查過去由于獲取和分析全體數據的困難，抽樣調查是一種常用統計分析方法。它根據隨機原則從總是一種常用統計分析方法。它根據隨機原則從總體中抽取部分實際數據進行調查，并運用概率估體中抽取部分實際數據進行調查，并運用概率估計方法，根據樣本數據推算總體相應的數量指標計方法，根據樣本數據推算總體相應的數量指標 抽樣分析的精確性隨抽樣隨機性的增加而提高，抽樣分析的精確性隨抽樣隨機性的增加而提高，與樣本數量

18、的增加關系不大。抽樣隨機性高時，與樣本數量的增加關系不大。抽樣隨機性高時，分析的精度能達到把全體作為樣本調查時的分析的精度能達到把全體作為樣本調查時的97% 樣本選擇的隨機性比樣本數量更重要樣本選擇的隨機性比樣本數量更重要大數據時代的思維變革大數據時代的思維變革 變革一變革一 更多更多: 不是隨機樣本不是隨機樣本, 而是全體數據而是全體數據1. 隨機抽樣：用最少的數據獲得最多的信息隨機抽樣：用最少的數據獲得最多的信息 抽樣分析的成功依賴于抽樣的隨機性，但實現抽抽樣分析的成功依賴于抽樣的隨機性，但實現抽樣的隨機性非常困難樣的隨機性非常困難 當想了解更深層次的細分領域的情況時，隨機抽當想了解更深層

19、次的細分領域的情況時，隨機抽樣方法不一定有效，即在宏觀領域起作用的方法樣方法不一定有效，即在宏觀領域起作用的方法在微觀領域可能失去了作用在微觀領域可能失去了作用 隨機抽樣需要嚴密的安排和執行，人們只能從抽隨機抽樣需要嚴密的安排和執行，人們只能從抽樣數據中得出事先設計好的問題的結果樣數據中得出事先設計好的問題的結果大數據時代的思維變革大數據時代的思維變革 變革一變革一 更多更多: 不是隨機樣本不是隨機樣本, 而是全體數據而是全體數據2. 全體數據：用全體數據可對數據進行深度探討全體數據：用全體數據可對數據進行深度探討 流感趨勢預測分析了整個美國幾十億條互聯網檢流感趨勢預測分析了整個美國幾十億條互

20、聯網檢索記錄，使得它能提高微觀層面分析的準確性，索記錄，使得它能提高微觀層面分析的準確性，甚至能夠推測某個特定城市的流感狀況甚至能夠推測某個特定城市的流感狀況 信用卡詐騙需通過觀察異常情況來識別，這只有信用卡詐騙需通過觀察異常情況來識別，這只有在掌握所有的數據時才能做到在掌握所有的數據時才能做到 社會科學是被社會科學是被“樣本樣本=全體全體”撼動得最厲害的一門撼動得最厲害的一門學科。這門學科過去非常依賴于樣本分析、研究學科。這門學科過去非常依賴于樣本分析、研究和調查問卷。當記錄下人們的平常狀態，就不用和調查問卷。當記錄下人們的平常狀態，就不用擔心在做研究和調查問卷時存在的偏見了擔心在做研究和調

21、查問卷時存在的偏見了大數據時代的思維變革大數據時代的思維變革 變革二變革二 更雜：不是精確性，更雜：不是精確性， 而是混雜性而是混雜性 對小數據而言，最基本和最重要的要求就是減少對小數據而言，最基本和最重要的要求就是減少錯誤，保證質量。因為收集的數據較少，應確保錯誤，保證質量。因為收集的數據較少，應確保每個數據盡量精確，以保證分析結果的準確性每個數據盡量精確，以保證分析結果的準確性 允許不精確數據是大數據的一個亮點允許不精確數據是大數據的一個亮點, 而非缺點。而非缺點。因為放松了容錯的標準，就可以掌握更多數據，因為放松了容錯的標準，就可以掌握更多數據，而掌握大量新型數據時，精確性就不那么重要了

22、而掌握大量新型數據時，精確性就不那么重要了 例如，與服務器處理投訴時的數據進行比較，用例如，與服務器處理投訴時的數據進行比較，用語音識別系統識別呼叫中心接到的投訴會產生不語音識別系統識別呼叫中心接到的投訴會產生不太準確的結果太準確的結果, 但它有助于把握事情的大致情況但它有助于把握事情的大致情況 不精確的大量新型數據能幫助掌握事情發展趨勢不精確的大量新型數據能幫助掌握事情發展趨勢大數據時代的思維變革大數據時代的思維變革 變革二變革二 更雜：不是精確性，更雜：不是精確性， 而是混雜性而是混雜性 執迷于精確性是信息缺乏時代的產物，大數據時執迷于精確性是信息缺乏時代的產物，大數據時代要求重新審視精確

23、性的優劣，如果將傳統的思代要求重新審視精確性的優劣，如果將傳統的思維模式運用于數字化、網絡化的維模式運用于數字化、網絡化的21世紀，就會錯世紀，就會錯過重要信息，失去做更多事情，創造出更好結果過重要信息，失去做更多事情，創造出更好結果的機會的機會 另一方面，需要與數據增加引起的各種混亂（數另一方面，需要與數據增加引起的各種混亂（數據格式不一致，數據錯誤率增加等）做斗爭。錯據格式不一致，數據錯誤率增加等）做斗爭。錯誤并不是大數據的固有特性，但可能是長期存在誤并不是大數據的固有特性，但可能是長期存在并需要去處理的現實問題并需要去處理的現實問題大數據時代的思維變革大數據時代的思維變革 變革三變革三

24、更好更好: 不是因果關系不是因果關系, 而是相關關系而是相關關系1. 因果關系與相關關系因果關系與相關關系 因果關系是指一個事件是另一個事件的結果因果關系是指一個事件是另一個事件的結果 相關關系是指兩個事件的發生存在某個規律相關關系是指兩個事件的發生存在某個規律 與通過邏輯推理研究因果關系不同，大數據研究與通過邏輯推理研究因果關系不同，大數據研究通過統計性的搜索、比較、聚類、分析和歸納，通過統計性的搜索、比較、聚類、分析和歸納，尋找事件（或數據）之間的相關性尋找事件（或數據）之間的相關性 一般來說，統計學無法檢驗邏輯上的因果關系一般來說，統計學無法檢驗邏輯上的因果關系 也許正因為統計方法不致力

25、于尋找真正的原因也許正因為統計方法不致力于尋找真正的原因, 才才促進數據挖掘和大數據技術在商業領域廣泛應用促進數據挖掘和大數據技術在商業領域廣泛應用大數據時代的思維變革大數據時代的思維變革 變革三變革三 更好更好: 不是因果關系不是因果關系, 而是相關關系而是相關關系2. 相關關系幫助捕捉現在和預測未來相關關系幫助捕捉現在和預測未來 如果如果a和和b經常一起發生，則只需注意到經常一起發生，則只需注意到b發生了發生了, 就可以預測就可以預測a也發生了也發生了 故障經常是慢慢出現的，通過收集所有數據，可故障經常是慢慢出現的，通過收集所有數據，可預先捕捉到事物要出故障的信號。如將發動機的預先捕捉到事

26、物要出故障的信號。如將發動機的嗡嗡聲、引擎過熱等異常情況與正常情況對比，嗡嗡聲、引擎過熱等異常情況與正常情況對比，就能知道什么地方將出毛病，及時更換或修復就能知道什么地方將出毛病，及時更換或修復 過去需先有想法，然后收集數據來測試想法的可過去需先有想法，然后收集數據來測試想法的可行性，現在可以對大數據進行相關關系分析知道行性，現在可以對大數據進行相關關系分析知道機票是否會飛漲、哪些詞條最能顯示流感的傳播機票是否會飛漲、哪些詞條最能顯示流感的傳播大數據時代的思維變革大數據時代的思維變革 變革三變革三 更好更好: 不是因果關系不是因果關系, 而是相關關系而是相關關系3. 大數據改變人類探索世界的方

27、法大數據改變人類探索世界的方法 越來越多的事物不斷地數據化，將拓展人類的視越來越多的事物不斷地數據化，將拓展人類的視野，使得人們可從大量的數據中，發現隱藏在其野，使得人們可從大量的數據中，發現隱藏在其中的自然規律、社會規律和經濟規律中的自然規律、社會規律和經濟規律 當網頁變成數據，谷歌具備了令人大跌眼球的全當網頁變成數據，谷歌具備了令人大跌眼球的全文搜索能力，在幾個毫秒之內，就能讓人們檢索文搜索能力，在幾個毫秒之內，就能讓人們檢索世界上幾乎所有的網頁世界上幾乎所有的網頁 當方位變成數據，每個人都能借助當方位變成數據，每個人都能借助gps 快速到達快速到達目的地目的地大數據時代的思維變革大數據時

28、代的思維變革 變革三變革三 更好更好: 不是因果關系不是因果關系, 而是相關關系而是相關關系3. 大數據改變人類探索世界的方法大數據改變人類探索世界的方法 當情緒變成數據，人們甚至根據大家快樂與否判當情緒變成數據，人們甚至根據大家快樂與否判斷股市的漲跌斷股市的漲跌 上述這些不同的數據可歸結為幾類相似的數學模上述這些不同的數據可歸結為幾類相似的數學模型，從而使得型，從而使得“數據科學數據科學”（應用數據學習知識（應用數據學習知識的學科）成為一門具備普遍適用的學科的學科）成為一門具備普遍適用的學科 生物信息學、計算社會學、天體信息學、電子工生物信息學、計算社會學、天體信息學、電子工程、金融學、經濟

29、學等學科，都依賴數據科學的程、金融學、經濟學等學科，都依賴數據科學的發展發展大數據的處理大數據的處理 大數據處理的幾種主要方式大數據處理的幾種主要方式 海量數據的處理對于當前的技術來說是一種極大海量數據的處理對于當前的技術來說是一種極大的挑戰，目前大數據的主要處理形式如下：的挑戰，目前大數據的主要處理形式如下： 靜態數據的批量處理靜態數據的批量處理 數據體量巨大、精確度高、價值密度低；數據體量巨大、精確度高、價值密度低；挖掘合挖掘合適模式、得出具體含義、制定明智決策、適模式、得出具體含義、制定明智決策、；用于；用于社交網絡、電子商務、搜索引擎等社交網絡、電子商務、搜索引擎等 在線數據的實時流式

30、處理在線數據的實時流式處理日志數據、傳感器數據、日志數據、傳感器數據、web數據等；數據連續數據等；數據連續不斷、來源眾多、格式復雜等不斷、來源眾多、格式復雜等; 流式挖掘、實時分流式挖掘、實時分析、析、；應用于智能交通、環境監控、金融銀行等；應用于智能交通、環境監控、金融銀行等 還有在線數據的交互處理、圖數據處理還有在線數據的交互處理、圖數據處理大數據的處理大數據的處理 mapreduce編程模型編程模型 是批量數據處理的一個常用編程模型是批量數據處理的一個常用編程模型 源于函數式語言的兩個高階函數：源于函數式語言的兩個高階函數：map和和reduce map(f1, x1, , xn) =

31、 f1(x1), , f1(xn) f1作用于作用于n個變元的計算可以并行個變元的計算可以并行 reduce(f2, y1, , yn) = f2( f2(f2(y1, y2), y3), , yn) 若二元函數若二元函數f2是有交換律和結合率的運算，則是有交換律和結合率的運算，則f2作作用于用于n個變元的計算也可以適當并行個變元的計算也可以適當并行 兩者的復合：兩者的復合： reduce(f2, map(f1, x1, , xn) mapreduce源于此，但更加一般源于此，但更加一般 mapreduce編程模型編程模型 mapreduce是一種比較專用的并行編程模型，面是一種比較專用的并行

32、編程模型，面向大數據集上的可并行化的問題向大數據集上的可并行化的問題 map完成過濾或分類，例如，它把數據集中所有完成過濾或分類，例如，它把數據集中所有的人按姓氏分成若干隊列，每個姓氏一個隊列；的人按姓氏分成若干隊列，每個姓氏一個隊列； reduce完成概括總結操作，例如，計算各姓氏隊完成概括總結操作，例如，計算各姓氏隊列中的人數，產生按姓氏的人口比例列中的人數，產生按姓氏的人口比例 mapreduce可以在并行計算機、計算機集群和計可以在并行計算機、計算機集群和計算機網格上實現算機網格上實現大數據的處理大數據的處理 mapreduce編程模型編程模型 計算過程如圖所示計算過程如圖所示 程序員

33、只需編程序員只需編寫寫map和和reduce函數函數1. map任務任務 執行執行map函數的函數的多個任務并行執行多個任務并行執行 每個每個map任務把文任務把文件塊轉換成件塊轉換成“鍵鍵-值值”(key-value)對序列對序列大數據的處理大數據的處理map任務任務reduce任務任務按鍵分組按鍵分組輸輸出出文文件件輸入輸入文件塊文件塊鍵鍵-值對值對 (k, v)鍵及所有值鍵及所有值(k, v, w, ) mapreduce編程模型編程模型2. 按鍵組合按鍵組合 其處理方式與其處理方式與兩個函數無關兩個函數無關 把把“鍵鍵-值值”對序對序列組成列組成“鍵鍵-值表值表”對對序列序列 把各把各

34、“鍵鍵-值表值表”對對分發給分發給reduce任務任務 按鍵組合由主控按鍵組合由主控程序完成程序完成大數據的處理大數據的處理map任務任務reduce任務任務按鍵分組按鍵分組輸輸出出文文件件輸入輸入文件塊文件塊鍵鍵-值對值對 (k, v)鍵及所有值鍵及所有值(k, v, w, ) mapreduce編程模型編程模型3. reduce任務任務 執行執行reduce函函數的多個任務并數的多個任務并行執行行執行 每個每個reduce任務任務把把“鍵鍵-值表值表”對中對中的值以某種方式組的值以某種方式組合，轉換成合，轉換成“鍵鍵-值值”對輸出對輸出大數據的處理大數據的處理map任務任務reduce任務

35、任務按鍵分組按鍵分組輸輸出出文文件件輸入輸入文件塊文件塊鍵鍵-值對值對 (k, v)鍵及所有值鍵及所有值(k, v, w, )當矩陣很大時，可用當矩陣很大時，可用mapreduce實現矩陣運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果bn大數據的處理大數據的處理x:y:z:當矩陣很大時，可用當矩陣很大時，可用mapreduce實現矩陣運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩

36、塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果bn大數據的處理大數據的處理x:y:z:bn大數據的處理大數據的處理x:y:z:當矩陣很大時，可用當矩陣很大時，可用mapreduce實現矩陣運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果bn大數據的處理大數據的處理x:y:z:當矩陣很大時，可用當矩陣很大時，可用mapreduce實現矩陣

37、運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果當矩陣很大時，可用當矩陣很大時，可用mapreduce實現矩陣運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果bn大數據的處理大數據的處理x:y:z:bn大數據的處理大數據的處理x:y:z:當矩陣很大時，

38、可用當矩陣很大時，可用mapreduce實現矩陣運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果bn大數據的處理大數據的處理x:y:z:當矩陣很大時，可用當矩陣很大時，可用mapreduce實現矩陣運算。對于分塊乘：實現矩陣運算。對于分塊乘：1. map任務計算兩塊的乘，用結任務計算兩塊的乘，用結果在果在z中的位置作為鍵中的位置作為鍵2. reduce任務按鍵值來分別累加任務按鍵值來分別累加map任務的結果任務的結果 大數

39、據分析的關鍵技術大數據分析的關鍵技術要挖掘大數據的大價值，必須對大數據進行內容要挖掘大數據的大價值，必須對大數據進行內容上的分析與計算上的分析與計算 深度學習深度學習大數據的出現提供了使用復雜大數據的出現提供了使用復雜 (而不而不是簡單或淺層是簡單或淺層) 的模型來有效地表征和解釋數據的的模型來有效地表征和解釋數據的機會，深度學習就是利用層次化的架構學習出對機會，深度學習就是利用層次化的架構學習出對象在不同層次上的表達象在不同層次上的表達 (例例:降低語音識別錯誤率降低語音識別錯誤率) 知識計算知識計算要對大數據進行高端分析，就需要要對大數據進行高端分析，就需要從大數據中抽取出有價值的知識，并

40、將其構建成從大數據中抽取出有價值的知識，并將其構建成可支持查詢、分析和計算的知識庫，涉及知識庫可支持查詢、分析和計算的知識庫，涉及知識庫的構建、多源知識的融合和知識庫的更新的構建、多源知識的融合和知識庫的更新大數據的分析大數據的分析大數據的分析大數據的分析 大數據分析的關鍵技術大數據分析的關鍵技術 社會計算社會計算是現代計算技術與社會科學之間的是現代計算技術與社會科學之間的交叉學科交叉學科, 它是指面向社會活動、社會過程、社會它是指面向社會活動、社會過程、社會結構、社會組織和社會功能的計算理論和方法。結構、社會組織和社會功能的計算理論和方法。在線社會計算包括在線社會網絡的結構分析、信在線社會計

41、算包括在線社會網絡的結構分析、信息傳播模型以及信息內容的分析、建模與挖掘等息傳播模型以及信息內容的分析、建模與挖掘等 可視化可視化 不同于傳統的信息可視化，大數據可不同于傳統的信息可視化，大數據可視化的最大挑戰源自其數據規模：如何提出新的視化的最大挑戰源自其數據規模：如何提出新的可視化方法，它能夠幫助人們分析大規模、高維可視化方法，它能夠幫助人們分析大規模、高維度、多來源、動態演化的信息，并輔助作出實時度、多來源、動態演化的信息，并輔助作出實時的決策的決策大數據的分析大數據的分析 pagerank初步初步 pagerank（網頁排名）通過對網絡浩瀚的超鏈接（網頁排名）通過對網絡浩瀚的超鏈接關系

42、的分析來確定一個頁面的等級關系的分析來確定一個頁面的等級 google把從把從a頁面到頁面到b頁面的鏈接解釋為頁面的鏈接解釋為a頁面給頁面給b頁面投票，頁面投票，b頁面從頁面從a頁面的投票能得多少分還頁面的投票能得多少分還與與a頁面的等級有關頁面的等級有關 一個頁面的一個頁面的pagerank，由所有給它投票的頁面的，由所有給它投票的頁面的數量和重要性，經過迭代計算得到數量和重要性，經過迭代計算得到 這項技術使得這項技術使得google成為第一個能夠戰勝作弊者成為第一個能夠戰勝作弊者的搜索引擎。當然，與作弊者之間的斗爭永遠不的搜索引擎。當然，與作弊者之間的斗爭永遠不會停止會停止大數據的分析大數

43、據的分析 pagerank初步初步1. 早期搜索引擎與詞項作弊早期搜索引擎與詞項作弊 搜索引擎：詞項出現在網頁頭部比在普通正文的搜索引擎：詞項出現在網頁頭部比在普通正文的得分高、詞項在網頁中出現的次數越多得分越高得分高、詞項在網頁中出現的次數越多得分越高 作弊者：在自己的網頁上增加熱門詞項作弊者：在自己的網頁上增加熱門詞項, 如如movie, 并重復很多次，以提高與并重復很多次，以提高與movie的相關性。詞項的相關性。詞項movie在該網頁上的顏色與背景色一樣，以掩蓋作在該網頁上的顏色與背景色一樣，以掩蓋作弊者的不道德行為弊者的不道德行為大數據的分析大數據的分析 pagerank初步初步2.

44、 google的對策的對策 使用使用pagerank技術來模擬技術來模擬web漫游者的行為：他漫游者的行為：他們從隨機頁面出發，每次從當前網頁隨機地選擇們從隨機頁面出發，每次從當前網頁隨機地選擇出鏈前行，該過程可以迭代多次。最終，較多漫出鏈前行，該過程可以迭代多次。最終，較多漫游者訪問的網頁則重要性較高。在決定查詢應答游者訪問的網頁則重要性較高。在決定查詢應答順序時，順序時，google把重要頁面放在前面把重要頁面放在前面 在判斷網頁內容時在判斷網頁內容時, 不僅考慮網頁上出現的詞項，不僅考慮網頁上出現的詞項，還考慮有鏈接指向該網頁的網頁中所使用的詞項還考慮有鏈接指向該網頁的網頁中所使用的詞項

45、大數據的分析大數據的分析 pagerank初步初步3. 最簡單的最簡單的pagerank舉例舉例 pagerank：網頁集：網頁集實數，值越大則網頁越重要實數，值越大則網頁越重要 定義網頁的定義網頁的web遷移矩陣遷移矩陣m來描述隨機漫游者的來描述隨機漫游者的下一步訪問行為下一步訪問行為例：從例：從a出發，以出發，以1/3的概率的概率訪問訪問b、c和和d，訪問，訪問a的的概率為概率為0 0 1/2 1 01/3 0 0 1/21/3 0 0 1/21/3 1/2 0 0a b c dm =abcd大數據的分析大數據的分析 pagerank初步初步3. 最簡單的最簡單的pagerank舉例舉例 隨機漫游者位置的概率分布可通過一個隨機漫游者位置的概率分布可通過一個n維向量維向量v來描述，每個分量表示處于相應網頁的概率來描述，每個分量表示處于相應網頁的概率例例(續續)：假定處于各網頁的初始概率相等：假定處于各網頁的初始概率相等 mkv是隨機漫游者是隨機漫游者k步后的概率分步后的概率分布向量布向量abcd 0 1/2 1 01/3 0 0 1/21/3 0 0 1/21/3 1/2 0 0a b c dm =1/41/41/41/4v大數據的分析大數據的分析 pagerank初步初步