Buscamos "Trolls". Algoritmo de tejas y similitud de coseno

Creo que muchos en las tensas discusiones en Internet se han enfrentado a acusaciones de personas de que son bots, trolls y pagados por el Kremlin, Kiev o Washington. Pero, ¿cómo identificar realmente a esas personas que intentan transmitir activamente su opinión al resto?



Tomemos, por ejemplo, cuatro textos (comentarios):

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

Desde un punto de vista humano, definitivamente hay una similitud en el primer y segundo comentario, están escritos sobre una persona y caracterizan sus aspectos positivos. Y tampoco tienen nada que ver con los textos tres y cuatro.



¿Cómo se llega al mismo resultado matemáticamente?

Es cursi comparar el número de palabras idénticas en ambos textos. Pero el problema surge de inmediato: ¿cómo comparar las palabras inteligente e inteligente ? La lematización de texto no siempre es adecuada, ya que las bibliotecas prefabricadas no admiten muchos idiomas.



En esos momentos, se justifica utilizar el algoritmo Shingle que divide el texto en n partes, cuyo tamaño se selecciona empíricamente para una tarea específica.



Ejemplo:







Calculemos la similitud del primer y segundo / primer y cuarto texto para n (1.9) mediante la fórmula:

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

Una imagen natural, con un aumento en la longitud, el número total de tejas aumenta y la relación entre el total de tejas y el volumen total disminuye. Entonces, para grandes cantidades de textos, es mejor usar la longitud de las tejas de 5 a 8, y cuando se trabaja con textos cortos, por ejemplo, tweets o comentarios, 2-4.



Pero volvamos a la práctica, tomemos los datos recopilados previamente del popular portal de entretenimiento ruso. Enlace a kaggle .



Para recopilar las discusiones más acaloradas, se eligió la etiqueta (sección) - Política, total recopilado:

• 944 publicaciones etiquetadas política
• 267.000 comentarios para ellos
• de los cuales más de 100 caracteres ~ 140 mil

Pasando al código:



borrar texto y dividir en tejas:

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)

Si solo tomamos comentarios de más de 100 caracteres, entonces el número de iteraciones de comparación es: $$$140000!/((140000 - 2)!*2! )$, que es bastante y el procesamiento incluso en el modo de subprocesos múltiples llevará bastante tiempo.



Por lo tanto, no compararemos en pares, sino con matrices m * n , usando similitud de coseno

donde m es el número de filas, que se selecciona opcionalmente según la cantidad de RAM, yn es el número de columnas, el número total de todas las tejas;



Implementación del algoritmo:

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)

Con m = 20,000 y la longitud de la teja = 8, obtenemos 7 matrices de 20,000 * ≈8800,000 de tamaño y, por lo tanto, 21 iteraciones de comparación. Mucho mejor ya.

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]

Para reducir el espacio ocupado, también usamos el tipo de datos float32. Su precisión es suficiente para que el algoritmo funcione correctamente.



Los resultados del trabajo se ingresan en la base de datos MySQL para su posterior procesamiento. Entonces, por ejemplo, agrupemos los comentarios, contando para cada uno la similitud con sus pares:

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

Mejores partidos:

1. El comentario ha sido eliminado. Motivo: esta cuenta ha sido eliminada.
2. El comentario ha sido eliminado. Razón: insultar a los usuarios.
3. El comentario ha sido eliminado. Motivo: insultos, comunicación grosera y provocaciones.
4. El comentario ha sido eliminado. Razón: Está prohibido publicar comentarios cuyo único propósito sea provocar hostilidad o incitación a la hostilidad, y los comentarios con llamadas a la violencia o el acoso están prohibidos.

La situación estándar para la discusión política en Internet.



Descartando enlaces, mensajes de la administración, y otros ruidos, pasamos directamente al análisis de la carga semántica de comentarios:





En cinco minutos, un hombre escribió 8 mensajes idénticos sobre el mismo tema sobre los eventos en Bielorrusia. En total, se incluyeron 260 mensajes de este autor en la base de datos, un vistazo rápido a ellos deja en claro una actitud negativa obvia hacia la situación en Bielorrusia, el propio usuario está por delante de la curva y llama a sus oponentes bots como argumentos.



Y su hermano también fue un observador en las elecciones:



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

Mi hermano fue un observador, no se les permitió en ningún lado.





El autor es claramente un fanático de la literatura histórica alemana.





El hombre busca rastros de la fábrica de trolls. Hola colega







Los ejemplos dados fueron superficiales. Para identificar relaciones más cercanas, es necesario expandir el conjunto de datos en un orden de magnitud, no solo por la cantidad de información, sino también por intervalos de tiempo. Esto permitirá identificar con mayor precisión los temas clave en torno a los cuales se construyen las discusiones, sus iniciadores, analizar las marcas de tiempo de los eventos y su correlación.

Pero incluso en un conjunto de este tipo, con un análisis manual detallado, por ejemplo, considerando enlaces individuales, puede encontrar algo interesante, dando terreno para la reflexión y el trabajo adicional.



GitHub



PS El procesamiento de la matriz 140,000 * 8800000 tomó aproximadamente 7 minutos en el procesador rayzen 5 1600.



En el futuro planeo continuar con este tema, estaré encantado de recibir críticas y sugerencias.