Fast Cosine Dissimilarity for Sparse (CSR) Vectors in High-Dimensional Data

Big-Data Scientist bukanlah seorang programmer, ia mungkin tidak memiliki kemampuan untuk membuat software sehandal para programer sejati. Namun tuntutan profesi menuntut mereka untuk mampu membuat High Performance Codes/program. Data scientist (DS) adalah ‘speed freak‘, yang ndak pernah puas kalau tidak bisa mengaplikasikan model statistika/matematika dengan performa yang optimal sesuai dengan teori.

Salah satu hal yang amat menjengkelkan bagi DS adalah jika code/tools yang digunakan tidak memiliki performa sesuai dengan teorinya (kompleksitas algoritma) #CurCol … ^_^ … Dihadapi dengan masalah ini DS akan mempelajari baris-perbaris dan mengamati setiap struktur data yang digunakan untuk menemukan si ‘culprit‘. Akhir² ini saya menemukan salah satu penyebab menurunnya performa komputasi di salah satu penelitian saya. Temuan tersebut saya share di artikel ini: “Cosine Scipy Spatial Distance (SSD) lambat dan boros memory untuk data besar dan berdimensi tinggi”

Di artikel ini saya akan mengajukan fungsi yang lebih baik (lebih cepat & lebih hemat memory) dan melakukan benchmark untuk menunjukkan secara empiris bahwa fungsi tersebut memang lebih baik dari fungsi standar yang sering digunakan banyak orang: SSD. Lebih jauh lagi, ketika data dan dimensi semakin besar/tinggi maka akan ditunjukan fungsi yang saya ajukan akan semakin lebih efisien dibanding SSD.

Pendahuluan Cosine Similarity/Disimilarity

Seperti biasa mari kita awali dengan sedikit teori. Sedikit mengulas balik dan mengingat kembali, rumus cosine yang sering di gunakan di text mining/text analytic. Seperti yang pernah saya sampaikan di artikel sebelumnya, saya mau menyatakan kembali bahwa cosine “bukanlah rumus jarak/distance/metric”. Karena untuk dikatakan sebagai jarak (metric di topology-Matematika) ia harus memenuhi tiga syarat: non negative, symmetric, dan pertidaksamaan segitiga. Cosine tidak memenuhi sifat ketiga, sehingga cosine bukanlah ukuran jarak, tapi lebih cocok disebut sebagai ukuran similarity/dissimilarity.

Similarity/dissimilarity?… Maksudnya? Mana yang sebaiknya dipilih?

Mengenal si Cosine:

Kesalahan umum kedua terhadap rumus cosine adalah menerapkan similarity cosine pada kasus dimana ia seharusnya menggunakan dissimilarity. Apa bedanya?  Secara formulasi bedanya tipis (hanya “1-…”) :

Namun maknawinya berbeda 180° (akan dijelaskan nanti di bawah). Range dari rumus cosine awalnya adalah -1≤cos(Θ)≤1, tapi pada kasus text mining/text analytics karena domainnya biasanya tidak negatif (misal tf, tfidf, bm25, dll) maka range cosine berubah menjadi 0≤cos(Θ)≤1.

Makna/Arti/Interpretasi:

Waktu di TK Kuncup Melati Berseri-Seri kita pernah belajar, cos(Θ=0)=1 dan cos(Θ=90°)=0, ilustrasinya seperti ini:

Kalau A adalah sebuah vektor yang mewakili sebuah objek/entitas (misal dokumen/tweet/status pada model VSM-vector Space Model) dan B adalah objek lain, maka jelas jika kedua objek semakin mirip maka sudutnya semakin kecil (kedua garis semakin berdekatan/berhimpit). Artinya nilai Θ semakin mendekati nol (0), sehingga cos(Θ) akan semakin mendekati 1. Tapi hati-hati, interpretasi ini menggunakan rumus awal Cosine (similarity).

Lalu yang sebaiknya digunakan di data science (data mining/statistik/machine learning) similarity atau dissimilarity? … sebenarnya bisa digunakan 2-2nya.. tapiiii… secara umum sebaiknya dissimilarity, karena dissimilarity ‘lebih dekat‘ dengan konsep jarak. Sehingga model Matematis/Statistik yang digunakan beserta model optimasi didalamnya tidak perlu dirubah. Misal optimasi di model k-means:

Perhatikan di optimasi tersebut ingin me-minimum-kan ‘jarak‘ antara objek (x) dengan pusat cluster (µ).  Maka seyogyanya dissimilarity yang digunakan. Mengapa? Karena optimasi diatas dicari dengan membuat keputusan dengan mencari objek-objek yang paling dekat dengan pusat cluster dengan mencari nilai minimumnya (berarti jarak~dissimilarity). Menggunakan dissimilarity juga menguntungkan karena jika Cosine ingin diganti dengan jarak lain seperti Euclid, Hamming, dll maka programnya tidak perlu dirubah sama sekali (selain fungsi jaraknya).

Banyak programer memilih similarity ketimbang dissimilarity karena komputasinya berkurang sedikit (satu flop: floating point operation). Tapi efisiensi ini ‘super-sangat-tidak signifikan-sekali’ ketimbang musibah akibat optimasi dan logika yang harus disesuaikan di seluruh program. Belum kerepotan kalau fungsi jarak akan dirubah… wuidih, pokoknya musibah deh …  :) Karena alasan ini juga maka SciPy (dan most statistik/data mining softwares) menggunakan dissimilarity ketimbang similarity: http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.spatial.distance.cosine.html

Python, Sparse, dan Cosine Dissimilarity: Permasalahan

Bagi mereka yang biasa mengolah data besar, terutama data teks, data yang besar dan berdimensi tinggi adalah makanan sehari-hari. Untuk data seperti ini representasi yang paling sering digunakan adalah struktur data ‘Sparse‘ (untuk yang belum familiar dengan matriks sparse silahkan baca “disini“).  Sparse memungkinkan untuk penyimpanan dan pengolahan yang jauh lebih efisien ketimbang bentuk matriks biasa (dense). Hal ini dikarenakan mayoritas elemen matriks sparse (nol=0) tidak disimpan secara eksplisit.

Namun sayangnya sparse butuh fungsi khusus untuk dapat dioperasikan dalam sebuah fungsi. Untuk dissimilarity cosine di Python, salah satu fungsi yang paling umum dan banyak digunakan adalah Scipy Spatial Distance (SSD). Sayangnya setelah saya coba untuk data yang besar, SSD tidak efisien karena karena domain fungsinya dense(numpy array), sehingga untuk menghitung dissimilarity antar 2 vektor harus dirubah ke bentuk dense-nya terlebih dahulu (boros memory), lalu dilakukan perhitungan (atas seluruh elemen, termasuk mayoritas nol). Akibatnya komputasi-pun menjadi tidak efisien juga. Walau Scipy telah dioptimasi dengan BLAS, namun seperti yang akan ditunjukkan dibawah, SSD tetap bermasalah untuk data besar berdimensi tinggi.

Solusi (Proposed Cosine Dissimilarity Function)

Matriks CSR Scipy punya beberapa properties yang tidak didokumentasi di manualnya
http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csr_matrix.html
Jika A adalah matriks/vektor CSR, maka A memiliki 3 properties berikut yang bisa kita manfaatkan:
row = A.indptr   # ==> index baris, numpy array
col  = A.indices # ==> index kolom (non-zero), numpy array
data = A.data # ==> index data (non-zero), numpy array

Menggunakan undocumented properties ini, kita bisa membuat fungsi dissimilarity cosine yang efisien, sebagai berikut (silahkan double-click codenya kalau mau “Copy-Paste”):

1 2 3 4 5 6 7 8 9 10 11 12

import numpy as np def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity     uData = u.data; vData = v.data     denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2))     if denominator>0:         uCol = u.indices; vCol = v.indices # np array         intersection = set(np.intersect1d(uCol,vCol))         uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection])         vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])                     return float(1-(np.dot(uI,vI)/denominator))     else:         return float("inf")

Update!!!…

Saya bertanya di StackOverFlow, “UnutBu” punya versi yang lebih cepat. Sekitar 3x lebih cepat dari fungsi diatas, berarti >210x lebih cepat dari SSD untuk data berdimensi tinggi. Berikut versi beliau:

1 2 3 4 5 6 7 8 9 10

def alt_fCosine(u,v):     uData, vData = u.data, v.data     denominator = math.sqrt(np.sum(uData**2) * np.sum(vData**2))     if denominator>0:         uCol, vCol = u.indices, v.indices         uI = uData[np.in1d(uCol, vCol)]         vI = vData[np.in1d(vCol, uCol)]         return 1-np.dot(uI,vI)/denominator     else:         return float("inf")

Experiment Settings:

Berikut ini adalah code untuk Benchmark antara fCosine dan SSD. Yang akan diukur adalah waktu dan penggunaan memory. Saya menggunakan cluster computer (HPC) dengan platform Linux, saya gunakan memory report setelah PBS job selesai (untuk masing-masing fungsi)). Sebagai validasi sederhana, rata-rata hasil perhitungan juga dikeluarkan sebagai output.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

import time, scipy.spatial.distance,numpy as np from sklearn.datasets import load_svmlight_file SSD = getattr(scipy.spatial.distance,'cosine') # The SSD Dissimilarity Function fVsm = '' # path to VSM # def fCosine(u,v): # Seperti diatas ↑ copas kesini kalau mau benchmark sendiri def Test(vsm,N,func):         hasil = 0.0 # digunakan untuk validasi sederhana hasil perhitungan     if func == 'SSD':         waktu = time.time()         for i in range(N-1):             hasil+=SSD(vsm[i].toarray(),vsm[i+1].toarray()) # Perhatikan SSD wajib pindah ke dense vector     else:         waktu = time.time()         for i in range(N-1):             hasil+=fCosine(vsm[i],vsm[i+1]) # Tidak perlu pindah ke dense vector, tetap Sparse!     waktu = time.time() - waktu     hasil = hasil/(N-1) # Hitung rata-rata jarak         return waktu, hasil if __name__ == "__main__":     vsm = load_svmlight_file(fVsm)[0] # load only the vectors not the class/labels     N,L = vsm.get_shape() # Banyaknya instances = baris di data = N, L = banyak variable/dimensi data     print ('Data size = {0} x {1}, density = {2}'.format(N,L,vsm.nnz/(N*L)))          t1,res1 = Test(vsm,N,'SSD')     t2,res2 = Test(vsm,N,'fCosine')     print ('waktu SSD = {0}, hasil = {1}'.format(t1,res1))     print ('waktu fCos = {0}, hasil = {1}'.format(t2,res2))

Data yang digunakan dan property-nya adalah sebagai berikut:

Hasil Eksperimen:

Perhatikan, grafik diatas menggunakan data yang saya transformasi dengan fungsi logaritma. Tujuannya agar discrepancy/perbedaan akibat ukuran skala data yang jauh berbeda bisa di minimalisir. Namun untuk melihat perbedaan sesungguhnya (di input space) silahkan lihat hasil di tabel.

Penutup

• fCosine lebih cepat hingga lebih dari 77x ketimbang SSD (~55 menit VS >3hari 3 malam!!!…) dan menggunakan memory yang lebih efisien. Catatan penting disini, sebenarnya pada percobaan data Wikipedia, prosesnya lebih dari 72 jam (259 200 detik), namun karena di PBS saya submit job dengan time limit tersebut, maka prosesnya terhenti (walau belum selesai: time limit excess). Artinya sebenarnya di data Wikipedia SSD butuh waktu lebih dari yang tertera di tabel.
• fCosine nampak lebih cepat & efisien terutama pada data yang lebih besar dan berdimensi tinggi. Di penelitian, saya menggunakan data yang jauh lebih besar & berdimensi lebih tinggi ketimbang Wikipedia/Medline, efek fCosine sangat nyata. Beda waktu bisa hitungan berhari-hari per-processor! (untuk proses distributed & paralel data mining).
• Hikmah : Hanya karena suatu modul terkenal dan banyak dipakai orang, bukan berarti ia state-of-the-art atau de facto. Setidaknya jika anda seorang peneliti/researcher, perlu berfikir kritis dan menelaah lebih jauh terhadap modul² yang digunakan. Bagi kaum profesional/pebisnis, mungkin cukup dengan mencoba untuk selalu up-to-date terhadap hasil penelitian terkini para akademisi.
• fCosine masih bisa di optimasi lebih jauh dengan JIT atau CyThon. Tapi hati-hati JIT tidak mau ada ‘list of list’, ‘list to array’, & list comprehension. Jadi kalau mau di-JIT fungsi diatas harus ditulis ulang. Kalau ada yang mau share versi JIT/CyThon dari fungsi diatas saya akan sangat berterima kasih & saya yakin akan bermanfaat bagi banyak orang (terutama para data scientist di Indonesia atau dunia umumnya).
• Fungsi fCosine diatas juga bisa dimodifikasi untuk matriks COO (coordinate). Namun hati-hati di matriks COO, property “A.indices” berubah menjadi “A.col”. Perlu diperhatikan juga, tidak seperti di CSR,  di matriks COO, elemen “kolom” tidak unik! … #IlearntThisTheHardWay … :D …
• Seperti biasa no CoPas artikel ya, pamali … :) … Tapi silahkan manfaatkan (CoPas) tools-tools/codes yang ada di sutanto.org. Semoga bermanfaat untuk membantu pengembangan ilmu dan pengaplikasian data mining/data science di Indonesia.

Cheers,
< / TES >^® ~ BNE 27/03/2016,22:02:06