本書致力于利用算法求解實際問題。第1部分介紹算法的核心內(nèi)容,探討什么是算法、如何設(shè)計算法,同時學習在算法中使用的數(shù)據(jù)結(jié)構(gòu)。重點講解排序算法、查找算法和求解圖問題的算法。第二部分討論各種機器學習算法,包括無監(jiān)督機器學習算法和傳統(tǒng)有監(jiān)督學習算法,詳細討論一些自然語言處理算法和推薦引擎。第三部分討論更高級的算法概念,重點介紹了密碼算法和大規(guī)模算法。本書還包含一些案例分析(如天氣預(yù)測、推文聚類和電影推薦引擎),用來說明如何才能更好地應(yīng)用這些算法。
算法一直在計算科學和計算實踐中發(fā)揮著重要作用。本書致力于利用算法求解實際問題。為了限度地利用算法,必須深入理解算法背后的邏輯和數(shù)學知識。我們先概要地介紹算法,并探索各種算法設(shè)計技術(shù)。接下來,學習線性規(guī)劃算法、PageRank算法、圖算法以及機器學習算法。本書還包含一些案例(如天氣預(yù)測、推文聚類和電影推薦引擎),用來說明如何才能地應(yīng)用這些算法。通過學習本書,你將對使用算法求解實際計算問題充滿信心。
讀者對象
本書為程序員而寫!無論你是希望深刻理解算法背后的數(shù)學知識的經(jīng)驗豐富的程序員,還是希望了解如何利用經(jīng)過實踐檢驗的算法來改進代碼設(shè)計和編寫方式的經(jīng)驗不足的程序員,閱讀本書都大有裨益。在閱讀本書前必須具有Python編程經(jīng)驗,數(shù)據(jù)科學知識對閱讀本書有幫助,但不是必需的。
本書內(nèi)容
第1章概述算法基礎(chǔ)。1.1節(jié)介紹理解不同算法如何工作所需的基本概念,概述人們初如何用算法以數(shù)學的形式表達特定類型的問題,還提到不同算法的局限性。1.2節(jié)講述描述算法邏輯的各種方法。由于本書用 Python編寫算法,1.3節(jié)說明如何設(shè)置環(huán)境以運行書中給出的例子。1.4節(jié)介紹算法設(shè)計技術(shù)。1.5節(jié)討論如何用不同方法量化算法性能,并與其他算法進行比較。1.6節(jié)討論驗證算法的特定實現(xiàn)的各種方法。
第2章著重講述算法中用于存儲臨時數(shù)據(jù)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。算法可能是數(shù)據(jù)密集型的,也可能是計算密集型的,或者既是數(shù)據(jù)密集型的又是計算密集型的。對于所有不同類型的算法,選擇恰當?shù)臄?shù)據(jù)結(jié)構(gòu)對其實現(xiàn)而言至關(guān)重要。許多算法具有遞歸和迭代邏輯,因而需要面向這種本征邏輯的專用數(shù)據(jù)結(jié)構(gòu)。由于本書用 Python編寫算法,這一章主要關(guān)注實現(xiàn)書中算法所需的 Python 數(shù)據(jù)結(jié)構(gòu)。
第3章給出用于排序和查找的核心算法。這些算法在后面將作為其他更復(fù)雜算法的基礎(chǔ)。本章先講述不同類型的排序算法,包括各種算法的性能比較。然后,講述各種查找算法,量化這些算法的性能和復(fù)雜度,并進行比較。后,講述這些算法的實際應(yīng)用。
第4章講述設(shè)計各種算法所需的核心概念,闡述各種算法并討論它們的優(yōu)缺點。理解這些概念對設(shè)計的復(fù)雜算法而言至關(guān)重要。這一章先討論不同類型的算法設(shè)計,然后求解著名的旅行商問題。之后討論線性規(guī)劃及其局限性。后,用實例展示如何用線性規(guī)劃進行產(chǎn)量規(guī)劃。
第5章著重講述常見于計算機科學中的圖算法。圖是許多計算問題的模型。本章講述表示和搜索圖的各種方法。搜索圖意味著用系統(tǒng)化的方法沿圖中的邊訪問圖中的頂點。圖搜索算法可以發(fā)現(xiàn)圖的很多結(jié)構(gòu)。很多算法都通過在輸入圖上執(zhí)行搜索算法來獲得結(jié)構(gòu)信息。其他幾個圖算法都是基本圖搜索算法的細化。圖的搜索技術(shù)是圖算法領(lǐng)域的核心。該章首先討論圖的兩種常見的計算表示:鄰接表和鄰接矩陣。接下來,講述廣度優(yōu)先搜索這種簡單的圖搜索算法,并說明如何創(chuàng)建廣度優(yōu)先搜索樹。然后講述深度優(yōu)先搜索,并給出深度優(yōu)先搜索算法訪問頂點順序的標準結(jié)論。
第6章討論無監(jiān)督機器學習算法。之所以被歸類為無監(jiān)督方法,是由于這些模型或算法在無監(jiān)督條件下從給定數(shù)據(jù)中學習固有的結(jié)構(gòu)、模式和關(guān)系。我們先討論聚類方法,這種機器學習方法基于固有的屬性或特征,試圖從數(shù)據(jù)集的數(shù)據(jù)樣本中找出相似性模式和關(guān)系模式,然后把數(shù)據(jù)樣本劃分為集群,使得各個集群內(nèi)的數(shù)據(jù)樣本具有相似性。接下來,討論降維算法,該算法用于處理特征較多的問題。之后,討論關(guān)聯(lián)規(guī)則挖掘算法,它們屬于數(shù)據(jù)挖掘方法,用于檢查和分析大規(guī)模交易數(shù)據(jù)集,以發(fā)現(xiàn)有意義的模式和規(guī)則,而這些模式表示了跨交易的各種商品之間有意義的關(guān)系和關(guān)聯(lián)。后,討論處理異常檢測的算法。
第7章描述與一組機器學習問題相關(guān)的傳統(tǒng)監(jiān)督機器學習算法。這些問題中的標記數(shù)據(jù)集具有輸入屬性和相應(yīng)的輸出標簽或類別。這些輸入和其相應(yīng)的輸出用于學習一個一般性系統(tǒng),該系統(tǒng)用于預(yù)測不在數(shù)據(jù)集中的其他數(shù)據(jù)點的結(jié)果。我們先從機器學習的角度概述分類的相關(guān)概念。接下來,討論重要的算法之一決策樹,給出決策樹算法的局限性和優(yōu)勢。接著介紹支持向量機和XGBoost這兩種重要的算法。后,討論線性回歸這種簡單的機器學習算法。
第8章首先介紹典型神經(jīng)網(wǎng)絡(luò)這種重要的機器學習技術(shù)的主要概念和組成部分。然后介紹各種神經(jīng)網(wǎng)絡(luò),并闡述用于實現(xiàn)這些神經(jīng)網(wǎng)絡(luò)的激活函數(shù)。之后,詳細討論反向傳播算法,這是目前應(yīng)用廣泛的訓練神經(jīng)網(wǎng)絡(luò)的收斂算法。接下來,介紹遷移學習技術(shù),它可以大大簡化模型訓練并部分地使其自動化。后,給出一個學習實例,討論如何在現(xiàn)實世界中利用深度學習進行欺詐檢測。
第9章介紹自然語言處理算法,從理論到實踐循序漸進地展開。首先介紹基礎(chǔ)知識,然后討論背后的數(shù)學知識。接下來,介紹一種流行的神經(jīng)網(wǎng)絡(luò),它廣泛應(yīng)用于設(shè)計和實現(xiàn)文本數(shù)據(jù)上的重要用例。此外,還介紹自然語言處理算法的局限性。后,給出一個案例,討論如何在自然語言處理領(lǐng)域訓練機器學習模型,以進行電影評論情感分析。
第10章重點討論推薦引擎,它先用與用戶偏好相關(guān)的信息建立模型,然后基于模型和信息向
譯者序
前言
關(guān)于作者
關(guān)于審校者
部分 基礎(chǔ)與核心算法
第1章 算法概述2
1.1 什么是算法2
1.2 描述算法邏輯4
1.2.1 理解偽代碼4
1.2.2 使用代碼片段6
1.2.3 制定執(zhí)行計劃6
1.3 Python包簡介7
1.3.1 Python包8
1.3.2 通過Jupyter Notebook執(zhí)行Python9
1.4 算法設(shè)計技術(shù)10
1.4.1 數(shù)據(jù)維度11
1.4.2 計算維度12
1.5 性能分析13
1.5.1 空間復(fù)雜度分析13
1.5.2 時間復(fù)雜度分析14
1.5.3 性能評估14
1.5.4 選擇算法15
1.5.5 大O記號15
1.6 驗證算法19
1.6.1 精確算法、近似算法和隨機算法19
1.6.2 可解釋性20
1.7 小結(jié)20
第2章 算法中的數(shù)據(jù)結(jié)構(gòu)21
2.1 Python中的數(shù)據(jù)結(jié)構(gòu)21
2.1.1 列表22
2.1.2 元組26
2.1.3 字典27
2.1.4 集合28
2.1.5 數(shù)據(jù)幀30
2.1.6 矩陣32
2.2 抽象數(shù)據(jù)類型33
2.2.1 向量33
2.2.2 棧34
2.2.3 隊列36
2.2.4 棧和隊列背后的基本思想37
2.2.5 樹38
2.3 小結(jié)40
第3章 排序算法和查找算法41
3.1 排序算法簡介41
3.1.1 在Python中交換變量42
3.1.2 冒泡排序42
3.1.3 插入排序44
3.1.4 歸并排序46
3.1.5 希爾排序48
3.1.6 選擇排序50
3.2 查找算法簡介51
3.2.1 線性查找52
3.2.2 二分查找52
3.2.3 插值查找53
3.3 實際應(yīng)用54
3.4 小結(jié)56
第4章 算法設(shè)計57
4.1 算法設(shè)計基本概念57
4.1.1 點所設(shè)計算法是否能產(chǎn)生預(yù)期的結(jié)果58
4.1.2 第二點所設(shè)計算法是否是獲取結(jié)果的方法58
4.1.3 第三點所設(shè)計算法在更大的數(shù)據(jù)集上表現(xiàn)如何61
4.2 理解算法策略61
4.2.1 分治策略62
4.2.2 動態(tài)規(guī)劃策略64
4.2.3 貪心算法64
4.3 實際應(yīng)用求解TSP65
4.3.1 使用蠻力策略66
4.3.2 使用貪心算法68
4.4 PageRank算法70
4.4.1 問題定義70
4.4.2 實現(xiàn)PageRank算法70
4.5 了解線性規(guī)劃73
4.6 實例用線性規(guī)劃實現(xiàn)產(chǎn)量規(guī)劃73
4.7 小結(jié)76
第5章 圖算法77
5.1 圖的表示77
5.1.1 圖的類型79
5.1.2 特殊類型的邊81
5.1.3 自我中心網(wǎng)絡(luò)82
5.1.4 社交網(wǎng)絡(luò)分析82
5.2 網(wǎng)絡(luò)分析理論簡介83
5.2.1 理解短路徑83
5.2.2 創(chuàng)建鄰域84
5.2.3 理解中心性度量85
5.2.4 用Python計算中心性指標87
5.3 理解圖的遍歷88
5.3.1 廣度優(yōu)先搜索89
5.3.2 深度優(yōu)先搜索92
5.4 實例欺詐分析93
5.4.1 進行簡單的欺詐分析96
5.4.2 瞭望塔欺詐分析法97
5.5 小結(jié)99
第二部分 機器學習算法
第6章 無監(jiān)督機器學習算法102
6.1 無監(jiān)督學習簡介102
6.1.1 數(shù)據(jù)挖掘生命周期中的無監(jiān)督學習103
6.1.2 無監(jiān)督學習的當前研究趨勢105
6.1.3 實例106
6.2 理解聚類算法107
6.2.1 量化相似性107
6.2.2 分層聚類113
6.2.3 評估聚類效果115
6.2.4 聚類算法的應(yīng)用115
6.3 降維116
6.3.1 主成分分析116
6.3.2 主成分分析的局限性118
6.4 關(guān)聯(lián)規(guī)則挖掘119
6.4.1 實例119
6.4.2 市場購物籃分析119
6.4.3 關(guān)聯(lián)規(guī)則120
6.4.4 排序規(guī)則122
6.4.5 關(guān)聯(lián)分析算法123
6.5 實例聚類相似推文127
6.5.1 主題建模128
6.5.2 聚類128
6.6 異常檢測算法129
6.6.1 基于聚類的異常檢測129
6.6.2 基于密度的異常檢測129
6.6.3 基于支持向量機的異常檢測129
6.7 小結(jié)130
第7章 傳統(tǒng)監(jiān)督學習算法131
7.1 理解監(jiān)督機器學習131
7.1.1 描述監(jiān)督機器學習132
7.1.2 理解使能條件134
7.1.3 區(qū)分分類器和回歸器134
7.2 理解分類算法135
7.2.1 分類器挑戰(zhàn)性問題135
7.2.2 評估分類器139
7.2.3 分類器的各個階段142
7.2.4 決策樹分類算法143
7.2.5 理解集成方法146
7.2.6 邏輯回歸149
7.2.7 支持向量機算法151
7.2.8 理解樸素貝葉斯算法153
7.2.9 各種分類算法的勝者156
7.3 理解回歸算法156
7.3.1 回歸器挑戰(zhàn)性問題156
7.3.2 線性回歸158
7.3.3 回歸樹算法162
7.3.4 梯度提升回歸算法163
7.3.5 各種回歸算法的勝者163
7.4 實例預(yù)測天氣164
7.5 小結(jié)166
第8章 神經(jīng)網(wǎng)絡(luò)算法167
8.1 理解人工神經(jīng)網(wǎng)絡(luò)168
8.2 人工神經(jīng)網(wǎng)絡(luò)的演化169
8.3 訓練神經(jīng)網(wǎng)絡(luò)171
8.3.1 解析神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)171
8.3.2 定義梯度下降172
8.3.3 激活函數(shù)173
8.4 工具和框架178
8.4.1 Keras178
8.4.2 理解TensorFlow181
8.4.3 理解神經(jīng)網(wǎng)絡(luò)的類型183
8.5 遷移學習185
8.6 實例用深度學習實現(xiàn)欺詐檢測186
8.7 小結(jié)189
第9章 自然語言處理算法190
9.1 自然語言處理簡介190