2010-06-07 6 views
3

Je construis un site web en python/django et je veux prédire si une soumission d'utilisateur est valide ou s'il s'agit d'un spam.Calcul de la probabilité de spam

Les utilisateurs ont un taux d'acceptation sur leurs soumissions, comme ce site a.

Les utilisateurs peuvent modérer les soumissions d'autres utilisateurs; et ces modérations sont ensuite métamodifiées par un administrateur.

Compte tenu de ceci:

  • l'utilisateur enregistré A avec une soumission accepte taux de 60% soumet quelque chose.
  • L'utilisateur B modère le message de A comme soumission valide. Cependant, l'utilisateur B a tort 70% du temps.
  • L'utilisateur C modère la publication de A comme spam. L'utilisateur C a généralement raison. Si l'utilisateur C dit quelque chose est spam/pas de spam, ce sera correct 80% du temps.

Comment puis-je prédire la probabilité que le message de A soit du spam?

Edit: J'ai fait un script python simulant ce scénario:

#!/usr/bin/env python 

import random 

def submit(p): 
    """Return 'ham' with (p*100)% probability""" 
    return 'ham' if random.random() < p else 'spam' 

def moderate(p, ham_or_spam): 
    """Moderate ham as ham and spam as spam with (p*100)% probability""" 
    if ham_or_spam == 'spam': 
     return 'spam' if random.random() < p else 'ham' 
    if ham_or_spam == 'ham': 
     return 'ham' if random.random() < p else 'spam' 

NUMBER_OF_SUBMISSIONS = 100000 
USER_A_HAM_RATIO = 0.6 # Will submit 60% ham 
USER_B_PRECISION = 0.3 # Will moderate a submission correctly 30% of the time 
USER_C_PRECISION = 0.8 # Will moderate a submission correctly 80% of the time 

user_a_submissions = [submit(USER_A_HAM_RATIO) \ 
         for i in xrange(NUMBER_OF_SUBMISSIONS)] 

print "User A has made %d submissions. %d of them are 'ham'." \ 
     % (len(user_a_submissions), user_a_submissions.count('ham')) 

user_b_moderations = [ moderate(USER_B_PRECISION, ham_or_spam) \ 
         for ham_or_spam in user_a_submissions] 

user_b_moderations_which_are_correct = \ 
    [i for i, j in zip(user_a_submissions, user_b_moderations) if i == j] 

print "User B has correctly moderated %d submissions." % \ 
    len(user_b_moderations_which_are_correct) 

user_c_moderations = [ moderate(USER_C_PRECISION, ham_or_spam) \ 
         for ham_or_spam in user_a_submissions] 

user_c_moderations_which_are_correct = \ 
    [i for i, j in zip(user_a_submissions, user_c_moderations) if i == j] 

print "User C has correctly moderated %d submissions." % \ 
    len(user_c_moderations_which_are_correct) 

i = 0 
j = 0  
k = 0 
for a, b, c in zip(user_a_submissions, user_b_moderations, user_c_moderations): 
    if b == 'spam' and c == 'ham': 
     i += 1 
     if a == 'spam': 
      j += 1 
     elif a == "ham": 
      k += 1 

print "'spam' was identified as 'spam' by user B and 'ham' by user C %d times." % j 
print "'ham' was identified as 'spam' by user B and 'ham' by user C %d times." % k 
print "If user B says it's spam and user C says it's ham, it will be spam \ 
     %.2f percent of the time, and ham %.2f percent of the time." % \ 
     (float(j)/i*100, float(k)/i*100) 

L'exécution du script me donne cette sortie:

  • utilisateur A a fait 100000 soumissions. 60194 d'entre eux sont «jambon».
  • L'utilisateur B a correctement modéré 29864 soumissions.
  • L'utilisateur C a correctement modéré 79990 soumissions.
  • 'spam' a été identifié comme 'spam' par l'utilisateur B et 'ham' par l'utilisateur C 2346 fois.
  • 'ham' a été identifié comme 'spam' par l'utilisateur B et 'ham' par l'utilisateur C 33634 fois.
  • Si l'utilisateur B dit que c'est du spam et que l'utilisateur C dit que c'est du jambon, ce sera du spam 6,52% du temps, et du jambon 93,48% du temps.

La probabilité ici est-elle raisonnable? Serait-ce la bonne façon de simuler le scénario?

+0

14,4% que ce n'est pas un spam ;-) – Boldewyn

Répondre

5

Bayes' Theorem nous dit:

<code>P(A|B)=P(B|A)P(A)/P(B)</code>

Changeons les lettres pour les événements A et B à X et Y resp. parce que vous utilisez A, B et C représentent les gens, et il rendrait les choses confuses:

P(X|Y) = P(Y|X) P(X)/P(Y) 

Modifier: ce qui suit est un peu mal parce X devrait être this post _by A_ is spam, pas seulement « ce poste est spam "(et donc Y devrait juste être" B accepte le message de A, C le rejette "). Je ne refais pas le calcul ici parce que les nombres sont changés de toute façon - voir autre édition ci-dessous pour le bon nombre et l'arithmétique correcte.

Vous voulez X à dire « ce post est un spam », Y à tenir pour la combinaison de circonstances A has posted it, B approved it, C rejected it (et supposons que l'indépendance conditionnelle des circonstances en question).

Nous avons besoin de P(X), la probabilité a priori que n'importe quel message (peu importe qui le fait ou l'approuve) soit du spam; P(Y), la probabilité a priori qu'une publication soit faite par A, approuvée par B, rejetée par C (spam ou non); et P(Y | X), identique à ce dernier mais avec le message étant spam.

Comme vous pouvez le remarquer, vous ne nous avez pas vraiment donné tous les éléments dont nous avons besoin pour le calcul. Vous nous dites trois points: un message donné par A est du spam avec une probabilité de 0.4 (cela semble être la façon dont le premier point se lit); La probabilité d'acceptation de B est de 0,3 mais nous n'avons aucune idée de ce qui diffère pour le spam et le non-spam, sauf qu'il devrait y avoir une différence "faible" (faible précision); C est 0,8 et encore une fois nous ne savons pas comment cela est influencé par le spam par rapport à non-spam, sauf qu'il devrait y avoir une différence "importante" (haute précision).

Nous avons donc besoin de plus de chiffres! Le fait que C ait une grande précision en acceptant 80% des messages nous indique que le spam global doit être étonnamment bas - si le spam globalement était le même 40% que pour A, alors C devrait en accepter la moitié (même s'il était parfait en acceptant toujours le non-spam) pour obtenir le taux global d'acceptation de 80%, et ce serait à peine "haute précision". Donc, disons que le spam total n'est que de 20% et que C n'en accepte qu'un quart (et rejette 1/16 du non-spam), une très bonne précision en effet et correspondant globalement aux chiffres que vous donnez. Devinant pour B, qui accepte à 30% au total, et maintenant "sachant" que le spam est globalement de 20%, on peut supposer que B accepte 1/4 du spam et seulement 5/16 du non-spam.

Ainsi: P(X)=0.2; P(Y)=0.3*0.2=0.06 (temps d'acceptation global de B temps de rejet de C); P(Y|X)=0.4*0.25*0.75=0.075 (Problème d'A du temps de Spam Le problème de B d'accepter le temps de Spam Le problème de C de rejeter le Spam). - P(X|Y)=0.075*0.2/0.06=0.25 - sauf si j'ai fait une erreur d'arithmétique (tout à fait possible, le but est surtout de vous montrer comment on peut raisonner dans de tels cas ;-), la probabilité que ce message soit un spam est de 0,25 - un peu plus élevé que la probabilité d'un message aléatoire étant spam, inférieur à la probabilité d'un poste aléatoire par A étant spam. Mais bien sûr (même dans l'hypothèse simplificatrice de l'indépendance conditionnelle), ce calcul est très sensible à mes suppositions/hypothèses sur les rapports entre faux positifs et faux négatifs pour B et C, et l'ensemble taux de spamIl y a cinq nombres de ce type impliqués (prob de spam global, prob pour B et C pour spam et non-spam) et vous ne nous donnez que deux contraintes (linéaires) pertinentes (prob inconditionnel d'acceptation pour B et C) et deux vagues affirmations "handwaving" (sur la basse et la haute précision), il y a donc beaucoup de degrés de liberté là-bas.

Si vous pouvez mieux estimer les cinq nombres clés, le calcul peut être rendu plus précis. Et, BTW, Python (et a fortiori Django) n'ont absolument rien à voir avec le cas - je vous recommande de supprimer ces balises non pertinentes pour obtenir une plus large gamme de réponses!

Modifier: les clarifie utilisateurs (dans un commentaire - SHD vraiment modifier son Q!):

Quand je dit "les modérations de B acceptent taux est seulement 30%" Je veux dire que pour tous les dix temps B modère quelque chose spam/aucun spam il fait le mal décision 7 fois. Il y a donc 70% chance qu'il va marquer quelque chose de spam/non spam quand ce n'est pas le cas. Pour l'utilisateur C, "His moderations 'accepter taux est de 80%" signifie que si C dit quelque chose est un spam ou non spam, il a raison 80% du temps. Les chances globales d'un utilisateur enregistré spamming est de 20%.

... et me demande de refaire le calcul (je suppose que les faux positifs et les négatifs sont également probables pour chacun de B et C). Notez que B est un excellent "indicateur contrarian", puisqu'il se trompe 70% du temps! -).

Quoi qu'il en soit: le taux d'acceptation global de A des postes A doit alors être 0.6 * 0.3 (quand il accepte le non-spam de A) + 0.4 * 0.7 (quand il accepte le spam de A) = 0.18 + 0.28 = 0.46; C doit être 0,8 * 0,4 + 0,2 * 0,6 = 0,32 + 0,12 = 0,44. Nous avons donc ...:

P(X)=0.4 (je l'avais mal à 0,2 avant depuis que je suis en ignorant le fait que Une probabilité de de spamming est de 0,4 - le prob global du spam n'est pas pertinent, puisque nous savons que le poste est A!); P(Y)=0.46*0.56=0.2576 (taux d'acceptation global de B pour le probème de rejet de A fois C pour A); P(Y|X)=0.7*0.8=0.56 (Problème de B d'accepter le temps de spam C problème de rejet de spam).

Donc P(X|Y)=0.56*0.4/0.2576=0.87 (arrondi). IOW: alors qu'à priori la probabilité qu'un message de A soit un spam est de 0.4, l'acceptation de B et le rejet de C l'augmentent, donc cet article spécifique de a environ 87% de chance d'être un spam.

+0

Je recommande d'examiner ma réponse concernant la précision dans la mise en œuvre de la loi de Bayes. http://stackoverflow.com/questions/2691021/problem-with-precision-floating-point-operation-in-c – Jacob

+0

@Jacob, avec le petit nombre d'opérations dont le PO a besoin, je ne pense pas que ce soit un problème cas (bien que l'utilisation de journaux est loin d'être une mauvaise idée). Si l'arithmétique de haute précision est souhaitée, GMP, MPIR & c sont toujours disponibles (et enveloppés dans 'gmpy' si l'OP veut utiliser Python, comme il l'a indiqué à l'origine - bien que je l'ait convaincu de supprimer cette balise trouver la bonne formule, donc s'inquiéter des problèmes numériques et de programmation dans _implementing_ cette formule est un peu prématuré - "séparation des préoccupations" est conseillé à la place ;-). –

+0

@alex - J'apprécierais beaucoup si vous pouviez refaire les arithmétiques - ma tête nage! :-) Je trouve plus facile d'apprendre par des exemples avec des nombres réels plutôt que de lire l'algorithme. – Hobhouse

2

On pourrait utiliser la classification bayésienne pour détecter le spam et sélectionner vos ensembles d'entraînement pour le spam et le jambon en fonction des résultats de la modification. Les résultats pourraient également être pondérés par le taux de messages acceptés par l'utilisateur.

Les résultats avec une forte probabilité d'être un spam pourraient être poussés dans un flux de travail de modération (si vous avez des modérateurs dédiés). De même, un échantillon de résultats d'anciennes modérations pourrait être soumis à un workflow de méta-modération pour avoir une vue sur la qualité de la classification (à savoir, nous avons un taux inacceptablement élevé de faux positifs et de négatifs). Enfin, un 'appel' où un utilisateur pourrait se plaindre d'affichages injustement classifiés pourrait également pousser des écritures dans un flux de travail de méta-modération. Si l'utilisateur a des antécédents de rejet en appel ou des taux excessivement élevés d'appels de soumission (peut-être une tentative d'attaque DOS), leurs messages peuvent être affectés de moins en moins de priorité dans le flux de travail des appels.

-1

Nous y allons plus empiriquement.

Nous avons trouvé que l'un des meilleurs indicateurs de spam est le nombre de liens externes dans un article/commentaire, puisque tout le but du spam est de vous faire aller quelque part et acheter quelque chose et/ou faire l'amical googlebot pense que la page liée est plus intéressante.

Nos règles générales pour utilisateurs non enregistrés sont: 1 lien pourrait être OK, 2 est 80% + probablement spam, 3 ou plus et ils sont toast. Nous gardons une liste des principaux noms de domaine qui apparaissent dans les publications rejetées et ceux-ci deviennent des déclencheurs même si dans un éditeur de liens 1 ou 2. Vous pouvez également utiliser un RBL, mais attention car ils peuvent être vraiment draconiens.

Quelque chose d'aussi simple pourrait ne pas fonctionner pour vous, mais cela a drastiquement réduit la charge sur nos modérateurs et nous n'avons eu aucune plainte de vrais humains.