Wir suchen "Trolle". Shingle-Algorithmus & Cosinus-Ähnlichkeit

Ich denke, dass viele in den angespannten Diskussionen im Internet Vorwürfen ausgesetzt waren, dass sie Bots, Trolle sind und vom Kreml, Kiew oder Washington bezahlt werden. Aber wie kann man wirklich diejenigen oder nur Menschen identifizieren, die versuchen, ihre Meinung aktiv an die anderen weiterzugeben?



Nehmen Sie zum Beispiel vier Texte (Kommentare):

text_1 = '       ,    '
text_2 = '      ,    ,    '
text_3 = '             '
text_4 = '   ,   ,     ,    '

Aus menschlicher Sicht gibt es definitiv eine Ähnlichkeit in den ersten und zweiten Kommentaren, sie sind über eine Person geschrieben und charakterisieren ihre positiven Aspekte. Und sie haben auch nichts mit den Texten drei und vier zu tun.



Wie kommt man mathematisch zum gleichen Ergebnis?

Es ist kitschig, die Anzahl identischer Wörter in beiden Texten zu vergleichen. Aber das Problem tritt sofort auf - wie kann man die Wörter klug und klug vergleichen ? Die Lemmatisierung von Text ist nicht immer geeignet, da vorgefertigte Bibliotheken nicht viele Sprachen unterstützen.



In solchen Momenten ist es gerechtfertigt, den Shingle-Algorithmus zu verwenden, der den Text von n Teilen aufteilt , deren Größe empirisch für eine bestimmte Aufgabe ausgewählt wird.



Beispiel:







Berechnen wir die Ähnlichkeit des ersten und zweiten / ersten und vierten Textes für n (1.9) nach folgender Formel:

sim = len(set(Shingles_1) & set(Shingles_2)) / len(set(Shingles_1) | set(Shingles_2)))

ShingleSize: 1
0.9166666666666666 / 0.7857142857142857
ShingleSize: 2
0.5196078431372549 / 0.40350877192982454
ShingleSize: 3
0.3404255319148936 / 0.2375
ShingleSize: 4
0.28205128205128205 / 0.18497109826589594 
ShingleSize: 5
0.2289156626506024 / 0.13812154696132597
ShingleSize: 6
0.1896551724137931 / 0.10752688172043011
ShingleSize: 7
0.15730337078651685 / 0.07894736842105263
ShingleSize: 8
0.13333333333333333 / 0.057291666666666664
ShingleSize: 9
0.10989010989010989 / 0.04145077720207254

Ein natürliches Bild mit zunehmender Länge nimmt die Gesamtzahl der Schindeln zu und das Verhältnis der Gesamtschindeln zum Gesamtvolumen ab. Für große Textmengen ist es daher besser, die Länge der Schindeln von 5 bis 8 zu verwenden und bei der Arbeit mit kurzen, z. B. Tweets oder Kommentaren - 2-4.



Aber zurück zum Üben, nehmen wir die vorab gesammelten Daten aus dem beliebten russischen Unterhaltungsportal. Link zu kaggle .



Um die heißesten Diskussionen zu sammeln, wurde das Tag (Abschnitt) - Politik ausgewählt, insgesamt gesammelt:

• 944 Beiträge mit dem Tag Politik
• 267.000 Kommentare zu ihnen
• davon mehr als 100 Zeichen ~ 140 Tausend

Weiter zum Code:



Text löschen und in Schindeln aufteilen:

def clean_text(text):
    text = text.split('\n')
    text = list(filter(None, text))
    text = ' '.join(text)
    text = re.sub(r"http\S+", "", text)
    text = re.sub(r'[^\w\s]', '', text)
    shingle = [text[i:i + ShingleSize] for i in range(len(text))][:-ShingleSize]
    return ','.join(shingle)

Wenn wir nur Kommentare mit mehr als 100 Zeichen verwenden, beträgt die Anzahl der Vergleichsiterationen: $$$140000!/((140000 - 2)!*2! )$Das ist ziemlich viel und die Verarbeitung selbst im Multithread-Modus wird ziemlich lange dauern.



Daher werden wir nicht paarweise vergleichen, sondern mit Matrizen m * n , wobei die Kosinusähnlichkeit verwendet wird,

wobei m die Anzahl der Zeilen ist, die optional abhängig von der RAM-Größe ausgewählt wird, und n die Anzahl der Spalten ist, die Gesamtzahl aller Schindeln;



Implementierung des Algorithmus:

csrMatrix = []
idArray = []
textArray = []
for i in range(ChunkSize, sparse_matrix.shape[0] + ChunkSize, ChunkSize):
    temp = sparse_matrix[i - ChunkSize:i - 1]
    idArray.append(corpusId[i - ChunkSize:i - 1])
    textArray.append(OriginalCorpus[i - ChunkSize:i - 1])
    csrMatrix.append(temp)

matrixCombinations = itertools.combinations_with_replacement(range(len(csrMatrix)), 2)

Mit m = 20.000 und Schindellänge = 8 erhalten wir 7 Matrizen mit einer Größe von 20.000 * ≈8800.000 und damit 21 Vergleichsiterationen. Schon viel besser.

def Sim(A, B, C, D):
    similarities = cosine_similarity(B[A[0]].astype(np.float32), B[A[1]].astype(np.float32))
    x, y = np.where(similarities > similarityPercent)
    res = []
    for k, j in zip(x, y):
        if D[A[0]][k] != D[A[1]][j]:
            res.append((D[A[0]][k], C[A[0]][k], similarities[k][j].item(), D[A[1]][j], C[A[1]][j]))
    return res

s = pool.starmap(Sim, zip(matrixCombinations, itertools.repeat(csrMatrix), itertools.repeat(textArray), itertools.repeat(idArray)))
s = [item for sublist in s for item in sublist]

Um den belegten Speicherplatz zu reduzieren, verwenden wir auch den Datentyp float32. Seine Genauigkeit reicht völlig aus, damit der Algorithmus korrekt funktioniert.



Die Ergebnisse der Arbeit werden zur weiteren Verarbeitung in die MySQL-Datenbank eingegeben. Lassen Sie uns zum Beispiel die Kommentare gruppieren und für jede die Ähnlichkeit mit ihren Paaren zählen:

SELECT FirstText, SUM(sim) as c FROM pikabu.similarity GROUP BY FirstId ORDER BY c DESC

Top-Spiele:

1. Kommentar wurde gelöscht. Grund: Dieses Konto wurde gelöscht.
2. Kommentar wurde gelöscht. Grund: Beleidigung der Benutzer.
3. Kommentar wurde gelöscht. Grund: Beleidigungen, unhöfliche Kommunikation und Provokationen.
4. Kommentar wurde gelöscht. Grund: Es ist verboten, Kommentare zu veröffentlichen, deren einziger Zweck darin besteht, Feindseligkeit oder Anstiftung zur Feindseligkeit zu verursachen, und Kommentare mit Aufrufen zu Gewalt oder Belästigung sind verboten.

Die Standardsituation für die politische Diskussion im Internet.



Wenn wir Links, Nachrichten von der Verwaltung und anderes Rauschen verwerfen, gehen wir direkt zur Analyse der semantischen Last von Kommentaren:





Innerhalb von fünf Minuten schrieb ein Mann 8 identische Nachrichten zum gleichen Thema über die Ereignisse in Belarus. Insgesamt wurden 260 Nachrichten dieses Autors in die Datenbank aufgenommen. Ein kurzer Blick auf sie macht deutlich, dass die Situation in Belarus offensichtlich negativ ist. Der Benutzer selbst ist der Kurve voraus und nennt die Bots seines Gegners als Argumente.



Und sein Bruder war Beobachter bei den Wahlen:



DaimosShip, 2020-08-18 22:52:41

Mein Bruder war Beobachter - sie durften nirgendwo hin





Der Autor ist eindeutig ein Fan der deutschen historischen Literatur





Der Mann sucht nach Spuren der Trollfabrik. Hallo Kollege.







Die angegebenen Beispiele befanden sich an der Oberfläche. Um engere Beziehungen zu identifizieren, muss der Datensatz um eine Größenordnung erweitert werden, nicht nur um die Informationsmenge, sondern auch um Zeitintervalle. Auf diese Weise können die Schlüsselthemen, um die sich die Diskussionen drehen, ihre Initiatoren genauer identifiziert, die Zeitstempel der Ereignisse und ihre Korrelation analysiert werden.

Aber selbst an einem solchen Set können Sie mit einer detaillierten manuellen Analyse, beispielsweise unter Berücksichtigung einzelner Verbindungen, etwas Interessantes finden, das Anlass zum Nachdenken und zur weiteren Arbeit gibt.



GitHub



PS Die Verarbeitung der Matrix 140.000 * 8800000 dauerte auf dem rayzen 5 1600-Prozessor ca. 7 Minuten.



In Zukunft möchte ich dieses Thema fortsetzen. Ich freue mich über Kritik und Vorschläge.