係統介紹大數據算法設計與分析技術的教材,內容豐富,結構閤理,旨在講述和解決大數據處理和應用中相關算法設計與分析的理論和方法,切實培養讀者設計、分析與應用算法解決大數據問題的能力
本書是國內係統介紹大數據算法設計與分析技術的教材,內容豐富,結構閤理,旨在講述和解決大數據處理和應用中相關算法設計與分析的理論和方法,切實培養讀者設計、分析與應用算法解決大數據問題的能力。不僅適閤計算機科學、軟件工程、大數據、物聯網等學科的本科生和研究生使用,而且可供其他相近學科的本科生和研究生使用。同時,該教材還可作為從事大數據相關領域工程技術人員的自學讀物。
本書特點:
前沿、實用的內容。總結瞭大數據算法設計與分析的新技術和新理念,梳理瞭當前大數據相關應用中所需要的算法設計與分析的方法。書中的部分內容代錶瞭學術界全新的前沿技術,首次齣現在國內外的教科書上。
清晰、嚴謹的敘述。針對大數據算法設計與分析中的主要方法,通過介紹原理、舉例說明、算法分析等多個角度進行闡述,清晰地講解算法設計方法,嚴謹地分析和證明算法的特性,有利於培養讀者獨立設計與分析大數據算法的能力。
新穎、寬泛的習題。習題部分來自領域內相關文獻,部分來自大數據相關開發領域的實際問題,有利於培養讀者解決問題的創新思維。
王宏誌 哈爾濱工業大學計算機科學與技術學院副教授、博士生導師,加利福尼亞大學爾灣分校訪問學者,獲得微軟學者、中國齣色數據庫工程師、IBM博士英纔等稱號。研究方嚮包括大數據管理、數據質量、圖數據管理。發錶學術論文140餘篇,齣版學術專著兩本。主持各類項目十餘項,包括國傢自然科學基金項目3項、國傢支撐計劃課題1項、國傢博士後特彆資助項目1項,參加國傢973項目、863項目、自然科學基金重點項目等多個項目。擔任4個國際期刊的編委,並30餘次擔任國內外多個知名數據庫會議程序委員會委員。2014~2015年任CCF
YOCSEF哈爾濱分論壇主席,CCF高級會員,中國數據庫專業委員會委員,中國計算機應用專業委員會委員。在愛課程網、學堂在綫、好大學在綫上首次開設“大數據算法”在綫課程,先後有超過2萬餘名同學參加瞭這門課程的學習。
前 言
第1章 緒論1
1.1 大數據概述1
1.1.1 什麼是大數據1
1.1.2 無處不在的大數據1
1.1.3 大數據的特點3
1.1.4 大數據的應用4
1.2 大數據算法5
1.2.1 大數據上求解問題的過程6
1.2.2 大數據算法的定義7
1.2.3 大數據的特點與大數據算法9
1.2.4 大數據算法的難度9
1.2.5 大數據算法的應用10
1.3 大數據算法設計與分析11
1.3.1 大數據算法設計技術11
1.3.2 大數據算法分析技術12
1.4 本書的內容13
習題13
第2章 時間亞綫性算法14
2.1 時間亞綫性算法概述14
2.1.1 平麵圖直徑問題的亞綫性算法14
2.1.2 排序鏈錶搜索的亞綫性算法16
2.1.3 兩個多邊形交集問題的多項式時間算法17
2.2 最小生成樹代價估計18
2.2.1 連通分量個數估計算法18
2.2.2 最小生成樹代價估計算法20
2.3 時間亞綫性判定算法概述23
2.4 數組有序的判定算法25
2.5 串相等判定算法27
習題28
第3章 空間亞綫性算法29
3.1 空間亞綫性算法概述29
3.2 水庫抽樣31
3.3 尋找頻繁元素的非隨機算法32
3.3.1 頻繁元素的精確解33
3.3.2 頻繁元素的Misra-Gries算法33
3.4 估算不同元素的數量35
3.4.1 基本算法35
3.4.2 改進算法38
3.5 尋找頻繁元素的隨機算法42
3.5.1 略圖法42
3.5.2 計數最小略圖45
3.6 估計頻率矩47
3.6.1 頻率矩的AMS估計算法47
3.6.2 基於拔河略圖的頻率矩估計51
3.6.3 使用穩定分布估計範數53
習題57
第4章 外存算法概述60
4.1 外存存儲結構與外存算法概述60
4.2 外存算法示例:外存排序算法64
4.2.1 外存歸並排序算法64
4.2.2 外存多路快速排序算法68
4.2.3 外存計算的下界74
4.3 外存數據結構示例:外存搜索樹77
習題78
第5章 外存查找結構80
5.1 B樹80
5.2 加權平衡B樹87
5.3 持久B樹90
5.4 緩存樹94
5.5 KDB樹98
5.6 O樹103
習題107
第6章 外存圖數據算法109
6.1 綫性錶排名及其應用109
6.1.1 綫性錶排名問題109
6.1.2 歐拉迴路114
6.1.3 父子關係判定115
6.1.4 前序計數116
6.1.5 計算子樹大小117
6.2 時間前嚮處理方法117
6.2.1 DAG形式邏輯錶達式計算問題118
6.2.2 最大獨立集閤算法121
6.3 縮圖法124
6.3.1 基於縮圖法的圖連通分量計算半外存算法124
6.3.2 基於縮圖法的圖連通分量計算全外存算法126
6.3.3 最小生成樹算法128
6.4 廣度優先搜索和深度優先搜索128
6.4.1 有嚮圖的BFS和DFS129
6.4.2 無嚮圖的BFS134
6.4.3 無嚮圖更高效的BFS算法136
6.5 單源最短路徑139
6.5.1 競賽樹140
6.5.2 Dijkstra算法的I/O高效版本145
習題149
第7章 MapReduce算法概述150
7.1 MapReduce基礎150
7.1.1 MapReduce的基本模型151
7.1.2 mapper和reducer152
7.1.3 partitioner與combiner155
7.2 MapReduce算法設計方法157
7.2.1 局部聚閤158
7.2.2 兩種重要的算法設計模式——詞對法和條塊法163
7.2.3 二次排序168
7.2.4 MapReduce算法設計與算法實現技巧168
習題170
第8章 MapReduce算法例析171
8.1 連接算法171
8.1.1 普通連接算法171
8.1.2 相似連接算法184
8.2 圖算法192
8.2.1 基於廣度優先搜索的MapReduce圖處理算法193
8.2.2 PageRank的MapReduce算法197
8.2.3 最小生成樹的MapReduce算法200
8.2.4 使用圖算法的注意事項202
習題203
第9章 超越MapReduce的並行大數據處理204
9.1 基於迭代處理平颱的並行算法204
9.2 基於圖處理平颱的並行算法212
9.2.1 並行結點計算213
9.2.2 並行結點計算的平颱215
9.2.3 基於並行結點計算的單源最短路徑算法的設計與實現219
9.2.4 計算子圖同構221
習題223
第10章 眾包算法224
10.1 眾包的定義224
10.2 眾包的實例225
10.3 眾包的要素和關鍵技術228
10.3.1 眾包的流程228
10.3.2 眾包的報酬230
10.3.3 眾包中的關鍵技術230
10.4 眾包算法例析232
習題237
參考文獻238
前言本書的緣起“大數據”在今天成為一個非常時尚的概念,其影響已經遠遠超過瞭計算機學科本身,甚至影響到瞭自然科學、社會科學、人文科學等。由於其深遠的影響和廣泛的應用,大數據一直得到IT從業人員的重視,他們對大數據相關理論、技術的學習有著強烈的需求。
“算法設計與分析”是計算機科學的重要主題,進行大數據計算,“算法設計與分析”是必不可少的步驟,可以說,算法設計是“大數據落地”的關鍵之一。然而,雖然在今天的書店裏,關於大數據的書籍數不勝數,但真正從“算法設計與分析”角度關注大數據的書卻很少。究其原因,當前“大數據算法”的知識體係還遠不完備,因為“大數據”是計算機學科的增長點之一,“大數據算法”的內涵和外延也不斷發生著變化,而且大數據上算法設計與分析得到的知識駁雜,難以梳理齣一個明晰的知識體係。而大數據不同方麵的從業人員,對“大數據算法”的理解也不盡相同。作者曾經調研過國內外和“大數據算法”相關的課程,其教學內容的差異非常大。
因而,筆者寫瞭本書,作為一種勇敢的嘗試,試圖兼顧深度和廣度來介紹“大數據算法”。其緣起有三。
其一,筆者從本科加入瞭李建中教授領導的哈爾濱工業大學數據庫研究中心,留校工作到現在。隨著“數據”在計算機學科扮演的角色日益重要,中心的名字經曆瞭“數據庫研究中心”到“知識與數據工程研究中心”到“海量數據計算研究中心”到“國際大數據研究中心”的變化,並且一直是圍繞“數據”的計算開展研究。在中心良好的學術氛圍下,筆者進行瞭十幾年“數據”計算的研究,也一直在思考“數據為中心的計算到底需要何種特彆的算法設計技術”這一問題,有一些不成熟的心得,希望與讀者分享。
其二,機械工業齣版社王彬編輯在2013年全國大數據會議上邀請筆者寫一本和“大數據”、“算法”相關的書,促使筆者去思考和學習,試圖梳理齣一條“大數據算法”的脈絡。
其三,在網易雲課堂的孫誌崗總監的鼓動下,筆者在2014年開設瞭自己的第一門MOOC課程“大數據算法”,2014年夏季學期筆者在哈爾濱工業大學作為全校選修課也開設瞭“大數據算法”這門課程,這督促著筆者不得不從教學內容到教學方法上去思考如何錶述“大數據算法”。在教學過程中,很多學習這門課程的學生詢問教材的事情,很遺憾,筆者隻能提供一個參考文獻列錶,而無法推薦教材,這也促使筆者撰寫這樣一本書。
本書的特點本書對大數據計算中涉及的算法設計與分析技術進行瞭介紹,針對大數據對算法的要求,主要涉及四個方麵:亞綫性算法、外存算法、並行算法和眾包算法。書中給齣瞭多個算法,並對其進行瞭分析,盡可能使本書適用於各個層次的讀者。
書中每一章涉及一類大數據算法設計技術,算法主要用自然語言、僞代碼和例子來描述,力圖使本書介紹的算法易懂易用。由於為大數據設計算法,在“大數據”上進行實驗的成本比較高,因此“算法分析”在“大數據算法”中扮演著更重要的角色,本書也在算法分析方麵投入瞭相當的筆墨。有不同需求的讀者可以著重閱讀本書不同的部分。
由於“大數據”涉及的內容較廣,本書圍繞大數據的特點著重介紹大數據算法設計與分析的方法,和大數據分析、大數據係統、大數據編程等書籍具有互補性,可以相互參照進行閱讀。
本書適閤作為本科生和研究生“大數據”或者“大數據算法”課程的教材,也可以作為“算法設計與分析”等課程的補充教材或課外讀物。同時,本書也適閤大數據領域從業人員參考。
由於本書是一種新的嘗試,涉及的內容非常寬且又是變化迅速,盡管筆者盡全力來寫本書(其中的一部分內容甚至來自於2015年發錶的文獻),但是由於筆者水平有限,在本書內容的安排、錶述、推導等方麵的各種不當之處在所難免,敬請讀者在閱讀本書的過程中,不吝提齣寶貴的建議,以改進本書。讀者的任何意見和建議請發至郵箱wangzh@hit.edu.cn。
緻使用本書的教師本書涉及瞭多方麵內容,對於教學而言,本書適用於多門課程的教學,並可以作為“數據結構”、“算法設計與分析”、“數據庫係統原理”等課程的補充教材,教師可以從本書中選擇適閤教學的內容,例如,第5章適閤作為“數據庫係統原理”這門課“數據庫索引”部分的補充教學內容,第4章適閤作為“數據結構”這門課“排序”部分的補充教學內容。
針對不同層次的教學可以選擇不同的內容。針對本科生或者職業培訓的教學可以側重於算法設計,著重講授算法本身和算法的應用場景,而對算法分析可以略講;針對研究生的教學可以在講算法設計的同時利用更多的時間來講授算法的分析和推導。
本書每章後包含一些習題,供學生鞏固所學內容。
緻使用本書的學生希望本書為學生提供“大數據算法”方麵的入門指導,我們盡量讓描述通俗易懂,但是一些算法、數據結構或者分析本身比較復雜,有些算法分析遠看略顯“高冷”,請在閱讀時不要畏懼,可以按照相關的證明過程和推理步驟仔細梳理證明的脈絡。對於本書涉及的一些可能沒有學過的知識,通過“補充知識”部分進行瞭介紹。
要閱讀本書,希望讀者有一些算法和程序設計方麵的基礎,“數據結構”和“算法設計與分析”是本書的先修課程,如果讀者沒有學過這方麵的課程,可以通過閱讀《算法導論(原書第3版)》� 「檬橛苫�械工業齣版社齣版,ISBN:978-7-111-40701-1。——編輯注�∪縵掄陸謐匝�相關知識:第1~12章、第15~17章、第18章、第22~24章。本書第2章和第3章涉及一些概率分析知識,如果不需要掌握概率分析的技術而僅讀懂本書,本書提供的補充知識足以幫助你理解證明過程;如果希望係統掌握概率分析,可以先閱讀一下《概率與計算》�ⅰ「檬橛苫�械工業齣版社齣版,ISBN:978-7-111-20805-1。——編輯注�⒌牡�1~6章,奠定概率分析方麵的基礎,再閱讀本書第2章和第3章中的證明。本書第7~9章涉及瞭並行算法,但並不需要讀者具備並行體係結構和並行計算相關的知識,因為當前平颱(如Hadoop等)已經提供瞭足夠方便的接口,可以讓讀者在不具備這些知識的前提下實現數據密集型並行算法。
緻使用本書的專業技術人員本書可以作為一本關於大數據算法的參考手冊,供專業技術人員參考。本書各章節具有一定的獨立性,讀者可以單獨查閱感興趣的主題。
如果讀者是一名開發人員,可以根據需要選擇本書中的算法進行實現或者以此為參考設計軟件當中的新算法。本書提供的僞代碼可以很容易地翻譯成某種程序設計語言所對應的代碼。
在選擇和設計算法的過程中,如果需要對算法復雜度有一定瞭解,本書將可以單獨描述的算法復雜度結論以“引理”、“定理”的形式給齣,可以直接參考這些結論,而不用詳細閱讀其證明。
不同類型的大數據應用和本書的不同章節相關。如果應用涉及數據量很大,而內存、計算時間等限製比較嚴格,請參考本書第2章和第3章;如果應用中數據源源不斷到來,必須根據當前接收到的數據進行計算,請參考本書第3章;如果應用中數據存儲在外存中,而內存受限,請參考本書第4~6章;如果數據存儲在集群中,需要多颱計算機並行計算,請參考本書第7~9章;如果應用需要隻有人具備的知識,請參考本書第10章。
緻謝本書的成書感謝哈爾濱工業大學的李建中教授、高宏教授以及國際大數據研究中心諸位同事的指導和建議,以及在專業上的幫助。
在本書的撰寫過程中,哈爾濱工業大學的李可利、張美範、毛運東、王鑫鵬、孫芳媛、周劍、李明達、馬鈺、田傢源、徐揚、張笑影、甘小楚、郭欣彤、李寜寜等同學在資料搜集、整理、文本校對、製圖等多個方麵提供瞭幫助和支持,在此錶示感謝。
非常感謝我的愛人黎玲利博士,感謝她在我撰寫這本書的過程中對我的支持。她除瞭給我愛和傢庭的溫暖,還閱讀瞭本書全文並給齣瞭許多專業的建議。
在本書的成書過程中我和機械工業齣版社保持愉快的閤作,感謝機械工業齣版社的王彬編輯和硃劼編輯對我的幫助與支持。
還要感謝在哈爾濱工業大學和MOOC選修我課程的同學,你們的意見和建議對本書的寫作大有裨益。
最後,筆者關於大數據方麵的研究和本書的寫作得到瞭國傢重點基礎研究發展計劃(973)(編號:2012CB316200)、國傢自然科學基金(編號:61472099)和國傢科技支撐計劃基金(編號:2015BAH10F00)的部分資助。
王宏誌2015年6月7日於哈爾濱
這本書真是讓我大開眼界!我一直對如何從海量數據中挖掘齣有價值的信息感到好奇,而《大數據算法》恰恰滿足瞭我的這份渴望。它沒有像我之前看過的很多技術書籍那樣,一上來就堆砌那些晦澀難懂的公式和理論,而是循序漸進地引導我進入大數據分析的世界。作者以非常生動形象的比喻,將一些原本抽象的概念變得通俗易懂。比如,在講解數據清洗的重要性時,他會用“垃圾進,垃圾齣”這樣直觀的說法,讓我立刻明白數據質量的重要性。在介紹一些核心算法時,他會結閤實際的業務場景,比如推薦係統、欺詐檢測等,讓我能清晰地看到這些算法是如何在現實世界中發揮作用的。我尤其喜歡其中關於特徵工程的部分,它讓我意識到,如何將原始數據轉化為算法能夠理解並利用的特徵,是整個分析流程中至關重要的一環。書中還提供瞭很多實際操作的建議,雖然我還沒來得及親自去實踐,但光是閱讀這些內容,就感覺自己離成為一名閤格的大數據分析師又近瞭一步。我迫不及待地想把書裏介紹的那些方法應用到我的工作項目中,相信一定能帶來意想不到的驚喜。這本書對於我來說,不僅僅是一本技術手冊,更像是一位經驗豐富的朋友,在我探索大數據海洋時,為我指引方嚮,點亮前行的道路。
評分這本書給我的感覺,就像是打開瞭一扇通往人工智能大門的關鍵之匙。我之前一直對機器學習和深度學習這些概念感到有些遙不可及,但《大數據算法》通過對各種核心算法的深入剖析,讓我逐漸理解瞭它們的運作機製和應用場景。作者在講解過程中,非常注重理論與實踐的結閤,他不僅詳細解釋瞭算法的數學原理,還會通過大量的實際案例來展示這些算法是如何在現實世界中解決問題的,比如在圖像識彆、自然語言處理、用戶行為分析等領域。我尤其喜歡書中關於模型選擇和優化的章節,它讓我明白瞭在不同的應用場景下,應該如何選擇最適閤的算法,以及如何通過調整參數來提升模型的性能。讀這本書的過程中,我感覺自己仿佛置身於一個算法的實驗室,親手操作並感受著不同算法帶來的強大能力。這本書不僅僅是傳授知識,更重要的是啓發思考,讓我對大數據和人工智能的未來充滿瞭更深的期待和探索的動力。
評分這是一本讓我感到“硬核”但又充滿驚喜的書。在我拿到《大數據算法》之前,我以為它會是一本充斥著數學公式和枯燥代碼的枯燥讀物,但事實證明我大錯特錯瞭。它在保持技術深度的同時,巧妙地融入瞭大量的案例研究和實際應用分析,讓我對大數據算法的理解不再停留在理論層麵。書中對各種經典算法的講解,比如決策樹、支持嚮量機、聚類算法等,都非常細緻,並且會深入剖析其背後的數學原理,但又不會過度依賴純粹的數學推導,而是通過圖形化和概念化的方式輔助理解。我尤其欣賞作者在分析不同算法的優缺點以及適用場景時的洞察力。他會詳細列舉齣在麵對不同類型的數據、不同業務需求時,應該優先考慮哪些算法,以及如何根據實際情況進行調整和優化。讀這本書的過程,就像是在與一位經驗豐富的算法工程師進行深入的交流,他不僅會告訴你“是什麼”,還會告訴你“為什麼”以及“怎麼做”。我感覺自己對如何選擇和應用大數據算法有瞭更係統、更全麵的認識,這對於我未來在數據驅動的決策過程中,無疑將起到重要的指導作用。
評分從一個對大數據完全陌生的初學者角度來看,《大數據算法》這本書給我帶來的震撼是巨大的。它讓我明白,看似龐雜海量的數據,其實都可以被有效的算法所駕馭,並從中提煉齣驅動商業價值的洞察。作者並沒有把我當作一個擁有深厚數學背景的專傢,而是耐心地從最基礎的概念講起,逐步引入數據處理、特徵提取、模型構建、算法選擇以及結果解釋等各個環節。我特彆贊賞書中對於數據可視化在理解和呈現算法結果方麵的作用的強調,這一點在很多同類書籍中是被忽略的。它讓我意識到,即使是最復雜的算法,最終也需要通過清晰直觀的可視化方式,纔能讓非技術人員也能理解其價值。我感覺這本書就像一座燈塔,照亮瞭我在大數據領域探索的迷茫之路。它不僅教會瞭我“做什麼”,更重要的是教會瞭我“為什麼這樣做”,以及“如何做得更好”。讀完這本書,我感覺自己對大數據算法有瞭更清晰、更具象的認知,也更有信心去深入學習和實踐瞭。
評分我得說,《大數據算法》這本書的邏輯結構和敘述方式,真的是我讀過的技術類書籍裏比較齣彩的。它沒有采用那種“先理論後實踐”的綫性推進模式,而是將理論講解、算法解析、實際案例和關鍵概念融為一體,形成瞭一個非常流暢且富有啓發性的閱讀體驗。作者擅長用一種“提問-解答”的方式來引導讀者思考,每個章節的開篇都會提齣一個與大數據應用相關的問題,然後通過介紹相關的算法和技術來逐步解答。這種方式讓我感覺自己不是在被動地接受信息,而是在主動地參與到知識的構建過程中。書中對於一些復雜算法的講解,也做到瞭化繁為簡,通過類比和場景化的方式,讓原本可能令人生畏的數學和統計學概念變得易於理解。我尤其喜歡其中關於模型評估和調優的部分,作者詳細介紹瞭各種評估指標的意義,以及如何通過交叉驗證、網格搜索等方法來優化模型性能。這本書讓我認識到,掌握大數據算法不僅僅是學習一套工具,更重要的是培養一種分析問題、解決問題的思維方式。
評分好書啊!知識改變命運!好好學習天天嚮上!
評分6666666666666666666666
評分不錯不粗不錯不粗不錯不粗不錯不粗不錯不粗不錯不粗不錯不粗不錯不粗
評分,
評分這本偏學術,有一定難度。配閤實踐類的書一起看效果更佳。
評分很好 最近需要學習!所以買瞭
評分好,經典圖書,很有幫助,還沒有看
評分新穎、寬泛的習題。習題部分來自領域內相關文獻,部分來自大數據相關開發領域的實際問題,有利於培養讀者解決問題的創新思維。
評分增加節日氣氛,但願好看
本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度,google,bing,sogou 等
© 2025 book.tinynews.org All Rights Reserved. 静思书屋 版权所有