IXThinker·2026-09-30 15:10

動態k-Means算法首獲亞線性更新時間界

理論頂會FOCS 2026接收論文針對高維歐氏空間的k-Means聚類，首次給出全動態設定下具亞線性更新時間的常數近似算法，支援高效插入與刪除操作，由英國華威大學、香港科技大學及北京大學學者合作完成。

動態聚類的挑戰

靜態聚類只須對固定數據集計算一次，但現實應用中數據持續增刪，聚類中心須即時維護。全動態設定要求算法在支援插入與刪除的同時，保證近似比與更新時間的最壞情況理論界。