一些聚类问题

假设我们是一家大型零售公司, 客户分布在全国各地. 为了方便管理和提供更好的服务, 我们需要把客户按照地理位置进行分类, 例如按城市或街道的维度把客户划分成区块, 每个区块是客户的集合. 主要考虑如下因素:

区块包含客户的地理位置尽可能集中
区块大小(客户数量)有限制
客户有权重, 例如客户分为普通客户和VIP客户.

下文总结几个可能需要求解的聚类问题.

问题列表

1. 等量的聚类问题(Equal-size clustering or balanced clustering)

给定点集 $X=\{\boldsymbol{x_1}, \boldsymbol{x_2}, ..., \boldsymbol{x_n}\}$ , 其中每个点是一个 $d$ 维实向量. 给定常数 $k$ 且 $n \mod k =0$ . 我们把 $X$ 划分(Partition)成 $k$ 个"等量"的子集 $S_1, S_2, ..., S_k$ . 令 $\boldsymbol{\mu_i}$ 代表 $S_i$ 的均值, 我们的目标是:
$\min \sum_{i=1}^k\sum_{\boldsymbol{x}\in S_i}||\boldsymbol{x} - \boldsymbol{\mu_i}||^2.$

2. 限容的聚类问题(Size-constrained clustering)

给定点集 $X=\{\boldsymbol{x_1}, \boldsymbol{x_2}, ..., \boldsymbol{x_n}\}$ , 其中每个点是一个 $d$ 维实向量. 给定常数 $LB$ , $UB$ 且 $LB\leq UB$ . 我们把 $X$ 划分(Partition)成 $k$ 个"满足容量限制"的子集 $S_1, S_2, ..., S_k$ , 即 $LB \leq |S_i|\leq UB$ , $\forall i$ . (注意: $k$ 不是输入参数.) 令 $\boldsymbol{\mu_i}$ 代表 $S_i$ 的均值, 我们的目标是:
$\min \sum_{i=1}^k\sum_{\boldsymbol{x}\in S_i}||\boldsymbol{x} - \boldsymbol{\mu_i}||^2.$

3. 限权的聚类问题(Weight-constrained clustering)

给定点集 $X=\{\boldsymbol{x_1}, \boldsymbol{x_2}, ..., \boldsymbol{x_n}\}$ 和权重 $w_1, w_2, ..., w_n$ , 其中每个点是一个 $d$ 维实向量. 给定常数 $LB$ , $UB$ 且 $LB\leq UB$ . 我们把 $X$ 划分(Partition)成 $k$ 个"满足容量限制"的子集 $S_1, S_2, ..., S_k$ , 即 $LB \leq w(S_i)\leq UB$ , $\forall i$ , 其中 $w(S_i)$ 代表 $S_i$ 对应的权重之和. (注意: $k$ 不是输入参数.) 令 $\boldsymbol{\mu_i}$ 代表 $S_i$ 的均值, 我们的目标是:
$\min \sum_{i=1}^k\sum_{\boldsymbol{x}\in S_i}||\boldsymbol{x} - \boldsymbol{\mu_i}||^2.$

说明

1. 计算复杂性

我们知道k-means是NP-hard. 甚至当 $k=2$ ^[1]以及平面上的k-means也是NP-hard^[2]. 与k-means相比, 问题1要求每个聚类(cluster)的元素个数相同. 那么它的复杂性也是NP-hard吗?
如果上述问题限制在 平面上的二维向量, 其计算复杂性是否NP-hard? 这是我们在实际应用中关心的问题.
问题1是问题2的特殊情况: 令 $LB=UB=n/k$ .
问题2是问题3的特殊情况: 令 $w_i=1$ , $\forall i$ .

2. 优化目标

上述3个问题的目标函数都是相同的,即最小化中心点到聚类点的距离( $L_2$ 范数)之和. 我们也可以考虑其它的优化目标, 例如最小化最大半径. 甚至也可以考虑用图的方式对上述问题建模(参考k-median, k-center).
在实际应用中, 我们期望做到每个类尽量集中. 因此, 无论上述问题用什么优化目标, 我们真正期望的不一定是最优解, 而是让结果"看起来"可以接受. 从计算角度来看, 我们希望高效且解的质量可以接受的算法.
从建模的角度来看, 我们是否有可能找到一种建模方式, 例如找到一种目标函数, 使得问题本身的计算复杂性可以降低成P问题? (且在实际中我们能接受这样的目标)

参考文献

M. Garey, D. Johnson, H. Witsenhausen. The complexity of the generalized LIoyd - Max problem. IEEE Transactions on Information Theory. 28(2): 255-256, 1982. ↩
M. Mahajan, P. Nimbhorkar and K.Varadarajan. The planar k-means problem is NP-hard. Lecture Notes in Computer Science. 5431. pp.274-285, 2009. ↩

最后编辑于：2020.02.05 15:00:25