Ⅰ 一文帶你認識30個重要的數據結構和演算法
數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。
它們是做什麼用的？
想像一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數組（矩陣）。
特性
鏈表是線性數據結構，就像數組一樣。鏈表和數組的主要區別在於鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接。
它們是做什麼用的？
鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索顯示的頁面的完美數據結構。
特性
堆棧是一種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（後進先出）規則。因此，添加到堆棧中的最後一個元素是您從中刪除的第一個元素。
堆棧可以使用數組或鏈表來實現。
它們是做什麼用的？
現實生活中最常見的例子是在食堂中將盤子疊放在一起。位於頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。
堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然後彈出它們。
另一個有趣的應用是有效括弧問題。給定一串括弧，您可以使用堆棧檢查它們是否匹配。
特性
隊列是受限訪問集合中的另一種數據類型，就像前面討論的堆棧一樣。主要區別在於隊列是按照FIFO（先進先出）模型組織的：隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。
它們是做什麼用的？
這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用於保存等待從顧問那裡獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。
一種特殊且非常重要的隊列類型是優先順序隊列。元素根據與它們關聯的「優先順序」被引入隊列：具有最高優先順序的元素首先被引入隊列。這個 ADT 在許多圖演算法（Dijkstra 演算法、BFS、Prim 演算法、霍夫曼編碼 ）中是必不可少的。它是使用堆實現的。
另一種特殊類型的隊列是deque 隊列（雙關語它的發音是「deck」）。可以從隊列的兩端插入/刪除元素。
特性
Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。
哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼，放入一個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。
最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。
理想情況下，散列函數會將每個鍵分配給一個唯一的桶，但他們的大多數設計都採用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。
它們是做什麼用的？
Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。
通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。
另一個有用的應用是值的標准化。假設我們要為一天中的每一分鍾（24 小時 = 1440 分鍾）分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鍾。
特性
術語：
因為maps 是使用自平衡紅黑樹實現的（文章後面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。
圖是表示一對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。
圖有兩種主要類型：有向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。
它們是做什麼用的？
特性
圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：
一棵樹是一個無向圖，在連通性方面最小（如果我們消除一條邊，圖將不再連接）和在無環方面最大（如果我們添加一條邊，圖將不再是無環的）。所以任何無環連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹。
根是一個固定節點，它確定樹中邊的方向，所以這就是一切「開始」的地方。葉子是樹的終端節點——這就是一切「結束」的地方。
一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。
它們是做什麼用的？
我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。
樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。
特性
二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2ⁿ-1 個可能的節點。
二叉搜索樹是一棵二叉樹，其中節點的值屬於一個完全有序的集合——任何任意選擇的節點的值都大於左子樹中的所有值，而小於右子樹中的所有值。
它們是做什麼用的？
BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變數/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成一個二叉樹，其中內部節點是運算符，葉子是變數/常量——它被稱為抽象語法樹（AST）。
BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。
特性
BST 有三種類型的 DFS 遍歷：
所有這些類型的樹都是自平衡二叉搜索樹。不同之處在於它們以對數時間平衡高度的方式。
AVL 樹在每次插入/刪除後都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 Landis。
在紅黑樹中，每個節點存儲一個額外的代表顏色的位，用於確保每次插入/刪除操作後的平衡。
在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。
它們是做什麼用的？
AVL 似乎是資料庫理論中最好的數據結構。
RBT（紅黑樹） 用於組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。
在 Windows NT 中（在虛擬內存、網路和文件系統代碼中），Splay 樹用於緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用於長文本字元串的字元串）。
特性
最小堆是一棵二叉樹，其中每個節點的值都大於或等於其父節點的值：val[par[x]]
Ⅱ 機器學習新手必看十大演算法
機器學習新手必看十大演算法
本文介紹了機器學習新手需要了解的 10 大演算法，包括線性回歸、Logistic 回歸、樸素貝葉斯、K 近鄰演算法等。
在機器學習中，有一種叫做「沒有免費的午餐」的定理。簡而言之，它指出沒有任何一種演算法對所有問題都有效，在監督學習(即預測建模)中尤其如此。
例如，你不能說神經網路總是比決策樹好，反之亦然。有很多因素在起作用，例如數據集的大小和結構。
因此，你應該針對具體問題嘗試多種不同演算法，並留出一個數據「測試集」來評估性能、選出優勝者。
當然，你嘗試的演算法必須適合你的問題，也就是選擇正確的機器學習任務。打個比方，如果你需要打掃房子，你可能會用吸塵器、掃帚或拖把，但是你不會拿出鏟子開始挖土。
大原則
不過也有一個普遍原則，即所有監督機器學習演算法預測建模的基礎。
機器學習演算法被描述為學習一個目標函數 f，該函數將輸入變數 X 最好地映射到輸出變數 Y：Y = f(X)
這是一個普遍的學習任務，我們可以根據輸入變數 X 的新樣本對 Y 進行預測。我們不知道函數 f 的樣子或形式。如果我們知道的話，我們將會直接使用它，不需要用機器學習演算法從數據中學習。
最常見的機器學習演算法是學習映射 Y = f(X) 來預測新 X 的 Y。這叫做預測建模或預測分析，我們的目標是盡可能作出最准確的預測。
對於想了解機器學習基礎知識的新手，本文將概述數據科學家使用的 top 10 機器學習演算法。
1. 線性回歸
線性回歸可能是統計學和機器學習中最知名和最易理解的演算法之一。
預測建模主要關注最小化模型誤差或者盡可能作出最准確的預測，以可解釋性為代價。我們將借用、重用包括統計學在內的很多不同領域的演算法，並將其用於這些目的。
線性回歸的表示是一個方程，它通過找到輸入變數的特定權重(稱為系數 B)，來描述一條最適合表示輸入變數 x 與輸出變數 y 關系的直線。
線性回歸
例如：y = B0 + B1 * x
我們將根據輸入 x 預測 y，線性回歸學習演算法的目標是找到系數 B0 和 B1 的值。
可以使用不同的技術從數據中學習線性回歸模型，例如用於普通最小二乘法和梯度下降優化的線性代數解。
線性回歸已經存在了 200 多年，並得到了廣泛研究。使用這種技術的一些經驗是盡可能去除非常相似(相關)的變數，並去除噪音。這是一種快速、簡單的技術，可以首先嘗試一下。
2. Logistic 回歸
Logistic 回歸是機器學習從統計學中借鑒的另一種技術。它是解決二分類問題的首選方法。
Logistic 回歸與線性回歸相似，目標都是找到每個輸入變數的權重，即系數值。與線性回歸不同的是，Logistic 回歸對輸出的預測使用被稱為 logistic 函數的非線性函數進行變換。
logistic 函數看起來像一個大的 S，並且可以將任何值轉換到 0 到 1 的區間內。這非常實用，因為我們可以規定 logistic 函數的輸出值是 0 和 1(例如，輸入小於 0.5 則輸出為 1)並預測類別值。
Logistic 回歸
由於模型的學習方式，Logistic 回歸的預測也可以作為給定數據實例(屬於類別 0 或 1)的概率。這對於需要為預測提供更多依據的問題很有用。
像線性回歸一樣，Logistic 回歸在刪除與輸出變數無關的屬性以及非常相似(相關)的屬性時效果更好。它是一個快速的學習模型，並且對於二分類問題非常有效。
3. 線性判別分析(LDA)
Logistic 回歸是一種分類演算法，傳統上，它僅限於只有兩類的分類問題。如果你有兩個以上的類別，那麼線性判別分析是首選的線性分類技術。
LDA 的表示非常簡單直接。它由數據的統計屬性構成，對每個類別進行計算。單個輸入變數的 LDA 包括：
每個類別的平均值;
所有類別的方差。
線性判別分析
進行預測的方法是計算每個類別的判別值並對具備最大值的類別進行預測。該技術假設數據呈高斯分布(鍾形曲線)，因此最好預先從數據中刪除異常值。這是處理分類預測建模問題的一種簡單而強大的方法。
4. 分類與回歸樹
決策樹是預測建模機器學習的一種重要演算法。
決策樹模型的表示是一個二叉樹。這是演算法和數據結構中的二叉樹，沒什麼特別的。每個節點代表一個單獨的輸入變數 x 和該變數上的一個分割點(假設變數是數字)。
決策樹
決策樹的葉節點包含一個用於預測的輸出變數 y。通過遍歷該樹的分割點，直到到達一個葉節點並輸出該節點的類別值就可以作出預測。
決策樹學習速度和預測速度都很快。它們還可以解決大量問題，並且不需要對數據做特別准備。
5. 樸素貝葉斯
樸素貝葉斯是一個簡單但是很強大的預測建模演算法。
該模型由兩種概率組成，這兩種概率都可以直接從訓練數據中計算出來：1)每個類別的概率;2)給定每個 x 的值，每個類別的條件概率。一旦計算出來，概率模型可用於使用貝葉斯定理對新數據進行預測。當你的數據是實值時，通常假設一個高斯分布(鍾形曲線)，這樣你可以簡單的估計這些概率。
貝葉斯定理
樸素貝葉斯之所以是樸素的，是因為它假設每個輸入變數是獨立的。這是一個強大的假設，真實的數據並非如此，但是，該技術在大量復雜問題上非常有用。
6. K 近鄰演算法
KNN 演算法非常簡單且有效。KNN 的模型表示是整個訓練數據集。是不是很簡單?
KNN 演算法在整個訓練集中搜索 K 個最相似實例(近鄰)並匯總這 K 個實例的輸出變數，以預測新數據點。對於回歸問題，這可能是平均輸出變數，對於分類問題，這可能是眾數(或最常見的)類別值。
訣竅在於如何確定數據實例間的相似性。如果屬性的度量單位相同(例如都是用英寸表示)，那麼最簡單的技術是使用歐幾里得距離，你可以根據每個輸入變數之間的差值直接計算出來其數值。
K 近鄰演算法
KNN 需要大量內存或空間來存儲所有數據，但是只有在需要預測時才執行計算(或學習)。你還可以隨時更新和管理訓練實例，以保持預測的准確性。
距離或緊密性的概念可能在非常高的維度(很多輸入變數)中會瓦解，這對演算法在你的問題上的性能產生負面影響。這被稱為維數災難。因此你最好只使用那些與預測輸出變數最相關的輸入變數。
7. 學習向量量化
K 近鄰演算法的一個缺點是你需要遍歷整個訓練數據集。學習向量量化演算法(簡稱 LVQ)是一種人工神經網路演算法，它允許你選擇訓練實例的數量，並精確地學習這些實例應該是什麼樣的。
學習向量量化
LVQ 的表示是碼本向量的集合。這些是在開始時隨機選擇的，並逐漸調整以在學習演算法的多次迭代中最好地總結訓練數據集。在學習之後，碼本向量可用於預測(類似 K 近鄰演算法)。最相似的近鄰(最佳匹配的碼本向量)通過計算每個碼本向量和新數據實例之間的距離找到。然後返回最佳匹配單元的類別值或(回歸中的實際值)作為預測。如果你重新調整數據，使其具有相同的范圍(比如 0 到 1 之間)，就可以獲得最佳結果。
如果你發現 KNN 在你的數據集上達到很好的結果，請嘗試用 LVQ 減少存儲整個訓練數據集的內存要求。
8. 支持向量機(SVM)
支持向量機可能是最受歡迎和最廣泛討論的機器學習演算法之一。
超平面是分割輸入變數空間的一條線。在 SVM 中，選擇一條可以最好地根據輸入變數類別(類別 0 或類別 1)對輸入變數空間進行分割的超平面。在二維中，你可以將其視為一條線，我們假設所有的輸入點都可以被這條線完全的分開。SVM 學習演算法找到了可以讓超平面對類別進行最佳分割的系數。
支持向量機
超平面和最近的數據點之間的距離被稱為間隔。分開兩個類別的最好的或最理想的超平面具備最大間隔。只有這些點與定義超平面和構建分類器有關。這些點被稱為支持向量，它們支持或定義了超平面。實際上，優化演算法用於尋找最大化間隔的系數的值。
SVM 可能是最強大的立即可用的分類器之一，值得一試。
9. Bagging 和隨機森林
隨機森林是最流行和最強大的機器學習演算法之一。它是 Bootstrap Aggregation(又稱 bagging)集成機器學習演算法的一種。
bootstrap 是從數據樣本中估算數量的一種強大的統計方法。例如平均數。你從數據中抽取大量樣本，計算平均值，然後平均所有的平均值以便更好的估計真實的平均值。
bagging 使用相同的方法，但是它估計整個統計模型，最常見的是決策樹。在訓練數據中抽取多個樣本，然後對每個數據樣本建模。當你需要對新數據進行預測時，每個模型都進行預測，並將所有的預測值平均以便更好的估計真實的輸出值。
隨機森林
隨機森林是對這種方法的一種調整，在隨機森林的方法中決策樹被創建以便於通過引入隨機性來進行次優分割，而不是選擇最佳分割點。
因此，針對每個數據樣本創建的模型將會與其他方式得到的有所不同，不過雖然方法獨特且不同，它們仍然是准確的。結合它們的預測可以更好的估計真實的輸出值。
如果你用方差較高的演算法(如決策樹)得到了很好的結果，那麼通常可以通過 bagging 該演算法來獲得更好的結果。
10. Boosting 和 AdaBoost
Boosting 是一種集成技術，它試圖集成一些弱分類器來創建一個強分類器。這通過從訓練數據中構建一個模型，然後創建第二個模型來嘗試糾正第一個模型的錯誤來完成。一直添加模型直到能夠完美預測訓練集，或添加的模型數量已經達到最大數量。
AdaBoost 是第一個為二分類開發的真正成功的 boosting 演算法。這是理解 boosting 的最佳起點。現代 boosting 方法建立在 AdaBoost 之上，最顯著的是隨機梯度提升。
AdaBoost
AdaBoost與短決策樹一起使用。在第一個決策樹創建之後，利用每個訓練實例上樹的性能來衡量下一個決策樹應該對每個訓練實例付出多少注意力。難以預測的訓練數據被分配更多權重，而容易預測的數據分配的權重較少。依次創建模型，每個模型在訓練實例上更新權重，影響序列中下一個決策樹的學習。在所有決策樹建立之後，對新數據進行預測，並且通過每個決策樹在訓練數據上的精確度評估其性能。
因為在糾正演算法錯誤上投入了太多注意力，所以具備已刪除異常值的干凈數據非常重要。
總結
初學者在面對各種機器學習演算法時經常問：「我應該用哪個演算法?」這個問題的答案取決於很多因素，包括：(1)數據的大小、質量和特性;(2)可用的計算時間;(3)任務的緊迫性;(4)你想用這些數據做什麼。
即使是經驗豐富的數據科學家在嘗試不同的演算法之前，也無法分辨哪種演算法會表現最好。雖然還有很多其他的機器學習演算法，但本篇文章中討論的是最受歡迎的演算法。如果你是機器學習的新手，這將是一個很好的學習起點。