Metode-metode dalam Data Mining - Seri Data Mining for Business Intelligence (6)

Metode-metode dalam DM

Ada banyak metode untuk melakukan kajian DM, antara lain ‘classification’ (klasifikasi), ‘regression’ (regresi), ‘clustering’, dan ‘association’ (asosiasi). Kebanyakan tool software DM menerapkan lebih dari satu teknik (atau algoritma) untuk setiap metode-metode tersebut. Bagian seri ini akan menyajikan metode-metode DM yang paling popular dan menjelaskan teknik-teknik penyajiannya.

Classification (klasifikasi)

Classification barangkali adalah metode dalam DM yang paling sering digunakan untuk menyelesaikan problem-problem di dunia nyata. Sebagai salah satu yang terpopuler dalam keluarga yang menggunakan teknik ‘machine-learning’, classification mempelajari pola-pola dari data historis (sekumpulan informasi –seperti ciri-ciri, variabel-variabel, fitur-fitur – pada berbagai karakteristik item-item yang sudah diberi label sebelumnya) dengan tujuan untuk menempatkan instans (object-object) baru (dengan label yang tak diketahui sebelumnya) ke dalam kelompok atau kelas masing-masing. Contohnya, kita bisa menggunakan classification untuk meramalkan apakah cuaca pada hari tertentu akan ‘cerah’ (sunny), ‘hujan’ (rainy) atau ‘berawan’ (cloudy). Beberapa jenis pekerjaan popular dalam menggunakan classification adalah ‘persetujuan kredit’ (misalnya risiko kredit ‘baik’ atau ‘buruk’), lokasi toko (misalnya, ‘baik’, ‘moderate’,’buruk’), target marketing (misalnya, ‘kemungkinan menjadi langganan’, ‘tidak ada harapan sama sekali’), deteksi fraud (misalnya, ‘ya’, ‘tidak’), dan telekomunikasi (misalnya, kemungkinan pindah ke perusahaan telpon yang lain, ‘yes/no’). Bila yang sedang diprediksikan adalah label kelas (misalnya, ‘cerah’, ‘hujan’, atau ‘berawan’) problem prediksi tersebut disebut dengan ‘classification’, sedangkan bila yang diprediksi adalah nilainya yang numerik (misalnya temperature seperti 68 F),  problem prediksi tersebut disebut dengan ‘regression’ (regresi). [Baca: Contoh Soal Klasifikasi Dalam Data Mining - Decision Tree - Rules Based - Naive Bayesia]


Meskipun ‘clustering’ (metode popular yang lain dalam DM) bisa juga digunakan untuk menentukan group-group (atau keanggotaan kelas) dari sesuatu, namun ada perbedaan penting diantara keduanya. Classification mempelajari fungsi antara karakteristik sesuatu  (misalnya variabel independent) dan keanggotannya (misalnya variabel output) melalui suatu proses pembelajaran ‘terawasi’ (supervised learning process) dimana kedua jenis variabel (input dan output) disajikan ke algoritma; sementara di dalam clustering, keanggotaan object dipelajari melalui suatu proses pembelajaran ‘tak-terawasi’ (unsupervised learning process) dimana hanya variabel input yang disajikan ke algoritma.  Tidak seperti dalam classification, clustering tidak memiliki mekanisme untuk ‘pengawasan’ (atau pengendalian) yang memaksakan proses pembelajaran; justru, algoritma dalam clustering menggunakan satu atau lebih heuristics (misalnya mengukur jarak multidimensi) untuk menemukan kelompok-kelompok object. [Baca juga: Pengertian Clustering atau Analisa Cluster]

Methodologi dua-langkah yang paling umum dari prediksi jenis classification adalah ‘model development/training’ dan ‘model testing/deployment’. Pada fase ‘model development’ sekumpulan data input, termasuk berbagai label kelas yang aktual, digunakan. Setelah suatu model ‘dilatih’, model tersebut di-tes terhadap sampel data yang tersisa untuk penilaian akurasi dan pada akhirnya diimplementasikan untuk penggunaan riil yang digunakan untuk memprediksi kelas-kelas dari instans data baru (dimana label kelas tdak diketahui). Beberapa faktor yang digunakan untuk menilai model adalah sebagai berikut:
  • Predictive accuracy (akurasi prediksi). Kemampuan model dalam memprediksi secara akurat terhadap label kelas dari data yang baru atau yang tak pernah terlihat sebelumnya. Akurasi prodiksi adalah faktor penilaian yang paling umum digunakan untuk model-model dalam classification. Untuk menghitung ukuran ini, label-label kelas riil dari dataset yang diuji dicocokkan dengan label-label kelas yang diprediksi oleh model. Akurasi kemudian bisa dihitung sebagai ‘angka akurasi’ (accuracy rate), yang merupakan persentase dari sampel-sampel dataset yang diuji yang dengan tepat di-klasifikasi-kan oleh model tersebut (lebih jauh mengenai topik ini diberikan nanti di seri ini).
  • Speed (kecepatan). Biaya komputasi yang digunakan untuk menghasilkan dan memanfaatkan model, yang berarti lebih cepat lebih baik.
  • Robustness (kehandalan). Kemampuan model untuk membuat prediksi yang cukup akurat, meskipun dengan data yang ‘noisy’ atau data yang nilainya hilang atau salah.
  • Scalability (skalabilitas). Kemampuan untuk membuat model prediksi secara efisien dengan pertimbangan jumlah data yang agak besar.
  • Interpretability (interpretabilitas). Tingkat pemahaman dan ‘insight’ yang diberikan oleh model (misalnya, bagaimana dan/atau apakah model membuat kesimpulan mengenai prediksi tertentu).
Menaksir/mengukur akurasi ‘yang sebenarnya’  dari berbagai model pada classification

Dalam berbagai problem classification, yang dijadikan sebagai sumber utama untuk menaksir akurasi adalah ‘confusion matrix’ (disebut juga ‘classification matrix’ atau ‘contigency table’). Gambar dibawah ini adalah ‘confusion matrix’ pada classification dengan dua-kelas. [Baca juga: Contoh problem dan jawaban tentang decision tree dan confusion matrix]

Angka-angka pada diagonal dari kiri atas ke kanan bawah adalah hasil prediksi yang benar, dan angka-angka diluar diagonal ini adalah hasil prediksi yang salah. 
Gambar table di bawah berikut menunjukkan persamaan-persamaan untuk akurasi pada model-model classification.
Ketika problem klasifikasi bukanlah problem biner, ‘confusion matrix’ seperti di atas akan menjadi lebih besar (satu matrix segiempat dengan ukuran sejumlah unique dari label kelas), dan akurasi menjadi terbatas pada jumlah akurasi per kelas dan akurasi ‘classifier’ secara keseluruhan.
Mengukur akurasi model classification (atau classifier) yang dihasilkan oleh algoritma pembelajaran terawasi (supervised learning algorithm) adalah hal yang penting karena dua alasan berikut: pertama, karena bisa digunakan untuk menilai akurasi prediksi di masa mendatang, yang bisa secara tidak langsung mengatakan tingkat konfidensi yang harus kita miliki dalam output classifier pada sistem prediksi. Kedua, bisa digunakan untuk memilih suatu ‘classifier’ dari sekumpulan yang sudah diberikan (mengidentifikasi model klasifikasi ‘yang terbaik’ diantara banyak model yang sudah dilatih).  Berikut ini adalah methodology-methodologi yang paling popular untuk penaksiran yang diterapkan pada model-model DM jenis klasifikasi.

SIMPLE SPLIT. ‘simple split’ (atau pengukuran pada sampel test atau ‘holdout’) membagi data menjadi dua subset data yang saling eklusif satu sama lain yang disebut dengan ‘training set’ (data yang digunakan untuk pelatihan) dan ‘test set’ atau ‘holdout set’ (data yang digunakan untuk menguji kecocokan). Biasanya yang umum dilakukan adalah memilih ‘dua-per-tiga’ data yang digunakan untuk ‘training set’ (untuk pelatihan) dan sisanya ‘sepertiga’ data digunakan sebagai ‘test set’ atau ‘holdout set’ (untuk pengujian). Data pelatihan (training set) digunakan oleh ‘inducer’ (pemroses atau model builder nya), dan classifier yang sudah dibuat kemudian diuji pada ‘test set’ atau ‘holdout set’ (data yang digunakan untuk pengujian). Pengecualian terhadap aturan ini adalah ketika ‘classifier’ nya adalah menggunakan jaringan syaraf tiruan (artificial neural network). Untuk kasus seperti ini, data dibagi menjadi tiga subset yang saling eksklusif satu sama lain, yaitu: training (pelatihan), validation (validasi), dan testing (pengujian). ‘Validation set’ (data yang digunakan untuk validasi) digunakan selama pembuatan model untuk mencegah overfitting (overfitting adalah situasi dimana banyak error yang acak). Gambar berikut menunjukkan methodology ‘simple split’.

Kritik utama dari metode ini adalah bahwa metode ini membuat asumsi bahwa data yang ada dalam dua subset memiliki jenis yang sama (misalnya, memiliki properties yang benar-benar sama). Karena ini adalah pembagian acak yang sederhana, pada kebanyakan dataset yang paling realistis dimana datanya ‘skewed’ (tidak simetris) pada variabel classification, asumsi yang seperti itu bisa saja salah. Untuk memperbaiki situasi seperti ini, sampling yang berlapis-lapis (stratified sampling) sangatlah disarankan, dimana lapisan-lapisan tersebut menjadi variabel output. Meskipun ini merupakan perbaikan pada ‘simple split’, hal ini masih memiliki ‘bias’ yang terkait dengan pembagian acak yang tunggal (pembagian acak sekali saja).

K-FOLD CROSS-VALIDATION.  Untuk memperkecil ‘bias’ yang terkait  dengan sampling random dari sampel data ‘training’ dan ‘holdout’ dalam membandingkan akurasi prediksi dari dua atau lebih metode yang digunakan, kita bisa menggunakan suatu methodology yang disebut dengan ‘k-fold cross validation’. Dalam ‘k-fold cross-validation’, yang disebut juga dengan rotation estimation, dataset yang utuh di pecah secara random menjadi ‘k’ subset dengan size yang hampir sama dan saling eksklusif satu sama lain. Model dalam 'classification’ di-latih dan di-tes sebanyak ‘k’ kali. Setiap kali pelatihan semua dilatih pada semua fold kecuali hanya satu fold saja yang disisakan untuk pengujian. Penilaian cross-validation terhadap akurasi model secara keseluruhan dihitung dengan mengambil rerata dari semua hasil akurasi individu ‘k’, seperti yang ditunjukkan dengan persaman berikut:
Dimana CVA adalah akurasi cross-validation, k adalah jumlah fold yang digunakan, dan A adalah ukuran akurasi (misalnya, hit-rate, sensitivity, specifity) dari masing-masing fold.

Beberapa metodeologi lainnya untuk penilaian pada ‘klasifikasi’ (classification). Beberapa methodology popular lainnya untuk penilaian pada klasifikasi adalah seperti berikut:
  • Leave-one-out. Metode ‘leave-one-out’ mirip dengan ‘k-fold cross-validation’ dimana nilai ‘k’ bernilai 1; yang artinya, setiap data digunakan untuk pengujian sekali pada sebanyak model yang dikembangkan sehingga ada sejumlah titik data. Metode ini sangat menghabiskan waktu, tetapi terkadang untuk dataset yang kecil metode ini adalah pilihan yang cocok.
  • Bootstrapping. Dengan bootstrapping, sejumlah instans yang tetap dari data awal dijadikan sampel (dengan pergantian) untuk pelatihan dan dataset sisanya digunakan untuk pengujian. Proses ini diulang-ulang sebanyak yang dinginkan.
  • Jackknifing. Mirip dengan methodologi ‘leave-one-out’; dengan ‘jackknifing’ akurasi dihitung dengan mengeluarkan satu sampel pada setiap iterasi dari proses estimasi.
  • Area under the ROC curve. ‘Area under the ROC curve’ adalah teknik penilaian secara grafis dimana ‘true positive rate’ digambar pada sumbu ‘Y’ dan ‘false positive rate’ digambar pada sumbu ‘X’.  ‘Area under the ROC curve’ menentukan ukuran akurasi suatu classifier: nilai 1 berarti classifier yang sempurna sedangkan 0.5 berarti tidak lebih baik dibandingkan peluang ‘acak’; dalam kenyataanya, nilai-nilai tersebut akan berkisar antara dua kasus ekstrem. Contohnya, dalam gambar berikut, A memiliki kinerja klasifikasi yang lebih baik dibandingkan B, sementara C tidak lebih baik dibandingkan peluang acak seperti undian melempar coin.



Teknik-teknik pada klasifikasi. Sejumlah teknik (atau algoritma) yang digunakan untuk pemodelan pada classification antara lain adalah seperti berikut:
  • Decision tree analysis (analisa pohon keputusan). Decision tree analysis (atau analisa pohon keputusan adalah suatu teknik yang termasuk keluarga machine-learning) bisa dibilang teknik klasifikasi yang paling popular pada area data mining. Deskripsi detil dari teknik ini diberikan pada bagian selanjutnya.[Lihat video: Ilustrasi tentang decision tree]
  • Statistical analysis (analisa statistik). Teknik-teknik statistik pada awalnya adalah algoritma klasifikasi yang populer selama bertahun-tahun sampai dengan kemunculan teknik-teknik ‘machine-learning’. Teknik-teknik klasifikasi statistik antara lain ‘logistic regression’ (regresi logistik) dan discriminant analysis (analisa diskriminan), keduanya berasumsi bahwa hubungan antara variabel input dan output pada dasarnya adalah linear, data terdistribusi normal, dan variabel-variabel tidak saling terkait dan tidak tergantung satu sama lain. Sifat-sifat dasar asumsi yang diragukan ini akhirnya membawa pergeseran ke arah teknik-teknik ‘machine-learning’.
  • Neural networks (jaringan syaraf tiruan). Ini adalah salah satu diantara teknik-teknik dalam ‘machine-learning’ yang paling popular yang bisa digunakan untuk problem-problem klasifikasi. 
  • Case-based reasoning (penalaran berbasis kasus). Pendekatan ini menggunakan kasus historis untuk mengenali berbagai kesamaan untuk menentukan suatu kasus baru ke dalam kategori yang paling mungkin.
  • Bayesian classifiers (classifier Bayesian). Pendekatan ini menggunakan teori probabilitas untuk membuat model-model klasifikasi berdasarkan kejadian-kejadian di masa lalu yang bisa untuk menempatkan suatu instans baru ke dalam kelas (atau kategori) yang paling mungkin.
  • Genetic algorithms (algoritma genetik). Penggunaan analogi terhadap evolusi alami untuk membuat mekanisme berbasis pencarian yang terarah untuk mengklasifikasikan sampel-sampel data.
  • Rough sets. Metode ini mempertimbangkan keanggotaan parsial dari label-label kelas ke kategori-kategori yang telah ditetapkan sebelumnya dalam membuat model-model (kumpulan aturan) untuk problem klasifikasi.

Gambaran utuh mengenai semua teknik-teknik klasifikasi akan jauh melampui scope seri ini, jadi hanya beberapa yang paling popular saja akan dibahas disini.

Decision trees (pohon keputusan). Sebelum menjelaskan detil-detil mengenai ‘decision tree’, kita perlu mendiskusikan suatu terminologi yang sederhana. Pertama, ‘decision tree’ meliputi banyak variabel input yang mungkin memiliki dampak pada klasifikasi berbagai pola yang berbeda. Variabel-variabel input tersebut biasanya disebut dengan ‘atribut’.  Contohnya, andaikan kita membuat suatu model untuk mengklasifikasikan ‘risiko terhadap utang’ berdasarkan dua karakteristik – ‘income’ dan ‘credit rating’ – dua karakteristik tersebut akan menjadi atribut-atribut dan output hasilnya adalah ‘class label’ (label kelas) (misalnya, low, medium, atau high risk). Kedua, satu pohon berisi beberapa cabang dan node (simpul). Satu cabang mewakili hasil dari suatu pengujian untuk mengklasifikasikan suatu pola (berbasis dari suatu pengujian) dengan menggunakan salah satu dari atribut-atribut tersebut. Satu ‘leaf node’ yang di ujung merupakan pilihan kelas yang terakhir untuk suatu pola (satu rantai cabang dari ‘root node’ hingga ke ‘leaf node’ yang akan disajikan sebagai ‘statement if-then’ yang kompleks).
Ide dasar dari ‘decision tree’ adalah bahwa decision tree membagi ‘training set’ (data pelatihan) secara rekursif hingga masing-masing divisi berisi contoh dari satu kelas secara keseluruhan. Setiap ‘non-leaf node’ terdapat suatu ‘split point’, yang digunakan untuk pengujian pada satu atau lebih atribut dan menentukan bagaimana data dibagi/dipilah lebih lanjut. Algoritma-algoritma pada decision tree, secara umum, membuat tree awal dari data pelatihan sedemikian rupa sehingga setiap ‘leaf node’ adalah bersih, dan kemudian memangkas tree tadi untuk meningkatkan generalisasinya, dan dari situlah akurasi pada data pengujian (test data). 
Pada fase pertumbuhan, tree tadi dibangun dengan cara membagi/membelah data secara rekursif hingga setiap divisi (hasil pembagian/pembelahan) bisa bersih (misalnya, hanya berisi anggota dari kelas yang sama) atau relatif kecil. Ide dasarnya adalah mengajukan pertanyaan yang jawaban-jawabannya akan memberikan informasi terbanyak, mirip dengan apa yang kita lakukan kita bermain game “Twenty Questions”.
Pembelah yang digunakan untuk membagi data bergantung pada jenis atribut yang digunakan pada pembelah tersebut. Untuk atribut kontinyu A, pembelahnya dalam bentuk value(A) < x, dimana x adalah suatu nilai maksimum. Contohnya, pembelah yang berdasarkan ‘income’ bisa berupa “income < 50000”.  Untuk atribut kategori A, pembelahnya dalam bentuk value(A) ada pada x, dimana x adalah ‘subset’ dari A. Sebagai contohnya, pembelahnya bisa berbasis gender: “Male vs Female”.
Algoritma umum untuk membuat pohon keputusan adalah seperti berikut:
  1. Buat satu ‘root node’ dan tugaskan semua data pelatihan ke ‘root node' tersebut.
  2. Pilih atribut pembelah yang terbaik
  3. Tambahkan satu cabang ke ‘root node’ untuk setiap nilai pembelah. Belahlah data menjadi subset yang saling eksklusif satu sama lain (tidak overlapping) disepanjang garis pembelah tersebut dan terapkan ke cabang-cabang.
  4. Ulangi langkah 2 dan 3 untuk setiap ‘leaf node’ hingga kriteria yang membuat berhenti dicapai (misalnya, node didominasi oleh label kelas  yang hanya berisi satu label saja)

Banyak algoritma lain yang berbeda telah diusulkan untuk membuat decision tree. Algoritma-algoritma itu berbeda terutama mengenai caranya dalam menentukan atribut pembelahnya (dan nilai pembelahnya), urutan dalam membelah atribut (membelah atribut yang sama hanya sekali atau berkali-kali), jumlah belahan di setiap node (binary vs ternary), kriteria penghenti, dan pemangkasan tree (pra- vs paska-pemangkasan). Beberapa algoritma yang paling terkenal adalah ID3 (diikuti dengan C4.5 dan C5 sebagai versi ID3 yang sudah di-upgrade) dari machine-learning, ‘classification and regression trees (CART) dari statistic, dan ‘chi-squared automatic interaction detector (CHAID) dari ‘pattern recognition’.

Ketika membuat suatu decision tree, tujuan dari setiap node adalah untuk menentukan atribut dan titik pembelah atribut yang membagi dengan cara terbaik data-data pelatihan untuk membersihkan penyajian kelas pada node tersebut. Untuk mengevaluasi seberapa baik pembelahnya, beberapa indeks untuk pembelah pernah diusulkan. Dua diantaranya yang paling umum adalah ‘Gini index’ dan ‘information gain’. Gini index dipakai di algoritma CART dan algoritma SPRINT (Scalable PaRallelizable Induction of Decision Trees). Beberapa versi dari ‘information gain’ dipakai pada ID3 (dan versi yang lebih baru yaitu C4.5 dan C5).

Gini index sudah dipakai di bidang ekonomi untuk mengukur perbedaan populasi. Konsep yang sama bisa digunakan untuk menentukan kemurnian dari kelas tertentu sebagai hasil dari keputusan untuk mempercabang disepanjang atribut atau variabel tertentu. Belahan terbaik adalah belahan yang meningkatkan kemurnian data yang dihasilkan dari pembelah yang sudah diusulkan/diajukan. Mari kita coba lihat sekilas pada kalkulasi sederhana dari Gini index:

Jika dataset S berisi contoh-contoh dari kelas-kelas n, Gini index adalah sebagai berikut
Dimana pj adalah frekwensi relative dari kelas j dalam S. Jika dataset S dibelah ke dalam dua subset, S1 dan S2, dengan size N1 dan N2, secara berurutan, Gini index dari data yang terbelah berisi contoh dari kelas n, dan Gini index didefinisikan dengan
Kombinasi atribut/pembelah yang memberikan ginisplit(S) terkecil dipilih untuk membelah node atau simpul. Dalam penentuan seperti itu, kita harus menghitung satu-satu semua titik pembelah yang mungkin untuk setiap atribut.

Information gain adalah mekanisme membelah yang dipakai pada ID3, yang barangkali merupakan algoritma decision tree yang paling luas diketahui. Information gain dikembangkan oleh Ross Quinlan pada 1986, dan sejak saat itu dia mengevolusikan algoritma ini ke algoritma C4.5 dan C5. Ide dasar dibalik ID3 (dan variannya) adalah menggunakan konsep yang disebut dengan ‘entropy’ sebagai penggganti dari Gini index. Entropy mengukur tingkat ke-tidakpasti-an atau ke-acak-an dalam suatu dataset. Jika semua data di dalam subset hanya menjadi milik satu kelas saja, itu berarti tidak ada ‘ke-tidakpasti-an’ atau ‘ke-acak-an’ dalam dataset tersebut; jadi entropy-nya adalah nol. Tujuan dari pendekatan ini adalah membuat ‘subtrees’ sehingga entropy dari setiap subset terakhir adalah nol (atau mendekati nol). Mari kita coba lihat pada kalkulasi dari information gain.

Anggap saja ada dua kelas, P (positif) dan N (negatif). Dataset S berisi sejumlah p dari kelas P dan sejumlah n dari kelas N. Jumlah informasi yang diperlukan untuk memutuskan jika suatu contoh acak dalam S menjadi milik P atau N adalah sebagai berikut
 

Anggaplah bahwa dengan menggunakan atribut A satu dataset S akan dibagi menjadi beberapa set {S1, S2, …, Sv}. Bila Si berisi contoh-contoh pi dari P dan contoh-contoh ni dari N, entropy, atau informasi yang diharapkan, yang diperlukan untuk mengklasifikasikan object-object dalam semua subtrees Si, adalah

Kemudian informasi yang akan didapatkan dengan mempercabangkan atribut A akan menjadi

                   Gain(A)= I(p,n)- E(A)

Kalkulasi-kalkulasi tersebut diulang untuk setiap atribut, dan atribut dengan ‘information gain’ yang tertinggi dipilih sebagai atribut pembelah. Ide dasar dibalik index pembelah ini agak mirip satu sama lain tetapi detil-detil algoritmanya sangat bervariasi. Definisi detil mengenai algoritma ID3 dan mekanisme pembelahannya bisa ditemukan di Quinlan (1986).

Analisa cluster pada Data Mining

Analisa cluster merupakan metode dalam DM yang sangat penting untuk mengklasifikasi items, events, atau concepts kedalam group-group umum yang disebut dengan ‘clusters’. Metode ini pada umumnya digunakan dalam biologi, kedokteran, genetika, analisa jaringan social, anthropologi, arkeologi, astronomi, pengenalan karakter (character recognition), dan bahkan pada pengembangan MIS (Management Information Systems). Karena DM sudah meningkat popularitasnya, teknik-teknik yang mendasarinya telah diterapkan hingga ke bisnis, terutama untuk marketing. Analisa cluster telah digunakan secara luas untuk pendeteksi penipuan (baik pada kartu kredit maupun penipuan dalam e-commerce) dan segmentasi market para pelanggan pada sistem CRM modern. Semakin banyak aplikasi yang diterapkan pada bisnis dan terus dikembangkan karena kekuatan analisa cluster sudah diketahui dan digunakan.

Analisa cluster adalah tool analisa data yang bersifat eksploratif untuk memecahkan berbagai problem klasifikasi. Tujuannya adalah menyortir berbagai macam kasus (misalnya, orang, hal-hal, dan peristiwa-peristiwa) ke dalam group, atau cluster, sehinggga tingkat asosiasi diantara anggota-anggota dengan cluster yang sama adalah kuat dan diantara anggota-anggota cluster yang berbeda adalah lemah. Setiap cluster menjelaskan kelas mana para anggotanya berada. Satu contoh analisa cluster satu dimensi adalah menetapkan kisaran nilai dimana didalamnya akan diberikan nilai-nilai kelas untuk suatu kelas kuliah. Ini mirip dengan problem analisa cluster yang dihadapi oleh department keuangan amerika ketika menetapkan golongan pada tahun 1980an. Contoh fiktif clustering adalah buku-buku novel Harry Potter dari J.K. Rowling. Topi penyortir menentukan ke asrama mana untuk menugaskan siswa tahun pertama di Hogwarts School. Contoh lain adalah menentukan bagaimana mengatur tempat duduk para tamu di pesta perkawinan. Sejauh yang dialami data mining, pentingnya analisa cluster adalah bahwa analisa ini menyingkapkan asosiasi dan struktur dalam data yang tidak nampak sebelumnya tetapi sangat bermanfaat setelah ditemukan.

Hasil-hasil dari analisa cluster mungkin bisa digunakan untuk:
  • Mengidentifikasi skema klasifikasi (misalnya, jenis-jenis pelanggan)
  • Menyarankan berbagai model statistik untuk menjelaskan populasi
  • Menunjukkan berbagai macam ‘rule’ (aturan) untuk menugaskan berbagai kasus baru ke kelas-kelas untuk berbagai maksud identifikasi, targeting, dan diagnose
  • Memberikan takaran terhadap definisi, size, dan perubahan pada apa yang sebelumnya merupakan konsep yang luas
  • Menemukan kasus yang khas untuk diberi label dan menyajikan kelas
  • Menurunkan size dan kompleksitas problem untuk berbagai metode DM lainnya
  • Mengidentifikasi data ‘asing’ pada domain tertentu (misalnya deteksi event yang jarang)
Menentukan jumlah cluster maksimal. Algoritma-algoritma dalam clustering biasanya memerlukan satu angka untuk menentukan jumlah cluster yang dkan ditemukan. Bila angka ini tidak diketahui dari knowledge sebelumnya, angka itu harus dipilih dengan suatu cara. Sayangnya tidak ada cara yang optimal untuk menghitung angka berapakah itu. Karena itu, beberapa metode heuristic yang berbeda-beda sudah diusulkan. Berikut adalah beberapa cara yang paling umum yang menjadi referensi:
  • Lihatlah pada persentase varians yang dijelaskan sebagai suatu fungsi dari jumlah cluster; yakni, pilihlah sejumlah cluster sehingga bila menambahkan satu cluster lain tidak akan memberikan pemodelan data yang jauh lebih baik. Secara spesifik, bila kita menggambar grafik persentase varians yang ditunjukkan oleh cluster-cluster tersebut, ada satu titik dimana keuntungan/keunggulan marjinal akan turun (digambar dengan suatu sudut pada grafik tersebut), yang menunjukkan jumlah cluster untuk dipilih.
  • Tentukan jumlah cluster ke (n/2)1/2, dimana n adalah jumlah titik-titik data. 
  • Gunakan ‘Akaike Information Criterion’ (AIC), yang merupakan ukuaan seberapa bagus tingkat kecocokannya (berdasarkan konsep entropy) untuk menentukan jumlah cluster.
  • Gunakan ‘bayesian Information Criterion (BIC), yang merupakan suatu criteria pemilihan model (berdasarkan estimasi kemungkinan maksimum) untuk menentukan jumlah cluster.
Beberapa metode analisa. Analisa cluster bisa saja berbasiskan pada satu atau lebih metode-metode umum berikut ini:
  • Metode-metode statistik (termasuk hirarkikal dan nonhirarkikal), seperti k-means, k-modes, dan seterusnya.
  • Jaringan syaraf tiruan / neural networks (dengan arsitektur yang disebut dengan self-organizing map atau SOM)
  • Logika samar / fuzzy logic (misalnya, fuzzy c-means algoritm)
  • Algoritma genetik
Masing-masing dari metode tersebut bekerja dengan satu atau dua kelas metode umum:
  • Divisive (dipecah-pecah). Dengan kelas-kelas ‘divisive’, semua items mulai dengan satu cluster dan kemudain dipecah-pecah.
  • Agglomerative. Dengan kela-kelas ‘agglomerative’, semua items mulai dengan cluster-cluster individu , dan kemudian cluster-cluster itu digabungkan bersama-sama.
Kebanyakan metode analisa cluster melibatkan penggunaan suatu pengukuran jarak untuk menghitung kedekatan antara pasangan-pasangan items. Beberapa jenis pengukuran jarak yang popular adalah jarak ‘Euclidian’ (jarak lurus biasa diantara dua titik yang akan diukur dengan suatu penggaris) dan jarak ‘Manhattan’ (disebut juga dengan jarak ‘rectilinear’, atau jarak ‘taxicab’, diantara dua titik). Seringkali, pengukuran-pengukuran tersebut didasarkan pada jarak sebenarnya yang diukur, tetapi ini tidak perlu begitu, seperti biasanya terjadi dalam pengembangan sistem informasi. Rerata yang diberi bobot bisa digunakan untuk menetapkan jarak-jarak tersebut. Contohnya, dalam suatu project sistem informasi, modul-modul individu dari sistem bisa mungkin terkait dengan kemiripan antara input, output, proses, dan data tertentu yang digunakan. Faktor-faktor tersebut kemudian disatukan, berpasangan berdasar item, menjadi satu pengukuran (jarak) tunggal saja.

Algoritma clustering k-means. Algoritma k-means (dimana k adalah jumlah cluster yang sudah ditetapkan sebelumnya) bisa dibilang algoritma clustering yang paling banyak direferensikan. Algoritma ini memiliki root-nya pada analisa statistik tradisional. Seperti tersirat dalam namanya, algoritma tersebut menunjuk setiap objek data (customer, event, object, etc) ke cluster yang pusatnya (disebut juga ‘centroid’) adalah yang terdekat. Pusat tersebut dihitung sebagai rerata dari semua titik pada cluster tersebut; yakni, koordinat-koordinatnya adalah rerata aritmetika untuk setiap dimensi secara terpisah di semua titik dalam cluster tersebut. Langkah-langkah algoritma tersebut adalah seperti dibawah ini dan ditunjukkan secara grafis pada gambar dibawahnya:

Tahap inisialisasi: pilihlah jumlah cluster (misalnya, nilai dari k)

Langkah 1: secara acak hasilkan titik-titik acak ‘k’ sebagai pusat-pusat cluster awal.
Langkah 2: tugaskan setiap titik ke pusat cluster terdekat
Langkah 3: hitung lagi pusat-pusat cluster baru

Tahap repetisi (pengulangan): ulangi langkah 2 dan 3 sampai suatu kriteia konvergensi dipenuhi (biasanya hingga penugasan titik-titik ke cluster-cluster menjadi stabil)


Association Rule Mining (Penggalian Aturan Asosiasi)

Association rule mining adalah metode dalam DM yang sangat popular yang biasanya digunakan sebagai contoh untuk menjelaskan mengenai apakah data mining itu dan apa yang bisa dilakukan bagi para pengguna yang kurang fasih secara teknologi. Sebagian besar dari kita tentu sudah mendengar mengenai hubungan yang terkenal (atau tercemar, tergantung dari cara kita melihatnya) antara penjualan bir dan popok di toko grosir. Menurut cerita, suatu supermarket besar (entah Wal-Mart, entah bukan; karena tidak ada konsensus mengenai supermarket mana) telah melakukan analisa kebiasaan belanja dari para pelanggan dan menemukan korelasi yang amat penting antara pembelian bir dan pembelian popok. Kemudian hal ini diteorikan alasannya bahwa para ayah (rupanya adalah para lelaki muda) ketika membeli popok ke supermarket untuk membeli popok buat bayi mereka (bisanya setiap hari kamis), karena mereka tidak bisa lagi pergi ke tempat olah raga sering-sering, maka mereka juga membeli bir. Sebagai hasil dari temuan tersebut, supermarket diperkirakan telah menempatkan popok disebelah bir, yang hasilnya adalah penjualan yang meningkat pada kedua barang tersebut.

Pada dasarnya, association rule mining bertujuan untuk menemukan hubungan (pertalian) antara berbagai variabel (item-item) pada database yang sangat besar. Karena penerapannya dianggap berhasil dalam menyelesaikan berbagai problem bisnis, biasanya teknik ini juga disebut dengan ‘market-basket analysis’ (analisa keranjang belanja). Ide utama dalam analisa keranjang belanja ini adalah  mengidentifikasi hubungan yang kuat antara berbagai produk (atau layanan) yang biasanya dibeli secara bersamaan (ada dalam keranjang secara bersama-sama, baik keranjang fisik di toko grosir atau keranjang virtual di situs e-commerce). Contohnya, analisa keranjang belanja mungkin saja menemukan suatu pola seperti, “Bila seorang pelanggan membeli computer laptop dan software anti-virus, dia juga akan membeli rencana perpanjangan layanan pada 70% dari waktu yang disediakan).” Input pada analisa keranjang belanja adalah data transaksi pada ‘Point of Sale’ PoS), dimana sejumlah produk dan/atau layanan yang dibeli secara bersamaan (persis seperti isi struk belanja) ditabulasikan dalam satu instans transaksi tunggal. Hasil dari analisa adalah informasi yang ternilai yang bisa digunakan untuk memahami lebih baik mengenai perilaku belanja para pelanggan yang bisa digunakan untuk memaksimalkan profit dari transaksi bisnis. Dari sisi bisnis bisa memanfaatkan knowledge seperti itu dengan cara (1) menaruh/menempatkan barang-barang berdekatan satu sama lain supaya lebih enak bagi pelanggan untuk mengambil barang-barang itu dan supaya pelanggan juga tidak lupa untuk membeli salah satu ketika membeli yang lainnya (sehingga meningkatkan volume penjualan); (2) mempromosikan produk-produk sebagai satu paket (jangan menempatkan satu produk pada penjualan jika yang lainnya sedang memberikan promosi); dan (3) memisahkan satu dengan (produk) yang lainnya supaya pelanggan harus berjalan melalui lorong-lorong untuk mencarinya, dan dengan begitu juga berpotensi melihat dan membeli produk lainnya.

Penerapan analisa keranjang belanja termasuk ‘cross-marketing’, ‘cross-selling’, desain/tata letak toko, desain catalog, desain situs e-commerce, optimasi periklanan online, product pricing, dan konfigurasi penjualan/promosi. Pada dasarnya, analisa keranjang belanja membantu peran bisnis dalam menarik kesimpulan atas kebutuhan dan preferensi dari pola-pola belanja pelanggan. Diluar dunia bisnis, association rules biasanya digunakan untuk menemukan hubungan antara gejala dan penyakit, diagnose dan karakteristik pasien dan pengobatan (digunakan dalam DSS medis), dan gen dan fungsinya (digunakan dalam project genom).
Suatu pertanyaan bagus untuk ditanyakan berkaitan dengan pola/hubungan yang bisa diungkap oleh association rule mining adalah “Apakah semua association rule itu menarik dan bermanfaat?” Untuk menjawab pertanyaan seperti itu, association rule mining menggunakan dua metrik umum: ‘support’ dan ‘confidence’. Sebelum mendefinisikan kedua istilah tersebut, mari kita lihat hal yang sedikit teknis dengan melihat seperti apa association rule itu:

X==>Y [S%,C%]

{Komputer Laptop, Software antivirus} ==> {Rencana PerpanjanganLayanan} [30%, 70%]

Disini, X (produk dan/atau layanan; disebut ‘left-hand side’, LHS, atau antecedent) diasosiakan dengan Y (produk dan/atau layanan; disebut ‘right-hand side’, RHS, atau consequent). S adalah ‘support’, dan C adalah ‘confidence’ untuk aturan khusus ini. support (S) dari suatu rulr adalah ukuran mengenai seberapa sering produk-produk dan/atau layanan (misalnya LHS + RHS = Komputer Laptop, Software antivirus, dan Rencana perpanjangan layanan) muncul bersamaan dalam transaksi yang sama; yaitu, proporsi transaksi dalam dataset yang berisi semua produk dan/atau layanan yang disebutkan dalam rule tertentu. Dalam contoh ini, 30 persen dari semua transaksi dalam database toko fiktif ini memilki semua tiga produk ini dalam satu struk penjualan. ‘Confidence’ dari suatu rule ini adalah ukuran seberapa sering produk dan/atau layanan dibagian RHS (consequent) ada bersamaan dengan produk dan/atau layanan pada LHS (antecedent); yakni, proporsi transaksi yang meliputi LHS dan juga meliputi RHS. Dengan kata lain, itu adalah probabilitas bersyarat untuk mendapatkan RHS yang ada dalam transaksi-transaksi dimana LHS sudah ada. 

Beberapa algorithma sudah tersedia untuk menghasilkan rule asosiasi. Beberapa algorithma yang terkenal adalah Apriori, Eclat, dan FP-Growth. Algorithma-algorithma tersebut hanya melakukan setengah saja dari pekerjaan itu, yaitu mengidentifikasi data-data produk yang sering muncul dalam database. Setelah data-data produk diidentifikasi, data-data tersebut perlu dikonversi menjadi rule-rule dengan bagian-bagian ‘antecedent’ dan ‘consequent’. Penentuan rule-rule dari data-data produk yang sering muncul adalah suatu proses pencocokan langsung, tetapi proses tersebut mungkin sangat memakan waktu bila dilakukan dengan database yang sangat besar. Meskipun bisa saja ada banyak item pada setiap bagian dari rule tersebut, pada praktiknya bagian ‘consequent’ biasanya berisi satu item tunggal saja. Bagian berikut ini akan dijelaskan salah satu algoritma yang paling popular untuk identifikasi data-data produk yang sering muncul.

Algorithma Apriori. Algorithma apriori adalah yang paling umum digunakan untuk menyingkap berbagai ‘association rule’. Misalkan ada satu set dari beberapa itemsets (misalnya, beberapa set transaksi retail, masing-masing memiliki item individu yang sudah dibeli), algorithma ini akan mencoba menemukan subset-subset yang sama dengan setidaknya sejumlah minimum dari itemsets (misalnya, memenuhi/setara dengan ‘support’ minimum). Apriori menggunakan pendekatan ‘bottom-up’, dimana subset-subset yang sering muncul ditambahkan satu item pada satu waktu (suatu metode yang dikenal dengan ‘candidate generation’, dimana volume subset-subset yang sering muncul bertambah dari subset-subset dengan satu-item menjadi subset-subset dengan dua-item, kemudia subset dengan tiga-item, etc), dan grup-grup kandidat pada setiap level diuji terhadap data pada minimum ‘support’. Algoritma tersebut akan berhenti bila tidak ada lagi penambahan yang berhasil untuk ditambahkan.

Sebagai contoh ilustrasi, pertimbangkan hal berikut. Sebuah toko grosir melacak transaksi penjualan melalui SKU (stock-keeping unit) dan dengan begitu tahu item-item mana yang biasanya dibeli secara bersamaan. Database transaksi, diikuti dengan langkah-langkah berikutnya dalam mengidentifikasi itemset-itemset yang sering muncul, ditunjukkan seperti dalam gambar berikut dibawah ini.

Masing-masing SKU dalam database transaksi berhubungan dengan suatu produk, mislanya “1 = butter”, “2 = bread”, “3 = water”, dan seterusnya. Langkah pertama dalam Apriori adalah menghitung frekwensi (misalnya, untuk ‘support’) dari tiap-tiap item (itemsets dengan satu-item). Karena ini adalah contoh yang terlalu disederhanakan, mari kita tetapkan minimum support adalah 3 (atau 50%; yang artinya bahwa satu itemset dipertimbangkan sebagai itemset yang sering muncul apabila menunjukkan sekurang-kurangnya 3 dari 6 transaksi di database). Karena semua itemsets dengan satu-item memiliki setidaknya 3 pada kolom ‘support’, mereka semua dimasukkan sebagai itemsets yang sering muncul. Namun, andaikan ada itemsets dengan satu-item tersebut tidak sering muncul, itemsets tersebut tidak akan dimasukkan sebagai anggota dari itemset dengan dua-item pada level berikutnya. Dengan begitu, Apriori akan ‘memangkas’ pohon dari semua itemsets yang berpotensi terjadi seperti itu. Seperti ditunjukkan dalam gambar di atas, dengan menggunakan itemsets dengan satu-item, semua itemsets dengan dua-item yang potensial dihasilkan dan database transaksi digunakan untuk menghitung nilai ‘support’. Karena itemset dengan dua-item {1,3} memiliki ‘support’ yang kurang dari 3, maka itemset tersebut tidak dimasukkan dalam itemsets yang sering muncul yang akan digunakan untuk menghasilkan itemsets di level berikutnya (itemsets dengan tiga-item). Algorithma tersebut kelihatannya sederhana, dan itu agaknya menipu, karena contoh di atas hanya untuk dataset yang kecil. Pada dataset yang jauh lebih besar, terutama pada jumlah item yang sangat banyak tetapi dengan kuantitas yang sedikit dan jumlah item yang sedikit tetapi dengan kuantitas yang sangat besar, proses pencarian dan penghitungan akan menjadi suatu proses yang sangat intensif secara komputasinal.

No comments:

Post a Comment