與機器學習算法有關的資料結構

擁有機器學習技能是不夠的。你還需要良好的資料結構的工作知識。學習更多，并解決一些問題。

是以，你已經決定不再使用固定的算法并開始編寫自己的機器學習方法。也許你已經有了一種新的叢集資料的新方法，或者你可能對你最喜歡的統計分類包的局限性感到失望。

無論哪種情況，你對資料結構和算法的了解越多，在代碼編寫時就越容易。

我不認為機器學習中使用的資料結構與其他軟體開發領域的資料結構有很大的不同。然而，由于許多問題的規模和難度，對基礎知識的掌握非常重要。

另外，由于機器學習是一個數學性非常強的領域，我們應該記住，資料結構是如何被用來解決數學問題的，以及它們是如何以自己的方式來處理數學問題的。

有兩種方法可以對資料結構進行分類:通過它們的實作和它們的操作。

通過實作，我指的是它們的程式設計方式和實際存儲模式的具體細節。它們的外觀并沒有如何實作更重要。對于按操作或抽象資料類型分類的資料結構來說，情況恰恰相反——它們的外觀和操作比實作方式更重要，事實上，它們通常可以使用許多不同的内部表示來實作。

當我說基本數組是機器學習中最重要的資料結構時，我并不是在開玩笑。這個實用的類型比你想象的要多。數組非常重要，因為它們被用于線性代數——這是你可以使用的最有用和最強大的數學工具。

是以，最常見的類型分别是一個和二維的類型，分别對應于向量和矩陣，但偶爾會遇到三個或四維的數組，它們要麼用于更進階别的張量，要麼為前者的組示例。

在進行矩陣運算時，你将不得不從令人眼花缭亂的各種庫、資料類型、甚至語言中進行選擇。許多科學程式設計語言，如Matlab，互動式資料語言(IDL)，以及帶有Numpy擴充的Python，主要是為處理向量和矩陣而設計的。

但這些資料結構的優點是，即使在更通用的程式設計語言中，實作向量和矩陣在metal很簡單，假設語言中有任何Fortran DNA。考慮矩陣向量乘法的平移：

使用C++：

在大多數情況下，數組可以在運作時配置設定到固定大小，或者可以計算可靠的上限。在那些需要數組無限擴充的情況下，可以使用可擴充數組，例如C ++标準模闆庫（STL）中的vector類。Matlab中的規則數組具有相似的可擴充性，可擴充數組是整個Python語言的基礎。

在這個資料結構中，有兩個中繼資料與實際資料值一起存儲。 這些是配置設定給資料結構的存儲空間量和陣列的實際大小。一旦數組大小超過存儲空間，将配置設定一個新空間，該空間的大小是其大小的兩倍，将值複制到其中，并删除舊數組。

這有一個O（n）操作，其中n是數組的大小，但由于它隻是偶爾發生，是以添加一個新值到實際結束的時間實際上被配置設定到常量時間O（1）。這是一個非常靈活的資料結構，具有快速的平均插入和快速通路。

可擴充數組非常适合組成其他更複雜的資料結構并使其可擴充。例如，要存儲稀疏矩陣，可以在結尾添加任意數量的新元素，然後按位置對其進行排序以更快地定位。稍後詳述！

連結清單由幾個分開配置設定的節點組成。每個節點都包含一個資料值和一個指向清單中下一個節點的指針。插入在不變的時間是非常有效的，但是通路一個值很慢，并且通常需要掃描大部分清單。

連結清單很容易拼接并分開。有許多變化——例如，可以在頭部或尾部進行插入;該清單可以是雙連結的，并且有許多類似的資料結構基于相同的原則。

主要是，我發現連結清單可用于解析不确定長度的清單。 之後，它們可以轉換為固定長度的陣列以便快速通路。出于這個原因，我使用了一個連結清單類，其中包含一個轉換為數組的方法。

二叉樹與連結清單相似，隻不過每個節點都有兩個指向後續節點的指針而不是一個。左側孩子的值總是小于父節點的值，而父節點的值又小于右側孩子的值。是以，二叉樹中的資料會自動排序。O（log n）的平均插入和通路都是有效的。像連結清單一樣，它們很容易轉換為數組，這是樹狀排序的基礎。

如果資料已經排序，二叉樹在O（n）最差的情況下效率較低，因為資料将被線性排列，就好像它是一個連結清單。雖然二叉樹中的排序受到限制，但它絕不是唯一的，并且可以根據插入的順序以相同的清單排列許多不同的配置。

為了使其更加平衡，可以将一些轉換應用于樹。自平衡樹會自動執行這些操作，以保持通路和插入的最佳平均值。

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

堆是另一個層次結構，類似于樹的有序資料結構，它具有垂直排序，而不是水準排序。這種排序适用于層次結構，但不适用于整個層次:父節點總是大于它的子節點，但是更進階别的節點并不一定比下面的節點要大。

插入和檢索都是通過更新來執行的。元素首先插入到最高可用位置。然後将其與其父母進行比較并提升，直至達到正确的等級。為了從堆中去掉一個元素，兩個孩子中較大的一個被提升到缺失的位置，然後這兩個孩子中較大的一個被提升，如此等等，直到每一個都變成正确的等級。

通常情況下，頂部的最高排名值将從堆中取出，以便對清單進行排序。 與樹不同，大多數堆隻是簡單地存儲在數組中，元素之間的關系隻是隐含的。

一個堆棧被定義為“先進後出”。一個元素被壓入堆棧的頂部，覆寫前一個元素。頂部的元素必須先彈出才能通路任何其他元素。

堆棧主要用于解析文法和實作計算機語言。

隊列被定義為“先入先出”。想想銀行櫃員面前的隊伍(對于我們這些年紀還大的人來說，還記得在網上銀行出現之前的一段時間)。隊列在實時程式設計中非常有用，是以程式可以維護要處理的作業清單。

考慮一個記錄運動員分段時間的應用程式。你輸入bib号碼，然後按Enter鍵，但你要做的時候，後面的運動員也通過了。是以你輸入的是最近接近運動員的bib号碼清單，然後按下一個單獨的鍵來注冊隊列中的下一個。

一個集合包含一個非重複元素的無序清單。如果添加已經在集合中的元素，則不會有任何更改。由于機器學習的許多數學知識都與集合有關，是以它們是非常有用的資料結構。

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

在實踐中，它的用處不大，部分原因是大多數關聯數組隻是一維的，而機器學習資料通常是多元的。

關聯數組适用于建構字典。

假設你正在建構一個DSL，想要存儲一個函數和變量清單，并且需要區分這兩者。

sin =函數。

var = 變量。

exp =函數。

x =變量。

sqrt =函數。

a =變量。

在“sqrt”查詢數組将傳回“函數”。

當你處理更多問題時，你肯定會遇到标準配方框不包含最佳結構的那些問題。你将需要設計自己的資料結構。

考慮一個多類分類器，它概括了一個二進制分類器來處理具有兩個以上類的分類問題。一個明顯的解決方案是平分：遞歸地将類分成兩組。但分層解決方案并不是解決多類的唯一方法，你可以使用類似于二叉樹的方法來組織二進制分類器。

考慮幾個分區，然後用它們同時解決所有類的機率。

最通用的解決方案将兩者結合起來，是以每個分層分區不需要是二進制的，而是可以通過非分層多類分類器來解決。這是在libAGF庫中采用的方法。

更複雜的資料結構也可以由基本結構組成。考慮一個稀疏矩陣類。在稀疏矩陣中，大多數元素都是零，并且隻存儲非零元素。我們可以将每個元素的位置和值存儲為一個三元組，并将它們的清單存儲在一個可擴充數組中。

資料結構本身偶爾也很有趣。令它們真正有趣的是它們可以解決的各種問題。

對于大多數工作，我使用了許多基本的固定長度數組。我主要使用更複雜的資料結構來使程式在運作和與外部界面互動方面更加流暢，并且更加便于使用者使用。不像以前的Fortran程式那樣，為了改變網格大小，我不得不忍受一個接近半小時的編譯周期（我實際上在這樣的程式上工作過！）。

即使你無法想出一個應用程式，我仍然認為知道諸如棧和隊列之類的東西是件好事。你永遠不知道什麼時候會派上用場。

真正複雜的人工智能應用程式可能會使用定向和無向圖，它們隻是樹和連結清單的一般化。如果你無法應對後者，你将如何建立起像前者那樣的東西?

如果你想自己練習和實作ML算法的資料結構，請嘗試解決下面的一些問題：

将矩陣向量乘法代碼片段封裝到名為matrix_times_vector的子例程中。設計子例程的調用文法。

使用struct，typedef或class，将矢量和矩陣分别封裝到一對稱為vect和matrix的抽象類型中。為這些類型設計一個API。

在網上找到至少三個以上的庫。

下載下傳并安裝LIBSVM庫。考慮方法Kernel :: k_function在“svm.cpp”的第316行。用于儲存向量的資料結構有哪些優缺點？

在LIBSVM庫中，如何重構核心函數的計算?

文中描述的哪些資料結構是抽象類型？

你可以使用什麼内部表示/資料結構來實作抽象資料類型?上面的清單中是否有未包含的内容?

使用二叉樹，設計一個關聯數組。

實作一個treesort和一個堆排序。現在使用相同的資料結構來查找前k個元素。什麼常見的機器學習算法适合這種情況？

用你喜歡的語言實作你最喜歡的資料結構。

<a href="https://promotion.aliyun.com/ntms/act/ambassador/sharetouser.html?userCode=j4nkrg1c&amp;utm_source=j4nkrg1c" target="_blank"><b>數十款阿裡雲産品限時折扣中，趕緊點選領劵開始雲上實踐吧！</b></a>

作者資訊

Luba Belokon 市場營銷人員，Peter Mills 研究科學家

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

作者：Luba Belokon，Peter Mills 譯者：董昭男 稽核：