機(jī)器學(xué)習(xí)算法的數(shù)據(jù)結(jié)構(gòu)是怎樣的

擁有機(jī)器學(xué)習(xí)技能是不夠的。你還需要良好的數(shù)據(jù)結(jié)構(gòu)的工作知識(shí)。學(xué)習(xí)更多，并解決一些問題。

因此，你已經(jīng)決定不再使用固定的算法并開始編寫自己的機(jī)器學(xué)習(xí)方法。也許你已經(jīng)有了一種新的集群數(shù)據(jù)的新方法，或者你可能對(duì)你最喜歡的統(tǒng)計(jì)分類包的局限性感到失望。

無論哪種情況，你對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的了解越多，在代碼編寫時(shí)就越容易。我不認(rèn)為機(jī)器學(xué)習(xí)中使用的數(shù)據(jù)結(jié)構(gòu)與其他軟件開發(fā)領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)有很大的不同。然而，由于許多問題的規(guī)模和難度，對(duì)基礎(chǔ)知識(shí)的掌握非常重要。

另外，由于機(jī)器學(xué)習(xí)是一個(gè)數(shù)學(xué)性非常強(qiáng)的領(lǐng)域，我們應(yīng)該記住，數(shù)據(jù)結(jié)構(gòu)是如何被用來解決數(shù)學(xué)問題的，以及它們是如何以自己的方式來處理數(shù)學(xué)問題的。有兩種方法可以對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類：通過它們的實(shí)現(xiàn)和它們的操作。

通過實(shí)現(xiàn)，我指的是它們的編程方式和實(shí)際存儲(chǔ)模式的具體細(xì)節(jié)。它們的外觀并沒有如何實(shí)現(xiàn)更重要。對(duì)于按操作或抽象數(shù)據(jù)類型分類的數(shù)據(jù)結(jié)構(gòu)來說，情況恰恰相反——它們的外觀和操作比實(shí)現(xiàn)方式更重要，事實(shí)上，它們通常可以使用許多不同的內(nèi)部表示來實(shí)現(xiàn)。

數(shù)組

當(dāng)我說基本數(shù)組是機(jī)器學(xué)習(xí)中最重要的數(shù)據(jù)結(jié)構(gòu)時(shí)，我并不是在開玩笑。這個(gè)實(shí)用的類型比你想象的要多。數(shù)組非常重要，因?yàn)樗鼈儽挥糜诰€性代數(shù)——這是你可以使用的最有用和最強(qiáng)大的數(shù)學(xué)工具。

因此，最常見的類型分別是一個(gè)和二維的類型，分別對(duì)應(yīng)于向量和矩陣，但偶爾會(huì)遇到三個(gè)或四維的數(shù)組，它們要么用于更高級(jí)別的張量，要么為前者的組示例。

在進(jìn)行矩陣運(yùn)算時(shí)，你將不得不從令人眼花繚亂的各種庫、數(shù)據(jù)類型、甚至語言中進(jìn)行選擇。許多科學(xué)編程語言，如Matlab，交互式數(shù)據(jù)語言（IDL），以及帶有Numpy擴(kuò)展的Python，主要是為處理向量和矩陣而設(shè)計(jì)的。

但這些數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)是，即使在更通用的編程語言中，實(shí)現(xiàn)向量和矩陣在metal很簡(jiǎn)單，假設(shè)語言中有任何Fortran DNA?？紤]矩陣向量乘法的平移：

使用C++：

for （int i=0; i0;

for （int j=0; j

在大多數(shù)情況下，數(shù)組可以在運(yùn)行時(shí)分配到固定大小，或者可以計(jì)算可靠的上限。在那些需要數(shù)組無限擴(kuò)展的情況下，可以使用可擴(kuò)展數(shù)組，例如C ++標(biāo)準(zhǔn)模板庫（STL）中的vector類。Matlab中的規(guī)則數(shù)組具有相似的可擴(kuò)展性，可擴(kuò)展數(shù)組是整個(gè)Python語言的基礎(chǔ)。

在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，有兩個(gè)元數(shù)據(jù)與實(shí)際數(shù)據(jù)值一起存儲(chǔ)。 這些是分配給數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間量和陣列的實(shí)際大小。一旦數(shù)組大小超過存儲(chǔ)空間，將分配一個(gè)新空間，該空間的大小是其大小的兩倍，將值復(fù)制到其中，并刪除舊數(shù)組。

這有一個(gè)O（n）操作，其中n是數(shù)組的大小，但由于它只是偶爾發(fā)生，所以添加一個(gè)新值到實(shí)際結(jié)束的時(shí)間實(shí)際上被分配到常量時(shí)間O（1）。這是一個(gè)非常靈活的數(shù)據(jù)結(jié)構(gòu)，具有快速的平均插入和快速訪問。

可擴(kuò)展數(shù)組非常適合組成其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)并使其可擴(kuò)展。例如，要存儲(chǔ)稀疏矩陣，可以在結(jié)尾添加任意數(shù)量的新元素，然后按位置對(duì)其進(jìn)行排序以更快地定位。稍后詳述！稀疏矩陣可用于文本分類問題。

鏈表

鏈表由幾個(gè)分開分配的節(jié)點(diǎn)組成。每個(gè)節(jié)點(diǎn)都包含一個(gè)數(shù)據(jù)值和一個(gè)指向列表中下一個(gè)節(jié)點(diǎn)的指針。插入在不變的時(shí)間是非常有效的，但是訪問一個(gè)值很慢，并且通常需要掃描大部分列表。

鏈表很容易拼接并分開。有許多變化——例如，可以在頭部或尾部進(jìn)行插入;該列表可以是雙鏈接的，并且有許多類似的數(shù)據(jù)結(jié)構(gòu)基于相同的原則。

主要是，我發(fā)現(xiàn)鏈表可用于解析不確定長(zhǎng)度的列表。 之后，它們可以轉(zhuǎn)換為固定長(zhǎng)度的陣列以便快速訪問。出于這個(gè)原因，我使用了一個(gè)鏈接列表類，其中包含一個(gè)轉(zhuǎn)換為數(shù)組的方法。

二叉樹

二叉樹與鏈表相似，只不過每個(gè)節(jié)點(diǎn)都有兩個(gè)指向后續(xù)節(jié)點(diǎn)的指針而不是一個(gè)。左側(cè)孩子的值總是小于父節(jié)點(diǎn)的值，而父節(jié)點(diǎn)的值又小于右側(cè)孩子的值。因此，二叉樹中的數(shù)據(jù)會(huì)自動(dòng)排序。O（log n）的平均插入和訪問都是有效的。像鏈接列表一樣，它們很容易轉(zhuǎn)換為數(shù)組，這是樹狀排序的基礎(chǔ)。

平衡樹

如果數(shù)據(jù)已經(jīng)排序，二叉樹在O（n）最差的情況下效率較低，因?yàn)閿?shù)據(jù)將被線性排列，就好像它是一個(gè)鏈表。雖然二叉樹中的排序受到限制，但它絕不是唯一的，并且可以根據(jù)插入的順序以相同的列表排列許多不同的配置。

為了使其更加平衡，可以將一些轉(zhuǎn)換應(yīng)用于樹。自平衡樹會(huì)自動(dòng)執(zhí)行這些操作，以保持訪問和插入的最佳平均值。

機(jī)器學(xué)習(xí)中普遍存在的問題是找到最接近某一特定點(diǎn)的鄰居。這個(gè)問題是NN算法所需要的。KD樹是一種二叉樹，它提供了一種有效的解決方案。

堆

堆是另一個(gè)層次結(jié)構(gòu)，類似于樹的有序數(shù)據(jù)結(jié)構(gòu)，它具有垂直排序，而不是水平排序。這種排序適用于層次結(jié)構(gòu)，但不適用于整個(gè)層次：父節(jié)點(diǎn)總是大于它的子節(jié)點(diǎn)，但是更高級(jí)別的節(jié)點(diǎn)并不一定比下面的節(jié)點(diǎn)要大。

插入和檢索都是通過升級(jí)來執(zhí)行的。元素首先插入到最高可用位置。然后將其與其父母進(jìn)行比較并提升，直至達(dá)到正確的等級(jí)。為了從堆中去掉一個(gè)元素，兩個(gè)孩子中較大的一個(gè)被提升到缺失的位置，然后這兩個(gè)孩子中較大的一個(gè)被提升，如此等等，直到每一個(gè)都變成正確的等級(jí)。

通常情況下，頂部的最高排名值將從堆中取出，以便對(duì)列表進(jìn)行排序。 與樹不同，大多數(shù)堆只是簡(jiǎn)單地存儲(chǔ)在數(shù)組中，元素之間的關(guān)系只是隱含的。

堆棧

一個(gè)堆棧被定義為“先進(jìn)后出”。一個(gè)元素被壓入堆棧的頂部，覆蓋前一個(gè)元素。頂部的元素必須先彈出才能訪問任何其他元素。

堆棧主要用于解析語法和實(shí)現(xiàn)計(jì)算機(jī)語言。

在許多機(jī)器學(xué)習(xí)應(yīng)用程序中，領(lǐng)域特定語言（DSL）是完美的解決方案。例如，libAGF庫使用遞歸控制語言將二進(jìn)制分類一般化到多類。特殊字符用于重復(fù)前面的選項(xiàng)，但是由于語言是遞歸的，所以必須從相同的層次或更高的層次上選擇該選項(xiàng)。這是由堆棧實(shí)現(xiàn)的。

隊(duì)列

隊(duì)列被定義為“先入先出”。想想銀行柜員面前的隊(duì)伍（對(duì)于我們這些年紀(jì)還大的人來說，還記得在網(wǎng)上銀行出現(xiàn)之前的一段時(shí)間）。隊(duì)列在實(shí)時(shí)編程中非常有用，因此程序可以維護(hù)要處理的作業(yè)列表。

考慮一個(gè)記錄運(yùn)動(dòng)員分段時(shí)間的應(yīng)用程序。你輸入bib號(hào)碼，然后按回車鍵，但你要做的時(shí)候，后面的運(yùn)動(dòng)員也通過了。所以你輸入的是最近接近運(yùn)動(dòng)員的bib號(hào)碼列表，然后按下一個(gè)單獨(dú)的鍵來注冊(cè)隊(duì)列中的下一個(gè)。

集合

一個(gè)集合包含一個(gè)非重復(fù)元素的無序列表。如果添加已經(jīng)在集合中的元素，則不會(huì)有任何更改。由于機(jī)器學(xué)習(xí)的許多數(shù)學(xué)知識(shí)都與集合有關(guān)，所以它們是非常有用的數(shù)據(jù)結(jié)構(gòu)。

關(guān)聯(lián)數(shù)組

在關(guān)聯(lián)數(shù)組中，有兩種類型的數(shù)據(jù)成對(duì)存儲(chǔ)：密鑰及其相關(guān)值。 數(shù)據(jù)結(jié)構(gòu)本質(zhì)上是關(guān)系型的：數(shù)值由其鍵來解決。由于大部分訓(xùn)練數(shù)據(jù)也是關(guān)系型的，這種類型的數(shù)據(jù)結(jié)構(gòu)似乎非常適合于機(jī)器學(xué)習(xí)問題。在實(shí)踐中，它的用處不大，部分原因是大多數(shù)關(guān)聯(lián)數(shù)組只是一維的，而機(jī)器學(xué)習(xí)數(shù)據(jù)通常是多維的。

關(guān)聯(lián)數(shù)組適用于構(gòu)建字典。假設(shè)你正在構(gòu)建一個(gè)DSL，想要存儲(chǔ)一個(gè)函數(shù)和變量列表，并且需要區(qū)分這兩者。

sin =函數(shù)。

var = 變量。

exp =函數(shù)。

x =變量。

sqrt =函數(shù)。

a =變量。

在“sqrt”查詢數(shù)組將返回“函數(shù)”。

自定義數(shù)據(jù)結(jié)構(gòu)

當(dāng)你處理更多問題時(shí)，你肯定會(huì)遇到標(biāo)準(zhǔn)配方框不包含最佳結(jié)構(gòu)的那些問題。你將需要設(shè)計(jì)自己的數(shù)據(jù)結(jié)構(gòu)。考慮一個(gè)多類分類器，它概括了一個(gè)二元分類器來處理具有兩個(gè)以上類的分類問題。一個(gè)明顯的解決方案是平分：遞歸地將類分成兩組。但分層解決方案并不是解決多類的唯一方法，你可以使用類似于二叉樹的方法來組織二進(jìn)制分類器?？紤]幾個(gè)分區(qū)，然后用它們同時(shí)解決所有類的概率。

最通用的解決方案將兩者結(jié)合起來，因此每個(gè)分層分區(qū)不需要是二進(jìn)制的，而是可以通過非分層多類分類器來解決。這是在libAGF庫中采用的方法。

更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)也可以由基本結(jié)構(gòu)組成?？紤]一個(gè)稀疏矩陣類。在稀疏矩陣中，大多數(shù)元素都是零，并且只存儲(chǔ)非零元素。我們可以將每個(gè)元素的位置和值存儲(chǔ)為一個(gè)三元組，并將它們的列表存儲(chǔ)在一個(gè)可擴(kuò)展數(shù)組中。

結(jié)論

數(shù)據(jù)結(jié)構(gòu)本身偶爾也很有趣。令它們真正有趣的是它們可以解決的各種問題。對(duì)于大多數(shù)工作，我使用了許多基本的固定長(zhǎng)度數(shù)組。我主要使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來使程序在運(yùn)行和與外部界面交互方面更加流暢，并且更加便于用戶使用。不像以前的Fortran程序那樣，為了改變網(wǎng)格大小，我不得不忍受一個(gè)接近半小時(shí)的編譯周期（我實(shí)際上在這樣的程序上工作過！）。

即使你無法想出一個(gè)應(yīng)用程序，我仍然認(rèn)為知道諸如棧和隊(duì)列之類的東西是件好事。你永遠(yuǎn)不知道什么時(shí)候會(huì)派上用場(chǎng)。真正復(fù)雜的人工智能應(yīng)用程序可能會(huì)使用定向和無向圖，它們只是樹和鏈表的一般化。如果你無法應(yīng)對(duì)后者，你將如何建立起像前者那樣的東西？

問題

如果你想自己練習(xí)和實(shí)現(xiàn)ML算法的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)嘗試解決下面的一些問題：

將矩陣向量乘法代碼片段封裝到名為matrix_times_vector的子例程中。設(shè)計(jì)子例程的調(diào)用語法。使用struct，typedef或class，將矢量和矩陣分別封裝到一對(duì)稱為vect和matrix的抽象類型中。為這些類型設(shè)計(jì)一個(gè)API。在網(wǎng)上找到至少三個(gè)以上的庫。

下載并安裝LIBSVM庫?？紤]方法Kernel ：： k_funcTIon在“svm.cpp”的第316行。用于保存向量的數(shù)據(jù)結(jié)構(gòu)有哪些優(yōu)缺點(diǎn)？在LIBSVM庫中，如何重構(gòu)內(nèi)核函數(shù)的計(jì)算？文中描述的哪些數(shù)據(jù)結(jié)構(gòu)是抽象類型？你可以使用什么內(nèi)部表示/數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)抽象數(shù)據(jù)類型？上面的列表中是否有未包含的內(nèi)容？

使用二叉樹，設(shè)計(jì)一個(gè)關(guān)聯(lián)數(shù)組。

在LIBSVM中考慮向量類型。如何用它來表示一個(gè)稀疏矩陣？與上面描述的稀疏矩陣類進(jìn)行對(duì)比?？纯赐暾念愋?。每個(gè)代表的優(yōu)點(diǎn)和缺點(diǎn)是什么？實(shí)現(xiàn)一個(gè)treesort和一個(gè)堆排序?，F(xiàn)在使用相同的數(shù)據(jù)結(jié)構(gòu)來查找前k個(gè)元素。什么常見的機(jī)器學(xué)習(xí)算法適合這種情況？用你喜歡的語言實(shí)現(xiàn)你最喜歡的數(shù)據(jù)結(jié)構(gòu)。