建站
咨詢
售后
建站咨詢
新聞中心
圖論一直是數(shù)學(xué)里十分重要的學(xué)科，其以圖為研究對象，通常用來描述某些事物之間的某種特定關(guān)系。而在機(jī)器學(xué)習(xí)的世界里，我們希望從數(shù)據(jù)中挖掘出隱含信息或模型。因此，如果我們將圖中的結(jié)點作為隨機(jī)變量，連接作為相關(guān)性關(guān)系，那么我們就能構(gòu)造出圖模型，并期望解決這一問題。本文將為構(gòu)造該模型提供最基礎(chǔ)的概念。
公司主營業(yè)務(wù)：網(wǎng)站設(shè)計制作、網(wǎng)站設(shè)計、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)建站是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)建站推出盤龍免費(fèi)做網(wǎng)站回饋大家。
我們都知道機(jī)器學(xué)習(xí)里的決策樹，其可以表示為給定特征條件下類的條件概率分布。并且我們知道決策樹由結(jié)點和有向邊組成，結(jié)點又由表示特征的內(nèi)部結(jié)點和表示類的葉結(jié)點構(gòu)成。而通常決策樹的學(xué)習(xí)又包括了特征的選擇、決策樹的生成和決策樹的剪枝。那么這種樹型算法又是來自哪呢?其實樹型只是圖的一個小分支，而接下來我們將進(jìn)一步了解源于離散數(shù)學(xué)并十分重要的分支：圖論(graph theory)。
如果這是你***次涉足關(guān)于圖論的內(nèi)容，那么本篇文章將會給你一個清晰的概念。同時也希望本文能將圖論的思想、基本模型闡述清楚，因此不論是對以后的機(jī)器學(xué)習(xí)模型構(gòu)建還是概率圖模型的理解都能提供一定的助力。
Loosey–goosey圖
當(dāng)***次開始研究非線性結(jié)構(gòu)時，我們需要學(xué)習(xí)它們最基礎(chǔ)的特征：即數(shù)據(jù)并不遵循特有的順序，至少是沒有明顯的數(shù)值關(guān)系，這一點就和我們看到的數(shù)組與鏈表一樣。正如我們所了解的，樹型結(jié)構(gòu)從根結(jié)點開始，并能和其他結(jié)點相連接，也就是說一棵完整的樹可以由其子樹構(gòu)成。樹由一組規(guī)則定義而成：即一個根結(jié)點可能連接或不連接到其他結(jié)點，但最終所有葉結(jié)點或內(nèi)部結(jié)點都能追溯到這個特定的位置。一些樹有更多的特定規(guī)則，如二叉搜索樹，該樹在任意時間內(nèi)每個結(jié)點都只和兩個子結(jié)點相連。而機(jī)器學(xué)習(xí)常用的決策樹就可以看成是 IF-THEN 規(guī)則的集合。即由決策樹的根結(jié)點到葉結(jié)點的每一條路徑構(gòu)建一條規(guī)則，路徑上內(nèi)部結(jié)點的特征對應(yīng)著規(guī)則的條件，而葉結(jié)點的類對應(yīng)著規(guī)則的結(jié)論。
那我們是否能將構(gòu)成樹狀的這些規(guī)則拋棄掉，不用再嚴(yán)格地遵守這些規(guī)則而生成圖(graph)。當(dāng)然這樣做是不會出錯的，只是生成不了樹，也不能以樹狀的結(jié)構(gòu)進(jìn)行計算了。但是我們進(jìn)一步能用圖進(jìn)行計算或處理任務(wù)。
| 樹型只不過是一種受限圖，只不過是遵循眾多規(guī)則的圖。樹型永遠(yuǎn)是圖中的一種，但圖遠(yuǎn)遠(yuǎn)不止是樹。 |
那么到底是什么讓樹型有別于傘狀圖呢?
首先，一棵樹只能朝一個方向傳播，即樹型是由有向邊(directed edge)構(gòu)成的。每一顆樹都是由根節(jié)點開始，向下往子節(jié)點或葉節(jié)點傳播。同樣樹型的每一條路徑都是唯一的，并且路徑上的所有子結(jié)點有且僅有一個父節(jié)點。所以這種樹型結(jié)構(gòu)一定不會存在循環(huán)結(jié)構(gòu)或鏈路。
而通過圖，所有的這些限制好像都突然消失了。因為圖是沒有任何「根結(jié)點」、「葉節(jié)點」和「單向邊」等這些概念的，所以圖中的結(jié)點可以連接多個子結(jié)點也可以有多個父結(jié)點，路徑也可以是有向流或者無向邊。或者如果想要圖更加復(fù)雜一點，也可以采用有向流和無向邊的組合，但是本文暫時并不會關(guān)注這些復(fù)雜系統(tǒng)。
有向圖和無向圖
現(xiàn)在我們已經(jīng)知道圖確實打破了構(gòu)造樹型的所有規(guī)則。但每一個圖都必須遵守一個基本原則：即圖有且至少有一個單結(jié)點。就像樹型至少需要一個根結(jié)點才可以看作是「樹」，圖也至少需要一個單結(jié)點以便可以看作是「圖」。只有一個結(jié)點的圖通常稱為「單例圖」，基本上我們不會使用這種單例圖處理任務(wù)。
通常能進(jìn)行運(yùn)算處理的圖都是更復(fù)雜一些的圖，但是不要太擔(dān)心，本文所描述的圖都不會太復(fù)雜，不過有些圖真的是超級復(fù)雜的。
首先我們會探討一下很容易辨認(rèn)和理解的兩種圖：有向圖(directed graphs)和無向圖(undirected graphs)。這兩種圖在圖論(graph theory)探討的問題中十分常見。
在圖中，結(jié)點和結(jié)點之間的連接并沒有確切的規(guī)則，邊(有時候也稱為鏈接)能以任何方式連接結(jié)點。
不同類型的邊或路徑對定義和識別圖時非常重要。邊的類型實際上是圖之間***、最明顯的區(qū)別之一。大多數(shù)情況下(只有一種例外)，圖會有兩種類型的邊：即具有方向或流向的邊和不具有方向或流動的邊。我們將其稱為有向邊(directed edges)和無向邊(undirected edges)。
在有向邊中，兩個結(jié)點以特定的方式連接。如下圖結(jié)點 A 連接結(jié)點 B 的方式所示，有向邊規(guī)定了兩個結(jié)點之間只有單一的方向，即只能從起始結(jié)點(origin)沿特定方向到目標(biāo)結(jié)點(destination)，永遠(yuǎn)不能反過來從目標(biāo)結(jié)點到起始結(jié)點。這種類型的有向邊在圖論問題中十分常見。
現(xiàn)在，我們再介紹一下與有向邊完全不同的無向邊。在無向邊(undirected edge)里，可通過的路徑是雙向的。也即兩個結(jié)點之間的路徑是雙向互通的，起始結(jié)點和目標(biāo)結(jié)點并沒有固定。
這種差異是十分重要的，因為圖中的邊確定了圖的類型。如果圖中所有的邊都是有向邊，那么該圖就是有向圖(directed graph)。如果圖所有的邊都是無向邊，那么該圖就是無向圖(undirected graph)。
以上所描述的圖看起來很有結(jié)構(gòu)性，但也許我們更應(yīng)該關(guān)心兩件事情：首先具體是什么條件或事件填充了圖，其次我們具體要關(guān)注圖的什么信息?
輕輕地：我們來到了圖的王國
計算機(jī)科學(xué)喜歡借鑒其他學(xué)科。具體來說是喜歡借鑒邏輯學(xué)和數(shù)學(xué)的許多概念。而圖論也是一樣，其最開始就是數(shù)學(xué)的一個分支，且以圖為研究對象，圖論經(jīng)常是研究頂點和邊組成圖的數(shù)學(xué)理論和方法。而我們所熟悉的圖數(shù)據(jù)結(jié)構(gòu)或樹型算法等計算機(jī)概念實際上都來自于數(shù)學(xué)，而對圖的研究就是圖論(graph theory)。
在數(shù)學(xué)中，圖是一種正式表征網(wǎng)絡(luò)的結(jié)構(gòu)，其基本上是所有互連對象的集合。
事實證明，當(dāng)計算機(jī)科學(xué)家將圖論應(yīng)用于代碼(創(chuàng)造出圖數(shù)據(jù)結(jié)構(gòu)或樹型算法等)時，那些理論并沒有改變多少。所以本文描述和實現(xiàn)圖的術(shù)語就是在數(shù)學(xué)圖論中的確切術(shù)語。
在數(shù)學(xué)術(shù)語中，我們將圖描述為有序?qū)?ordered pairs)。還記得以前學(xué)過的函數(shù)，它的定義就是在二維坐標(biāo)軸上分布的有序?qū)?x，y)集合。圖也是使用類似的定義，只不過使用圖的結(jié)點(vertices)v 和邊(edges)e 代替 x 和 y。
因此，圖的正式數(shù)學(xué)定義即為：G=(V，E)
但是問題來了，如果我們的圖有多個結(jié)點和多條邊怎么辦，實際上有多個結(jié)點通常就會有多條邊，那么這種情況又該怎么定義圖呢。
實際上上述定義式并不會失效，因為有序?qū)?V，E)實際上是由兩組對象組成：一組結(jié)點，一組邊。
現(xiàn)在廣義的圖定義變得更加有意義，但如果能有一個實例來說明的話，這個概念就會比較好理解，所以下圖是我們使用 8 個結(jié)點，12 條邊組成的一個無向圖，我們會詳細(xì)解釋該圖是如何用數(shù)學(xué)正式定義。
那么上圖那個例子到底說了些什么。
我們將有序?qū)τ洖?V，E)，但因為每一項都是一個對象，所以我們必須把這些項寫出來。V 已經(jīng)定義為八個結(jié)點的無序集，而「無序」這一概念在這里非常重要。因為圖與樹型不同，其結(jié)點沒有層次結(jié)構(gòu)。因此排序并不重要，我們也不需要對它們進(jìn)行排序。
我們還須將 E 定義為包含所有邊的項。同樣，邊這一對象也是無序的。原因就在于圖的邊是無向邊，它沒有固定的流向或方向，也就是沒有固定的起始節(jié)點和目標(biāo)節(jié)點，所以每條邊都是無序地。
當(dāng)然，無向圖的「無序」這一特性可能會引起一些疑惑，但有向圖又有什么性質(zhì)呢?下面是另一個案例，該圖是由三個結(jié)點和三條有向邊組成的有向圖。
在有向圖中，定義結(jié)點的方式和無向圖中是一樣的，但有向邊和無向邊的定義是不一樣的。在有向圖中，邊的對象定義為有序?qū)?使用圓括弧表示)，因為這種情況下，邊的方向十分重要。因為在有向圖中，邊只能是從起始結(jié)點到目標(biāo)結(jié)點，所以邊必須進(jìn)行排序，從而定義 E 中有序?qū)η耙粋€元素為起始結(jié)點，后一個元素為目標(biāo)結(jié)點。
所以以上就是我們?nèi)绾味x一個圖，但是在定義圖之后，我們什么時候才能實際應(yīng)用圖呢。下面我們將一起來了解一下圖的應(yīng)用和計算。
超級社交圖
圖其實就在我們身邊，只是我們不了解而已。
事實上，你在閱讀這篇文章的時候，你就是處于一張圖中。網(wǎng)絡(luò)就是巨大的圖結(jié)構(gòu)，每個終端是一個結(jié)點，而互聯(lián)網(wǎng)就是網(wǎng)絡(luò)的邊。網(wǎng)頁也是，當(dāng)我們點擊網(wǎng)站并在 URL 之間來回瀏覽時，我們就是在圖中瀏覽。有的網(wǎng)頁之間是無向邊，可以在兩個網(wǎng)頁之間來回切換，而有的是有向邊，只能從一個網(wǎng)頁轉(zhuǎn)到另一個。
現(xiàn)在，我們使用一個更加生動的案例，以說明圖與日常的交互：社交網(wǎng)絡(luò)。
微信是一個龐大的社交網(wǎng)絡(luò)，它也是一種圖。如果我們能更多地去思考它實際的功能，那么我們可以更好地理解怎樣定義和確定圖的類型是什么。在微信上，如果我希望成為你的朋友，那么我需要添加你為好友，且你必須接受我的請求。在你不是我的微信好友情況下，我也會不是你的微信好友。兩個用戶之間的關(guān)系(圖中的結(jié)點和邊)是雙向的。其沒有起始節(jié)點和目標(biāo)節(jié)點這一概念。
那你現(xiàn)在能判斷微信的圖是什么類型了么。
因此微信就是一種大型無向圖，用戶之間可以同時相互傳遞信息。
但另外一種社交網(wǎng)絡(luò)微博卻是有向圖，因為在用戶發(fā)布微博時，博文這一信息會在同時間點由用戶向粉絲發(fā)送，這一過程是有方向不可逆的。
在了解了圖論的基礎(chǔ)概念和定義表達(dá)式后，或許我們可以進(jìn)一步窺探一些概率圖模型的重要思想。
機(jī)器學(xué)習(xí)的一個核心任務(wù)是從觀測到的數(shù)據(jù)中挖掘隱含的知識，而概率圖模型是實現(xiàn)這一任務(wù)的重要手段。概率圖模型巧妙地結(jié)合了圖論和概率論。從圖論的角度來說，概率圖模型就是一個包含結(jié)點與邊的圖。結(jié)點可以分為兩類：隱含結(jié)點和觀測結(jié)點。邊可以分為有向邊或無向邊。從概率論的角度來看，概率圖模型是一個概率分布，圖中的結(jié)點對應(yīng)于隨機(jī)變量，邊對應(yīng)于隨機(jī)變量的相關(guān)性關(guān)系。給定一個實際問題，我們通常會觀測到一些數(shù)據(jù)，并且希望能夠挖掘出隱含在數(shù)據(jù)中的知識。那么怎樣才能使用概率圖模型挖掘這些隱藏知識呢?通常情況下我們會構(gòu)建一個圖：用觀測結(jié)點表示觀測到的數(shù)據(jù)，用隱含結(jié)點表示潛在的知識，用邊來描述知識與數(shù)據(jù)的相互關(guān)系，***獲得一個概率分布。給定概率分布之后，通過進(jìn)行兩個任務(wù)獲取知識：即推斷 (給定觀測結(jié)點，推斷隱含結(jié)點的后驗分布)和學(xué)習(xí) (學(xué)習(xí)概率分布的參數(shù))。
基本的圖模型可以大致分為兩個類別：貝葉斯網(wǎng)絡(luò) (Bayesian Network) 和馬爾可夫隨機(jī)場 (Markov Random Field)。它們的主要區(qū)別在于采用不同類型的圖來表達(dá)變量之間的關(guān)系：貝葉斯網(wǎng)絡(luò)采用有向無環(huán)圖 (Directed Acyclic Graph) 來表達(dá)因果關(guān)系，馬爾可夫隨機(jī)場則采用無向圖 (Undirected Graph) 來表達(dá)變量間的相互作用。這種結(jié)構(gòu)上的區(qū)別導(dǎo)致了它們在建模和推斷方面的一系列微妙的差異。
至此，我們已經(jīng)知道了圖論到底是什么，也知道基本有向圖和無向圖的標(biāo)準(zhǔn)定義。在文章的***，我們更是將圖論的基本概念和概率論的基本思想相結(jié)合來理解概率圖模型。但我們都知道概率圖模型十分強(qiáng)大與重要，所以我們也許需要進(jìn)一步專門地學(xué)習(xí)這一機(jī)器學(xué)習(xí)方法。
原文：
https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory?utm_content=buffer6fb86&utm_medium=social&utm_source=twitter.com&utm_campaign=buffer
【本文是專欄機(jī)構(gòu)機(jī)器之心的原創(chuàng)譯文，微信公眾號“機(jī)器之心( id: almosthuman2014)”】
戳這里，看該作者更多好文
當(dāng)前文章：想了解概率圖模型？你要先理解圖論的基本定義與形式
本文來源：http://www.fisionsoft.com.cn/article/cocgdgj.html
