導(dǎo)語(yǔ)
根據(jù)距離或相似度對(duì)數(shù)據(jù)點(diǎn)聚類，是研究諸多自然和社會(huì)問(wèn)題的有力工具。而在各種聚類算法中，分層聚類具有特別的優(yōu)勢(shì)。近日，電子科技大學(xué)周濤教授領(lǐng)銜的研究組，在 Information Sciences 雜志發(fā)表論文，提出一種新的層次聚類算法。該算法在多領(lǐng)域的數(shù)據(jù)集中展示出超越同類算法的強(qiáng)大能力，在網(wǎng)絡(luò)社團(tuán)檢測(cè)問(wèn)題上具有廣泛應(yīng)用前景。
論文題目：
Hierarchical clustering supported by reciprocal nearest neighbors
論文地址：
https://www.sciencedirect.com/science/article/pii/S0020025520303157
圖1：層次聚類算法結(jié)果的示意圖
傳統(tǒng)的聚類算法有很多常見的缺陷，例如需要預(yù)先指定聚類的數(shù)目（提前知道要聚成幾類），又如雖然有了聚類的結(jié)果，但是這些類別之間的關(guān)系并不明朗。層次聚類算法天然地可以克服這些缺陷。層次聚類算法在最高層面把所有數(shù)據(jù)點(diǎn)看成一個(gè)大類，然后從這個(gè)大類中分出幾個(gè)一級(jí)子類，每個(gè)一級(jí)子類又再分裂出若干二級(jí)子類，以此類推。我們不需要提前知道要聚成幾類，而且不同子類與子類之間的組織結(jié)構(gòu)非常清晰。圖1是一個(gè)典型的層次聚類算法的結(jié)果，從上到下可以自動(dòng)得到不同分辨率的聚類結(jié)果，且數(shù)據(jù)點(diǎn)之間的遠(yuǎn)近親疏關(guān)系都非常清晰。在網(wǎng)絡(luò)社團(tuán)挖掘中著名的 Girvan-Newman 算法[4]就是典型的層次聚類算法，這類算法可以得到不同尺度的網(wǎng)絡(luò)組織方式。當(dāng)然，層次聚類算法也有很多缺陷，譬如計(jì)算復(fù)雜度往往較長(zhǎng)，受噪音點(diǎn)的影響較大，等等。
假設(shè)每一個(gè)數(shù)據(jù)點(diǎn)都喜歡距離自己最近的那個(gè)數(shù)據(jù)點(diǎn)。如果我們從一個(gè)數(shù)據(jù)點(diǎn) A 出發(fā)，依次追逐它喜歡的對(duì)象。善良的愿望讓我們期望 A 喜歡 B，B 也喜歡 A，但事實(shí)往往并非如此，很多時(shí)候類似于 A->B->C->D->E 這樣很快遠(yuǎn)離 A，有時(shí)候會(huì)形成復(fù)雜難纏的關(guān)系，例如 A->B->C->D->A，甚至是 A->B->C->A。如果非常幸運(yùn)，存在某對(duì)數(shù)據(jù)點(diǎn) A、B，滿足 A 喜歡 B，B 也喜歡 A，我們就認(rèn)為這是一對(duì)鴛鴦節(jié)點(diǎn)（更正式的說(shuō)法是“互為最近鄰”）。
我們提出了一種新的層次聚類算法，其核心假設(shè)只有一個(gè)，非常善良，就是“棒不打鴛鴦”互為最近鄰的數(shù)據(jù)點(diǎn)對(duì)應(yīng)該處于同一個(gè)類別中。
圖2：構(gòu)建聚類子樹的過(guò)程示意圖
給定了若干數(shù)據(jù)點(diǎn)且定義好距離，我們首先要做的是構(gòu)建聚類子樹。初始的時(shí)候荒蕪無(wú)樹，所有數(shù)據(jù)點(diǎn)都是自由的。這個(gè)時(shí)候我們從隨機(jī)選定的一個(gè)自由數(shù)據(jù)點(diǎn) A1 出發(fā)，找到它喜歡的數(shù)據(jù)點(diǎn) A2，然后再找 A2 喜歡的數(shù)據(jù)點(diǎn) A3……依次類推，形成一個(gè)序列 A1，A2，A3，A4，……。如果存在某個(gè)Ai=Ai-2（意味這Ai-2和Ai-1是一對(duì)鴛鴦），那么就可以停下來(lái)了，這個(gè)時(shí)候A1到Ai-1構(gòu)成了一個(gè)聚類子樹，Ai-2 和 Ai-1 被定義為這個(gè)聚類子樹的一對(duì)支撐節(jié)點(diǎn)。我們?cè)偌右粋�(gè)虛擬的根節(jié)點(diǎn)，它的位置是 Ai-2 和 Ai-1 的“中點(diǎn)”，且同時(shí)和 Ai-2 與 Ai-1 相連，就是這個(gè)聚類子樹的代表點(diǎn)。如果序列A1，A2，A3，A4，……在遇到鴛鴦節(jié)點(diǎn)之前就碰到了非自由節(jié)點(diǎn)（已經(jīng)屬于某個(gè)聚類子樹的節(jié)點(diǎn)），例如 A4 可能屬于另外的子樹，則 A1，A2，A3 自動(dòng)依附到這個(gè)已經(jīng)存在的子樹上。如果構(gòu)成的聚類子樹“又瘦又高”，我們會(huì)進(jìn)行剪枝，形成一些孤立節(jié)點(diǎn)組成的特殊的聚類子樹，它們的代表點(diǎn)就是自己（操作細(xì)節(jié)請(qǐng)參考原文[5]）。
圖3：迭代過(guò)程示意圖
如圖3所示，在確定了聚類子樹后，我們用這些聚類子樹的代表點(diǎn)作為新的數(shù)據(jù)點(diǎn)，然后可以把剛才的方法繼續(xù)用于這些新數(shù)據(jù)點(diǎn)基于新數(shù)據(jù)點(diǎn)對(duì)之間的距離，我們又可以使用“棒不打鴛鴦”的算法。這樣通過(guò)迭代的方式，我們就可以獲得整個(gè)層次聚類的結(jié)果。如果數(shù)據(jù)點(diǎn)所在的距離空間不是歐幾里得空間，我們沒有辦法定義所謂“中點(diǎn)”的位置（譬如某維特征是顏色，距離是海明距離，則我們很難定義綠色和粉色的中點(diǎn)），這個(gè)時(shí)候我們也可以直接計(jì)算“中點(diǎn)”與“中點(diǎn)”之間的距離（具體推導(dǎo)請(qǐng)參考[5]），從而不影響整個(gè)算法的實(shí)現(xiàn)。
如果有 n 個(gè)數(shù)據(jù)點(diǎn)，利用 K-D Tree[6]可以在 O(nlogn) 時(shí)間找到所有最近鄰，進(jìn)而可以證明，在最壞的情況下，本算法的時(shí)間復(fù)雜度也不超過(guò) O(nlogn)，簡(jiǎn)要推導(dǎo)如下：
我們基于兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集，UCI Database 和 Olivetti face data set，測(cè)試了我們的算法效果，并和四種有代表的算法，GA[7]、CURE[8]、AP[9] 和 DD[10]，進(jìn)行了比較。結(jié)果顯示，我們提出的基于“棒不打鴛鴦”的算法，不僅聚類效果遠(yuǎn)遠(yuǎn)顯著好于其他算法，而且 CPU 時(shí)間也是最短的。
圖4：本算法與 Girvan-Newman 算法在社團(tuán)挖掘任務(wù)上的比較
我們還選擇了若干被充分研究過(guò)且有社團(tuán)結(jié)構(gòu)“標(biāo)準(zhǔn)答案”的網(wǎng)絡(luò)，并對(duì)比了本算法和 Girvan-Newman 算法在社團(tuán)挖掘方面的效果。如圖4所示，橫坐標(biāo)是劃分的社團(tuán)數(shù)目，藍(lán)色陰影部分就是本算法效果好于 Girvan-Newman 算法的情況，黃色陰影部分就是 Girvan-Newman 算法好于本算法的情況�？梢钥吹�，在絕大多數(shù)情況下本算法是占優(yōu)的。
如何定義網(wǎng)絡(luò)上節(jié)點(diǎn)之間的距離[11]，以及評(píng)估聚類效果（Rand Index [12]）和社團(tuán)挖掘效果（Triangle Participation Ratio[13]）的參數(shù)的具體含義，可以參考原文[5]。
圖5：推薦給大家茶余飯后消遣的科普書
對(duì)于現(xiàn)在做大數(shù)據(jù)和人工智能研究的學(xué)生、學(xué)者和業(yè)界人員而言，更時(shí)髦的是特征工程和深度學(xué)習(xí)，數(shù)據(jù)挖掘單算法的研究已經(jīng)沒有那么性感了。但是我個(gè)人特別喜歡這個(gè)工作不僅僅是因?yàn)檫@個(gè)算法既快又好，更主要是因?yàn)檫@個(gè)算法背后有簡(jiǎn)單優(yōu)美的假設(shè)：“兩個(gè)互為最近鄰的數(shù)據(jù)點(diǎn)（節(jié)點(diǎn)）應(yīng)該被分到一個(gè)類別中”。畢竟，作為被好奇心驅(qū)動(dòng)的人類，站在黑匣子外面瞻仰它神奇效果的快樂，終歸比不上拆解零件洞悉機(jī)制的快感。也借此機(jī)會(huì)推薦我和兩位同學(xué)最近新寫的數(shù)據(jù)挖掘簡(jiǎn)明教材（基本上是科普級(jí)別的）[1]，里面是數(shù)據(jù)挖掘最優(yōu)美算法的集萃，希望大家喜歡。
參考文獻(xiàn)：
[1] 周濤，袁飛，莊旭，《最簡(jiǎn)數(shù)據(jù)挖掘》(電子工業(yè)出版社，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.
（參考文獻(xiàn)可上下滑動(dòng)）
作者：周濤
編輯：張爽
