如果您是一名工程師，您很可能在完成搜索和查找算法時(shí)用過(guò)圖形的數(shù)據(jù)結(jié)構(gòu)。您是否也曾在機(jī)器學(xué)習(xí)問(wèn)題上用過(guò)呢?

本教程分為兩部分：

• ***部分(也就是本篇啦!)： 用于無(wú)監(jiān)督學(xué)習(xí)的圖像

我們?yōu)槭裁葱枰P(guān)心圖形?

對(duì)于數(shù)據(jù)科學(xué)家，圖形是一個(gè)非常令人著迷的研究課題，標(biāo)記數(shù)據(jù)的方法在處理機(jī)器學(xué)習(xí)問(wèn)題并不總是有效。圖形在無(wú)監(jiān)督上下文中非常強(qiáng)大，因?yàn)樗鼈兺ㄟ^(guò)利用數(shù)據(jù)的基礎(chǔ)子結(jié)構(gòu)來(lái)充分利用您擁有的數(shù)據(jù)。

對(duì)于某些機(jī)器學(xué)習(xí)問(wèn)題，圖形能幫您在沒(méi)有標(biāo)簽的地方獲得標(biāo)記數(shù)據(jù)!

我將會(huì)向您介紹一種被稱(chēng)為社團(tuán)檢測(cè)(Community Detection)的方法去找到圖形中同一類(lèi)數(shù)據(jù)點(diǎn)的聚類(lèi)。我們將使用Spark圖形的幀數(shù)來(lái)處理我從2017年9月的Common Crawl dataset開(kāi)始創(chuàng)建的大型網(wǎng)絡(luò)圖表。

圖形的概念是用來(lái)表示對(duì)象配對(duì)關(guān)系的數(shù)據(jù)結(jié)構(gòu)。圖由節(jié)點(diǎn)(也成為頂點(diǎn))和邊組成。他們可以是定向的或者不定向。例如，Twitter可以是一個(gè)有向圖;這種關(guān)系是單向的，僅僅是因?yàn)槲谊P(guān)注另一個(gè)用戶(hù)，不意味著他們也關(guān)注了我! 

當(dāng)您為越來(lái)越多的頁(yè)面執(zhí)行此操作時(shí)，您會(huì)注意到子結(jié)構(gòu)的出現(xiàn)。 在真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)上，這些子結(jié)構(gòu)可能非常龐大和復(fù)雜!

為什么圖形那么有用?

機(jī)器學(xué)習(xí)存在許多問(wèn)題問(wèn)題，其中標(biāo)簽(關(guān)于數(shù)據(jù)點(diǎn)是一類(lèi)還是另一類(lèi)的信息)不可用。 無(wú)監(jiān)督學(xué)習(xí)問(wèn)題依賴(lài)于在數(shù)據(jù)點(diǎn)之間找到相似性以將數(shù)據(jù)分類(lèi)為組或群集。 將此與受監(jiān)督的方法進(jìn)行對(duì)比，其中數(shù)據(jù)用適當(dāng)?shù)念?lèi)標(biāo)記，并且您的模型學(xué)習(xí)使用這些標(biāo)簽來(lái)區(qū)分類(lèi)。

源網(wǎng)址: http://beta.cambridgespark.com/courses/jpm/01-module.html

當(dāng)您無(wú)法輕松獲取更多數(shù)據(jù)時(shí)，無(wú)監(jiān)督學(xué)習(xí)非常有用，因此您可以利用您擁有的數(shù)據(jù)獲得更多價(jià)值。 標(biāo)簽可能不可用; 即使它們是，它們可能太耗時(shí)或昂貴。 在機(jī)器學(xué)習(xí)問(wèn)題開(kāi)始時(shí)，我們也可能不知道我們正在尋找多少類(lèi)對(duì)象!

這就是我們?cè)诠ぞ呦渲行枰獔D形的原因：

• 圖形允許我們?cè)跓o(wú)人監(jiān)督的設(shè)置中從我們的數(shù)據(jù)中獲得更多價(jià)值。 我們可以從圖中獲得聚類(lèi)。

無(wú)人監(jiān)督的學(xué)習(xí)與人類(lèi)學(xué)習(xí)的方式?jīng)]有什么不同。你是如何首先學(xué)會(huì)區(qū)分狗和貓的? 我想對(duì)于大多數(shù)人來(lái)說(shuō)，沒(méi)有人一生下來(lái)就會(huì)長(zhǎng)大，還能用精確的分類(lèi)術(shù)語(yǔ)來(lái)定義狗或貓是什么。你的父母也沒(méi)有給你一張包含數(shù)千只貓狗照片的語(yǔ)料庫(kù)，每張照片都標(biāo)有標(biāo)簽，并要求你畫(huà)出一個(gè)準(zhǔn)確劃分兩類(lèi)動(dòng)物的決定邊界。

如果你的童年和我的一樣，你可能遇到了幾只貓、幾只狗。 一直以來(lái)，你確定了兩種動(dòng)物之間的顯著差異，以及每種動(dòng)物的相關(guān)共同特征。 我們的大腦在從我們的環(huán)境中吸收信息，綜合這些數(shù)據(jù)，以及在我們生活中遇到的截然不同的事物之間制定共同點(diǎn)，我們的大腦實(shí)在是令人難以置信。

這是一個(gè)新聞網(wǎng)站下所有頁(yè)面的示例圖表。

聚類(lèi)有許多令人激動(dòng)的應(yīng)用。我的工作中遇到了一些例子：

• 為無(wú)法通過(guò)標(biāo)簽學(xué)習(xí)的數(shù)據(jù)集預(yù)測(cè)標(biāo)簽
• 生成受眾群體細(xì)分和分類(lèi)分組
• 為類(lèi)似的站點(diǎn)建立推薦人

發(fā)現(xiàn)異常

使用群集作為半監(jiān)督機(jī)器學(xué)習(xí)集合的一部分。 群集可以幫助您將已知標(biāo)簽擴(kuò)展到附近的數(shù)據(jù)點(diǎn)以增加訓(xùn)練數(shù)據(jù)大小，或者如果需要立即使用標(biāo)簽直到輔助系統(tǒng)對(duì)其進(jìn)行分類(lèi)，則可以直接使用它們。

這是最關(guān)鍵的：在無(wú)人監(jiān)督的學(xué)習(xí)中，聚類(lèi)是社團(tuán)，反之亦然。

圖形也是聚類(lèi)!

***的區(qū)別是，您不依賴(lài)于工程特征，而是依賴(lài)圖中的底層網(wǎng)絡(luò)結(jié)構(gòu)來(lái)派生集群。 您可以使用圖中的邊來(lái)測(cè)量數(shù)據(jù)點(diǎn)之間的相似度，而不是使用預(yù)定義的距離度量。

之前我們提到了社團(tuán)(Community)，現(xiàn)在來(lái)大致介紹一下社團(tuán)這個(gè)概念。社團(tuán)定義不是***的，我們通常這樣來(lái)描述它：一個(gè)社團(tuán)是一個(gè)圖的子結(jié)構(gòu)，在這個(gè)子結(jié)構(gòu)中，結(jié)構(gòu)內(nèi)的結(jié)點(diǎn)相互之間聯(lián)系的比結(jié)構(gòu)外的結(jié)點(diǎn)連的更近，更緊密。而找到這些社團(tuán)(或者聚類(lèi))的過(guò)程叫做社團(tuán)檢測(cè)。

Zachary空手道俱樂(lè)部。圖片來(lái)自于KONECT，2017年4月。數(shù)據(jù)集來(lái)自于1977年Zachary的最初研究。

Zachary空手道俱樂(lè)部數(shù)據(jù)集對(duì)一個(gè)跆拳道俱樂(lè)部中各種會(huì)員之間的關(guān)系進(jìn)行了建模。有一次，俱樂(lè)部的兩名成員發(fā)生沖突，俱樂(lè)部最終分裂成多個(gè)社區(qū)。由圖可見(jiàn)，四個(gè)不同的社區(qū)由不同顏色表示。

可以思考一下無(wú)監(jiān)督聚類(lèi)算法是如何進(jìn)行的。需要考慮到這一點(diǎn)，在你選擇的特征空間中，其中的數(shù)據(jù)點(diǎn)與別的數(shù)據(jù)點(diǎn)之間的距離并不是特別緊密。數(shù)據(jù)之間的距離越緊密，也就意味著他們之間相似度越高。 你可以根據(jù)數(shù)據(jù)點(diǎn)之間的距離矩陣，將具有相似屬性的數(shù)據(jù)放入同一個(gè)聚類(lèi)中。

運(yùn)用圖可以幫助你實(shí)現(xiàn)類(lèi)似的集群，而無(wú)需像傳統(tǒng)集群那樣選擇數(shù)據(jù)特征。

每個(gè)淺藍(lán)色點(diǎn)代表單個(gè)網(wǎng)頁(yè)，即節(jié)點(diǎn)

每條深藍(lán)色線代表兩個(gè)頁(yè)之間的鏈接，即邊

新聞網(wǎng)站的子頁(yè)面結(jié)構(gòu)由我使用Gephi生成。

即使在此級(jí)別，您也可以看到頁(yè)面的密集群集或社團(tuán)。 您可以發(fā)現(xiàn)更高度中心性的節(jié)點(diǎn)(頁(yè)面都具有鏈接到它們的大量其他頁(yè)面)

如果一個(gè)站點(diǎn)的連接都如此密集，想象一下我們可以從成千上萬(wàn)的站點(diǎn)中挖掘出什么!

等等，為啥這種方法能行得通呢?

讓我們繼續(xù)往下學(xué)習(xí)。我們需要做出哪些假設(shè)，來(lái)讓我們依靠社區(qū)檢測(cè)來(lái)查找具有相似屬性的節(jié)點(diǎn)?

最重要的一個(gè)是：

結(jié)點(diǎn)之間的連接線并不是隨機(jī)的。

如果你的圖是隨機(jī)的話，那么根本不會(huì)行得通的。但是現(xiàn)實(shí)生活中大多數(shù)的圖并不是隨機(jī)的。結(jié)點(diǎn)相互之間的連接關(guān)系是存在某種相關(guān)性的。以下兩個(gè)原則會(huì)解釋其中的原因：

1. 相互影響原則。相互連接在一起的結(jié)點(diǎn)更容易共享或者傳遞特征。試著想象一下，當(dāng)你的幾個(gè)朋友嘗到了Spark帶來(lái)的便利的時(shí)候，你作為與他們相互聯(lián)系緊密的人，也有可能會(huì)開(kāi)始學(xué)著使用Spark。“我所有的朋友都在用，所以我也要用”
2. 同質(zhì)相吸原則。結(jié)點(diǎn)之間有著一個(gè)相類(lèi)似的特征，或者有某些關(guān)聯(lián)的時(shí)候，很有可能會(huì)連接在一起。例如，如果你和我都喜歡用Python而且都喜歡圖，用圖來(lái)表示的話，我們很有可能是兩個(gè)相互連接的結(jié)點(diǎn)。這也叫做正匹配，“物以類(lèi)聚”。

在現(xiàn)實(shí)生活中，這兩個(gè)原則會(huì)相互作用!

研究人員利用這些現(xiàn)象可以對(duì)圖中的一些有趣的問(wèn)題建模。例如，F(xiàn)arine et al通過(guò)動(dòng)物之間強(qiáng)烈關(guān)聯(lián)性預(yù)測(cè)了狒狒的位置——對(duì)行為生態(tài)學(xué)產(chǎn)生了很好的影響。

Farine, Damien R., et al“最近鄰居和長(zhǎng)期分支機(jī)構(gòu)都能預(yù)測(cè)野生狒狒集體行動(dòng)期間的個(gè)體位置。”科學(xué)報(bào)告6(2016)：27704

同質(zhì)相吸原則經(jīng)常用于社交網(wǎng)絡(luò)研究。Adamic和Glance在2004年大選期間對(duì)政治博客進(jìn)行了一項(xiàng)引人入勝的研究。 他們用圖表的方式，顯示了不同的博客如何相互引用;藍(lán)色節(jié)點(diǎn)代表自由博客，紅色節(jié)點(diǎn)是保守的博客。 也許不出所料，他們發(fā)現(xiàn)博客傾向于引用同樣政治傾向的其他博客。

Adamic，Lada A.和Natalie Glance。 “政治博客圈和2004年美國(guó)大選：區(qū)分了他們的博客。”第三屆國(guó)際鏈接發(fā)現(xiàn)研討會(huì)論文集。ACM，2005年。

即使在個(gè)人層面上，同質(zhì)相吸原則也是有道理的。 機(jī)會(huì)是你自己的朋友網(wǎng)絡(luò)由可能與你年齡相同，住在同一個(gè)城鎮(zhèn)，有相同的愛(ài)好，或去同一所學(xué)校的人組成! 在工作中，你是一個(gè)活生生同質(zhì)相吸原則的例子。不要畏懼，大膽將它加入到簡(jiǎn)歷中!

我們已經(jīng)介紹了圖是怎么運(yùn)用數(shù)據(jù)中基本的網(wǎng)絡(luò)特性來(lái)生成聚類(lèi)。在互聯(lián)網(wǎng)中，這些聚類(lèi)對(duì)于推薦系統(tǒng)、觀眾分類(lèi)、以及異常檢測(cè)等等都有重大意義。

在第二部分(鏈接傳送門(mén))，我們會(huì)將對(duì)社團(tuán)檢測(cè)技術(shù)進(jìn)行深入研究，并且學(xué)著怎么利用常用的爬蟲(chóng)數(shù)據(jù)集，從網(wǎng)頁(yè)的圖狀結(jié)構(gòu)中得到聚類(lèi)。