Loci VS Centroid/Hubs: Pendekatan Baru dalam Menganalisa Data yang Besar (Big Data)

Artikel ini adalah pembahasan non-teknis dan penjelasan lebih lanjut dari artikel saya di Springer Lecture Notes in Computer Science Series tentang Clusters’ Loci dan mengapa ia adalah salah satu perkembangan penting menarik dalam dunia Big Data (Mining).  Accepted version dari papernya dapat diunduh di link green open access QUT ePrint berikut (Link).
Pertama-tama kita mulai dengan hal yang unik/baru dari paper diatas (Novelty) dan mengapa ia penting untuk perkembangan analisa big data (signifikansi):

  1. Analisa data mining (science) untuk data yang besar biasanya dilakukan dengan membangun suatu sistem terdistribusi khusus (e.g. Hadoop, Map Reduce, & Mahout). Namun dunia industri (terutama skala kecil-menengah) secara umum tidak begitu suka dengan pendekatan Big Data yang ada sekarang ini. Mengapa? Karena membangun infrastrukturnya tidaklah murah (walau dengan cloud technology sekalipun). Selain itu, dikarenakan tingkat kesulitan dan sulitnya akses pendidikan ke infrastruktur big data yang mahal ini, human resources/ahli yang menguasai bidang ini juga cenderung masih sangat sedikit (bahkan di negara maju). Di sisi lain, sebenarnya Big Data bukanlah ‘barang baru‘. Ia saat ini ramai dibicarakan (teliti & aplikasikan) untuk keperluan analisa data. Namun sebenarnya data yang berukuran sangat besar sudah lama dapat diproses dengan baik oleh sistem retrieval (e.g. search engine). Mudahnya kita bisa saksikan melalui kesuksesan Google, Facebook, atau twitter dalam mengolah data yang sangat besar dan secara konstan terus membesar.Metode yang saya ajukan di paper di atas diberi nama Loci based Semi-supervised Document Clustering (LSDC). Perbedaan paling utama dari metode tersebut adalah penggunaan teknologi Information retrieval (IR)/search engine dalam membantu meng-efisienkan komputasi. Pada dasarnya ia memanfaatkan struktur data khusus search engine yang disebut inverted index untuk menghindari membandingkan (scan) seluruh dokumen yang ada ketika hendak mengelompokkan suatu dokumen tertentu. Gambar 1 merupakan ilustrasi perbedaan pendekatan LSDC dan metode (big) data mining lainnya. Mengapa pendekatan ini saya katakan lebih murah dan mudah? Karena saat ini tools search engine tersedia cukup banyak & dengan license yang bersahabat, belum lagi mengatur “scalability” sistem IR jauh lebih mudah (ketika datanya membesar). Analisa akhir yang dilakukan juga menggunakan metode konvensional biasa yang relatif mudah karena ‘well established‘.
    IR-Data-Mining

    Gambar 1. Pendekatan baru dalam menganalisa data yang besar.

  2. Kebanyakan penelitian di Big Data fokus pada pemrosesan paralel dan-atau data yang terdistribusi. Sebagian yang lain mengajukan suatu metode sampling atau aproksimasi pada teorinya. Tidak banyak penelitian yang benar-benar melihat perbedaan suatu sifat Geometris/Statistik/Matematik dari data yang besar. Pada data yang relatif kecil dan berdimensi tinggi (jumlah variabel yang banyak), terkenal suatu permasalahan yang biasa di sebut sebagai  ‘curse of high dimensionality‘. Namun menariknya ternyata pada data yang besar, ada suatu sifat tertentu pada data berdimensi tinggi yang dapat dimanfaatkan: yaitu mereka cenderung untuk mengelompok (secara teknis: berkumpul dalam suatu k-nearest neighbour). Pengelompokkan ini biasa disebut sebagai cluster Hubness. Terdapat beberapa paper (hasil penelitian) yang menjelaskan bahwa algoritma clustering yang memanfaatkan Hubness ini lebih akurat dibandingkan unsupervised clustering lain pada umumnya. Namun sayangnya kompleksitas algoritmanya tinggi [O(N3)], sehingga mustahil di aplikasikan di data yang besar.LSDC memanfaatkan sifat Hubness, namun dengan 2 perbedaan mendasar: Pertama LSDC menggunakan Locus (jamak=Loci) dan bukan murni hubs. Apa itu Locus? di BioInformatika Locus adalah lokasi gen penting dalam suatu kromosom, di big data (mining) Lokus didefinisikan sebagai sub-himpunan dokumen-dokumen terpenting (relevance) dalam suatu cluster terhadap dokumen yang akan dikelompokkan. Perbedaan Kedua adalah Locus di cluster ini dapat dibayangkan sebagai proyeksi Hubs di dimensi rendah dan bersifat dinamis. Mengapa dinamis? Karena tidak seperti Hubs/centroid yang merupakan representasi statis suatu cluster, Locus adalah representasi cluster spesifik terhadap dokumen tertentu, artinya locus suatu cluster tertentu akan berbeda untuk dokumen yang berbeda pula. Supaya lebih jelas perbedaan clustering dengan centroid dan Hubs saya berikan perbandingannya pada Gambar 2.
    Comparisons of Centroids, Hubs, and Loci

    Gambar 2. Comparisons of Centroids, Hubs, and Loci in clustering.

Mengapa LSDC cocok untuk data yang besar ?

  • Tidak seperti metode/algoritma cluster yang lain (e.g. K-Means) LSDC tidak memerlukan input K (jumlah cluster) sebagai inputnya. LSDC akan menentukan sendiri total cluster seluruhnya saat clustering dilakukan. Pada data yang kecil K dapat ditentukan dengan cara ‘coba-coba‘ (Elbow Method/Silhoutte), namun di data yang besar hal ini tidak mungkin untuk dilakukan.
  • LSDC incremental dan mendukung topic/concept drift. Apa artinya?  Ia dapat menentukan suatu dokumen dapat dikelompokkan pada cluster yang baru yang tidak ada pada hasil pengelompokkan pada iterasi-iterasi sebelumnya. Sehingga LSDC dapat digunakan secara real-time walau datanya terus membesar.
  • Kompleksitas LSDC linear dan tidak dipengaruhi oleh banyaknya cluster intrinsic dalam data. Loh kok bisa? Mustahil? No …. Hal ini  memungkinkan karena penggunaan inverted index search engine. LSDC memang membutuhkan preprocessing yang lebih dibanding metode lain (untuk meng-ekstrak query dan mengindex data), namun proses ini “embarassingly parallel” (dapat dijalankan secara parallel dan independent) sebelum analisa (clustering) dilakukan.
  • “Akurasi” LSDC on-par bahkan dengan metode clustering “batch” [tidak incremental]. Selain hasil yang dilaporkan di paper, saya membuat visualisasi untuk memberi gambaran akurasi hasil LSDC (Gambar 3).
  • LSDC mendukung multi-modal data, apa artinya? …. Karena similarity (jarak) dihitung dengan perbandingan vektor sederhana, maka kombinasi Tipe Data (teks, time, & space) seperti di metode CICR dapat dilakukan. Maksudnya? Artinya informasi non-teks dapat dengan mudah dimasukkan dalam algoritmanya: seperti tanggal, lokasi dokumen dibuat, dsb.
Visualisasi_LSDC

Gambar 3. Bagian atas adalah visualisasi “Ground truth” cluster, bagian bawah adalah hasil LSDC. Visualisasi dibuat menggunakan t-SNE (kanan) dan ukuran relatif cluster (kiri).

Batasan metode: Tentu saja tidak ada yang namanya “obat dewa” atau dengan kata lain tidak ada metode yang sempurna. LSDC akan memiliki hasil yang baik bila ‘cluster hypothesis‘ di information retrieval-nya  dipenuhi dengan baik. Pada paper ini clusteringnya juga masih semi-supervised dan dibatasi oleh data tidak (semi) terstruktur (teks/dokumen).

Penutup & Penelitian Lebih lanjut:

Di artikel ini dipaparkan suatu pendekatan baru yang unik dalam menganalisa data yang besar.  Dengan memanfaatkan kemampuan sistem IR, analisa clustering data yang besar dapat dilakukan dengan relatif lebih murah, mudah dan cepat, tanpa mengorbankan akurasi. Saat ini saya sedang menyiapkan publikasi untuk pengembangan metode ini di kasus unsupervised. Lebih jauh lagi pengembangan metode ini untuk sistem yang parallel dan terdistribusi juga memungkinkan. Cukup banyak pengembangan lain yang bisa dilakukan, diantaranya adalah generalisasi ke data non teks dan model data mining lainnya seperti klasifikasi dan rekomendasi.

Semoga bermanfaat,

</TES>® Bne, 02112015

5 thoughts on “Loci VS Centroid/Hubs: Pendekatan Baru dalam Menganalisa Data yang Besar (Big Data)

  1. Artikel yang bagus, tapi penjelasannya terlalu basa-basi, tidak langsung pada pointnya, terkesan enggan untuk menuju point atau memang begitu style penulis. Tidak ada yang baru inverted index metode standar pada IR, sedangkan penentuan jumlah cluster sudah ada algoritma EM (expectation-maximation), contoh ada pada weka untuk clustering. Jadi menurut saya, artikel ini semacam tambal sulam saja, atau comot metode yang ada di metode x dan y ditambahkan pada metode f bagian p dan k, belom cukup untuk dapat dikatakan sebuah kontribusi. CMIIW, Salam kenal Pak.

    • Terima kasih atas kritiknya … ^_^ … inverted index memang tidak baru Pak. Inti metode yang di propose adalah menggunakan tree ala CF-tree-nya BIRCH dan cluster hubness di dimensi yang tinggi. Detailnya bisa dibaca di papernya, saya bisa kirim kalau Bapak mau. Main feature dari metode clustering di paper tersebut performance. Menggunakan EM untuk jutaan record dan ratusan ribu dimensi nyaris mustahil (mungkin dgn super-super-super komputer). Setau saya baru kali ini ada metode analytics yang menggunakan IR system untuk mempercepat komputasi metode machine learning (statistik/data mining). Mohon koreksinya dengan menunjukkan paper yang pernah melakukan hal tersebut.

      Saya baru belajar menulis Pak, mungkin kalau Bapak menunjukkan paper-paper atau buku-buku yang pernah Bapak tulis (misal link Google Scholar/Scopus Author profile), saya bisa belajar dari Bapak … Terima kasih atas bimbingannya … Salam kenal juga Pak :)

  2. Pingback: Model-Model Statistika / Data Science | Taufik Sutanto

Leave a Reply