k-means Clustering Demo

k-means Clustering Demo
by Alissa Liu
for Game Maker 8.0

Description:
Demonstrates data clustering/grouping using k-means method. In this demonstration, n two-dimensional vector data (represented by points) are given in random (with specific range) and also given specific number of clusters (k, max=7). With given random centroids of each cluster (represented by X-mark points), the algorithm attempts to perform clustering/grouping data until convergence. Colors of each data indicate their cluster/group.

Links: [You must be registered and logged in to see this link.]

Screenshots:

Spoiler:

Spoiler:

Spoiler:

Implementation usage:
The function is clustering(). Requires the following parameters:
- n: number of data
- k: number of clusters
- cx[0..k-1], cy[0..k-1]: cluster centroid vector
- xp[0..n-1], yp[0..n-1]: data vector
- cp[0..n-1]: cluster number of data (-1 as uninitialized)

The resulting output is cp[0..n-1] value of each data

wah, gk ngerti
ilmu ku blum sampe kesana (kali)

well, mungkin bahasanya terlalu teknis, tapi itung2 belajar buat UAS besok

mungkin penjelasannya yang lebih akrab itu sistem untuk mengelompokkan data berdasarkan jarak perbedaannya, jadi beberapa data yang terlihat bergerombol dikelompokkan jadi satu

UAS ? good luck ya

I see, mngkin lain kali aku akan perlu ini
nice share deh kalo gitu

Mantap nih algoritmanya... [You must be registered and logged in to see this image.]

sampe bingung ane....

nice job asuna


penggerombolan data berguna untuk bikin game2 yang memiliki jumlah item banyak, seperti RTS misalnya.


mungkin aku bisa bayangkan satu contoh penggunaan: kalau punya anak buah monster jumlahnya ribuan, untuk nyuruh mereka berkumpul ke masing2 grup... bisa sih pake koordinat terus mereka move toward ke koordinat itu masing2 tapi mungkin lama sekali hasilnya (karena itu berarti array dengan ribuan koordinat). lebih efektif kalau ada titik pusat/centroid dan masing2 men-generate koordinat tujuan. hasilnya adalah koordinat tujuan yang ngga persis seperti kotak2, jadi hasilnya lebih natural.

bisa juga diapply untuk warna?

@zebrakelabu:
kalo baca komentar om rasa ny jdi useful bnget example ini

@zebrakelabu

disini centroid diinisialisasi secara random/heuristik sebagai seed, lalu diubah2 sampe pas, kompleksitasnya kira2 O(kn) pada tiap iterasi dikali banyak iterasi yang bisa saja eksponensial, emang gitu sih algoritmanya
tapi di demonya yang jumlahnya cuma ratusan masih cukup cepat

btw masih ada algoritma lain seperti k-medoids, Hierarchical clustering, Expectation–maximization algorithm, dll, yang mungkin lebih bagus & efisien dan tidak perlu ditentukan jumlah kelompok & centroid terlebih dahulu

kalo mau silahkan bereksperimen sendiri dgn algoritma lain tsb

btw warna bisa digunakan sebagai label kelompoknya

Asuna wrote:@zebrakelabu

disini centroid diinisialisasi secara random/heuristik sebagai seed, lalu diubah2 sampe pas, kompleksitasnya kira2 O(kn) pada tiap iterasi dikali banyak iterasi yang bisa saja eksponensial, emang gitu sih algoritmanya [You must be registered and logged in to see this image.]
tapi di demonya yang jumlahnya cuma ratusan masih cukup cepat [You must be registered and logged in to see this image.]

btw masih ada algoritma lain seperti k-medoids, Hierarchical clustering, Expectation–maximization algorithm, dll, yang mungkin lebih bagus & efisien dan tidak perlu ditentukan jumlah kelompok & centroid terlebih dahulu [You must be registered and logged in to see this image.]

kalo mau silahkan bereksperimen sendiri dgn algoritma lain tsb [You must be registered and logged in to see this image.]

btw warna bisa digunakan sebagai label kelompoknya [You must be registered and logged in to see this image.]

Wah banyakbanget om....

ente jago om [You must be registered and logged in to see this image.]

Ajarin ane lah...

^
silakan pelajari disini kalo mau, btw ini termasuk di bidang AI
[You must be registered and logged in to see this link.]

Asuna wrote:^
silakan pelajari disini kalo mau, btw ini termasuk di bidang AI [You must be registered and logged in to see this image.]
[You must be registered and logged in to see this link.]

Ok sip Menuju tkp...

Thanks om.. [You must be registered and logged in to see this image.]

@Asuna:
kalo algoritma sudoku tau gk?

@Kevin
cara paling kasar: Brute force

cara dengan pendekatan AI problem solving: Arc consistency check or local search algorithm (hill climbing, simulated annealing, genetic algorithm)

cara yang lebih strategis (pendekatan greedy):
1. isi semua kotak dengan 1 kemungkinan angka
2. kalo belum terisi semua, tebak angka pada salah satu kotak dengan kemungkinan angka paling sedikit
3. lakukan langkah 1
4. kalo ada kotak yang ga bisa diisi angka, backtrack ke state/keadaan sebelum menebak dan kembali ke langkah 2

btw ini OOT deh, sudoku ga ada hubungannya sama topik ini

ya udh lh, thanks atas penjelasan ny,, tdi juga sempet cari" info di google

ok, mari kita lihat examplenya ...

MY EYESSS THERES TO MANY SCRIPT *plaaaaak (benernya dikit sih, cuma kelihatan rumit )

Belum mudeng Harus dapet pendidikan formal sepertinya Tunggu kuliah ah ... Nggak sabar. Tapi diajarkan ndak seperti yang ada di Example jurusan TI? :O

@FisherCS
mungkin begitu awalnya kalo liat source code punya orang
tapi kalo dipelajari dgn seksama beserta konsepnya jadi baru ngerti

kalo dasar2 pemrograman iya
tapi tentang algoritma clustering di bidang AI emang dipelajari di kuliah jurusan TI, atau anda bisa pelajari sendiri di ebook atau wikipedia

start small aja tapi terus dikembangkan dari sana

(btw avatar fishercs keren euy, itu gambar sendiri? )

@Asuna: Ya udah, kalau gitu ITB deh

@zebrakelabu: Doodle Pencil sudah sangat sederhana
Pengennya sih gambar sendiri om kayak di avatarku Kemampuan belum nyampai. Aku snip dari digital comicnya Assasins Creed om

@FisherCS
jurusan TI di kampus lain juga gitu, emangny anda pikir cuma di kampus itu doang?

Walah -_- Im just kidding Tapi impianku disana, atau BINUS yang ada jurusan GATnya. Rencanaku ya di Unbraw.

well silakan aja, it's your choice and no need to regret then
yang penting apapun kampusnya, minumnya teh botol sosro ujung2nya bisa dapet job yang pas buatmu

ah sudahlah, ga usah terlalu OOT lagi

mantep 
bisa bikin data mining nih di gm.. 

"btw, game emang tidak terpisahkan dengan teknik algoritma"