導 讀

本文是 ICLR 2023 入選 notable-top-5%*的論文 Near-optimal Coresets for Robust Clustering 的解讀。該論文由北京大學前沿計算研究中心姜少峰課題組與華為理論計算機實驗室合作完成。根據(jù)理論計算領域慣例，作者按姓名首字母排序。

文章針對一種具有魯棒性的聚類問題設計核心集構造算法，該算法構造的核心集大小指數(shù)級地改進了已有結果，并且逼近理論下界。

*對應往年的 Oral。

論文鏈接：

https://arxiv.org/abs/2210.10394

01

問題介紹

經(jīng)典的聚類問題，如k-means，旨在尋找一個大小為 k 的點集作為聚類中心，使得所有數(shù)據(jù)點到聚類中心的距離（的冪次）和這一目標函數(shù)最小化。聚類問題是數(shù)據(jù)分析、機器學習領域的核心問題之一。然而，經(jīng)典的聚類問題的目標函數(shù)經(jīng)常面臨魯棒性問題，尤其是當數(shù)據(jù)中有（敵對）噪聲時。舉例來說，如果在一個數(shù)據(jù)集中加入一個距離足夠遠的異常點，聚類算法會被誤導，并在該異常點處設置一個聚類中心。因此，本文聚焦于一種具有魯棒性的聚類問題：帶有異常點的聚類問題（clustering with outliers），記為 (k,z,m)-魯棒聚類，這里m 為一個指示異常點數(shù)量的參數(shù)。具體來說，給定數(shù)據(jù)集 X，(k,z,m) -魯棒聚類問題希望找到一個大小為 k 的聚類中心 C，以最小化如下目標函數(shù)：

在該魯棒聚類目標函數(shù)中，首先把數(shù)據(jù)點按照到 C 的距離進行排序，然后剔除掉最遠的 m 個點，最后在剩下點上套用經(jīng)典聚類的目標函數(shù)。特別地，當 m=0 時，該問題退化成經(jīng)典的聚類問題。目標函數(shù)中的 z 是距離求和的冪次，常見選取 z=1或2，分別對應于 k-median 和 k -means 的目標函數(shù)。

異常點的出現(xiàn)使得為經(jīng)典聚類設計的高效算法不再適用，這帶來了顯著的計算挑戰(zhàn)，在大數(shù)據(jù)計算的背景下尤為突出。因此，我們考慮針對帶有異常點的聚類問題的核心集（coresets）。粗略來說，一個ε-核心集是一個極小數(shù)據(jù)摘要，使得對于任意的聚類中心 C，在核心集上計算得到的目標函數(shù)的值與在原數(shù)據(jù)集上計算得到的值的相對誤差不超過 ε。一旦有了核心集，我們只需要將已有的近似算法直接（或經(jīng)過少部分修改后）運行在核心集上即可得到對于原大數(shù)據(jù)上問題的近似。自然地，核心集這種基于將大數(shù)據(jù)化為小數(shù)據(jù)的方法在大數(shù)據(jù)計算上，尤其是亞線性算法設計上，也有重要應用。例如，核心集通?？梢灾苯佑糜诘玫骄垲悊栴}的數(shù)據(jù)流（streaming）算法、分布式（distributed）算法和動態(tài)（dynamic）算法。

02

主要結果

本文針對 (k,z,m)-魯棒聚類問題，設計了一個可在線性時間內構造的大小為

的 ε-核心集。其中? 隱藏了 polylog(f) 因子。

我們的結果顯著改進了已有的結果：大小為 的核心集構造算法 [FS12]，以及一個僅達到雙重標準近似（即不能保證恰好對 m 個異常點有效）的核心集構造算法 [HJLW18]。此外，我們還證明了任何針對該問題的核心集的大小至少為 Ω(m)。該理論下界結合經(jīng)典聚類問題的核心集大小下界 [CLSS22] 說明了我們的核心集構造算法已經(jīng)逼近理論極限。

我們還在若干實際數(shù)據(jù)集中測試了該算法，并與三種 baseline 算法進行比較：簡單均勻采樣算法（US）、考慮異常點的均勻采樣算法（OAUS）以及由 Feldman 和 Schulman 提出的基于敏感性采樣算法（Sensitivity Sampling，SS）。我們的算法在所有數(shù)據(jù)集上都展現(xiàn)了顯著的優(yōu)越性。下圖是在多種實際數(shù)據(jù)集上的性能對比，其中橫軸是核心集的大小，縱軸代表在數(shù)據(jù)集上的實際誤差。

另外，我們進一步從實驗上證明了我們的核心集可以顯著加速已有魯棒聚類算法。我們選擇測試了兩種算法：基于經(jīng)典 Lloyd 的算法（LL）和局部搜索算法（LS）。實驗表明，在大小約為1000的核心集上運行算法（記運行時間為 ）與在原數(shù)據(jù)集上運行算法（記運行時間為 ）相比，提速了近百倍（即使加上核心集構造時間 ），而計算得出的解的相對誤差不超過5%。下表是該實驗的結果。

03

算法與分析

構造算法：我們的算法基于最近提出的核心集構造算法框架 [BCAJ+22]，大致分為如下步驟：

• 運行已有的三重標準（tri-criteria）近似算法，得到一組近似解。

• 根據(jù)對數(shù)據(jù)集進行聚類，計算出 m 個到 的最遠點，將這些點從數(shù)據(jù)集中刪除并加入核心集S。

• 對于每一個類，利用 [BCAJ+22] 提出的方法將其劃分成若干圓環(huán)（rings）和若干圓環(huán)組成的集合，稱為群（groups）。

• 對于每個圓環(huán)，均勻采樣一定數(shù)量的點并加入S。

• 對于每個群，計算一個大小為2的核心集并加入S。

• 輸出S作為最終核心集。

誤差分析：類似于 [BCAJ+22]，我們對圓環(huán)和群分別進行分析。然而，異常點的存在為證明帶來了不少困難。在這里，我們以z=1的情況為例說明。

對于一個圓環(huán)R，核心集誤差來自于均勻采樣。在 [BCAJ+22] 中，對于任意一個聚類中心 C，均勻采樣的誤差被證明不超過 ε·cost(R,C)（忽略一些極小項），即 ε 乘上所有 R 中的點到 C 的距離和。而由于異常點的存在，我們無法直接利用他們的結論控制誤差在 ε·(R,C)之內，其中? 為 R 中的異常點數(shù)量（相對于 C）。這是因為 (R,C) 可以遠小于cost(R,C)甚至接近于 0（當? ≈|R|時）。在本文中，我們給出了誤差的另一種上界，從而保證除了ε -相對誤差之外的誤差可以利用 ε·OPT來控制。

在群的誤差分析中，我們的思路與 [BCAJ+22] 類似。具體來說，我們首先根據(jù)群中點的分布情況將群分為染色群和非染色群兩類，其中染色群的數(shù)量極少。我們稱一個群是壞的當且僅當它產(chǎn)生的誤差遠大于 ε·(G,C)。在 [BCAJ+22] 中，他們證明了只有染色群才可能是壞的群，并且利用加性誤差（additive error）控制了壞的群的誤差。而當群中存在異常點時，非染色群也有可能是壞的（理由與圓環(huán)的情況類似，即 (G,C)可以非常小）。在本文中，我們通過一些幾何上的觀察，證明了壞的非染色群數(shù)量也是有限的，從而證明這一類誤差同樣可以利用加性誤差進行控制。

除此之外，我們還需要保證所有關于環(huán)/群的誤差分析能對所有的異常點數(shù)量 t≤m同時成立。這是因為對不同的聚類中心C，每個圓環(huán)/群的異常點數(shù)量是不固定且無法事先預知的。

參考文獻

[BCAJ+22] Vladimir Braverman, Vincent Cohen-Addad, Shaofeng Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In FOCS. IEEE Computer Society, 2022.

[CLSS22] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In STOC, pages 1038–1051. ACM, 2022.

[FS12] Dan Feldman and Leonard J Schulman. Data reduction for weighted and outlier-resistant clustering. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1343–1354. SIAM, 2012.

[HJLW18] Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In FOCS, pages 814–825. IEEE Computer Society, 2018.