PENGARUH PENGGUNAAN METODE POWER DAN TRUNCATED POWER PADA PCA-PART UNTUK INISIALISASI K-MEANS ABSTRACT

Seminar Nasional Sains & Teknologi V Lembaga Penelitian Universitas Lampung 19-20 November 2013

PENGARUH PENGGUNAAN METODE POWER DAN TRUNCATED POWER PADA PCA-PART UNTUK INISIALISASI K-MEANS Erie Sadewo1, Muhammad Mashuri2, dan Ali Ridho Barakbah3 1

Mahasiswa Pascasarjana, Jurusan Statistika, F-MIPA ITS Surabaya 2 Jurusan Statistika, F-MIPA ITS Surabaya 3 Jurusan Teknik Komputer dan Informasi, Politeknik Elektronika Negeri Surabaya Surel: [email protected]

ABSTRACT K-Means was one of the most popular clustering algorithms, famous because it’s simplicity in implementation and speed in computing time. As an iterative algorithm, KMeans is sensitive to clustering initializations, and tend to produce local optimum solution. To have global optimum, one must restart K-Means a number of times, which was inefficient, nor guarantees that the final solution will be unique. One of K-Means modified form that resulting global optimum solution reached by applying PCA-Part for its initialization. In this paper, we try to optimize PCA-Part for K-Means initialization by implementing Power and Truncated Power method on its eigenvalue computation. The effectiveness of the use of both methods is measured by its computing time and the final Within Cluster Sum Square of Error (WC-SSE). The study using 12 dataset from UCI Machine Learning Repository shows that essentially, the Power and Truncated Power method is more efficient on computing time, and accuracy. There were no significant difference between Power and Truncated Power method on computing time, but Truncated Power gives better accuracy than the Power method on WC-SSE criteria. Keyword: Clustering, K-Means, PCA-Part, power Method, truncated Power

PENDAHULUAN Salah satu jenis algoritma clustering yang paling banyak digunakan adalah KMeans. Keunggulan terpenting algoritma ini adalah sangat mudah untuk diterapkan dan membutuhkan waktu komputasi yang relatif singkat dibandingkan algoritma lainnya. Namun algoritma ini masih memiliki kekurangan, karena sebagai suatu algoritma dengan pendekatan iteratif, K-Means sensitif terhadap kondisi inisialisasi awal clustering (Bradley dan Fayyad, 1998). Dalam algoritma K-Means standar, pemilihan inisialisasi awal yang dilakukan secara acak sehingga cenderung menghasilkan hasil clustering yang hanya konvergen pada optimum lokal. Agar cluster yang dihasilkan dapat dikatakan sebagai optimum

1326 POSTER


yang berlaku secara global, diperlukan adanya sejumlah pengulangan algoritma KMeans. Akibatnya, tidak terdapat adanya jaminan solusi cluster yang dihasilkan unik. Salah satu alternatif untuk mendapatkan hasil clustering yang optimum pada KMeans adalah dengan memodifikasi proses inisialisasi yang biasanya dilakukan melalui metode random seed dan random partition. Jika dalam prosesnya sebagian besar metode modifikasi pada inialisasi K-Means masih mengandung unsur random, maka Su dan Dy (2004) memperkenalkan suatu metode deterministik untuk inisialisasi K-means. Proses inisialisasi dilakukan dengan memproyeksikan data ke dalam suatu garis pada ruang euclidean dan mempartisinya berdasarkan eigenvektor yang dihasilkan Principal Component Analysis (PCA). Dengan memanfaatkan PCA untuk menemukan cluster yang menyumbangkan Sum Square Error (SSE) terbesar, maka akan didapati bahwa partisi terhadap cluster dengan SSE terbesar tersebut secara iteratif akan memperkecil SSE yang didapatkan pada tahap akhir. Metode tersebut dikenal sebagai PCA-Part. Dengan menggunakan bantuan PCA, maka PCA-Part dapat menghindari adanya ketidakpastian dan pemborosan waktu yang diakibatkan oleh adanya pengulangan KMeans. penggunaan PCA-Part untuk inisialisasi K-Means memberikan hasil yang serupa dengan nilai SSE minimal yang didapatkan melalui 100 kali pengulangan KMeans standar (Su dan Dy, 2006). Metode ini juga dinilai sangat kompetitif jika dibandingkan dengan K-Means++, yang merupakan salah salah satu metode inisialisasi terbaik sampai saat ini (Celebi dan Kingravi, 2012). Su dan Dy (2004) menekankan pada pentingnya penggunaan nilai eigenvalue terbesar sebagai dasar untuk menetapkan cluster yang akan dipartisi. Pada kenyataannya, operasi aljabar matriks yang digunakan seperti Householder-QR, masih melibatkan cara faktorisasi, sehingga dianggap kurang efisien. Untuk meningkatkan kecepatan waktu komputasi PCA-Part pada inisialiasi K-Means, Su dan Dy (2004) mengusulkan adanya penggunaan metode iterasi Power. Metode Power memiliki kelemahan yaitu ketika selisih antara nilai eigenvalue terbesar ( 1 ) dan eigenvalue terbesar kedua ( 2 ) sangat kecil, maka waka waktu yang dibutuhkan untuk mencapai nilai yang konvergen menjadi lambat (Saad, 2011). Untuk mengantisiapsi adanya kemungkinan tersebut, dalam penelitian ini juga akan digunakan metode Truncated Power (Yuan dan Zhang, 2013). Sebagaimana halnya Metode Power, 1327 POSTER


Metode Truncated Power dipilih karena cukup sederhana dan efektif dalam memecahkan masalah optimasi nonconvex. Sebagaimana pada metode Power, penggunaan metode Truncated Power yang bersifat iteratif memiliki potensi untuk menghasilkan selisih nilai akibat perkalian vektor yang melibatkan tingkat ketelitian atau toleransi tertentu. Oleh karena itu akan diteliti, sejauh mana pengaruh perbedaan eigenvektor yang dihasilkan oleh kedua metode tersebut pada Sum Square Error Within Cluster (SSE-WC) akhir yang dihasilkan oleh PCA-Part untuk inisialisasi K-Means. METODE Jika misalkan A  ai |1, 2,..., n merupakan suatu atribut dari vektor berdimensi n, dan X  {xi | i  1, 2,..., r} merupakan data pada A. Algoritma K-Means membentuk K partisi dari X yang disebut sebagai cluster S  {si , i  1, 2,..., K } , dimana terdapat suatu

M  {mi | i  1, 2,..., n( si )} yang merupakan anggota dari S dan M  X . Setiap cluster tersebut memiliki suatu titik pusat C  {ci | i  1, 2,..., k} . Algoritma K-Means Menurut Su dan Dy (2006), istilah K-Means dapat diartikan sebagai proses untuk menempatkan setiap titik data xi ke dalam cluster dengan nilai rata-rata yang memiliki jarak terdekat. Dengan demikian, tujuan akhir dari K-Means adalah untuk meminimumkan SSE diantara seluruh k-cluster. k

2

J ( si )    xi  i .

(1)

i 1 xi si

Sum Square Error merupakan kriteria optimasi K-Means yang paling banyak digunakan (Duda dan Hart, 2000). Sebagai suatu algoritma yang sangat ringkas (Greedy Algorithm), K-Means hanya dapat konvergen pada suatu minimum lokal. Menurut Arai dan Barakbah (2007), langkah yang digunakan dalam algoritma K-Means dapat dijelaskan sebagai berikut: i).

Memulai algoritma dengan membangkitkan pusat cluster awal ck secara random

1328 POSTER

Seminar Nasional Sains & Teknologi V Lembaga Penelitian Universitas Lampung 19-20 November 2013 ii). Menghitung jarak d ( x, c) antara setiap vektor xi terhadap pusat cluster ck yang

didapatkan pada i) iii). mengelompokkan xi ke dalam sk yang memiliki d ( x, c) minimum iv). Hitung pusat cluster baru ci 

1 p  m( si , j ) , dimana p  n(si ) p j 1

v). Mengulangi mulai dari langkah ii) hingga Ci  Ci 1

Menurut Kovesi et al. (2001), algoritma tersebut akan berhenti pada iterasi ke t pada

C t  C t 1  . Ct

suatu nilai  jika K-Means mencapai

Partisi Cluster Menggunakan PCA Dengan membagi sebuah cluster, akan didapatkan suatu nilai SSE baru yang merupakan hasil penjumlahan dari SSE setiap partisi cluster. Jika  merupakan rata-rata dari cluster C yang akan dibagi, maka Setelah membagi cluster C menjadi dua sub cluster yaitu C1 dan C2, akan didapatkan nilai rata-rata baru yaitu 1 dan 2 . Dengan demikian nilai SSE yang baru berubah menjadi: SSEbaru 



2



xi  1 

xi C1

xi  2

2

(2)

xi C2

Setiap d-dimensi vektor xi dan rata-rata  dapat direpresentasikan pada suatu jumlah terboboti dari   1 , 2 ,..., d  , yaitu vektor basis ortonormal yang linier dan independen, sehingga d

d

xi   yiss dan  j    jss s 1

(3)

s 1

Dalam hal ini, Su dan Dy (2006) telah membuktikan bahwa nilai  p

yang

meminimumkan SSE baru adalah ekuivalen dengan nilai  p yang memaksimalkan

 (y 

ip p

xi C

  p p )2   ( yip p  1 p p )2  xi C1

 (y 

ip p

  2 p p )2

(4)

xi C2

Selanjutnya PCA-Part akan memilih  p sebagai komponen yang berkontribusi terhadap nilai SSE terbesar. Eigenvektor terbesar dari matriks kovarians merupakan bagian yang memiliki kontribusi terhadap SSE terbesar (Fukunaga, 1990). Untuk 1329 POSTER


mendapatkan

eigenvektor

dari

eigenvalue terbesar, dapat dilakukan

dengan

menggunakan metode Householder-QL/QR. Pada metode ini, matriks kovarian didekomposisi menjadi matriks Upper Hessenberg, kemudian dilanjutkan dengan faktorisasi implisit QL/QR dengan pergeseran. Secara sederhana, metode inisialisasi menggunakan PCA-Part untuk K-Means dapat dituliskan sebagai berikut: i).

Kumpulkan seluruh data xi pada satu cluster C j , proyeksikan xi  C j dan  j pada suatu yi dan  j , suatu titik pada vektor y menggunakan eigenvektor yang dihasilkan eigenvalue dengan nilai terbesar

ii).

Partisi vektor y ke dalam dua bagian, dengan menggunakan  j sebagai titik potong, hitung SSE yang dihasilkan set data di setiap bagian yang baru

iii). Pilih C j sebagai cluster berikutnya yang akan dipartisi jika SSE yang dihasilkan lebih besar dibandingkan dengan bagian partisi lainnya, ulangi hingga didapatkan sebanyak K-cluster. Metode Power Sesuai teorema Abel-Ruffini, untuk persamaan polinomial yang berdimensi lebih besar dari lima, tidak terdapat solusi aljabar umum. Untuk mendapatkan solusi digunakan metode iterasi. Misalkan terdapat suatu matriks simetris A berukuran p x p, yang hanya memiliki satu eigenvalue 1 , yang nilainya secara absolut lebih besar dibandingkan dengan seluruh eigenvalue yang dimilikinya. Jika uk 1  Auk , maka dengan mengambil suatu vektor u0 yang sembarang dan tidak nol, akan didapatkan: u1  Au0 u 2  Au1  A( Au 0 )  A 2u 0 u3  Au 2  A( A 2u 0 )  A3u 0

(5)

 u k  Au k 1  A( A k 1u 0 )  A k u 0

Maka berdasarkan Rayleigh Quotient

u tk  u k 1 lim  1 k  u t  u k k

1330 POSTER


Sementara itu barisan vektor yang dinormalkan u k 

uk uk

akan konvergen pada

eigenvektor dari 1 . Metode Truncated Power Metode Truncated Power yang diperkenalkan dengan kekhususan pada permasalahan eigenvalue pada data yang bersifat sparse. Jika terdapat A, suatu matriks simetris semidefinit positif berukuran p x p, maka permasalahan eigenvalue untuk ksparse yang terbesar bertujuan meminimumkan bentuk kuadratik u t Au dengan vektor unit u 

p

yang menyebar dengan tidak lebih dari k elemen yang bernilai tidak nol:

max ( A, k )  max ut Au u

p

dengan u  1, u 0  k .

melambangkan jarak l2 , sementara

Notasi

0

melambangkan jarak l0 , yang

menghitung jumlah komponen bernilai tidak nol pada vektor. Jika terdapat suatu A *k , suatu submatriks utama berukuran k x k dari matriks A, yang memiliki nilai eigenvalue terbesar, maka max (A, k ) akan sebanding dengan

max ( A*k ) . Sebagai salah satu solusi dari permasalahan tersebut, dilakukan pembangkitan suatu barisan eigenvektor k-sparse u0 , u1 ,... dari suatu pendekatan awal

u0 . Selanjutnya diberikan suatu set indeks F, dengan u ( F )  max( uT Au ) p

dimana u  1 , dan supp(u )  F

u

Pada setiap tahap t, vektor perantara ut1 dikalikan dengan matriks A, kemudian setiap masukan dipotong nilainya ke nol, kecuali untuk masukan k yang terbesar. Dengan kata lain jika terdapat suatu vektor u dan set indeks F, maka operasi pemotongan Truncate(u, F ) merupakan suatu vektor yang dihasilkan dengan membuat suatu batasan dari u ke F, sehingga  u i  F [Truncate(u, F )]i   i selainnya 0

Hasilnya berupa vektor yang kemudian akan dinormalkan unit jarak sehingga menjadi vektor ut . 1331 POSTER


Secara umum, metode Truncated Power dapat dituliskan sebagai berikut: i). Pada t  1 , hitung ut'  Aut 1 / Aut 1 ii). Jika Ft  sup(u t' , k ) , merupakan indeks dari u 't dengan nilai absolut k yang terbesar, maka hitung uˆ t  Truncate(u 't , Ft ) iii). Normalkan ut  uˆ t / uˆ t iv). Ulangi langkah ii) dengan t  t  1 hingga konvergen Sumber Data Pada penelitian ini digunakan 12 set data testing yang diambil dari UCI Machine Learning Repository. Pemilihan set data tersebut dilakukan dengan mempertimbangkan variasi jumlah objek (N), jumlah variabel/ atribut (D), serta jumlah cluster/kelas yang sebenarnya (K’). Dari seluruh set data yang digunakan, hanya terdapat satu buah set data yang berkategori sparse, yaitu pada data CNAE-9. Pada setiap set data, clustering akan diulang sebanyak 100 kali. Selain itu juga akan diteliti pengenai pengaruh penggunaan metode penyelesaian eigenvalue yang digunakan terhadap SSE akhir yang terbentuk. Pengolahan data dilakukan dengan menggunakan software Matlab 2013a.

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

Tabel 1 Deskripsi set data yang digunakan dalam penelitian Set Data N D K’ (2) (3) (4) (5) Abalone 4177 7 29 Cardiotographic 2126 21 10 Ionosphere 351 34 2 Iris 150 4 3 Isolet 7797 617 26 letter recognition 20000 16 26 libras movement DB 360 90 15 Musk(clean2) 6598 166 2 rock vs mines 208 60 2 Shuttle (statlog)-training 43500 9 7 Wine 178 13 3 wine quality 6497 11 7 Sumber: http://archive.ics.uci.edu/ml/

1332 POSTER


HASIL DAN PEMBAHASAN Hasil clustering dengan menggunakan metode PCA-Part untuk inisialisasi KMeans menunjukkan bahwa penggunaan metode Power dan Truncated Power tidak selalu menghasilkan waktu komputasi yang lebih cepat dibandingkan dengan metode Householder-QR. Dari 12 set data yang digunakan, terdapat tiga set data dimana waktu komputasi PCA-Part K-Means standar lebih baik dibandingkan dengan penggunan metode Power dan Truncated Power. Hal ini terjadi ketika jumlah kelompok yang dibentuk lebih dari 20, sedangkan banyaknya dimensi sedikit. Ketika jumlah dimensi besar, maka metode Power dan Truncated Power selalu memberikan hasil yang lebih baik dibandingkan dengan metode standar. Secara umum, tidak terdapat perbedaan signifikan waktu komputasi antara metode Power dan Truncated Power. Namun jika dibandingkan dengan metode standar, penggunaan kedua metode tersebut lebih efisien. Tabel 2 Perbandingan Rasio Waktu Komputasi PCA-Part Untuk Inisialisasi K-Means Dengan Menggunakan Metode Power dan Truncated Power Terhadap Householder-QR ID Set Data Power Trunc Power (1) (2) (3) (4) 1 Abalone 1.054 1.787 2 Cardiotographic 1.055 1.089 3 Ionosphere 0.449 0.597 4 Iris 0.990 1.330 5 Isolet 0.158 0.143 6 letter recognition 1.337 1.226 7 libras movement DB 0.049 0.045 8 Musk(clean2) 0.371 0.394 9 rock vs mines 0.150 0.154 10 Shuttle (statlog)-training 0.870 0.658 11 Wine 0.617 0.140 12 wine quality 0.181 0.174 Sumber: hasil pengolahan Dari sisi ketepatan hasil clustering yang diukur menggunakan kriteria SSEwithin cluster, ternyata penggunaan metode penghitungan eigenvalue yang berbeda juga akan menghasilkan cluster dengan SSE yang berbeda. Meskipun secara umum tidak terdapat perbedaan yang signifikan, namun dapat dikatakan bahwa penggunaan metode Power dan Truncated Power memberikan hasil yang lebih akurat. Hal ini terlihat 1333 POSTER


perbandingan besaran SSE within cluster yang dihasilkan oleh penggunaan metode Power dan Truncated Power terhadap standar. Dari Tabel 3, dapat terlihat bahwa metode Truncated Power memberikan nilai SSE paling minimal dibandingkan dengan kedua metode lainnya. Tabel 3 Perbandingan Rasio SSE yang dihasilkan PCA-Part Untuk Inisialisasi K-Means Dengan Menggunakan Metode Power dan Truncated Power Terhadap Householder-QR ID Set Data H-QL/QR Power Trunc Power (1) (2) (3) (4) (5) 1 Abalone 26.8207 26.8235 26.6326 2 Cardiotographic 2419.4 2419.4 2419.4 3 Ionosphere 117.0957 117.0957 117.0957 4 Iris 443870 445420 442240 5 Isolet 618810 627230 611560 6 letter recognition 5.92E+09 5.92E+09 5.92E+09 7 libras movement DB 5.88E+08 5.88E+08 5.88E+08 8 Musk(clean2) 1796700 1796400 1796400 9 rock vs mines 344.7364 329.9515 333.7056 10 Shuttle (statlog)-training 2629300 2629300 2629300 11 Wine 2662700 2615000 2615000 12 wine quality 280.534 280.534 280.534 Sumber: hasil pengolahan KESIMPULAN Hasil pengujian terhadap 12 set data yang memiliki karakteristik berbeda memberikan kesimpulan bahwa penggunaan metode Power dan Truncated Power lebih baik untuk diterapkan pada PCA-Part untuk inisialisasi K-Means dibandingkan dengan metode standar. Dari sisi kecepatan, didapati bahwa waktu komputasi yang dihasilkan melalui penggunaan metode Power dan Truncated Power lebih efisien dibandingkan dengan standar. Meskipun demikian, tidak terdapat perbedaan signifikan waktu komputasi antara metode Power dan Truncated Power. Dari sisi akurasi, SSE within cluster yang dihasilkan oleh kedua metode tersebut secara rata-rata selalu lebih baik dibandingkan dengan metode standar. Meskipun demikian, penggunaan metode Truncated Power akan memberikan hasil clustering yang lebih baik dan stabil dibandingkan dengan metode Power.

1334 POSTER


DAFTAR PUSTAKA Arai, K., Barakbah, A.R., 2007. Hierarchical K-Means: an algorithm for centroids initialization for K-Means. Reports of the Faculty of Science and Engineering 36 (1).Saga: Saga University Bradley, P.S., Fayyad, U.M., 1998. Refining Initial Points for K-Means Clustering. In: Proc. 15th International Conference on Machine Learning (ICML98). J. Shavlik (ed.). pp. 91-99. Morgan Kaufmann, San Francisco Celebi, M.E., Kingravi, H.A., 2012. Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering. International Journal of Pattern Recognition and Artificial Intelligence, 26(7): 1250018. Duda, R., Hart, P., Stork, D., 2001. Pattern Classification, second ed. John Wiley and Sons, New York. Fukunaga, K., 1990. Introduction to Statistical pattern Recognition. Academic Press, Boston, MA. Kövesi, B., Boucher, J.M., Saoudi, S., 2001. Stochastic K-Means algorithm for vector quantization. Pattern Recognition Lett. 22, pp. 603-610. Saad, Y. 2011. Numerical Methods for Large Eigenvalue Problems 2nd Edition. Society for Industrial and Applied Mathemathics, Philadephia. Su, T., Dy, J., 2004. A Deterministic Method for Initializing K-Means Clustering. In: Proc. 16th IEEE International Conference on Tools with Tools with Artificial Intelligence (ICTAI2004), pp.784-786 __________, 2006. In Search of Deterministic Method for Initializing K-Means and Gaussian Mixture Clustering. Intelligent Data Analysis. Vol. 11, No. 4, pp. 319338. Yuan, X.T., Zhang T., 2013. Truncated Power Method for Sparse Eigenvalue Problems. Journal of Machine Learning Research, 14. pp. 899-925.

1335 POSTER

PENGARUH PENGGUNAAN METODE POWER DAN TRUNCATED POWER PADA PCA-PART UNTUK INISIALISASI K-MEANS ABSTRACT

Recommend Documents