Игнорирование поддельных имен пользователей

Question

Итак, я использую api, который возвращает мне имена пользователей. В них есть некоторые поддельные, такие как:

8spZKYf1t2 
xOzJzaYJe2 
0x5jD4xmTM 
PJFBoDFJsW 
UZV908nNF7 
CRuMGgh1bM 
lyhDRamtFf 
wELYyunHZU 
NC8ZbYCjig 
plK2KtwQwE 
EKRlRLRitP 
0CULcA8lIR 
Yyi2NV3P8n 

Кто-нибудь знает хороший алгоритм, чтобы игнорировать их?

Answer 1

Вам понадобится база данных имен пользователей, чтобы узнать разницу между реальными и поддельными. Назовите этот «тренировочный комплект»:

1. Из учебного набора подсчитайте количество вхождений для каждой комбинации из трех букв. Например, из «mtimmerm» вы добавили счетчики для «mti», «tim», «imm» и т. Д. Пусть N(x) будет количеством отсчетов для x в обучающем наборе, и пусть TOTAL будет общее число counts , Пусть F(x) = (N(x)+1)/(TOTAL+1) Это будет наша оценка частоты, с которой эта 3-буквенная комбинация встречается в именах пользователей.

2. Учитывая кандидат имя пользователя U, для каждых 3-буквенных комбинаций x в U, вычислить H (х) = -log (F (X)). Добавьте все это вместе и разделите на length(U)-2 (количество комбинаций), чтобы получить H(U). Это показатель того, насколько «нереалистичным» является U.

Вычислить H(U) для связки имен пользователей, и вы должны найти, что гораздо выше, поддельные.

Если вы хотите, чтобы изучить теорию позади, как это работает, слово Google является «Энтропия»: https://en.wikipedia.org/wiki/Entropy_(information_theory)

То, что мы делаем, это делает статистическую модель для имен пользователей, а затем вычисления, как «необычно» каждый имя пользователя соответствует этой модели. Это на самом деле показатель того, сколько бит потребуется для хранения имени пользователя, если мы использовали нашу модель для сжатия (вроде - я упростил вычисления, но они должны быть достаточно точными относительно друг друга). Случайно сгенерированные имена пользователей (которые мы предполагаем, являются фальшивыми) будут содержать больше информации для хранения, чем реальные.

ПРИМЕЧАНИЕ: это хорошо, если набор тренировок не содержит поддельных имен пользователей, но он не будет слишком сильно отличаться, если большинство из них являются реальными. Также обратите внимание, что не совсем правильно тестировать имена от учебного набора. Если вы собираетесь тестировать имена из набора тренировок, то вычитайте 1/(TOTAL+1) из каждого F(X), поэтому собственные подсчеты имени пользователя не включаются при его тестировании.