algorithm - K-均值聚类分区

Question

我正在使用 matlab，我有一个名为 MeansOfK 的非常非常大的 .mat 文件，其中包含近 5,000,000 x N。我的测试数据包括汽车和非汽车。我的问题是，当我尝试对 MeansofK 使用 k-means 时。它总是内存不足。

[idx, ctr] = kmeans(MeansOfK , k, 'Distance', 'sqEuclidean');

我的选择是

1.我使用分而治之的技术，其中我将汽车和非汽车划分为更小的分区，并将其放入 k-means 中。

2.我将汽车类和非汽车类分开，并尝试对这两个类使用 k-means。

最终输出将是汽车或非汽车的组合类别。来自 k-means 过程。

所以我的问题是？

我将要做的事情可行吗？如果我对文件进行分区而不是将其作为一个整体进行，它会影响我的 k-means 的输出吗？

建议和答案总是很感激 :)谢谢

Answer 1

您可以做什么，可以利用 Johnson-Lindenstrauss lemma 的结果将数据集嵌入低维空间的位置以及在较小数据集上进行 kmeans 计算时的位置。例如，如果你的数据矩阵是 A 你可以这样做:

% N is the number of data points and s is the reduced dimension
S  =  randn (N, s)/s q r t (s) ;
C  =  A ∗ S ;

% now you can do you kmeans computation on C
[idx, ctr] = kmeans(MeansOfK , k, 'Distance', 'sqEuclidean');

基本上，您可以对原始数据集使用 idx 和 ctr 结果，这将为您提供 (1+epsilon) 近似值。您还可以根据 Dan Feldman 的工作获得更好的结果。这基本上是说您可以对数据进行计算和 SVD，并在 k/epsilon 引擎值上进行投影以计算 kmeans 值并获得 (1+epsilon) 近似值。

---

更新

基于评论，我想建议利用 coresets 方法，再次基于 el 的 Dan Feldman 的论文，Turning Big Data Into Tiny Data .这些技术提供了将大量数据减少为更小数据的能力，并可证明保证提供 (1+epsilon) 近似于最佳 kmeans 解决方案。此外，您可以继续构建流式核心集，这将允许您在流式传输数据时保持 O(logn * epsilon) 近似值(第 10 节，图 3)，例如在你的情况下分成更小的 block 。最终您可以在生成的核心集上运行 kmeans 计算。

你也可能会考虑看看我最近的 publication以获取有关如何处理您的案件的更多详细信息。在这里，您还可以在我的 github account 中找到引用资料如果您想使用它。