PPT Data Mining metode k Means tugasssss

Data mining

1. Clustering dengan K- Means PERTEMUAN 12 Program Studi Teknik Informatika

2. K- Means Metode pengelompokan data partitioning (non hierarki). Data berkarakteristik sama dimasukkan ke dalam satu kelompok. Meminimalk an v a r ia s i d a lam s a tu k e lomp o k d a n m e m a ksim a lkan kelompok.

3. Algoritma K-Means Langkah 1: Tentukan nilai k = jumlah cluster. Langkah 2 : Tentukan k centroid awal dengan memilih k data secara random. Bisa dipilih k data pertama sebagai centroid, atau k data terjauh sebagai centroid. Langkah 3 : Hitung jarak tiap data ke centroid dengan menggunakan persamaan Euclidean Distance. Berikut rumus yang digunakan untuk menghitung persamaan Euclidean Distance . Langkah 4 : Masukkan tiap data ke dalam cluster dengan jarak centroid terdekat . Langkah 5 : Hitung ulang centroid menggunakan rata-rata ( mean ) data dalam suatu cluster. C Langkah 6: Ulang langkah 3, 4, 5 sampai konvergen , yaitu sampai tidak ada lagi perpindahan objek dari satu cluster ke cluster yang lain.  

4. Algoritma K Means Mulai Berhenti Jumlah cluster k Inisialisasi centroid Hitung jarak objek ke centroid Kelompokkan objek ke dalam cluster dengan jarak centroid minimum Masih ada perpindahan objek ? Hitung ulang posisi centroid Hasil cluster Ya Tidak

5. Fakta tentang k-means Merupakan algoritma clustering yang cukup efisien dan cepat dengan O ( tkn ). n : jumlah data k : jumlah cluster t : jumlah iterasi Jumlah cluster, k , harus ditentukan di awal . Hasil clustering sensitive terhadap initial condition . Hasil clustering bisa berbeda tergantung pada pemilihan jumlah cluster ( k ) dan posisi awal centroid.

6. Inisialisasi centroid secara random www.its.ac.id Jika pemilihan k dan centroid awal kurang tepat , a lgoritma bisa terjebak pada local optimum . Bagaimana meningkatkan peluang untuk mendapat hasil yang global optimum ? Jalankan algoritma k-means berulang kali menggunakan nilai awal yang berbeda-beda Pilih hasil clustering yang paling optimal Sub-optimal Clustering Optimal Clustering

7. Evaluasi dan Validasi Model Clustering Tendency Clustering Tendency merupakan kecenderungan suatu data untuk terklasifikasi kedalam cluster tertentu. Biasanya, data yang memiliki clustering tendency yang tinggi akan lebih mudah dikelompokkan ke dalam suatu cluster yang sesuai dengan karakteristik data tersebut. Clustering tendency dapat diukur dengan menggunakan beberapa metode: Silhoutte Coefficient. Nilai silhoutte score berkisar antara -1 hingga 1, dengan nilai yang mendekati 1 menunjukkan bahwa kemiripan atau kesamaan antar data dalam satu cluster sangat tinggi, sedangkan nilai yang mendekati 0 menunjukkan bahwa kemiripan atau kesamaan antar data dalam satu cluster rendah adalah jarak rata-rata ke instance lain dalam cluster yang sama, adalah jarak rata-rata ke instance cluster terdekat berikutnya.  

8. Pemilihan jumlah cluster, k Untuk menentukan jumlah cluster yang tepat, dapat digunakan metode berikut: Metode Elbow Metode Elbow merupakan metode empiris untuk mencari jumlah cluster yang optimal pada suatu dataset.

9. Pemilihan jumlah cluster, k Untuk menentukan jumlah cluster yang tepat, dapat digunakan metode berikut: b. Metode Silhoutte metode untuk mencari jumlah cluster yang optimal serta interpretasi dan validasi konsistensi dalam cluster data. Metode silhoutte menghitung koefisien silhoutte setiap titik yang mengukur seberapa mirip suatu titik dengan clusternya sendiri dibandingkan dengan cluster lainnya. Semakin besar nilai silhoutte score, semakin baik pembagian cluster yang didapat. https://miro.medium.com/v2/resize:fit:640/format:webp/1*FDahPZQHWMxaZSSf369NHA.png

10. Clustering Quality Clustering quality adalah seberapa baik hasil clustering yang diperoleh dari suatu proses clustering. Clustering quality merupakan indikator penting untuk menentukan seberapa baik hasil clustering yang diperoleh, sehingga dapat membantu dalam menentukan pembagian kelompok yang tepat dan efektif. Terdapat beberapa metode yang dapat digunakan untuk mengukur clustering quality, diantaranya: Silhoutte Score : Skornya dibatasi antara -1 untuk pengelompokan yang salah dan +1 untuk pengelompokan yang sangat padat. Skor sekitar nol menunjukkan cluster yang tumpang tindih. Davies Bouldin Index : Indeks ini menandakan rata-rata ‘kesamaan’ antar cluster, dimana kesamaan merupakan ukuran yang membandingkan jarak antar cluster dengan ukuran cluster itu sendiri. Nol adalah skor serendah mungkin. Nilai yang mendekati nol menunjukkan partisi yang lebih baik. Indeks Calinski-Harabasz : Skornya lebih tinggi ketika clusternya padat dan terpisah dengan baik, yang berhubungan dengan konsep standar sebuah cluster. Adjusted Rand Index : Adjusted mutual information V-measure

11. Studi Kasus Diketahui dataset produksi cabai rawit di Indonesia yang terdiri dari 10 provinsi untuk melakukan perhitungan manual menggunakan algoritma K-Means. Dataset terdiri dari 6 fitur, yaitu 1 fitur provinsi dan lima fitur lainnya merupakan fitur tahun produksi. Berikut ini tampilan dari dataset yang akan digunakan Provinsi Tahun 2021 Tahun 2020 T ahun 2019 Tahun 2018 Tahun 2017 Aceh 51686 64782 61887 62168 53800 Sumatera Utara 78663 61160 49246 39825 31727 Sumatera Barat 35118 33356 31782 25178 22872 Riau 6694 8627 8120 12691 10902 Jambi 11526 13588 9880 8273 8352 Sumatera Selatan 11562 11645 11014 13449 15826 Bengkulu 16278 11476 11118 11353 7823 Lampung 10921 10558 12796 14649 14705 Kep Bangka Belitung 3954 3386 2002 2036 1729 Kep Riau 1627 2230 2339 1716 1061

12. Studi Kasus Menentukan jumlah cluster Langkah pertama adalah menentukan jumlah cluster yang akan dibuat. Pada kasus ini, kita akan menggunakan sebanyak 3 cluster, yaitu tinggi, sedang dan rendah. 2 . Melakukan Normalisasi Data Selanjutnya kita akan melakukan normalisasi data, karena terdapat perbedaan besaran antara fitur satu terhadap fitur lainnya, sehingga kita dapat memperkecil besaran angka tersebut dengan melakukan normalisasi pada fitur setiap fitur dengan teknik min-max normalization yang memiliki rumus sbb: Diketahui :     Tahun_2021 Tahun_2020 Tahun_2019 Tahun_2018 Tahun_2017 min 1627 2230 2002 1716 1061 max 78663 64782 61887 62168 53800 Contoh perhitungan normalisasi: Aceh =  

13. Studi Kasus Provinsi Tahun 2021 Tahun 2020 T ahun 2019 Tahun 2018 Tahun 2017 Aceh 0,6498 1,0000 1,0000 1,0000 1,0000 Sumatera Utara 1,0000 0,9421 0,7889 0,6304 0,5815 Sumatera Barat 0,4347 0,4976 0,4973 0,3881 0,4136 Riau 0,0658 0,1023 0,1022 0,1815 0,1866 Jambi 0,1285 0,1816 0,1316 0,1085 0,1382 Sumatera Selatan 0,1290 0,1505 0,1505 0,1941 0,2800 Bengkulu 0,1902 0,1478 0,1522 0,1594 0,1282 Lampung 0,1206 0,1331 0,1802 0,2139 0,2587 Kep Bangka Belitung 0,0302 0,0185 0,0000 0,0053 0,0127 Kep Riau 0,0000 0,0000 0,0056 0,0000 0,0000 Lakukan hal serupa pada fitur-fitur lainnya, sehingga diperoleh hasil perhitungan nilai normalisasi seluruh data.

14. Studi Kasus 3. Iterasi 1 : Menentukan Centroid Awal Cluster Kemudian tentukan centroid awal cluster secara acak. Kita bisa menentukan centroid dengan bebas, misalnya yang kita pilih adalah sbb:   Tahun_2021 Tahun_2020 Tahun_2019 Tahun_2018 Tahun_2017 Tinggi (C1) 1,000 1,000 1,000 1,000 1,000 Sedang (C2) 0,650 0,942 0,789 0,630 0,581 Rendah (C3) 0,030 0,018 0,006 0,005 0,013 4. Menghitung jarak data dengan Centroid Ingat bahwa centroid pada langkah 3 dapat dipilih secara acak. Selanjutnya kita hitung jarak antara data dengan centroidnya. Persamaan yang digunakan adalah Euclidean Distance seperti berikut: Contoh perhitungan jarak data ke-1 pada masing-masing cluster adalah  

15. Studi Kasus Lakukan perhitungan yang sama untuk data lainnya terhadap setiap centroid seperti contoh sebelumnya, sehingga akan diperoleh jarak pada masing-masing cluster di iterasi pertama sbb: Provinsi Jarak C1 Jarak C2 Jarak C3 Aceh 0,3502 0,5997 2,0738 Sumatera Utara 0,5997 0,3500 1,7669 Sumatera Barat 1,2422 0,6449 0,9708 Riau 1,9535 1,3695 0,281 Jambi 1,9290 1,3234 0,2803 Sumatera Selatan 1,8357 1,2597 0,3941 Bengkulu 1,8887 1,2942 0,3178 Lampung 1,8342 1,2581 0,3949 Kep Bangka Belitung 2,2064 1,6043 0,0056 Kep Riau 2,2336 1,6307 0,0378

16. Studi Kasus 5. Pengelompokan Data Kolom yang diberikan warna menandai nilai paling minimal di antara baris pada setiap data provinsi. Jika sudah didapatkan perhitungan nilai minimalnya seperti di slide sebelumnya, kita dapat mengelompokan data sesuai dengan cluster-nya. Hasil sbb: Provinsi C1 C2 C3 Aceh √ Sumatera Utara √ Sumatera Barat √ Riau √ Jambi √ Sumatera Selatan √ Bengkulu √ Lampung √ Kep Bangka Belitung √ Kep Riau √

17. Studi Kasus 6. Penentuan Nilai Centroid Baru Setelah didapatkan cluster pada iterasi pertama, kita tentukan kembali nilai centroid baru berdasarkan data anggota tiap cluster yang sudah didapatkan menggunakan rumus sbb: Menghitung centroid baru pada fitur tahun_2021 dengan cara sbb: Lakukan perhitungan yang sama terhadap fitur “tahun_2020” hingga fitur “tahun_2017” sehingga diperoleh nilai centroid baru. Iterasi selanjutnya dilakukan dengan cara yang sama seperti langkah ke-4 sampai langkah ke-6 hingga tidak ada perubahan data dari satu cluster ke dalam cluster lainnya. Setelah proses iterasi lanjutan dilakukan dan data dipastikan tidak ada perubahan dari cluster satu ke cluster lainnya. Maka akan diperoleh hasil akhirnya.  

18. Studi Kasus   Tahun 2021 Tahun 2020 Tahun 2019 Tahun 2018 Tahun 2017 C1 0,6498 1 1 1 1 C2 0,71735 0,71985 0,6431 0,50925 0,49755 C3 0,0949 0,104829 0,103186 0,123243 0,143486 NIlai Centroid Baru Iterasi Selanjutnya : Iterasi 2 4. Menghitung jarak data dengan Centroid Selanjutnya kita hitung jarak antara data dengan centroidnya. Persamaan yang digunakan adalah Euclidean Distance seperti berikut: Contoh perhitungan jarak data ke-1 pada masing-masing cluster adalah  

19. Studi Kasus Lakukan perhitungan yang sama untuk data lainnya terhadap setiap centroid seperti contoh sebelumnya, sehingga akan diperoleh jarak pada masing-masing cluster di iterasi kedua sbb:   C1 C2 C3 Aceh 0,0000 0,8389 1,8482 Sumatera Utara 0,6945 0,4151 1,5619 Sumatera Barat 1,1268 0,4151 0,7538 Riau 1,8123 1,1413 0,0781 Jambi 1,7981 1,0899 0,0899 Sumatera Selatan 1,6978 1,0294 0,1707 Bengkulu 1,7672 1,0512 0,1220 Lampung 1,6944 1,0290 0,1700 Kep Bangka Belitung 2,0764 1,3663 0,2309 Kep Riau 2,1003 1,3950 0,2555

20. Studi Kasus 5. Pengelompokan Data Kolom yang diberikan warna menandai nilai paling minimal di antara baris pada setiap data provinsi. Jika sudah didapatkan perhitungan nilai minimalnya seperti di slide sebelumnya, kita dapat mengelompokan data sesuai dengan cluster-nya. Hasil sbb: Provinsi C1 C2 C3 Aceh √ Sumatera Utara √ Sumatera Barat √ Riau √ Jambi √ Sumatera Selatan √ Bengkulu √ Lampung √ Kep Bangka Belitung √ Kep Riau √ Tidak ada perpindahan . Hasil cluster diperoleh.

21. Program Python Import Library Load Dataset

22. Program Python Eksplorasi Data Analysis

23. Program Python Eksplorasi Data Analysis Tidak ada missing value

24. Program Python Enkode variabel kategori

25. Program Python Pre-Processing data

26. Program Python Menentukan jumlah cluster

27. Program Python K-Means Clustering

28. Program Python Evaluasi Model

29. Latihan Terapkan teknik clustering menggunakan algoritma k-means terhadap data latih di bawah ini baik secara Perhitungan manual : Jumlah kelompok (K) = 2 No Atribut 1 Atribut 2 1 1 3 2 4 2 3 5 7 4 8 6 5 9 11 6 12 10

30. TERIMA KASIH