时间戳

首页 > 解决方案 > 从候选列表中找到最佳 k-means

algorithm - 从候选列表中找到最佳 k-means

问题描述

我有一个大小为 n 的点数组，称为 A，以及一个大小为 O(k)>k 的候选数组，称为 S。我想在 S 中找到 k 个点，使得从 A 的点到它们最近的点的距离平方和k个点中的点将被最小化。一种方法是检查 S 中任何可能的 k 点的成本并取最小值，但这需要 O(k^k*n) 时间，有没有更有效的方法来做到这一点？

我需要最佳解决方案或恒定近似值。

我需要这个的原因是我试图尽快找到 k-means 的常数近似值，然后将其用于核心集构造（核心集 = 数据最小化，同时仍然保持任何查询的成本大致相同） . 我能够证明，如果我们假设在最优聚类中每个聚类都有 omega(n/k) 点，我们可以非常快速地创建一个大小为 O(k) 的候选者列表，其中包含 k 的 3 近似值-意思是，所以我想知道我们是否可以及时找到那些 k 点或它们的成本的恒定近似值，这比穷举搜索要快。

k=2 的示例 在此示例中，S 是绿点，A 是红点。该算法应该从 S 返回 2 个圆圈点，因为它们最小化了从 A 的点到 2 的最近点的距离平方和。

标签： algorithmk-means

解决方案

我有一个大小n为 的点数组，以及一个大小为A的候选数组。我想找到这样的点，使得从点到它们离点的最近点的距离平方和最小化。O(k)>kSkSAk

听起来这可以简单地通过检查N点与K点来找到具有最小平方距离的k点来解决。N

因此，我现在相当确定这实际上是在点中为每个点找到k-nearest neighbors（K-NN 作为计算几何问题，而不是模式识别定义），而不是实际上是 k-means。NK

对于更高维度，D在算法中考虑维度通常很有用。

提到的算法确实是O(NDk^2)在考虑 K-NN 时。这可以O(NDk)通过对距离使用快速选择算法来改进。这允许N针对每个点K检查点列表O(N)以找到最近的k点。

https://en.wikipedia.org/wiki/Quickselect

编辑：似乎对快速选择以及是否可以使用有些混淆。这是一个O(DkNlogN)使用标准排序O(NlogN)而不是 quickselect的解决方案O(N)。尽管这在实践中可能会更快，并且正如您在大多数语言中看到的那样，它很容易实现。

results = {}
for y in F:
  def distanceSquared(x):
    distance(x,y) # Custom distance for each y

  # First k sorted by distanceSquared
  results[y] = S.sort(key=distanceSquared)[:k]
return results

更新新视觉

# Build up distance sums O(A*N*D)
results = {}
for y in F:
  def distanceSquared(x):
    distance(x,y) # Custom distance for each y

  # Sum of distance squared from y for all points in S
  results[y] = sum(map(distanceSquared, S))

def results_key_value(key):
  results[key]

# First k results sorted by key O(D*AlogA)
results.keys().sort(key=results_key_value)[:k]

您可以通过仅考虑从这些点中选择的 Z 个随机点来进行近似S。S或者，如果它们足够靠近，您可以合并点。这可能会减小S到更小的尺寸，只要长度S保持在大约F^2或更大的尺寸，它不应该影响F选择太多的点。尽管您还需要调整点的权重以更好地处理它。IE：表示 10 个点的点的平方距离乘以 10，以说明它充当 10 个点，而不仅仅是 1。

推荐阅读