Evaluasi Eksternal Clustering “Pairwise” F-ß-Score & NMI: Teori & Aplikasi

Tidak seperti model klasifikasi (supervised learning), evaluasi pada model clustering (unsupervised learning) jauh lebih menantang. Mengapa? Hal ini berawal dari definisi awal permasalahan pengelompokan (clustering) yang sebenarnya tidak well-definedditambah dengan tidak adanya nilai pembanding yang jelas seperti klasifikasi. Namun pada kasus tertentu, terdapat suatu nilai pengelompokan pembanding yang biasa disebut Ground Truth (GT)/gold standard. GT ini adalah pengetahuan sebelumnya (prior information kalau kata orang Bekasi :) ) yang dapat digunakan untuk mendapatkan hasil evaluasi clustering yang lebih terarah (tidak musti objective, malah seringnya subjective). Namun sayangnya menggunakan GT untuk evaluasi semi-supervised clustering tidak semudah pada kasus klasifikasi. Artikel ini akan membahas secara mendalam penggunaan GT, baik secara teori, maupun aplikasinya.

Pendahuluan

Saya akan mulai terlebih dahulu dengan mengapa saya menulis artikel ini. Hingga saat ini rujukan untuk pairwise clustering evaluation (evaluasi eksternal clustering) sangatlah terbatas, bahkan hanya ada satu referensi yang biasanya digunakan, yaitu buku Introduction to Information Retrieval oleh Christopher D. Manning. Walau penjelasan di buku tersebut menurut saya sudah cukup baik, namun cukup banyak pembaca yang masih bingung dalam penerapannya. Setidaknya sudah beberapa orang japri/PM saya menawarkan MLM, eh salah… maksud saya menanyakan hal ini.
Tidak hanya itu, “Anehnya” hampir di semua software analisis data seperti RapidMiner, Weka, SPSS, SAS, bahkan sampai modul Python seperti SciPy/Scikit-Learn (saat artikel ini ditulis) tidak memiliki fungsi untuk menghitung pairwise F-Score, random index, purity, dll (yang ada hanya pairwise NMI di SciPy). Karena minimnya referensi dan tools terkait evaluasi pairwise (eksternal) ini, saya menulis artikel & mengupload beberapa script untuk menghitung metric-metric ini. Amal jariah bisa berbentuk codes/tools kan ya?  … :D …. Script Matlab diberikan untuk yang versi dasar yang mudah dipahami untuk pemula, namun hanya cocok untuk data yang kecil. Sedangkan script PyThon (python 2 & 3) diberikan dengan algoritma yang cocok untuk data yang lebih besar.

Clustering VS Semi-Supervised Clustering VS Klasifikasi: Apa bedanya?

Saya mengasumsikan minimal pembaca sudah mengetahui tentang dasar unsupervised learning (clustering) dan supervised learning (klasifikasi). Kalau belum, please baca “post ini“ terlebih dahulu. Mengapa Semi-Supervised clustering dan bukan clustering unsupervised biasa saja? Baca di post ini di bagian semi-supervised clustering. Tapi kalau sudah baca, namun masih bingung atau kurang PeDe atau kurang kasih sayang … mari kita simak ilustrasi berikut … :)
Misal tabel berikut adalah hasil output sebuah sembarang data (5 objek/datum/instances) dari 2 model clustering yang berbeda,  2 model klasifikasi yang berbeda, sebuah hasil semi-supervised clustering, dan sebuah nilai pembanding cluster Ground Truth (GT/gold standard). Catatan: berarti di klasifikasi, hasil dibawah adalah variabel target/dependent ya … kalau bingung apa itu variabel target/dependent, silahkan pegangan … eh salah… maksudnya silahkan baca “post ini“.
idCluster Label ICluster Label IIclass/category  Iclass/category IISSC labelGT
1121236
2121236
3212157
4212157
5352198
Contoh ini akan memperjelas 2 hal: yang pertama beda cara kita melihat hasil klasifikasi dan clustering/SSC dan yang kedua mengapa evaluasi di SSC lebih menantang ketimbang klasifikasi.
  1. Beda makna hasil clustering dan klasifikasi:
    Misal kolom 2 dan kolom 3 adalah hasil clustering dari 2 algoritma yang berbeda (“misal” sebut saja k-means dan EM). Perhatikan, walaupun kolom 2 dan 3 memiliki nilai yang berbeda, namun hasil clustering kolom kedua “sama bin idem wal serupa” dengan kolom ketiga. Mengapa? Karena clustering tugasnya hanya mengelompokkan. Sedangkan nama kelompoknya hanyalah label belaka, boleh berbeda-beda. angka 1,2,3, dan 5 di kolom 2 dan 3 hanyalah label yang nilainya bisa diganti-ganti. Contoh, kolom ke-3 bisa diganti dengan nilai di kolom kedua & itu syah/valid bin boleh wal okay …. :) … bahkan nama kelompoknya bisa diganti dengan nama kelompok KelompenCapir atau nama kelompok ibu-ibu PKK … :D … cuma codingnya geli aja nanti rasanya … :p …

    Makna sesungguhnya dari tiap clusternya butuh cabang ilmu tersendiri di data science. Yang paling sederhana, secara umum tentu saja kita bisa melihat nilai centroid-nya (pusat). Untuk data text, kita bisa menggunakan metode-metode di cluster summarization, topic modelling, atau menggunakan cluster hubs untuk data berdimensi tinggi.

    Namun hal ini tidak berlaku untuk hasil klasifikasi (kolom 4 dan 5). Variable target adalah kelas/kategori yang memiliki makna khusus. Misal “1” bermakna “kanker ganas” dan “2” bermakna “bukan kanker”.  Sehingga kolom ke-4 dan ke-5 memiliki hasil yang tidak sama, dan bahkan saling bertolak belakang. Dan kalau nilai-nilai ini dituker bisa berabe, bayangkan orang yang ndak kena kanker, tiba-tiba di vonis kena kanker ganas (atau sebaliknya). tapi karena ketegasan makna variabel target ini, menghitung error (evaluasi) di klasifikasi sangat mudah. Kita tinggal hitung berapa yang benar, dan berapa yang salah. Akurasi modelnya di dapat dari presentase proporsi jumlah prediksi yang benar.
  2. Mengapa evaluasi di SSC/eksternal evaluasi clustering lebih riweuh?
    Lah iya gimana ndak riweuh… karena nilai labelnya boleh bermacam-macam. Sebagai contoh, hasil clustering (fully unsupervised) di kolom {2,3} dan hasil SSC di kolom ke-5 kalau dibandingkan dengan nilai ground truth di kolom terakhir (ke-6) itu semua podo bin sama wal the same. Lah, terus gimana dong? Mau ga mau untuk menghitung metric (nilai) evaluasinya haruslah dengan menggunakan perbandingan berpasangan (pairwise comparisons)…. wuidih mahluk apa ya ini? kalau jomblo dan belum punya pasangan apa iya bisa menghitungnya?… Tenang saja ga usah hawatir, insya Allah dengan rahmat-Nya Agan akan dapet jodoh… eh salah, maksudnya bisa mengevaluasi (eksternal) pairwise-clustering.

True/False – Positive/Negative

Di klasifikasi ada confusion matrix yang isinya adalah nilai-nilai True Positive (TP), True Negative (TN), False Positive (FP), dan False Negative (FN). Apa itu TP, TN, FP, dan FN ? yang jelas mereka bikin confuse (bingung) ya? … :D … tenang, gampang kok ngertiinnya. Keterangan lengkap di wikipedia tentang hal ini sudah cukup jelas dan cantik,… eh salah maksudnya rinci  (silahkan baca disini). Saya akan bahas secara sekilas saja, lalu lebih banyak nanti membahas makna ke-4 nilai tersebut di SSC (karena maknanya akan berubah & merupakan kunci penting dalam memahami evaluasi pairwise clustering).
Secara sederhana makna TP-TN-FP-FN di klasifikasi secara mudah dijelaskan oleh tabel berikut:
confusion matrix
“True” jika prediksinya benar. Positive jika itu korespon ke nilai yang positive dan likewise ke yang negative. “False” jika prediksinya salah misal harusnya 0 diprediksi 1 atau sebaliknya. Masih bingung juga? … ini nih penjelasan yang paling mudah sekali memahaminya.
False Positive – False Negative … :D

TP-TN-FP-FN di clustering atau SSC

Emang beda makna ya di clustering? … ya iya …. kan tadi sudah dibahas, di clustering label tidak memiliki makna tetap, dan hal tersebut memaksa kita tidak menggunakan nilai labelnya secara langsung. Yang kita bisa lakukan adalah melakukan perbandingan berpasangan. Apakah itu? … ini nih maksudnya.
TP-TN-FP-FN di clustering atau SSC:
  1.  True Positive (TP):
    dua objek (misal d1 dan d2) berdasarkan hasil sebuah algoritma clustering berada di kelompok yang sama, dan “menurut GT” memang keduanya benarberada di kelompok yang sama. Misal di GT label d1 dan d2 = {1, 1} dan di clustering = {3, 3}.
  2. True Negative (TN):
    d1 dan d2 tidak dikelompokan ke dalam satu cluster, dan memang menurut GT mereka berdua ndak berjodoh. Misal di GT label d1 dan d2 = {1,2} dan di clustering = {7, 8}
  3. False Positive (FP):
    d1 dan d2 menurut GT harusnya berada di kelompok yang berbeda, tapi karena satu dan lain hal mereka dikelompokkan ke 2 cluster yang sama oleh algoritma clusternya. Ini kayak dijodohin paksa gitu deh Gan … :v …. Misal di GT label d1 dan d2 = {1, 2} dan di hasil clustering = {5, 5}
  4. False Negative (FN):
    d1 dan d2 menurut GT harusnya di cluster sama, tapi dipisahkan oleh jarak dan waktu,… eh salah… maksudnya oleh hasil clusteringnya (kebalikan FP). Misal di GT label d1 dan d2 = {2, 2} dan di hasil clustering = {5, 7}.
Nah… kalau sudah paham,… menghitung precision, recall, F-ß-score, & Random index. jadi mudah banget deh … tinggal hitung saja ada berapa banyak TP, TF, FN, dan FP di data kita. Yang harus hati-hati adalah berarti jumlah pasangan di data jadi N(N-1)/2 ya Gan …. inget pelajaran kalkulus/Matematika diskrit ga dulu waktu di SD kuncup melati? … kalau ada N objek, maka jumlah pasangan yang bisa dibuat adalah sebanyak N(N-1)/2 … gitu kata bu guru waktu itu … contoh… dari 4 objek yang berbeda: {a,b,c,d} maka pasangan yang bisa dibentuk ada sebanyak 4(4-2)/2=6 , yaitu {ab,ac,ad,bc,bd,cd}. Kalau ga percaya tanya dah sama tetangga sebelah … Insya Allah jelas … bingungnya … :D … nah pasangan-pasangan {ab,ac,ad,bc,bd,cd} inilah yang akan kita tentukan apakah mereka (masing-masing) adalah TP, TF, FN, “atau” FP?
Sebelum kita masuk ke penjelasan implementasinya, tentu saja kita butuh rumusnya… ini nih, saya ambil dari bukunya suhu Christopher D. Manning, dkk:
Precision (P) , Recall (R), F-ß-Score, dan Random Index (RI).
Sedikit penjelasannya:
Precision: Lihat deh dirumusnya, P hanya menggunakan ukuran apakah hasil clustering/SSC-nya positive atau tidak. Jadi Precision bermakna ketepatan dalam pengambilan keputusan. Misal di Information Retrieval (IR), ini bermakna berapa banyak hasil search yang tepat (relevant) yang keluar di hasil query.
Recall: Kalau dilihat di rumusnya hanya ada TP dan FN lalu kalau masih ingat apa itu FN… ndak akan terlalu susah memaknai recall. Misal di IR, ini bermakna berapa banyak hasil search yang relevant yang berhasil dikeluarkan oleh hasil query.
F-ß-Score: Kalau nilai ß=1, jadi deh metric yang cukup terkenal dan banyak digunakan di paper-paper: F-1-score. Apa itu F-ß-Score? … lagi-lagi selalu kembalikan ke resepnya, eh salah maksudnya rumusnya. Kalau dilihat rumusnya jelas bahwa F-ß-Score mencoba men-scale (nimbang) antara Precision dan Recall.  Jika ß=1 maka makna F1-score menjadi balance (keseimbangan) dari nilai precision dan recall. Namun ndak dosa jika ß tidak sama dengan satu, boleh kok ß=2, yang artinya kita lebih mementingkan recall ketimbang precision dan begitu juga ß=1/2 jika menurut kita precision lebih penting. Baca keterangan lengkapnya disini.
Random Index: perhatiin deh … ada sesuatu yang “kurang” di  F-ß-Score … tau ga? … yups …  F-ß-Score sama sekali ndak memakai nilai TN. Kalau orang Statistik/Matematik pasti langsung bawel, lalu mengkaitkan dengan konsep derajat bebas dan ceramah ga napes 5 jam bilang TN ga perlu … tapi mari kita tinggalkan mereka sejenak…. :D …. Random index, “lebih adil” dengan mempertimbangkan semua kemungkinan yang ada: TP, TF, FN, & FP. Kalau kita ‘pentelengin’ rumusnya, kita akan dapatkan bahwa Random Index memiliki makna yang cukup sederhana, yaitu persentase (proporsi) keputusan yang “benar”.

Lalu bagaimana dengan Purity dan Normalized Mutual Information (NMI)?

yaaa…. ga gimana-gimana sih … biasa aja … :D …. ok deh, mari kita bahas satu-persatu … karena kalau dua-perdua juga hasilnya satu juga … #GaZeBo … :p
  1.  Purity
    Purity mengukur seberapa murni pikiran Agan,… eh salah maksudnya hasil clusteringnya. Kalau menurut bahasa planet Namek yang ditemukan di kitab kuning suhu CD Manning, begini katanya:
    Purity
    Bujug dah!!!… apaan itu ‘nya? … tenang… tenang saudara-saudara … itu belum seberapa dibandingkan NMI nanti … :D …. (siapa suruh jadi data scientist … #ketawaJahat) …. Gampang kok … N cuma jumlah data, omega (w): hasil cluster dan c-nya bermakna nilai di GT. |w∩c| maknanya jumlah (kardinalitas) data yang terkelompokkan dengan benar. Ingat ya Gan, di pelajaran Biologi kita belajar tanda “||” punya tiga makna bergantung domainnya. Kalau di dalamnya himpunan, || artinya jumlah elemen (kardinalitas himpunan), kalau di dalamnya matrix, || artinya determinan, dan kalau didalamnya skalar/angka makna tanda mutlak/absolut. Btw… bener kan ya… kita belajar gituan di Biologi? .. :D …

    Nah balik lagi ke rumus Purity, sumasi (penjumlahan) diatas cuma mau bilang itu, yaitu berapa banyak sih yang bener di kelompokkan di kelompok yang sama. dibagi N karena mau hitung rata-rata-nya. Lalu apa maksud “Maksimum j”? … ya iyalah Gan … ini deh saya kasih contoh biar lebih jelas …
    misal menurut GT ada 2 cluster : I={ayam, burung, pinguin} dan II={kuda, zebra}. Terus hasil clusternya misal: I={ayam, burung, kuda} dan II={pinguin, zebra} … Artinya di cluster I ada 2 objek yang benar dikelompokkan dan di cluster II satu yang benar. Tapi bisa juga kan kita mikirnya kebalik (karena clustering label tidak bermakna tetap): bisa juga kita mikirnya dibalik (Labelnya dibalik I <==>II), cluster II: satu yang benar (kuda), lalu di cluster I satu yang benar (pinguin). Tapi karena ini nilainya lebih kecil, kita milihnya yang lebih besar (hence, maximum j di rumus).
    Contoh lain tentu saja dari kitab kuning Pak CD Manning:
    purity_ilustration.
    Kalau belum jelas juga, coba ambil wudhu dulu deh gan … terus shalat sunnah 8 rakaat … ;) …. atau kalau mau tanya di kolom komentar dibawah juga boleh … :D … O iya, clustering yg bagus purity-nya mendekati 1, kalau yang jelek mendekati selain saya … eh salah maksudnya mendekati 0 … #usaha #udahPunyaAnak4MasihGenit … :v …
  2. Normalized Mutual Information (NMI):
    Sebelum yang normalized, kita bahas dulu yang ga normalized ya ….
    Mutual Information (MI) di referensi utama kita utama kita lambangnya I, dan katanya I sama dengan = 

    P itu cuma probabilitas Gan … (kejadian dari ruang sample/kardinalitas ruang sampel) atau gampangnya Agan mungkin ingat p=A/N. Tapi dalam hal ini “A”nya adalah kejadian apakah datanya dikelompokkan dengan benar. Lihat deh rumusnya, ada kesamaan kan dengan purity? …. Cuma summasinya jalan terhadap w dan c. Apa artinya?  Kalau purity tadi hanya mempertimbangkan benar/tidak, MI mempertimbangkan keduanya (bolak-balik). Kalau Agan pas kuliah Statistik Matematik (StatMath) ga bolos, ini terkait joint probability distribution Gan, P(w) dan P(c) independent distributionnya … baca deh disini.  Faktor log-nya mengukur seberapa besar kebergantungan hasil cluster dan GT. Mudahnya gini Gan, lagi-lagi di dasar statistik, kalau 2 kejadian independent, maka P(w∩c)=P(w)xP(c) … kalau itu terjadi maka log diatas jadi log(1) = 0. Maka nilai MI Agan jadi nol (0)  … hasil cluster Agan ama GT ga nyambung … :v .. sedih ya Gan? … gapapa cup cup cup …. Mungkin Agan pas clustering lupa pake Lem/Lakban jadi ga nyambung … :D … #kidding…

    Nah itu tadi MI, kalau mau di normalisasi kita kudu hitung Entropy, tau kan Gan Entropy? … Kayak nyasar pelajaran Kimia/Fisika ya? … Karena memang Entropy di ML/data science terinspirasi dari Entropy di Kimia Gan. Entropy disini menghitung banyaknya informasi di data. Di lain tulisan saya akan jelaskan lebih lanjut. Tapi sekarang kita bahas saja dulu rumusnya:
    Entropy GT dilambangkan H(w), nanti entropy hasil cluster dilambangkan H(C) rumusnya bersesuaian (cuma beda domain), yaitu: 

    |wk|/N maknanya jelas kan ya? jangan lupa || itu kardinalitas (jumlah elemen), jadi |wk|/N itu proporsi ukuran cluster (cluster size) terhadap jumlah data. p log(p) itu rumus umum entropy Gan. Kalau ga sabar nunggu post saya tentang hal tersebut yang ndak tau kapan terbitnya, silahkan baca keterangan lengkapnya disini.
  3. Nah… baru deh NMI bisa dihitung yang nilainya =
    Kenapa sih kita hitung NMI? … lihat balik deh di rumus Purity. kalau kita bikin hasil cluster yang “ngawur” dimana dari N data kita bentuk N cluster, maka Puritynya 1 Gan … padahal super ngawur gituh … :) … Nah, NMI menjadi penyeimbang (trade-off) agar bias ini tidak terjadi … (ciee bias… apaan tuh?…au ah … :p ) Sama seperti Purity, nilai NMI antara 0 (buruk)  dan 1 (baik).

Implementasi (Matlab & Python):

Anak jaman sekarang biasanya ga sabaran.. “Teori mulu, aplikasinya mana NIH?!!!??…” Untung saya anak jaman dulu, jadi lebih penyabar & penyayang (#Gubragh).

Implementasi Dasar (Tidak Scalable-hanya cocok untuk data yang kecil, namun mudah dipahami):

Saya capek ngetik penjelasan, lihat di komentar scriptnya aja ya … kalau ndak jelas komen dibawah. Agan bisa double click di window codenya lalu ‘CoPas’, atau unduh seluruh code dibawah di link BERIKUT.
MATLAB:
PYTHON 
Sebelum saya berikan code-nya, ada hasil penelitian dari rekan riset dari grup riset yang sama di QUT (mantan orang Microsoft) yang sudah buat Code-nya dalam Python 2 dengan import dari file hasil cluster dan GT dari file teks.
Code yang saya buat dibawah ini adalah Fork dari code tersebut. Saya adjust agar dapat digunakan di Python 3 & 2, serta input variabel yang sama dengan code Matlab diatas (lebih sederhana: List). Code ini bisa digunakan di single prosesor untuk data hingga ukuran jutaan, kalau code matlab diatas, data ratusan ribu sudah megap-megap.
Misal Code dibawah diberi nama “Clus_Eval.py” maka untuk menggunakannya, letakkan script tersebut di folder yang sama, lalu dari program Python Agan, silahkan lakukan hal berikut:
from Clus_Eval import f1_nmi
#Lalu untuk menghitung metrics yang dibahas di artikel ini:
F1,NMI,Nclus,Ngt,meanClus,sdClus,cMax,cMin = f1_nmi(gt,cid)
# Dimana cid adalah cluster label dari hasil cluster Agan, dan gt adalah ground truthnya, keduanya adalah tipe data List.
Ada extra output (kalau mau), yaitu jumlah total cluster Agan (Nclus), jumlah cluster di GT (Ngt), rata-rata size cluster Agan (meanClus), standar deviasi ukuran cluster (sdClus), ukuran cluster terbesar (cMax), dan ukuran cluster terkecil (cMin).
Kalau hanya ingin F1 dan NMI, maka perintahnya:
F1,NMI = f1_nmi(gt,cid)[0:2]

Penutup dan Disclaimer