導語
根據距離或相似度對數據點聚類，是研究諸多自然和社會問題的有力工具。而在各種聚類算法中，分層聚類具有特別的優勢。近日，電子科技大學周濤教授領銜的研究組，在 Information Sciences 雜志發表論文，提出一種新的層次聚類算法。該算法在多領域的數據集中展示出超越同類算法的強大能力，在網絡社團檢測問題上具有廣泛應用前景。
論文題目：
Hierarchical clustering supported by reciprocal nearest neighbors
論文地址：
https://www.sciencedirect.com/science/article/pii/S0020025520303157
圖1：層次聚類算法結果的示意圖
傳統的聚類算法有很多常見的缺陷，例如需要預先指定聚類的數目（提前知道要聚成幾類），又如雖然有了聚類的結果，但是這些類別之間的關系并不明朗。層次聚類算法天然地可以克服這些缺陷。層次聚類算法在最高層面把所有數據點看成一個大類，然后從這個大類中分出幾個一級子類，每個一級子類又再分裂出若干二級子類，以此類推。我們不需要提前知道要聚成幾類，而且不同子類與子類之間的組織結構非常清晰。圖1是一個典型的層次聚類算法的結果，從上到下可以自動得到不同分辨率的聚類結果，且數據點之間的遠近親疏關系都非常清晰。在網絡社團挖掘中著名的 Girvan-Newman 算法[4]就是典型的層次聚類算法，這類算法可以得到不同尺度的網絡組織方式。當然，層次聚類算法也有很多缺陷，譬如計算復雜度往往較長，受噪音點的影響較大，等等。
假設每一個數據點都喜歡距離自己最近的那個數據點。如果我們從一個數據點 A 出發，依次追逐它喜歡的對象。善良的愿望讓我們期望 A 喜歡 B，B 也喜歡 A，但事實往往并非如此，很多時候類似于 A->B->C->D->E 這樣很快遠離 A，有時候會形成復雜難纏的關系，例如 A->B->C->D->A，甚至是 A->B->C->A。如果非常幸運，存在某對數據點 A、B，滿足 A 喜歡 B，B 也喜歡 A，我們就認為這是一對鴛鴦節點（更正式的說法是“互為最近鄰”）。
我們提出了一種新的層次聚類算法，其核心假設只有一個，非常善良，就是“棒不打鴛鴦”互為最近鄰的數據點對應該處于同一個類別中。
圖2：構建聚類子樹的過程示意圖
給定了若干數據點且定義好距離，我們首先要做的是構建聚類子樹。初始的時候荒蕪無樹，所有數據點都是自由的。這個時候我們從隨機選定的一個自由數據點 A1 出發，找到它喜歡的數據點 A2，然后再找 A2 喜歡的數據點 A3……依次類推，形成一個序列 A1，A2，A3，A4，……。如果存在某個Ai=Ai-2（意味這Ai-2和Ai-1是一對鴛鴦），那么就可以停下來了，這個時候A1到Ai-1構成了一個聚類子樹，Ai-2 和 Ai-1 被定義為這個聚類子樹的一對支撐節點。我們再加一個虛擬的根節點，它的位置是 Ai-2 和 Ai-1 的“中點”，且同時和 Ai-2 與 Ai-1 相連，就是這個聚類子樹的代表點。如果序列A1，A2，A3，A4，……在遇到鴛鴦節點之前就碰到了非自由節點（已經屬于某個聚類子樹的節點），例如 A4 可能屬于另外的子樹，則 A1，A2，A3 自動依附到這個已經存在的子樹上。如果構成的聚類子樹“又瘦又高”，我們會進行剪枝，形成一些孤立節點組成的特殊的聚類子樹，它們的代表點就是自己（操作細節請參考原文[5]）。
圖3：迭代過程示意圖
如圖3所示，在確定了聚類子樹后，我們用這些聚類子樹的代表點作為新的數據點，然后可以把剛才的方法繼續用于這些新數據點基于新數據點對之間的距離，我們又可以使用“棒不打鴛鴦”的算法。這樣通過迭代的方式，我們就可以獲得整個層次聚類的結果。如果數據點所在的距離空間不是歐幾里得空間，我們沒有辦法定義所謂“中點”的位置（譬如某維特征是顏色，距離是海明距離，則我們很難定義綠色和粉色的中點），這個時候我們也可以直接計算“中點”與“中點”之間的距離（具體推導請參考[5]），從而不影響整個算法的實現。
如果有 n 個數據點，利用 K-D Tree[6]可以在 O(nlogn) 時間找到所有最近鄰，進而可以證明，在最壞的情況下，本算法的時間復雜度也不超過 O(nlogn)，簡要推導如下：
我們基于兩個標準數據集，UCI Database 和 Olivetti face data set，測試了我們的算法效果，并和四種有代表的算法，GA[7]、CURE[8]、AP[9] 和 DD[10]，進行了比較。結果顯示，我們提出的基于“棒不打鴛鴦”的算法，不僅聚類效果遠遠顯著好于其他算法，而且 CPU 時間也是最短的。
圖4：本算法與 Girvan-Newman 算法在社團挖掘任務上的比較
我們還選擇了若干被充分研究過且有社團結構“標準答案”的網絡，并對比了本算法和 Girvan-Newman 算法在社團挖掘方面的效果。如圖4所示，橫坐標是劃分的社團數目，藍色陰影部分就是本算法效果好于 Girvan-Newman 算法的情況，黃色陰影部分就是 Girvan-Newman 算法好于本算法的情況�？梢钥吹�，在絕大多數情況下本算法是占優的。
如何定義網絡上節點之間的距離[11]，以及評估聚類效果（Rand Index [12]）和社團挖掘效果（Triangle Participation Ratio[13]）的參數的具體含義，可以參考原文[5]。
圖5：推薦給大家茶余飯后消遣的科普書
對于現在做大數據和人工智能研究的學生、學者和業界人員而言，更時髦的是特征工程和深度學習，數據挖掘單算法的研究已經沒有那么性感了。但是我個人特別喜歡這個工作不僅僅是因為這個算法既快又好，更主要是因為這個算法背后有簡單優美的假設：“兩個互為最近鄰的數據點（節點）應該被分到一個類別中”。畢竟，作為被好奇心驅動的人類，站在黑匣子外面瞻仰它神奇效果的快樂，終歸比不上拆解零件洞悉機制的快感。也借此機會推薦我和兩位同學最近新寫的數據挖掘簡明教材（基本上是科普級別的）[1]，里面是數據挖掘最優美算法的集萃，希望大家喜歡。
參考文獻：
[1] 周濤，袁飛，莊旭，《最簡數據挖掘》(電子工業出版社，2020).
[2] P. N. Tan, M. Steinbach, A. Karpatne, V. Kumar, Introduction to Data Mining - Chapter 7 (Pearson, 2018).
[3] A. K. Jain, Dataclustering: 50years beyond k-means, Pattern Recognit. Lett. 31 (2010) 651666.
[4] M. Girvan, M. E. J. Newman, Community structure in social and biological networks, PNAS 99 (2002) 78217826.
[5] Y.-B. Xie, Y.-L. Lee, C. Wang, D.-B. Chen, T. Zhou, Hierarchical clustering supported by reciprocal nearest neighbors, Information Science 527 (2020) 279-292.
[6] J. L. Bentley, Multidimensional binary search trees used for associative searching, Commun. ACM 18 (1975) 509517.
[7] J. H. Ward Jr., Hierarchical grouping to optimize an objective function, J. Am. Stat. Assoc. 58 (1963) 236244.
[8] S. Guha, R. Rastogi, K. Shim, Cure: anefficient clustering algorithm for large database, Inf. Syst. 26 (2001) 3558.
[9] B. J. Frey, D. Dueck, Clustering bypassing messages between data points, Science 315 (2007) 972976.
[10] A. Rodrigue, A. Laio, Clustering by fast search and find of density peaks, Science 344 (2014) 14921496.
[11] F. Fouss, A. Pirotte, J. M. Renders, M. Saerens, Randomwalk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Trans. Knowl. Data Eng. 19 (2007) 355369.
[12] W. M. Rand, Objective criteria for the evaluation of clustering methods, J. Am. Stat. Assoc. 66 (1971) 846850.
[13] J. Yang, J. Leskovec, Defining and evaluating network communities based on ground-truth, Knowl. Inf. Syst. 42 (2015) 181213.
（參考文獻可上下滑動）
作者：周濤
編輯：張爽
