Konvergensi dalam metode Hartigan-Wong k-means dan algoritma lainnya

Saya telah mencoba untuk memahami berbagai algoritma pengelompokan k-means terutama yang diterapkan dalam statspaket Rbahasa.

Saya mengerti algoritma Lloyd dan algoritma online MacQueen. Cara saya memahaminya adalah sebagai berikut:

Algoritma Lloyd:

Awalnya pengamatan acak 'k' dipilih yang akan berfungsi sebagai centroid dari kelompok 'k'. Kemudian langkah-langkah berikut terjadi dalam iterasi sampai centroid bertemu.

1. Jarak Euclidean antara setiap pengamatan dan centroid yang dipilih dihitung.
2. Pengamatan yang paling dekat dengan setiap centroid ditandai dalam ember 'k'.
3. Rata-rata dari semua pengamatan di setiap ember berfungsi sebagai centroid baru.
4. Centroid baru menggantikan centroid lama dan iterasi kembali ke langkah 1 jika centroid lama dan baru tidak bertemu.

Kondisi untuk berkumpul adalah sebagai berikut: centroid lama dan baru persis sama, perbedaan antara centroid kecil (dari urutan 10 ^ -3) atau jumlah maksimum iterasi (10 atau 100) tercapai.

Algoritma MacQueen:

Ini adalah versi online di mana instance 'k' pertama dipilih sebagai centroid.

Kemudian setiap instance ditempatkan dalam ember tergantung pada centroid mana yang paling dekat dengan instance itu. Centroid masing-masing dihitung ulang.

Ulangi langkah ini sampai setiap instance ditempatkan di ember yang sesuai.

Algoritma ini hanya memiliki satu iterasi dan loop berjalan untuk instance 'x'

Algoritma Hartigan-Wong:

1. Tetapkan semua poin / instance ke ember acak dan hitung centroid masing-masing.
2. Mulai dari instance pertama temukan centroid terdekat dan bawa ember itu. Jika ember berubah maka hitung ulang centroid baru yaitu centroid dari ember yang baru ditetapkan dan centroid dari tugas ember lama karena itu adalah dua centroid yang dipengaruhi oleh perubahan tersebut.
3. Lingkari semua titik dan dapatkan centroid baru.
4. Lakukan iterasi kedua poin 2 dan 3 yang melakukan semacam operasi pembersihan dan menugaskan kembali poin liar untuk memperbaiki ember.

Jadi algoritma ini melakukan 2 iterasi sebelum kita melihat hasil konvergensi.

Sekarang, saya tidak yakin apakah yang saya pikirkan pada poin 4 dalam algoritma Hartigan-Wong adalah metode algoritma yang benar. Pertanyaan saya adalah, apakah metode berikut untuk Hartigan-Wong adalah metode yang benar untuk mengimplementasikan k-means? Apakah hanya ada dua iterasi untuk metode ini? jika tidak, bagaimana kondisi konvergensi (kapan harus berhenti)?

Penjelasan implementasi lain yang mungkin saya mengerti adalah.

1. Tetapkan semua poin / instance ke ember acak dan hitung centroid masing-masing.
2. Mulai dari instance pertama, temukan centroid terdekat dan tetapkan ember itu. Jika ember berubah maka hitung ulang centroid baru yaitu centroid dari ember yang baru ditetapkan dan centroid dari tugas ember lama karena itu adalah dua centroid yang dipengaruhi oleh perubahan.
3. Setelah ada perubahan dalam bucket untuk titik mana pun, kembali ke instance pertama dan ulangi langkah-langkah lagi.
4. Iterasi berakhir ketika semua instance di-iterasi dan tidak ada poin yang berubah.

Dengan cara ini ada banyak iterasi yang dimulai dari awal dataset berulang kali setiap kali ketika instance mengubah ember.

Penjelasan apa pun akan membantu dan tolong beri tahu saya jika saya pemahaman saya untuk salah satu metode ini salah.

Algoritma HW, dari makalah 1979, mengambil sebagai input cluster awal. Namun, penulis menyarankan metode untuk mendapatkannya di bagian terakhir mereka. Mereka menulis bahwa dijamin tidak ada cluster yang akan kosong setelah penugasan awal dalam subrutin . Bunyinya sebagai berikut:

1. $\bar{x}$
2. $\bar{x}$$||x_i - \bar{x}||_2$
3. $\{ 1 + (L-1) [M/K] \}$$L=1, \dots, K$$[\ \cdot\ ]$$1$

Adapun algoritma utama, dijelaskan dalam makalah yang disebut Hartigan's K-Means Versus Lloyd's K-Means-Is It Time for a Change? oleh N Slonim, E Aharoni, K Crammer, diterbitkan pada 2013 oleh AJCAI . Perhatikan bahwa versi ini hanya menggunakan partisi awal acak. Bunyinya sebagai berikut.

$x \in \mathcal{X}$$K$

1. $\mathcal{C}$$\mathcal{X}$$K$$C \in \mathcal{C}$$v_C$

2. $\mathcal{X}$$x \in \mathcal{X}$

   $s = 1$

   $x$$C$$C^{-} = C \setminus \{ x \}$

   $$\begin{align*} C^+ = \Big\{ \mathrm{argmin}_{C^* \in (\mathcal{C} \setminus C) \cup C^{-}}\ \frac{1}{n} d(x,v_C^*) + \frac{1}{n} \sum_{y \in C^*} [d(y,v_{C^* \cup x}) - d(y,v_{C^*})] \Big\} \cup \{ x \} \end{align*}$$

   $C^{+} \neq C$$C \leftarrow C^{-}$$C^* \leftarrow C^{+}$$v_{C}$$v_{C^*}$$s \leftarrow 0$

3. $s=0$

$C^*$$\mathrm{argmin}$$x$$C^*$$d$$v_C$$v_{C^* \cup \{x \}}$

Saya pikir jawaban untuk semua pertanyaan Anda tersirat dalam algoritma di atas ... Namun, saya masih harus memastikan implementasi algoritma ini standar . Khususnya jika itu adalah yang diterapkan dalam R. Setiap komentar / edit disambut.