可擴充集合檢測
編者按：基于圖的機器算法學習是一個強大的工具。結合運用子產品特性，能夠在集合檢測中發揮更大作用。
很多複雜的問題都可以使用圖來表示和學習----社交網絡，細菌行為，神經網絡等等。本文探讨了圖中節點
自發地形成内部密集連結（在此稱為“集合”）的趨勢; 生物網絡的顯着的和普遍的屬性。
集合檢測旨在将圖劃分為密集連接配接的節點的群集，其中屬于不同集合的節點僅稀疏地連接配接。
圖形分析涉及到節點（描述為磁盤）的研究及其與其他節點（線）的互動。 社群檢測旨在通過其“團體”對節點進行分類。
子產品化的公式為：
其中：nc是集合的數量; lc為邊數; dc為頂點度和; m是圖的大小（邊數）。 我們将使用這個方程以尋找最佳分區的全局度量。 簡而言之：更高的分數将被給予一個集合配置提供更高于外部的内部連結。
那麼該如何進行優化呢？優化方案的重點是利用圖形拓撲知識。我這裡使用了一個特殊的算法簇，稱為聚合。這些算法能夠很快捷地将節點收集（或合并）。 這具有許多優點，因為它通常僅需要鄰近節點的第一級知識和小的增量合并步驟，便可使全局解決方案朝向逐漸平衡。您可能會指出，子產品度量提供了圖形狀态的全局視圖，而不是本地訓示器。 那麼，這如何轉化為我剛才提到的小地方增量？
基本方法确實包括疊代地合并優化局部子產品化的節點，讓我們繼續定義：
其中Σin是c内的權重鍊路的總和，Σtot對連結到c的節點進行求和，k i對連結到節點i,ki的節點進行求和，m為 歸一化因子作為整個圖的權重連結的和。
這個局部優化函數可以很容易地轉換為圖表域内的可解釋的度量。 例如，
• 集合強度：集合中的權重連結的總和。
• 集合人氣：對特定集合中的節點的權重連結事件的總和。
• 節點所屬：從節點到社群的權重連結的總和。
換句話說，權重連結可以是在運作時計算的節點的類型的函數（如果你處理具有各種類型的關系和節點的多元圖，則是有用的）。
壓縮階段之前的收斂疊代示例
現在我們都設定了我們的優化函數和局部成本，典型的聚集政策包括兩個疊代階段（傳輸和壓縮）。假設n個節點的權重網絡，我們開始通過向網絡的每個節點配置設定不同的集合。
傳輸：對于每個節點i，考慮其鄰近節點j，并通過交換c_i為c_j來評估子產品化的增益。貪婪過程将節點傳送到相鄰集合，使子產品化的增益最大化（假設增益為正）。該過程應用于所有節點，直到沒有單獨的移動點。
壓縮：建構一個新的網絡，其節點是在第一階段發現的集合;稱為壓縮的過程（見下圖）。為此，集合之間的邊權重被計算為對應的兩個集合中的節點之間的内部邊之和。
聚集過程：階段1收斂到局部子產品化的局部平衡。 第二階段包括壓縮下一次疊代的圖形，是以減少了要考慮的節點數量，同時也減少了計算時間。
需要解決的關鍵問題：因為這是一個貪婪的算法，你必須根據你的情況和手頭的資料定義一個停止标準。
如何定義這個标準？ 可以嘗試的方式有：最大數量的疊代，在傳輸階段期間的最小子產品性增益，或任何其他相關的資訊。仍然不确定什麼時候停止？ 隻要確定你儲存疊代過程的每個中間步驟，運作直到你的圖形中隻剩下一個節點。 有趣的是，通過跟蹤每個步驟，您還可以從您的集合的層次視圖中獲益，然後作進一步探索和利用。
在後續的博文中，我将讨論如何在使用spark graphx的分布式系統上實作這一點，spark graphx是我的項目的一部分。
<a href="https://promotion.aliyun.com/ntms/act/ambassador/sharetouser.html?usercode=lwju78qa&utm_source=lwju78qa">數十款阿裡雲産品限時折扣中，趕緊點選領劵開始雲上實踐吧！</a>
文章原标題《graph-based machine learning: part i》，作者：sebastien dery