2

假设文本文件中有一个 URL 列表（以百万为单位），并且文本文件中有另一个列表，其中包含列入黑名单的单词。

我愿意对 URL 列表做如下处理。

- Parse the URLs and store them in some DS
- Process the URLs and blacklist those URLs which contain atleast one of the 
  blacklisted words.
- If there exists a URL containing 50% or more blacklisted words, add the other 
  words of that URL in the list of blacklisted words.
- Since now the blacklisted words list has been modified then it's probable 
  that the URLs which were not blacklisted earlier can get blacklisted now. So, 
  the algorithm should handle this case as well and mark the earlier whitelisted 
  URLs as blacklisted if they contain these newly added blacklisted words.

最后，我应该有一个列入白名单的 URL 列表

有什么建议可以用来实现最有效的时间和空间复杂度解决方案的最佳算法和 DS 吗？

4

2 回答 2

1

使用矩阵来存储 URL。

  1. 首先，通过Porter Stemmer将每个 URL 分解为单词，并将它们放入矩阵中（一个 URL 一行，一个单词一个项目）。

  2. 然后使用TFIDF对矩阵中的每个词进行评分，并删除低分词（它们将是流行词，如 'a'、'the' 等，对于判断垃圾邮件没有信息）。

  3. 手动初始化黑名单（把一些常用的黑字放进去）。

  4. 只需按照您给定的方式运行该过程。

于 2012-12-15T09:10:51.627 回答
1

我将只回答这个问题的机器学习部分，并让数据结构/高效文本匹配的东西保持开放。

首先，如果不确定性是一个问题，您可以在更新之前使用给定版本的黑名单/分类器对数据进行完整的传递。这样，无论输入的顺序如何，您都会得到相同的答案。另一方面，我认为决定论不应该被看重。在机器学习中，随机梯度下降不是顺序不变的，但它在实践中表现良好，尤其是在大型数据集上。

其次，您可能想要小心使用直接的黑名单，除非您愿意手动过滤提议的候选术语（甚至可能仍然如此），并且可能想要使用更柔和的概率方法。朴素贝叶斯是可以合理工作的最简单的方法。例如，这可能会让您将有关伟哥的医学文章标记为非垃圾邮件，即使它包含垃圾邮件词，因为它来自非常受信任的主机（如 webmd）。

您可以使用您手动选择的黑名单术语来生成一组初始的带有负面标签的 URL。然后你可以想出另一组正标签（甚至可能从你的语料库中随机挑选，假设它大多是好的），并用它来训练一个初始的朴素贝叶斯分类器。然后，您可以利用您的想法，通过进行半监督学习，根据特定语料库上的分类器自己的输出来更改分类器。这将从一小部分初始标记文档中为您提供良好的学习/雪崩效果。

于 2012-12-15T17:33:10.113 回答