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

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

無論哪種情況镇草，你對數(shù)據(jù)結(jié)構(gòu)和算法的了解越多眶痰，在代碼編寫時就越容易。

我不認為機器學(xué)習(xí)中使用的數(shù)據(jù)結(jié)構(gòu)與其他軟件開發(fā)領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)有很大的不同梯啤。然而竖伯，由于許多問題的規(guī)模和難度，對基礎(chǔ)知識的掌握非常重要。

另外黔夭，由于機器學(xué)習(xí)是一個數(shù)學(xué)性非常強的領(lǐng)域宏胯，我們應(yīng)該記住，數(shù)據(jù)結(jié)構(gòu)是如何被用來解決數(shù)學(xué)問題的本姥，以及它們是如何以自己的方式來處理數(shù)學(xué)問題的肩袍。

有兩種方法可以對數(shù)據(jù)結(jié)構(gòu)進行分類:通過它們的實現(xiàn)和它們的操作。

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

數(shù)組

當(dāng)我說基本數(shù)組是機器學(xué)習(xí)中最重要的數(shù)據(jù)結(jié)構(gòu)時，我并不是在開玩笑捺球。這個實用的類型比你想象的要多缸浦。數(shù)組非常重要，因為它們被用于線性代數(shù)——這是你可以使用的最有用和最強大的數(shù)學(xué)工具氮兵。

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

在進行矩陣運算時掺涛，你將不得不從令人眼花繚亂的各種庫、數(shù)據(jù)類型疼进、甚至語言中進行選擇薪缆。許多科學(xué)編程語言，如Matlab颠悬，交互式數(shù)據(jù)語言(IDL)，以及帶有Numpy擴展的Python定血，主要是為處理向量和矩陣而設(shè)計的赔癌。

但這些數(shù)據(jù)結(jié)構(gòu)的優(yōu)點是，即使在更通用的編程語言中澜沟，實現(xiàn)向量和矩陣在metal很簡單灾票，假設(shè)語言中有任何Fortran DNA∶Ｋ洌考慮矩陣向量乘法的平移：

使用C++：

在大多數(shù)情況下刊苍，數(shù)組可以在運行時分配到固定大小既们，或者可以計算可靠的上限。在那些需要數(shù)組無限擴展的情況下正什，可以使用可擴展數(shù)組啥纸，例如C ++標準模板庫（STL）中的vector類。Matlab中的規(guī)則數(shù)組具有相似的可擴展性婴氮，可擴展數(shù)組是整個Python語言的基礎(chǔ)斯棒。

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

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

可擴展數(shù)組非常適合組成其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)并使其可擴展厨内。例如，要存儲稀疏矩陣渺贤，可以在結(jié)尾添加任意數(shù)量的新元素雏胃，然后按位置對其進行排序以更快地定位。稍后詳述志鞍！

稀疏矩陣可用于文本分類問題瞭亮。

鏈表

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

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

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

二叉樹

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

平衡樹

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

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

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

堆

堆是另一個層次結(jié)構(gòu)容劳，類似于樹的有序數(shù)據(jù)結(jié)構(gòu)喘沿，它具有垂直排序，而不是水平排序竭贩。這種排序適用于層次結(jié)構(gòu)蚜印，但不適用于整個層次:父節(jié)點總是大于它的子節(jié)點，但是更高級別的節(jié)點并不一定比下面的節(jié)點要大娶视。

插入和檢索都是通過升級來執(zhí)行的晒哄。元素首先插入到最高可用位置。然后將其與其父母進行比較并提升肪获，直至達到正確的等級寝凌。為了從堆中去掉一個元素，兩個孩子中較大的一個被提升到缺失的位置孝赫，然后這兩個孩子中較大的一個被提升较木，如此等等，直到每一個都變成正確的等級青柄。

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

堆棧

一個堆棧被定義為“先進后出”虹蒋。一個元素被壓入堆棧的頂部，覆蓋前一個元素飒货。頂部的元素必須先彈出才能訪問任何其他元素魄衅。

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

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

隊列

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

考慮一個記錄運動員分段時間的應(yīng)用程序山憨。你輸入bib號碼，然后按回車鍵弥喉，但你要做的時候郁竟，后面的運動員也通過了。所以你輸入的是最近接近運動員的bib號碼列表由境，然后按下一個單獨的鍵來注冊隊列中的下一個棚亩。

集合

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

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

在關(guān)聯(lián)數(shù)組中瘸彤，有兩種類型的數(shù)據(jù)成對存儲：密鑰及其相關(guān)值修然。 數(shù)據(jù)結(jié)構(gòu)本質(zhì)上是關(guān)系型的：數(shù)值由其鍵來解決。由于大部分訓(xùn)練數(shù)據(jù)也是關(guān)系型的质况，這種類型的數(shù)據(jù)結(jié)構(gòu)似乎非常適合于機器學(xué)習(xí)問題愕宋。

在實踐中，它的用處不大结榄，部分原因是大多數(shù)關(guān)聯(lián)數(shù)組只是一維的中贝，而機器學(xué)習(xí)數(shù)據(jù)通常是多維的。

關(guān)聯(lián)數(shù)組適用于構(gòu)建字典臼朗。

假設(shè)你正在構(gòu)建一個DSL雄妥，想要存儲一個函數(shù)和變量列表，并且需要區(qū)分這兩者依溯。

sin =函數(shù)老厌。

var = 變量。

exp =函數(shù)黎炉。

x =變量枝秤。

sqrt =函數(shù)。

a =變量慷嗜。

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

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

當(dāng)你處理更多問題時，你肯定會遇到標準配方框不包含最佳結(jié)構(gòu)的那些問題庆械。你將需要設(shè)計自己的數(shù)據(jù)結(jié)構(gòu)薇溃。

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

考慮幾個分區(qū)策幼，然后用它們同時解決所有類的概率。

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

更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)也可以由基本結(jié)構(gòu)組成唐含∏掣。考慮一個稀疏矩陣類。在稀疏矩陣中捷枯，大多數(shù)元素都是零脑题，并且只存儲非零元素。我們可以將每個元素的位置和值存儲為一個三元組铜靶，并將它們的列表存儲在一個可擴展數(shù)組中。

結(jié)論

數(shù)據(jù)結(jié)構(gòu)本身偶爾也很有趣他炊。令它們真正有趣的是它們可以解決的各種問題争剿。

對于大多數(shù)工作，我使用了許多基本的固定長度數(shù)組痊末。我主要使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來使程序在運行和與外部界面交互方面更加流暢蚕苇，并且更加便于用戶使用。不像以前的Fortran程序那樣凿叠，為了改變網(wǎng)格大小涩笤，我不得不忍受一個接近半小時的編譯周期（我實際上在這樣的程序上工作過ＡЫ鳌）驳规。

即使你無法想出一個應(yīng)用程序痕钢，我仍然認為知道諸如棧和隊列之類的東西是件好事答憔。你永遠不知道什么時候會派上用場鹊汛。

真正復(fù)雜的人工智能應(yīng)用程序可能會使用定向和無向圖仔雷，它們只是樹和鏈表的一般化水醋。如果你無法應(yīng)對后者管削，你將如何建立起像前者那樣的東西?

問題

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

將矩陣向量乘法代碼片段封裝到名為matrix_times_vector的子例程中罗心。設(shè)計子例程的調(diào)用語法。

使用struct城瞎，typedef或class渤闷，將矢量和矩陣分別封裝到一對稱為vect和matrix的抽象類型中。為這些類型設(shè)計一個API脖镀。

在網(wǎng)上找到至少三個以上的庫飒箭。

下載并安裝LIBSVM庫⊙鸦遥考慮方法Kernel :: k_function在“svm.cpp”的第316行补憾。用于保存向量的數(shù)據(jù)結(jié)構(gòu)有哪些優(yōu)缺點？

在LIBSVM庫中卷员，如何重構(gòu)內(nèi)核函數(shù)的計算?

文中描述的哪些數(shù)據(jù)結(jié)構(gòu)是抽象類型盈匾？

你可以使用什么內(nèi)部表示/數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)抽象數(shù)據(jù)類型?上面的列表中是否有未包含的內(nèi)容?

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

在LIBSVM中考慮向量類型削饵。如何用它來表示一個稀疏矩陣?與上面描述的稀疏矩陣類進行對比岩瘦。看看完整的類型窿撬。每個代表的優(yōu)點和缺點是什么?

實現(xiàn)一個treesort和一個堆排序∑裘粒現(xiàn)在使用相同的數(shù)據(jù)結(jié)構(gòu)來查找前k個元素。什么常見的機器學(xué)習(xí)算法適合這種情況劈伴？

用你喜歡的語言實現(xiàn)你最喜歡的數(shù)據(jù)結(jié)構(gòu)密末。

作者：阿里云云棲社區(qū)

鏈接：http://www.reibang.com/p/c650e55f1a03

來源：簡書

著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)跛璧，非商業(yè)轉(zhuǎn)載請注明出處严里。