與機器學習演算法相關的數據結構，了解一下

我不認為機器學習中使用的數據結構與在軟體開發的其他領域中使用的數據結構有很大的不同。然而，由於許多問題的規模和難度，掌握基本知識是必不可少的。

此外，由於機器學習是數學領域，我們應該記住數據結構如何用來解決數學問題，以及它們本身就是數學對象的方式。

有兩種方法可以對數據結構進行分類：通過實現和操作。

數組

當我說基本數組是機器學習中最重要的數據結構時，我不是在開玩笑。這種麵包加黃油的類型比你想像的還要多。數組非常重要，因為它們用於線性代數，這是你可以使用的最有用和最強大的數學工具。

因此，最常見的類型將是一維和二維類型，分別對應於向量和矩陣，但是你偶爾會遇到三維或四維數組，它們要麼用於較高的等級，要麼用於對前者的示例進行分組。

在執行矩陣運算時，你必須從令人眼花繚亂的各種庫、數據類型甚至語言中進行選擇。許多科學編程語言，如Matlab、InteractiveDataLanguage(IDL)和帶有Numpy擴展的Python，主要用於處理向量和矩陣。

但是這些數據結構的好處是，即使在更通用的編程語言中，實現向量和矩陣也是很簡單的，假設語言中有任何Fortran DNA。考慮矩陣向量乘法的平移：

C++：

for (int i=0; i

y[i]=0;

for (int j=0; j

}

在大多數情況下，可以在運行時將數組分配給固定大小，或者可以計算可靠的上限。在需要無限擴展數組的情況下，可以使用可擴展數組，如C++標準模板庫(STL)中的向量類。Matlab中的常規數組具有類似的可擴展性，可擴展數組是整個Python語言的基礎。

在該數據結構中，存在與實際數據值一起存儲的兩個元數據。這些是分配給數據結構的存儲空間量以及陣列的實際大小。一旦數組的大小超過存儲空間，就會分配一個大小為兩倍的新空間，將值複製到其中，並刪除舊數組。

這是一個O(n)操作，其中n是數組的大小，但由於它只是偶爾發生，所以將一個新值添加到末尾的時間實際上會被分解為常數時間O(1)。它是一個非常靈活的數據結構，具有快速平均插入和快速訪問。

可擴展數組非常適合組合其他更複雜的數據結構並使其可擴展。例如，為了存儲稀疏矩陣，可以在末尾添加任意數量的新元素，然後按位置對它們進行排序以使位置更快。

稀疏矩陣可用於文本分類問題。

鏈表

鏈表由幾個單獨分配的節點組成。每個節點都包含一個數據值以及指向列表中下一個節點的指針。插入在固定時間非常有效，但訪問值很慢並且通常需要掃描大部分列表。

鏈接列表很容易拼接在一起以及分開。有許多變化，例如，插入可以在頭部或尾部進行;列表可以是雙向鏈接的，並且有許多基於相同原理的類似數據結構，例如下面的二叉樹：

主要是，我發現鏈接列表可用於解析不確定長度的列表。之後，它們可以轉換為固定長度的數組以便快速訪問。因此，我使用鏈接列表類，其中包含轉換為數組的方法。

二叉樹

二叉樹類似於鏈表，只不過每個節點有兩個指向後續節點的指針，而不是只有一個節點。左子節點中的值始終小於父節點中的值，而父節點中的值又小於右子節點中的值。因此，二叉樹中的數據被自動排序。插入和訪問在O（log n）平均有效。與鏈表一樣，它們很容易轉換為數組，這是樹排序的基礎。

平衡樹

如果數據已經被排序，則在O（n）最壞的情況下二進位樹效率較低，因為數據將被線性布局，就好像它是鏈表一樣。雖然二叉樹中的排序受到約束，但它絕不是唯一的，並且根據插入的順序，可以在許多不同的配置中排列相同的列表。

有幾種轉換可以應用於樹，以使其更加平衡。自平衡樹自動執行這些操作，以便以最佳平均值訪問和插入。

機器學習中一個普遍存在的問題是找出最接近某一特定點的鄰域。神經網路演算法需要解決這個問題。KD樹是一種二叉樹，它提供了一種有效的解決方案。

堆是另一種類似於樹的分層有序數據結構，除了水平排序之外，它還具有垂直排序。這種排序沿層次結構進行，但不是跨層次的：父節點總是大於其兩個子節點，但是級別較高的節點不一定大於不直接位於其下面的較低的節點。

插入和檢索都是通過升級完成的。元素首先插入到最高的可用位置。然後把它和它的父母進行比較，並提升到正確的等級。要從堆中取下一個元素，兩個子元素中越大的子元素被提升到缺失的位置，那麼這兩個子元素中的更大的子元素就會被提升。

通常，頂部的最高排序值是從堆中提取的，以便對列表進行排序。與樹不同，大多數堆只是存儲在數組中，元素之間的關係僅是隱式的。

堆疊

堆棧被定義為「先進後出」，一個元素被推到堆棧頂部，覆蓋前一個元素。必須先彈出頂部元素，然後才能訪問其他元素。

棧主要用於解析語法和實現計算機語言。

有許多機器學習應用程序，其中領域特定語言(DSL)是完美的解決方案。例如，libAGF庫使用遞歸控制語言將二進位分類推廣到多類。特殊字元用於重複前面的選項，但由於該語言是遞歸的，因此該選項必須取自相同的層級或更高級別。這是通過堆棧實現的。

隊列

隊列被定義為「先入先出」。隊列在實時編程中非常有用，因此程序可以維護要處理的作業列表。集合由非重複元素的無序列表組成。如果您添加了一個已經在集合中的元素，則不會有任何更改。由於機器學習的許多數學處理集，它們是非常有用的數據結構。

關聯陣列

在關聯數組中，有兩種類型的數據成對存儲：密鑰及其關聯值。數據結構本質上是關係的：值由其鍵來解決。由於大部分訓練數據也是關係型的，因此這種類型的數據結構似乎非常適合機器學習問題。

在實踐中，它的使用並不多，部分原因是大多數關聯數組都是一維的，而機器學習數據通常是多維的。

關聯數組適用於構建字典。

假設你正在構建一個DSL，希望存儲函數和變數的列表，並且需要區分這兩者。

sin= function

var= variable

exp= function

x= variable

sqrt= function

a= variable

查詢「sqrt」上的數組將返回「函數」。

自定義數據結構

當你處理更多問題時，你肯定會遇到標準配方框不包含最佳結構的問題。你需要設計自己的數據結構。

考慮一個多類分類器，它推廣二元分類器以處理具有兩個以上類的分類問題。一個明顯的解決方案是二分法：遞歸地將類分成兩組。你可以使用類似於二叉樹的東西來組織二進位分類器，除了分層解決方案不是解決多類的唯一方法。

考慮幾個分區，然後使用這些分區同時求解所有類的概率。

更複雜的數據結構也可以由基本結構組成。考慮一個稀疏矩陣類。在稀疏矩陣中，大多數元素為零，並且僅存儲非零元素。我們可以將每個元素的位置和值存儲為三元組，並在可擴展數組中包含它們的列表。

3乘3的等式：

結論

在我所做的大部分工作中，我使用了很多基本的固定長度數組。我使用複雜的數據結構，使程序在運行方式和與外部世界的介面方面更加流暢，也更方便用戶使用。不像以前的Fortran程序，為了改變網格大小，必須忍受將近半個小時的編譯周期。

即使你不能想出一個應用程序，我仍然認為知道堆棧和隊列之類的東西是很好的。你永遠不知道什麼時候能派上用場。

真正複雜的人工智慧應用程序可能會使用定向和無向圖等事物，這些圖實際上只是樹和鏈表的概括。如果你無法應對後者，你將如何建造像前者一樣的東西？

問題

如果你想自己練習並實現ML演算法的數據結構，請嘗試解決以下一些問題：

1. 將矩陣向量乘法代碼片段封裝到一個名為MatrixTimeVectoral的子常式中，為子常式設計調用語法。

2. 使用struct、typedef或class，將向量和矩陣分別封裝成兩個抽象類型，稱為Vect和矩陣。為類型設計API。

3. 在網上找到至少三個執行上述操作的庫。

4. 下載並安裝LIBSVM庫。考慮一下「svm.cpp」第316行中的Kernel：K_Function方法。用於保存向量的數據結構的優點和缺點是什麼？

5. 如何在LIBSVM庫中重構核函數的計算？

6. 文本中描述的哪些數據結構是抽象類型？

7. 你可以使用什麼內部表示/數據結構來實現抽象數據類型？是否有未列入上述清單的？

原文標題《Data Structures Related to Machine Learning Algorithms》

作者：Luba Belokon

譯者：lemon

本文為譯文，不代表雲加社區觀點

—— 完 ——

關注云加社區，回復3加讀者群

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！