PENGUKURAN KEMAMPUAN PREDIKTIF TEKNIK CLUSTERING DENGAN FIGURE OF MERIT 1 Rosni Lumbantoruan Politeknik Informatika Del Jl. Sisingamangaraja Sitoluama, Laguboti Toba Samosir, Sumatera Utara, Indonesia 22381 Email :
[email protected] Abstract In the recent few decades, molecular biology as well as the gene data grows fast. The present of microarray technology can produce a huge of gene expression data in just once experiment. For the fast growing of gene data, there is a need for analyzing data and finding the information hidden in the data. One technique to analyze microarray data is by using clustering. In this paper, we proposed a software module for clustering microarray data and measuring the predictive power of the clustering algorithm. Clustering algorithms used are Hierarchical Clustering (HC), K-Means with K-Means and KMedoids method, and Self Organizing Map (SOM). The result of the clustering microarray data is used as the input for measuring the predictive power of the algorithm by using statistical approach, Figure Of Merit (FOM). The index result of applying FOM can be used as a reference to choose the proper algorithm for clustering certain microarray data. We have found that by applying FOM to budding yeast data Saccharomyces cerevisiae, K-Means with K-Median method superiors K-Means method and SOM. Keywords: Clustering, Microarray, Hierarchical Clustering, K-Means, Self Organizing Map, Figure of Merit. Abstrak Dalam beberapa dekade terakhir ini, ilmu biologi terutama bidang molekuler semakin berkembang pesat. Terlebih lagi dengan munculnya teknologi microarray yang mampu menghasilkan data ekspresi gen yang sangat besar hanya dalam sekali eksperimen. Seiring dengan semakin banyaknya data, terutama data yang dihasilkan dari teknologi microarray maka muncul kebutuhan untuk menganalisis data, untuk mencari informasi yang terkandung pada data tersebut. Salah satu teknik untuk menganalisis data microarray adalah dengan teknik clustering. Banyak algoritma clustering yang tersedia untuk menganalisis data ekspresi gen, namun hanya sedikit petunjuk tentang tingkat kemampuan prediktif algoritma. Modul perangkat lunak ini menawarkan solusi terhadap permasalahan tersebut dengan mengaplikasikan Figure Of Merit, yang dapat mengukur kemampuan prediktif algoritma clustering. Data yang digunakan untuk teknik clustering dan pengukuran kemampuan prediktif algoritma adalah data sel ragi / Shaccaromyces Cereviciae. Berdasarkan penghitungan indeks nilai kemampuan prediktif algoritma, diperoleh bahwa K-Means dengan metoda K-Median mempunyai kemampuan prediktif yang lebih tinggi dalam meng-cluster data sel ragi dibandingkan dengan kedua algoritma lainnya. Kata Kunci : Clustering, Microarray, Hierarchical Clustering, K-Means, Self Organizing Map, Figure of Merit. 1
Makalah ini disarikan dari Tugas Akhir Strata 1 di Institut Teknologi Bandung, di bawah bimbingan Ibu Dr. ir. M.M. Inggriani Liem dan Bapak Dr. Adi Pancoro. Pada kesempatan ini, penulis juga mengucapkan terima kasih kepada pihak penyelenggara Seminar Nasional "Conference on Applied Information Technology (CAIT)" yang memberi kesempatan kepada penulis untuk menyampaikan hasil kajian kepada peserta seminar.
1
PENDAHULUAN Dalam dekade terakhir, disiplin ilmu biologi mengalami perkembangan pesat terutama di tingkat molekuler. Berbagai teknologi baru telah dikembangkan untuk mendapatkan informasi mengenai gen yaitu satuan terkecil dari makhluk hidup. Banyaknya penelitian yang dilakukan telah menghasilkan data dan informasi biologi dalam jumlah yang sangat besar. Dengan semakin banyak dan kompleksnya informasi yang dihasilkan, diperlukan pendekatan baru untuk memahami fenomena makhluk hidup. Dalam hal ini, pendekatan teknologi informasi sangat dibutuhkan dalam pengelolaan dan pengolahan data biologi terutama dalam hal penyediaan berbagai kakas perangkat lunak untuk membantu analisis data [1]. Munculnya teknologi microarray DNA memungkinkan untuk memonitor ribuan level ekspresi gen secara bersamaan. Hasil dari microarray adalah sebuah matriks dengan baris yang berasosiasi dengan setiap gen dan kolom yang berasosiasi dengan sampel/kondisi. Setiap elemen matriks menunjukkan level ekspresi gen tertentu pada sampel/kondisi tertentu. Salah satu bentuk data microarray adalah time-series microarray yang menyatakan hasil pengukuran terhadap sampel gen secara terurut berdasarkan waktu pengamatan [2]. Salah satu informasi yang diperoleh dengan memonitor level ekspresi gen dalam tahap perkembangan yang berbeda, kondisi kesehatan, dan organisme yang berbeda dapat membantu memahami fungsi gen dan jaringannya, membantu melakukan diagnosis penyakit, dan mengetahui pengaruh dari pengobatan medis. Namun, jumlah data microarray yang sangat besar memunculkan tantangan baru untuk analisis ekspresi gen. Langkah utama dalam analisis data ekspresi gen adalah mengidentifikasi kelompok gen yang mempunyai pola ekspresi yang sama. Salah satu cara yang paling umum dilakukan untuk menganalisis data hasil microarray adalah dengan teknik clustering [3,4]. Terdapat banyak algoritma clustering, diantaranya Hierarchical Clustering [5], K-Means [6], dan Self Organizing Maps [7]. Hierarchical Clustering (HC) mengelompokkan data dalam struktur hierarki, K-Means membagi data menjadi k-jumlah cluster, sedangkan SOM membagi data ke dalam k-partisi. Algoritma-algoritma ini sudah banyak diimplementasikan dan merupakan aplikasi open source [8]. Manfaat dari implementasi beberapa algoritma dalam satu aplikasi berguna dalam penelitian. Peneliti dapat menggunakan beberapa metoda cluster, misalnya menggunakan algoritma hierarchical untuk memprediksikan jumlah cluster yang terbaik yang harus dihasilkan. Dari hasil ini kemudian digunakan algoritma K-Means untuk mendapatkan cluster akhir. Setelah cluster diperoleh, kemudian dapat dilanjutkan dengan proses visualisasi. Banyak algoritma clustering yang tersedia untuk menganalisis data ekspresi gen, namun hanya sedikit petunjuk tentang tingkat kemampuan prediktif algoritma. Misalnya perangkat lunak yang dikembangkan oleh Eisen [8], menerapkan algoritma HC, K-Means, SOM, dan Principal component analysis;namun perangkat lunak ini hanya meng-cluster-kan data gen dan tidak mengukur kualitas dari algoritma yang digunakan. Pilihan untuk memilih hasil clustering yang tepat diserahkan kepada pengguna perangkat lunak. Begitu juga dengan CLICK and EXPANDER[9], sistem untuk clustering dan visualisasi data ekspresi gen. Sistem ini menggunakan algoritma CLICK untuk menghasilkan cluster yang memiliki tingkat kesamaan yang tinggi. Selain itu, sistem ini menyediakan alat untuk memvisualisasikan analisis data ekspresi gen dengan menggunakan EXPANDER, namun sistem ini tidak menyediakan fasilitas untuk mengukur tingkat keakuratan cluster yang dihasilkan. Dengan mempertimbangkan kurangnya petunjuk untuk mengukur tingkat keakuratan/kemampuan prediktif algoritma, modul perangkat lunak ini menawarkan solusi untuk pengukuran tingkat kemampuan prediktif algoritma dengan mengaplikasikan Figure Of Merit (FOM). FOM menggunakan hasil clustering sebagai masukan untuk mengukur kemampuan prediktif algoritma. Hasil perhitungan Figure Of Merit divisualisasikan dalam bentuk grafik.
2
METODA/PRODUK TERDAHULU YANG AKAN DIKEMBANGKAN Terdapat banyak algoritma clustering dan sudah banyak diimplementasikan. Salah satu perangkat lunak yang dijadikan sebagai acuan adalah perangkat lunak yang dikembangkan oleh Eisen [8] dan tersedia secara open source. Perangkat lunak ini mengimplementasikan tiga algoritma clustering yaitu HC, K-Means, dan SOM. Perangkat lunak dibangun dengan menggunakan bahasa pemrograman C++. Banyak perangkat lunak yang mengaplikasikan teknik clustering, namun masih jarang ditemukan perangkat lunak yang memberikan informasi tentang pemilihan algoritma yang paling tepat digunakan. Begitu juga dengan perangkat lunak yang dikembangkan oleh Eisen. Permasalahan ini menjadi pertimbangan untuk mengembangkan perangkat lunak yang sudah ada dengan menambahkan fungsi pengukuran kemampuan prediktif algoritma. Kemampuan prediktif algoritma dapat dijadikan sebagai referensi oleh pengguna untuk memilih algoritma yang akan digunakan.
3
METODA PENELITIAN Modul perangkat lunak yang dibangun ditujukan untuk melakukan clustering terhadap data genetik microarray serta mengukur kemampuan prediktif algoritma. Data microarray yang digunakan untuk melakukan penelitian adalah data sel ragi yang tersedia secara publik. Modul perangkat lunak mengaplikasikan tiga jenis algoritma clustering yaitu Hierarchical Clustering (HC), K-Means, dan Self Organizing Map (SOM). Sebelum melakukan clustering, dilakukan proses normalisasi untuk menghindari pengaruh pemilihan metriks jarak yang digunakan pada algoritma clustering. Hasil clustering akan dijadikan sebagai masukan untuk penghitungan tingkat kemampuan prediktif algoritma clustering yang digunakan dengan mengaplikasikan Figure Of Merit (FOM). Penjelasan tentang metoda penelitian yang digunakan akan dijelaskan pada subbab-subbab berikut.
3.1
Data Microarray Keluaran dari microarray DNA adalah matriks dengan baris yang berasosiasi dengan gen, dan baris pada matriks yang berasosiasi dengan kondisi/profil level ekspresi gen. Level ekspresi gen dapat berupa nilai absolut atau relatif. Setiap baris merepresentasikan pola ekspresi gen. Setiap kolom merepresentasikan eksperimen/ profil kondisi. Masukan pada raw data matrix adalah nilai rasio, absolut, atau nilai distribusi. Data ekspresi gen dapat direpresentasikan sebagai matriks, yang disebut dengan raw data matrix. Setiap baris pada matriks berisi data untuk gen tertentu, dan setiap kolom merepresentasikan sebuah kondisi. Dengan demikian, Rij adalah level ekspresi untuk gen i, pada kondisi j. data ekspresi gen dapat direpresentasikan dalam bentuk rasio, nilai absolute, atau nilai distribusi. Pola ekspresi dari gen i adalah baris ke i dari Rij. Pola ekspresi kondisi j adalah kolom ke j dari Rij. Pada beberapa algoritma clustering, raw data matrix diproses terlebih dahulu untuk menghasilkan sebuah matriks similarity [seperti pada gambar 3-1], dengan Sij merefleksikan kesamaan pola ekspresi dari gen i dan gen j. Matriks similarity lebih besar dari raw data matrix karena biasanya gen lebih banyak daripada kondisi (kolom) [2].
Gambar 3-1 Pembentukan Raw Data Matrix menjadi Similarity Matrix [2] 3.2
Representasi Data Clustering Algoritma clustering mengelompokkan objek atau data berdasarkan indeks kedekatan antara pasangan objek. Kumpulan objek yang merupakan raw data untuk clustering dapat dinyatakan dengan 2 (dua) format standar yaitu: pattern matrix dan proximity matrix. Data microarray pada umumnya sudah direpresentasikan dalam bentuk pattern matrix, seperti dibahas pada subbab 3.2.1. Penjelasan tentang pattern matrix dan proximity matrix, lebih jelasnya akan dibahas pada subbab-subbab sebagai berikut [10].
3.2.1
Pattern Matrix Apabila setiap objek pada himpunan n objek (gen) direpresentasikan oleh sebanyak d jenis pengukuran/sampel, setiap objek direpresentasikan dengan sebuah pattern. Himpunan dipandang sebagai n x d pattern matrix. Setiap baris pada matriks mendefinisikan sebuah pattern dan setiap kolom menyatakan feature, atau pengukuran. Misalnya, untuk melakukan cluster terhadap fungsi waktu seperti sinyal biologi, nilai sampel yang diperoleh pada waktu tertentu adalah feature. Himpunan nilai feature dari sebuah sinyal adalah pattern, diharapkan feature yang sama digunakan untuk mengukur semua pola. Misalkan dilakukan cluster terhadap pasien pada suatu rumah sakit, maka setiap baris pada pattern matrix akan merepresentasikan satu individu. Feature atau kolom pada pattern matrix, akan merepresentasikan respon terhadap jawaban pada formulir masuk rumah sakit atau hasil diagnosis. Pertanyaan dan tes diagnosis harus sama untuk setiap pasien untuk eksprerimen tertentu. Informasi yang bersifat kategorikal seperti usia, jenis kelamin, agama, atau warna rambut, biasanya diterjemahkan sebagai hasil dari analisis clustering, bukan bagian dari pattern matrix. Pattern matrix dapat digambarkan sebagai kumpulan objek pada baris dan atribut pada kolom seperti Gambar 3.2 sebagai berikut [11].
Gambar 3-2 Format Data Clustering Baris merupakan objek yang diamati, pada Gambar 3-2 adalah 1, 2, …, n. sedangkan atribut dinyatakan dalam kolom 1, 2, …m. Nilai pada matriks, misalnya 4.7 untuk objek 1 dan atribut 1 adalah hasil pengukuran berupa level ekspresi pengamatan. Pada umumnya, objek dapat berupa gen maupun sampel. Sampel pada pattern matrix bisa merupakan pengamatan terhadap waktu (time points), pengamatan terhadap sekelompok gen (tissue types), dan pengamatan selama dilakukan treatment tertentu. Jenis-jenis data microarray berdasarkan sampel pengamatan yang digunakan untuk proses clustering adalah time series microarray, tissue types microarray, dan treatment condition microarray [11].
Time series microarray
Gambar 3-3 Pola data time series microarray Pola pada Gambar 3-3 merupakan pengamatan terhadap n gen dan m lama waktu sebagai atribut. Pola ini dikenal sebagai time series microarray. Data microarray yang digunakan dibatasi hanya time series micrroarray, yaitu sampel berupa hasil pengamatan level ekspresi gen pada perioda tertentu. Format data sampel yang digunakan adalah tab-delimited text. Dalam hal ini sampel dalam bentuk matriks, dengan baris berasosiasi dengan gen, dan kolom berasosiasi dengan kondisi atau waktu pengamatan. Setiap elemen xnm pada matriks X merepresentasikan level ekspresi gen n pada sampel m. Baris pertama pada matrix X berisi nama atribut yang terdiri dari nama gen dan label identifikasi setiap sampel yang tersedia. Berikut adalah contoh data microarray yang diambil dari hasil eksperimen terhadap sekumpulan gen saccharomyces cerevisiae pada suatu perioda tertentu.
Gambar 3-4 Data microarray (Saccharomyces Cerevisiae) [12] Nilai data microarray pada gambar 3-4 menyatakan jumlah mRNA yang dihasilkan gen pada perioda tertentu. Misalnya gen CLN1, pada pengukuran 10 satuan waktu pertama, transformasi nilai yang diperoleh dari intensitas warna slide microarray adalah minus 1,34; sedangkan 30 satuan waktu berikutnya diperoleh jumlah mRNA yang semakin besar yaitu 1,21. Tissue types microarray
Gambar 3-5 Pola data microarray berdasarkan jenis tissue Pola pada Gambar 3-5 merupakan pengamatan sebanyak n gen terhadap m jenis tissue.
Treatment condition microarray
Gambar 3-6 Pola data microarray berdasarkan kondisi treatment Pola data pada Gambar 3-6 merupakan pengamatan terhadap n gen dengan m kondisi treatment, misalnya untuk mengamati pengaruh pengobatan yang dilakukan terhadap sel berpenyakit. 3.2.2
Proximity Matrix
Clutering membutuhkan indeks kedekatan, atau kesamaan antar pasangan pattern. Indeks kedekatan dapat dihitung dari pattern matrix. Proximity matrix mengakumulasikan kedekatan indeks berpasangan pada sebuah matriks dimana setiap baris dan kolom merepresentasikan sebuah pattern. Diagonal matriks diabaikan karena semua pattern diasumsikan mempunyai derajat yang sama dengan dirinya sendiri. Selain itu, diasumsikan bahwa semua proximity matrix adalah simetris, sehingga semua pasangan objek mempunyai indeks kedekatan yang sama, tanpa memperdulikan letak penulisan objek pada matriks. Indeks kedekatan dapat berupa similarity atau dissimilarity. Semakin mirip objek ke-i dengan objek ke-j, maka semakin besar indeks similarity dan semakin kecil indeks dissimilarity [10]. Pada algoritma clustering, penghitungan indeks kedekatan antara dua buah objek merupakan bagian yang sangat fundamental dalam menempatkan objek tersebut di dalam suatu cluster. Analisis microarray juga menerapkan hal yang sama untuk menemukan gen yang mirip dengan menemukan dan mengelompokkan gen-gen yang jaraknya dekat satu dengan yang lain. Pencarian jarak antar gen dilakukan berdasarkan jarak vektor ekspresi untuk setiap gen. Untuk dapat dikelaskan sebagai metrik, jarak dij, antara dua vektor, i dan j, seperti pada Gambar 3-7, harus memenuhi syarat [13]: 1. Jarak harus positif, dij ≥ 0 2. Jarak harus simetris, dij = dji, maka jarak dari i ke j sama dengan jarak j ke i. 3. Jarak objek ke dirinya sendiri adalah 0, dii = 0.
Gambar 3-7 Ruang vektor i dan j [13] Terdapat beberapa metrik yang dapat digunakan untuk menghitung indeks kedekatan antar objek, beberapa diantaranya adalah Euclidean dan Pearson correlation coefficient. Euclidean menghitung indeks kedekatan antar objek dengan mengunakan hukum Phytagoras. Berdasarkan cara kerja hukum Phytagoras, Euclidean memenuhi ketiga syarat yang harus dipenuhi sehingga dapat disebut sebagai metrik. Pearson menghitung indeks kedekatan antar objek berdasarkan korelasi objek. Semakin identik dua gen, maka jarak antar gen tersebut menjadi 1, sehingga jarak antar gen dengan dirinya sendiri adalah 1. Jarak yang dihasilkan oleh Pearson tidak selalu positif. Dengan demikian, berdasarkan ketiga syarat yang harus dipenuhi sehingga dapat disebut sebagai metrik, Pearson tidak memenuhi syarat ke-1 dan ke-3. Disimpulkan bahwa Pearson bukanlah metrik seutuhnya, namun dikategorikan sebagai semi-metrik. Pada pembahasan berikutnya Pearson akan dimasukkan ke dalam metrik, karena Pearson dapat dikonversi sehingga memenuhi ketiga kondisi tersebut.
Pembahasan lebih detil tentang metrik similaritas Euclidean dan Pearson dapat dilihat pada subbab 3.2.2.1 dan subbab 3.2.2.2 [14]. Misalkan x = (x1, ...., xn) dan y = (y1, ...., yn) adalah dua gen, yang direpresentasikan dengan vektor n-dimensi (n adalah jumlah poin waktu pengamatan) dengan nilai ekspresi berdasarkan eksperimen. 3.2.2.1 Euclidean Fungsi jarak Euclidean menghitung jarak antara dua level ekspresi gen dengan menggunakan hukum Phytagoras, dengan rumus:
D( x , y) =
n
∑ (x i =1
i
− yi )2
(1)
Penghitungan menggunakan fungsi jarak Euclidean bergantung kepada magnituda level ekspresi gen. Hasil penghitungan koefisien dengan Euclidean adalah matriks dissimilarity, semakin kecil koefisien dua gen maka semakin identik kedua gen tersebut [15]. 3.2.2.2 Pearson Correlation Coefficient Cara yang paling sederhana untuk memahami korelasi koefisien adalah dengan menggambar gen X dan Y sebagai vektor ekspresi, nilai kemiripan bentuk kedua vektor X dan Y dinyatakan dalam nilai korelasi cor (X,Y). Korelasi koefisien Pearson yang selalu berada antara –1 dan 1, dengan kasus khusus: 1 : apabila kedua rangkaian gen (sekumpulan level ekspresi gen terhadap beberapa kondisi pengamatan) identik satu dengan yang lain. Pada Gambar 3-8, label 1 sampai 7 merupakan rangkaian gen. Gen B dan C identik, dengan rangkaian gen yang persis sama. Selain itu, Gen B, C, dan A juga identik karena mempunyai pola rangkaian gen yang sama, hal ini disebabkan level ekspresi Gen A untuk setiap label bertambah 0.2 dari level ekspresi B atau C. 1. 0 : apabila kedua rangkaian gen tidak berhubungan/berkorelasi sama sekali, 2. -1 : apabila rangkaian gen yang satu merupakan kebalikan dari rangkaian gen yang lain. Contoh rangkaian gen dan korelasi antar gen dapat dilihat pada gambar 3-8. Contoh kasus rangkaian gen yang berkebalikan yang menghasilkan korelasi –1, terjadi pada Gen C dan Gen F. Sedangkan contoh kasus yang tidak memiliki korelasi sama sekali terjadi pada Gen C dengan Gen D.
Gambar 3-8 Kasus Khusus Korelasi Rangkaian Gen
Koefisien korelasi tidak berubah terhadap operasi transformasi linier terhadap data. Sehingga apabila semua nilai Y ditambah dengan 2, atau ditambah 7, maka korelasi antara nilai X dan Y tidak akan berubah. Hal ini disebabkan, bentuk kedua vektor tetap sama, tetapi magnitudanya yang berbeda.
cor ( x, y ) =
1 n (xi − µ x )( y i − µ y ) , ∑ n i =1 σ xσ y
(2)
dengan µ dan the standar deviasi σ didefinisikan sebagai berikut:
µ x = E[ x ] =
1 n ∑ xi n i =1
σ x = E[( x − µ x ) 2 ] = E[ x 2 ] − µ 2x =
(3)
1 n 2 ∑ x i − µ 2x n i =1
(4)
Koefisien korelasi merupakan ukuran kedekatan gen x dan y. Apabila x dan y identik, maka koefisien = 1, dan 0 untuk sebaliknya. Dengan demikian E[xy] = E[x]E[y]. Koefiesien korelasi Pearson menghasilkan matriks similarity, semakin kecil koefisien antara dua gen, maka semakin tidak identik kedua gen tersebut [15]. 3.3
Normalisasi Normalisasi bertujuan untuk menjamin bahwa perbedaan intensitas pada data microarray memang diakibatkan oleh ekspresi gen yang berbeda-beda. Normalisasi akan mengidentifikasi dan menghilangkan dampak dari akibat variasi yang terjadi akibat pengukuran pencahayaan yang berpijar, selain dari perbedaan ekspresi, misalnya [16]. 1. Perbedaan efisiensi pelabelan dyes. 2. Perbedaan jumlah label Cy3- dan Cy5 mRNA. 3. Perbedaan paramater scanning. 4. Pencetakan (print-tip), dan lain sebagainya. Normalisasi dapat diterapkan untuk menghilangkan efek pemilihan metrik jarak pada saat melakukan clustering. Normalisasi dilakukan dengan cara mentransformasi semua data ke dalam skala yang sama dengan mengurangi data dengan nilai tengah dan membagikan dengan varian data [17]. Proses pada normalisasi adalah menjadikan nilai jarak atau kuadrat penjumlahan nilai vektor baris/kolom menjadi 1.0 [8].
3.4
Algoritma Clustering Pada subbab berikut diuraikan teknik-teknik clustering yang digunakan, yaitu Hierarchical Clustering, K-Means, dan Self Organizing Maps.
3.4.1
Hierarchical Clustering (HC) HC menempatkan elemen masukan dalam bentuk struktur hierarki pohon dengan jarak dalam pohon merefleksikan kesamaan elemen. Elemen ditempatkan sebagai daun pada pohon. Elemen dengan kemiripan paling tinggi dihubungkan dengan cabang yang pendek, dengan demikian semakin panjang cabang yang menghubungkan elemen, maka semakin menurun tingkat kemiripan kedua elemen tersebut [2].
Gambar 3-9 TreeView Data Cluster Hasil Penerapan Algoritma HC Pada contoh Gambar 3-9, B dan C lebih mirip dibandingkan dengan B terhadap A. Keuntungan dari HC adalah sederhana dan hasilnya lebih mudah direalisasikan. HC merupakan teknik yang paling banyak digunakan untuk analisis data ekspresi gen. HC merupakan algoritma dengan pendekatan agglomerative dengan profile ekspresi tunggal digabungkan membentuk kelompok, yang akan terus digabungkan sehingga terbentuk satu pohon hierarki. Proses HC adalah sebagai berikut [13]: 1. Hitung distance matrix untuk semua gen yang akan di-cluster. 2. Temukan dua gen yang paling mirip dari distance matrix atau cluster; pada tahap awal, setiap cluster hanya terdiri dari satu gen. Apabila terdapat beberapa pasangan yang mempunyai jarak, aturan penentuan digunakan untuk pemilihan dari beberapa alternatif tersebut. 3. Gabungkan kedua cluster yang dipilih menjadi satu cluster baru, sehingga menjadi terdiri dari paling sedikit dua objek. 4. Hitung jarak antara cluster yang baru dihasilkan terhadap semua cluster yang lain. Penghitungan semua jarak tidak dibutuhkan karena hanya yang terlibat dengan cluster baru yang berubah. 5. Ulangi langkah 2-4 sehingga semua objek berada dalam satu cluster. Terdapat beberapa jenis algoritma HC yang dapat diaplikasikan untuk data microarray yaitu [15]: 1. Single-linkage clustering: Jarak antara dua cluster, i dan j, dihitung sebagai jarak minimum antara sebuah anggota cluster i dan sebuah anggota cluster j. Metoda ini cenderung menghasilkan cluster yang loose karena cluster dapat digabungkan apabila ada dua anggota yang dekat satu dengan yang lain. 2. Complete-linkage clustering: Complete linkage clustering juga dikenal sebagai metoda ketetanggaan maksimum. Jarak antara dua cluster dihitung sebagai jarak maksimum dari anggota cluster yang relevan. Metoda ini cenderung menghasilkan cluster yang ukurannya sama dan elemen cluster yang banyak. 3. Average-linkage clustering: Jarak antara cluster dihitung dengan menggunakan nilai rata-rata. Terdapat bermacam-macam metoda untuk menghitung nilai rata-rata. Metoda yang paling umum digunakan adalah unweighted pair-group method average (UPGMA). Jarak rata-rata dihitung dari jarak antara setiap poin pada cluster dengan semua poin pada cluster lainnya. Dua cluster dengan jarak rata-rata yang paling rendah akan digabungkan untuk membentuk satu cluster yang baru.
3.4.2
K-Means K-Means mengelompokkan objek ke dalam k cluster, k adalah jumlah cluster akhir yang akan dihasilkan, dispesifikasikan oleh pengguna. K-Means mempunyai dua metoda yaitu K-Means dan K-Medoids. K-Means menghitung ratarata (mean) dari cluster yang terbentuk, sedangkan K-Medoids menghitung nilai tengah (median) cluster yang terbentuk sehingga data dengan nilai tertinggi dan terendah tidak mempengaruhi clustering. Proses pada algoritma K-Means dengan metoda K-Means dan K-Medoids adalah [13]: 1. Pilih k objek secara acak untuk dijadikan sebagai cluster center (centroid). 2. Kelompokkan semua objek secara acak ke dalam salah satu dari k cluster center yang ada. 3. Apabila: a. Menggunakan metoda K-Means, hitung rata-rata vektor ekspresi dari setiap cluster yang akan digunakan untuk menghitung jarak antar cluster. b. Menggunakan metoda K-Medoids, hitung nilai tengah vektor ekspresi cluster dari setiap cluster yang akan digunakan untuk menghitung jarak antar cluster. 4. Dengan menggunakan metoda iteratif, objek dipindahkan antar cluster dan jarak intra dan intercluster dihitung untuk setiap perpindahan. Objek dimungkinkan untuk tetap pada cluster yang baru hanya jika jarak baru lebih dekat dibandingkan dengan jarak pada cluster sebelumnya.
5. Untuk setiap perpindahan, dilakukan penghitungan ulang terhadap vektor ekspresi dari setiap cluster. 6. Acak proses sehingga pemindahan objek mengakibatkan cluster lebih bervariasi, menaikkan jarak intra-cluster dan menurunkan ketidaksamaan inter-cluster. 3.4.3
Self Organizing Map (SOM) SOM adalah teknik clustering neural network yang berbasis pendekatan divisive. SOM menempatkan gen-gen ke dalam rangkaian partisi berdasarkan similaritas vektor ekspresi gen dengan vektor referensi yang ditentukan untuk setiap partisi. Proses penentuan vektor referensi membedakan SOM dengan K-Means. Sebelum memulai analisis, pengguna menentukan konfigurasi geometri untuk partisi, biasanya ruang dua dimensi atau grid heksagonal. Pada setiap partisi dihasilkan vektor secara acak, namun sebelum gen-gen dapat ditempatkan pada partisi, vektor terlebih dahulu uji dengan menggunakan proses secara iterative sehingga data terpisah satu dengan yang lain dengan baik [13]: Tahapan proses SOM adalah [13]: 1. Vektor acak dibangun dan ditempatkan pada masing-masing k-partisi. 2. Sebuah gen dipilih secara acak. Identifikasi vektor referensi yang paling dekat dengan gen, dengan menggunakan distance metric. 3. Vektor referensi disesuaikan sehingga lebih mirip dengan vektor gen yang dialokasikan (assign). Vektor referensi yang berada pada grid dua dimensi disesuaikan sehingga vektor tersebut lebih mirip dengan vektor gen yang dialokasikan. 4. Langkah 2 dan 3 diulangi beberapa atau ribuan kali, menurunkan jumlah dengan menyesuaikan vektor referensi dan meningkatkan paramater yang digunakan untuk menentukan kemiripan pada setiap langkah. 5. Gen dipetakan ke dalam partisi yang relevan berdasarkan kemiripan gen terhadap vektor referensi.
3.5
Validasi Hasil Clustering Validasi cluster merupakan prosedur yang mengevaluasi hasil dari analisis clustering dengan cara yang objektif dan kuantitatif.
Indeks validasi cluster untuk mengukur ketepatan struktur yang diperoleh dari analisis clustering, dalam hal dapat diterjemahkan secara objektif, adalah probabilitas. Ketepatan struktrur cluster menyatakan bahwa struktur menyediakan informasi yang benar mengenai data, atau kemampuan struktrur yang diperoleh untuk merefleksikan karakter intrinsik data. Tiga jenis struktur tersebut adalah hierarchies, partitions, dan clusters. Hierarchies adalah sekumpulan sekuens partisi. Partitions adalah hasil dari algoritma clustering partitional/non hierarkis, dan cluster adalah himpunan bagian individual dari pattern. Terdapat tiga kriteria prosedur untuk validasi struktur clustering yaitu kriteria eksternal, internal, dan relatif. Kriteria eksternal mengukur performansi dengan membandingkan struktur clustering dengan informasi yang sudah ada sebelumnya (priori information). Misalnya, kriteria eksternal mengukur derajat koresponden antara jumlah cluster yang diperoleh dari sebuah algoritma clustering dengan kategori label sebagai informasi priori. Kriteria internal memperkirakan kecocokan antara struktur dan data, menggunakan data itu sendiri. Misalnya, kriteria internal akan mengukur derajat sebuah partisi yang diperoleh dari algoritma clustering akan ditempatkan oleh proximity matrix yang diberikan. Kriteria relatif menentukan struktur yang lebih baik bila dibandingkan dengan struktur yang lain, seperti lebih stabil atau lebih cocok untuk data tertentu. Misalnya, kriteria relatif akan mengukur secara kuatitatif kesesuaian data dengan penerapan single-link atau complete-link pada hierarkis [10] . Untuk validasi hasil clustering, kriteria eksternal memiliki keunggulan karena melakukan penilaian kualitas cluster yang terpisah dan tidak mengandung perkiraaan-perkiraan atau prasangka. Namun, kriteria eksternal juga memiliki kerugian karena untuk pengukuran data ekspresi gen, “gold standard” eksternal jarang sekali ada. Kriteria internal menghindari penggunaan standar, tetapi memiliki alternatif yaitu melakukan validasi terhadap cluster dengan menggunakan informasi yang sama dengan informasi untuk clustering [18]. Pendekatan untuk menggunakan kriteria eksternal adalah dengan mengasumsikan bahwa tidak dibutuhkan standar eksternal. Evaluasi penilaian kualitas cluster menggunakan satu kondisi (kolom) saja dari raw data yang akan digunakan sebagai masukan validasi. Contoh penerapan kriteria eksternal adalah Figure Of Merit (FOM). 3.5.1
Figure Of Merit (FOM) Figure Of Merit adalah pengukuran kemampuan prediktif suatu algoritma clustering. Himpunan data ekspresi gen terdiri dari ukuran level ekspresi dari n gen yang diukur terhadap m kondisi. Misalkan sebuah algoritma clustering diaplikasikan terhadap data dari kondisi 1, …., (e-1), (e+1), …., m, dan kondisi e digunakan untuk memperkirakan kemampuan prediktif algoritma. Misalkan terdapat cluster sebanyak k, C1, C2, ……, Ck. R(g,e) adalah level ekspresi gen g untuk kondisi e pada raw data matriks (gambar 3-10). µC1(e) adalah nilai rata-rata level ekspresi pada kondisi e dari gen pada cluster C1. Normalisasi ke-2 dari FOM adalah deviasi akar kuadrat nilai tengah pada kondisi e dari level ekspresi gen relatif terhadap nilai tengah cluster dirumuskan, . …………(5) Setiap m kondisi dapat digunakan sebagai kondisi eksperimen yang dibuang (left-out). Aggregate FOM, FOMtot(k) = , adalah estimasi dari total kemampuan prediktif algoritma terhadap semua kondisi untuk sebanyak k cluster pada himpunan data.
Gambar 3-10 Perhitungan FOM terhadap Raw Data Matrix
Gambar 3.5-11 Perbandingan Algoritma A dan B Pada kasus penggunaan nilai rata-rata dari kuadrat jarak nilai tengah sebagai FOM, aggregate FOM yang kecil menandakan tingkat prediktif algoritma yang tinggi. Contohnya, pada gambar 3-11 algoritma B mempunyai kemampuan prediktif yang lebih tinggi daripada algoritma A [18]. 4
ANALISIS Indeks validasi kemampuan prediktif algoritma dapat digunakan sebagai acuan dalam pemilihan algoritma clustering. Hasil pengaplikasian FOM terhadap data hasil clustering sel ragi dapat dilihat pada gambar 4-1 berikut. Pada gambar 4-1 diperoleh bahwa algoritma K-Medoids mempunyai tingkat kemampuan prediktif yang paling tinggi, kemudian diikuti oleh algoritma K-Means dan algoritma SOM. Untuk jumlah cluster sama dengan 3, algoritma K-Medoids dan K-Means mempunyai indeks FOM yang sama. Sedangkan untuk jumlah cluster lebih besar dari 3 K-Medoids menunjukkan tingkat kemampuan prediktif dibandingkan K-Means dan SOM.
Gambar 4-1 Indeks FOM Algoritma Pada gambar 4-2 diperoleh bahwa untuk jumlah cluster 2 sampai 3 SOM menunjukkan indeks FOM yang lebih rendah (tingkat kemampuan prediktif tinggi) dibandingkan K-Means dan K-Medoids. Sedangkan untuk jumlah cluster lebih besar 3, K-Medoids menunjukkan tingkat kemampuan prediktif yang lebih tinggi dibandingkan dengan K-Means dan SOM.
Gambar 4-2 Indeks FOM Algoritma 5
KESIMPULAN DAN SARAN Berdasarkan perbandingan kemampuan prediktif algoritma non-hierarki dengan menggunakan data sel ragi, maka disimpulkan bahwa Algoritma K-Means bagus digunakan untuk mengelompokkan data ke dalam jumlah cluster yang banyak. Algoritma K-Medoids, digunakan sebagai algoritma tambahan untuk perbandingan kemampuan prediktif. Dari beberapa kali percobaan K-Medoids lebih bagus daripada algoritma K-Means dalam menghasilkan jumlah cluster yang besar, namun berlaku sebaliknya untuk jumlah cluster yang kecil. Hal ini dikarenakan K-Medoids tidak dipengaruhi oleh data yang terlalu besar atau terlalu kecil. Algoritma SOM, cenderung menunjukkan performansi yang stabil. Dari segi kemampuan prediktif dengan FOM, SOM tidak lebih bagus dari K-Means dan K-Medoids. Algoritma HC banyak digunakan untuk clustering data secara hirarkis saja, sementara itu, tidak semua data merupakan bagian dari data yang lain (terstruktur secara hierarkis). Dengan demikian untuk data yang membutuhkan beberapa cluster dan data yang tidak terstruktur secara hierarki digunakan algoritma non-hierarki seperti K-Means dan SOM.
Karena teknik clustering dengan algoritma K-Means dan SOM dimulai dengan inisialisasi cluster secara random, maka hasil yang diperoleh setiap melakukan clustering akan berbeda-beda. Hal ini mengakibatkan nilai FOM yang dihasilkan setiap menjalankan clustering akan berbeda-beda pula. Algoritma non-hierarki/partisional seperti K-Means dan SOM membagi data menjadi k-cluster. Namun untuk data dengan level ekspresi yang sama, algoritma partisional ini tetap mengelompokkan data menjadi satu cluster saja. Validasi hasil clustering dengan menggunakan FOM, diterapkan pada algoritma clustering yang menghasilkan lebih dari satu cluster. Dengan demikian, pada modul perangkat lunak ini FOM tidak dapat diterapkan pada Hierarchical Clustering, karena hanya menghasilkan satu cluster. FOM dapat diaplikasikan untuk algoritma hierarki yang menghasilkan hanya satu cluster seperti Hierachical Clustering (HC). HC dapat menghasilkan beberapa cluster dengan cara memotong cabangcabang pada pohon sehingga akan dihasilkan cluster-cluster sesuai dengan jumlah cluster/gen yang berada dibawah cabang tersebut. Untuk menghasilkan n-jumlah cluster, maka cabang dipotong pada n1 cabang terdekat dari induk. Penomoran cabang dilakukan dari daun. Penghitungan FOM untuk algoritma hierarki ini diperlukan untuk perbandingan kemampuan prediktif antara algoritma clustering hierarki dengan non-hierarki atau partisional. Pemilihan jumlah cluster sebagai salah satu parameter dalam clustering sangat mempengaruhi cluster yang dihasilkan. Alangkah baiknya apabila ada pembahasan berikutnya tentang cara pemilihan jumlah cluster dan metrik jarak untuk memperoleh cluster yang akurat.
6
DAFTAR PUSTAKA 1. Zubir, Henny Y, “Pemodelan Informasi untuk Pemahaman Sistem Regulatori Genetik In-Silico”. Prosiding pada Konferensi Nasional Sistem Informasi 2005 di Bandung. 2. Shamir, Ron, “Analysis of Gene Expression Data”, Tel Aviv University, 2004, Lecture 1. 3. D.K Toulis; V.P. Palgianakos; M.N. Vrahatis, “Unsupervised Clustering of Bioinformatics Data”, European Simposium on Inteligent Technologies, Hybrid Systems and their implementation on Smart Adaptive Systems, Aachen, Germany, 2004. 4. S, Alexander; Q.John; T. Zlatko 2000. “Cluster Analysis of Microarray Data”. Bioinformatics, Application Note Vol.18 no.1 2002. 5. JA. Hartigan, “Clustering Algorithms” New York: John Wiley and Sons 1975. 6. J. MacQueen: “Some methods for classification and analysis of multivariate observations”, In Proc 5th Berkeley Symp Math Stat Probability (Edited by: University of California Press). Cam LML, Neyman J 1965, 281-297. 7. T. Kohonen, “Self Organizing Maps”, Berlin/Heidelberg: Springer-Verlag 1997. 1998. 8. Eisen M et al, “Cluster Analysis and Visualization”, PNAS 95:14863, 1998. 9. Roded Sharan, Adi Maron-Katz, Ron Shamir, “CLICK and EXPANDER : a system for clustering and visualizing gene expression data”, Berkeley, 2003. 10. Anil K. Jain, Richard C. Dubes, “Algorithm for Clustering Data”, Prentice Hall Advanced Reference Series, 1998. 11. Dan Nettleton, “Cluster and Classification Analysis of Microarray Data”, http://www.public.iastate.edu/~dnett/microarray/lecturenotes.shtml, tanggal akses 4 Agustus 2006. 12. Botstein, David, Bruce Futcher, Patrick Brown, Michael Zhang. Yeast Cell Cycle Analysis Project. Stanford University. http://cellcyclewww. stanford.edu/, tanggal akses 28 Juni 2006. 13. John Quakenbush, “Computational Analysis of Microarray Data”, Nature Reviews, Genetic, Macmilan Magazines Ltd, Volume 2, Juni 2001. 14. Yu Bai, “Microarray Analysis and Clustering”, Lecture 15, 2004. 15. Rainer Breitling, “Analysis of Gene Expression Data”, Bioinformatics Research Centre and Institute of Biomedical and Life Sciences University Glasglow, 2005. 16. Vince Carey, Sandrine Dudoit, “Short course : Practical Analysis of DNA Microarray Data”, Bioconductor, Denmark, 2003. 17. Gepas Team, “Tutorian on DNA Array Data Clustering”, Bioinformatics Department, 2006.
18. K.Y. Yeung, D. R. Haynor, W. L. Ruzzo, “Validating clustering for gene expression data”, Bioinformatics, volume 17, number 4, April 2001.
