algorithm - 根据他使用的词来发现多个不同用户帐户背后的用户

Question

我想创建算法来区分论坛上以不同昵称写作的人。

目标是发现人们匿名注册新帐户到 flame 论坛，而不是在他们的主帐户下。

基本上我在考虑提取他们使用的词并根据相似性或这些词来比较用户。

如图所示，用户 3 和用户 4 使用相同的单词。这意味着计算机后面可能有一个人。

很明显，所有用户都在使用很多常用词。所以我应该关注“用户特定”的词。

输入是(与上图相关):

<word1, user1>
<word2, user1>
<word2, user2>
<word3, user2>
<word4, user2>
<word5, user3>
<word5, user4>
... etc. The order doesnt matter

输出应该是:

user1
user2
user3 = user4

我正在用 Java 做这件事，但我希望这个问题与语言无关。

有什么想法吗？

1) 如何存储单词/用户？什么数据结构？

2) 如何摆脱每个人都使用的常用词？我不得不以某种方式在用户特定的单词中忽略它们。也许我可以忽略它们，因为它们会迷路。恐怕他们会隐藏“用户特定词”的显着差异

3) 如何识别同一用户？ - 以某种方式计算每个用户之间的相同单词？

我非常感谢提前提出的每一个建议。

Answer 1

一般来说，这是作者识别的任务，有几篇好论文，如this这可能会给你很多信息。以下是我对这个话题的建议。

<强>1。用户识别/作者识别本身

最简单的文本分类是按主题分类，首先要选择有意义的词。也就是说，如果你想区分关于 Apple 公司和 apple 水果的文本，你会计算“吃”、“橙子”、“iPhone”等词，但你通常会忽略诸如冠词、词形、部分等词词性 (POS) 信息等。然而，很多人可能会谈论相同的话题，但使用不同的演讲风格，即文章、词语形式以及按主题分类时您忽略的所有内容。因此，您应该考虑的第一件事也是最主要的事情是为您的算法收集最有用的特征。作者的风格可以通过“a”和“the”等词的出现频率、POS 信息(例如，有些人倾向于使用现在时间，其他人倾向于使用 future 时间)、常用短语(“I would like”与“I'd喜欢”与“我想要”)等等。请注意，不应完全丢弃主题词 - 它们仍然显示用户感兴趣的主题。但是您应该以某种方式特殊对待它们，例如您可以按主题对文本进行预分类，然后区分对其不感兴趣的用户。

当您完成特征收集后，您可以使用一种机器学习算法来找到文本作者的最佳猜测。至于我，这里的 2 个最佳建议是概率和 cosine similarity文本向量和用户的公共(public)向量之间。

<强>2。区分常用词

或者，在最近的上下文中，共同特征。我能想到的摆脱所有人或多或少平等使用的词的最好方法是为每个这样的特征计算熵:

entropy(x) = -sum(P(Ui|x) * log(P(Ui|x)))

其中 x 是特征，U - 用户，P(Ui|x) - 第 i 个用户给定特征的条件概率x，sum 是所有用户的总和。

熵值高表示该特征的分布接近均匀，因此几乎没有用。

<强>3。数据表示

这里常用的方法是使用用户特征矩阵。也就是说，您只需构建表，其中行是用户 ID，列是功能。例如。单元格 [3][12] 显示归一化的用户 #3 使用功能 #12 的次数(不要忘记根据用户使用过的功能总数对这些频率进行归一化!)。

根据您要使用的特征和矩阵的大小，您可能希望使用稀疏矩阵实现而不是密集矩阵。例如。如果您使用 1000 个特征并且对于每个特定用户，大约 90% 的单元格是 0，将所有这些零保留在内存中没有意义，稀疏实现是更好的选择。