为具有任意成本函数的集合的子集找到 k 个最佳代表的算法

Question

给定一组 N 个点，我需要将其分成 k 个子集 S1，...，Sk。每个子集 Si 都会有一个代表性的 Ri。我想找到这些 R1, ..., Rk 以最小化子集成员相对于集群代表的任意成本函数。基本上，

\min \sum_{i=1}^k \sum_{Pj \in Si} 成本(Pj, Ri)

其中集群代表 Ri 本身是通过另一个任意归约函数从集群成员获得的

Ri = 减少(Si)

我从 k-means 聚类中获得灵感，并提出了以下算法，我将其称为 k-reduce 聚类。我想知道是否有任何算法或算法系列可以完成我想做的事情。

# Initialize using k random samples from S, could use better initialization
cluster_repr = random_samples(S, k) # list of k points
clusters = None

while True:

    # Step 1: Assignment
    old_clusters = clusters
    clusters = [[] for i in range(n)]
    for Pj in S:
        # assign s to the cluster that minimizes its cost wrt to the representative
        cluster_idx = argmin(
            cluster_repr,
            lambda Ri : cost_fn(Pj, Ri)
        )
        clusters[cluster_idx].append(Pj)

    # Step 2: Update step
    cluster_repr = [reduce_fn(clusters[i]) for i in range(n)]

    total_dist = None
    if old_clusters == clusters: break

Answer 1

如果没有对这些函数的一些假设，这个问题是 NP 困难的。

示范。让我们将 3DM 简化为这个。采用具有

3k

节点的 3 部分超图。创建成本函数

cost(Pj, Ri) = ||Ri||

。创建一个

reduce

函数，该函数将映射到超图中任何三元组的范数为 1 的“代表”，否则将非常大。现在，如果存在 3 匹配，则最佳解决方案将是 3 匹配，并且我们已将已知的 NP 完全问题（实际上是 Karp 最初的 21 个问题之一）简化为这个问题。

一般来说，我们不知道如何验证解决方案在多项式时间内是否最优。所以我们不知道你的问题在 P 中。因此我们知道如何证明的最好方法是它是 NP 难的。