Algoritma K-means clustering

13Nov08

K-Means adalah teknik yang cukup sederhana dan cepat dalam pekerjaan pengelompokkan data (clustering). Prinsip utama dari teknik ini adalah menyusun k buah prototipe/pusat massa (centroid)/rata-rata (mean) dari sekumpulan data berdimensi n. Teknik ini mensyaratkan nilai k sudah diketahui sebelumnya (a priori). Algoritma k-means dimulai dengan pembentukan prototipe cluster di awal kemudian secara iteratif prototipe cluster ini diperbaiki hingga konvergen (tidak terjadi perubahan yang signifikan pada prototipe cluster). Perubahan ini diukur menggunakan fungsi objektif J yang umumnya didefinisikan sebagai jumlah atau rata-rata jarak tiap item data dengan pusat massa kelompoknya. Secara lebih detil algoritma k-means adalah seperti berikut :

  1. inisialisasi nilai J (misal MAXINT)
  2. Tentukan prototipe cluster awal (bisa secara acak ataupun dipilih salah satu secara acak dari koleksi data)
  3. Masukkan tiap satuan data ke dalam kelompok yang jarak dengan pusat massa-nya paling dekat
  4. ubah nilai pusat massa tiap cluster sebagai rata-rata (mean) dari seluruh anggota kelompok tersebut
  5. Hitung fungsi objektif J
  6. jika nilai J sama dengan sebelumnya, berhenti atau ulangi langkah 3


Berikut ini adalah contoh implementasi algoritma k-means dalam delphi.

{ garis besar kode }
type
  TTrainingData=record
    feature : array of real;
    truth : integer;
  end;

procedure DoKMeans;
begin
  Initialize;
  repeat
    Inc(NumStep);

    ReviseMinimum;
    CalculateCentroid;
    MeasureAccuracy;
    
  until IsConverge or (NumStep > MaxStep);
end;
var
  NumStep,MaxStep : longint;
  CurJ, OldJ : double;
  Err, MinErr : double;
  NumCorrect : integer;

  proposal : array of array of integer;
  centroid : array of array of double;
  distance : array of array of double;
  solution : array of integer;

  procedure RandomPick;
  var
    p, q, r : integer;
  begin
    for p := 0 to NumClass-1 do begin
      if p = 0 then
        r := Random(Length(FData))
      else
        r := r + Random((Length(FData)-r));
        
      for q := 0 to FeatureLength-1 do
        centroid[p][q] := FData[r].feature[q];
    end;
  end;

  procedure CalculateDistanceFromCentroids;
  var
    i, j, k : integer;
    tmp : double;
  begin
    for j := 0 to High(FData) do
      for i := 0 to NumClass-1 do begin
        tmp := 0.0;
        for k := 0 to FeatureLength-1 do
          tmp := tmp + sqr(FData[j].feature[k]-centroid[i][k]);
        distance[j][i] := sqrt(tmp);
      end;
  end;

  procedure Initialize;
  var
    p : integer;
  begin
    NumStep := 0;
    MaxStep := 3000;
    MinErr  := MAXINT;
    OldJ    := MAXINT;
    
    setlength(proposal, NumClass);
    setlength(centroid, NumClass);
    for p := 0 to NumClass-1 do begin
      setlength(proposal[p], 0);
      setlength(centroid[p], FeatureLength);
    end;

    setlength(solution, Length(FData));
    setlength(distance, Length(FData));
    for p := 0 to high(FData) do
      Setlength(distance[p], NumClass);

    RandomPick;
    CalculateDistanceFromCentroids;
  end;

  procedure CalculateCentroid;
  var
    i, j, k : integer;
    NumInstances : integer;
  begin
    for j := 0 to NumClass-1 do begin
      NumInstances := 0;
      for k := 0 to FeatureLength-1 do
          centroid[j][k] := 0.0;

      for i := 0 to High(proposal[j]) do begin
        for k := 0 to FeatureLength-1 do
          centroid[j][k] := centroid[j][k] + FData[proposal[j][i]].feature[k];
        Inc(NumInstances);
      end;

      if NumInstances > 0 then
        for k := 0 to FeatureLength-1 do
          centroid[j][k] := centroid[j][k] / NumInstances;
    end;
    CalculateDistanceFromCentroids;
  end;

  function IsConverge:boolean;
  var
    i, j : integer;
  begin
    CurJ := 0;
    for i := 0 to NumClass-1 do
      for j := 0 to High(proposal[i]) do
        CurJ := CurJ + distance[proposal[i][j]][i];

    Result := (Abs(CurJ-OldJ) < 1e-2);
    OldJ := CurJ;
  end;

  procedure ReviseMinimum;
  var
    i, j, p, minidx : integer;
    min : double;
  begin
    for p := 0 to NumClass-1 do
      setlength(proposal[p], 0);
      
    for j := 0 to High(FData) do begin
      minidx := 0;
      min := distance[j][minidx];
      for i := 1 to NumClass-1 do
        if distance[j][i] < min then begin
          minidx := i;
          min := distance[j][minidx];
        end;
      setlength(proposal[minidx], length(proposal[minidx])+1);
      proposal[minidx][high(proposal[minidx])] := j;
    end;
  end;

  procedure MeasureAccuracy;
  var
    i, j : integer;
    parsolution : array of integer;
  begin
    NumCorrect := 0;
    setlength(parsolution, Length(FData));
    for i := 0 to NumClass-1 do
      for j := 0 to High(proposal[i]) do 
        parsolution[proposal[i][j]] := i+1;
    
    for i := 0 to High(FData) do
      if (parsolution[i] = FData[i].truth) then
        Inc(NumCorrect);

    Err := (Length(FData)-NumCorrect) * 100 / Length(FData);
    if Err < MinErr then begin
      MinErr := Err;
      for j := 0 to High(FData) do
        solution[j] := parsolution[j];
    end;
    Setlength(parsolution, 0);
  end;

Aplikasi
Algoritma nggak seru kalau tidak ada aplikasinya, jadi saya tampilkan skrinsyut aplikasi algoritma k-means untuk kuantisasi warna citra.

citra asal

citra asal


citra hasil

citra hasil

Penutup
Algoritma k-means clustering walaupun cepat tetapi keakuratannya tidak dijamin. Seringkali algoritma ini mengalami konvergensi prematur. Pada algoritma di atas juga tidak dijamin jarak antara masing-masing centroid tidak merentang sehingga jika ada dua atau lebih kelompok dengan titik pusat massa yang berdekatan atau terdapat kelompok yang tidak memiliki anggota maka hasilnya akan tidak memuaskan.

About these ads


23 Responses to “Algoritma K-means clustering”

  1. blog anda telah terdaftar di lomba blogging oss week. sebuah e-mail telah dikirim ke e-mail Anda, atau klik http://poss.itb.ac.id/lombablog untuk informasi lebih lanjut

  2. 2 Ranum

    Mas, BIsa kasi contoh/ gambaran implementasi Algoritma Aprioiri untuk Association Rule ???
    Soalnya aku sedang buat TA tentang Data Mining dengan metode Association Rule untuk analisa pola belanja konsumen pada Supermarket. TA ku terhambat pada tahap implementasinya.
    Aplikasi yang aku rancang Pakai Delphi 7 dan SQL Server 2000
    Terima Kasih

  3. wow, cool

  4. 4 Sky

    Mas Bisa minta program lengkapnya…, soalnya aku sedang membuat tugas yang berkaitan dengan ini. thanks…

  5. 5 ibeth

    mas…
    boleh saya minta penjelasan tentang perbedaan hasil algoritma K-means dengan Expectation Maximization pada several dataset soalnya kami dapat topik ini, mohon pencerahannya.. thanks

  6. mas,,,
    tanya dong…
    bagaimana meng-clusterkan sebuag image?
    bagaimana extract fiturenya?
    mohon bantuannya…

    kirim ke email aja ya
    tq

  7. 7 purwA

    mas…makasih nih artikelnya,,,,,sangat berguna bagi saya…

    saya mau tanya nich……..

    kalo kluster k-means buat data yang matrik bisa tidak?….mohon penjelasannya yach…..

    kirim email ajah yach mas,,

    thanxs

  8. 8 ach samsudin choir

    punya algoritmanya complete linkage dalam contoh aplikasi ga?
    thx ya, algoritma ttg K-Means Ok bgt….

  9. 9 may

    kalo pke matlab gmn ya?

    • saya nggak pernah pake matlab tapi algoritmanya sederhana kok:
      0 tentukan k nilai
      1 untuk tiap data, pilih nilai yang paling dekat
      2 update nilai tsb dari rata-rata data yang memilih nilai tsb
      3 ulangi langkah 1 sampai kondisi berhenti (maksimal iterasi atau nggak ada lagi yang berubah pihak)

  10. numpang sedot boz…
    thanks ya..

    Best Regards

  11. contoh programnya ada gk bos?
    bingung form aplikasinya gmn

  12. 13 yogi

    mas…
    minta tolong dikasoh pencerahan…
    algoritma yang palng cocok dan mudah untuk text mining untuk pencarian text itu apa ya???
    perispan buat TA…..

  13. mas saya minta tolong gimana sich… caranya menghapus area bayangan pada image dengan menggunakan fuzzy K-means… jadi cm area bayanganya aja yang dihapus…tanpa harus menghapus warna dasar dari image tersebut. kira2 source code delphinya kyak gm…!!!
    bisa kirim lewat email saya “ekawiarta@gmail.com” soalnya saya lg menyelesaikan tugas akhir… tolong saya mas…!!! atas bantuanya saya ucapkan terima kasih..!!

  14. mas saya melihat source code fuzzy k-means diatas susah untuk dimengerti kurang jelas seperti komponen2 apa saja yang diperlukan, pendeklarasian variabel dan function2 yang digunakan… tolong dijelaskan mas…..!!!!!!!

  15. 16 oka

    Mas mohon pencerahaannya nih, apa bisa diterapkan pada basis web? Truss klo jumlah centoid di set satu tapi dengan data multi dimensi bisa ga? Klo centroid kita yang tentukan bole ga pake algoritma sendiri, tapi nilai centroid kita tentukan sendiri tanpa mengambil dari data yang ada?
    Trims

  16. 17 alil

    mas boleh minta tolong kasih contoh aplikasi yang pake VB donk…. soalnya saya sedang ngerjain TA dan bingung tentang pengclusterannya….. thanx

  17. 18 tanya

    mas, kalo pemrograman untuk matlab pengklusteran data mahasiswa punya contohnya gak?

  18. manrap gannn!!!! terimaksih,, kebetulan saya lagi belajar ini… ^^

  19. mas mo nanya …
    lo nerapin k-mean pd sistem penerimaan karyawan bisa gak,,,,,,?
    jika bisa berarti penerimaan karyawan itu gak isi istilah gugur (tidak diterima) ya, soalnya saya berpikiran k-mean itu gak ada istilah tidak.

  20. 21 Bana

    Wah bagus Mas, gampang dimengerti.
    Berarti awalnya secara apriori qt tentuin count of pusat massa dan pusat massa nya ya. Lalu akan ada data2 yg ngumpul disana. Kemudian, hitung mean unt masing2 cluster yg terbentuk. Mean inilah sebagai pusat data yg baru ya?
    Kemudian secara iteratif, akan ada data yg berkumpul lg di pusat massa yg baru..Trus looping hingga didapatkan clustering terbaik :)

    Best,
    Ana

    • ya, betul seperti itu

  21. Mungkin ini bisa membantu yang membutuhkan contoh/implementasi dengan bahasa pemprograman php, http://bitscript-tipstrikpemprograman.blogspot.com/2012/10/contoh-algoritma-k-means-dan-k-medoid.html


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s


Ikuti

Get every new post delivered to your Inbox.

Bergabunglah dengan 2.048 pengikut lainnya.

%d bloggers like this: