pengelompokan jenis tanah menggunakan algoritma clustering k

Pengelompokan Jenis Tanah Menggunakan Algoritma Clustering K-Means

Nama : Farisa ArriyaniNPM : 10104657Pembimbing : Ibu Sulistyo Puspitodjati,

SSi., Skom., MSc.

Latar Belakang Masalah

Perkembangan pembangunan di negara Indonesia yang meningkat dari tahun ke tahun

banyaknya proyek-proyek pembangunan jalan raya di berbagai tempat

diperlukan pengetahuan mengenai struktur dan jenis tanah dari wilayah yang akan dibangun.

Banyak faktor yang mempengaruhi pemilihan jenis penelitian tanah yang diharapkan bisa memberikan data yang cukup akurat

Pengelompokkan data tanah dengan alat sondir sulit mengenali beberapa objek tanah yang berbeda-beda tapi mempunyai sifat serupa

terdapat objek-objek yang masuk ke dalam kelompok yang tidak sesuai.

dibutuhkan pengetahuan mengenai jumlah kelompok yang benar agar objek-objek tanah tersebut dapat dikelompokkan sesuai dengan karakteristik yang dimilikinya

Pembatasan Masalah

penelitian suatu data tanah dengan menggunakan Pengklasteran k-Means dan pendekatan bootstrapped method

Proses pengklasteran menggunakan perangkat lunak Weka 3.5.7.

Data yang digunakan adalah data proyek Ruas Jalan Pontianak-Tayan.

Jumlah klaster (k) yang dipakai dimulai dari 6, 7, 8, 9, dan 10 dan jumlah seed dimulai dari 1, 10, 20, dan 30.

Tujuan Penelitian

mengelompokkan dan menemukan jumlah klaster(kelas) yang paling tepat/ akurat terhadap data tanah

menganalisa hasilnya untuk menentukan parameter-parameter batasan(berdasarkan karakteristik) pada masing-masing klaster untuk mengklasifikasian tanah secara umum

Diharapkan penelitian ini dapat digunakan sebagai landasan untuk tahapan pelabelan, atau pengklasifikasian secara rinci pada pengembangan selanjutnya

Penulisan

Bab I : PendahuluanBab II : Landasan TeoriBab III : Metode PenelitianBab IV : Hasil PenelitianBab V : Penutup

Tanah material yang terdiri dari :

- butiran mineral padat yang tidak tersementasi (terikat secara kimia) satu sama lain- bahan-bahan organik yang telah melapuk (yang berpartikel padat) disertai zat cair & gas yang mengisi ruang-ruang kosong di antara partikel-partikel padat tersebut

untuk mendiskripsikan tanah dibutuhkan pengetahuan tentang : - sifat-sifat asli tanah - warna- formasi batuannya - tekstur- ukuran butirnya - konsistensi

Secara garis besar, tanah dibagi menjadi 3 bagian :1. Tanah berbutir kasar: kerikil (gravel), pasir (sand) 2. Tanah berbutir halus: lanau( slit/sloam ), lempung ( clay ), lempung berat ( heavy clay )3. tanah yang bersifat organik. Contoh: tanah gambut (peat soil)

Atribut Tanah : - kedalaman (depth(d) dalam satuan meter (m) - tekanan konus (qc) dalam satuan (kg/cm2)- jumlah hambatan (JH) dalam satuan (kg/cm2)- Perlawanan gesek dalam satuan (kg/cm2)

Pengklasteran (Clustering) pengelompokkan sejumlah data atau objek ke dalam klaster (group)

sehingga dalam setiap klaster akan berisi data yang semirip mungkin Termasuk unsupervised learning Data pada teknik pengklasteran tidak diketahui keluarannya

(outputnya atau labelnya) digunakan fungsi kriteria: jumlah dari kesalahan kuadrat (sum of

squared-error, SSE) yang dapat mengukur kualitas klastering yang dibuat

p Є Ci = tiap data poin pada cluster i, mi = centroid dari cluster i, d = jarak/ distances/ variance terdekat pada masing-masing cluster i.

mengoptimalkan nilai fungsi kriteria tersebut Nilai SSE tergantung pada jumlah klaster dan bagaimana data

dikelompokkan ke dalam klaster-klaster. Semakin kecil nilai SSE semakin bagus hasil klastering yang dibuat

2

1

,

k

i Cpi

i

mpdSSE

Metode k-Means

Termasuk partitioning clustering objek-objek dikelompokkan ke dalam k kelompok atau klaster Untuk melakukan klastering ini, nilai k harus ditentukan terlebih

dahulu Kluster-kluster tersebut mempunyai suatu nilai tengah / nilai

pusat yang disebut dengan centroid menggunakan ukuran ketidakmiripan untuk mengelompokkan

objek. Ketidakmiripan diterjemahkan dalam konsep jarak (distance (d)) Jika jarak dua objek atau data titik cukup dekat, maka dua objek

itu mirip. Semakin dekat berarti semakin tinggi kemiripannya Tujuan dari k-Means : meminimalisir total dari jarak elemen-

elemen antar kluster (jarak antara suatu elemen dalam sebuah kluster dengan nilai centroid kluster tersebut)

Algoritma k-Means

1. Pilih jumlah klaster k yang diinginkan 2. Inisialisasi k pusat klaster (centroid) secara random/ acak3. Tempatkan setiap data atau objek ke klaster terdekat. Kedekatan dua

objek ditentukan berdasar jarak. Jarak yang dipakai pada algoritma k-Means adalah Euclidean distance (d).

x = x1, x2, . . . , xn, dan y = y1, y2, . . . , yn merupakan banyaknya n atribut(kolom) antara 2 record.

4. Hitung kembali pusat klaster dengan keanggotaan klaster yang sekarang. Pusat klaster adalah rata-rata (mean) dari semua data atau objek dalam klaster tertentu.

n

iiiEuclidean yxyxd

1

2,

Algoritma k-Means (Lanjutan)

Misal: untuk masing-masing klaster terdapat n poin-poin data (a1,b1,c1), (a2,b2,c2), (a3,b3,c3),. . . , (an,bn,cn), dimana a,b,c merupakan jumlah atribut (dimensi dari data), centroid dari poin-poin data tersebut adalah nilai mean/ titik tengahnya yaitu

Sebagai contoh, poin-poin data (1,1,1), (1,2,1), (1,3,1), dan (2,1,1) memiliki centroid yaitu

Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru. Jika pusat klaster sudah tidak berubah lagi, maka proses pengklasteran selesai. Atau, kembali lagi ke langkah nomor 3 sampai pusat klaster tidak berubah lagi/ stabil atau tidak ada penurunan yang signifikan dari nilai SSE (Sum of Squared Errors)

ncnbnam iiik ,,

00.1,75.1,25.14

1111,4

1321,4

2111

km

Contoh Algoritma k-Means

Instances X YA 1 3

B 3 3

C 4 3

D 5 3

E 1 2

F 4 2

G 1 1

H 2 1

1. Tentukan jumlah klaster k=22. Tentukan centroid awal secara

acak misal dari data disamping m1 =(1,1), m2=(2,1)

3. Tempatkan tiap objek ke klaster terdekat berdasarkan nilai centroid yang paling dekat selisihnya(jaraknya). Pada tabel 2.Didapatkan hasil: anggota cluster1 = {A,E,G}, cluster2={B,C,D,F,H}. Nilai SSE yaitu :

=

2

1

,

k

i Cpi

i

mpdSSE

Tabel 1 Data point

Gambar 1 tampilan data awal

Contoh Algoritma k-Means(Lanjutan)

4. Menghitung nilai centroid yang baru :

5. Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru. Pada tabel 3. Nilai SSE yang baru :

Tabel 2

2,13/123,3/1111 m

4,2;6,35/12333,5/245432 m

Gambar Clusters dan centroid setelah tahap pertama.


Terdapat perubahan anggota cluster yaitu cluster1={A,E,G,H}, cluster2={B,C,D,F}, maka cari lagi nilai centroid yang baru yaitu : m1=(1,25;1,75) dan m2=(4;2,75)

Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru. Pada tabel 4. Nilai SSE yang baru :

Tabel 3

Gambar Clusters dan centroid setelah tahap kedua.


Dapat dilihat pada tabel 4.Tidak ada perubahan anggota lagi pada masing-masing cluster

Hasil akhir yaitu :cluster1={A,E,G,H}, dan cluster2={B,C,D,F} dengan nilai SSE = 6,25 dan jumlah iterasi 3

Tabel 4

Metode Bootstrapped

merupakan metoda berbasis-komputer yang sering digunakan untuk menilai ketelitian dari banyak penaksiran statistik yang dikembangkan oleh Efron (1979)

Salah satu pendekatan yang digunakan untuk menentukan jumlah cluster yang paling tepat saat menggunakan metode k-means

melakukan sampling dengan perubahan terhadap data asli secara berulang-ulang untuk membangun beberapa set data palsu

Untuk masing-masing data set palsu, dihitung perkiraan yang diharapkan

Algoritma Bootstrapped

1. pilah data(sample) menjadi dua set dengan ukuran tertentu(random), misal 80%:20%. Yang 80% sebagai data training(untuk memodel). Sedangkan yang 20% sebagai data validasi.

2. pemodelan menggunakan k-means terhadap data training. Catat persentase data yang menjadi bagian masing-masing cluster dan cluster center/ SSE dari masing-masing cluster.

3. pemodelan menggunakan k-means terhadap data validasi.4. Bandingkan persentase data yang menjadi bagian dari masing-

masing cluster dan nilai SSE antara data training dan data validasi.

5. Ulangi langkah 1-4 beberapa kali untuk menambah akurasi. 6. Model yang mempunyai perbedaan antara data training dan

data validasi data terkecil yang dipilih sebagai model (atau jumlah kelompok ) yang paling tepat. perbedaan tersebut dicari dengan nilai rata-rata perbedaan setiap pemodelan yang dilakukan

Percobaan Menggunakan Weka(Persiapan data/preprocess)

Menggunakan data tanah dari proyek Ruas Jalan Pontianak-Tayan sebanyak 150 data (record) dan 8 atribut

Menghilangkan 3 atribut yang diperoleh dari hasil perhitungan yaitu : Hambatan Pelekat (HP), Jumlah Hambatan Pelekat (JHP), dan Hambatan Setempat (HS)

Data mentah : 150 record dan 5 atribut Data terdiri dari 4 atribut numerik (untuk clustering)

dan 1 atribut nominal (deskripsi tanah) untuk pelabelan

Data disimpan dalam file .csv atau .arff

Percobaan Menggunakan Weka (Lanjutan)

Gambar Tampilan data pada preprocess

Percobaan Menggunakan Weka (Lanjutan)

Gambar Pilihan filterisasi filters.unsupervised.instance.Resample

Gambar Parameter-parameter pada filterisasi filters.unsupervised.instance.Resample

Proses Clustering pada Weka

Percobaan dilakukan dengan 2 pendekatan :1. Pendekatan Pertama : menggunakan metode bootstrapped (membagi data menjadi data training dan data validasi dengan jumlah atribut yang sama(5)) yaitu : 65%;35%, 70%;30%, 75%;25%, 80%;20%, 85%;15% 2. Pendekatan kedua : pengklasteran terhadap data utuh mentah yaitu 150 record dan 4 atribut numerik serta 1 atribut nominal

Percobaan menggunakan mode use training set untuk menentukan jumlah cluster dan classes to clusters evaluation untuk pelabelan

jumlah klaster (k) yaitu dimulai dari 6 (berdasarkan jumlah kelas pada data asli), kemudian 7, 8, 9, dan 10

Nilai seed yang dipilih adalah mulai dari 1, 10, 20, dan 30

Percobaan Menggunakan Weka (Panel cluster pada Weka)

Percobaan Menggunakan Weka

Gambar Parameter-parameter pada SimpleKMeans

Gambar Daftar algoritma pada panel “Choose”

Gambar Contoh ignore attributes deskripsi tanah

Hasil Percobaan Pendekatan Pertama

Output pada Pendekatan Pertama (Pengklasteran terhadap data training(65%) dengan jumlah klaster(k=6) dan seed 1)

Hasil Percobaan Pendekatan Pertama (Lanjutan)

Output pada Pendekatan Pertama (Pengklasteran terhadap data validasi(35%) dengan jumlah klaster(k=6) dan seed 1)

Analisis Pendekatan Pertama

Analisis Pendekatan Pertama (Lanjutan)

Hasil Percobaan Pendekatan Kedua

Output pada Pendekatan Kedua (Pengklasteran terhadap data utuh(mentah) dengan k=10 dan seed 1)

Analisis Pendekatan Kedua Jarak antara anggota di dalam klaster atau WCV (Within Cluster Variation)

diasumsikan oleh nilai SSE sebesar 3.83, jumlah iterasi sebanyak 15, dan jarak antar klaster atau BCV (Between Cluster Variation) yaitu :

2

2

2

2

6,89412,55,42105,66875,18235,125,141667,34286,13333,6

7333,641765,17875,119474,185,55882,56875,408333,81905,47778,43

1333,562353,11375,77368,128125,37647,34375,266667,57619,24444,37

2533,71294,268,247053,39,152,197375,43333,222,121556,29

2222 275,41754,1334793,921032,107 601,1703105,17890421,8552095,11471

222,39617

041,199

Analisis Pendekatan Kedua (Lanjutan)

Gambar Visualisasi scatter plot pada data tanah dengan k 10 dan seed 1 Gambar Jendela Instances Info


Gambar Informasi terhadap data utuh(mentah) dengan k=10

dan seed 1 pada classes to clusters evaluation

Kesimpulan perbandingan perbedaan antara data training dan data validasi

menghasilkan nilai SSE dan persentase instance terkecil berada pada jumlah klaster/ kelompok (k=10) dan seed 1.

jumlah kelompok (k=10) diatas merupakan yang paling baik(akurat) karena semakin kecil nilai SSE maka semakin baik pula hasil pengklasteran yang dilakukan.

Jarak antar anggota di dalam klaster atau WCV (Within Cluster Variation) sebesar 3.83 yang dilihat dari nilai SSE-nya

jumlah iterasi sebanyak 15 jarak antar klaster atau BCV (Between Cluster Variation) sebesar

199,041. Pengelompokan jenis tanah didapat berdasarkan karakteristik pada

masing-masing kelompok(cluster 0 sampai 9) berdasarkan range tiap-tiap atribut (kedalaman, tekanan konus(qc), jumlah hambatan, dan perlawanan gesek).

Pelabelan(pemberian nama kelas) didapatkan hasil klaster 3,4,5, dan 7 tidak memiliki label. Sedangkan klaster 0 memiliki label Sand, klaster 1 slit/sloam, klaster 2 clay, klaster 6 Peat, klaster 8 Heavy Clay, dan klaster 9 Gravel yang didapatkan berdasarkan atribut nominal pada data.

Saran

menambah jumlah percobaan menjadi 10 kali atau lebih untuk pembagian data(sample)

menambah jumlah klaster lebih dari 10 serta penggunaan seed yang berbeda-beda agar hasil yang didapat menjadi lebih akurat.

menggabungkan algoritma k-means dengan algoritma lainnya seperti misalnya algoritma genetik (GA) untuk mendapatkan hasil yang optimal.

pengelompokan jenis tanah menggunakan algoritma clustering k

Documents