K-均值聚类配准

Question

我正在使用matlab，我有一个非常大的.mat文件，名为MeansOfK，包含近500万x N，我的测试数据包括Car和非car。我的问题是，当我试图使用k-均值的MeansofK.它总是没有记忆。

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

我的选择是

1.采用分而治之的方法，将汽车和非轿车划分为较小的分区，并将其放入k-均值。

2.我把汽车类和非汽车类分开，并试图对这两个类使用k-方法。

最后的输出将是汽车或非汽车的组合类。从k均值过程中。

所以我的问题是？

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

建议和答案永远值得赞赏:)谢谢

Answer 1

您能做的是，您可以利用Johnson-Lindenstrauss引理的结果，将数据集嵌入到较低维度的空间中，并在较小的数据集上进行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)近似。而且，根据丹·费尔德曼的工作，您可以获得更好的结果，这基本上是说，您可以计算和计算您的数据，并在k/epsilon引擎值上进行投影，以计算kmeans值和get (1+epsilon)近似。

​

更新

​

基于评论，我想建议利用coreset方法，再一次基于Dan在el，将大数据转化为小数据的论文。该技术提供了将大量数据减少到更小的能力，并提供了(1+epsilon)对最优k-均值解的逼近。此外，您还可以继续进行流coreset构造，这将允许您在流数据时保持O(logn * epsilon)近似(图3第10节)，例如，在您的情况下，将分区划分为较小的块。最终，您可以在结果的coreset上运行kmeans计算。

此外，您可能会考虑查看我最近的出版，以获得关于如何处理您的案例的更多细节。在这里，如果您想要使用，也可以在我的github帐户中找到一个引用。

Answer 2

我想说，如果不可能增加内存，您唯一的实际选择就是将数据划分为更小的集合。当我使用协作过滤算法运行一个大数据项目时，我们用来处理高达7亿以上的集合，每当我们耗尽内存时，这意味着我们需要将数据分割成更小的集合，并分别在它们上运行算法。