2025AI第1算法入數據的例子是公元前18000拉底河與底格里斯河河畔（兩河流域），人花了900算法。輾轉相除法的意思是兩個正整數a和b（ab）的最大公約數，輸入兩個正整數a和計算a除以b的余數如果r等于0，則最大公約數為當前的b如果r不等于0，則a=b，b=r，跳轉至步驟（2）LikelihoodEstimate，MLE）在神經網絡模型中應用廣泛；貝葉斯學元胞自動機（CellularAutomata，CA）。元胞自動機中單個個體的顧名思義，數據分析（DataAnalysis）就是對數據進行分析，顧名思義，機器學習（MachineLearning）就是讓機器自己去學提高面向大學生手機市場的投資收益率（ReturnonInvestment，算法是一個很大的概念，AI第3第2算法之可以稱為算法；往小了說，在信息技術（InformationTechnology，對于數學關系f(x+y)=f(x)+f(y)，線性代數不關心其中x和y的具體含義是什么，其研究的是擁有這種線性映射關系的函數f質。標量：表示一個簡單的數，如29、31的“50”次是[50,51,52,53,52,48,45]，則“[50,51,52,53,48,45]”是一個向量；加上這周每天賣出的豆沙包、咸菜包的數量，（batch）可見，掌握向量和矩陣的相關知識，對于算法“內力”的修煉至關重要。既然涉及運算，自然會有相應的運算法則，那么向量和矩陣的運算法則是怎么樣的呢？某公司有n名員工，月工資用向量[a1,a2,…,an-1,an]表示，其表2-1員工漲薪情況（一情形二：公司業績不錯，根據員工完成業績的不同，老板決定對不同的員工給出相應的工資漲幅。以絕對值漲幅為例（也可以是不同的比例漲幅），給第i位員工每月增加bi元工資，可以用行（列）向與行（列）向量之間的加法來計算漲薪后的工資，如表2-2所示。表2-2員工漲薪情況（二根據行向量與列向量相乘的例子可知，使運算成立的一個隱含條件是，行向量的列數必須與列向量的行數相等，如例子中的向量長度均為n，這有助于理解后面的矩陣運算（向量是一種特殊的矩陣）向量的列數與行向量的行數都等于1即可得到一個矩陣，具體計算方法如下。在機器學習中，向量通常用于表示特定維度空間中不同維度的特征值，因此又稱為特征向量。例如，一個二維特征向量[1,2]表示兩個特征，第一個特征維度的值為1，第二個特征維度的值為2。既然是空間，那就存在距離的概念，即同一個特征空間中不同特征向量之間存在著某種關系，如相似的特征表現。假設有另一個二維特征向量4]，其在兩個特征維度上的值分別為2和4，可以發現，這個二維特征向量和前面的二維特征向量，在各個維度上的特征值大小恰好相差一倍，這說明二者的特征表現相似，只是程度不同。當然，在實際算法工程中，特征向量之間的關系會有更復雜的度量方式，如相似度、相關系數等。假設A、B、C在線性代數中，關于向量和矩陣的知識點還有很多，包括單位矩陣、對角矩陣、對稱矩陣等，這些知識點在PCA分解等算法中都有所運用，下文只對這些概念進行簡單介紹，感興趣的讀者可以自行深入拓展學習。①從該小組中選出3②從該小組中選出3可以用形式化的語言描述排列問題，即n個人中計算m法；最后從剩下的3個人中選出1個人站在位置3上，一共有3種選法；因此共有60（5×4×3）母A表示排列，具體計算公式如下。法總數就是10（60/3!）種。使用字母C表示組合，具體計算公式如看到這節，你可能會問：搞AI算法還需要學習高等數學？大家知道，高等數學涵蓋的知識點比較多，并且比較難以理解。別擔心，本書只講解高等數學中與AI算法最相關的兩個知識點——導數和梯度這兩個知識點在AI算法的公式推導中至關重要，有助于幫助我們理解算法模型在實際應用中起作用的原因。三角函數處處連續，同時處處可導。以正弦函數y=sinx數圖像上的每個點都是光滑的，可以計算函數圖像在該點處的切線斜率，如圖2-1所示。圖2- 正弦函數y=sinx的圖數圖像同樣處處連續。但是，在坐標為(0,0)的點的位置雖然連續，圖2- 線性絕對值函數y=|x|的圖此外，在使用神經網絡的AI表2-3事件之間的基本關系和集合運算一樣，事件之間的運算也具備以下3交換律：A∪B=B∪A，A∩B=B∩A結合律：A∪B∪C=A∪(B∪C)，A∩B∩C=A∩(B∩C)分配律：A∩(B∪C)=(A∩B)∪(A∩C)，A∪(B∩C)=(A∪B)∩(拋硬幣正面朝上的次數和地鐵站的上車人數都是可數的，最小單位是1，壽命、人的身高體重的取值是連續的，沒有最小單位，在數學中稱為連續，這類隨機變量稱為連續型隨機變量。拋擲一枚質地均勻的硬幣，正反兩面出現的概率各占一半，在進行足夠數量的拋擲實驗后，正反兩面實際出現的次數會各自接近這個50%方法是用實驗中事件的發生概率乘重復實驗的總次數，一般用字母μ或E表示。顧名思義，條件概率是指事件滿足一定條件所發生的概率。在通常情況下，兩個事件A和B，P(A|B)表示在事件BA發生的概率。圖2- 均勻分布的連續型隨機變量的概率密度函數圖顧名思義，二項分布就是取值只有正、負兩種結果的概率分布，因此其隨機變量只能是離散型隨機變量。用數學語言描述就是，關于個獨立的二值實驗中有多少次為正的離散型概率分布。當p=0.5、n=12時，二項分布的概率質量函數圖像如圖2-4圖2- 二項分布的概率質量函數圖像量。與二項分布不同，幾何分布關心的是事件（或實驗）發生n第x次取得成功的概率。典型的例子是打靶，在n次打靶過程中第一次命中靶心的概率。幾何分布的數學期望如下。當p=0.5時，幾何分布的概率質量函數圖像如圖2-5圖2- 幾何分布的概率質量函數圖像當μ=0.9時，泊松分布的概率質量函數圖像如圖2-6圖2- 泊松分布的概率質量函數圖像當λ=0.8時，指數分布的概率質量函數圖像如圖2-7圖2- 指數分布的概率質量函數圖像高斯分布的概率密度函數圖像如圖2-8圖2- 高斯分布的概率密度函數圖最優化問題分為有約束的最優化問題和無約束的最優化問題。有約束的最優化問題分為等式約束優化問題和不等式約束優化問題，這類問題通常使用拉格朗日乘數法和KKT分為全局最優化問題和局部最優化問題，這類問題可以使用牛頓法和最小二乘法解決。石頭平時比較喜歡自己在家里榨果汁，主要使用5種原材料：杧果、草莓、香蕉、牛奶和木瓜。石頭在榨果汁時常用的42-4所示，5種原材料在不同超市的售賣價格如表2-5的形式計算這4種果汁配方的成本分別是多少。表2-4石頭在榨果汁時常用的4種配方（單位：份表2-55種原材料在不同超市的售賣價格（單位：元/份5第3算法之招數組（Array）連續分配的方式存儲的。由于是連續存儲，因此只要知道某個元素在數組中的編號（下標）及數組的起始位置，相加計算偏移就能訪問這個元素的值。數組按空間維度劃分，可以分為一維數組、二維數組、多維數組，一維數組的存儲圖例如圖3-1所示。圖3- 一維數組的存儲圖明。小王、小李和小張一起去電影院看電影，在買票選座位時希望選擇同一排的連號座位，這種座位分配方式就是一維數組的存儲方式。假設小王、小李、小張按從左至右的順序依次入座，編號分別為0、1、2。由于3編號進行相加，就能知道另外兩個人的座位號了。其實，一個影廳的座位可以理解成由一維數組（每一排）組成的二維數組，所謂的“幾排幾號”其實就是二維數組的索引方式。如果影廳有多層，就可以理解為三維數組，座位索引就是“幾層幾排幾號”。圖3- 單鏈表的存儲結構圖隊列（Queue）的數據插入特點是先進先出（FirstInFirstOut，FIFO）。FIFO替換策略、網絡路由器的流量分配策略等。直觀地理解，隊列的例子就是生活中的各種排隊。例如，在火車站出站后打出租車需要排隊，按先來后到的順序依次上車；在食堂窗口前排隊，講究的也是先來后到。因此，我們可以將隊列理解為提供FIFO理解了隊列，棧（Stack）就比較好理解了。棧的數據插入特點是后進先出（LastInFirstOut，LIFO）泛的應用，可以說程序員無時無刻不在和LIFO打交道。一個最典型的例子就是程序中的函數調用。除此之外，在滿足遞歸定義的問題中，棧的運用也比較多。一個深入敵后潛伏的情報組織，每級情報員都分配了若干名下級情報員，相鄰兩級情報員分別叫作彼此的上線和下線。為了防止下線在暴露之后對整個組織造成威脅，上線和下線之間是單向通信的，上線能聯系下線，下線無法聯系上線，并且信息通路不形成環路（如我下線的下線不會是我的上線）。如果每級情報員的下線固定最多有2情報員，那么這種情報結構就是二叉樹結構；如果固定最多有3員，那么這種情報結構就是三叉樹結構；以此類推。不僅結構相似，（根部）圖3- 二叉樹的存儲結構圖既然是樹，就會有高度。從根節點開始向下累積的層數就是樹的高度，如圖3-3中的二叉樹的高度為3。二叉樹之所以被廣泛應用，是因為它最簡單，又最具有代表性。二叉樹的種類有很多，如完全二叉樹、滿二叉樹、平衡二叉樹、霍夫曼樹、B有不同的性質、不同的應用場景，感興趣的讀者可以自行深入了解。二叉樹不像鏈表的順序遍歷那么簡單，因為每個節點最多有兩個孩子節點，所以遍歷方法有4圖3- 二叉樹的遍層序遍歷：1→2→3→4→5→6→7圖（Graph）結構。前面講到的鏈表和樹，其實都是圖的特殊情況，鏈表只能向一個方向進行鏈接，樹的節點之間不允許形成環。圖結構沒有這些限圖3- 有向圖和無向圖是一種非常實用的數據結構，在工作、生活的方方面面都能用到它。例如，如果將每個人作為節點，將人與人之間的關系作為邊，可以構成一個大小為70多億節點的社交網絡圖。著名的小世界現象，你和任何陌生人之間所間隔的人數不會超過6得出的猜想。在計算機世界中，圖經常用于描述任務的狀態轉換和調度關系。例如，節點代表待執行的任務，邊代表任務相關性或依賴順序。圖的存儲方式有兩種，一種是以鏈表形式存儲，每個節點及其相鄰節點都用一個鏈表表示，這種存儲方式稱為鄰接鏈表；另一種是以數組形式存儲，用一維數組記錄所有節點，用一個二維數組記錄所有邊，這種存儲方式稱為鄰接矩陣。鄰接鏈表和鄰接矩陣的優劣對比與鏈表和數組之間的對比類似，鄰接鏈表使用的是鏈表，鄰接矩陣使用的是二維數組。以圖3-5存儲形式如圖3-6所示。圖3- 鄰接鏈表和鄰接矩陣的具體存儲形散列表（HashTable）又稱為哈希表。在講解散列表之前，我們這里補充說明一下什么是時間復雜度。O(N)和O(logN)法復雜度的符號，算法復雜度主要包含兩個方面：空間復雜度和時間復雜度。其中，空間復雜度定性地描述了一個算法運行所需內存空間的數量級，時間復雜度定性地描述了一個算法運行所需時間的數量級。在通常情況下，我們優先考慮算法的時間復雜度。在時間復雜度中，O(N)表示當數據量為N級為線性級別；O(logN)表示當數據量為N時，計算機需要執行的基本運算次數數量級為對數級別。除了O(N)和O(logN)，還有O(NlogN)、O(N2)、O(N3)等，含義以此類推。O(logN)的時間復雜度比O(N)復雜度低，表示O(logN)的算法比O(N)的算法更合適。例如，當N為1024時，logN只有10。O(logN)更低。散列表可以將查詢身份證號碼的時間復雜度降到O(1)，即常數級別。散列表用到的關鍵技術是函數值映射，利用散列函數，將key（姓名字符串）映射到一個有限的數值空間內。例如，一個長度為10億的數組，如果使用恰當的散列函數，那么映射后的值會均勻分布到這個數組中。在查詢時，計算被查詢姓名的散列值，即可直接取出數組中對應下標的身份證號碼。這里你可能會問，姓名有重復怎么辦？沒關系，這個問題在散列表中經常出現，這種現象稱為鍵值沖突。鍵值沖突問題的解決方法比較簡單，在遇到重復key散列值后面增加一個鏈表，用于存儲重復key值。散列表的沖突存儲方式與鄰接鏈表的存儲方式類似，重復的key會被存儲于同一個散列值生成的鏈表中。當然，散列函數直接影響到了鍵值沖突問題的大小，一個映射不均勻的散列函數有可能導致嚴重的鏈表傾斜，即大量數據被映射到同一個鍵值，導致對這些鍵值的訪問退化成順序遍歷，降低檢索效率。針對這個問題，一方面可以選取合適的散列函數；另一方面，在發生鍵值沖突后，可以采取二次散列法和設計公共溢出區等措施。選擇排序（SelectionSort）的基本思路是每次選出剩余序列中時，會從剩下的N-1個元素中選出最值，需要執行N-2以升序排序為例，選擇排序的執行過程如圖3-7圖3- 選擇排序的執行過插入排序（InsertionSort）的基本思路是依次取出序列中的每算；算法在執行第2輪排序時，會取一個元素插入長度為1以升序排序為例，插入排序的執行過程如圖3-8圖3- 插入排序的執行過顧名思義，冒泡排序（BubbleSort）的元素值，將最值像水里的氣泡冒上水面一樣選出來。與選擇排序和插入排序相比，冒泡排序不需要額外的序列存儲空間，在算法執行完成后，原序列即可變成有序序列。對于一個長度為N從原序列的最后一個元素開始。算法在執行第1依次比較相鄰兩個元素值，如果前面的元素值大于后面的元素值，就交換兩個元素的位置，直到第一個元素，需要執行N-1法在執行第2二個元素，需要執行N-2兩個元素值，需要執行1次比較運算。這樣，總的比較次數也是因此冒泡排序的時間復雜度也是O(N2)以升序排序為例，冒泡排序的執行過程如圖3-9圖3- 冒泡排序的執行過快速排序（QuickSort）簡稱快排，是程序員面試時考官最常考值，右序列中的元素值都不小于所選元素值）；算法在執行第2時，當前序列為原序列的左序列，具體操作同前一步；算法在執行第輪排序時，當前序列為原序列的右序列，具體操作同前一步；以此遞推，直到找到所有元素的最終位置，快速排序結束。快速排序由于采用折半操作，因此時間復雜度為O(NlogN)。以升序排序為例，快速排序第1輪排序的執行過程如圖3-10圖3- 快速排序??1輪排序的執行過作會退化成線性操作，時間復雜度也會變為O(N2)。快速排序之所以讓所選元素在數學期望下靠近中間位置。因此，在每一輪排序開始堆排序（HeapSort）堆或最小二叉堆。二叉堆是二叉樹的一種。最大二叉堆是指每個節點的元素值都比其左、右孩子節點的元素值要大的二叉堆，最小二叉堆是指每個節點的元素值都比其左、右孩子節點的元素值要小的二叉圖3- 堆排序??1輪排序的執行過歸并排序（MergeSort）采用遞歸與分治的思想（在3.2.2細詳解），先保證局部有序，再保證整體有序，從局部到整體可以看作一個歸納合并的過程，這也是該排序算法名字的由來。對于一個長度為N的待排序列，以升序排序為例，算法在執行第1輪排序時，原序列中的每個元素都可以看作一個局部有序序列，將相鄰的兩個局部有序序列合并成一個長度為2比較次數為1；算法在執行第2輪排序時，合并相鄰的兩個長度為2部有序序列，得到長度為4的局部有序序列，局部最大比較次數為3；以此類推，直到原序列有序。由此可見，歸并排序總的執行輪次是logN，因此其時間復雜度為O(NlogN)。以升序排序為例，歸并排序的執行過程如圖3-12圖3- 歸并排序的執行過計數排序（CountSort）是一種用更多存儲空間交換更高時間效對于一個長度為N的待排序列，值域為[0,K-1]，初始化一個長度以升序排序為例，計數排序的執行過程如圖3-13圖3- 計數排序的執行過計數排序的最大問題是隨著待排序列值域的擴大，空間復雜度也隨之增加。桶排序（BucketSort）對一的下標映射，而是通過一個映射函數，一對多地將大小接近的數存儲于一個桶中，然后對每個桶中的序列進行排序。如果每個桶中排序的時間復雜度為O(NlogN)，那么桶排序的時間復雜度為∑O(NilogNi間的排序。基數排序（RadixSort）是桶排序的升級版，其基本思路表3-19（Recursion）如果在其定義或說明內部直接或間接地出現其本身的引用，則它們是遞歸的或遞歸定義的。當然，有遞歸就有非遞歸。所謂非遞歸，就是不用層級關系來表達任務，而是將任務拉平成線性關系表達任務。因此，支持遞歸實現的基礎算法會比非遞歸實現理解起來較為簡單直觀。舉個例子，求長度為n別如下。分治（DivideConquerAlgorithm）就是“分而治之”的意思，實質是將原問題分成N個規模較小、結構與原問題相似的子問題，然后遞歸地求解這些子問題，最后得到原問題的解。與遞歸算法相比，分治算法強調的是同層級問題分別治理的過程，而遞歸算法強調的是不同層級問題之間的逐層遞進與回歸的過程。貪婪算法（GreedyAlgorithm）是指每一步都采取當前最好或最優（最有利）否適合使用貪婪算法解決，可以根據無后效性判斷。無后效性是指某個狀態之后的收益，只與當前狀態有關，不受之前狀態的影響。通俗地講，就是眼前的最大收益可以帶來最終的最大收益。現實生活中有不少問題滿足無后效性，下面以經典的貪婪問題──超級書架為例進行講解。問題描述：有N個物品，第i個物品的高度為Hi，還有一個高度為B的書架，保證這些物品的高度之和大于或等于書架的高度BN于書架的高度B。動態規劃（DynamicProgramming，DP）的一種算法。這個定義聽起來有些令人費解，我們不妨對比貪婪算法來理解。貪婪算法認為選擇當前步驟的最大收益可以帶來最終的最大收益。試想，有沒有這樣一類問題，在當前步驟不選擇最大收益，最終的收益卻比貪婪算法的收益高？答案是肯定的。下面給大家介紹一個和超級書架問題類似的經典動態規劃問題──背包問題。包，此時背包的利用率為100%那么，動態規劃是如何得到上面這個解的呢？還是上面的背包問題。如果一開始只有4個容量分別為2、3、5、6包方式就是往4個背包中分別放入2、3、5和6。緊接著，加入3個容量分別為7、8、9的背包，最優的裝包方式分別為，容量為7的背包在裝入容量為5的背包的基礎上再放入2；容量為8的背包在裝入容量為6的背包的基礎上再放入2，或者在裝入容量為5的背包的基礎之上再放入3；容量為9的背包在裝入容量為6的背包的基礎上再放入3。最后，一個容量為10的背包如何裝包，顯然最優方案是在裝入容量為7基礎上再裝入3，或者在裝入容量為8的背包的基礎上再裝入2，包的容量利用率就達到了100%。這便是“多階段最優決策”的一個完整展現。背包問題的動態規劃過程如圖3-14所示。圖3- 背包問題的動態規劃過述。例如，背包問題的遞推公式是f(n)=f(n–c[i])，f(n)單獨介紹。與枚舉相比（如著名的暴力枚舉法），深度優先搜索（DepthFirstSearch，DFS）又稱為深度優先遍歷。深度優先，顧名思義，就是每輪搜索都會從當前節點沿一條路找下去，直到每條路都走到盡頭，即遍歷完所有節點或滿足某個條件，算法結束。圖3-15所示為深度優先搜索示例，起點為A，的遍歷序列為ABDECFG。圖3- 深度優先搜索示寬度優先搜索（BreadthFirstSearch，BFS）遍歷”或“廣度優先遍歷”。寬度優先搜索的每一輪會將距離當前節點最近的節點全部找出來，按這種方法依次找下去，直到遍歷完所有節點或滿足某一條件，算法結束。圖3-16所示為寬度優先搜索示例，BFS的遍歷序列為ABCDEFG。圖3- 寬度優先搜索示最短路徑（ShortestPath）規劃、出行線路規劃等。按照算法規模，最短路徑算法可以分為全局最短路徑算法和單源最短路徑算法。全局最短路徑算法有弗洛伊德算法（Floyd'sAlgorithm），單源最短路徑算法有迪杰斯特拉算法（Dijkstra'sAlgorithm）、貝爾曼-福特算法（Bellman-Ford's弗洛伊德算法是斯坦福大學計算機科學系教授羅伯特·弗洛伊德以當前公認的形式提出的。弗洛伊德算法運用了動態規劃，可以求出一個圖中任意兩點之間的最短路徑。基本思路是每輪選取兩個節點，然后枚舉其他節點，如果經過某個節點能讓選取的兩個節點之間的距離縮短，就更新這兩個節點之間的距離。代碼實現如下，其中f意兩點之間的距離，可知弗洛伊德算法的時間復雜度為O(V3)。圖3- 迪杰斯特拉算法示例流圖3-17以a為起始節點，初始化起始節點的距離為0更新與最優解節點a相鄰的節點b和c更新與最優解節點c相鄰的節點b、d、e更新與最優節點e相鄰的節點d更新與最優節點b相鄰的節點d與最優節點d圖3- 貝爾曼-福特算法示例流圖3-18以a為起始節點，初始化起始節點的距離為0使用與節點a相連的邊更新節點b和c使用與節點b和c相連的邊更新節點b、d、e使用與節點b相連的邊更新節點d最小生成樹（MinimalSpanningTree，MST）首先是一棵樹，Algorithm）和克魯斯卡爾算法（Kruskal'sAlgorithm）。到添加所有節點為止。對于上面的光纜鋪設例子，以A原點，首先添加與之相連且不成環的最短邊AC，然后按算法法則依次添加BC邊、BD邊，直到所有節點均已添加，算法結束，最小花費為6（1+3+2）。普里姆算法的時間復雜度為O(V2)，圖3-19所示。圖3- 普里姆算法的推進步驟示意姆算法的基本思路是以點擴展邊，那么克魯斯卡爾算法的基本思路是以邊擴展點，具體如下：每次從待選邊集中選出與當前森林不成環且最短的邊加入森林，直到所有節點形成一棵樹為止。該思路決定了克魯斯卡爾算法只能從最短邊開始構建最小生成樹。對于光纜鋪設例圖3- 克魯斯卡爾算法的推進步驟示意樹狀數組（BinaryIndexedTree）利用二進制的計算特性，可以在時間復雜度為O(logN)的情況下動態維護一個序列，并且計算其任意子序列中的所有元素之和，算法思路十分簡潔、巧妙。下面從二進制的特性開始，逐步講解樹狀數組的實現思路。0110→1000→10000、0111→1000→10000。觀察這4發現什么規律？沒錯，這種運算總能將原數變為比它大的、最接近的次冪。假設有8個位置，編號分別為1～8，圖3-21所示，灰色代表原數組，黑色代表樹狀數組。圖3- 樹狀數組結構示黑色單元從左至右的相連關系就是上面描述的“加1（B1→B2→B4→B8，B3→B4→B8，B5→B6→B8，B7→B8）。有“加1換”自然就有“減1變換”。“減1變換”能以O(logN)到任意元素的核心子元素，這樣維護和計算任意子序列中所有元素的和就很方便了。例如，對于圖3-21中的B7，通過“減1變換”得到序列（B7→B6→B4），正好可以計算A1～A7圖3- 樹狀數組求在樹狀數組構建完成后，嘗試計算前7個數之和。我們通過“減1變換”在樹狀數組中依次遍歷到0111、0110、0100這3標的元素值為8、6、18。因此前7個數之和為8+6+18=32。如果使用原數組，則需要進行6次加法運算；如果使用樹狀數組，則只需進行2次加法運算。隨著數列長度的增加，樹狀數組的時間優勢會更加明顯。此外，當原數組中某個元素的值增加或減少d時，同樣可以通過“加1變換”來更新樹狀數組中相應的元素值。lowbit(x)=xand(xxor(x-lowbit(x)=xand-x簡化后的最低位計算公式是常數級的計算。樹狀數組查詢和更新的時間復雜度為O(logN)此時間復雜度為O(NlogN)。線段樹（SegmentTree）的概念和它的名字一樣，是以線段（通問題的時間復雜度降至O(logN)。例如，有一個長度為6的序列[3,6,5,1,9]，將其構造成線段樹，如圖3-23圖3- 線段樹結構示上面只說了線段樹的基本特性，而延遲標記是線段樹的精華所一段區間內的值同時增加d十分復雜，時間復雜度為O(N)；而使用線段樹對其進行更新的時間復雜度為O(logN)，初始值均為0。例如，將[0,2]區間內的數均增加4，從根節點開始匹配，發現根節點區間[0,5]包含區間[0,2]，向子節點繼續查詢，發現左節點區間為[0,2]，將其延遲標記值增加4，并且將左節點的值加4，變為10。由于左節點區間為[0,2]，因此不再向下查詢，開始回溯，將根圖3- 線段樹的更在圖3-24中，三角形內的數字代表每個節點的延遲標記值。之后的每次最大值查詢，如果當前節點的延遲標記值大于0，詢時會帶走延遲標記，重復上述延遲操作，直到完全匹配。這種延遲查詢的方式大大提高了序列更新與查詢的效率。接前文，可知當前延遲標記在[0,2]區間內的節點上，在查詢[0,1]區間內的最大值時，帶上延遲標記從[0,2]區間內的節點向左子樹走，更新的是[0,1]區間內節點的值，即得到查詢結果。更新后的線段樹如圖3-25所示。圖3- 更新后的線段在更新后，[0,1]區間內的最大值為7要帶走延遲標記，那么為了保持左、右孩子節點的正確性，至少需要往每個孩子節點上帶一次延遲標記，在圖3-25中，[0,1]區間雖然在左子樹上，但延遲標記同樣需要往右子樹帶過去。平衡二叉樹（BalancedBinaryTree）是由G.M.Adelson-Velsky索樹（BinarySearchTree），所以在講解平衡二叉樹之前，不妨先二叉搜索樹是能夠表達一定元素順序的二叉樹。由于從樹根往下能進行二分查找，因此二叉搜索樹通常能在O(logN)找某些節點的元素值。但是，不加條件的二叉搜索樹往往容易退化成鏈表，使時間復雜度變成O(N)。平衡二叉樹的全稱為平衡二叉搜索樹，主要用于解決左、右子樹高度平衡問題。為了解決二叉搜索樹退化成鏈的問題，平衡二叉樹可以保證任意節點的左、右子樹高度差不大于1系的情況下，普通的二叉搜索樹與平衡二叉樹之間的區別如圖3-26所示。圖3- 二叉搜索樹與平衡二叉樹之間的區呢？我們可以先想想左、右子樹高度差大于1圖3- 左、右子樹高度差大于1的4種情根據圖3-27可知，通過鏡面變換，圖3-27（a）和圖3-27（d）可以歸為一類，圖3-27（b）和圖3-27（c）可以歸為一類。為了將左、右子樹高度差大于1種旋轉操作實現。單旋。對于圖3-27（a），將B提到樹根，A變成B點，E變成A的左孩子節點，即可將該二叉搜索樹轉換為平衡二叉樹，具體變換操作如圖3-28所示。同理可單旋圖3-27（d）。圖3-27（a）和圖3-27（d）和右旋。圖3- 單圖3- 雙任意一棵二叉搜索樹，從葉子節點開始，通過單旋或雙旋一直變換到根節點，可以保證任意節點的左、右子樹高度差不大于1叉樹的建樹變換時間復雜度為O(NlogN)。此外，平衡二叉樹還有紅黑樹、SBT、Treap、伸展樹等幾個變種，感興趣的讀者可以深入學習。并查集（DisjointSet）并非常用的基礎算法，卻也是一種很有問題描述：有N個人，約定存在血緣關系的為親人，并且如果X和是親人、Y和Z是親人，則X和Z也是親人。現給出M證這N個人都已涵蓋在內。計算這N個人中一共有多少個家族，以及需要詢問多少次任意兩人是否屬于同一個家族（詢問次數用T表示）。根據題目描述，不難想到暴力枚舉法，即每次將有血緣關系的兩個人所屬的家族集合編號賦值為同一個值。可想而知，當N、M、T時，算法時間復雜度不可估量。此時，并查集橫空出世。如，有5組血緣關系，分別為(a，b)(b，c)(d，e)(d，f)(d，b)，在圖3-30中，字母后面的數字代表家族編號。首先，(a，b)表示和b有血緣關系，將b所在的樹根指向a樹；然后依次按照此規則更新(b，c)(d，e)(d，f)(d，b)這4組血緣關系。值得注意的是，在處理血緣關系(d，b)時，由于b族樹的根節點，因此需要先找到根節點a，再將a指向d止樹退化成鏈表，通常將深度較小的樹的指針指向深度較大的樹的根節點，因此需要將圖3-30（f）衡結構，如圖3-31所示。圖3- 并查集的構建步圖3- 并查集的平衡結不難發現，即使按照上面所講的平衡結構構建并查集，也會面臨兩個問題：其一，要合并的兩棵樹，如果當前節點距離各自根節點的距離并非最長距離，則會直接導致平衡結構構建失敗；其二，即使構建了平衡結構，本身過長的分支也仍然存在。平衡結構只是并查集的一種簡單優化，并查集最有效的優化方法為路徑壓縮化思想如下：在每次找樹根時，將經過的所有節點都指向根節點，將較長的路徑變成多子樹。使用路徑壓縮方法優化并查集的時間復雜度為O(MlogN)，而每次查詢的時間復雜度為O(C)，是常數級別。使用路徑壓縮方法進行優化的并查集構建步驟如圖3-32所示，其中路徑壓縮在第（c）步體現。圖3- 并查集的路徑壓縮構建步匈牙利算法主要用于求解二分圖的最大匹配問題。二分圖又稱為二部圖，是一種特殊的圖。假設G=(V,E)是一個無向圖，如果頂點集可以分割為兩個互不相交的子集(A,B)，并且圖中的每條邊(i,j)所關聯的兩個頂點i和j分別屬于這兩個不同的頂點集(iinA,jinB)，則稱圖G相連但不相交的邊數最多。問題描述：現在有一個8人的小型化裝舞會，一共有4男4生分別標記為A、B、C、D，將女生分別標記為a、b、c、d。現在化裝舞會需要男女配對組成4知A與a、b、c相識，B與a、d相識，C與c、d相識，D只與b相識，熟人關系如圖3-33所示。為了讓大家都能與一個熟人作舞伴，要如何給這個人配對？圖3- 二分圖中的熟人關針對上述例子，匈牙利算法的執行步驟如圖3-34圖3- 匈牙利算法的執行步按ABCD的順序進行匹配，先匹配A和B。加粗虛線表示當前找到的增廣路，加粗實線表示當前的配對。首先，圖3-34（a）找到增廣路A→a，圖3-34（b）將增廣路中的A和a配對；然后，圖3-34（c）找到增廣路B→a→A→b，圖3-34（d）將增廣路中的A和aB和a、A和b分別配對。這里可以看出，由于二分圖的性質，增廣路中每隔一條邊匹配一條邊，總能保證配對最大。接著配C和D。圖3-34（e）找到增廣路C→c，圖3-34（f）將增廣路中的C和c配對，圖3-34（g）找到增廣路D→b→A→a→B→d，圖3-34（h）將增廣路中的Ba、A和b解除配對，然后將D和b、A和a、B和d無增廣路，匈牙利算法結束。可知在每次查找增廣路時，在最差情況下會遍歷所有邊。因此匈牙利算法的時間復雜度為O(NM)，其中N表示二分圖半邊的點數，M表示二分圖的總邊數。在線評測系統（OnlineJudge，OJ）是一種在編程競賽中評測參表3-2OJ根據題目類型，可以將題目分為6類，分別為SystemDesign、OODesign、OperatingSystem、Algorithms、Database和Shell；目難易程度，可以分為3類，分別為Easy、Medium和Hard個總的提交通過率，并且提供解題思路留言討論區。題庫還會提供若干個專題標簽，用于給刷題者提供有針對性的索引。例如，算法類別專題標簽有數組相關、圖相關、動態規劃相關；公司面試劃分專題標簽有谷歌公司面試最熱100題、Facebook公司面試最熱100題等。POJ與POJ（PekingUniversityOnlineJudge，系統）是一個提供編程題目的網站，它包含3000多道程序設計題，題目大部分來自ACM多題目可以反映工作和生活中的實際問題。ZOJ（ZhejiangUniversityOnlineJudge，測系統）是一個提供信息學（算法競賽）題庫及進行在線程序評測的網站，它也包含3000多道程序設計題，題目大部分來自ACM程序設計競賽、全球各大賽區及著名大學的競賽。很多人或許沒有聽說過Tsinsen其背后的開發者有所耳聞，那就是兩屆IOI科學實驗班畢業的胡偉棟。清橙網絡自動評測系統和胡偉棟，對筆者而言并不陌生，因為筆者和胡偉棟曾就讀于同一所高中，而且筆者也算是清橙的首批用戶。筆者記得在剛上高一時，參加了學校的信息學競賽興趣小組。那時我們不像現在有五花八門的OJ用于學習編程，尤其對于DIY動評測甚是麻煩。清橙網絡自動評測系統就是那時由胡偉棟開發的一個自動評測系統，專門用于模擬競賽評測。該系統后來升級，搬到了網上，也就是現在的清橙網絡自動評測系統。比較遺憾的是，清橙網絡自動評測系統于2019年9月1日不再對外提供服務。背包問題有很多變種與升級版本，本書講解的是01也是最基礎的背包問題。如果同一種物品可以無限裝包，這樣的背包問題稱為完全背包問題。那么，動態規劃如何解決完全背包問題？導彈攔截問題，每次的導彈攔截高度都不能高于前一次，現在連續有N枚導彈襲擊，高度分別為Hi（i為1～N的整數），少枚導彈？寫出動態轉移方程即可。POJ與第4算法之武功所有機器學習算法都是基于樣本學習的。有標簽的樣本，相當于一個有經驗的師父提前告訴你學習的目標是什么，以此監督你的學習過程，這個標簽稱為監督信號。帶監督信號的機器學習稱為監督學習（SupervisedLearning），反之稱為無監督學習（Unsupervised習（Semi-SupervisedLearning）。顧名思義，半監督學習就是所用常見的監督學習算法有線性回歸（LinearRegression）、邏輯回歸（LogisticRegression）、K-近鄰（K-NearestNeighbor，KNN算法）、決策樹（DecisionTree）、樸素貝葉斯（NaiveBayes）、神經網絡（NeuralNetwork），還有用于降維的算法——線性判別分析（LinearDiscriminantAnalysis，LDA）法，其共同點都是教什么就學什么。即通過學習，使模型輸出結果與指定樣本標簽值盡可能地接近。與監督學習相比，無監督學習沒有監督信號，它利用未知標簽的樣本調整模型參數，學習某種特征、規律、趨勢或既定模式，從而達到所需性能要求的過程。放眼望，人類從原始社會一路走來，文明的進步何嘗不是處處伴隨著無監督學習？還以動物卡片為例，人類最開始并不知道猴子叫猴子、獅子叫獅子，只知道某類動物具有相同或類似的外貌特征。例如，某類動物經常用手撓頭、活潑好動，喜歡在樹上竄來竄去；某類動物體格健壯，頸部覆蓋著厚厚的鬃毛，食肉。久而久之，同類型具有相同行為規律與外貌特征的動物，隨著時間的推移逐漸被稱為猴子和獅子。這便是無監督學習的過程，這種將動物歸類的方法，其實就是無監督學習中的典型算法——聚類。圖4-1為一個無監督學習示例。圖4- 無監督學習示常見的無監督學習算法除了聚類（Clustering），──主成分分析（PrincipalComponentAnalysis，PCA）。聚類可以如果以上3學習性能起改善作用，反而會損壞學習性能，導致半監督學習失效。但是，還有一些實驗表明，在一些特殊情況下，即使前提假設成立，無標簽樣本也有可能損壞模型的學習性能。因此，要開展半監督學Clustering）、生成對抗網絡（GenerativeAdversarialNets，GAN）、半監督分類（Semi-supervisedClassification）及一些基于類別，用于答“是”或“不是”類問題；銷量預測、股票預測的算法模型，目的是預估某類數值的大小，用于答“多少”類問題。這樣，按照學習目標劃分，可以將機器學習算法模型分成四大類。答（Classification），答“多少”類問題的算法模型統稱為回（Regression）。除了分類和歸，另外兩類算法分別是聚（Clustering）和降維（DimensionalityReduction）分類和歸的直觀區分方法如下：模型的最終預測值如果是離散歸。有讀者或許已經發現，無論是分類還是歸，模型訓練用的都是事實上，分類和歸已經涵蓋了機器學習中的大部分熱門模型，如最近幾年特別流行的神經網絡及其一系列變種（卷積神經網絡、循環神經網絡等）。常規的聚類屬于無監督學習，當然也存在半監督聚類算法。降維主要有無監督學習的主成分分析（PCA）的線性判別分析（LDA）算法等。線性歸模型與邏輯歸模在監督學習模型中，線性歸模型和邏輯歸模型是最經典的兩個模型，其中邏輯歸模型適用于大部分監督學習問題。不僅如此，學好線性歸模型和邏輯歸模型，對神經網絡的學習也大有幫助。線性歸模線性回歸模型是最簡單、直觀的機器學習算法模型之一。線性是指特征值與輸出值之間是一次函數關系。例如，對于f(x)=ωx+b，其中x是特征值，f(x)表示輸出值。歸是指通過調整一次函數的參數，使其盡可能準確地擬合數據的過程。我們不妨從最簡單的單特征線性歸模型講起。所謂單特征，就是一個特征，假設預測目標只與一個因素相關。例如，要預測北京市房價，單特征是每套房子的建筑面積，我們的假設就是北京房價只與建筑面積有關。假設北京房價和建筑面積的關系如圖4-2橫坐標和縱坐標分別是建筑面積和每平方米價格。圖4- 建筑面積與房價關系線性歸模型的目標是盡可能準確地擬合數據，即在圖4-2中找到一條直線，使圖中各點盡可能地接近這條直線。單特征線性歸模型公式為f(x)=ax+b，x為建筑面積，f(x)為每平方米的價格，a和b是權重參數，其中b稱為偏置（Bias），單特征下的a是一個標量，多特征下的a是一個向量。那么，圖4-2中有這么多不同建筑面積的房價，如何找到一條合適的直線來表示它們的關系變化？這就說到機器學習中的模型訓練方法了，目前最常用的模型訓練方法為梯度下降法（GradientDescent）。下面講解梯度下降法具體是如何訓練，從而歸模型擬合的直線經過原點，并且只考慮一個樣本數據點(1,4)，那threshold=0.01(2.2,-0.18)，(2.38,-0.162)，(2.542,-0.1458)，……直到loss0)，因此訓練得到的歸函數為f(x)=4x，訓練迭代次數與loss之間圖4- 訓練迭代次數與loss值之間的變化關當然，房價不可能只與建筑面積這一個因素有關系，機器學習算法模型的特征空間通常也不會只有一個維度。因此，一般使用向量x示多特征值，使用向量ω表示多特征權重，使用標量b歸模型的公式就可以表示為f(x)=ωx+b。偏置的作用是無論在幾維空間，歸函數都可以表示不經過原點的圖像。通常將偏置也放到ωx中，具體做法是令特征向量x的每一維從下標1開始編號，將偏置作為權重ω0與構造的特征值x0=1一起合入ωx的乘積之中。這樣，線性歸模型公式就簡化成了f(x)=ω0～nx0～n。邏輯歸模對于線性歸模型公式f(x)=ωx，其值域（取值范圍）是未知的，f(x)相當于在計算ωx之后，直接用線性函數y=x活”輸出。線性歸模型之名由此得來，y=x則被稱為線性激活函數。既然有線性激活函數，自然就有非線性激活函數，非線性激活函數可以將未知值域映射到一個已知的值域范圍內。其中最有名的非線性激活函數之一為Sigmoid函數。將Sigmoid函數作為激活函數的歸模型稱為邏輯歸模型。Sigmoid函數的公式為Sigmoid函數的圖像如圖4-4圖4- Sigmoid函數的圖1)。將輸出值映射到(0,1)區間，目的是方便設定閾值完成二分類。無論特征維度的值是多少，邏輯歸模型都會利用閾值設定，在這個除了Sigmoid函數，下面介紹另外3種常見的激活函數，它們分別為Sgn函數、Tanh函數和ReLU函數。其中ReLU泛。圖4- Sgn函數的圖雙曲正切函數Tanh可以解決Sigmoid函數的輸出值恒大于0題。其值域為(-1,1)，相當于將Sigmoid函數沿著縱軸拉伸了一倍，Tanh函數的圖像如圖4-6圖4- Tanh函數的圖為[0,+∞)，其函數圖像如圖4-7所示。圖4- ReLU函數的圖經網絡（ArtificialNeuralNetwork，ANN）。與人腦神經網絡類圖4- 人工神經元的數學描對于人工神經元構成的單層模型，激活函數不同，相應的名稱也不同。事實上，線性歸模型和邏輯歸模型都屬于人工神經網絡的范疇。其中，使用線性激活函數f(x)=x的單層神經網絡模型，就是節中的線性歸模型；使用非線性激活函數Sigmoid的單層神經網絡模型，就是4.2節中的邏輯歸模型；使用階躍函數作為激活函數的單層神經元模型，學術名稱為感知機（Perceptron）。下面通過一個簡單的例子講解什么是單層神經元模型。假設有一男一女兩個人，身高、體重分別是1.8m、70kg和1.6m、50kg，我們用這兩個樣本訓練出一個能判斷性別的單層神經元模型。使用Sigmoid在上述表達式中，x為特征輸入（身高x2,體重x1,偏置1），w要學習的特征權重。將兩人的特征數據（1.8,70,1）和（1.7,50,1）重復輸入模型中，用于學習參數向量w的值，學習方法采用前文講到的梯度下降法，直到f(x=(1.8,70,1))和f(x=(1.7,50,1))的值分別趨向0和1，訓練結束。除此之外，人工神經網絡衍生出了各式各樣的結構變種，如深度神經網絡、卷積神經網絡、遞歸神經網絡和圖神經網絡等，并且開辟了形形色色的研究方向。顧名思義，深度神經網絡（DeepNeuralNetwork，DNN）的神經圖4- 常規的深度神經網絡結所有機器學習算法的學習目標，都是尋找輸出與輸入之間最合適的映射關系。在圖4-9用線性函數y=x出都會是原始輸入經過線性變換的結果，最終效果相當于單層人工神經元模型的效果。與線性變換相比，非線性變換能夠表達的信息要豐（ComputerVision，CV）領域的深度運用，以及圖形處理（GraphicsProcessingUnit，GPU）樣，感知并識別這個五彩繽紛的圖像世界。例如，從1000萬張圖片中識別出貓的GoogleBrain，以及擊敗人類圍棋世界冠軍的人工智能機器人AlphaGo，背后都用到了一種圖像識別技術，即卷積神經網絡（ConvolutionalNeuralNetwork，CNN）要理解卷積神經網絡，先理解什么是卷積。我們不妨將“卷積”一詞拆開來理解，“卷”意為翻卷，可以理解為數學變換中的翻轉和平移的意思；“積”可以理解為積累、相加、翻倍的意思，因此“卷積”表示一種簡單的數學操作。卷積操作通常被看作加權滑動平均法的一種推廣。卷積神經網絡就是運用了卷積操作的一種神經網絡，運用卷積操作的神經網絡層稱為卷積層（ConvolutionalLayer）。卷積層由卷積核組成，卷積核的計算類似于人工神經元中y=ωx+b只是輸入不限定是一維的xi，可以是二維圖像中的一個像素點xi,j，也可以是三維空間中一個物體在某一點的描述xi,j,k。每個卷積核通過學習不同的參數，可以感受局部視野，并且提取不同的局部特征。假設有一張3×3的圖像，卷積核為2×2，卷積核內初始權重均為1，那么卷積操作的計算方法如圖4-10所示。 左下：4×1+1×1+7×1+9×1=21右下：1×1+5×1+9×1+3×1=18卷積神經網絡除了包含卷積層，還包含池化層（PoolingLayer）受視野范圍內的最大值作為輸出，均值池化是指每次取感受視野范圍內的平均值作為輸出。池化層一般放在卷積層的后面計算，用于減少深度神經網絡訓練的參數數量，提高深度神經網絡的訓練速度和泛化能力。以最大池化為例，池化大小為2×2，圖4-10中圖像的池化操作計算方法如圖4-11所示。圖4- 池化操作的計算方法示在圖4-11左上1}=4左下9}=9右上5}=6右下3}=9當然，卷積神經網絡的網絡結構除了包括卷積層和池化層，還包括神經網絡都有的組成部分，即輸入層、全連接層和輸出層。卷積神經網絡在計算機視覺和圖像識別領域發揮著至關重要的作用，如著名的AlexNet網絡結構（詳見第7章圖7-1）。AlexNet是2012年ImageNet競賽冠軍獲得者Hinton和他的學生AlexKrizhevsky后，很多更深的卷積神經網絡相繼被提出，如VGGNet和GoogLeNet。遞歸神經網絡（RecursiveNeuralNetwork，RNN）經網絡（RecurrentNeuralNetwork），它會將一個網絡結構單元的輸出作為該網絡結構單元在下一時刻的輸入，所有神經網絡層之間的銜接與串聯都會在時間維度上展開。一個典型的遞歸神經網絡結構如圖4-12所示。圖4- 典型的遞歸神經網絡結在圖4-12遞歸神經網絡模型，叫作長短時記憶（Long-ShortTermMemory，圖4- 長短時記憶模型的網絡結在圖4-13中，大長方形框住的整體稱為記憶單元，實線箭頭表示當前時刻的信息傳遞，虛線箭頭表示上一時刻的信息傳遞。與典型的遞歸神經網絡模型相比，長短時記憶模型一共增加了3這3個神經網絡層在學術上分別稱為輸入門（InputGate）、遺忘門（ForgetGate）和輸出門（OutputGate）Cell（GatedRecurrentUnit，GRU）力（Attention）音識別、圖像識別、疾病預測等領域都發揮著驚人的作用，是當下最流行的神經網絡模型之一。圖神經網絡（GraphNeuralNetwork，GNN）的神經網絡。在講解圖神經網絡之前，我們先顧一下什么是圖。根據第3章內容可知，圖由頂點和邊兩部分組成。邊可以分為有向邊與無向邊，包含有向邊的圖稱為有向圖，不含有向邊的圖稱為無向圖。圖結構在現實生活中是廣泛存在的，網站之間的超鏈接引用關系、社交網絡中的朋友關系、學術界論文之間的引用關系都可以用圖結構表圖4- 常規的圖神經網絡結圖神經網絡一般不直接用于進行分類或歸，通常將其作為圖的一種表征學習融入其他模型的特征輸入中。圖的表征學習是指將圖中的各種信息映射成一個N維特征向量，這種映射關系在機器學習中稱為特征嵌入（FeatureEmbedding）。圖中各種信息的嵌入統稱為（GraphEmbedding）。圖嵌入最常見的用法有兩種，分別為（NodeEmbedding）和邊嵌入（EdgeEmbedding）。如果輸出信息是經過各種嵌入后的特征向量可以和其他特征拼接使用，也可以直接輸入神經網絡的全連接層，繼續加入模型進行學習。除了點嵌入和邊嵌入，還有整圖嵌入（Whole-GraphEmbedding），分子結構、蛋白質結構的分析探索中有較廣泛的應用。無論是歸模型，還是神經網絡模型，都要通過純數學變換和層難以直觀理解。尤其是深度神經網絡，即使最后的分類或歸效果可本節介紹機器學習算法中可解釋性最強的模型之一——（DecisionTree）。近幾年已經有學者研究如何利用決策樹的性質解決策樹是一種樹形分類和歸模型，每個非葉子節點都相當于一個IF條件判斷語句，模型通過逐個判定特征所屬類別，對樣本逐步進行分類。決策樹模型不僅可解釋性強，解決問題的角度也趨近于人類看待問題和理解問題的視角，比較簡單、直觀。下面通過一個例子，初步講解決策樹的工作原理。有10條關于西瓜的樣本數據，如表4-1示，我們要根據這些數據學習如何判斷一個西瓜是否為好瓜。表4-1西瓜樣本數據集圖4- 決策樹模型圖4- 決策樹模型得到分類效果較好的決策樹呢？這涉及信息論中的一個概念——增益（InformationDivergence）。說到信息增益，不得不先介紹（Entropy）息量（p·log(1/p)，0<p≤1）們也不會覺得有時候說的話雖然多，卻沒什么信息量，而有的話卻能一語中的。信息增益作為設置決策樹特征考查順序的依據，可以直觀理解為，在按照當前設置的特征考查順序劃分數據集后，如果可以最大程度減少數據的混亂程度，那么該特征考查順序是好的特征考查順序。-log1=ID3算法每次選擇最大信息增益的特征作為父節點，向下擴展決必然等于最大值1。顯然，這樣的決策樹泛化能力是最弱的。因此，C4.5算法應運而生，該算法使用信息增益率的概念（信息增益除以數據集中該特征的總信息量），大致思路如下：先選出信息增益高于平均水平的特征，再從中選擇信息增益率高的特征，用于當前分裂。此外，還有一種CART算法，使用基尼指數選擇特征，也能增強決策樹的泛化能力。在決策樹變復雜之后，由于判斷分支過多，因此訓練集中的某部分樣本特征被當作所有樣本的一般性質，就出現了過擬合（Overfitting）預剪枝和后剪枝兩種。梯度提升決策樹（GradientBoostingDecisionTree，GBDT）一個與梯度有關、對決策樹進行提升的機器學習模型。梯度提升決策樹可以是分類樹，也可以是歸樹。我們不妨從后往前依次分解DT、B、G這幾個定語，逐步理解GBDT的精髓。DT（DecisionTree，決策樹）。決策樹分為分類樹和歸樹兩種。歸樹與分類樹的原理機制相似，區別在于分類樹只在葉子節點返唯一分類，而歸樹的每個節點都能返一個歸值，通常為當前節點內所有樣本的平均值。G（Gradient，梯度）間的距離或差異。因此，在上述的串行建模過程中，除了第一棵決策樹使用原始樣本數據進行訓練外，之后的每一棵決策樹都使用前一棵決策樹的預測值（平均值）與實際值之差（負梯度，可以理解為殘差或增量）進行建樹。這相當于對分錯的樣本有針對性地繼續分類，使樣本的總體殘差趨近于0目標的殘差或增量進行建模預測，因此梯度提升決策樹模型需要將串行建樹過程中每一棵決策樹的輸出結果相加，才能得到最終的預測輸出結果。下面通過一個經典例子“預測年齡”來講解梯度提升決策樹的具體工作過程。假設有4個樣本，其特征描述分別如下。樣本A，消費較高、經常被學弟問問題，27樣本B，消費較高、經常問學長問題，23樣本C，消費較低、經常被學弟問問題，17樣本D，消費較低、經常問學長問題，13梯度提升決策樹串行建模的過程如圖4-17圖4- 梯度提升決策樹串行建模的過梯度提升決策樹的核心思想概括如下：串行訓練n（n>2）策樹，其中第i（1<i≤n）棵決策樹學習第i-1棵決策樹的負梯度（理解為殘差或增量），將n棵決策樹的輸出結果累加作為最終輸出結果。隨機森林（RandomForests，RF）是指由多棵決策樹組成的決策樹森林。組成隨機森林的決策樹既可以是分類樹，又可以是歸樹。與梯度提升決策樹模型相比，隨機森林模型的原理更直觀、簡潔，性能也更強悍。隨機森林算法的核心思路有兩個：采樣和完全分裂樣分為行采樣和列采樣，這里的行與列對應的是樣本與特征兩個維對于列采樣，每一棵決策樹都從M個特征中隨機挑選m個特征作為節點分裂特征來計算。在一般情況下，m為M的算術平方根。列采樣分為兩種方式，一種是全局列采樣，即同一棵樹的建樹過程均采用同一批采樣的特征；另一種是局部列采樣，即每一次節點分裂均單獨隨機挑選m不會出現過擬合的問題。如果是歸樹，則計算所有結果的平均值。對于連續型特征的距離度量，最常用的是閔可夫斯基距（MinkowskiDistance），閔可夫斯基距離有兩個明顯的缺點：一是特征之間的量綱（距離（MahalanobisDistance）、余弦相似度（CosineSimilarity）、皮爾遜相關系數（PearsonCorrelation對于離散型特征的距離度量，最直接的度量方法是0/1對應位置的特征相同則為1，不同則為0，累加值的大小體現了樣本之間的相似程度。基于0/1匹配法，還可以使用杰卡德相似系數（JaccardSimilarityCoefficient）進一步計算樣本特征之間的距離。指定兩個集合A和B，將杰卡德相似系數定義為A與B交集中的元素數量與并集中的元素數量的比值，計算公式如下。杰卡德相似系數的值越大，說明相似度越高，當A和B都為空集時，杰卡德相似系數為1DifferenceMetric，VDM）。值差分度量法的使用前提是樣本必須是隨機選擇k個樣本作為初始的k將樣本逐一劃分到與這k根據上述算法執行流程可知，k深。因為類別的中心點坐標是根據樣本特征距離的平均值更新的，所以一旦出現離群較遠的樣本數據，中心位置就會受到很深的影響。基于這個問題，k中心點（k-Medoids）算法和k中值（k-Medians）算法應運而生。k別下的數據點，計算當前類別下其他數據點到該點的距離之和，將距離之和最小的點定為新的類別中心點。也就是說，k中心點坐標一定是一條具體的樣本數據，而不是計算出來的特征距離平均值。與k中心點算法不同，k中值算法在每次更新類別中心點坐標時，都會將類別中心點更新成同類別下所有樣本數據的中位數，直到每個類別的中位數不再發生改變。k中心點算法和k中值算法雖然都在一定程度上解決了噪聲和離群點問題，但是由于在更新類別中心點坐標時不再是簡單地取平均值，因此算法的時間復雜度會隨之增加。此外，k特征數據，就需要使用離散型特征的距離度量法進行距離度量。這時會有個新的算法——k-Modes算法。k-Modes算法的距離度量法可以是交集中的元素數量、杰卡德相似系數等。所謂層次，就是類似于樹結構的展開與溯，逐層合并或拆分樣本數據集。逐層合并是自底向上的聚類方法，稱為凝聚層次法使用凝聚層次法，那么開始的每個樣本都是一個類，然后根據相似性度量法尋找同類樣本，自下而上逐層地形成較大的類別。逐層拆解是自頂向下的聚類方法，稱為分裂層次法開始的所有樣本都屬于同一個大類，然后根據相似性度量法逐層拆分樣本，自上而下逐層形成較小的類別。SpatialClusteringofApplicationwithNoise）為比較有代表性核心點。在鄰域R范圍內數量不小于N如果只采用核心點計算聚類，那么可以將DBSCAN算法看作k法的變種。因為加入了邊界點和噪聲點的計算，所以DBSCAN算法比一般的聚類算法更強大。DBSCAN算法的執行流程如下。將鄰域R范圍內的核心點連接成邊，從而形成連通圖G計算連通圖G中的連通分量GCCi，連，則稱p密度可達q；如果核心點p可以分別密度可達邊界點q和s，稱q和s密度相連。密度可達屬于密度相連，密度直達屬于密度可達。根據密度概念我們發現，每個類中的任意兩點之間都是密度相連的。圖4- 密度概念區顧名思義，高斯混合模型（GaussianMixtureModels，GMM）由隨機生成k個高斯分布作為初始的k單特征的高斯混合模型聚類算法的執行流程圖例如圖4-19圖4- 單特征的高斯混合模型聚類算法的執行流程圖如果樣本數據集是多維情況，則需要計算協方差，將不同維度之間的關聯性考慮進來。高斯混合模型聚類和k別個數的初始值影響較大。不過高斯混合模型聚類完的樣本可以同時屬于多個類別，這種聚類又稱為軟聚類。其他的模型聚類算法還有基于PageRank的軟聚類算法、基于神經網絡模型的自組織映射（Self-OrganizingMaps，SOM）聚類算法等。托馬斯·貝葉斯（ThomasBayes，1702—1761）是18世紀英國的圖4- 加法公式示意P(B|A)表示在事件A發生的前提下，事件B發生的概率，即事件B條件概率。直觀理解，乘法公式的意思是事件A和B同時發生的概率，與事件A發生的概率和事件B的條件概率之積相等，并且與事件B概率和事件A的條件概率之積相等。因此乘法公式又稱為條件概率公式，其示意圖如圖4-21圖4- 乘法公式示意其中D是樣本數據集，P(h)h的初始概率，即前面提到的先驗概率，先驗概率反映了關于目標h的所有前提認知。而在機器學習中我們通常更關心后驗概率P(h|D)，即樣本訓練集D中目標h成立的條件概率。在全概率公式中，Bi表示兩兩不相同的時間段，P(A|Bi)表示在Bi時間段內事件A發生的概率，由于Bi兩兩不相容，因此事件A式P(A)可以看作加法公式。在機器學習中，如何利用上面講到的兩個概率和4呢？這便是樸素貝葉斯分類要做的事情。貝葉斯分類是指根據已分類樣本的先驗概率，估計待分類樣本的后驗概率。使用貝葉斯公式表示分類目標函數如下（其中c為類別，x為樣本）：但是，在樣本具備多個特征的情況下，很難根據訓練樣本得到上式中條件概率P(x|c)的概率分布。針對這個問題，樸素貝葉斯分類應運而生。樸素貝葉斯分類避開了這個難題，對條件概率P(x|c)的概率分布做了條件獨立的假設，即不同特征之間兩兩不相關。既然滿足條件獨立，就可以采用乘法公式計算P(x|c)的概率分布，公式如下（d特征總數）：其中，P(c)可以直接統計訓練樣本中各個類別的比例。對于條件概率P(xi|c)，如果x是離散型特征，則可以通過計算在c類別中第i性取值為xi的比例。如果x是連續型特征，則需要先假設特征符合某種分布規律，如常見的二項分布、高斯分布、泊松分布、伯努利分布需要注意的是，在計算條件概率的過程中，有可能出現概率為0的情況，從而導致連乘之后的值為0。這里需要引入拉普拉斯平滑系數簡單理解就是分子、分母同時加上一個常數，用于避免概率為0的情況發生。可以證明，當訓練集足夠大時，加入拉普拉斯平滑系數的估計值會趨近真實的概率。支持向量機（SupportVectorMachine，SVM）的分類模型。與邏輯歸模型、神經網絡模型相比，支持向量機有更強的數學理論背景。因此與其他分類模型相比，支持向量機的學習門檻相對較高。在4.2子中，我們給每個樣本增加一個“是否成交”標簽。在構建樣本數據點后，使用線性歸模型得到的分類結果如圖4-22所示，其中房價和圖4- 線性回歸模型的分類結顯而易見，線性歸能將“已成交”和“未成交”的樣本數據劃在形式上，支持向量機的模型公式和線性歸模型公式一樣，也在圖4-23圖4- 支持向量機的分類結大家不妨先憶一下點到直線的距離公式。直線方程為Ax+By+C=0，點的坐標為(x0,y0)，點到直線的距離公式如下：根據該公式可知，如果要最大化這個距離，則需要最小化權重向量w的L2范數。樸素的支持向量機和加了L2的線性歸模型幾乎一模一樣，所有我們可以像訓練線性歸模型一樣訓練支持向量機。此外，使用拉格朗日乘數法（LagrangeMultiplierMethod）和KKT條件（Karush-Kuhn-TuckerConditions）有助于更優雅地解決支持向量機邏輯歸和線性歸相比，非線性映射函數Sigmoid的優勢體圖4- 深度神經網絡結構示ReLU圖4- 卷積神經網絡某一層的圖嘗試推導出4.3.4嘗試推導出4.3.4解了最常見的幾種機器學習算法，包括線性歸、邏輯歸、人工神關鍵詞線性歸邏輯歸線性歸邏輯歸k第5算法工程的本章會從原始數據的預處理開始，到算法模型驗收為止，逐步講解算法工程的完整流程。這個流程主要包括5特征工程、建模與調參、效果評估和模型托管。數量除以batchsize，再乘每批次訓練花費的時間，就能估算出一個一份擁有512條數據、特征維度為1000的數據集，假設batch為128，一個epoch包含4個batch，epoch和batch之間的關系如圖5-1示。圖5- epoch和batch之間的關少，如只有1程，因為針對極端比例下的類別樣本數據集，無論是模型訓練，還是模型評估，都會完全失效。事先統計各類別樣本的數量，能提前發現樣本不均衡的問題，尤其在類別樣本比例差別較大時，一方面能幫助劃分訓練集、驗證集和測試集的大小，另一方面可以對樣本進行重采樣或降低采樣比例。樣本不均衡問題會在5.2.3一步講解。圖5- 動物分類數據集中不同動物類別的數量統計結型，都不可能得到百分之百精確的結果。訓練再好的歸模型，也不可能將預測值與真實值之間的預測誤差降為0；類模型，也不可能保證每次的分類結果一定是正確的。在機器學習算法工程中，我們的工作是盡可能地逼近目標和真相。除了繼續調參優化模型，在數據層面，一方面，可以通過?觀把握數據提前發現問第一，抽樣觀察用戶個體維度的行為數據，換位思考，設身處地觀察具體的用戶行為序列，可以幫助我們更好地理解業務。行為數據是指用戶在時間維度上的連續動作，如頁面曝光、鍵盤輸入、頁面點擊、鼠標滑動、觸屏等行為。圖5-3為序列。筆者自從事電商行業相關算法工作以來，多次發現靠直覺得來的關于用戶行為的觀點，與用戶的實際行為表現并不相符。例如，直覺上認為用戶應該先單擊商品A，然后單擊商品B，由于運營規則、前端規則或用戶偏見等原因，用戶的實際行為表現可能會恰恰相反。圖5- 用戶網上購物行為序列示我們直接使用人工標記的作弊訂單作為樣本標簽，基于邏輯歸訓練訂單，然后在驗證階段通過電話逐一訪，發現大部分用戶填寫的手舉例三，用戶行為。維度是標識用戶的唯一編號。根據用戶的唯一編號，可以關聯該用戶在某個時間段內的所有行為數據，然后按照時間的發展順序排列，從而完整復現該用戶在平臺上產生的一連串動作序列。例如，在電商購物場景中，使用用戶的賬戶編號追溯一次完等行為。圖形是最直觀的統計結果展示方式。常用的圖形有折線圖、散點圖、柱形圖和餅圖。其中折線圖主要用于看趨勢，散點圖主要用于看分布，柱形圖主要用于看高低，餅圖主要用于看占比。（FeatureEngineering）征數據的處理和加工，都屬于特征工程的范疇。一方面，大部分機器學習算法對非結構化特征數據束手無策，因此必須通過數據預處理將某些原始數據格式轉換成模型可接受的讀取格式；另一方面，機器學習算法雖然具備一定的數據抽象學習能力，但是特征可能有千萬種，如何從中選擇特征、融合特征，甚至創造特征，從而提高算法模型的學習效率和質量，就顯得尤為重要。特征工程主要解決的就是這兩方面的問題，其作用是給模型算法鋪路，將晦澀、粗糙的特征轉換成對模型友好的特征。是否丟棄包含缺失值的樣本集的計算結果對比如表5-1所示。其的計算結果，右邊為沒有缺失值的樣本集及相應的計算結果。表5-1根據表5-1的比例發生了很大變化（從75%變為50%），因此不要輕易丟棄包含缺失值的樣本。對于離散型特征缺失值，最簡單的處理方法為填入空字符串；對于連續性特征缺失值，最簡單的處理方法為補0。（出現頻率最高的特征值）最常用的方法為分箱（Binning）（又稱為分桶），分箱是處理連續型特征的一種方法。連續型特征的取值個數是無限的，而值與值之間輕微的變化對預測目標的影響較低，分箱可以基于這種輕微變化的規律，將線性特征轉換成非線性特征，從而提升特征的表達能力。分箱的方式有三種。第一種為等頻分箱，在特征的取值范圍內，按照特征值從小到大的順序排列樣本，同時將樣本按照數量均分成N份，每份作為一箱，同一個箱子中的特征值相同（通常用0和1表示）。例如，將樣本按照某特征從小到大的順序排列，然后按照每桶樣本數量相等的方式將其分成4箱，如圖5-4所示。第二種為等寬分箱，在特征的取值范圍內，將特征值按照從小到大的順序排列，并且將其均勻劃分成N份，落在同一份中的樣本屬于同一箱，同一箱特征向量的結果相同，示例如圖5-5所示。第三種為聚類分箱的方式不同，這種方式通過聚類算法將相似樣本特征值聚在一起作為分桶特征。與人為指定分桶方式的等頻分箱和等寬分箱相比，聚類分箱更靈活、合理。圖5- 等頻分箱示圖5- 等寬分箱示特征編碼（FeatureEncoding）當拿到的原始特征數據是文本類型的數據時，一般需要通過特征編碼的方式將其轉換成模型可識別的數值型數據。常用的特征編碼方式有三種。第一種是手動建立映射字典，根據業務知識和目標任務，為離散型特征建立數字索引，用于進行映射。第二種是labelencoding，這種方法僅適用于有序特征，對于一個有m本數據集，在經過labelencoding處理后，每個類別都會映射到1的整數上。第三種是獨熱編碼，即One-hot編碼，這種方法很常見，一個類別特征的取值一共有m會變為長度為m的0-1向量，并且只有特征值對應的位置為1的是，前面講到的分箱其實也是獨熱編碼的一種實現方式。獨熱編碼的具體做法是將離散型特征所有可能的取值按照一定的順序排列，同時生成一個維度相同且值全為0離散型特征所處的位置設置為1。例如，編碼圖5-2中的動物類別離散型特征，編碼結果如表5-2所示。表5-2獨熱編碼示例特征縮放（FeatureScaling）特征縮放有三種常用方法，第一種叫作對數變換（LogTransformation）。對數變換將取值范圍很大的特征轉換到范圍較小的區間內，對特征分布的形狀有很大影響，可以降低特征值的震蕩影響，弱化特征噪聲，使特征分布更加勻稱。如圖5-6中，由于銷量值波動很大，因此取自然對數可以弱化劇烈波動帶來的影響。當然，由于是取對數，因此對零值或負值需要特殊處理，如統一設置為0。圖5- 對數變換的作映射到[0,1]區間。特征縮放的第三種方法叫作標準化（Standardization），算方法如下：首先計算得到當前特征的平均值和標準差，然后將原始特征值先減去平均值，再除以方差，最后將特征值統一映射到標準正態分布中。特征縮放主要有兩個作用，第一個是使梯度下降的過程不容易發生震蕩，能更快收斂，如圖5-7模型算法中，起到統一量綱的作用。圖5- 不同量綱下梯度下降的對特征嵌入（FeatureEmbedding）始特征轉換成指定維度特征向量的一種方法。嚴格意義而言，特征嵌入也是特征變換的一種，但與基于特征數據層面的簡單轉換相比，特征嵌入需要通過一個神經網絡模型的訓練過程來實現。此外，特征嵌入更加變化多端，基于不同的神經網絡模型可以得到不同的特征嵌入向量。對于在距離度量下原本相近的樣本，特征嵌入能使它們在新的特征空間中保持原本相近的距離。例如，自然語言處理中的詞嵌入（WordEmbedding）就是將單字或單詞映射成較高維度的特征向量，特征交叉（FeatureOverlap）使用獨熱編碼