pengelompokan dengan elemen yang sama
Asumsikan bahwa kita memiliki serangkaian pengamatan: $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, mengandung $n$ pengamatan untuk dimensi tetap $d$. Asumsikan, kami memiliki beberapa bilangan bulat tetap$k$. Pengelompokan k-means (dengan jarak l2) adalah masalah menemukan sentroid pada kluster$S_{1}, \dots, S_{k}$ meminimalkan itu $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ dimana $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ adalah sentroid, yaitu $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.
Asumsikan, di sana $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ ada elemen yang sama $\{x\} \subset \mathbf{X}$.
Apakah mungkin bahwa dalam solusi global (teoritis) ini sama satu sama lain $\{x\}$ termasuk dalam kelompok yang berbeda?
Jawaban
Pertama, kita perlu membedakan antara solusi k-means yang optimal secara global dan hasil yang Anda peroleh dari algoritma k-means. Ada cukup banyak di sekitar ini, dan kecuali set data sangat kecil, mereka akan memberikan optimal lokal yang belum tentu global. (Anda mengatakan "global" dalam pertanyaan Anda jadi saya berasumsi yang Anda maksud adalah solusi optimal secara global; hanya untuk memastikan.)
Jawaban atas pertanyaan Anda dimulai dengan "tidak biasanya"; mereka$\|x-q_j\|$-nilai jelas sama untuk semua $q_j$, jadi setelah algoritme terkonvergensi (atau optimal secara global $q_j$ diketahui), mereka semua akan ditetapkan ke orang terdekat mereka $q_j$, yang sama untuk mereka semua.
Situasi luar biasa yang tidak tercakup oleh argumen di atas terjadi jika tidak hanya beberapa $x$ sama, tetapi jaraknya juga sama dengan dua atau lebih $q_j$. Saya sebenarnya tidak mengetahui algoritme apa pun yang dalam hal ini dapat menetapkannya ke cluster yang berbeda, tetapi saya tidak dapat mengecualikan bahwa implementasi semacam itu ada.
Sebenarnya saya belum mencoba membuktikannya tetapi saya curiga bahwa optimal global tidak akan pernah memisahkan pengamatan yang sama, karena kemungkinan besar jika pengamatan yang sama dipisahkan, seseorang dapat mencapai solusi yang lebih baik dengan menempatkan semuanya ke dalam cluster yang memiliki mayoritas. dari mereka (atau sembarang cluster jika mereka didistribusikan secara merata). Tampaknya tidak masuk akal jika obsrvasi ini memengaruhi lebih dari satu mean cluster (membuatnya berpotensi lebih buruk untuk sebagian besar pengamatan lain dalam cluster itu). Orang mungkin bisa membuktikan menghabiskan sore ini mengerjakan matematika, tapi tidak ada jaminan di sini, hanya tebakan.
Apa yang telah saya lihat adalah sejumlah contoh 1-d dengan titik yang sama berada di antara dua bagian data seperti 1,2,3,3,4,5. Memang Anda mendapatkan solusi yang lebih baik ($k=2$) dalam hal biaya jika Anda meletakkan dua 3 baik dalam cluster dengan 1,2, atau dengan 4,5, daripada satu ke kiri dan satu ke kanan (Anda dapat memeriksa ini dengan menghitung fungsi biaya secara eksplisit) .