[Tugas] Data Mining ~ K-Nearest Neighbour

       Posting tentang tugas perkuliahan semoga membantu para pencari tugas-tugas. Tugas ini diposting dalam sebuah forum dan hanya mahasiswa dan dosen saja yang bisa mempostingkan isi dari thread tersebut. 

1.  Analogi pembelajaran nearest neighbor classifier?

2.  n-dimensional space pada k-nearest neighbor?

3.  fungsi variabel k pada k-nearest neighbor?

4.  pengaruh memilih nilai variabel k pada k-nearest neighbor jika terlalu kecil?

5.  pengaruh memilih nilai variabel k pada k-nearest neighbor jika terlalu besar?

6.  closeness pada k-nearest neighbor?

7.  penanganan atribut dengan range data yang lebar pada k-nearest neighbor?

8.  penanganan atribut kategorikal pada k-nearest neighbor?

9.  penanganan "missing value" pada k-nearest neighbor?

10. penentuan nilai variabel k yang terbaik pada k-nearest neighbor?

11. kelemahan pada nearest neighbor classifier karena menggunakan perbandingan jarak?

12. pembobotan pada nearest neighbor classifier?

13. Holdout method?

14. Random subsampling?

15. k-fold cross validation?

16. Bootstraping?

17. Confusion matrix?

18. sensitivity?

19. specificity?

20. precision?

21. recall?

22. accuracy kombinasi dari sensitivity dan specificity?

23. Ensemble method?

24. Bagging?

25. Boosting?

Jawab

1. Analogi pembelajaran nearest neighbor classifier?

a)    Konsep dasar dari K-NN adalah mencari jarak terdekat antara data yang akan dievaluasi dengan K tetangga terdekatnya dalam data pelatihan. 

b)    Penghitungan jarak dilakukan dengan konsep Euclidean. 

c)    Jumlah kelas yang paling banyak dengan jarak terdekat tersebut akan menjadi kelas dimana data evaluasi tersebut berada. 

2  

Sejauh yang saya ketahui, pada umumnya tujuan dari K-Nearest Classification sendiri yakni untuk mengklasifikasikan sebuah obyek baru berdasarkan atribut maupun contoh training.

Kaitan nya antara N-dimensional dengan atribut atau contoh training tersebut yakni, contoh training tersebut diproyeksikan ke "ruang" berdimensi banyak, dimana masing-masing dari dimensi tersebut merepresentasikan fitur/attribut dari sebuah data.

3. Fungsi variabel k pada k-nearest neighbor?

Dalam pengenalan pola, k-neighbor nearest (k-NN) adalah metode untuk mengklasifikasikan objek berdasarkan contohpelatihan terdekat di ruang fitur. k-NN adalah jenis contoh pembelajaran berbasis, atau lazy learning di mana fungsi ini hanyadidekati secara lokal dan perhitungan semua ditangguhkan sampai klasifikasi. 

4  Pengaruh nilai K yang terlalu kecil adalah dapat menghasilkan akurasi yang rendah. Hal ini disebabkan dengan kecilnya nilai K, maka klasifikasi akan lebih terpengaruh oleh noise. 

5  Pengaruh nilai K yang terlalu besar adalah dapat menghasilkan akurasi yang besar. Hal ini disebabkan dengan besarnya nilai K, maka klasifikasi akan lebih terpengaruh oleh noise. 

no.6 :

closeness pada k-nearest neighbor ialah :

Closeness: dinyatakan dengan Euclidean Distance, dimana Euclidean Distance antara 2 titik, 

contohnya : X = (x1, x2, ….., xn) dan Y = (y1,y2,….,yn) adalah d(X,Y)

8. 

Untuk atribut kategorikal, metode sederhana adalah dengan membandingkan nilai dari atribut di tuple X1 dengan yang di tuple X2. Jika keduanya adalah identik (misalnya, tuples X1 dan X2 keduanya memiliki warna biru), maka perbedaan antara keduanya dianggap sebagai 0.

Jika keduanya berbeda (misalnya, tuple X1 adalah biru tetapi tuple X2 adalah merah), maka selisih tersebut dianggap 1. Metode lain dapat menggabungkan skema yang lebih canggih untuk grading diferensial (misalnya, di mana skor perbedaan yang lebih besar diberikan, katakanlah, untuk biru dan putih daripada biru dan hitam).

9.  penanganan "missing value" pada k-nearest neighbor?

Data mining adalah salah satu cabang keilmuan yang banyak dipakai dalam menggali informasi dari suatu data yang disajikan. Salah satu permasalahan yang sering muncul dalam penggalian informasi itu adalah adanya missing value pada data. Hal ini dapat membuat tingkat keakuratan dari informasi yang didapat menjadi berkurang. Ada beberapa cara untuk mengatasi hal ini. Salah satunya adalah dengan melakukan pengisian terhadap missing value tersebut. Cara ini disebut proses imputasi.

10.

Nilai k yang terbaik untuk algoritma ini tergantung pada data. Secara umum, nilai k yang tinggi akan mengurangi efek noise pada klasifikasi, tetapi membuat batasan antara setiap klasifikasi menjadi semakin kabur. Nilai k yang bagus dapat dipilih dengan optimasi parameter, misalnya dengan menggunakan cross-validation. Kasus khusus dimana klasifikasi diprediksikan berdasarkan training data yang paling dekat (dengan kata lain, k = 1) disebut algoritma nearest neighbor.

11

Hal ini dikarenakan k-nearest neighbour classifier mengukur jarak spektral setiap pixel ke semua pixel yang ada dalam daerah sampel. Waktu proses klasifikasi akan semakin lama seiring semakin banyaknya jumlah saluran, bertambah besarnya ukuran daerah sampel dan bertambahnya jumlah kelas yang akan diklasikasikan.

cth: Pengujian k-nearest neighbour classier untuk kedua algoritma pengukur jarak spektral di-lakukan pada beberapa variasi dimensi citra. Dimensi citra yang ditentukan adalah 500x500 pixel, 1.000x1.000 pixel, dan 2.000x2.000 pixel (dengan jumlah saluran tetap sama). Jumlah kelas tutupan lahan (landcover) yang diklasikasikan juga dibuat bervariasi, yaitu 5 kelas, 10 kelas dan 15 kelas tutupan lahan. Pembuatan daerah sampel (training area) untuk klasifikasi dan untuk uji akurasi hasil klasifikasi dilakukan berdasarkan data hasil survey lapangan (ground check). Uji akurasi hasil klasikasi dilakukan menggunakan metode Confusion Matrix, dan uji esiensi (lamanya waktu proses klasikasi) dinyatakan dalam satuan detik.

13. Holdout Method

Dalam metode ini data dibagi menjadi dua kelompok data independen, yaitu data pelatihan dan data pengujian, secara acak. Secara khusus dua pertiga dari data dialokasikan dalam kelompok data pelatihan, dan sepertiga sisanya ke dalam kelompok data pengujian. Data pelatihan digunakan untuk memperoleh model, dan akurasinya diestimasi menggunakan data pengujian. Estimasinya bersifat pesimis karena hanya sebagian dari data awal yang digunakan untuk memperoleh model.

14. Random Subsampling

Adalah variasi dari metode Holdout. Metode ini adalah metode Holdout yang diulang sebanyak k kali Estimasi akurasi keseluruhan diambil dari rata-rata pada akurasi yang sering terjadi setiap iterasi. Contohnya adalah, mengambil rata-rata dari tingkat kesalahan prediksi.

15.

K-Fold cross validation adalah salah satu cara untuk meningkatkan atas metode ketidaksepakatan. Kumpulan data dibagi menjadi subset k, dan metode holdout diulang sebanyak k kali. Setiap kali, salah satu himpunan bagian k digunakan sebagai test set dan k-1 subset lainnya diletakkan bersama-sama untuk membentuk satu set pelatihan. Kemudian kesalahan rata-rata di semua percobaan k dihitung. 

Keuntungan dari metode ini adalah kurang pentingnya bagaimana data akan dibagi. Setiap titik data akan berada dalam tes set tepat satu kali, dan akan berada dalam pelatihan set k-1 kali. Varians dari estimasi yang dihasilkan berkurang karena k meningkat. 

Kerugian dari metode ini adalah bahwa algoritma pelatihan harus diulang kembali dari awal k kali, yang berarti dibutuhkan waktu k sebagai perhitungan banyak untuk membuat evaluasi. 

Sebuah varian dari metode ini adalah untuk secara acak membagi data ke dalam tes dan training set k waktu yang berbeda. 

16. Bootstrapping

bootstrapping adalah suatu metode untuk menderivasikan estimasi yang kuat dari error standar dan interval kepercayaan untuk mengestimasi proporsi, rerata, median, odds ratio, koefisien korelasi atau koefisien regresi. bootstrapping juga dapat digunakan untuk mengembangkan uji hipotesis. bootstrapping sangat berguna sebagai alternatif untuk estimasi parameter ketika peneliti merasa ragu dapat memenuhi asumsu pada data mereka.

17. Confusion Matrix adalah sebuah tabel yang terdiri atas banyaknya baris data uji yang diprediksi benar dan tidak benar oleh model klasifikasi, tabel ini diperlukan untuk menentukan kinerja suatu model klasifikasi.

18. sensitivity

suatu teknik menganalisa resiko dengan tujuan untuk memperoleh informasi dengan hasil yang optimal dengan merubah rubah variabel yang paling sensitive dalam kondisi yang tidak pasti

atau bisa juga analisis yang menggunakan simulasi dengan menunjukan perubahan 1 variabel yang paling sensitive maka kinerja akan berubah sekian persen pada bagian lainnya

19. Specificity adalah ukuran tingkatan derajat classifier dapat mengenal negatives samples ("no") berdasarkan true negatives yang dapat diprediksi secara benar jika yang diberikan adalah sample negatives.

20. Precision 

adalah perbandingan jumlah dokumen relevan yang didapatkan sistem dengan jumlah seluruh dokumen yang terambil oleh sistem baik relevan maupun tidak relevan.

Precision = (relevan dokument) n (retrieved document)

                                   retrieved document

21. Recall

Dalam data mining,recall adalah permasalahan klasifikasi perhitungan kinerja,pengambilan data yang berhasil dilakukan terhadap bagian data yang relevan dengan query.Dalam klasifikasi binari, recall disebut juga dengan sensitivity. Peluang munculnya data relevan yang diambil sesuai dengan query dapat dilihat dengan recall, sebagian kecil dari dokumen yang relevan dengan query yang berhasil diambil.

Rumus: (D/C+D)x100%

22.

Sensitivitas dan spesifisitas adalah ukuran statistik kinerja tes klasifikasi biner, juga dikenal dalam statistik sebagai fungsi klasifikasi. Sensitivitas (juga disebut tingkat recall di beberapa bidang) mengukur proporsi positif aktual yang benar diidentifikasi seperti itu (misalnya persentase orang sakit yang benar diidentifikasi memiliki kondisi). Spesifisitas mengukur proporsi negatif yang diidentifikasi dengan benar (misalnya persentase orang sehat yang benar diidentifikasi sebagai tidak memiliki kondisi).

No 23. Ensamble Method

Ensamble method yaitu membangun model prediksi yang terdiri dari atas banyak classifier dan melakukan proses dengan melakukan voting hasil prediksi dari calssifiernya. Ensamble method memiliki beberapa syarat yaitu para classifier harus independen satu dengan yang lainnya dan performa classifier penyusunnya harus lebih baik dari tebakan random.

24. Bagging

Bagging merupakan metode yang dapat memperbaiki hasil dari algoritma klasifikasi machine learning. Metode ini diformulasikan oleh Leo Breinman tahun 1996 dan nama tersebut disimpulkan dari phrase ”Bootstrap Aggregating”. Dengan penerapan metode ini maka hasil klasifikasi ataupun prediksi terhadap data akan semakin akurat.

25.

Boosting merupakan meta-algoritma dalam machine learning untuk melakukan supervised learning. Teoriboosting dikenalkan berdasarkan pertanyaan yang diajukan Kearns pada tahun 1988 : Dapatkah sekumpulan weak learner menciptakan satau kesatuan strong learner? Weak learner adalah classifier yang hanya memiliki sedikit korelasi dengan klasifikasi yang sebenarnya, sementara strong learner adalah classifier yang memiliki korelasi dengan klasifikasi yang sebenarnya.

Kebanyakan algoritma boosting mengikuti sebuah rancangan. Secara umum boosting terjadi dalam iterasi, secaraincremental menambahkan weak learner ke dalam satu strong learner. Pada setiap iterasi, satu weak learnerbelajar dari suatu data latihan. Kemudian, weak learner itu ditambhakan kedalam strong learner. Setelah weak learner ditambahkan, data-data kemudian diubah masing-masing bobotnya. Data-data mengalami kesalahaan klasifikasi akan mengalami penambahan bobot, dan data-data yang klasifikasi dengan benar akan mengalami pengurangan bobot. Oleh karena itu, weak learner pada iterasi selanjutnya akan lebih terfokus pada data-data yang mengalami kesalahan klasifikasi oleh weak learner yang sebelumnya.

AdaBoost merupakan variasi yang paling terkenal dari algoritma boosting dan merupakan algoritma pertama yang beradaptasi dengan weak learner. Contoh algoritma boosting lainnya : LPBoost, TotalBoost, BrownBoost, MadaBoost, LogitBoost.