Mengapa Algoritma Pengelompokan Sempurna Tidak Ada

Sebagai insinyur perangkat lunak, kami selalu menggunakan algoritme pengelompokan. Baik itu mengelompokkan pengguna serupa, mengkategorikan konten, atau mendeteksi pola dalam data, pengelompokan tampaknya sederhana: cukup kelompokkan hal-hal serupa, bukan? Anda mungkin pernah menggunakan k-means, DBSCAN, atau pengelompokan aglomeratif, dan berpikir Anda hanya perlu memilih algoritme yang tepat untuk kasus penggunaan Anda.

Tapi inilah yang sebagian besar tutorial tidak akan beritahukan kepada Anda: setiap algoritma pengelompokan yang Anda pilih pada dasarnya memiliki kelemahan. Bukan karena implementasi yang buruk atau parameter yang salah, tapi karena perhitungannya sendiri. Pada tahun 2002, Jon Kleinberg (di sebuah kertas diterbitkan di NIPS 2002) membuktikan sesuatu yang seharusnya membuat setiap pengembang berhenti sejenak: tidak mungkin algoritma pengelompokan mana pun memiliki ketiga properti yang secara alami kita inginkan.

Anggap saja sebagai teorema CAP pengelompokan. Sama seperti sistem terdistribusi yang memaksa Anda untuk memilih antara konsistensi, ketersediaan, dan toleransi partisi, Kleinberg menunjukkan bahwa algoritme pengelompokan memaksa Anda untuk memilih antara invarian skala, kekayaan, dan konsistensi. Anda tidak bisa mendapatkan ketiganya – selamanya, ini adalah kemustahilan matematis.

Sebelum Anda menerapkan solusi pengelompokan berikutnya dalam produksi, Anda perlu memahami apa yang Anda tinggalkan. Mari selami ketiga properti ini dan lihat mengapa Anda harus selalu memilih apa yang harus dikorbankan.

Sebelum kita membahas teorema ini, kita memerlukan definisi yang tepat tentang clustering. Makalah ini mendefinisikannya dalam kumpulan titik data dan fungsi jarak seperti yang didefinisikan di bawah ini:

Kami menyebut data yang dikelompokkan sebagai kumpulan S dari n poin.

Untuk melakukan clustering, model clustering perlu menghitung jarak berpasangan antara setiap titik data dan untuk itu diperlukan fungsi jarak.

Fungsi jarak adalah fungsi matematika yang mengambil dua titik data i Dan j sebagai parameter, dan menghitung jarak di antara keduanya. Jika parameternya i Dan j adalah titik data yang sama maka jarak antara keduanya seperti yang dihitung oleh fungsi ini harus 0.

Terakhir, makalah ini mendefinisikan pengelompokan sebagai fungsi dari fungsi jarak ddan kumpulan titik data S sedemikian rupa sehingga terpartisi S menjadi subset-subset yang lebih kecil dimana masing-masing subset mewakili sebuah cluster. Secara matematis:

Dalam kaitannya dengan fungsi jarak d, fungsi pengelompokan dapat didefinisikan sebagai fungsi ƒ yang mengambil fungsi jarak d pada S dan mengembalikan partisi Γ dari S.

Misalnya, algoritma k-means mengambil jumlah cluster k, fungsi jarak (seperti Fungsi jarak Euclidean), dan kumpulan titik data sebagai masukan, dan menghasilkan k cluster sebagai keluarannya. K cluster ini pada dasarnya adalah partisi dari kumpulan data asli S.

Kami ingin algoritme pengelompokan kami menunjukkan tiga properti yang diinginkan, yang disebut invariansi skala, kekayaan, dan konsistensi. Mari kita pahami apa arti properti ini.

Invariansi skala adalah properti yang terdengar terlalu jelas: jika Anda mengambil titik data dan menskalakan semua jarak di antara titik tersebut dengan faktor yang sama, klaster Anda tidak akan berubah.

Misalnya, jika untuk dua titik i,j dalam kumpulan data, jarak antara keduanya adalah d(i,j). Kemudian, jika kita menskalakan jarak ini dengan faktor 𝛼 sehingga menjadi 𝛼.d(i,j) maka hasil pengelompokannya tidak akan berubah. Artinya algoritma pengelompokan tidak berubah terhadap skala.

Di dunia nyata, hal ini lebih penting daripada yang Anda kira. Pernahkah Anda:

• Mengubah satuan pengukuran Anda (seperti kaki menjadi meter)

• Menormalkan data Anda secara berbeda

• Menerapkan penskalaan yang berbeda pada fitur Anda hanya untuk menemukan hasil pengelompokan Anda berubah total? Itulah yang terjadi jika algoritme Anda tidak berskala invarian.

Kekayaan adalah tentang kemungkinan — algoritme pengelompokan harus mampu menghasilkan pengelompokan apa pun yang mungkin masuk akal untuk data Anda.

Bayangkan Anda sedang menyortir lemari pakaian Anda. Terkadang Anda mungkin ingin mengelompokkan pakaian berdasarkan warna (membuat banyak kelompok), di lain waktu berdasarkan musim (empat kelompok), atau sekadar menjadi ‘pakai sekarang’ dan ‘simpan’ (dua kelompok). Algoritme pengelompokan yang benar-benar kaya harus mampu menangani semua kemungkinan ini, bukan memaksa Anda ke dalam sejumlah kelompok yang telah ditentukan.

Namun banyak algoritma populer yang gagal memenuhi persyaratan ini. Ambil k-means, misalnya. Saat Anda menentukan k=3, Anda telah mengesampingkan kemungkinan menemukan dua atau empat cluster, meskipun itu yang secara alami disarankan oleh data Anda. Ini seperti memaksa lemari pakaian Anda menjadi tiga kelompok, meskipun itu tidak masuk akal untuk pakaian Anda.

Secara matematis: jika f adalah fungsi pengelompokan kami dan S adalah kumpulan data kami, kekayaan berarti itu f harus mampu menghasilkan kemungkinan partisi S. Dengan kata lain, range(f) harus sama dengan himpunan semua cara yang mungkin untuk mempartisi S.

Meskipun secara teori fleksibilitas ini terdengar bagus, Anda mungkin dapat melihat mengapa banyak algoritma praktis mengorbankannya. Saat Anda menganalisis data nyata, Anda sering kali ingin mengontrol jumlah cluster agar hasilnya dapat diinterpretasikan

Properti ketiga, konsistensi, artinya jika klaster yang ada bagus, membuat titik serupa menjadi lebih mirip dan titik berbeda menjadi lebih berbeda tidak akan mengubah klaster ini.

Mari kita uraikan ini dengan contoh sederhana. Bayangkan Anda mengelompokkan film ke dalam genre berdasarkan karakteristiknya. Sekarang:

• Dua film aksi menambahkan adegan yang lebih eksplosif, membuatnya semakin mirip satu sama lain

• Sedangkan film romantis lebih banyak menambahkan adegan romantis sehingga semakin berbeda dengan film laga

Konsistensi berarti bahwa jika perubahan ini hanya memperkuat pengelompokan yang ada, algoritma pengelompokan Anda tidak akan tiba-tiba memutuskan untuk mengatur ulang kelompok tersebut.

Secara matematis: jika Γ adalah pengelompokan titik menggunakan fungsi jarak ddan kami membuat fungsi jarak baru d' Di mana:

• Untuk dua poin apa pun i,j dalam cluster yang sama: d'(i,j) < d(i,j) (hal serupa menjadi lebih mirip)

• Untuk dua poin apa pun i,j dalam cluster yang berbeda: d'(i,j) > d(i,j) (hal yang berbeda menjadi lebih berbeda)

Maka algoritma pengelompokan yang konsisten harus menghasilkan pengelompokan yang sama Γ dengan d' seperti yang terjadi dengan d. Fungsi jarak baru ini d' disebut a Γ transformasi dari d.

Meskipun Kleinberg membuktikannya secara matematis (lihat makalahnya untuk bukti lengkapnya), mari kita lihat bagaimana batasan ‘pilih dua dari tiga’ ini muncul dalam algoritme yang mungkin Anda gunakan saat ini.

Tautan tunggal adalah bentuk pengelompokan hierarki. Ini dimulai dengan sederhana: setiap titik adalah clusternya sendiri, dan kami secara bertahap menggabungkan cluster terdekat. Bagian yang menarik adalah memutuskan bagaimana menghentikan algoritma. Salah satu dari tiga kriteria umum digunakan untuk menghentikan algoritma dan masing-masing kriteria memiliki trade off yang berakar pada teorema ketidakmungkinan.

• Apa yang kami lakukan: Hentikan pengelompokan setelah kami memiliki k cluster

• Apa yang kita korbankan: Kekayaan

• Mengapa? Kami telah mengunci diri ke dalam k grup. Algoritme kami tidak akan pernah menemukan pengelompokan lain yang ukurannya lebih kecil atau lebih besar dari k.

• Apa yang kami lakukan: Kami terus menggabungkan cluster selama jaraknya <= jarak tertentu r. Ketika semua cluster berada pada jarak yang lebih besar dari r, algoritma secara otomatis berhenti.

• Apa yang kami korbankan: Invariansi skala

• Mengapa? Jika kita memperbesar data sebanyak 2x (atau faktor lainnya), maka cluster yang sebelumnya dapat digabungkan tiba-tiba menjadi terlalu berjauhan dan tidak akan digabungkan. Ini mengubah keluaran pengelompokan.

• Apa yang kami lakukan: Kami menghitung jarak berpasangan maksimum ρ dalam kumpulan data kami menggunakan beberapa fungsi jarak d1. Setelah itu kita hanya menggabungkan dua cluster jika jaraknya <= αρDi mana α < 1.

• Yang kami korbankan: Konsistensi

• Mengapa? Katakanlah kita mengubah fungsi jarak dari d1 ke d2sedemikian rupa sehingga d2 membuat titik-titik yang serupa menjadi semakin serupa, dan titik-titik yang tidak serupa menjadi semakin berbeda. Secara lebih formal, d2 adalah a Γ transformasi dari d1. Kemudian menurut definisi, jarak berpasangan maksimum diperoleh dengan menggunakan d2 akan lebih besar dari ρdan sebagai hasilnya diperoleh keluaran clustering dengan menggunakan d2 juga akan sangat berbeda dari clustering aslinya.

Pengelompokan berbasis centroid mengacu pada yang umum digunakan k-berarti Dan k-median algoritma. Dimana kita memulai dengan yang telah ditentukan sebelumnya k jumlah cluster dengan memilih k titik-titik dalam data sebagai centroid dan kemudian menugaskan setiap titik ke cluster terdekatnya. Algoritme ini secara iteratif mengoptimalkan pusat massa dari k cluster dengan menghitung rata-rata (atau median) setiap cluster, dan kemudian mendistribusikan ulang titik-titik tersebut berdasarkan pusat cluster terdekat. Algoritme biasanya berhenti ketika cluster menjadi stabil.

Algoritme ini mengalami masalah tidak memuaskan kekayaan properti karena segera setelah kita menetapkan jumlah cluster k, secara otomatis menghilangkan kemungkinan mencapai semua kemungkinan clustering sebagai output.

Makalah ini membuktikan bahwa algoritma ini tidak memuaskan konsistensi properti juga. Misalnya, untuk k=2, k-means dapat menghasilkan cluster X dan Y. Namun, jika kita memperkecil jarak antara titik-titik dalam X, dan Y, sekaligus menambah jarak antara titik-titik dalam X dan Y, maka algoritma mungkin menghasilkan dua cluster yang sangat berbeda sebagai keluarannya. Makalah ini memiliki bukti formal untuk contoh spesifik ini yang juga digeneralisasikan menjadi k > 2.

Sekarang Anda tahu mengapa algoritma pengelompokan memaksa Anda untuk berkorban. Hal ini bukanlah suatu kelemahan dalam implementasi atau suatu keterbatasan yang pada akhirnya akan kita atasi – secara matematis mustahil untuk memiliki semuanya. Setiap algoritme pengelompokan harus menghilangkan invarian skala, kekayaan, atau konsistensi. Tidak ada jalan keluar dari pertukaran mendasar ini.

Namun begitu Anda memahami apa yang Anda serahkan, Anda dapat membuat batasan ini berhasil untuk Anda. Sama seperti para insinyur yang memilih antara konsistensi dan ketersediaan dalam sistem terdistribusi, Anda dapat secara strategis memilih properti pengelompokan mana yang akan dikorbankan:

• Butuh algoritme Anda untuk menangani data berapa pun skalanya? Anda mungkin harus melepaskan kekayaan.

• Ingin fleksibilitas untuk menemukan kemungkinan pengelompokan? Bersiaplah untuk kehilangan invarian skala.

• Perlu hasil agar tetap stabil ketika pola klaster menjadi lebih jelas? Anda mungkin akan mengorbankan kekayaan.

Daripada melawan keterbatasan ini, gunakanlah keterbatasan tersebut sebagai panduan. Tanyakan pada diri Anda:

• Properti apa yang paling penting untuk kasus penggunaan spesifik Anda?

• Trade-off manakah yang dapat ditoleransi oleh aplikasi Anda?

• Bagaimana Anda dapat merancang sistem Anda dengan mengetahui keterbatasan yang melekat ini?

Memahami teorema Kleinberg tidak hanya membuat Anda menjadi ahli teori yang lebih baik – tetapi juga membuat Anda menjadi insinyur yang lebih efektif. Karena di dunia nyata, kesuksesan bukanlah tentang menemukan algoritma clustering yang sempurna (tidak ada). Ini tentang memilih pengorbanan yang tepat untuk kebutuhan spesifik Anda.

Jika menurut Anda pekerjaan saya menarik dan berharga, Anda dapat mendukung saya dengan memilih langganan berbayar (biayanya $6 bulanan/$60 tahunan). Sebagai bonus, Anda mendapatkan akses ke sesi live bulanan, dan semua rekaman sebelumnya.

Banyak orang melaporkan pembayaran gagal, atau tidak ingin berlangganan berulang. Untuk itu saya juga punya halaman belimeacoffee. Di mana Anda dapat membelikan saya kopi atau menjadi anggota. Saya akan meningkatkan Anda ke langganan berbayar dengan durasi yang setara di sini.

Belikan aku kopi

Saya juga memiliki halaman Sponsor GitHub. Anda akan mendapatkan lencana sponsorship, dan juga langganan berbayar pelengkap di sini.

Sponsori saya di GitHub