Dan*_*Dan 2 cluster-analysis hierarchical-clustering data-mining
我对聚类和相关主题相当新,所以请原谅我的问题.
我试图通过做一些测试来介绍这个领域,作为第一个实验,我想根据内容相似性在推文上创建集群.实验的基本思想是将推文存储在数据库上并定期计算聚类(即使用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得分是......").另请注意,我希望这与语言无关,所以我对处理特定语言问题不感兴趣.
在我看来,你试图解决两个不同的问题,即"句法"和"语义"聚类.它们是完全不同的问题,特别是如果你处于短文本分析领域(当然,Twitter是短文本分析的王者).
"语法"聚类意味着聚合来自同一来源的推文.您的Foursquare示例非常适合,但转发,人们共享在线报纸文章或博客文章以及许多其他案例也很常见.对于这种类型的问题,使用N-gram模型几乎是强制性的,正如你所说的(我的经验表明N = 2对推文有好处,因为你可以找到有3-4个特征的重要推文).规范化也是一个重要的因素,删除RT标记,提及,标签可能会有所帮助.
"语义"聚类意味着聚合共享相同主题的推文.这是一个更加困难的问题,如果你试图聚合随机的推文样本,由于它们通常携带的信息太少,它不会起作用.但是,如果您将域限制为特定的推文子集(即匹配关键字或主题标签的子集),这些技术可能会起作用.LSA在这里可能很有用,但它对句法集群没用.
根据你的观察,我认为你想要的是语法聚类.但是,您最大的问题是您需要在线群集,而不是静态群集.在静态情况下运行良好的经典聚类算法(如层次聚类或联合查找)并不适合在线聚类,除非每次将新推文添加到数据库时从头开始重做聚类.根据我的经验,"平均"集群以添加新元素并不是一个很好的解决方案,因为每次新数据进入时都需要保留每个集群成员的所有信息以更新"平均".此外,算法如分层聚类和联合找到工作很好,因为如果在它们之间找到相似性的链接,它们可以加入预先存在的聚类,
像MinHash(或SimHash)这样的算法确实更适合在线聚类,因为它们支持对类似文档进行"查询"的想法.MinHash本质上是一种获取超过某个相似阈值的文档对的方法(特别是MinHash可以被认为是Jaccard相似度的估计),而不必像成对比较那样依赖二次算法(事实上,O(nlog(n))及时).但是,它在空间上是二次的,因此MinHash的仅内存实现仅对小型集合有用(例如10000条推文).但是,在您的情况下,在数据库中保存您的推文的"草图"(即通过最小化一段推文获得的哈希集)以形成"索引"并查询新的草图是有用的.那个指数.然后,您可以通过在匹配相似性查询的顶点(推文)之间添加边来形成相似性图.图表的已连接组件将是您的群集.