在100万个用户名中,尽可能找出机器自动创建的用户名。
其实就是反spam比较简单的一种。有些人说拿每个用户名取google或baidu搜索下看看有没有上网痕迹。先不说这个靠不靠谱,出题人明显是想从算法角度去解决此问题,而非社会工程学,所以那些就算了。我开始想了个对100万个用户名先进行分词,然后统计每个词在这100万个用户名中出现的次数,也就是统计词频。然后按照词频进行倒排序,取top n。接下来就在那100万个用户名中找出包含top n中出现的词。这些很可能就是机器创建的。但后来想这么做并不科学,可能会误杀一大片正常用户名。因为在每个时间段都会出现一些热词,很多人喜欢用这些热词作为用户名的一部分。或者是某些经典词,可能会被大部分人使用。因此我觉得除非可以人工参与进来找出一些热词。将热词从top n中排除。否则这个方法一点也不好。
想看看大家有什么想法,一起讨论下。注意,此命题说了只能针对用户名,而不能去对用户发言或注册日期之类的做处理。

解决方案 »

  1.   

    就拿csdn的用户库来试手上还有100M+的那个库。目前觉得靠谱点的就是 某些字符 + 数字,并且数字是顺着一直下去的。
      

  2.   

    这个用算法无解...ci169
    ci1699
    ci16999
    ci169999
    ci1699999就像上面这几个CSDN账号哪个是机器注册能算出来嘛。
      

  3.   

    首先想下如果我们自己来写注册脚本,我们会用什么方法创建用户名。最重要的一点是什么?肯定是尽量避免重复。我觉得其他的都不重要,很少注册机会想要去迷惑管理员自己不是机器人的吧?首先我们肯定会用个特定的前缀或包含一个特定的公共字符串,这样和别人重复的几率就会降低,并且易于我们自己管理,有如namespace。后面可能会跟一些顺序号,或者是一些随机字符。我觉得仅仅从用户名上去考虑,也只有特定前缀或公共字符串可以拿来利用,因为顺序号是不能说明什么问题的。我们也没什么规律可循。所以找包含高词频词的用户名应该是比较靠谱的一种方法。只不过这一个维度肯定还不够。
    应该加入搜索引擎经常用到的停词概念。比如在某个时段,某些词属于热词,就像最近“2012”、“末日”肯定是个热词,那么用它们进行注册的人一定会比以往多。那么在特征样本中(top n),就应该把这类词排除出去。看了下反spam经常使用的贝叶斯分类,只看懂了个大概。具体的实在看不懂。
    大概意思貌似也是对现有数据做分析,建立特征样本,然后再与每个实例进行比较。貌似和我想的那种方法有一点点类似。
      

  4.   

    有意思的题目,有没有什么免费LAMP空间?上传一份,大家来攻破一下。
    'tom'.substr(str_shuffle("abcdefghijklmnopqrstuvwxyz"), 0, 4);
      

  5.   

    使用 贝叶斯分类 应该只正路,只是如何组织原始数据是个问题
    在有众多不确定因素的前提下就贸然提及算法有点不妥
    建议你先使用 weka(一个java的数据挖掘软件)做一下探测