Algoritme pengelompokan sederhana dan skalabel untuk peringkasan data – Menuju AI – Teknologi, Sains, dan Teknik Terbaik

Penulis: Haris Angelidakis

[Source: https://d1m75rqqgidzqn.cloudfront.net/wp-data/2020/01/17162345/clustering-algorithms-in-Machine-Learning.jpg]

Pembelajaran mesin

Algoritma Pengelompokan Sederhana dan Skalabel untuk Peringkasan Data

Heuristik Gonzalez untuk k-Center

pengantar

Di era data besar, kebutuhan untuk merancang prosedur yang efisien yang merangkum jutaan titik data dengan cara yang bermakna lebih mendesak dari sebelumnya. Salah satu cara paling sukses untuk melakukannya, yang termasuk dalam kerangka pembelajaran tanpa pengawasan, adalah pengelompokan. Secara kasar, dengan asumsi bahwa ada beberapa pengertian tentang jarak antar titik yang menangkap seberapa mirip atau tidak kesamaan dua titik, tujuan dari algoritma pengelompokan adalah sebagai berikut:

algoritma pengelompokan menghitung subset kecil dari titik-titik tertentu yang dapat berfungsi sebagai sekumpulan perwakilan dari semua titik.

Mari kita coba membuatnya sedikit lebih formal. Misalkan kita memiliki poin N.

{p (1), p (2),…, p (N)},

dan beberapa pengertian tentang jarak di antara mereka dilambangkan sebagai

D (p (i), p (j)), untuk 1 ≤ i, j ≤ N.

Mengulangi, pada tingkat tinggi, kami ingin melakukan hal berikut:

pilih k poin di antara {p (1),…, p (N)} yang merangkum semua poin dengan cara terbaik.

Sekarang kita membahas apa artinya “meringkas dengan cara terbaik”. Cara standar untuk mengukur apakah sekumpulan k pusat itu baik atau tidak adalah dengan mendefinisikan fungsi biaya yang merangkum jarak semua titik ke pusat terdekatnya di antara yang dipilih. Secara lebih formal, mengingat sekumpulan C dari k pusat, ada tiga tujuan utama yang biasanya dipelajari.

k-Median objektif: Di sini, kami meminimalkan jarak rata-rata setiap titik ke pusat terdekatnya di C (sesuai dengan minimalisasi l1). Tujuan k-Means: Di sini, kita meminimalkan jarak kuadrat rata-rata dari setiap titik ke pusat terdekatnya di C (sesuai dengan minimisasi l2). k-Pusat tujuan: Di sini, kami meminimalkan jarak maksimum suatu titik ke pusat terdekatnya di C (sesuai dengan l-infinity-minimization).

Pada artikel ini, kami fokus pada tujuan terakhir, dan menyajikan algoritma yang sangat sederhana dan cepat, yang diusulkan oleh Teofilo Gonzalez pada tahun 1985, yang juga memberikan faktor perkiraan yang ketat untuk masalah tersebut, dengan asumsi bahwa P tidak sama dengan NP.

Masalah k-Center

Kami tertarik dengan masalah berikut ini, yang dikenal sebagai masalah k-Center. Input terdiri dari

ruang metrik (P, D), di mana P = {p (1),…, p (N)} adalah himpunan titik N dan D adalah fungsi jarak antara titik-titik ini, dan parameter bilangan bulat k, yang menunjukkan jumlah pusat yang diizinkan untuk kami buka.

Tujuannya adalah untuk menghitung subset C dari P yang memiliki titik k sedemikian rupa sehingga jarak terbesar dari setiap titik ke C dapat diminimalkan. Lebih formal, tujuan untuk himpunan bagian C tertentu sama dengan max D (p, C) di semua titik p di P, di mana D (p, C): = min {D (p, c): c di C}, dan tujuannya adalah untuk meminimalkan fungsi tujuan ini.

Cara yang setara, dan mungkin lebih mudah, untuk menyusun tujuan adalah sebagai berikut: hitung himpunan bagian C dari P yang memiliki titik k dan jari-jari terkecil yang mungkin r sedemikian rupa sehingga jika kita mempertimbangkan bola dengan jari-jari r di sekitar titik-titik di C, penyatuan bola-bola ini mencakup semua titik di P. Dalam notasi matematika, ini berarti bahwa {p: D (p, C) ≤ r} = P.

Contoh instance k-Center dan pemilihan pusat ketika k = 15 [Source: https://www-m9.ma.tum.de/games/kcenter-game/img/kcenter.png]

Heuristik Gonzalez

Misalkan P = {p (1),…, p (N)} menunjukkan himpunan masukan poin. Heuristik Gonzalez adalah algoritme serakah yang dimulai dengan memilih pusat sembarang, lalu untuk membuat pilihan pusat berikutnya, ia memilih titik yang paling jauh dari titik yang dipilih sejauh ini. Sesederhana itu!

Kami sekarang memberikan deskripsi algoritma dalam pseudocode.

1. Misalkan Z = P; S = blankset;
2. Pilih sembarang titik p dari P;
3. Atur Z = P – {p}; S = S + {p};
4. Untuk i = 2, …, k:
Misalkan p ‘menjadi titik di Z yang memaksimalkan D (p’, S);
Setel Z = Z – {p ‘}; S = S + {p ‘};
5. Kembali S;

Pengamatan: Dengan asumsi bahwa jarak antara dua titik dapat dihitung dalam waktu konstan, total waktu berjalan dari algoritme adalah O (nk).

Dalam praktiknya, ini adalah algoritme yang sangat cepat dan mudah diterapkan, yang dapat diskalakan dan dapat diterapkan ke kumpulan data yang sangat besar. Selain kecepatannya, ini juga merupakan algoritma yang secara teoritis optimal untuk masalah tersebut, dengan asumsi bahwa P tidak sama dengan NP. Lebih tepatnya, sekarang kita akan melakukan analisis teoritis dan menunjukkan bahwa selalu berhasil mengembalikan solusi yang biayanya berada dalam faktor 2 dari biaya optimal; dengan kata lain, ini adalah algoritma 2-aproksimasi. Selain itu, faktor 2 ini ketat, artinya seseorang tidak dapat mengharapkan faktor aproksimasi yang lebih baik, dengan asumsi bahwa P tidak sama dengan NP; hasil ini dibuktikan oleh Hsu dan Nemhauser (1979).

Catatan: Jika Anda tertarik untuk mempelajari lebih lanjut tentang algoritme perkiraan, Anda dapat melihat artikel saya tentang topik tersebut di sini.

Teorema: Heuristik Gonzalez adalah algoritma 2-aproksimasi untuk masalah k-Center.

Untuk membuktikan teorema di atas, kami menyatakan dengan OPT biaya optimal dalam contoh tertentu. Misalkan c (1),…, c (k) adalah pemilihan pusat yang optimal dengan cluster yang sesuai C (1),…, C (k); Dengan kata lain, setiap cluster C (i) berisi semua titik data yang lebih dekat ke c (i) dibandingkan dengan c (j) lainnya, untuk j berbeda dari i, memutuskan hubungan secara sewenang-wenang. Misalkan s (1),…, s (k) menjadi pusat yang dipilih dari heuristik Gonzalez, diberikan dalam urutan algoritma yang memilihnya. Kami akan menunjukkan bahwa bola dengan radius 2 OPT di sekitar titik {s (1),…, s (k)} mencakup semua titik data. Kami melakukan beberapa analisis kasus:

(1) Misalkan setiap titik s (i) milik cluster berbeda dari solusi optimal. Dengan kata lain, misalkan himpunan poin {s (1),…, s (k)} yang dihitung oleh algoritme “mengenai” setiap cluster dari solusi optimal. Untuk setiap i = 1,…, k, misalkan g (s (i)) menunjukkan pusat solusi optimal yang paling dekat dengan s (i). Pada pembahasan sebelumnya, kita memiliki {g (s (1)), g (s (2)),…, g (s (k))} = {c (1),…, c (k)}.

Selain itu, untuk setiap i, kami memiliki D (s (i), g (s (i))) ≤ OPT, karena kami mengasumsikan bahwa {c (1),…, c (k)} adalah pemilihan center yang optimal. Jadi, untuk setiap i, kita dapatkan bahwa setiap titik cluster C (g (s (i))) berada dalam jarak 2 OPT dari s (i), karena untuk setiap titik p dalam cluster C (g (s (i) ))), dengan pertidaksamaan segitiga kita memiliki D (s (i), p) ≤ D (s (i), g (s (i))) + D (g (s (i)), p) ≤ OPT + OPT = 2 OPT. Kami menyimpulkan bahwa setiap titik berada dalam jarak 2 OPT dari pusat yang dipilih.

(2) Misalkan pada beberapa iterasi i, titik s (i) termasuk dalam cluster optimal C (j) yang telah “terkena” oleh beberapa titik s

D (s (i), s

Dengan pilihan serakah yang dibuat algoritme, pada awal iterasi ke-i, algoritme memilih titik yang memiliki jarak terbesar yang mungkin dari himpunan {s (1),…, s (i-1)} di antara semuanya poin yang tidak dipilih sejauh ini. Perhitungan di atas sekarang menyiratkan bahwa jarak ini paling banyak 2 OPT. Ini berarti bahwa semua titik yang tersisa berada pada jarak paling banyak 2 OPT dari kumpulan pusat yang dipilih.

Dalam kedua kasus, kami menunjukkan bahwa semua titik berada dalam jarak 2 OPT dari kumpulan pusat yang dipilih. Dengan demikian, algoritme tersebut memang merupakan algoritme pendekatan 2 untuk masalah k-Center.

Kesimpulan

Dalam artikel singkat ini, kami menjelaskan pendekatan serakah yang sangat sederhana untuk titik pengelompokan yang ternyata sangat efektif dan sangat cepat. Penerapan algoritme apa pun yang masuk akal dapat diskalakan dengan mudah hingga jutaan poin, dan karenanya menyediakan cara yang sangat nyaman untuk mendapatkan ringkasan kecil kumpulan data besar! Sebagai bonus tambahan, ini adalah salah satu algoritma terbersih dan termudah untuk dianalisis secara teoritis, dan memberikan faktor perkiraan yang ketat untuk masalah tersebut! Apa lagi yang bisa Anda minta ?!

Referensi

Teofilo F. Gonzalez: Clustering untuk Meminimalkan Jarak Intercluster Maksimum. Teor. Comput. Sci. 38: 293–306 (1985) Wen-Lian Hsu, George L. Nemhauser: Masalah lokasi kemacetan yang mudah dan sulit. Kebijaksanaan. Appl. Matematika. 1 (3): 209–215 (1979)

Algoritme pengelompokan sederhana dan skalabel untuk peringkasan data awalnya dipublikasikan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyorot dan menanggapi cerita ini.

Diterbitkan melalui Towards AI