如果您是一名工程師，您很可能在完成搜索和查找算法時用過圖形的數(shù)據結構。您是否也曾在機器學習問題上用過呢?

本教程分為兩部分：

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

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

對于數(shù)據科學家，圖形是一個非常令人著迷的研究課題，標記數(shù)據的方法在處理機器學習問題并不總是有效。圖形在無監(jiān)督上下文中非常強大，因為它們通過利用數(shù)據的基礎子結構來充分利用您擁有的數(shù)據。

對于某些機器學習問題，圖形能幫您在沒有標簽的地方獲得標記數(shù)據!

我將會向您介紹一種被稱為社團檢測(Community Detection)的方法去找到圖形中同一類數(shù)據點的聚類。我們將使用Spark圖形的幀數(shù)來處理我從2017年9月的Common Crawl dataset開始創(chuàng)建的大型網絡圖表。

圖形的概念是用來表示對象配對關系的數(shù)據結構。圖由節(jié)點(也成為頂點)和邊組成。他們可以是定向的或者不定向。例如，Twitter可以是一個有向圖;這種關系是單向的，僅僅是因為我關注另一個用戶，不意味著他們也關注了我! 

當您為越來越多的頁面執(zhí)行此操作時，您會注意到子結構的出現(xiàn)。 在真實的網絡數(shù)據上，這些子結構可能非常龐大和復雜!

為什么圖形那么有用?

機器學習存在許多問題問題，其中標簽(關于數(shù)據點是一類還是另一類的信息)不可用。 無監(jiān)督學習問題依賴于在數(shù)據點之間找到相似性以將數(shù)據分類為組或群集。 將此與受監(jiān)督的方法進行對比，其中數(shù)據用適當?shù)念悩擞洠⑶夷哪Ｐ蛯W習使用這些標簽來區(qū)分類。

源網址: http://beta.cambridgespark.com/courses/jpm/01-module.html

當您無法輕松獲取更多數(shù)據時，無監(jiān)督學習非常有用，因此您可以利用您擁有的數(shù)據獲得更多價值。 標簽可能不可用; 即使它們是，它們可能太耗時或昂貴。 在機器學習問題開始時，我們也可能不知道我們正在尋找多少類對象!

這就是我們在工具箱中需要圖形的原因：

• 圖形允許我們在無人監(jiān)督的設置中從我們的數(shù)據中獲得更多價值。 我們可以從圖中獲得聚類。

無人監(jiān)督的學習與人類學習的方式沒有什么不同。你是如何首先學會區(qū)分狗和貓的? 我想對于大多數(shù)人來說，沒有人一生下來就會長大，還能用精確的分類術語來定義狗或貓是什么。你的父母也沒有給你一張包含數(shù)千只貓狗照片的語料庫，每張照片都標有標簽，并要求你畫出一個準確劃分兩類動物的決定邊界。

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

這是一個新聞網站下所有頁面的示例圖表。

聚類有許多令人激動的應用。我的工作中遇到了一些例子：

• 為無法通過標簽學習的數(shù)據集預測標簽
• 生成受眾群體細分和分類分組
• 為類似的站點建立推薦人

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

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

這是最關鍵的：在無人監(jiān)督的學習中，聚類是社團，反之亦然。

圖形也是聚類!

***的區(qū)別是，您不依賴于工程特征，而是依賴圖中的底層網絡結構來派生集群。 您可以使用圖中的邊來測量數(shù)據點之間的相似度，而不是使用預定義的距離度量。

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

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

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

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

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

每個淺藍色點代表單個網頁，即節(jié)點

每條深藍色線代表兩個頁之間的鏈接，即邊

新聞網站的子頁面結構由我使用Gephi生成。

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

如果一個站點的連接都如此密集，想象一下我們可以從成千上萬的站點中挖掘出什么!

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

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

最重要的一個是：

結點之間的連接線并不是隨機的。

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

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

在現(xiàn)實生活中，這兩個原則會相互作用!

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

Farine, Damien R., et al“最近鄰居和長期分支機構都能預測野生狒狒集體行動期間的個體位置。”科學報告6(2016)：27704

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

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

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

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

在第二部分(鏈接傳送門)，我們會將對社團檢測技術進行深入研究，并且學著怎么利用常用的爬蟲數(shù)據集，從網頁的圖狀結構中得到聚類。