稀疏二元向量数据集的聚类

Question

如果我有一个稀疏数据集，其中每个数据由一个1000元素的向量描述，该向量的每个元素可以是0或1（有很多0和一些1），您知道任何距离函数可以帮助我对它们进行聚类吗？在这种情况下，像欧几里得距离这样的东西是否方便？我想知道是否有一个简单方便的距离度量可以用于这种情况，以尝试我的数据。

谢谢

- shn

---

K-meloids中使用的畸变函数怎么样？它与欧几里得距离并没有太大的区别。 - Neo

@CRK K-meloids使用p = 1的Minkowski距离，这是欧几里得距离的一般情况，不是吗？ - shn

Answer 1

这个问题没有一个答案。最佳实践取决于领域。

一旦您确定了相似度度量方法，聚类通常通过平均或查找中心点来完成。有关算法示例，请参见以下聚类二进制数据的论文:

• Carlos Ordonez. 使用K-means对二进制数据流进行聚类。PDF
• Tao Li. 二进制数据聚类的通用模型。PDF

有关相似性测量方法的想法，请参见在线“二进制字符串相似性测量工具”。他们提到：Sokal-Michener、Jaccard、Russell-Rao、Hamann、Sorensen、antiDice、Sneath-Sokal、Rodger-Tanimoto、Ochiai、Yule、Anderberg、Kulczynski、Pearson's Phi、Gower2、点积、余弦系数、汉明距离等相似度度量方法。他们还引用了以下论文：

• Luke, B. T.，二进制对象聚类
• Lin, D.，相似性的信息论定义。
• Toit，du S.H.C.； Steyn，A.G.W.； Stumpf，R.H.；图形探索性数据分析；第3章，第77页，1986年；Springer-Verlag。

（我个人喜欢余弦系数。还有KL散度及其Jensen距离等方法。）

- cyborg

---

谢谢你的回答，这是一个有趣的链接。但是，假设我们使用汉明（或余弦或任何其他距离），我们如何学习每组向量的代表性。我的意思是，假设我们有v1 = 0100100001100和v2 = 0001100001100，它们彼此接近，因为它们只在两个位（第二个和第三个位置）上不同，那么例如汉明距离将为2（余弦将为0.7500），问题是：v1和v2的代表向量将是什么？如何（学习）仅表示应该代表v1和v2以及所有接近它们的其他向量的向量值。 - shn

代表向量是平均值（质心，而不是二进制）或中心点。阅读论文以了解如何找到它们的示例。 - cyborg

死链：“用于测量二进制字符串相似度的工具” - Ahue

Answer 2

请看用于稀疏文本向量的距离函数，如余弦距离，以及用于比较集合的Jaccard距离。

- Has QUIT--Anony-Mousse

Answer 3

许多关于二进制向量的距离/相似度函数已被提出。在《二进制相似性和距离测量综述- Choi，Cha，Tappert 2010》中，作者列出了76个这样的函数。

- Lior Kogan

Answer 4

如果它确实是许多0和一些1，您可以尝试对第一个或最后一个1进行聚类 - 参见http://aggregate.org/MAGIC/#Least 最不显著的1位

- Eugen Rieck

---

首先或最后一个？在这种情况下，两个向量之间的函数度量如何定义？Distance（V1，V2） - shn