cluster-analysis - 对推文聚类方法的质疑

Question

我对聚类和相关主题还很陌生，所以请原谅我的问题。

我试图通过做一些测试来进入这个领域，作为第一个实验，我想根据内容相似性在推文上创建集群。实验的基本思想是将推文存储在数据库中并定期计算聚类(即使用 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) > threshold 但 sim(Tn,T4) < threshold。我的直觉告诉我应该对集群使用类似平均值的值，以避免出现此问题。

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

最后是计算问题。我已经阅读了一些关于 minhash 的文章，它似乎是这个问题的答案，尽管我需要对它做更多的研究。

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

根据我正在阅读的内容，用于此目的的工具将是层次聚类，因为它允许在新数据输入时重新分组聚类。这是正确的吗？

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

Answer 1

在我看来，您正试图将两个不同的问题合而为一，即“句法”和“语义”聚类。它们是完全不同的问题，特别是如果您处于短文本分析领域(当然，Twitter 是短文本分析之王)。

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

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

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

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