Kami mencari "Troll". Algoritma Shingle & Kesamaan Cosine

Saya pikir banyak orang dalam diskusi menegangkan di Internet telah menghadapi tuduhan orang bahwa mereka adalah bot, troll dan dibayar oleh Kremlin, Kiev atau Washington. Tetapi bagaimana cara mengidentifikasi mereka atau hanya orang yang mencoba secara aktif menyampaikan pendapat mereka kepada yang lain?



Ambil, misalnya, empat teks (komentar):

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

Dari sudut pandang manusia pasti ada kesamaan pada komentar pertama dan kedua, mereka menulis tentang satu orang dan mencirikan aspek positifnya. Dan mereka juga tidak ada hubungannya dengan teks tiga dan empat.



Bagaimana Anda sampai pada hasil yang sama secara matematis?

Sangat klise untuk membandingkan jumlah kata yang identik di kedua teks. Tetapi masalah segera muncul - bagaimana membandingkan kata-kata pintar dan pintar ? Lemmatisasi teks tidak selalu cocok, karena pustaka yang sudah jadi tidak mendukung banyak bahasa.



Pada saat-saat seperti itu, dibenarkan untuk menggunakan Algoritma Shingle yang membagi teks menjadi n bagian, yang ukurannya dipilih secara empiris untuk tugas tertentu.



Contoh:







Mari kita hitung kesamaan teks pertama dan kedua / pertama dan keempat untuk n (1.9) dengan rumus:

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

Gambaran alami, dengan bertambahnya panjangnya, jumlah sirap meningkat dan rasio total sirap terhadap volume total menurun. Jadi untuk teks volume besar, lebih baik menggunakan panjang sirap dari 5 hingga 8, dan saat bekerja dengan yang pendek, misalnya, tweet atau komentar - 2-4.



Namun kembali berlatih, mari kita ambil data yang telah dikumpulkan sebelumnya dari portal hiburan populer Rusia. Tautan ke kaggle .



Untuk mengumpulkan diskusi paling panas, tag (bagian) - Politik dipilih, total dikumpulkan:

• 944 kiriman menandai politik
• 267.000 komentar untuk mereka
• yang mana lebih dari 100 karakter ~ 140 ribu

Pindah ke kode:



Menghapus teks dan membaginya menjadi sirap:

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)

Jika kita hanya mengambil komentar dengan panjang lebih dari 100 karakter, maka jumlah iterasi perbandingannya adalah: $$$140000!/((140000 - 2)!*2! )$, yang jumlahnya cukup banyak dan pemrosesan bahkan dalam mode multi-threaded akan membutuhkan waktu yang cukup lama.



Oleh karena itu, kita tidak akan membandingkan berpasangan, tetapi dengan matriks m * n , menggunakan kesamaan kosinus di

mana m adalah jumlah baris, yang dipilih secara opsional tergantung pada jumlah RAM, dan n adalah jumlah kolom, jumlah total semua sirap;



Implementasi algoritma:

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)

Dengan m = 20.000 dan panjang sirap = 8, kita mendapatkan 7 matriks berukuran 20.000 * ≈8800.000, dan oleh karena itu ada 21 iterasi perbandingan. Jauh lebih baik.

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]

Untuk mengurangi ruang yang ditempati, kami juga menggunakan tipe data float32. Akurasinya cukup untuk membuat algoritme bekerja dengan benar.



Hasil pekerjaan tersebut dimasukkan ke dalam database MySQL untuk diproses lebih lanjut. Jadi, misalnya, mari kita kelompokkan komentar, menghitung setiap kesamaan dengan pasangannya:

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

Pertandingan teratas:

1. Komentar telah dihapus. Alasan: Akun ini telah dihapus.
2. Komentar telah dihapus. Alasan: menghina pengguna.
3. Komentar telah dihapus. Alasan: penghinaan, komunikasi kasar, dan provokasi.
4. Komentar telah dihapus. Alasan: Dilarang memposting komentar, yang tujuan utamanya adalah menyebabkan permusuhan atau hasutan untuk bermusuhan, dan komentar dengan seruan untuk kekerasan atau pelecehan dilarang.

Situasi standar untuk diskusi politik di Internet.



Membuang tautan, pesan dari administrasi, dan gangguan lainnya, kami langsung menuju ke analisis beban semantik komentar:





Dalam lima menit, seorang pria menulis 8 pesan identik dengan topik yang sama mengenai peristiwa di Belarusia. Secara total, 260 pesan dari penulis ini dimasukkan ke dalam database, sekilas pada mereka memperjelas sikap negatif yang jelas terhadap situasi di Belarusia, pengguna sendiri berada di depan kurva dan menyebut bot lawannya sebagai argumen.



Dan saudaranya adalah pengamat pada pemilihan:



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

Kakak saya adalah seorang pengamat - mereka tidak diizinkan di mana pun





Penulisnya jelas merupakan penggemar sastra sejarah Jerman





Pria itu sedang mencari jejak pabrik troll. Halo kolega.







Contoh yang diberikan ada di permukaan. Untuk mengidentifikasi hubungan yang lebih dekat, kumpulan data perlu diperluas berdasarkan urutan besarnya, tidak hanya dengan jumlah informasi, tetapi juga dengan interval waktu. Ini akan memungkinkan untuk lebih akurat mengidentifikasi topik-topik utama di sekitar mana diskusi dibangun, pemrakarsanya, menganalisis stempel waktu peristiwa dan korelasinya.

Tetapi bahkan pada set seperti itu, dengan analisis manual terperinci, misalnya, mempertimbangkan koneksi tunggal, Anda dapat menemukan sesuatu yang menarik, yang memberikan dasar untuk pemikiran dan pekerjaan lebih lanjut.



GitHub



PS Memproses matriks 140,000 * 8800000 membutuhkan waktu sekitar 7 menit pada prosesor rayzen 5 1600



Kedepan, saya berencana untuk melanjutkan topik ini, saya akan senang untuk kritik dan saran.