kNN Classification



kNN dapat digunakan untuk proses klasifikasi. Prinsipnya kita mau tahu apa klasifikasi data di posisi tertentu. Kemudian kita mencari sebanyak k data terdekat. Kemudian sifat-sifat data di posisi yang kita tunjuk adalah klasifikasi dengan jumlah data yang paling banyak.

STEP-BY-STEP kNN:

  1. Plot seluruh sampel data
  2. Temukan k=3 sampel data terdekat. Klasifikasi dengan jumlah sampel terbanyak adalah klasifikasi yang dihasilkan. Catat hasil klasifikasi ini.
  3. Ulangi langkah kedua menggunakan bilangan ganjil k=5, 7, 9 ... sampai tidak ada lagi perbedaan jenis klasifikasi yang dhasilkan.

    CONTOH SOAL:  

    Sebuah SMA memiliki kebijakan untuk membagi jurusan IPA dan IPS berdasarkan nilai ujian matematika dan bahasa Inggrisnya.
    • Bila nilai matematikanya lebih tinggi dari bahasa Inggris, maka siswa tsb masuk ke jurusan IPA. 
    • Sebaliknya bila nilai bahasa Inggrisnya lebih tinggi dari nilai matematikanya, maka siswa tsb masuk ke jurusan  IPS.


    PERTANYAAN: Kalau seorang siswa dengan nilai matematika 4 dan bahasa Inggris juga 4, sebaiknya masuk ke jurusan apa?

    STEP-1: Menggambarkan Plot. 
    • Plot terdiri dari 2 sumbu. 
    • Sumbu horisontal (mendatar) menggambarkan nilai bahasa Inggris dan sumbu vertikal (tegak) menggambarkan nilai matematika.


    STEP-2: Plot Data Pertama 
    • Pertama-tama kita mendapatkan A seorang siswa IPA. Nilai matematikanya 8 tetapi nilai bahasa Inggrisnya cuma 4. A kita letakkan pada posisi (4,8) seperti terlihat pada gambar. 
    • Yang IPA kta beri warna Biru dan IPS kita beri warna Merah. A kita beri warna biru.

    STEP-3: Plot Data Kedua. 
    • Setelah itu, kita mendapatkan B seorang siswa IPS. Nilai matematikanya 7 dan nilai bahasa Inggrisnya 9. B kita letakkan pada posisi (9,7) seperti terlihat pada gambar. 
    • B kita beri warna merah karena IPS.

    STEP-4: Plot Data Seluruhnya. 
    • Seluruhnya, kita dapatkan 5 siswa IPA dan 5 siswa IPS
    • Kemudian kita plot data yang masih belum kita plot mulai dari C, D,  sampai J seperti pada gambar.

    STEP-5: Plot Data P 
    • Kemudian kita plot data yang ditanyakan yaitu P dengan nilai matematika dan bahasa Inggris sama-sama 4.
    • Kita Plot P di posisi (4,4) seperti terlihat pada gambar.

    STEP-6: k=3.
    • Biasanya nilai k bilangan ganjil
    • Sebaiknya k tidak sama dengan 1 karena kurang informasinya. 
    • Bilangan ganjil bukan 1, kita gunakan k=3.
    • Karena k=3, kita harus mencari 3 tetangga terdekat dengan P. Kita temukan titik F, D, dan H.
    • Karena ada 2 data berwarna biru dan hanya 1 merah, maka untuk k=3, P akan ikut warna biru atau klasifikasi IPA.

    STEP-7: k=5.
    • Selanjutnya, kita  ganti k=5. 
    • Sehingga kita harus mencari 5 tetangga terdekat dengan P. Kita temukan titik F, D, A, H, dan J.
    • Karena 3 data berwarna biru dan hanya 2 merah, maka untuk k=5, P akan ikut warna biru atau klasifikasi IPA.
    • Karena sudah tidak terjadi perubahan klasifikasi, maka kita putuskan untuk tidak menambah nilai k lagi.

    KESIMPULAN

    •  Siswa P sebaiknya masuk jurusan IPA.

    Simple Additive Weighting (SAW)



    Untuk membuat keputusan menggunakan algoritma SAW dibutuhkan beberapa hal sbb:

    1. Opsi: Pilihan yang akan diputuskan pemenangnya
    2. Kriteria: aturan-aturan untuk pemilihan pemenang
    Kriteria dalam SAW terbagi menjadi dua, yaitu:
    • Kriteria Positif yaitu kriteria yang mendukung pencapaian target.Semakin besar nilainya, semakin besar dukungannya pada keputusan.
      Contoh: IPK (Indeks Prestasi Komulatif), semakin tinggi, semakin pintar, maka semakin mudah pencapaian target.
    • Kriteria Negatif yaitu kriteria yang menghambat pencapaian target. Semakin besar nilainya, semakin besar hambatannya pada pencapaian target.
      Contoh lokasi rumah, semakin besar (jauh) lokasi rumah, maka semakin sulit untuk bisa datang dalam meeting, sehingga mempersulit proses membuat keputusan. Biaya, semakinbesar biaya semakin sulit target tercapai.  

    Contoh Soal

    • Jono ingin memilih seorang temannya sebagai anggota kelompok dalam mata kuliah Decision Support System. Targetnya adalah menyelesaikan tugas kelompok tepat waktu dengan nilai A. 

    STEP BY STEP SOLUSI DENGAN METODE SAW:


    STEP-1: Membuat opsi/pilihan/kandidat
    • Jono mengamati teman-teman kuliahnya. Ada 3 option yang ia pertimbangkan yang semuanya adalah teman dekatnya, yaitu: Anno, Kevin, dan Henri.
    STEP-2: Membuat Kriteria Positif dan negatif
    • Kriteria Positif
      • IPK semakin besar IPK ,semakin pintar temannya tsb
      • Rajin semakin rajin semakin membantu selesainya tugas kelompok.
    • Kriteria negatif
      • Usia semakin tua semakin susah untuk berkomunikasi
      • Lokasi Rumah, semakin jauh rumahnya, semakin sulit bisa bertemu

    STEP-3: Melakukan pembobotan atas kriteria

    • IPK: 40%
    • Rajin 30%
    • Usia 15%
    • Lokasi Rumah 15%
    Total nilai pembobotan harus 100% atau 1.

    STEP-4: Membuat tabel SAW awal

    • Lengkapi judul kolom-kolom dengan kriteria positif dan negatif.
    • Kemudian isi kolom opsi


    STEP-5: Mengisi tabel SAW kolom IPK. 
    Kolom IPK diisi dengan nilai IPK opsi.

    STEP-6: Mengisi tabel SAW kolom RAJIN.
    Kolom RAJIN diisi dengan nilai bobot sbb:

    • Nilai 3 bila sangat Rajin
    • Nilai 2 bila cukup Rajin
    • Nilai 1 bila kurang Rajin

    STEP-7: Mengisi tabel SAW kolom USIA. 
    Kolom USIA diisi dengan nilai bobot sbb:

    • Nilai 3 bila lebih tua
    • Nilai 2 bila sama usianya
    • Nilai 1 bila lebih muda


    STEP-8: Mengisi tabel SAW kolom LOKASI RUMAH.
    Kolom LOKASI RUMAH diisi dengan nilai bobot sbb:

    • Nilai 3 bila jauh sekali
    • Nilai 2 bila jauh
    • Nilai 1 bila dekat

    STEP-9: Pemilihan nilai MAXIMUM dan MINIMUM.
    • Untuk kolom kriteria positif, dipilih nilai MAX
    • Untuk kolom kriteria negatif dipilih nilai MINIMUM

    STEP-10: Normalisasi kolom IPK.
    karena kolom IPK adalah kolom kriteria positif, maka normalisasi kolom ini dilakukan dengan cara mengganti setiap nilai dengan nilai sel dibagi dengan nilai MAX pada kolom.
    • Nilai MAX pada kolom IPK = 3.1
    • IPK ANNO= 3.0/3.1=0.97
    • IPK KEVIN= 2.9/3.1=0.94
    • IPK HENRI= 3.1/3.1=1

    STEP-11: Normalisasi kolom RAJIN.
    karena kolom RAJIN adalah kolom kriteria positif, maka normalisasi kolom ini dilakukan dengan cara mengganti setiap nilai dengan nilai sel dibagi dengan nilai MAX pada kolom.
    • Nilai MAX pada kolom RAJIN = 3
    • ANNO= 1/3=0.33
    • KEVIN= 3/3=1
    • HENRI= 2/3=0.67

    STEP-11: Normalisasi kolom USIA.
    karena kolom USIA adalah kolom kriteria negatif, maka normalisasi kolom ini dilakukan dengan cara mengganti setiap nilai dengan nilai MINIMUM dibagi dengan nilai sel pada kolom.
    • Nilai MINIMUM pada kolom USIA = 1
    • ANNO= 1/3=0.33
    • KEVIN= 1/1=1
    • HENRI= 1/2=0.5
    STEP-12: Normalisasi kolom LOKASI RUMAH.
    karena kolom LOKASI RUMAH adalah kolom kriteria negatif, maka normalisasi kolom ini dilakukan dengan cara mengganti setiap nilai dengan nilai MINIMUM dibagi dengan nilai sel pada kolom.
    • Nilai MINIMUM pada kolom LOKASI RUMAH = 2
    • ANNO= 2/2=1
    • KEVIN= 2/2=1
    • HENRI= 2/3=0.67
    STEP-13: Menghitung Skor
    Perhitungan skor dilakukan dengan menjumlahkan setiap nilai sel dengan nilai bobot kolomnya untuk asing-masing opsi.

    • Skor ANNO=0.97x40%+0.33x30%+0.33x15%+1.00x15%=0.69
    • Skor KEVIN=0.94x40%+1.00x30%+1.00x15%+1.00x15%=0.98
    • Skor HENRI=1.00x40%+0.67x30%+0.50x15%+0.67x15%=0.78
    STEP 14: Membuat Keputusan
    Buat daftar pemenang dengan mengrutkan skor dari tertinggi ke terendah.
    • Teman yang direkomendasikan untuk menjadi anggota kelompok Jono adalah 
      1. Kevin skor 0.98
      2. Henri skor 0.78
      3. Anno skor 0.69



    Time Series Basic Patterns



    Time Series merupakan suatu jenis analisis tentang nilai suatu objek terhadap perubahan waktu. Contohnya nilai mata uang, harga barang, jumlah barang, dll. Perubahan waktu harus dinyatakan dalam interval waktu yang sama, misalkan dalam:
    • mingguan: W1, W2, W3, ... 
    • harian: Senin, Selasa, Rabu, Kamis, Jumat, Sabtu, Minggu atau bisa juga D1, D2, D3, ... 
    • tahunan: 2001, 2002, 2003, ... 
    • dalam 2 harian: D2, D4, D6, D8, ...
    • dalam periode 4 jam: H4, H8, H12, ...
    • dll yang penting sama interval waktunya.
    Dalam analisis timeseries kita mencoba membaca pattern yang terjadi dan kegunaannya adalah kita membuat prediksi di masa depan.

    gambar 1

    • Gambar 1 menunjukkan hasil penjualan es krim di tahun 2010-2012, dimana terjadi pattern hasil penjualan yang berulang-ulang setiap tahunnya. Di Q4 setiap tahunnya naik sampai mencapai puncak dan kemudian turun sampai nol di Q1, kemudian, naik lagi di Q2dan turun di Q3. 
    • Kita bisa berharap pola yang sama akan terjadi lagi di tahun 2013 yaitu penjualan es krim akan mencapai puncaknya pada Q4 tahun 2013.
    Selanjutnya kita akan bahas macam-macam pattern dalam analisis timeseries.

    Variation (Variasi)

    • Sebuah variasi  terjadi bila  terjadi pola High (titik tertinggi) dan Low (titik terrendah) secara bergantian.
    • Pada gambar 2, kita temukan H dan L muncul bergantian
    • Variasi  terjadi bisa kapan saja tidak peduli berapapun interval waktunya.
    gambar 2

    Trend

    • Trend ada tiga yaitu trend naik (uptrend), trend turun (downtrend), dan tidak ada trend (sideways)
    • Trend dikatakan UPTREND kalau H berikutnya cenderung lebih tinggi dari H sebelumnya dan L berikutnya juga cenderung lebih tinggi dari L sebelumnya. Contoh gambar 3.

    gambar 3


    • Trend dikatakan DOWNTREND kalau H berikutnya cenderung lebih rendah dari H sebelumnya dan L berikutnya juga cenderung lebih rendah dari L sebelumnya. Contohnya gambar 4.
    gambar 4


    • SIDEWAYS atau tidak ada trend terjadi kalau kedua kondisi trend di atas tidak ditemukan. Tidak uptrend, tidak downtrend juga. Contoh gambar 5.
    gambar 5


    Seasonal (Musiman)

    • Suatu keadaan disebut SEASONAL bila kita dapat menemukan pola H dan L salah satu atau kedua-duanya muncul secara konsisten pada periode waktu tertentu.
    • Seasonal selalu/sering terjadi dan terberulang-ulang pada periode waktu tertentu. 
    • Contoh gambar 6, musim rambutan terjadi di Q4 sehingga penjualan rambutan mecapai puncaknya di akhir tahun.
    gambar 6

    Cyclic (Siklus)
    • Sama seperti seasonal, CYCLIC juga selalu terjadi namun periode waktunya tidak menentu. Contoh gambar 7, puncak peningkatan penjualan marmer tidak menentu bergantung pada aktifitas impor dan produsen lokal.
    • Cyclic memiliki 4 fase yaitu"
      • Peak (prosperity) mencapai titik puncak
      • Contraction/resesi: penurunan
      • trough (depression) :mencapai titik terrendah
      • expansion/recovery/growth: perkembangan
    gambar 7

    Irregular (Random)

    • Yaitu keadaan dimana tidak bisa ditemukan pola apapun dalam satu periode waktu tertentu.
    • Biasanya terjadi setelah musiman selesai, ataupun mengalami bencana alam sehingga pola/trend menjadi rusak.

    Belajar Hierarchy Clustering Menggunakan R


    Contoh Soal: 

    Buatlah satu analisis cluster hierarchy menggunakan data sampel wanita di AS (women dataset di R).
    Packages: factoextra
    Library:factoextra 
    Data:Women dataset in R


    STEP-1: Exploratory Data Analysis

    head(women, nrow = 6) # Show 6 rows pertama data wanita di US
    
    
    
    Perhatikan ada dua kolom yaitu kolom height (tinggi badan) dan kolom weight (berat badan). Apakah data bisa langsung dibandingkan? Tidak bisa, karena berbeda satuan, tinggi badan dalam inch dan berat badan dalam lbs.

    Supaya bisa dibandingkan, kita membuat skala dalam R digunakan fungsi scale() gunanya untuk mendapatkan jarak yang seimbang antara dua dimensi atau lebih dengan beda satuan.

    df <- scale(women) # skala data
    head(df, nrow = 6) # Show 6 rows pertama hasil skala
    
    

    STEP-2: Menghitung Jarak Eucledian


    Sekarang kita menghitung jarak eucledian dari df. Disini kita gunakan fungsi dari R dist atau distance (jarak) formatnya dist(namavariable,method) hasilnya disimpan dalam variabel women.dist. Run:

    women.dist <- dist(df, method = "euclidean")  # menghitung jarak
    as.matrix(women.dist)[1:5, 1:5] # menampilkan matrix
    
    

    Berapa jarak wanita kedua dan ketiga? Jawab: 0.2957487
    Apakah jarak wanita kedua dan ketiga dengan jarak wanita ketiga dan kedua sama? Jawab Ya mengapa? Karena jarak pada dua objek yang sama.
    Berapa jarak wanita keempat dan keempat? Jawab NOL mengapa? Jarak pada dirinya sendiri=NOL.

    STEP-3: Membuat Hierarchy Cluster (HC)

    Sekarang kita membuat hierarchy cluster. Fungsi yang digunakan adalah hc.lust(d,method) dimana d adalah struktur hasil proses fungsi dist() dan ada beberapa macam pilihan method jarak antar cluster di R:
    • single linkage: "single" 
    • complete linkage: "complete"
    • average linkage: "average"
    • centroid linkage: "centroid"
    • ward D2  "ward.D2" 
    • mcquitty: "mcquitty"
    • median: "median" (= WPGMC)
    Contohnya kita pergunakan ward D2:
    women.hc <- hclust(d = women.dist, method = "ward.D2")

    STEP -4: Visualisasi Dendrodram

    Dendrodram merupakan visualisasi hasil hierarchy clustering dalam bentuk hirarki menggunakan library factoextra dan fungsi fviz_dend(hasilcluster,cex) Run program ini:

    library("factoextra") #gunakan library factoextra
    
    fviz_dend(women.hc, cex = 0.5) #membuat dendodram

    Bila kita membagi data women menjadi 2 cluster, maka
    - Cluster pertama={11,12,13,14,15}
    - Cluster kedua ={1,2,3,…10}

    Bila kita membagi data women menjadi 3 cluster, maka
    - Cluster pertama={11,12,13,14,15}
    - Cluster kedua ={1,2,3,4,5}
    - Cluster ketiga ={6,7,8,9,10}

    gambar 1 dendodram


    Praktekkan metode single linkage, complete linkage, average linkage, dan juga centroid untuk membuat 3 cluster dan kemudian kita dapatkan hasil berikut ini:
    • Dari Metode Ward.D2, complete, average, dan centroid: K1={11,12,13,14,15}, K2={1,2,3,4,5}, K3={6,7,8,9,10}
    • Single linkage K1={14}, K2={15}, K3={1,2,3,…13}

    Kesimpulan

    • Single linkage tidak bisa dipergunakan dalam membuat cluster untuk dataset women. Sedangkan yang lain menghasilkan cluster yang sama. 3 cluster yang benar adalah K1={11,12,13,14,15},K2={1,2,3,4,5},K3={6,7,8,9,10}