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

本教程分為兩部分：

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

我們為什么需要關心圖形?

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

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

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

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

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

為什么圖形那么有用?

機器學習存在許多問題問題，其中標簽(關于數據點是一類還是另一類的信息)不可用。 無監督學習問題依賴于在數據點之間找到相似性以將數據分類為組或群集。 將此與受監督的方法進行對比，其中數據用適當的類標記，并且您的模型學習使用這些標簽來區分類。

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

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

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

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

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

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

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

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

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

發現異常

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

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

圖形也是聚類!

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

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

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

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

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

運用圖可以幫助你實現類似的集群，而無需像傳統集群那樣選擇數據特征。

每個淺藍色點代表單個網頁，即節點

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

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

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

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

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

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

最重要的一個是：

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

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

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

在現實生活中，這兩個原則會相互作用!

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

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

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

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

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

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

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