K-means adalah algoritma pengelompokan tanpa pengawasan standar, yang, diberikan satu set "titik" dan sejumlah kluster K, akan menetapkan setiap "titik" ke salah satu kluster K.
Pseudo-Code of K-means
Perhatikan bahwa ada banyak varian K-means. Anda harus mengimplementasikan algoritma yang saya jelaskan di bawah ini. Anda mungkin memiliki beberapa variasi pada algoritma atau menggunakan built-in selama Anda akan mendapatkan hasil yang sama seperti algoritma ini diberi poin awal yang sama.
Dalam tantangan ini, semua input akan menjadi titik pada bidang 2D (setiap titik diwakili oleh koordinatnya dalam x dan y).
Inputs: K, the number of clusters
P, the set of points
Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster
Loop:
For each point in P:
Assign to the cluster whose centroid is the nearest (Euclidean distance)
In case of a tie, any of the tied cluster can be chosen
Recompute the centroid of each cluster:
Its x coordinate is the average of all x's of the points in the cluster
Its y coordinate is the average of all y's of the points in the cluster
Until the clusters don't change from one iteration to the next
Output: the set of clusters
Masukan dan keluaran
- Anda dapat mengambil K dan P melalui
STDIN
, atau sebagai argumen fungsi, dll. - P dan titik-titik dalam P dapat direpresentasikan menggunakan struktur apa pun yang alami untuk set / daftar dalam bahasa pilihan Anda.
- K adalah bilangan bulat yang benar-benar positif.
- Anda dapat berasumsi bahwa input tersebut valid.
- Akan selalu ada setidaknya poin K di P.
- Anda dapat menampilkan cluster untuk
STDOUT
, mengembalikannya dari suatu fungsi, dll. - Pemesanan cluster dan pemesanan di dalam cluster tidak penting. -Anda dapat mengembalikan kelompok titik untuk mewakili kelompok, atau setiap titik yang dilabeli dengan pengidentifikasi untuk gugus (misalnya bilangan bulat).
Uji kasus
Karena cluster yang dihasilkan tergantung pada titik mana yang awalnya dipilih, Anda mungkin tidak semua mendapatkan hasil yang sama (atau hasil yang sama setiap kali Anda menjalankan kode Anda).
Karena itu, ambil saja output sebagai contoh output.
Input:
K = 1
P = [[1,2.5]]
Output:
[[[1,2.5]]]
Input:
K = 3
P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
[[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]
Input:
K = 2
P = [[1,1], [1,1], [1,1]]
Output:
[[[1,1]],[[1,1],[1,1]]]
Mencetak gol
Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.
sumber
1
, semua poin dari yang kedua memiliki label2
dll)K=2, P = [[1,1], [1,1], [1,1]]
.Jawaban:
Matlab, 25 byte
Diberi
n x 2
matriks (misalnya satu baris per titik[[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]
), fungsi ini mengembalikan daftar label untuk setiap titik input.sumber
C ++,
479474 byteHanya ~ 20x sebanyak Matlab!
Golf
Input / output ke algoritma adalah seperangkat poin (
struct P
) denganx
dany
; dan output adalah himpunan yang sama, dengani
himpunan mereka untuk menunjukkan indeks dari kluster keluaran dimana titik berakhir.Ekstra
i
itu juga digunakan untuk mengidentifikasi kelompok. Di loop utama, centroid terdekat untuk setiap titik ditemukan dengan mengurutkan salinan centroid saat ini dengan kedekatan dengan titik itu.Ini menangani kasus degenerasi (kluster kosong) dengan menjaga posisi sentroid sebelumnya yang sesuai (lihat definisi
P::n
, yang juga mengembalikan jarak ke centroid sebelumnya). Beberapa karakter dapat dihemat dengan mengasumsikan bahwa ini tidak akan muncul.Tidak disatukan, dengan utama
sumber
#define R p){return
dan mengubah argumen kedual
menjadip
sehingga Anda dapat menggunakannya tiga kali total?J,
6054 byteMenentukan kata kerja pembantu
p
yang mengambil daftar titik dan centroid dan mengklasifikasikan setiap titik dengan indeks centroid terdekat. Kemudian, ia menggunakan itu untuk mengulangi proses memilih centroid baru dengan mengambil rata-rata dari titik-titik di masing-masing cluster sampai konvergen, dan kemudian untuk mempartisi poin untuk output.Pemakaian
Nilai k diberikan sebagai bilangan bulat pada LHS. Daftar poin diberikan sebagai array 2d pada RHS. Di sini ditentukan sebagai daftar poin yang dibentuk kembali menjadi array 2d dari 5 x 2. Output akan menjadi label yang mana setiap titik cluster berada dalam urutan yang sama dengan input.
Jika Anda ingin menggunakan benih tetap untuk hasil yang dapat direproduksi, ganti
?
dengan a?.
di(?#)
.Penjelasan
sumber
CJam (60 byte)
Ini adalah fungsi yang mengambil inputnya dalam bentuk
k p
di stack. Diasumsikan bahwa poin diwakili dengan ganda, bukan int. Itu tidak secara implisit mengasumsikan apa pun tentang dimensi titik, sehingga akan mengelompok dengan baik di ruang Euclidean 6-D seperti pada 2-D yang ditentukan.Demo online
sumber
Mathematica
1412 byteKarena built-in diizinkan, ini harus dilakukan.
Contoh
{{{4, 8}, {-13.37, -12.1}}, {{15, 16}, {23, 42}}, {{666, -666}}}
sumber
f = FindClusters
,f[something]
.Jelly , 24 byte
Cobalah online!
Menggunakan fitur yang diterapkan setelah tantangan ini diposting. Seharusnya, ini tidak lagi bersaing .
Penjelasan
sumber
R , 273 byte
Cobalah online!
Dibawa
P
sebagai matriks, denganx
dany
koordinat masing-masing di kolom pertama dan kedua. KembaliP
dengan kolom pertama yang ditambahkan yang menunjukkan indeks cluster (integer).Saya harus mendefinisikan ulang
w
dengan menyalin sumber darinnet::which.is.max
agar sesuai dengan persyaratan bahwa cluster dipilih secara acak dalam kasus ikatan. Kalau tidak, saya akan menggunakanwhich.min
daribase
total 210 byte. Masih ada ruang untuk bermain golf, tetapi saya tidak ingin mengaburkan banyak hal untuk memberi orang lain kesempatan untuk melihat kemungkinan masalah dalam kode saya.sumber
Julia 213 byte
Mengembalikan array dengan panjang yang sama dengan
p
, dengan bilangan bulat yang menunjukkan kelompok mana elemen terkaitp
milik.Saya pikir masih ada sedikit ruang untuk mengoptimalkan penghitungan karakter.
(Tentu saja saya bisa menggunakan paket Clustering.jl untuk melakukannya secara sepele)
sumber