BAB II TINJAUAN PUSTAKA 2.1 Tinjauan Teoritis 2.1.1 Analisis Berbasis Cluster Analisis berbasis cluster merupakan suatu teknik untuk membagi data ke dalam beberapa kelompok (cluster) yang memiliki arti dan berguna. Jika kelompok yang memiliki arti adalah tujuannya, maka cluster-cluster harus dapat mengetahui struktur alami dari data. Semakin besar kesamaan (homogenitas) antar objek dalam suatu cluster dan semakin besar perbedaan antara cluster, maka clustering akan semakin baik (Tan P., Steinbach M., Kumar V., 2005:487). Pada proses clustering tidak diperlukan label kelas untuk setiap data yang diproses karena nantinya label baru bisa diberikan ketika cluster sudah terbentuk. Karena tidak adanya label kelas maka clustering sering disebut juga pembelajaran tidak terbimbing (unsupervised learning) (Prasetyo, 2014). Prasetyo menyatakan bahwa proses clustering dapat dibedakan menjadi tiga jenis, yaitu dapat dibedakan menurut struktur cluster, keanggotaan data dalam cluster, dan kekompakan data dalam cluster. Adapun penjabaran dari ketiga jenis proses clustering tersebut ditunjukkan secara rinci pada Tabel 2.1 Tabel 2.1 Jenis-jenis Proses Clustering (Sumber : Prasetyo, 2014) Proses Clustering
Menurut Struktur cluster
Deskripsi
Hirarki
a. Satu data tunggal bisa dianggap sebagai sebuah cluster. b. Dua atau lebih cluster kecil dapat bergabung menjadi sebuah cluster besar. c. Begitu seterusnya hingga semua data dapat bergabung menjadi sebuah cluster.
Partisi
a. Membagi sejumlah
7
set data ke dalam cluster yang tidak
8
bertumpang-tindih antara satu cluster dengan cluster lain. b. Setiap data hanya menjadi anggota satu cluster saja. Menurut keanggotaan data dalam cluster Menurut kekompakan data dalam cluster
Ekslusif
Sebuah data bisa dipastikan hanya menjadi anggota satu cluster dan tidak menjadi angota di cluster lain.
Tumpang-tindih
Membolehkan sebuah data menjadi anggota di lebih dari satu cluster.
Lengkap Parsial
Jika semua data bisa bergabung, maka data kompak menjadi satu cluster, jika tidak data dikatakan menyimpang.
Karena tidak ada label kelas yang digunakan dalam prosesnya, oleh Prasetyo clustering dikatakan sangat cocok untuk melakukan clustering data yang label kelasnya memang sulit didapatkan pada saat pembangkitan fitur. Pada clustering, segera setelah cluster terbentuk, maka label kelas untuk setiap data dapat diberikan dengan cara mengamati keluaran yang dihasilkan oleh proses clustering. Karena tidak membutuhkan label kelas, kemiripan (similarity) harus didefinisikan berdasarkan atribut objek, di mana definisi tersebut bergantung pada algoritma clustering yang diterapkan. Algoritma clustering yang “bagus” digunakan tergantung pada penerapan set data yang diproses. Pada algoritma clustering terdahulu kebanyakan didesain dengan asumsi bahwa atribut dari data yang diolah merupakan data yang bersifat numerik. Namun, hal tersebut tidak sepenuhnya benar pada kasus-kasus dalam dunia nyata, data bisa didapatkan dari berbagai macam tipe data seperti diskret (kategorikal), temporal, atau structural (Aggarwal, C.C. & Reddy, C.K., 2014: 15-16). Adapun tipe data yang dapat diteliti dalam analisis berbasis cluster menurut Aggrawal & Reddy adalah : a. Clustering pada data kategorikal. b. Clustering pada data teks. c. Clustering pada data multimedia. d. Clustering pada data time-series.
9
e. Clustering pada rangkaian diskret. f. Clustering pada data berbasis jaringan. g. Clustering pada data yang tidak pasti. 2.1.2 Clustering Pada Set Data Kategorikal Proses clustering pada set data kategorikal membagi N buah objek ke dalam k buah cluster. Objek o memiliki m buah atribut {o1, o2,…., om}. Atribut oi, i=1..m, memiliki sebuah domain Di dari data kategorikal atau boolean. Adapun klasifikasi dari algoritma yang dapat digunakan untuk melakukan proses clustering pada data kategorikal diperlihatkan pada Gambar 2.1
Gambar 2.1 Klasifikasi Algoritma Clustering untuk Data Kategorikal (Sumber : Aggarwal, C.C. & Reddy, C.K., 2014: 280) Dalam proses clustering data kategorikal, perhitungan similarity atau jarak antar data kategorikal tidak seperti pada data numerik yang kontinyu. Salah satu karekteristik dari data kategorikal adalah atribut kategorikal menggunakan nilai diskret yang tidak memiliki susunan yang inheren yang ada pada atribut data numerik. Beberapa teknik dapat digunakan untuk mengukur similaritas pada clustering
data
kategorikal
diantaranya,
hamming
distance,
pendekatan
10
probabilitas, information-theoritic measures, dan context-based similarity measures (Aggarwal, C.C. & Reddy, C.K., 2014: 284). 2.1.3 Algoritma k-Means Secara historis algoritma k-Means menjadi salah satu algoritma yang paling penting dalam bidang data mining (Wu & Kumar, 2009 pada Prasetyo, 2014:189). Algoritma k-Means dapat diterapkan pada data yang direpresentasikan dalam rdimensi ruang tempat. Algoritma ini mengelompokkan set data r-dimensi, X = {xi | i=1,…., N }, di mana xi ∈ ℜ𝑑 yang menyatakan data ke-i sebagai titik data. Algoritma k-Means mempartisi X ke dalam k cluster, algoritma k-Means mengelompokkan semua titik data dalam X sehingga setiap titik xi hanya jatuh dalam satu k partisi. Yang diperhatikan adalah titik berada dalam cluster yang mana, dilakukan dengan cara memberikan setiap titik sebuah ID cluster. Titik dengan ID cluster sama berarti berada dalam stu cluster yang sama, sedangkan titik dengan ID cluster yang berbeda berada dalam cluster yang berbeda. Untuk menyatakan hal ini, biasanya dilakukan dengan vektor keanggotaan cluster m dengan panjang N, di mana mi bernilai ID cluster titik xi. Parameter yang harus dimasukkan ketika menggunakan algoritma k- Means adalah nilai k. Nilai k yang digunakan biasanya didasarkan pada informasi yang diketahui sebelumnya tentang berapa banyak cluster data yang muncul dalam X, berapa banyak cluster yang dibutuhkan untuk penerapannya, atau jenis cluster dicari dengan mengeksplorasi/melakukan percobaan dengan beberapa nilai k. Beberapa nilai k yang dipilih tidak perlu memahami bagaimana k-means mempartisi set data x. (Prasetyo, 2014:190) Dalam k-means, setiap cluster dari k cluster diwakili oleh titik tunggal dalam ℜ𝑑 . Set representative cluster dinyatakan C={cj/J=1, ..., k}. Sejumlah k representative cluster tersebut tersebut disebut juga sebagai cluster means atau cluster centroid (atau centroid saja). Untuk set data dalam x dikelompokkan berdasarkan konsep kedekatan atau kemiripan. Meskipun konsep yang dimaksud untuk data-data yang berkumpul dalam satu cluster adalah data-data yang mirip, tetapi kuantitas yang digunakan untuk mengukurnya adalah ketidakmiripan
11
(dissimilarity). Artinya, data-data dengan ketidakmiripan (jarak) yang kecil/dekat maka lebih besar kemungkinannya untuk bergabung dalam satu cluster. Metrik yang umum digunakan untuk ketidakmiripannya adalah Euclidean. (Prasetyo, 2014:190) Prasetyo menyatakan, pada saat data sudah dihitung ketidakmiripan terhadap setiap centroid, maka selanjutnya dipilih ketidakmiripan yang paling kecil sebagai cluster yang akan diikuti sebagai relokasi data pada cluster di sebuah iterasi. Relokasi sebuah data dalam cluster yang diikuti dapat dinyatakan dengan nilai keanggotaan a yang bernilai 0 atau 1. Nilai 0 jika tidak menjadi anggota sebuah data cluster, hanya satu yang bernilai 1, sedangkan lainnya 0 seperti dinyatakan oleh persamaan berikut 1, arg min{𝑑(𝑥1 , 𝑐1 )} 𝑎𝑖𝑗 = { .........................................(6.3.1) 0, 𝑙𝑎𝑖𝑛𝑛𝑦𝑎 d(xi,cj) menyatakan ketidakmiripan (jarak) dri data ke-i ke cluster cj. Sementara relokasi centroid untuk mendapatkan titik centroid C didapatkan dengan menghitung rata-rata setiap fitur dari semua data yang tergabung dalam setiap cluster. Rata-rata sebuah fitur dari semua data dalam sebuah cluster dinyatakan oleh persamaan berikut: 1
C1 = 𝑁𝑘 ∑NK 1=1 X jl ……………………………… (6.3.2) Nk adalah jumlah data yang tergabung dalam cluster. Jika diperhatikan dari langkahnya yang selalu memilih cluster terdekat, maka sebenarnya K=-Means berusaha untuk meminimalkan fungsi objektif/fungsi biaya non-negatif, seperti dinyatakan oleh persamaan berikut: 𝐾 2 𝐽 = ∑𝑁 𝑖=1 ∑𝑖=1 𝑎𝑖𝑐 𝑑(𝑥𝑖 , 𝑐1 ) …………………(6.3.3)
Algoritma clustering dengan k-Means (Prasetyo, 2014:191) 1. Insialisasi: tentukan nilai k sebagai jumlah cluster yang diinginkan dan metric ketidakmiripan (jarak) yang diinginkan. Jika perlu, tetapkan ambang batas perubahan fungsi objektif fungsi dan ambang batas perubahan posisi centroid.
12
2. Pilih K data dari set data X sebagai centroid. 3. Alokasikan semua data ke centroid terdekat dengan metric jarak yang sudah ditetapkan (memperbarui cluster ID setiap data). 4. Hitung kembali centroid C berdasarkan data yang mengikuti clusteri masingmasing. 5. Ulangi langkah 3 dan 4 hingga kondisi konvergen tercapai, yaitu (a) perubahan fungsi objektif sudah di bawah ambang batas yang diinginkan; atau (b) tidak ada data yang berindah cluster; atau (c) perubahan posisi centroid sudah di bawah ambang batas yang ditetapkan. Algoritma k-means disajikan pada Algoritma k-means mengelompokkan set data x dalam langkah iterative. Berikut dua langkah utamanya, yaitu (1) penentua kembali ID cluster dari semua titik data dalam X, da (2) memperbarui representasi cluster (centroid) berdasarkan titik data dalam setiap cluster.Algoritma bekerja sebagai berikut: Pertama, representasi cluster diinisialisasi dengan memilih k data daa ℜ𝑑 secara acak.Selanjutnya, secara iterative melakukan dua langkah berikut sampai tercapai kondisi konvergen. Langkah 1: Data assignment. Setiap data ditetapkan ke centroid terdekat dengan pemecahan hubungan apa adanya. Hasilnya berupa data yang terpartisipasi. Langkah 2: Relocation of “means”. Setiap representasi cluster direlokasi ke pusat (center) dengan rata-rata aritmetika dari semua data yang ditetapkan masuk ke dalamnya. Rasionalnya langkah ini didasarkan pada observasi bahwa dalam memberikan set titik, representasi tunggal yang terbaik untuk set tersebut (dalam hal meminimalkan jumlah kuadrat jarak Euclidean diantara setiap titik data dan representative) adalah dari rata-rata dari titik data. Hal ini jugalah yang menyebabkan metode ini sering disebut dengan cluster mean atau cluster mean atau cluster centroid, seperti nama yang dimiliki. Algoritma k-Means mencapai kondisi konvergen ketika pengalokasian kembai titik data (dan juga lokasi centroid c1) tidak lagi berubah. Proses dari iterasi higga dicapai kondisi konvergen juga dapat diamati dari nilai fungsi obyektif yang
13
didapatkan. Pada kondisi yang semakin konvergen dapat diamati bahwa nilai fungsi objekti akan semakin menurun. 2.1.4 Algoritma k-Modes Algoritma k-Means hanya dapat bekerja dengan baik untuk set data yang tipe data nya numerik (interval atau rasio), namun tidak dapat digunakan untuk fitur kategorikal (nominal atau ordinal). Untuk menyelesaikan masalah tersebut, kModes melakukan modifikasi pada k-Means sebagai berikut (Prasetyo, 2014) : 1. Menggunakan ukuran pencocokan ketidakmiripan sederhana pada fitur data bertipe kategorikal. 2. Mengganti mean cluster dengan modus (nilai yang paling sering muncul). 3. Menggunakan metode berbasis frekuensi untuk mencari modus dari sekumpulan nilai. Andaikan X dan Y adalah dua data dengan fitur bertipe kategorikal. Ukuran ketidakmiripan di antara X dan Y dapat diukur dengan jumlah ketidakcocokan nilai dari fitur yang berkorespondensi dari dua data. Semakin keil nilai ketidakcocokan, maka semakin mirip dua data tersebut. Metrik seperti ini sering disebut dengan pencocokan sederhana (simple matching) yang diusulkan oleh Kaufman dan Rousseeuw (1990) pada Prasetyo, 2014. Formula yang digunakan seperti pada persamaan berikut: 𝑑(𝑋, 𝑌) = ∑𝑟𝑗=1 ∈ (𝑥𝑗 , 𝑦𝑗 )…………… (2.2.4.1) r adalah jumlah fitur, sedangkan
( ) adalah nilai pencocokan seperti pada
persamaan berikut: ∈ (xj , yj ) = {
0 (𝑥𝑗 = 𝑦𝑗 ) ……………. (2.2.4.2) 1 (𝑥𝑗 ≠ 𝑦𝑗 )
Misalkan X adalah set data yang nilai fiturnya bertipe kategorikal, A1, A2, ...An,maka modus dari X = (X1, X2,…….. Xn) adalah data Q = (q1, q2,…….. qn) yang meminimalkan nilai seperti pada persamaan :
14
𝐷(𝑋, 𝑌) = ∑𝑛𝑖=1 𝑑 (𝑥𝑖 , 𝑄) …………… (2.2.4.4) Untuk persamaan (6.4.4), vector Q merupakan vector yang bukan bagian dari X. Andaikan 𝑛𝑐 𝑘,𝑗 adalah jumlah objek yang dimiliki oleh kategori 𝑐𝑘𝑗 ke-k pada atribut Aj dan fr(Aj= 𝐶𝑘𝑗 |X)=
𝑛𝑐 𝑘𝑗 𝑛
adalah frekuensi relatif kategori 𝑛𝑐 𝑘,𝑗 dalam X.
Maka fungsi D(X,Q) akan minimal jika fr(Aj= 𝑞𝑗 |X)≥ fr(Aj= 𝐶𝑘𝑗 |X) untuk qj≠ 𝑐𝑘𝑗 untuk semua j= 1, ….., r. Yang perlu ditekankan dalam masalah modus adalah bahwa modus dari set data X tidak bersifat unik. Misalnya modus dari set {[a,b], [a,c], [c,b], [b,c]} bisa didapat [a,b] atau [a,c]. Fungsi objektif yang digunakan dalam K-Modes seperti pada persamaan berikut: 𝐽 = ∑𝑘𝑙=1 ∑𝑛𝑖=1 ∑𝑟𝑗=1 𝑤𝑖,𝑙 ∈ (𝑥𝑖,𝑗 , 𝑞𝑙,𝑗 )……….(2.2.4.5) ∈ ( ) adalah nilai pencocokan seperti pada persamaan (8.15) antara vector dengan modus cluster yang diikuti, sedangkan 𝑤𝑖,𝑙 ∈ 𝑊 adalah nilai keanggotaan data dapat setiap cluster. 𝑤𝑖,𝑙 ∈ 𝑊 memiliki nilai [0,1] yang didapatkan dari persamaan wi,l {
1 0
𝑗𝑖𝑘𝑎 𝑑(𝑋𝑖 , 𝑄𝑙 ) < 𝑑(𝑋𝑖 , 𝑄𝑡 ), 𝑢𝑛𝑡𝑢𝑘 𝑙 = 1, … , 𝑘, 𝑢𝑛𝑡𝑢𝑘 𝑡 = 1, … , 𝑘 𝑢𝑛𝑡𝑢𝑘 𝑡 ≠ 𝑙 ……………(2.2.4.6)
k adalah jumlah cluster, sedangkan n adalah jumlah data dalam cluster. Adapun algoritma k-Modes (Prasetyo, 2014). 1. Pilih k data sebagai inisialisasi centroid (modus), satu untuk setiap cluster. 2. Alokasikan data ke cluster dengan modusnya terdekat menggunakan persamaan (6.4.1). 3. Perbarui modus (sebagai centroid) dari setiap cluster dengan nilai kategori yang sering muncul pada setiap cluster. Ulangi langkah 2 dan 3 selama masih memenuhi syarat: (1) masih ada data yang berpindah cluster, atau (2) perubahan nilai fungsi objektif masih di bawah ambang batas yang ditentukan.
15
2.1.5 Metode Inisialisasi Untuk Mencari Centroid Awal pada k-Modes 2.1.6 Metode Pengembangan Perangkat Lunak Waterfall Metode pengembangan perangkat lunak Waterfall merupakan salah satu model proses perangkat lunak yang mengambil kegiatan proses dasar seperti spesifikasi, pengembangan, validasi, dan evolusi. Model ini kemudian merepresentasikannya ke dalam bentuk fase-fase proses yang berbeda seperti analisis dan pendefinisian kebutuhan, perancangan perangkat lunak, implementasi, pengujian unit, integrasi sistem, pengujian sistem, serta operasi dan pemeliharaan (Sommerville, 2003).
Gambar 2.2 Model Metodologi Waterfall (Sumber : Sommerville, 2003) Adapun penjelasan tahapan-tahapan dari model waterfall yang ditunjukkan pada gambar 1 menurut Sommerville (2003) adalah sebagai berikut : 1. Analisis dan Penentuan Kebutuhan Merupakan tahap pengumpulan informasi mengenai kebutuhan sistem yang didapat dari pengguna (user). Proses ini mendefinisikan secara rinci mengenai fungsi-fungsi, batasan dan tujuan dari perangkat lunak sebagai spesifikasi sistem.
2. Desain Sistem dan Perangkat Lunak Tahap desain merupakan tahap yang melibatkan proses perancangan sistem yang difokuskan pada empat atribut, yaitu struktur data, arsitektur perangkat lunak,
16
representasi antarmuka, dan detail (algoritma) prosedural. Yang dimaksud struktur data adalah representasi dari hubungan logis antara elemen-elemen data individual.
3. Implementasi dan Pengujian Pada tahap ini, perancangan perangkat lunak direalisasikan sebagai serangkaian program atau unit program. Kemudian proses pengujian melibatkan verifikasi bahwa setiap unit program telah memenuhi kebutuhan yang telah didefinisikan pada tahap pertama.
4. Integrasi dan Uji Coba Sistem Unit program/program individual diintegrasikan menjadi sebuah kesatuan sistem dan kemudian dilakukan pengujian. Dengan kata lain, pengujian ini ditujukan untuk menguji keterhubungan dari tiap-tiap fungsi perangkat lunak sudah memenuhi kebutuhan. Setelah pengujian sistem selesai dilakukan, perangkat lunak dikirim kepada pelanggan/user.
5. Operasi dan Pemeliharaan Sistem Tahap ini biasanya memerlukan waktu yang paling lama, di mana sistem diterapkan dan digunakan. Pemeliharaan mencakup proses pengoreksian beberapa kesalahan yang tidak ditemukan pada tahap-tahap sebelumnya ataupun penambahan kebutuhan-kebuthan baru yang diperlukan.
2.1.7 Functional Decomposition Diagram (FDD) Functional Decomposition Diagram atau disingkat dengan isitlah FDD merupakan sebuah representasi top-down (disajikan dalam bentuk hirarki) dari sebuah fungsi atau proses dari suatu sistem (Rosenblatt, 2013:140). Menurut Rosenblatt dengan menggunakan FDD, suatu analis sistem dapat menunjukkan proses bisnis dan memecahnya kembali menjadi beberapa tingkatan fungsi atau proses yang lebih detail yang hampir mirip dengan sebuah struktur organisasi. 2.1.8 Data Flow Diagram (DFD) Menurut Rosenblatt (2013) DFD merupakan sebuah diagram yang merepresentasikan bagaimana suatu sistem menyimpan, memproses, dan mentransformasi suatu data. Diagram konteks adalah diagram yang terdiri dari suatu proses dan menggambarkan ruang lingkup suatu sistem. Diagram konteks
17
merupakan level tertinggi dari DFD yang menggambarkan seluruh input ke sistem atau output dari sistem. Diagram konteks akan memberi gambaran tentang keseluruan sistem. Sistem dibatasi oleh boundary (dapat digambarkan dengan garis putus). Dalam diagram konteks hanya ada satu proses. Tidak boleh ada store dalam diagram konteks. Data Flow Diagram (DFD) adalah suatu diagram yang menggunakan notasinotasi untuk menggambarkan arus dari data sistem, yang penggunaannya sangat membantu untuk memahami sistem secara logika, tersruktur dan jelas. DFD merupakan alat bantu dalam menggambarkan atau menjelaskan proses kerja suatu sistem. DFD sering digunakan untuk menggambarkan suatu sistem yang telah ada atau sistem baru yang akan dikembangkan secara logika tanpa mempertimbangkan lingkungan fisik di mana data tersebut mengalir(misalnya lewat telepon, surat dan sebagainya) atau lingkungan fisik di mana data tersebut akan disimpan (misalnya file kartu, microfiche, hard disk, tape, diskette, dll). DFD merupakan alat yang digunakan pada metodologi pengembangan sistem yang terstruktur (structured analysis and design)
Gambar 2.3 Simbol-simbol pada DFD
18
2.1.9 Evaluasi Cluster Menggunakan Silhoutte Index Silhouette Index (SI) dapat digunakan untuk melakukan validasi terhadap sebuah data, cluster tunggal (satu cluster dari sejumlah cluster), atau bahkan keseluruhan cluster. Metode ini yang paling banyak digunakan untuk memvalidasi cluster yang menggabungkan nilai kohesi dan separasi. Untuk menghitung nilai SI dari sebuah data ke-i, ada 2 komponen yaitu ai dan bi. ai adalah rata-rata jarak data ke-i terhadap semua data lainnya dalam satu cluster, dan bi didapatkan dengan menghitung rata-rata jarak data ke-i terhadap semua data dari cluster yang lain tidak dalam satu cluster dengan data ke-i, kemudian diambil yang terkecil (Tan et al, 2006, Petrovic, 2003 pada Prasetyo, 2014: 283-284). 𝑗
Berikut formula untuk mnghitung 𝑎𝑖 : 𝑗
𝑎𝑖 = 𝑗
1 𝑚𝑖 −1
𝑚
𝑗 𝑗 𝑗 ∑𝑟=1 𝑑(𝑥𝑖 , 𝑥𝑟 ),
𝑖 = 1,2, … , 𝑚𝑗 …………………………..(6.7.1)
𝑟≠𝑖
𝑗
𝑑(𝑥𝑖 , 𝑥𝑟 ) adalah jarak data ke-i dengan data ke-r dalam satu cluster j, sedangkan mj adalah jumlah dalam cluster ke-j. 𝑗
Berikut formula untuk meghitung 𝑏𝑖 : 1
𝑚𝑛 𝑗 𝑗 𝑏𝑖 = 𝑚𝑖𝑛𝑛=1,…,𝑘 {𝑚 ∑𝑟=1 𝑑(𝑥𝑖 , 𝑥𝑟𝑛 )}, 𝑛≠𝑗
𝑛
𝑗
Untuk mendapatkan 𝑆𝐼𝑖 =
𝑖 = 1,2, … , 𝑚𝑛 …………….(6.7.2)
𝑟≠𝑖
𝑗
𝑗
𝑏𝑖 −𝑎𝑖 𝑗
𝑗
……………………….(6.7.3)
max{𝑎𝑖 , 𝑏𝑖 }
Nilai ai mengukur seberapa tidak mirip sebuah data dengan cluster yang diikutinya, nilai yang semakin kecil menandakan semakin tepatnya data tersebut berada dalam cluster tersebut. Nilai bi yang besar menandakan bahwa data tersebut semakin tepat berada daam cluster tersebut. Nilai SI negative (ai>bi) menandakan bahwa data tersebut tidak tepat berada dalam cluster tersebut (karena lebih dekat dengan cluster yang lain). SI bernilai 0 (atau mendekati 0) berarti data tersebut posisinya berada di perbatasan di antara dua cluster.
19
Untuk nilai SI dari sebuah cluster didapatkan dengan menghitung rata-rata nilai SI semua data yang bergabung dalam cluster tersebut, seperti pada persamaan berikut: 𝑚
1
𝑗 𝑗 𝑆𝐼𝑗 = m ∑𝑗=1 𝑆𝐼𝑖 ……………………….(6.7.4) j
Seentara nilai SI global didapatkan dengan menghitung rata-rata nilai SI dari semua cluster seperti pada persamaan berikut: 1
𝑆𝐼 = k ∑𝑘𝑗=1 𝑆𝐼𝑗 ……………………….(6.7.5) k adalah jumlah cluster. 2.1.10 Strategi Pengujian Perangkat Lunak Menurut Everret, G.D. dan McLeod R. strategi pengujian perangkat lunak dapat di bagi menjadi 4 bagian utama yaitu Static Testing, White Box Testing, Black Box Testing, dan Performance Testing. 2.1.10.2 Black Box Testing Black Box Testing atau dikenal sebagai “Behaviour Testing” merupakan suatu metode pengujian yang digunakan untuk menguji executable code dari suatu perangkat lunak terhadap perilakunya. Pendekatan Black Box Testing dapat dilakukan jika sudah ada executable code. Orang-orang yang terlibat dalam Black Box Testing adalah tester, end-user, dan developer. Tester merencanakan keahlian eksekusi pada negative dan positive black box testing. End-user memiliki pengetahuan bagaimana perilaku bisnis yang tepat dan sesuai dengan ekspektasi, dan developer memiliki pengetahuan tentang perilaku bisnis yang di implementasikan pada perangkat lunak. Tester melakukan black box testing bersama end-user dan developer memvalidasi hasil yang diharapkan dengan hasil pengujian. Jika hasil pengujian tidak sama dengan ekspektasi maka developer harus memperbaiki kesalahan tersebut baik itu pada spesifikasi maupun implementasi.
20
2.2 Tinjauan Empiris Pada penelitian ini, peneliti menggunakan beberapa penelitian terkait yang pernah dilakukan oleh peneliti lain sebagai tinjauan studi, yaitu sebagai berikut : 1. Extension to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values. (Huang, Z. 1998). Pada penelitian ini, penulis mengembangkan sebuah algoritma baru dari algoritma k-Means yang digunakan untuk melakukan proses clustering pada data yang memiliki nilai kategorikal yang diberi istilah k-Modes. Hasil yang diperoleh dari penelitian ini membuktikan bahwa algoritma k-Modes mampu melakukan proses clustering pada data set kategorikal yang besar secara efisien. 2. Clustering Categorical Data with k-Modes. (Huang, Z. 2009). Pada penelitian ini, penulis menjabarkan hasil pengembangan algoritma kModes untuk melakukan proses clustering pada data dengan nilai kategorikal dengan
sedikit
perubahan
pada
proses
perhitungan
ketidaksamaan
(dissimilarity) menggunakan fungsi yang didefinisikan oleh Ng, Li, Huang & He, 2007. 3. Attribute Value Weighting in k-Modes Clustering. (Zengyou He, Xiaofei Xu, & Shengchun Deng, 2011). Pada penelitian ini, penulis mengajukan sebuah metode baru dalam proses perhitungan ketidaksamaan pada bagian algoritma k-Modes. Metode yang dikembangan adalah weighted dissimilarity measure menggantikan perhitungan simple matching pada algoritma k-Modes yang asli. Adapun persamaan yang digunakan pada metode weighted dissimilarity measure terdapat pada pemaparan sebagai berikut : 1 − 𝜔(𝑥𝑖𝑗 ), 𝑥𝑗 = 𝑦𝑗 𝑑𝑤 (𝑥𝑖𝑗 , 𝑦𝑖𝑗 ) = { …………………………. (2.2.1) 1, 𝑥𝑗 ≠ 𝑦𝑗 Dimana : 𝜔(𝑥𝑖𝑗 ) = 1 − ∑𝑥 (𝑡) ∈ 𝑀(𝑥 𝑖𝑗
(𝑡) (𝑡) 𝑓(𝑥𝑖𝑗 |𝐷 )(𝑓(𝑥𝑖𝑗 |𝐷 )−1) 𝑖𝑗 )
𝑛(𝑛−1)
.............….(2.2.2)
21
(𝑡)
(𝑡)
dengan syarat : 𝑀(𝑥𝑖𝑗 ) = { 𝑥𝑖𝑗 | 𝑓(𝑥𝑖𝑗 |𝐷) ≤ 𝑓(𝑥𝑖𝑗 |𝐷) } Dmiana D adalah set (𝑡)
data yang memiliki m atribut kategorikal. 𝑓(𝑥𝑖𝑗 |𝐷) adalah frekuensi kemunculan (𝑡)
nilai atribut 𝑥2𝑗 pada dataset dan 𝑓(𝑥2𝑗 |𝐷) adalah frekuensi kemunculan nilai atribut 𝑥2𝑗 pada dataset.
