Algoritma Clustering yang Efisien dan Stabil – Menuju AI – Teknologi, Sains, dan Teknik Terbaik

Pengarang: LA Tran

Pembelajaran Mendalam

Mari kita tingkatkan potensi yang kurang diperhatikan

Secara umum, pengelompokan adalah mengelompokkan kumpulan data multidimensi ke dalam kelompok yang terkait erat. Perwakilan klasik dari algoritma pengelompokan adalah K-means Clustering dan Self-Organizing Map (SOM). Anda dapat dengan mudah menemukan banyak sumber untuk penjelasan algoritme tersebut. Kali ini, izinkan saya memperkenalkan kepada Anda semua algoritma pengelompokan efisien lainnya tetapi tampaknya tidak banyak peneliti yang memperhatikan: Jaringan Saraf Centroid untuk Pembelajaran Kompetitif Tanpa Pengawasan. Silakan klik di sini untuk melihat lebih dekat pada kertas asli.

Hasil Jaringan Saraf Centroid — Gambar oleh Penulis (sumber)

Dan sekarang, mari kita mulai!

Jaringan Saraf Centroid (CentNN)

Untuk menghindari kebingungan dengan Convolution Neural Network, saya ingin menggunakan istilah “CentNN” dalam posting ini.

CentNN adalah algoritma pembelajaran kompetitif tanpa pengawasan berdasarkan algoritma pengelompokan k-means klasik yang memperkirakan centroid dari grup cluster terkait pada tanggal pelatihan. CentNN tidak memerlukan jadwal yang telah ditentukan untuk koefisien pembelajaran atau jumlah total iterasi untuk pengelompokan. Dalam makalah tersebut, hasil simulasi pada masalah pengelompokan dan masalah kompresi gambar menunjukkan bahwa CentNN konvergen jauh lebih cepat daripada algoritma konvensional dengan kualitas pengelompokan yang kompatibel sementara algoritma lain dapat memberikan hasil yang tidak stabil tergantung pada nilai awal koefisien pembelajaran dan jumlah total iterasi.

Algoritma Jaringan Saraf Centroid. (gambar dari kertas)

Gambar di atas menunjukkan algoritma CentNN. Jika Anda bosan melihat semua persamaan matematika itu, jangan khawatir, saya akan membuatnya lebih mudah dipahami dengan contoh matematika sekolah menengah.

Pembaruan Berat

Inti dari algoritme adalah prosedur pembaruan bobot: Bagaimana cara menghitung secara efisien pusat massa dari sekelompok titik data ketika satu titik data bergerak masuk atau keluar?

Misalnya, kami memiliki 100 bilangan bulat, sangat sederhana untuk menghitung nilai rata-rata dengan merata-ratakan semuanya. Lalu apa yang terjadi jika kita memiliki satu bilangan bulat lagi? Apakah kita perlu rata-rata semua 101 itu lagi? Jawabannya adalah tidak!

Katakanlah kita memiliki N dan N+1 titik data, nilai rata-rata w dihitung sebagai berikut:

Dari 2 persamaan di atas:

Sekarang kita dapat menghitung rata-rata dari 101 bilangan bulat tanpa merata-ratakannya lagi. Ini mirip ketika kita memindahkan satu bilangan bulat untuk memiliki 99 bilangan bulat.

Dan contoh di atas menjelaskan persamaan ini dalam makalah:

Persamaan Pembaruan Berat

Contoh Penjelasan Visual

Diberikan kumpulan data dengan 30 titik data seperti gambar di bawah ini, tujuan kami adalah mengelompokkannya menjadi 3 klaster.

Gambar oleh Penulis

Zaman 0: Inisialisasi

Cari 1 centroid c untuk semua data, kemudian bagi c menjadi 2 bobot w1, w2 dengan kecil.

w1 = c + , w2 = c — (misalnya = 0,05)

Gambar oleh Penulis

Sebelum melanjutkan, mari kita bicara tentang istilah “neuron pemenang” dan “neuron pecundang”.

pemenang neuron: input data x, neuron pemenang adalah bobot (w) yang paling dekat dengan x di antara semua bobot. neuron pecundang: masukan sebuah data x pada epoch n, jika pada epoch (n-1), w adalah bobot terdekat dengan x, tetapi pada epoch n, ada bobot lain w’ yang lebih dekat ke x daripada w, maka w adalah neuron pecundang dan w’ adalah neuron pemenang untuk data x pada epoch n.

Temukan neuron pemenang untuk setiap x dalam X.

x1 datang, w1 menang → perbarui w1 x2 datang, w2 menang → perbarui w2 x3 datang, w1 menang → perbarui w1 … x30 datang, w1 menang → perbarui w1

Gambar oleh Penulis

Setelah epoch 0, kita selalu memiliki 2 centroid dan informasi dari clustered data point. Sekarang, simpan di sini:

x1 datang, w1 menang x2 datang, w2 menang x3 datang, w1 menang … x30 datang, w1 menang

Zaman 1:

Temukan neuron pemenang untuk setiap x dalam X.

Gambar oleh Penulis x1 datang, w2 menang → w1 kalah, kalah += 1, perbarui bobot. x2 datang, w2 menang x3 datang, w1 menang … x30 datang, w1 menang

Setelah epoch 1, kami memiliki 1 data yang clusternya diperbarui, dan jumlah neuron yang kalah bertambah 1. Dengan melihat, kita masih dapat menyadari bahwa x1 lebih dekat ke w2 daripada w1, tetapi pada epoch 0, x1 di-cluster ke w1 , sekarang diperbarui dengan benar. Sekali lagi, simpan informasinya di sini:

x1 datang, w2 menang x2 datang, w2 menang x3 datang, w1 menang … x30 datang, w1 menang

Zaman 2:

Terus temukan neuron pemenang untuk setiap x dalam X.

Gambar oleh Penulis x1 datang, w2 menang x2 datang, w2 menang x3 datang, w1 menang … x30 datang, w1 menang

Sekarang, tidak ada yang berubah. Mari kita periksa apakah jumlah cluster sekarang mencapai jumlah yang tidak diinginkan. Jawabannya BELUM. Kemudian kita mulai membagi centroid dengan kesalahan terbanyak dengan kecil.

Gambar oleh Penulis

Sekarang lakukan prosedur yang sama dari Epoch 1.

Zaman 3:

Gambar oleh Penulis
Gambar oleh Penulis

Zaman 4:

Gambar oleh Penulis

Zaman 5:

Gambar oleh Penulis

Sekarang, tidak ada yang berubah, dan kami juga mencapai jumlah cluster yang diinginkan. Sekarang, waktunya berpesta!

GIF melalui Tenor [image-source]

Di bawah ini adalah perbandingan antara hasil K-Means Clustering dan CentNN dalam kompresi citra. Kita dapat melihat bahwa CentNN mengungguli K-Means Clustering dalam hal PSNR (rasio signal-to-noise puncak), dengan PSNR 47,53 dibandingkan dengan PSNR 46,35, masing-masing. Dalam contoh, ukuran gambar adalah 128 × 128, jumlah cluster adalah 48.

Hasil Kompresi Gambar — Gambar oleh Penulis

Implementasi CentNN

Kalian dapat menemukan implementasi CentNN saya dengan Python di sini. Jika Anda merasa itu membantu, jangan ragu untuk memberikannya bintang.

Omong-omong, Anda dipersilakan untuk mengunjungi halaman Facebook saya yang untuk berbagi hal-hal tentang Pembelajaran Mesin: Menyelam ke Pembelajaran Mesin.

Dalam posting ini, saya telah memperkenalkan kepada Anda semua Centroid Neural Network (CentNN), sebuah algoritma pengelompokan yang efisien. Fitur utama CentNN adalah memperbarui bobot setiap kali satu data baru datang, sementara K-means Clustering memperbarui centroid setelah setiap iterasi.

Untuk menghindari algoritma terjebak pada solusi minimum lokal yang tidak diinginkan, CentNN memulai dengan mengatur jumlah grup menjadi dua dan meningkatkan jumlah grup satu per satu hingga mencapai jumlah grup yang telah ditentukan. Algoritma CentNN tidak memberikan jaminan konvergensi ke solusi minimum global seperti algoritma unsupervised lainnya tetapi memberikan jaminan konvergensi ke minimum lokal.

Centroid Neural Network: An Efficient and Stable Clustering Algorithm awalnya diterbitkan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.

Diterbitkan melalui Menuju AI