在上一篇文章中，我們主要介紹了論文《Mobile Targeting Using Customer Trajectory Patterns》的整體思路，並推薦了這篇論文關於檢驗推薦效果的實驗設計。

MonsterGroup：第二期（上）：基於用戶軌跡聚類的POI推薦?

zhuanlan.zhihu.com圖標

現在我們繼續對這篇文章的探討，本次我們聚焦演算法的部分。這篇論文的演算法之所以效果高於其他組別，核心思想就在於：1）從多個角度加權計算了用戶之間的相似度；2）根據兩兩之間的相似度進行了Graph Clustering。最終的效果就是有相同偏好的用戶被聚在了同一組，那麼既然大家興趣類似，你喜歡的自然大概率也是我喜歡的。

接下來我們就介紹一些關於Clustering的知識，尤其會詳細介紹經典的演算法，最後我們再推薦幾篇相關的論文。

一、聚類的兩種類型

對已知的「點」進行聚類，我們首先要判斷這些「點」是建立在什麼數學結構上的，一般來說如果這些點存在「類別」，那麼用兩種結構來描述都是自然的：

  • 歐氏空間：所有點都坐落在歐式空間裏，兩兩之間的距離的定義是自然的，距離越小，「相似度」越高。
  • 圖（Graph）：所有點都是Graph中的點，兩兩之間的「相似度」用edge的權重來度量是自然的，權重越大，「相似度」越高。

在這兩種不同的結構中，度量與相似度的關係正好是反著的，這自然也就衍生出兩種完全不同的聚類方法：Vector Clustering 和 Graph Clustering。

那麼我們在實際應用中，用哪種結構更好呢？有時候還這不好說，比如我們舉個例子。比如對於兩個點，我們從多個維度用數值定義了屬性，得到兩個向量 x_1 和 x_2 。那麼 | x_1 - x_2 | 就是個很自然的距離， e^{-|x_1 - x_2 |} 就是個很自然的權重。如果按照前一種，那就是Vector Clustering，如果按照後一種，那就是Graph Clustering。

Vector Clustering似乎大家更熟悉些，經典的演算法包括K-Means等等。Graph Clustering雖然也常見，但感覺大家對Markov Clustering Algorithm要相對陌生一些，而我們推薦的這篇論文恰恰選擇的是把用戶建立在了圖上，然後用Markov Clustering進行聚類，因此我們接下來著重介紹Graph Clustering。

二、Markov Clustering Algorithm

我們考慮這樣一個Graph：

ABCD間兩兩互連，EFG間兩兩互連，ABCD與EFG僅靠DE一條邊連接，而且DE的權重還是最小的。因此，很顯然，ABCD應該聚成一類，EFG應該聚成一類。

a）一個極端

Markov Clustering是如何把這種直觀的視覺轉為演算法的呢？我們建立這樣一個Markov模型：一個人在圖上隨機遊走（Random Walk），每一步隨機走向一個相鄰的點，轉移的概率和邊的權重成正比。比如當處於A時，下一步走到B、D的概率都是0.25，走到C的概率是0.5。那麼一個很自然的想法就是：假如你從ABCD這一堆裏出發，那麼最後還是在ABCD這一堆裏的概率高；如果你從EFG這一堆裏出發，那麼最後還是在EFG這一堆裏的概率高。然而這完全是錯的：一個Markov鏈的平穩分佈，和初始位置無關，無論你從哪兒出發，最終轉移到某個點的概率都是相同的（當然Markov鏈要滿足一些很基本的性質）。說到這裡，如果你對Markov鏈不熟悉，建議讀一下下面這本書的Chapter 4，大概一個多小時能讀完。

Introduction to Probability Models?

www.elsevier.com圖標

最終的平穩分佈怎麼求呢？我們記這個Markov鏈的狀態轉移矩陣為 T ， T(i, j) 表示從 j 轉移到 i 的概率，那麼 T^n 就表示 n 步後，從 j 轉移到 i 的概率， 當 n o infty 後，轉移矩陣的每行都會是相同的值（因為轉移到 i 的概率不依賴於最開始的位置），這個概率也就是平穩分佈中的概率。

綜上，這樣一個簡單的隨機遊走，對聚類沒有什麼直接的幫助，因為長期看，任意位置都能到達，而且出現在各個位置的概率是相同的。原因何在？因為有些「閘門」雖然小，但終究存在，你還是總能有機會通過去。

b）另一個極端

因此，一個直觀的想法是讓大的「閘門」更大，小的「閘門」更小。極端情況就是，我們處於圖中一點時，只能沿著權重最大的邊轉移。相應的新轉移矩陣也就是對 T 的每一列，最大值的位置取1，其他位置都是0。這樣結果會如何呢？以上面的圖為例：如果從ABCD中出發，那麼就會在AC間震蕩，如果從EFG中出發，那麼就會在FG間震蕩。

我們實現了兩個目標：1）最終所處的位置與出發點相關的，這是我們希望看到的；2）ABCD中出發的點跑不到EFG了，反之也相同，這也是我們希望看到的。然而，這又走向了另一個極端，這個圖被分割得過於支離破碎，而且有很多點一段時間後就不會再到達了。

以上我們討論的兩種狀態轉移方式分別走向了兩個極端，演算法中有個常用的思路就是找到兩個極端情況，然後混合一下加個權，就會是理想的中間狀態。對於我們當下的情況，「混合」的方式很簡單，就是我們不要一上來就把「閘門」的放縮走向極端，而要一點一點放縮。我們只需要交替對狀態轉移矩陣 T 執行一下兩種操作：

  • 轉移矩陣取冪： T = T^k
  • 放縮一下閘門： T_{cdot j} = T_{cdot j}^r / sum_i T_{i j}^r 。

我們來解釋一下這個放縮過程。對於一個向量 [1, 2, 3, 4] ，標準化後為 [0.1, 0.2, 0.3, 0.4] 。我們對向量中的某一項做平方，得到 [0.01, 0.04, 0.09, 0.16] ，標準化後為 [0.0333, 0.1333, 0.3000, 0.5333] ，很明顯，高權重與低權重的差距更大了。

重複上述兩個操作， T 依然會收斂，收斂後觀察 T ，在每一行中，只有部分元素是非零的，這些非零元素位置對應的點就是一類。

Talk is Cheap. Show me the code. 下面我們直接給了Matlab代碼，大家可以直接運行（生成點，構建Graph，實現聚類，展示結果的部分都寫好了），觀察結果。

% 生成3組2維正態分佈，然後混在一起
Group1 = repmat([4, 2], 20 , 1) + randn(20, 2) * chol([1, 0; 0, 1]);
Group2 = repmat([3, 7], 30 , 1) + randn(30, 2) * chol([2, 0; 0, 2]);
Group3 = repmat([8, 4], 40 , 1) + randn(40, 2) * chol([1, 0; 0, 1]);
Point = [Group1; Group2; Group3]; N = length(Point);

% 用e^(-l)做覈定義Graph中邊的weight，若l>3，則不建立邊
f1 = figure(1);
T = zeros(N);
for i = 2: N
for j = 1: (i - 1)
l = norm(Point(i, :) - Point(j, :));
if l > 3
continue
end
plot([Point(i, 1), Point(j, 1)], [Point(i, 2), Point(j, 2)], color, [0.8, 0.8, 0.8]); hold on
T(i, j) = exp(-l); T(j, i) = T(i, j);
end
end
a = gca; f2 = figure(2); copyobj(a, f2);

% T為Markov鏈對應的狀態轉移矩陣
S = sum(T);
for j = 1: N
T(:, j) = T(:, j) / S(j);
end

% Markov Clustering Algorithm
M = T;
for iter = 1: 200
M = M ^ 2;

for j = 1: N
M(:, j) = M(:, j) .^ 2;
M(:, j) = M(:, j) / sum(M(:, j));
end
end

% 在figure(1)中展示原本的分類，在figure(2)中展示聚類的結果
figure(1);
scatter(Group1(:, 1), Group1(:, 2)); hold on
scatter(Group2(:, 1), Group2(:, 2)); hold on
scatter(Group3(:, 1), Group3(:, 2));

figure(2);
for i = 1: N
loc = find(M(i, :) > 10e-3);
if isempty(loc)
continue
end
group = Point(loc, :);
scatter(group(:, 1), group(:, 2)); hold on
end

結果：

原本的類別
聚類的結果

三、Clique Percolation Method

Markov Clustering Algorithm給出的聚類結果，每個點只屬於一類。但是在現實生活中，每個人往往不屬於一個Community，比如你上大學時會形成一個圈子，工作後又會形成一個圈子，這兩個圈子對你都有很大的影響。因此，我們有時候也希望提出一個聚類演算法，最後得到的Community可以overlap。

這個演算法已經被提出了，並被大量應用在各個領域，這就是Clique Percolation Method。Clique的含義為「小黨派」，在圖論中，如果一個圖中的幾個點，兩兩之間都有邊，則這幾個點就構成了一個Clique。實現Clique Percolation Method，首先要找到所有的Clique。關於這個演算法，我們這裡不再展開，在這裡推薦一個不錯的PPT：

Clique Percolation Method?

www.comp.nus.edu.sg

讀完這個PPT大概需要5分鐘時間，讀完之後演算法基本就懂了，當然如何提升運行效率還是個更複雜的問題。

對於有權重的圖，這個演算法也是有效的，這時候在定義Clique時，我們需要邊的權重滿足一定條件，這裡也不再展開。

四、結語

關於圖聚類，我們有大量的演算法可以幫助我們實現。有在度量空間內聚類的，有在圖上聚類的；有聚成獨立的類的，有聚成overlapping的類的。實際上，在我看來，用哪個都差不多。比如我們推薦的這篇通過聚類進而有針對性發廣告的論文，把node建立在Graph上是OK的，建立在度量空間裏也是很平凡的；聚類的時候用Markov演算法聚成獨立的類，推薦的結果是好的，假如聚成有重疊的類，推薦的結果也不會差。

這是因為，現實生活的模型要比我們能model的複雜得多，從一個角度說，根本不存在這麼簡單的「類」，因此把演算法做得再複雜，也不見得能提升效果，也很難說哪種聚類方法更好；從另一個角度說，簡單的聚類確實能很好的表述現實模型中很核心的一部分，因此但凡是個不錯的聚類，都能幫助我們提升對社會的認識。

最後，核心的核心，還是數據。這些演算法都很簡單，也玩兒不出什麼新的花樣了，難的是去找數據。比如這個廣告推薦，演算法上早就不知道比這個高端到哪兒去了，但是人家找到數據，並進行了檢驗，這就能發MS。

附錄：補充論文

關於聚類的題材，我們再補充幾篇論文

@愛可可-愛生活 老師近期的論文推薦的裏也一篇文章也與此相關，這篇論文是個很不錯的綜述，對Markov Clustering和Clique Percolation都有提及，針對的是動態的圖（即Community也在隨著時間演化）：

  • He, Ziwei, et al. "A Comparative Study of Different Approaches for Tracking Communities in Evolving Social Networks."2017 IEEE International Conference on Data Science and Advanced Analytics (DSAA). IEEE, 2017.

Markov Clustering都提出20年了，用這個演算法隨便聚個類依舊能水篇論文，比如這篇，用Markov Clustering 在宇宙中尋找galaxy groups，推薦這篇文章只是說明一下Markov Clustering被應用的廣泛性：

  • Stothert, L., P. Norberg, and C. M. Baugh. "A new approach to finding galaxy groups using Markov Clustering."Monthly Notices of the Royal Astronomical Society: Letters(2019).

這篇也很有意思，我們剛才提到的演算法都是先定義點與點之間的相似度，再進行聚類，而這篇論文提出的方法在計算相似度的同時完成了聚類。想法也很簡單，也用到了剛才提過的找兩個極端在加權混合一下的思想：

  • Nie, Feiping, Xiaoqian Wang, and Heng Huang. "Clustering and projected clustering with adaptive neighbors."Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.

下面這篇更有意思，點的信息是有殘缺的（比如研究每個人對電影的偏好，有200部電影，我們只能得到你對其中50部的看法），這篇文章提出了在殘缺的前提下聚類的方法，而且一邊聚類，一邊還把缺失的信息估計了：

  • Ning, Xia, and George Karypis. "Slim: Sparse linear methods for top-n recommender systems."2011 IEEE 11th International Conference on Data Mining. IEEE, 2011.

最後，方法千千萬，空口談演算法沒前途，誰用聚類做了實事兒，誰纔是勝利者。


推薦閱讀：
相關文章