摘要—找到合適的密度函數(shù)對(duì)于基于密度的聚類(lèi)算法（如 DBSCAN 和 DPC）至關(guān)重要北苟。這些算法中通常使用與單位 d 維歐幾里得球的指示函數(shù)相對(duì)應(yīng)的樸素密度闷袒。這種密度會(huì)因在復(fù)雜數(shù)據(jù)集中捕獲局部特征而受到影響。為了解決這個(gè)問(wèn)題，我們提出了一種新的核擴(kuò)散密度函數(shù)，它可以適應(yīng)不同的局部分布特征和平滑度的數(shù)據(jù)。此外让歼，我們開(kāi)發(fā)了一個(gè)可以在線性時(shí)間和空間中有效計(jì)算的代理項(xiàng)，并證明它與核擴(kuò)散密度函數(shù)漸近等效丽啡。在基準(zhǔn)和大規(guī)模人臉圖像數(shù)據(jù)集上進(jìn)行的大量經(jīng)驗(yàn)實(shí)驗(yàn)表明谋右，所提出的方法不僅比經(jīng)典的基于密度的聚類(lèi)算法有了顯著改進(jìn)，而且大大優(yōu)于最先進(jìn)的人臉聚類(lèi)方法碌上。

1 簡(jiǎn)介

基于密度的聚類(lèi)算法現(xiàn)在廣泛用于各種應(yīng)用倚评，包括高能物理（Tramacere & Vecchio，2012馏予；Rovere 等天梧，2020）、材料科學(xué)（Marquis 等霞丧，2019呢岗；Reza 等， 2007)蛹尝、社交網(wǎng)絡(luò)分析 (Shi et al., 2014; Khatoon & Banu, 2019) 到分子生物學(xué) (Cao et al., 2017; Ziegler et al., 2020)后豫。在這些算法中，數(shù)據(jù)點(diǎn)被劃分為集群突那，這些集群被認(rèn)為是相對(duì)于潛在概率密度或類(lèi)似參考函數(shù)而言足夠高或局部高密度的區(qū)域挫酿。我們?cè)谡撐闹卸挤Q(chēng)它們?yōu)槊芏群瘮?shù)。這些技術(shù)對(duì)從業(yè)者很有吸引力愕难，因?yàn)樗鼈兊姆菂?shù)特征可以靈活地發(fā)現(xiàn)具有任意形狀的集群早龟，而經(jīng)典方法如 k-means 和 k-medoids (Friedman et al., 2001) 只能檢測(cè)凸（例如惫霸，球形）簇。在基于密度的聚類(lèi)方面的開(kāi)創(chuàng)性工作包括 DBSCAN (Ester et al., 1996) 和 DPC (Rodriguez & Laio, 2014)葱弟，以及許多其他 (Ankerst et al., 1999; Cuevas et al., 2001; Comaniciu & Meer壹店，2002；Hinneburg 和 Gabriel芝加，2007硅卢；Stuetzle，2003）藏杖。

大多數(shù)基于密度的聚類(lèi)算法隱含地識(shí)別聚類(lèi)中心将塑，并通過(guò)與附近較高密度點(diǎn)的連接將剩余點(diǎn)分配給聚類(lèi)。要繼續(xù)使用這些方法制市，它需要一個(gè)密度函數(shù)抬旺，它通常是對(duì)潛在真實(shí)概率密度或其某些變體的估計(jì)弊予。例如祥楣，一個(gè)流行的選擇是樸素密度函數(shù)，它通過(guò)簡(jiǎn)單地計(jì)算每個(gè) x 的 ε-鄰域中覆蓋的數(shù)據(jù)點(diǎn)的數(shù)量來(lái)執(zhí)行汉柒。請(qǐng)注意误褪，這樣的密度不適用于不同的分布區(qū)域些膨。具有挑戰(zhàn)性的場(chǎng)景之一是數(shù)據(jù)中的集群具有不同的局部特征睬涧，例如大小抚吠、高度缤剧、分布和平滑度泪掀。因此负懦，得到的密度函數(shù)傾向于使數(shù)據(jù)分布中的波峰和波谷變平陪捷，從而導(dǎo)致對(duì)聚類(lèi)數(shù)量的低估（見(jiàn)圖 1）踩窖。已經(jīng)提出了 DBSCAN 和 DPC 的許多啟發(fā)式變體來(lái)放大局部特征乓诽，從而使聚類(lèi)任務(wù)更容易（Campello et al., 2013; Chen et al., 2018; Ert?z et al., 2003; Zhu et al., 2016 ）帜羊。這些方法中的大多數(shù)可以被視為對(duì)樸素密度函數(shù)的某些變換執(zhí)行聚類(lèi)。但是鸠天，如果樸素密度函數(shù)本身首先存在很大問(wèn)題讼育，那么這些方法將變得不那么有效。

此外稠集，即使我們應(yīng)用自適應(yīng)替代方法來(lái)修改經(jīng)典密度函數(shù)奶段，通常使用的線性核密度估計(jì)器 (KDE) 也存在其他有爭(zhēng)議的問(wèn)題。它經(jīng)常遭受?chē)?yán)重的邊界偏差（Marron & Ruppert, 1994）剥纷，并且被認(rèn)為計(jì)算成本很高痹籍。這些現(xiàn)象阻礙了經(jīng)典密度函數(shù)的實(shí)用性和可靠性，特別是對(duì)于大規(guī)模和復(fù)雜的聚類(lèi)任務(wù)晦鞋。

為了克服基于密度的聚類(lèi)算法中的這些問(wèn)題蹲缠，在本文中刺洒，我們提出了一種通用方法來(lái)構(gòu)建所謂的核擴(kuò)散密度函數(shù)來(lái)代替經(jīng)典的密度函數(shù)。關(guān)鍵思想是從具有所需局部自適應(yīng)特性的用戶(hù)指定的二元核構(gòu)建密度吼砂。我們沒(méi)有使用樸素密度函數(shù)及其變體逆航，而是利用二元核來(lái)推導(dǎo)轉(zhuǎn)移概率。這種轉(zhuǎn)移概率引發(fā)了擴(kuò)散過(guò)程渔肩，該轉(zhuǎn)移概率允許有限且平穩(wěn)的分布因俐。這種限制分布可作為一種似是而非的密度函數(shù)，用于減少誤差的聚類(lèi)周偎。

為了克服基于密度的聚類(lèi)算法中的這些問(wèn)題抹剩，在本文中，我們提出了一種通用方法來(lái)構(gòu)建所謂的核擴(kuò)散密度函數(shù)來(lái)代替經(jīng)典的密度函數(shù)蓉坎。關(guān)鍵思想是從具有所需局部自適應(yīng)特性的用戶(hù)指定的二元核構(gòu)建密度澳眷。我們沒(méi)有使用樸素密度函數(shù)及其變體，而是利用二元核來(lái)推導(dǎo)轉(zhuǎn)移概率蛉艾。這種轉(zhuǎn)移概率引發(fā)了擴(kuò)散過(guò)程钳踊，該轉(zhuǎn)移概率允許有限且平穩(wěn)的分布。這種限制分布可作為一種似是而非的密度函數(shù)勿侯，用于減少誤差的聚類(lèi)拓瞪。

在這個(gè)框架下，我們提供了對(duì)稱(chēng)和非對(duì)稱(chēng)二元核的例子來(lái)構(gòu)建核擴(kuò)散密度函數(shù)助琐，它可以解決聚類(lèi)復(fù)雜和局部變化的數(shù)據(jù)祭埂。我們將由此產(chǎn)生的適應(yīng) DBSCAN 和 DPC 算法應(yīng)用于廣泛不同的經(jīng)驗(yàn)數(shù)據(jù)集，并在這些分析中顯示出顯著的改進(jìn)兵钮。本文的主要貢獻(xiàn)總結(jié)如下：

? 我們引入新的二元核函數(shù)并構(gòu)建相關(guān)的核擴(kuò)散過(guò)程蛆橡。基于擴(kuò)散過(guò)程掘譬，我們提出了一種核擴(kuò)散密度函數(shù)來(lái)適應(yīng)基于密度的聚類(lèi)算法泰演，如 DBSACN 和 DPC，在存在不同局部特征的情況下達(dá)到準(zhǔn)確性屁药。

? 我們推導(dǎo)出一個(gè)計(jì)算效率更高的替代物粥血，并通過(guò)分析表明它與所提出的核擴(kuò)散密度函數(shù)是漸近等效的。

? 通過(guò)大量實(shí)驗(yàn)酿箭，我們證明了核擴(kuò)散密度函數(shù)在應(yīng)用于 DBSCAN 和 DPC 時(shí)優(yōu)于樸素密度函數(shù)及其變體复亏，并表明它在人臉聚類(lèi)任務(wù)上優(yōu)于最先進(jìn)的基于 GCN 的方法。

2 相關(guān)工作

基于密度的聚類(lèi) 有大量關(guān)于采用基于密度的聚類(lèi)算法來(lái)解決數(shù)據(jù)中不同聚類(lèi)的巨大變化的文獻(xiàn)缭嫡。 DPC 本身就是 DBSCAN 的一種改進(jìn)缔御，因?yàn)樗粌H通過(guò)最高密度值確定聚類(lèi)中心，而且還考慮到它們之間的距離妇蛀，因此在復(fù)雜的聚類(lèi)任務(wù)中通常具有更好的性能耕突。其他嘗試包括重新調(diào)整數(shù)據(jù)以具有相對(duì)參考度量而不是 KDE (Zhu et al., 2016; Chen et al., 2018)笤成，以及使用兩點(diǎn)之間的共享最近鄰數(shù)來(lái)代替幾何距離 (Ert?z等人，2003）眷茁。

擴(kuò)散圖擴(kuò)散圖技術(shù)（Coifman et al., 2005; Coifman & Lafon, 2006）根據(jù)數(shù)據(jù)的基本幾何結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行多尺度組織炕泳。它使用局部相似性度量來(lái)創(chuàng)建數(shù)據(jù)的擴(kuò)散過(guò)程，該過(guò)程沿時(shí)間 t 整合不同尺度的局部幾何上祈。一般來(lái)說(shuō)培遵，diffusion會(huì)將數(shù)據(jù)分割成小t中的幾個(gè)較小的簇，并將數(shù)據(jù)分組為大t的一個(gè)簇登刺。在精心選擇的時(shí)間 t 應(yīng)用特征函數(shù)會(huì)導(dǎo)致數(shù)據(jù)的良好宏觀表示籽腕，這在降維和譜聚類(lèi)中很有用（Nadler 等人，2005 年）纸俭。

人臉聚類(lèi)人臉聚類(lèi)作為機(jī)器學(xué)習(xí)中的一個(gè)重要應(yīng)用已經(jīng)被廣泛研究皇耗。傳統(tǒng)算法包括 k-means、層次聚類(lèi) (Sibson, 1973) 和 ARO (Otto et al., 2017)揍很。最近的許多工作都利用了監(jiān)督信息和 GCN 模型郎楼，與傳統(tǒng)算法相比取得了令人矚目的改進(jìn)。僅舉幾例女轿，CDP (Zhan et al., 2018) 提出聚合不同模型提取的特征箭启； L-GCN (Wang et al., 2019) 預(yù)測(cè)實(shí)例樞軸子圖中的鏈接； LTC (Yang et al., 2019) 生成一系列子圖作為提議蛉迹，并在其上檢測(cè)人臉簇；和 GCN(V+E) (Yang et al., 2020) 通過(guò) GCN 學(xué)習(xí)置信度和連通性放妈。在本文中北救，我們證明了所提出的具有核擴(kuò)散的基于密度的聚類(lèi)算法，作為一種通用的聚類(lèi)方法芜抒，甚至優(yōu)于專(zhuān)門(mén)為人臉聚類(lèi)設(shè)計(jì)的這些最先進(jìn)的方法珍策。

3 預(yù)備知識(shí) 3.1 符號(hào)

讓數(shù)據(jù)集 D = {x1, . . . , xn} ? Rd 是從分布測(cè)量 F 中抽取的 n i.i.d 個(gè)樣本，在 Rd 上具有密度 f宅倒。令 Fn 表示相對(duì)于 D 測(cè)量的相應(yīng)經(jīng)驗(yàn)分布攘宙，

即，F(xiàn)n(A) = 1 ??n 1A(xi)拐迁，其中 1A(·) 表示集合 A 的指示函數(shù)蹭劈。我們寫(xiě)為 ||u||當(dāng) n i=1 時(shí)，向量 u 的歐幾里得范數(shù)线召。令 B(x, ε) 和 Vd 分別表示以 x 為中心的 d 維 ε 球和單位球 B(0, 1) 的體積铺韧。令 Nk(x) 表示數(shù)據(jù)集 D 中點(diǎn) x 的 k 最近鄰的集合。

3.2 密度函數(shù)

基于密度的算法通過(guò)在由 ρ 表示的密度函數(shù)中指定和分割高值區(qū)域來(lái)執(zhí)行聚類(lèi)缓淹。通常哈打，我們計(jì)算每個(gè) ρ(xi)塔逃，然后識(shí)別具有（局部）最高值的聚類(lèi)中心。許多流行的算法料仗，如 DBSCAN 和 DPC湾盗，采用以下樸素密度函數(shù)：

樸素密度函數(shù) ρnaive 實(shí)際上是對(duì)精心選擇的 ε 的 f 的經(jīng)驗(yàn)估計(jì)。很容易觀察到立轧，為了聚類(lèi)的目的淹仑，我們只關(guān)心 ρnaive(x) 直到一個(gè)歸一化常數(shù)，這使得它簡(jiǎn)單地等同于計(jì)算 ε-ball 中圍繞 x 的數(shù)據(jù)點(diǎn)的總數(shù)肺孵。

在實(shí)踐中匀借，數(shù)據(jù)分布可能非常復(fù)雜，并且包含難以檢測(cè)的各種局部特征平窘。對(duì)于所有 x 具有相同半徑 ε 的 (1) 中的樸素密度通常遭受不令人滿(mǎn)意的經(jīng)驗(yàn)性能吓肋，例如，無(wú)法識(shí)別具有較少數(shù)據(jù)點(diǎn)的小集群瑰艘。緩解此問(wèn)題的一種可能方法是通過(guò)轉(zhuǎn)換為以下局部對(duì)比度 (LC) 函數(shù) (Chen et al., 2018)：

通過(guò)這種方式是鬼，ρLC 將每個(gè)數(shù)據(jù)點(diǎn)的密度與其 k 近鄰進(jìn)行比較。為了看到 LC 的好處紫新，讓我們將 x 視為一個(gè)聚類(lèi)中心均蜜。經(jīng)過(guò)局部對(duì)比后，無(wú)論該簇的大小如何芒率，ρLC(x) 都可能達(dá)到 k 的值囤耳。

然而，像 ρLC 這樣的密度函數(shù)仍然高度依賴(lài)于 ρnaive 的基礎(chǔ)性能偶芍。這限制了它們?cè)诰哂刑魬?zhàn)性的局部特征的聚類(lèi)數(shù)據(jù)中的應(yīng)用充择。

4 方法論

在本節(jié)中，我們提出了一種基于核擴(kuò)散密度函數(shù)概念的新型基于密度的聚類(lèi)算法匪蟀。為此椎麦，我們將引入一個(gè)核擴(kuò)散密度函數(shù)，它考慮了局部適應(yīng)性材彪，非常適合聚類(lèi)目的观挎。我們提供了有關(guān)如何從由二元核引起的擴(kuò)散過(guò)程中導(dǎo)出此密度函數(shù)的詳細(xì)信息。我們還提供了一個(gè)計(jì)算效率更高的代理密度函數(shù)段化。

4.1 擴(kuò)散過(guò)程和核擴(kuò)散密度 考慮二元核函數(shù) k : D × D → R+嘁捷，這樣：

? k(x, y) 是半正定的，即 k(x, y) ≥ 0穗泵。

? k(x, y) 是關(guān)于 x 和 y 的 Fn 可積的普气。

我們將 d(x) = n ?? k(x, y)dFn(y) 定義為 x 處體積的局部度量并定義

容易看出 p(x, y) 滿(mǎn)足守恒性質(zhì) n ??

p(x, y) 可以看作是在數(shù)據(jù)集上從點(diǎn) x 到點(diǎn) y 的隨機(jī)游走的概率，它在 D 上誘導(dǎo)出一條具有 n × n 轉(zhuǎn)移矩陣 P = [p(x, y)] 的馬爾可夫鏈佃延。這種技術(shù)在各種應(yīng)用中都是標(biāo)準(zhǔn)的现诀，稱(chēng)為歸一化圖拉普拉斯構(gòu)造夷磕。例如，我們可以將 D 視為一個(gè)圖仔沿，將 L = I - P 視為歸一化圖拉普拉斯算子坐桩，將 d(x) 視為歸一化因子。

對(duì)于 t ≥ 0封锉，在 t 個(gè)時(shí)間步長(zhǎng)內(nèi)從 x 過(guò)渡到 y 的概率由 Pt 給出绵跷，即 P 的 t 次方。及時(shí)向前運(yùn)行馬爾可夫鏈成福，我們觀察不同尺度的數(shù)據(jù)集碾局，即擴(kuò)散在 D 上處理 Xt。設(shè) ρ(x, t): D × R+ → R+ 為相關(guān)概率密度奴艾，由以下具有初始條件的二階微分方程控制：

其中 φ0(x) 是時(shí)間 t = 0 時(shí)的概率密度净当。在實(shí)踐中，我們可以使用任何有效的 φ0(x) 選擇蕴潦，

例如密度均勻像啼。

為了給出擴(kuò)散過(guò)程的一個(gè)明確的例子，考慮一個(gè) k 的子類(lèi)潭苞，即各向同性核忽冻，其中 k(x, y) = K(||x ? y||2/h) 對(duì)于某個(gè)函數(shù) K : R → R+。在這里此疹，我們可以將 h 雙重解釋為推斷局部信息的尺度參數(shù)和隨機(jī)游走跳躍的時(shí)間步長(zhǎng) h = Δt僧诚。然后我們可以將 forward Chapman-KolmogorovoperatorTF 定義為

注意，TF 是時(shí)間 t=h 時(shí)的數(shù)據(jù)分布秀菱，因此可以看作是左乘轉(zhuǎn)移矩陣 P 的連續(xù)模擬振诬。令 h → 0，隨機(jī)游走收斂到一個(gè)連續(xù)擴(kuò)散過(guò)程衍菱，概率密度在 t 中連續(xù)演化。在這種情況下肩豁，我們可以將（4）中的二階微分方程明確寫(xiě)為：

? ρ(x,t) = lim ρ^(x,t+h)?ρ(x,t) = lim TF ?Iρ(x,t), (5) ?th h→0 h h→0 h

其中 Lh = limh→0 (TF ? I)/h 是該過(guò)程的常規(guī)無(wú)窮小生成器〖勾現(xiàn)在我們準(zhǔn)備介紹我們的核擴(kuò)散密度函數(shù)。

定義 1. (核擴(kuò)散密度函數(shù)) 假設(shè) P 誘導(dǎo)的馬爾可夫鏈?zhǔn)潜闅v的清钥，我們將核擴(kuò)散密度函數(shù)定義為擴(kuò)散過(guò)程 Xt 的極限概率密度琼锋，即

ρKD(x)= lim ρ(x,t)。 (6) t→∞

我們提供了一些直覺(jué)祟昭，說(shuō)明為什么 ρKD 作為有效的聚類(lèi)密度函數(shù)缕坎。隨著 t 值的增加，擴(kuò)散過(guò)程 Xt 在增加的尺度上揭示了數(shù)據(jù)分布 F 的幾何結(jié)構(gòu)（例如高密度區(qū)域）篡悟。要看到這一點(diǎn)谜叹，請(qǐng)注意轉(zhuǎn)移概率 P 反映了數(shù)據(jù)點(diǎn)之間的連通性匾寝。我們可以將集群解釋為在轉(zhuǎn)換期間停留在該區(qū)域的概率很高的區(qū)域。由于所涉及的數(shù)據(jù)點(diǎn)密集且高度連接荷腊，因此沿著基礎(chǔ)幾何結(jié)構(gòu)的路徑的概率隨著 t 的增加而增加艳悔。因此，路徑與短而高概率的跳躍一起形成女仰。而不遵循這種結(jié)構(gòu)的路徑會(huì)形成長(zhǎng)而低概率的跳躍猜年，這會(huì)降低路徑的整體概率。

同時(shí)疾忍，為了防止所有數(shù)據(jù)的擴(kuò)散過(guò)程在 t → ∞ 時(shí)將所有數(shù)據(jù)分組到一個(gè)大簇中乔外，我們可以使用某些專(zhuān)注于局部自適應(yīng)性的復(fù)雜形式的 k(x,y)。這將有助于減緩擴(kuò)散并引導(dǎo)過(guò)程逐漸朝著正確的幾何結(jié)構(gòu)方向發(fā)展一罩。因此杨幼，它們?cè)诜糯髱缀谓Y(jié)構(gòu)和識(shí)別局部特征信號(hào)之間取得了平衡。

4.2 本地自適應(yīng)內(nèi)核

為了解決核擴(kuò)散密度函數(shù)的局部適應(yīng)性擒抛，我們提出了以下兩個(gè)二元核推汽。它們都是最常用的經(jīng)典內(nèi)核的非常簡(jiǎn)單的變體。

對(duì)稱(chēng)高斯核：

這里 h 和 k 是超參數(shù)歧沪。請(qǐng)注意歹撒，在這種情況下 k(x, y) 是不對(duì)稱(chēng)的，因?yàn)?y ∈ Nk (x) 并不意味著 x ∈ Nk(y)诊胞。

(7) 和 (8) 中定義的雙變量?jī)?nèi)核分別只是經(jīng)典高斯內(nèi)核和 ε- 鄰域或 k-最近鄰內(nèi)核的組合暖夭。通過(guò)這些簡(jiǎn)單的組合，我們?cè)诰植繀^(qū)域截?cái)喔咚购四旃拢總€(gè)點(diǎn) y 對(duì)構(gòu)建密度函數(shù) ρKD(x) 的貢獻(xiàn)不僅取決于距離 ||y - x||還有關(guān)于 x 周?chē)木植繋缀谓Y(jié)構(gòu)迈着。因此，新內(nèi)核在不同的 x 處具有自適應(yīng)性邪码，這有望導(dǎo)致針對(duì)局部特征的更好的聚類(lèi)性能裕菠。我們注意到非對(duì)稱(chēng)高斯核考慮了每個(gè) x 周?chē)淖兓徲颍虼伺c對(duì)稱(chēng)高斯核相比更具適應(yīng)性闭专。

雖然這里我們只提供了兩個(gè)局部自適應(yīng)內(nèi)核的例子奴潘，但在這個(gè)框架下可以很容易地以類(lèi)似的精神創(chuàng)建其他選項(xiàng)，例如影钉，將高斯內(nèi)核更改為其他內(nèi)核或?qū)?ε-neighbourhood (k-nearest neighbours) 內(nèi)核更改為其他內(nèi)核局部截?cái)嗪瘮?shù)画髓。一旦確定了 k(x, y)，我們就可以推導(dǎo)出相應(yīng)的密度函數(shù) ρKD平委。接下來(lái)奈虾，我們只需要簡(jiǎn)單地應(yīng)用任何基于 ρKD 的密度聚類(lèi)過(guò)程，如 DPC 或 DBSCAN，而不是簡(jiǎn)單的密度函數(shù) ρnaive肉微。

在第 5 節(jié)中匾鸥，我們使用上述兩個(gè)局部自適應(yīng)內(nèi)核評(píng)估了所提出的內(nèi)核擴(kuò)散密度函數(shù)的經(jīng)驗(yàn)性能。它們優(yōu)于現(xiàn)有的基于密度的算法和其他最先進(jìn)的方法浪册。

4.3 快速核擴(kuò)散密度

核擴(kuò)散密度函數(shù) ρKD 可以計(jì)算為由轉(zhuǎn)移矩陣 P 引起的馬爾可夫鏈的平穩(wěn)分布扫腺。在數(shù)值上，我們可以通過(guò)迭代右乘 P 與 ρ(x, t) 直到收斂村象，或者對(duì) P 應(yīng)用 QR 分解來(lái)解決它笆环。這些方法在計(jì)算成本方面很昂貴，尤其是當(dāng)樣本量 n 很大時(shí)厚者。

為了解決這個(gè)問(wèn)題躁劣，我們提出了以下計(jì)算效率更高的 ρKD(x) 替代項(xiàng)。

定義 2. (快速核擴(kuò)散密度函數(shù)) 設(shè) p(y, x) 為從點(diǎn) y 到點(diǎn) x 的轉(zhuǎn)移概率库菲，如等式 (3) 中所定義账忘。我們將快速核擴(kuò)散密度函數(shù)定義為

很簡(jiǎn)單，ρFKD 可以在線性時(shí)間和內(nèi)存空間中獲得熙宇，因?yàn)槲覀冎恍枰?/p>

計(jì)算矩陣 P 的列平均值鳖擒。

在這里，我們表明 ρFKD 不僅計(jì)算效率高烫止，而且適用于檢測(cè)局部特征蒋荚。這可以通過(guò)以下定理 1 來(lái)說(shuō)明」萑洌考慮一個(gè)特殊情況期升，即 k(x,y) = 1B(x,ε)(y)。那么很容易驗(yàn)證

其中 Cd = nεdVd 是歸一化常數(shù)互躬。通過(guò)這種方式播赁，我們?cè)谶@個(gè)特殊示例中建立了 ρFKD 和樸素密度函數(shù) ρnaive 之間的聯(lián)系。

定理 1. 考慮上述特殊情況 k(x, y) = 1B(x,ε)(y)吼渡。此外容为，假設(shè)數(shù)據(jù)集 D = {x1 , ..., xn } 可以分成 m 個(gè)不相交的集群：即 X = D1 ?? ... Dm 并且對(duì)于每個(gè) x ∈ D, B(x, ε)包含與 x 屬于同一簇的數(shù)據(jù)點(diǎn)。將 ρ ?j = 1 ?? ρFKD(x) 表示為簇 j 中的平均密度寺酪。我們有

定理 1 表明舟奠，無(wú)論集群大小和其他局部特征如何，每個(gè)集群中的平均 ρFKD 都是相同的房维。這表明 ρFKD 提高了小簇的密度，這對(duì)于找到小簇的密度峰值至關(guān)重要抬纸。

以前我們聲稱(chēng) ρFKD 是核擴(kuò)散密度 ρKD 的替代物咙俩。接下來(lái)，我們想從漸近的角度揭示這兩個(gè)密度函數(shù)之間的關(guān)系。為了繼續(xù)阿趁，我們需要以下假設(shè)膜蛔。

假設(shè) 1. 存在某個(gè)正常數(shù) c < 1，使得 ρFKD(x) ≤ c 對(duì)于每個(gè) x ∈ D 均成立脖阵。

這是一個(gè)非常溫和的假設(shè)皂股，因?yàn)樗冀K認(rèn)為 ρFKD(x) < 1，并且數(shù)據(jù)集上的 ρFKD(x) 的平均值是 ?? 提出以下定理來(lái)表征 ρFKD 和 ρKD 之間的一致接近性命黔。

ρFKD(x)dFn(x) = 1/n呜呐，隨著 n → ∞ 消失。現(xiàn)在我們準(zhǔn)備好了

定理 2悍募。假設(shè)假設(shè) 1 成立并且由核 k(x,y) 誘導(dǎo)的馬爾可夫鏈?zhǔn)潜闅v的蘑辑。我們有

定理 2 意味著當(dāng) n 足夠大時(shí)，ρFKD 一致地逼近 ρKD坠宴。所以我們?cè)趯?shí)踐中用它來(lái)代替 ρKD 是安全的洋魂。我們?cè)诘?5 節(jié)中的數(shù)值實(shí)驗(yàn)也驗(yàn)證了這一結(jié)果。

在本節(jié)中喜鼓，我們根據(jù) ρnaive 經(jīng)驗(yàn)評(píng)估提出的核擴(kuò)散密度函數(shù)

和 ρLC 在基于密度的聚類(lèi)算法中副砍，并將它們與其他最先進(jìn)的方法進(jìn)行比較。我們將 ρsym 和 ρsym 分別表示為具有對(duì)稱(chēng)高斯核的核擴(kuò)散密度函數(shù)及其快速替代函數(shù)庄岖。類(lèi)似地豁翎，我們將 ρKD 和 ρFKD 分別表示為具有非對(duì)稱(chēng)高斯核的兩個(gè)密度函數(shù)。我們?cè)趶V泛的數(shù)據(jù)集上檢查它們的性能顿锰。聚類(lèi)結(jié)果以 Pairwise F-score (Banerjee et al., 2005) 和 BCubed F-score (Amigó et al., 2009) 衡量谨垃。

參數(shù) ε（球的半徑，在 ρnaive硼控、ρLC刘陶、ρsym 和 ρsym 中使用），k（最近的不對(duì)稱(chēng) asym KD FKD 的數(shù)量ρLC牢撼、ρKD 和 ρFKD 中使用的鄰居）通過(guò)在參數(shù)空間中的合適范圍內(nèi)搜索來(lái)調(diào)整匙隔，并且 h（用于 ρsym、ρsym熏版、ρa(bǔ)sym 和 ρa(bǔ)sym 的高斯核的帶寬）固定為 0.5纷责。

5.1 基準(zhǔn)數(shù)據(jù)集的性能

我們現(xiàn)在討論來(lái)自 UCI 存儲(chǔ)庫(kù)的 13 個(gè)基準(zhǔn)數(shù)據(jù)集（~100 到 5,000 個(gè)數(shù)據(jù)點(diǎn)）的性能。元數(shù)據(jù)總結(jié)在附錄中撼短。

如表 1 所示再膳，就 KD KD 聚類(lèi)精度而言，ρsym 和 ρa(bǔ)sym 均優(yōu)于 ρnaive 和 ρLC曲横。所提出的具有非對(duì)稱(chēng)高斯核的核擴(kuò)散密度函數(shù) ρa(bǔ)sym 在解析上具有更好的局部自適應(yīng)性喂柒，在大多數(shù) KD 數(shù)據(jù)集上取得了最佳結(jié)果不瓶，并且大大優(yōu)于 ρnaive 和 ρLC。值得注意的是灾杰，兩個(gè)快速替代物 ρsym 和 ρa(bǔ)sym 與它們的原始對(duì)應(yīng)物 ρsym 和 asym FKD FKD KD ρKD 取得了可比的結(jié)果蚊丐。在附錄中，對(duì)于應(yīng)用于 DBSCAN 的同一組密度函數(shù)艳吠，觀察到了類(lèi)似的結(jié)果麦备。

5.2 人臉圖像數(shù)據(jù)集的性能

近年來(lái)，根據(jù)潛在身份對(duì)人臉圖像進(jìn)行聚類(lèi)成為一項(xiàng)重要應(yīng)用昭娩。從某種意義上說(shuō)凛篙，人臉圖像數(shù)據(jù)集通常包含數(shù)千個(gè)身份，對(duì)應(yīng)于數(shù)千個(gè)集群题禀，這是一個(gè)挑戰(zhàn)鞋诗。同時(shí)，每個(gè)身份（集群）的圖像數(shù)量也有很大差異迈嘹，對(duì)應(yīng)于集群大小的變化削彬。我們?cè)u(píng)估了該方法在兩個(gè)流行的人臉圖像數(shù)據(jù)集上的性能：emore_200k (Zhan et al., 2018) 和 MS1M (Guo et al., 2016)。

emore_200k秀仲。該數(shù)據(jù)集包含 2,577 個(gè)身份和 200,000 張圖像融痛，遵循 Zhan 等人的協(xié)議。 （2018 年）神僵。結(jié)果總結(jié)在表 2 中雁刷。提出的擴(kuò)散密度函數(shù)應(yīng)用于 DPC，并與 k-means保礼、HAC (Sibson, 1973)沛励、ARO (Otto et al., 2017) 和 CDP (Zhan et al. , 2018)。同樣炮障，我們觀察到提出的密度函數(shù)比 ρnaive 和 ρLC 有了顯著改進(jìn)目派。還值得指出的是，基于密度的聚類(lèi)與提出的核擴(kuò)散密度函數(shù)也大大優(yōu)于 CDP 等最先進(jìn)的方法胁赢。

MS1M企蹭。該數(shù)據(jù)集包含 8,573 個(gè)身份和大約 584,000 張圖像，遵循 Yang 等人的協(xié)議智末。 （2020 年）谅摄。我們?cè)诒?3 中報(bào)告了聚類(lèi)性能的結(jié)果。圖 2 繪制了不同密度函數(shù)（應(yīng)用于 DPC）的精度與召回曲線系馆。在表 3 中送漠，提出的核擴(kuò)散密度函數(shù)優(yōu)于 ρnaive 和 ρLC .請(qǐng)注意，基于 GCN 的方法由蘑，如 L-GCN (Wang et al., 2019)螺男、LTC (Yang et al., 2019) 和 GCN (V+E) (Yang et al., 2020) 通嘲衾澹可以實(shí)現(xiàn)更好的聚類(lèi)由于它們的監(jiān)督性質(zhì)，其性能優(yōu)于無(wú)監(jiān)督方法下隧。然而，令人鼓舞的是谓媒，所提出的核擴(kuò)散方法雖然也是無(wú)監(jiān)督的聚類(lèi)方法淆院，但明顯優(yōu)于基于 GCN 的方法。

5.3 敏感性分析

接下來(lái)句惯，我們檢查所提出的核擴(kuò)散密度函數(shù)對(duì)超參數(shù)的敏感性土辩，并將其與 ρnaive 和 ρLC 進(jìn)行比較。結(jié)果是通過(guò)在 emore_200k 和 MS1M 上進(jìn)行的大量實(shí)驗(yàn)獲得的抢野，如圖 3 所示拷淘。我們可以看到，當(dāng)我們改變 ε 的值時(shí)指孤，ρsym 的聚類(lèi)性能比 ρnaive 和 ρLC 穩(wěn)定得多启涯。雖然 ρa(bǔ)sym 對(duì) KD sym asym KD 參數(shù) k 是穩(wěn)健的，但 ρKD 和 ρKD 對(duì)參數(shù) h 都非常穩(wěn)健恃轩。

5.4 計(jì)算成本

我們?cè)?MS1M 上進(jìn)行了一系列實(shí)驗(yàn)结洼，以證明快速替代 ρFKD 在時(shí)間和空間方面的計(jì)算效率。通過(guò)從 MS1M 收集的不同百分位水平的子采樣數(shù)據(jù)叉跛，我們運(yùn)行核擴(kuò)散密度 ρKD 和快速替代 ρFKD松忍。從圖 4 可以看出，ρKD 的運(yùn)行時(shí)間和內(nèi)存使用量隨著樣本量的增加而顯著增加筷厘。而 ρFKD 保留了非常低的計(jì)算成本鸣峭。這表明 ρFKD 實(shí)現(xiàn)了出色的計(jì)算效率，在實(shí)踐中應(yīng)該受到青睞酥艳。

六摊溶，結(jié)論

基于密度的聚類(lèi)對(duì)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘有著深遠(yuǎn)的影響。然而玖雁，基礎(chǔ)樸素密度函數(shù)會(huì)檢測(cè)到不同的局部特征更扁，從而導(dǎo)致聚類(lèi)中的額外錯(cuò)誤。我們提出了一組基于核擴(kuò)散過(guò)程的新密度函數(shù)來(lái)解決這個(gè)問(wèn)題赫冬，它適應(yīng)不同局部分布特征的密度區(qū)域浓镜。我們證明，與經(jīng)典版本和其他最先進(jìn)的方法相比劲厌，采用所提出方法的 DBSCAN 和 DPC 提高了聚類(lèi)性能膛薛。