2

我想知道有效的算法/数据结构来识别流数据中的以下信息。

考虑像 twitter 这样的实时流数据。我主要对以下查询感兴趣,而不是存储实际数据。

我需要我的查询在实际数据上运行,而不是在任何重复数据上运行。

由于我对存储完整数据不感兴趣,因此我很难识别重复的帖子。但是,我可以散列所有帖子并检查它们。但我也想找出几乎重复的帖子。我怎样才能做到这一点。

确定用户讨论的前 k 个主题。

我想确定用户讨论的热门话题。我不想要 twitter 显示的高频词。相反,我想给出一些最常用词的高级主题名称。

我希望我的系统是实时的。我的意思是,我的系统应该能够处理任何数量的流量。

我可以想到 map reduce 方法,但我不确定如何处理同步问题。例如,重复的帖子可以到达不同的节点,并且它们都可以将它们存储在索引中。

在典型的新闻源中,将删除数据中的所有停用词。在我的系统中,我想通过识别各种主题中最常见的词来更新我的停用词列表。

什么是有效的算法/数据结构来实现这一点。

我想在一段时间内存储主题以检索数据中有趣的模式。比如说,星期五晚上每个人都想去看电影。存储这些数据的有效方法是什么。

我正在考虑将它存储在 hadoop 分布式文件系统中,但是随着时间的推移,这些索引变得如此之大,以至于 I/O 将成为我的主要瓶颈。

考虑来自世界各地推文的多语言数据。如何识别跨地理区域正在讨论的类似主题?

这里有2个问题。一是识别正在使用的语言。它可以根据发推文的人来识别。但是这些信息可能会影响用户的隐私。其他想法,可以通过训练算法运行它。目前为此遵循的最佳方法是什么。其他问题实际上是在字典中查找单词并将其与常见的中间语言相关联,例如说英语。如何处理词义消歧,就像在不同比赛中使用同一个词一样。

识别单词边界

一种可能性是使用某种训练算法。但是最好的方法是什么。这在某种程度上类似于词义消歧,因为您将能够根据实际句子识别词边界。

我正在考虑开发一个原型并评估系统,而不是具体的实现。我认为不可能废弃实时推特数据。我认为这种方法可以在一些在线免费提供的数据上进行测试。任何想法,我可以在哪里获得这些数据。

感谢您的反馈。

谢谢你的时间。

——巴拉

4

3 回答 3

1

这里隐藏着几个不同的问题。我无法理解您要问的所有问题,但据我所知,这是一个重要的问题:您想按主题对消息进行分类。您还想删除重复项。

删除重复项(相对)容易。要删除“接近”重复项,您可以首先从数据中删除不感兴趣的部分。您可以从删除大写和标点符号开始。您还可以删除最常用的单词。然后,您可以将生成的消息添加到 Bloom 过滤器。散列对于 Twitter 来说还不够好,因为散列的消息不会比完整消息小很多。你最终会得到一个不适合内存的哈希值。这就是为什么您要改用 Bloom 过滤器的原因。它可能必须是一个非常大的布隆过滤器,但它仍然会比哈希表小。

另一部分是一个困难的分类问题。你可能不想自己写这部分。有许多库和程序可用于分类,但可能很难找到适合您需求的库和程序。一个例子是 Vowpal Wabbit 项目,它是一种用于分类的快速在线算法。但是,它一次只适用于一个类别。对于多个类别,您必须运行多个副本并分别训练它们。

识别语言听起来不那么困难。不要尝试做一些聪明的事情,比如“训练”,而是将每种语言中最常用的单词放入字典中。对于每条消息,使用出现频率最高的语言。

如果您希望算法自己提出类别,祝您好运。

于 2010-01-22T04:27:27.697 回答
0

我不确定我是否在回答您的主要问题,但您可以通过计算两条消息之间的Levenshtein 距离来确定它们的相似性。您可以将其视为两个字符串之间的“编辑差异”(IE,需要对一个字符串进行多少次编辑,才能将其转换为另一个字符串)。

于 2010-01-22T04:03:04.277 回答
0

您好,我们使用api.cortical.io功能创建了一个非常相似的演示。在那里,您可以创建每条推文的语义指纹。(您还可以提取最重要的关键字或一些类似的术语,它们实际上不需要成为推文的一部分)。我们使用指纹根据内容过滤 twitter 流。在twistiller.com 上,您可以看到结果。公开的 1% 推特流针对四个不同的主题领域进行监控。

于 2014-11-12T21:37:23.483 回答