K-均值聚类分区

Question

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

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

我的选择是

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

2.I 将汽车和非汽车分开类并尝试对两者都使用 k-means 类。

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

所以我的问题是？

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

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

Answer 1

我会说，如果增加内存是不可能的，你唯一真正的选择是将数据分成更小的集合。当我运行一个使用协同过滤算法的大数据项目时，我们过去常常处理高达 7 亿 + 的集合，每当我们用尽内存时，就意味着我们需要将数据分成更小的集合，并且运行分别对它们的算法。

Answer 2

您可以利用 Johnson-Lindenstrauss lemma 的结果将数据集嵌入到较低维度 space 以及在较小的数据集上进行 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，Turning Big Data Into Tiny Data 的 Dan Feldman 的论文。这些技术提供了将大量数据减少为更小数据的能力，并可证明保证提供 (1+epsilon) 近似于最佳 kmeans 解决方案。此外，您可以继续构建流式核心集，这将允许您在流式传输数据时保持 O(logn * epsilon) 近似（第 10 节，图 3），例如在你的情况下分成更小的块。最终您可以运行对结果核心集进行 kmeans 计算。

另外，如果你想使用它，你可能会考虑看看我最近的 publication to get more details on how to handle your case. Here you can find also a reference in my github account。

K-均值聚类分区

K-Means Clustering Paritioning

algorithm

matlab

image-processing

k-means