K-Means Clustering ( Wikipedia )
Tugas di sini agak sederhana, melakukan iterasi tunggal dari algoritma pengelompokan k-means pada matriks biner. Ini pada dasarnya adalah tugas pengaturan untuk algoritma k-means utama, saya merasa pengaturan mungkin lebih mudah dan menarik bahasa golf untuk mencobanya juga. Matriks yang diteruskan ke Anda akan memiliki format berikut:
0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
1 mewakili suatu poin, sedangkan 0 mewakili suatu kekurangan poin. Tugas Anda adalah menghasilkan k-1
centroid secara acak dan melakukan pengelompokan awal data di sekitar centroid yang telah Anda hasilkan. k
didefinisikan sebagai min(grid#Width, grid#Height)-1
. Pelabelan setiap centroid harus dimulai dari 2
sampai k
. Misalnya, dalam skenario ini Anda bisa menghasilkan centroid berikut:
Centroid 2 was generated at: (1.0, 4.0)
Centroid 3 was generated at: (1.0, 5.0)
Centroid 4 was generated at: (5.0, 1.0)
Centroid 5 was generated at: (3.0, 3.0)
Centroid 6 was generated at: (0.0, 2.0)
Centroid 7 was generated at: (6.0, 6.0)
Centroid 8 was generated at: (2.0, 6.0)
Setelah menghasilkan centroid, Anda harus mengulang setiap titik yang ditandai dengan 1
, karena kami dapat memperlakukan yang ditandai dengan 0
ruang kosong. Untuk setiap centroid, Anda harus memutuskan centroid mana yang paling dekat dengan titik yang dimaksud. Inilah jarak untuk contoh:
(0,8) distance from centroid 2 is 4.123105625617661
(0,8) distance from centroid 3 is 3.1622776601683795
(0,8) distance from centroid 4 is 8.602325267042627
(0,8) distance from centroid 5 is 5.830951894845301
(0,8) distance from centroid 6 is 6.0
(0,8) distance from centroid 7 is 6.324555320336759
(0,8) distance from centroid 8 is 2.8284271247461903
(1,1) distance from centroid 2 is 3.0
(1,1) distance from centroid 3 is 4.0
(1,1) distance from centroid 4 is 4.0
(1,1) distance from centroid 5 is 2.8284271247461903
(1,1) distance from centroid 6 is 1.4142135623730951
(1,1) distance from centroid 7 is 7.0710678118654755
(1,1) distance from centroid 8 is 5.0990195135927845
(2,8) distance from centroid 2 is 4.123105625617661
(2,8) distance from centroid 3 is 3.1622776601683795
(2,8) distance from centroid 4 is 7.615773105863909
(2,8) distance from centroid 5 is 5.0990195135927845
(2,8) distance from centroid 6 is 6.324555320336759
(2,8) distance from centroid 7 is 4.47213595499958
(2,8) distance from centroid 8 is 2.0
(3,2) distance from centroid 2 is 2.8284271247461903
(3,2) distance from centroid 3 is 3.605551275463989
(3,2) distance from centroid 4 is 2.23606797749979
(3,2) distance from centroid 5 is 1.0
(3,2) distance from centroid 6 is 3.0
(3,2) distance from centroid 7 is 5.0
(3,2) distance from centroid 8 is 4.123105625617661
(4,5) distance from centroid 2 is 3.1622776601683795
(4,5) distance from centroid 3 is 3.0
(4,5) distance from centroid 4 is 4.123105625617661
(4,5) distance from centroid 5 is 2.23606797749979
(4,5) distance from centroid 6 is 5.0
(4,5) distance from centroid 7 is 2.23606797749979
(4,5) distance from centroid 8 is 2.23606797749979
(4,8) distance from centroid 2 is 5.0
(4,8) distance from centroid 3 is 4.242640687119285
(4,8) distance from centroid 4 is 7.0710678118654755
(4,8) distance from centroid 5 is 5.0990195135927845
(4,8) distance from centroid 6 is 7.211102550927978
(4,8) distance from centroid 7 is 2.8284271247461903
(4,8) distance from centroid 8 is 2.8284271247461903
(6,1) distance from centroid 2 is 5.830951894845301
(6,1) distance from centroid 3 is 6.4031242374328485
(6,1) distance from centroid 4 is 1.0
(6,1) distance from centroid 5 is 3.605551275463989
(6,1) distance from centroid 6 is 6.082762530298219
(6,1) distance from centroid 7 is 5.0
(6,1) distance from centroid 8 is 6.4031242374328485
(7,1) distance from centroid 2 is 6.708203932499369
(7,1) distance from centroid 3 is 7.211102550927978
(7,1) distance from centroid 4 is 2.0
(7,1) distance from centroid 5 is 4.47213595499958
(7,1) distance from centroid 6 is 7.0710678118654755
(7,1) distance from centroid 7 is 5.0990195135927845
(7,1) distance from centroid 8 is 7.0710678118654755
(7,5) distance from centroid 2 is 6.082762530298219
(7,5) distance from centroid 3 is 6.0
(7,5) distance from centroid 4 is 4.47213595499958
(7,5) distance from centroid 5 is 4.47213595499958
(7,5) distance from centroid 6 is 7.615773105863909
(7,5) distance from centroid 7 is 1.4142135623730951
(7,5) distance from centroid 8 is 5.0990195135927845
(8,1) distance from centroid 2 is 7.615773105863909
(8,1) distance from centroid 3 is 8.06225774829855
(8,1) distance from centroid 4 is 3.0
(8,1) distance from centroid 5 is 5.385164807134504
(8,1) distance from centroid 6 is 8.06225774829855
(8,1) distance from centroid 7 is 5.385164807134504
(8,1) distance from centroid 8 is 7.810249675906654
(8,8) distance from centroid 2 is 8.06225774829855
(8,8) distance from centroid 3 is 7.615773105863909
(8,8) distance from centroid 4 is 7.615773105863909
(8,8) distance from centroid 5 is 7.0710678118654755
(8,8) distance from centroid 6 is 10.0
(8,8) distance from centroid 7 is 2.8284271247461903
(8,8) distance from centroid 8 is 6.324555320336759
Hasil akhir dari algoritma pengelompokan adalah bahwa tidak boleh ada 1 yang tersisa dalam matriks, hanya angka centroid. Inilah sebabnya mengapa penting untuk memberi label pada centroid 2-k+1
, yang memungkinkan kami untuk menggantinya, sebagai berikut:
0 0 0 0 0 0 0 0 8
0 6 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 8
0 0 5 0 0 0 0 0 0
0 0 0 0 0 5 0 0 7
0 0 0 0 0 0 0 0 0
0 4 0 0 0 0 0 0 0
0 4 0 0 0 7 0 0 0
0 4 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0
Ini adalah tata letak pengelompokan awal untuk 7 centroid pada grid yang disediakan, diberikan centroid yang dihasilkan secara acak. Tugas Anda adalah untuk mengeluarkan versi clustered dari input binary grid.
Aturan
- The
k-1
centroid harus dihasilkan secara acak dan harus di mana saja dari(0,0)
ke(grid#Width, grid#Height)
.- Nilai
k
adalahmin(grid#Width, grid#Height)-1
. - Centroid yang dihasilkan HARUS dinomori dari
2
kek
.
- Nilai
- Format input HARUS berupa kisi 0s dan 1s, di mana 0s mewakili ruang kosong dan 1s mewakili poin.
- Kisi adalah string yang menggunakan 1-char per sel dan
\n
sebagai pembatas baris atau array 2D. - Kisi yang dilewati tidak dijamin berbentuk bujur sangkar, tetapi dijamin tidak kosong.
- Kisi adalah string yang menggunakan 1-char per sel dan
- Hasil akhir dapat menggunakan array atau string yang dibatasi.
- Kode terpendek menang, ini kode-golf .
sumber
Jawaban:
Mathematica 109 Bytes
Jika saya memahami pertanyaan dengan benar, sesuatu seperti ini seharusnya berhasil. "KMeans" adalah salah satu metode bawaan untuk FindClusters dan ClusteringComponents.
Penggunaan:
%@in//MatrixForm
untuk mendapatkan visualisasi,in
adalah array integer.sumber