2

I have points with binary features:

id, feature 1, feature 2, ....
1, 0, 1, 0, 1, ...
2, 1, 1, 0, 1, ...

and the size of matrix is about 20k * 200k but it is sparse. I am using Mahout for clustering data by kmeans algorithm and have the following questions:

  1. Is kmeans a good candidate for binary features?
  2. Is there any way to reduce dimensions while keeping the concept of Manhattan distance measure (I need manhattan instead of Cosine or Tanimoto)
  3. The memory usage of kmeans is high and needs 4GB memory for each Map/Reduce Task on (4Mb Blocks on 400Mb vector file for 3k clusterss). Considering that Vector object in Mahout uses double entries, is there any way to use just Boolean entries for points but double entries for centers?
4

2 回答 2

2

如果你有一个好的距离度量，k-means 是一个很好的候选者。曼哈顿距离可能很好；我喜欢对数似然。

你可以使用任何你喜欢的降维技术。我喜欢交替最小二乘；SVD 也很好用。对于这个大小矩阵，您可以使用 Commons Math 在内存中轻松完成，而不是使用 Hadoop——这太过分了。

（另请参阅http ://myrrix.com——我在那里有一个非常快速的 ALS 实现，您可以在核心/在线模块中重用。它可以在几秒钟内以数十 MB 的堆来处理它。）

您的特征矩阵中不再有二进制 0/1 值。在特征空间中，余弦距离应该很好（1 - cosineSimilarity）。Tanimoto/Jaccard 不合适。

于 2012-07-11T08:39:16.573 回答
2

k-means 有一个经常被忽视的大要求：它需要计算一个合理的均值。这比人们想象的要重要得多。

  • 如果均值不降低方差，它可能不会收敛（算术平均值对于欧几里得距离是最优的。对于曼哈顿，据说中位数更好。对于非常不同的指标，我不知道）
  • 平均值可能不再那么稀疏了
  • 平均值也不再是二元向量

此外，特别是对于大型数据集，您想使用哪个k？

你真的应该研究其他距离措施。您的数据量并不大；使用一台计算机应该仍然足够。使用紧凑的向量表示，它将很容易适应主存储器。只是不要先使用计算 ^2 相似度矩阵的东西。也许尝试一些带有二进制向量相似性索引的东西。

k-means 相当容易实现，特别是如果您不进行任何提前播种。为了减少内存使用，只需自己实现它以获得最适合您的数据的表示。它可以是一个位集，也可以是一个非零维度的排序列表。曼哈顿距离然后归结为计算向量不同的维数！

于 2012-07-12T06:44:18.560 回答