2

我对集群和相关主题相当陌生，所以请原谅我的问题。

我试图通过做一些测试来介绍这个领域，作为第一个实验，我想根据内容相似性在推文上创建集群。实验的基本思想是将推文存储在数据库中并定期计算聚类（即使用 cron 作业）。请注意，数据库会不时获得新的推文。

在这个领域一无所知，我的想法（可能是幼稚的）会做这样的事情：

1. For each new tweet in the db, extract N-grams (N=3 for example) into a set
2. Perform Jaccard similarity and compare with each of the existing clusters. If result > threshold then it would be assigned to that cluster
3. Once finished I'd get M clusters containing similar tweets

现在我发现这种基本方法存在一些问题。抛开计算成本不谈，一条推文和一个集群如何进行比较？假设我有一条推文 Tn 和一个包含 T1、T4、T10 的集群 C1，我应该将它与哪个比较？鉴于我们谈论的是相似性，很可能会发生 sim(Tn,T1) > 阈值但 sim(Tn,T4) < 阈值。我的直觉告诉我，应该为集群使用平均值之类的东西，以避免这个问题。

此外，sim(Tn, C1) 和 sim(Tn, C2) 都可能 > 阈值，但与 C1 的相似性会更高。在这种情况下，Tn 应该转到 C1。这也可以通过蛮力来完成，以将推文分配给具有最大相似性的集群。

最后，这是计算问题。我一直在阅读一些关于 minhash 的内容，它似乎是这个问题的答案，尽管我需要对它做更多的研究。

无论如何，我的主要问题是：有该领域经验的人可以推荐我应该采用哪种方法吗？我读过一些关于 LSA 和其他方法的提及，但试图应对所有事情变得有点不知所措，所以我很感激一些指导。

从我正在阅读的工具来看，这将是层次聚类，因为它允许在新数据进入时重新组合集群。它是否正确？

请注意，我不是在寻找任何复杂的案例。我的用例想法是能够在没有任何先前信息的情况下将类似的推文分组。例如，来自 Foursquare 的推文（“我正在签到……”彼此相似就是一种情况，或者“我的 klout 分数是……”）。另请注意，我希望这与语言无关，因此我对必须处理特定的语言问题不感兴趣。

4

2 回答 2

7

在我看来，您正试图将两个不同的问题合二为一，即“句法”和“语义”聚类。它们是完全不同的问题，尤其是在短文本分析领域（当然，Twitter 是短文本分析之王）。

“句法”聚类意味着聚合最有可能来自同一来源的推文。您的 Foursquare 示例非常适合，但转发、分享在线报纸文章或博客文章的人以及许多其他情况也很常见。对于这类问题，正如您所说，使用 N-gram 模型几乎是强制性的（我的经验表明 N=2 对推文有好处，因为您可以找到具有低至 3-4 个特征的重要推文）。规范化在这里也是一个重要因素，删除 RT 标签、提及、主题标签可能会有所帮助。

“语义”聚类意味着聚合具有相同主题的推文。这是一个更加困难的问题，如果您尝试聚合推文的随机样本，它可能不会起作用，因为它们通常携带的信息太少。但是，如果您将域限制为特定的推文子集（即匹配关键字或主题标签的推文），这些技术可能会起作用。LSA 在这里可能很有用，而它对句法簇没用。

根据您的观察，我认为您想要的是句法聚类。但是，您最大的问题是您需要在线集群，而不是静态集群。在静态情况下运行良好的经典聚类算法（如层次聚类或联合查找）并不真正适合在线聚类，除非每次将新推文添加到数据库时都从头开始重做聚类。根据我的经验，“平均”集群以添加新元素并不是一个很好的解决方案，因为您需要保留每个集群成员的所有信息，以便在每次新数据进入时更新“平均值”。此外，分层等算法聚类和联合发现效果很好，因为如果在它们之间找到相似性链接，它们可以加入预先存在的集群，

像 MinHash（或 SimHash）这样的算法确实更适合在线聚类，因为它们支持“查询”类似文档的想法。MinHash 本质上是一种获取超过一定相似度阈值的文档对的方法（特别是 MinHash 可以认为是 Jaccard 相似度的估计量），而不必依赖像成对比较这样的二次算法（实际上是O(nlog(n))及时）。但是，它在空间上是二次的，因此 MinHash 的仅内存实现仅对小型集合（例如 10000 条推文）有用。但是，在您的情况下，将推文的“草图”（即通过对推文进行最小散列处理获得的散列集）保存在数据库中以形成“索引”并查询新的那个索引。然后，您可以通过在与相似度查询匹配的顶点（推文）之间添加边来形成相似度图。您的图形的连接组件将是您的集群。

于 2013-10-01T09:43:10.077 回答
3

对我来说，这听起来很像树冠预聚类。

本质上，每个集群都由启动集群的第一个对象表示。外半径内的对象加入集群。不在至少一个簇的内半径内的对象启动一个新簇。这样，您可以获得数据集的重叠（非不相交！）量化。由于这可以大大减少数据大小，因此可以用来加速各种算法。

但是不要指望聚类推文会产生有用的结果。推文数据只是噪音太大。大多数推文只有几个词，不足以定义良好的相似性。另一方面，你有各种各样的转推，它们几乎是重复的——但检测起来很简单。

那么什么是好的推文集群呢？这种 n-gram 相似性真的能捕捉到这一点吗？

于 2013-09-27T15:36:49.403 回答