提出新型聚类框架,优化多层级成本约束下的聚类质量。
Clustering to Minimize Cluster-Aware Norm Objectives
- 设计基于最大距离求和的内层范数与有序加权外层范数的聚类算法
- 对前ℓ个最大距离求和的场景实现常数倍近似解
- 适用于需关注集群负载均衡或半径控制的场景
我们提出一种通用聚类问题:将数据点集 $P$ 划分为 $k$ 个簇,通过选取 $k$ 个中心 $X$ 并为每个点分配一个中心。每个簇的成本由其点到中心的距离向量的单调对称内范数 $f$ 表示,目标是最小化各簇成本构成向量的外范数 $g$。该问题称为 $(f,g)$-Clustering,可统一 $k$-Center、$k$-Median、Min-Sum of Radii、Min-Load $k$-Clustering 等经典问题。本文首次研究具有簇感知性质的目标函数。主要成果包括:针对内范数为 $ extsf{top}_ ho$(取最大 $ ho$ 个距离之和)与外范数为 $ extsf{L}_1$ 的情形,给出常数因子近似算法;针对外范数为 $ extsf{Ord}$($ extsf{top}_ ho$ 的凸组合)的情形,同样设计出常数因子近似算法。
原文摘要 · Abstract (English)
We initiate the study of the following general clustering problem. We seek to partition a given set $P$ of data points into $k$ clusters by finding a set $X$ of $k$ centers and assigning each data point to one of the centers. The cost of a cluster, represented by a center $x\in X$, is a monotone, symmetric norm $f$ (inner norm) of the vector of distances of points assigned to $x$. The goal is to minimize a norm $g$ (outer norm) of the vector of cluster costs. This problem, which we call $(f,g)$-Clustering, generalizes many fundamental clustering problems such as $k$-Center, $k$-Median , Min-Sum of Radii, and Min-Load $k$-Clustering . A recent line of research (Chakrabarty, Swamy [STOC'19]) studies norm objectives that are oblivious to the cluster structure such as $k$-Median and $k$-Center. In contrast, our problem models cluster-aware objectives including Min-Sum of Radii and Min-Load $k$-Clustering. Our main results are as follows. First, we design a constant-factor approximation algorithm for $(\textsf{top}_\ell,\mathcal{L}_1)$-Clustering where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ largest distances. Second, we design a constant-factor approximation\ for $(\mathcal{L}_\infty,\textsf{Ord})$-Clustering where the outer norm is a convex combination of $\textsf{top}_\ell$ norms (ordered weighted norm).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。