BAB II TINJAUAN PUSTAKA 2.1 Sistem Informasi Klasifikasi Tingkat Prestasi Mahasiswa Berdasarkan Seleksi Ujian Masuk Ke Perguruan Tinggi. Sistem informasi klasifikasi tingkat prestasi mahasiswa berdasarkan seleksi ujian masuk ke perguruan tinggi dengan algoritma k-means dari teknik clustering adalah sistem informasi yang nantinya mengelompokkan data mahasiswa berdasarkan tingkat prestasi dan jalur masuk ke perguruan tinggi. Sistem ini bertujuan untuk mengklasifikasikan tingkat prestasi mahasiswa berdasarkan seleksi ujian masuk ke perguruan tinggi sehingga dapat dijadikan acuan dalam menganalisa, memahami dan memvisualisasikan data tingkat prestasi mahasiswa, serta dapat dijadikan acuan dalam proses penerimaan mahasiswa baru. Sistem dapat membaca data set tingkat prestasi mahasiswa dan jenis ujian masuk ke perguruan tinggi. Sistem dapat mengklasifikasikan dengan menggunakan algoritma k-means, teknik clustering berdasarkan tingkat prestasi mahasiswa dan jenis ujian masuk ke perguruan tinggi. Berdasarkan data yang dibaca, akan dihasilkan grafik tingkat prestasi mahasiswa berdasarkan seleksi ujian masuk ke perguruan tinggi. Sistem informasi klasifikasi tingkat prestasi mahasiswa berdasarkan seleksi ujian masuk ke perguruan tinggi dengan teknik clustering diharapkan dapat dijadikan acuan dalam menganalisa, memahami serta memvisualisasikan data tingkat prestasi mahasiswa yang nantinya menjadi acuan dalam proses penerimaan mahasiswa baru. 2.2 Data Mining. Perkembangan data mining (DM) yang pesat tidak dapat lepas dari perkembangan teknologi informasi yang memungkinkan data dalam jumlah besar terakumulasi. Sebagai contoh, toko swalayan merekam setiap penjualan barang dengan memakai alat POS (point of sales). Database data penjualan tersebut bisa

4

5

mencapai beberapa GB setiap harinya untuk sebuah jaringan toko swalayan berskala nasional. Perkembangan internet juga punya andil cukup besar dalam akumulasi data. Tetapi pertumbuhan yang pesat dari akumulasi data itu telah menciptakan kondisi yang sering disebut sebagai rich of data but poor of information karena data yang terkumpul itu tidak dapat digunakan untuk aplikasi yang berguna. Tidak jarang kumpulan data itu dibiarkan begitu saja seakan-akan kuburan data (data tombs) (Iko, 2003:1). DM itu sendiri adalah serangkaian proses untuk menggali nilai tambah berupa pengetahuan yang selama ini tidak diketahui secara manual dari suatu kumpulan data. Mining berarti usaha untuk mendapatkan sedikit barang berharga dari sejumlah besar material dasar. Karena itu DM sebenarnya memiliki akar yang panjang dari bidang ilmu seperti kecerdasan buatan (artificial intelligent), machine learning, statistic dan database (Iko, 2003:1). Definisi sederhana dari data mining adalah ekstraksi informasi atau pola yang penting atau menarik dari data yang ada di database yang besar (Yudho, 2003:1). Dalam jurnal ilmiah, data mining juga dikenal dengan nama Knowledge Discovery in Databases (KDD). Menurut Taufik Abidin, data mining atau juga dikenal dengan sebutan knowledge discovery in database lahir karena data yang terkumpul sekarang ini sudah mencapai terrabyte (1000 gigabytes). Data mining merupakan proses mencari pola-pola menarik dalam data. Beberapa teknik yang sering disebut-sebut dalam literatur DM antara lain : Clustering, Classification, Association Rule Mining (ARM), Neural Network, Genetic Algorithm dan lain-lain. 2.3 Classification. Classification adalah proses untuk menemukan model atau fungsi yang menjelaskan atau membedakan konsep atau kelas data, dengan tujuan untuk dapat memperkirakan kelas dari suatu objek yang labelnya tidak diketahui. Model itu sendiri bisa berupa aturan jika-maka, berupa decision tree, formula matematis atau neural network. Decision tree adalah salah satu metode classification yang paling populer karena mudah untuk diinterpretasi oleh manusia. Algoritma decision tree yang

6

paling terkenal adalah C4.5, tetapi akhir-akhir ini telah dikembangkan algoritma yang mampu menangani data skala besar yang tidak dapat ditampung di main memori seperti RainForest. Metode-metode classification yang lain adalah Bayesian, neural network, genetic algorithm, fuzzy, case-based reasoning, dan k-nearest neighbor. Proses classification biasanya dibagi menjadi dua fase : learning dan test. Pada fase learning, sebagian data yang telah diketahui kelas datanya diumpankan untuk membentuk model perkiraan. Kemudian pada fase test model yang sudah terbentuk diuji dengan sebagian data lainnya untuk mengetahui akurasi dari model tsb. Bila akurasinya mencukupi model ini dapat dipakai untuk prediksi kelas data yang belum diketahui. 2.4 Clustering. Berbeda dengan association rule mining dan classification dimana kelas data telah ditentukan sebelumnya, clustering melakukan pengelompokan data tanpa berdasarkan kelas data tertentu. Clustering dapat didefinisikan sebagai proses mengelompokkan sekumpulan objek sedemikian hingga objek dalam satu grup lebih serupa karakteristiknya dibandingkan dengan objek-objek di grup-grup yang lain. Bahkan clustering dapat dipakai untuk memberikan label pada kelas data yang belum diketahui. Karena itu clustering sering digolongkan sebagai metode unsupervised learning. Analisa grup sangat bermanfaat untuk mengetahui dan memahami distribusi data dan sering sekali digunakan sebagai proses awal sebelum teknik-teknik data mining lain digunakan. Prinsip dari clustering adalah memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan kesamaan antar kelas atau cluster. Clustering dapat dilakukan pada data yang memiliki beberapa atribut yang dipetakan sebagai multidimensi. Secara garis besar teknik-teknik clustering dapat dikategorikan dalam 2 kelompok. Teknik clustering berdasarkan hirarki (hierarchy-based) dan berdasarkan partisi (Distance-based). Banyak algoritma clustering memerlukan fungsi jarak untuk mengukur kemiripan antar data, diperlukan juga metode untuk normalisasi bermacam atribut yang dimiliki data. Beberapa kategori algoritma clustering yang banyak dikenal adalah metode partisi dimana pemakai harus

7

menentukan jumlah k partisi yang diinginkan lalu setiap data dites untuk dimasukkan pada salah satu partisi. 2.4.1 Hierarchy-based clustering Hierarchy-based clustering terbagi menjadi 2 jenis yaitu agglomerative dan divisive. Pendekatan secara agglomerative (bottom-up) memulai clustering dengan mengambil setiap objek sebagai objek yang terpisah satu sama lainnya dan menggabungkannya satu persatu berdasarkan suatu metric (measurement) atau lebih singkatnya menggabungkan cluster kecil menjadi cluster lebih besar. Sebaliknya, divisive (top-down) memulai clustering dengan menganggap bahwa semua objek berada dalam satu cluster kemudian memecahkannya satu persatu sehingga pada akhirnya setiap objek merupakan suatu cluster tersendiri atau dengan kata lain memecah cluster besar menjadi cluster yang lebih kecil. Kelemahan metode ini adalah bila salah satu penggabungan atau pemecahan dilakukan pada tempat yang salah, tidak akan didapatkan cluster yang optimal. Sebuah pohon struktur data yang disebut dendrogram, dapat digunakan untuk mengilustrasikan teknik Hierarchical Algorithm dan pengaturan dari clusters yang berbeda. Akar didalam pohon dendrogram mengandung satu cluster dimana semua elemen menjadi satu elemen cluster. Simpul internal dalam dendrogram mewakili cluster baru yang dibentuk melalui penggabungan cluster yang muncul sebagai anaknya didalam pohon. Masing-masing level didalam pohon adalah dihubungkan dengan ukuran jarak yang digunakan untuk menggabungkan cluster. Semua cluster dihasilkan pada level utama yang dirangkaikan karena anak cluster memiliki jarak antara mereka kurang dari jarak nilai yang dihubungkan dengan level ini dalam pohon. Teknik hierarchical baik dijajarkan untuk banyak aplikasi clustering yang memang menunjukkan hubungan antara clusters. Sebagai contoh dalam biologi taksonomi, tanaman dan hewan dapat dengan mudah dipandang sebagai hierarchy dari cluster. 2.4.1.1 Agglomerative Algorithm. Agglomerative Algorithm dimulai dengan item individu masing-masing cluster-nya dan dengan pengulangan penghubungan cluster sampai semua item

8

termasuk ke dalam satu clusters. Agglomerative Algorithm berbeda dalam bagaimana cluster dihubungkan pada masing-masing level. Diasumsikan bahwa set dari elemen dan jarak antara mereka diberikan masukan. Digunakan n*n vertex adjacency matrix, A, sebagai input. Di sini adjacency matrix, A, berisi suatu nilai jarak, bukan suatu boolean sederhana: A[I,j] = dis(ti,tj). Output dari algoritma ini adalah dendrogram. DE, yang mewakili sebagai set dari 3 persamaan (d,k,K) dimana d adalah jarak ambang pintu, k adalah jumlah cluster, dan K adalah set dari cluster. Pengeluaran dendrogram menghasilkan set dari banyak cluster bukan hanya satu clustering. Pemakai dapat menentukan yang mana dari cluster (berdasarkan jarak ambang pintu) yang diharapkan untuk digunakan. Algoritma ini menggunakan procedure yang disebut NewCluster untuk menentukan bagaimana untuk kreasi level berikutnya dari cluster dari level sebelumnya. Teknik single link, complete link, dan average link merupakan yang paling terkenal diantara teknik agglomerative berdasarkan konsep teori graph terkenal. Agglomerative Algorithm.Input: D={t1, t2,.tn} //set of element A // Adjacency matrix showing distance between elements Output: DE //Dendogram represented as a set of ordered triples Agglomerative algorithm: d = 0; k = n; K={{ t1}.{tn}}; DE = (d,k,K); // initially dendrogram contains each element in its own cluster M = MST(A); repeat oldk = k; d = d + 1; ad = Vertex adjacency matrix for graph with threshold distance of d; (k,K) = NewCluster(Ad,D); If oldk k then DE = DE (d,k,K); //New set of clusters added to dendogram until k = 1

9

Semua algoritma mendekati pengalaman pelanggaran waktu dan ruang penemuanan. Ruang yang dikehendaki untuk adjacency matrik adalah O(n2) dimana n item untuk cluster. Karena pengulangan pembawaan dari algoritma, matrik harus diakses berulang kali. Algoritma diatas mengerjakan pengujian maxd dari matrik, dimana maxd adalah jarak terlebar diantara 2 poin. Ditambahkan, kelengkapan procedure New Clusters bisa jadi mahal. Ini berpotensi menjadi masalah menjengkelkan di dalam database yang besar. Keputusan lainnya dengan pendekatan agglomerative yaitu tidak ada penambahan. Jadi, saat elemen baru ditambahkan atau salah satu yang tua dipindahkan atau diganti, semua algoritma harus diulang. a. Single Link Algorithm. Teknik single link berdasarkan ide penemuan maksimal dihubungkan komponen dalam grafik. Komponen penghubung adalah suatu grafik yang ada jalan kecil antara 2 puncak. Dengan pendekatan single link 2 cluster dihubungkan jika sedikitnya ada 2 ujung yang mengubungkan 2 clusters; yaitu jika jarak minimum antara 2 point kurang dari atau sama ke jarak ambang pintu. Untuk alasan ini, sering disebut nearest neighbor teknik clustering. Single link algorithm dicapai melalui mengganti New Cluster Procedure dalam agglomerative algoritma dengan procedure untuk menghubungkan komponen dari graph, kita menerima bahwa procedure untuk menghubungkan komponen dari grafik. Pendekatan single link sangat sederhana, tetapi memiliki beberapa masalah. Algoritma ini sangat tidak efisien karena penghubung komponen, yang sebuah ruang O(n2) dan time algorithms yang disebut pada masing-masing pengulangan. Efisiensi algoritma dapat dikembangkan melalui melihat pada cluster yang mana dari level yang lebih dekat dapat dihubungkan pada setiap langkah. Masalah lain yaitu clustering menghasilkan cluster dengan rantai yang panjang. Pandangan lain untuk menghubungkan cluster dalam pendekatan single link yaitu 2 cluster dihubungkan pada tingkatan dimana jarak ambang pintu yaitu d jika jarak minimum antara suatu puncak dalam 1 cluster dan suatu puncak pada cluster yang lainnya yaitu paling banyak pada d.

10

Terdapat variasi lain dari single link algoritma satu variasi, berdasarkan penggunaan minimum spanning tree (MST), ditunjukkan dalam algoritma 8. disini menerima bahwa sebuah procedure, MST, menghasilkan sebuah minimum spanning tree diberikan sebuah adjacency matrik sebagai input. Cluster dihubungkan dalam menambah jarak kelas ditemukan dalam MST. Dalam algoritma kita melihat bahwa sekali-kali cluster dihubungkan, jarak antara mereka dalam pohon menjadi tak terhingga dengan alternative, kita dapat mengganti 2 titik dan ujung dalam satu titik. Single Link Algorithm.Input: D={t1, t2,.tn} A Output: DE MST single link algorithm: d = 0; k = n; K={{ t1}.{tn}}; DE = (d,k,K); cluster M = MST(A); repeat oldk = k; Ki,Kj = two clusters closest together in MST; k = oldk 1; d = dis(Ki,Kj); DE = DE (d,k,K); //New set of clusters added to dendogram dis(Ki,Kj) = ; until k = 1 //set of element // Adjacency matrix showing distance between elements //Dendogram represented as a set of ordered triples

// initially dendrogram contains each element in its own

Pendekatan single link yang tidak bagus untuk efek rantainya, yaitu 2 cluster dihubungkan jika hanya 2 dari titik mereka dekat dengan yang lainnya. Itu mungkin titik-titik dalam cluster masing-masing dihubungkan pada bagian yang jauh, tetapi ini tidak berakibat pada algoritma. Jadi, akibatnya cluster mungkin memiliki titik yang tidak sesuai dengan yang lain dalam semuanya, tetapi hanya terjadi untuk titik yang dekat dengan yang lainnya.

11

b. Complete Link Algorithm Walaupun Complete link algorithm sama dengan single link algorithm, mencari hubungan bukannya komponen yang dihubungkan. Cliques adalah grafik maksimal yang mana terdapat sebuah ujung antara 2 puncak. Disini, procedure digunakan untuk menemukan jarak maksimum antara suatu cluster sehingga 2 cluster dihubungkan jika jarak maksimum kurang dari atau sama dengan jarak ambang pintu. Dalam algoritma ini, menerima keadaan procedure, clique yang menemukan semua cliques dalam sebuah grafik. Cluster ditemukan dengan complete link method lebih ringkas dibandingkan dengan single link method. Variasi dari complete link algorithm disebut farthest neighbor algorithm. Disini cluster terdekat dihubungkan dimana jarak adalah ukuran terkecil dengan melihat pada jarak maksimum antara 2 titik. c. Average Link Algorithm Teknik average link menghubungkan 2 cluster jika jarak rata-rata antara 2 titik dalam 2 sasaran cluster dibawah jarak ambang pintu. Algoritma digunakan disini adalah sedikit berbeda dari yang ditemukan dalam single link dan complete link, karena kita harus menguji complete graph (tidak hanya threshold graph) pada setiap tingkatan. Average Link Algorithm.Input: D={t1, t2,.tn} //set of element A // Adjacency matrix showing distance between elements Output: DE //Dendogram represented as a set of ordered triples Average link algorithm: d = 0; k = n; K={{ t1}.{tn}}; DE = (d,k,K); // initially dendrogram contains each element in its own cluster M = MST(A); repeat oldk = k; d = d + 0.5; for each pair of Ki,Kj K do ave = average distance between all ti Ki and tj Kj ;

12

if ave d, then K =K-{Ki}-{Kj} {Ki Kj}; k = oldk 1; DE = DE (d,k,K); //New dendogram until k = 1

set

of

clusters

added

to

Note : dalam algoritma ini kita tambahkan d dengan 0,5 bukannya dengan 1. ini merupakan putusan semaunya berdasarkan pemahaman dari data. 2.4.1.2 disivise algorithm Dengan divisive clustering, semua item mulanya ditempatkan pada 1 cluster dan cluster-cluster yang diubah membelah menjadi 2 sampai semua item dalam cluster-nya sendiri. Paham ini untuk membagi cluster dimana beberapa elemen tidak cukup dekat dengan elemen lainnya. Satu contoh sederhana dari divisive algorithm adalah berdasarkan versi MST (Minimum Spanning Tree) dari single link algorithm. Disini, bagaimanapun kita potong ujung dari MST dari terbesar sampai terkecil. 2.4.2 Nonhierarchical or partitional-based clustering Nonhierarchical atau partitional clustering membuat clusters dalam satu langkah sebagai lawan dari beberapa langkah. Hanya satu set clusters yang dibuat, walaupun beberapa set berbeda dari cluster mungkin dibuat secara internal dengan berbagai algoritma. Masalah dengan algoritma partitional adalah mereka berbeda dari combinatorial explosion dalam kaitan dengan banyaknya kemungkinan pemecahan masalah. 2.4.2.1 Minimum Spanning Tree (MST) Selain algoritma agglomerative dan divisive berdasarkan pada penggunaan MST, juga ada partitional MST algorithm. Ini merupakan pendekatan yang sangat sederhana yang menggambarkan bagaimana algoritma partitional bekerja. Karena masalah clustering adalah untuk menggambarkan suatu pemetaan, output dari algoritma ini menunjukkan cluster sebagai satuan pasangan dipesan (ti,j), dimana f(ti) = Kj.

13

Partitional MST Algorithm. Input: D = (t1, t2,...,tn) A K Output: F Partitional MST algorithm: M = MST(A) identify inconsistent edges in M; remove k-1 inconsistent edges; create output representation; // Mapping represented as a set of ordered paire // Adjacency matrix showing distance between elements // Number of desired clusters

2.4.2.2 Squared Error Clustering Algorithm Squared Error Clustering Algorithm memperkecil squared error. Squared error for the cluster adalah penjumlahan jarak Euclidean yang squared antar unsur-unsur dalam cluster dan cluster centroid, Ck. Squared Error Clustering Algorithm.Input: D= (t1, t2,...,tn) Output: K // Set Of clusters Squared error algorithm: Assign each item t1 to the cluster; Calculate center for each cluster; Repeat Assign each item t1 to the cluster which has the closest center; Calculate new center for each cluster; Calculate squared error; Until the difference between successive squared errors Is below a threshold; // Set of elements

2.4.2.3 K-means Clustering K-means adalah suatu iterasi algoritma clustering dimana items dipindahkan antar set clustering sampai set yang diinginkan tercapai.

14

2.4.2.4 Nearest Neighbor Algorithm. Suatu algoritma yang serupa dengan teknik single link disebut algoritma nearest neighbor. Dengan algoritma ini, items penggabungan iterasi dalam cluster yang terdekat. Dalam algoritma ini ambang pintu, t, digunakan untuk menentukan jika item akan dimasukkan ke cluster atau jika suatu cluster baru dibuat. Nearest Neighbor Algorithm.Input: D= (t1, t2,...,tn) A Output: K // Set of clusters Nearest neighbor algorithm: K1 = {t1}; K = {K1}; k = 1; for i = 2 to n do find the tm in some cluster Km in k such that dis (ti, tm) is the smallest; if dis(ti, tm), t then Km= Km ti else K= k + 1; Kk= (ti); // Set of elements // Adjacency matrix showing distance between elements

2.4.2.5 PAM (Partitional Arround Medoids) Algorithm Algoritma PAM biasanya disebut algoritma K-medoids, membuat suatu cluster dengan suatu medoid. Penggunaan suatu medoid adalah suatu pendekatan yang menangani outlier dengan baik. Partitional Arround Medoids Algorithm.Input: D = (t1, t2,...,tn) A k Output: K // Set of clusters PAM algorithm: arbitrarily select k medoids from D; repeat for each th not a medoid do for each medoid ti do // Set of elements // Adjacency matrix showing distance between elements // Number of desired clusters

15

calculate TCih; find i.h where TCih is the smallest; if TCih < 0, then replace medoid ti with th; until TCih 0: for each ti D do assign ti to Kj, where dis (ti.tj) is the smallest over all medoids;

2.4.2.6 Bond Energy Algorithm (BEA). BEA telah dikembangkan dan digunakan dalam area desain database untuk menentukan bagaimana cara menggolongkan data dan bagaimana cara fisik menempatkan data pada suatu disk. Dengan BEA, affinity (bond) antar database didasarkan pada pemakaian umum. Bond digunakan oleh algoritma clustering sebagai persamaan ukur. Ukuran yang nyata menghitung seringnya atribut keduanya digunakan bersama-sama dalam waktu yang ditentukan. Langkahlangkah dasar algoritma ini adalah: 1. buat suatu matrik atribut dimana masing-masing masukan menandai adanya hubungan antar dua rekanan. Isi persamaan matrik didasarkan pada frekuensi dari pemakaian pasangan atribut umum. 2. BEA kemudian mengkonversi persamaan matrik ke matrik BOND dimana masukan menghadirkan suatu jenis paling dekat yang mengikat didasarkan pada co-access. 3. terakhir, perancang gambar kotak di sekitar daerah matrik dengan persamaan tinggi. 2.4.2.7 Clustering with Genetic Algorithms. Untuk menentukan bagaimana cara melaksanakan cluster dengan algoritma genetika, pertama harus menentukan bagaimana cara menghadirkan masingmasing cluster. Satu pendekatan sederhana adalah menggunakan suatu bit-map penyajian untuk masing-masing cluster. Clustering with Genetic Algorithms.Input: D = (t1.t2..tn) // Set of elements

16

k Output:

// Number of desired clusters

K // Set of clusters GA clustering algorithm: randomly create an initial solution; repeat use crossover to create a new solution; until termination criteria is met;

2.4.3

Clustering Large Database. Clustering algorithm yang disebutkan sebelumnya adalah beberapa teknik

clustering classic. Saat clustering digunakan dengan database dinamik, algoritma ini mungkin tidak dimiliki dengan tidak sah. Pertama, mereka semua menerima bahwa (karena kebanyakan O(n2)) cukup, ada memori utama untuk menguasai data untuk menjadi cluster dan struktur data diperlukan untuk mendukung mereka. Dengan database besar yang mengandung seribu item atau lebih, asumsi ini tidak realitis. Selain itu, penampilan I/Os selalu melalui ulangan berulang kali dari sebuah algoritma adalah sangat mahal. Karena dari pembatasan memori utama ini, algoritma tidak menimbang ke database yang besar. Hal yang lain yaitu beberapa penerimaan bahwa data semua ada hanya sekali. Teknik ini tidak memiliki dengan tidak sah untuk dinamik database teknik clustering harus sesuai untuk beradaptasi sebagai perubahan database. Algoritma dirundingkan dalam subseksi selanjutnya masing-masing ujian adalah hal yang digabungkan dengan penampilan clustering dalam sekitar sebuah database. Untuk menampilkan dengan tepat dalam database yang besar, clustering algorithm harus: 1. menghendaki tidak lebih (lebih baik kurang) dari satu pandangan teliti (scan) dari database. 2. memiliki kepandaian untuk memberi status dan jawaban terbaik hingga sekian selama algoritma berjalan. Ini kadang-kadang dimaksudkan sebagai kemampuan untuk online. 3. dapat ditunda, dapat dihentikan dan dapat disingkat 4. mampu untuk update penambahan hasil seperti data yang ditambah atau dipindahkan dari database

17

5. bekerja dengan memori utama yang dibatasi 6. jadi cakap dari penunjukan teknik berbeda untuk scanning database. 7. proses setiap tuple hanya sekali. Belakangan ini penyelidikan pada Microsoft diselidiki bagaimana untuk merapikan penampilan clustering algoritma dengan database yang lebar. Ide dasar dari pendekatan pertimbangan seperti: 1. baca subset dari database sampai memori utama 2. gunakan teknik clustering untuk data dalam memori 3. kombinasikan hasilnya dengan contoh dulu 4. data dalam memori lalu dibagi 3 tipe yang berbeda: item tersebut akan selalu dibutuhkan bahkan saat contoh selanjutnya dibawa masuk, itu dapat dibuang dengan menyediakan perkembangan untuk data yang dilindungi yang disiapkan untuk menjawab masalah, dan itu akan disimpan dalam sebuah format yang dikompres. Berdasarkan tipe, setiap item data lalu dilindungi, dihapus atau dikompres dalam memori. 5. jika batas kriteria tidak ditemukan, lalu ulang dari langkah 1. Pendekatan ini dapat digunakan untuk K-means algoritma dan bisa ditunjukkan untuk keberhasilan. 2.4.3.1 BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies). BIRCH adalah desain untuk clustering yang banyak dari data metrik. Ini diasumsikan bahwa disana mungkin dibatasi banyaknya memori utama dan mencapai sebuah linear I/O time menghendaki hanya satu database yang memandang dengan teliti. Incremental dan hierarchical ini menggunakan teknik penangangan outlier. Disini titik ditemukan dalam daerah jarang pupolasi yang dipindahkan. Ide dasar dari algoritma yaitu sebuah pohon dibangun untuk menangkap informasi yang diperlukan untuk menjalankan clustering. Clustering lalu dijalankan pada pohon tersebut, dimana penyegelan dari titik dalam pohon berisi informasi yang diperlukan untuk menghitung jarak nilai karakteristik terbesar dari algoritma BIRCH adalah penggunaan clustering feature yaitu triple yang mengandung informasi tentang suatu cluster. Clustering feature

18

menyediakan ringkasan informasi tentang 1 cluster. Melalui definisi ini jelas bahwa BIRCH digunakan hanya untuk data numerik. Algoritma ini menggunakan pohon yang disebut CF. Ukuran dari pohon ditentukan oleh nilai threshold, T, yang dihubungkan dengan setiap titik daun. Diameter maksimum yang dizinkan untuk suatu daun. Diameter ini adalah rata-rata dari jarak yang dipasangkan antara semua titik dalam cluster. Setiap titik internal bersesuaian untuk sebuah cluster yang disusun dari setiap subcluster yang diwakili oleh anaknya. Clustering feature (CF) adalah triple (N, LS, SS) dimana jumlah titik dalam cluster adalah N, LS adalah jumlah titik dalam cluster dan SS adalah jumlah persegi dari titik dalam cluster. Pohon CF adalah Pohon keseimbangan dengan cabang faktor (jumlah maksimum dari anak suatu titik yang dimiliki) B. Setiap titik internal mengandung sebuah CF triple untuk setiap anak-anaknya. Setiap titik daun juga menggambarkan sebuah cluster dan mengandung sebuah masukan CF untuk setiap subcluster didalamnya. Subcluster dalam titik daun harus memiliki diameter tidak lebih besar dari Threshold value T yang diberikan Tidak seperti dendogram, pohon CF diselidiki dalam top-down fashion. Setiap titik pohon CF mengandung clustering rencana informasi tentang subclusternya. Sebagai titik ditambahkan ke masalah clustering, pohon CF dibuat. Titik disisipkan ke dalam cluster (digambarkan oleh titik daun) untuk yang terdekat, jika diameter untuk titik daun lebih besar dari T, lalu pembagian dan kesimbangan dari pohon yang dijalankan (sama yang digunakan dalam pohon B) algoritma menyesuaikan ke ukuran memori utama melalui penggantian nilai Threshold yang lebih lebar T, menghasilkan pohon CF yang lebih kecil. Proses ini dapat dikerjakan tanpa pembacaan ulang data. Clustering feature data menyediakan cukup informasi untuk menjalankan pemadatan. Kompleksitas algoritma adalah O(N). Algoritma BIRCH.Input: D={t1, t2,.tn} //Set of element T //Threshold for CF tree construction Output: K //Set of clusters BIRCH clustering algorithm:

19for each pair of ti D do determine correct leaf node for ti insertion; if threshold condition is not violated, then add ti to clusters and update CF triples; else if room to insert ti , then insert ti as single and update CF triples; else split leaf node and redistribute CF features;

Pada kenyataanya, algoritma ini, hanya pertama dari beberapa langkah yang diajukan untuk memakai BIRCH dengan database lebar. Rencana lengkap dari langkah-langkah adalah: 1. buat permulaan pohon CF menggunakan versi yang dimodifikasi dari algoritma BIRCH. ini dalam mengerjakan muatan database kedalam memori. Jika memori tidak cukup untuk menyusun pohon CF baru yang lebih kecil disusun. Ini dapat dilakukan dengan menyisipkan titik daun dari pohon sebelumnya kedalam pohon baru yang kecil 2. clustering yang digambarkan oleh pohon CF mungkin tidak alami karena setiap pemasukkan memiliki batas ukur. Ditambahkan, input dari perintah dapat secara negatif berdampak pada hasil. Masalah tersebut dapat diatasi melalui pendekatan global clustering lainnya yang dipasang untuk titik daun dalam pohon CF. disini setiap titik daun dijamu sebagai sigle point dari clustering. Walaupun pekerjaan yang asli memproses sebuah centroidbased agglomerative hierarchical clustering menjadi cluster dari subclusters, clustering algorithm lainnya dapat digunakan. 3. pase terakhir (yang dipilih) kembalikan.semua point dengan meletakanya dalam cluster yang memiliki centroid terdekat dipindahkan selama pase ini. BIRCH adalah linear dalam sepasang ruang dan I/O time pemilihan nilai threshold menyuruh ke sebuah eksekusi efisien dari algoritma. Dengan cara lain, pohon mungkin harus membuat ulang banyak times untuk menjamin bahwa itu dapat menjadi resident memori. Ini memberikan time complexity terjelek dari O(n2).

20

2.4.3.2 DBSCAN. Pendekatan yang dilakukan melalui DBSCAN adalah untuk menghasilkan cluster dengan ukuran minimum dan density. Density dibatasi sebagai jumlah titik minimum dalam jarak pasti dari setiap yang lainnya. Ini menangani masalah outlier dengan menjamin bahwa sebuah outlier (atau set kecil dari outlier) tidak akan menghasilkan sebuah cluster. Satu input parameter, minPTS menunjukkan jumlah titik minimum dalam suatu cluster. Ditambahkan, untuk setiap titik dalam sebuah cluster harus menjadi titik lainnya dalam cluster yang berjarak dari titik tersebut kurang dari masukan nilai threshold, Eps. Eps neighborhod atau neighborhod dari titik adalah set dari titik dalam sebuah jarak Eps. Jumlah cluster yang dimaksud, k, adalah bukan masukan melainkan yang ditentukan oleh algoritma itu sendiri. Algoritma DBSCANInput: D={t1, t2,.tn} //Set of elements MinPts //Number of points in clusters Eps //Maximum distance for density measure Output: K={K1, K2,.Kn} //Set of clusters DBSCAN algorithm: k = 0; //initially there are no clusters for i = 1 to n do if ti is not in a cluster, then X = {ti | tj is density-reachable from ti}; if X is a valid cluster, then k = k + 1; Kk = X;

Time complexity yang diharapkan dari DBSCAN adalah O(n lg n). Itu mungkin bahwa border point dapat termasuk ke dalam 2 cluster. Algoritma akan menempatkan titik ini dalam cluster yang manapun yang dihasilkan pertama DBSCAN dibandingkan dengan CLARANS dan ditemukan untuk menjadi lebih efisien oleh sebuah faktor dari 205 sampai 1900. Ditambahkan, kesuksesan ditemukan semua cluster dan menyiarkan dari tes dataset, sedangkan CLARANS tidak

21

2.4.3.3 CURE (Clustering Using Representatives) Algorithm. Satu objektif untuk CURE clustering algoritma adalah menangani outlier dengan baik. Cure memiliki sepasang komponen hierarchical dan pembagian elemen. Pertama jumlah titik konstan, c, dipilih dari setiap cluster. Penanganan CURE dibatasi memori utama oleh perolehan contoh acak untuk menemukan jawaban cluster acak dibagi dan setiap bagian lalu memihak clustered hasilan cluster, lalu dilkengkapi dengan clustered dalam celah kedua. Contoh dan pembagian dilakukan hanya untuk menjamin bahwa data (tak peduli ukuran database) dapat sesuai kedalam memori utama yang tersedia. Ketika clustering dari contoh sudah lengkap dibentuk cabeling data pada disk. Item data ditunjukkan untuk cluster dengan representative point terdekat. Langkah dasar dari CURE untuk database yang besar adalah: 1. peroleh contoh dari database. 2. bagi contoh ke dalam bagian P dari luasn . Ini dilakukan untuk p

mempercepat algoritma karena clustering dibentuk pertama pada setiap bagian. 3. secara parsial cluster poin dari setiap bagian menggunakan hierarchical algoritma, ini memberikan terkaan pertama tentang apa seharusnya clusters. Jumlah cluster adalah pq untuk beberapa konstanta q 4. pindahkan outliers. Outlier dihapus oleh penggunaan 2 teknik yang berbeda. Teknik pertama menghapus cluster yang tumbuh sangat lambat. Saat jumlah cluster dibawah threshold, cluster dengan hanya 1 atau 2 item dihapus. Ini mungkin bahwa outlier yang dekat adalah bagian dari contoh dan tidak akan diteliti oleh teknik eleminasi outlier pertama. Teknik kedua memindahkan cluster yang sangat kecil terhadap akhir dari phase clustering. 5. clusters sepenuhnya pada semua data dalam contoh menggunakan Algoritma 12 disini untuk menjamin proses dalam memori utama, masukann

22

termasuk hanya cluster representative dari cluster yang ditemukan untuk setiap bagian selama sebagian langkah clustering (3) 6. clusters keseluruhan database pada disk menggunakan titik C untuk menggambarkan setiap cluster. Sebuah item dalam database ditempatkan di dalam cluster yang memiliki representative point terdekat dengannya. Set dari representative points cukup kecil untuk sesuai ke dalam memori utama sehingga setiap titik n harus dibandingkan dengan ck representative point.

Algoritma CUREInput: D={t1, t2,.tn} //Set of elements k //Desired number of clusters Output: Q //Heap containing one entry for each cluster CURE algorithm: T = build(D); Q = heapify(D); // initially build heap with one entry per item repeat u = min(Q); delete (Q, u.close); w = merge(u,v); delete(T,u); delete(T,v); insert(T,w); for each x Q do x.close = find closest cluster to x; if x is closest to w, then w.close = x; insert(Q,w); until number of nodes in Q is k;

Eksperimen yang ditunjukkan dibandingkan Cure dengan Birch dan pendekatan MST. Kualitas cluster yang ditemukan dengan Cure adalah lebih baik selama nilai penelitian faktor

berdampak pada hasil, dengan nilai antara 0.2

dan 0.7, cluster yang benar tetap ditemukan. Ketika jumlah representative point tiap cluster lebih besar dari lima, cluster yang benar selalu tetap ditemukan. Contoh acak ukuran kira-kira 2.5% dan jumlah bagian lebih besar dari 1 atau 2

23

times kiranya untuk bekerja lebih baik. Hasil dengan dataset yang besar menunjukkan bahwa CURE menimbang dengan baik dibandingkan BIRCH.

2.5 Algoritma K-Means. Seperti yang dijelaskan bagian sebelumnya, K-Means merupakan salah satu metode data clustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster. Metode ini mempartisi data ke dalam cluster sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang lain. Adapun tujuan dari data clustering ini adalah untuk meminimalisasikan objective function yang diset dalam proses clustering, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi antar cluster. Data clustering menggunakan metode K-Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut: K-means Algorithm Input: D = (t1, t2,...,tn) // Set of elements K // Number of desired clusters Output: K // Set of clusters K-means algoritma: assign initial values for means m1,m2,..mk; repeat assign each item t1 to the cluster which has the closest mean; calculate new mean for each cluster; until convergence criteria is met; 1. 2. 3. 4. Tentukan jumlah cluster Alokasikan data ke dalam cluster secara random Hitung centroid rata-rata dari data yang ada di masing-masing Alokasikan masing-masing data ke centroid/rata-rata terdekat

cluster

24

5.

Kembali ke Step 3, apabila masih ada data yang berpindah cluster

atau apabila perubahan nilai centroid. Distance space diimplementasikan dalam menghitung jarak (distance) antara data dan centroid termasuk di antaranya L1 (Manhattan/City Block) distance space[9], L2 (Euclidean) distance space[3], dan Lp (Minkowski) distance space[9]. Jarak antara dua titik x1 dan x2 pada Manhattan/City Block distance space dihitung dengan menggunakan rumus sebagai berikut: (1) dimana: p |.| : Dimensi data : Nilai absolut

Sedangkan untuk L2 (Euclidean) distance space, jarak antara dua titik dihitung menggunakan rumus sebagai berikut[3]: (2) dimana: p : Dimensi data

Lp (Minkowski) distance space yang merupakan generalisasi dari beberapa distance space yang ada seperti L1 (Manhattan/City Block) dan L2 (Euclidean), juga telah diimplementasikan. Tetapi secara umum distance space yang sering digunakan adalah Manhattan dan Euclidean. Euclidean sering digunakan karena penghitungan jarak dalam distance space ini merupakan jarak terpendek yang bisa didapatkan antara dua titik yang diperhitungkan, sedangkan Manhattan sering digunakan karena kemampuannya dalam mendeteksi keadaan khusus seperti keberadaaan outliers dengan lebih baik. Ada dua cara pengalokasian data kembali ke dalam masing-masing cluster pada saat proses iterasi clustering. Kedua cara tersebut adalah pengalokasian dengan cara tegas (hard), dimana data item secara tegas dinyatakan sebagai

25

anggota cluster yang satu dan tidak menjadi anggota cluster lainnya, dan dengan cara fuzzy, dimana masing-masing data item diberikan nilai kemungkinan untuk bisa bergabung ke setiap cluster yang ada. Kedua cara pengalokasian tersebut diakomodasikan pada dua metode Hard K-Means dan Fuzzy K-Means. Perbedaan di antara kedua metode ini terletak pada asumsi yang dipakai sebagai dasar pengalokasian. Hard K-Means Pengalokasian kembali data ke dalam masing-masing cluster dalam metode Hard K-Means didasarkan pada perbandingan jarak antara data dengan centroid setiap cluster yang ada. Data dialokasikan ulang secara tegas ke cluster yang mempunyai centroid terdekat dengan data tersebut. Pengalokasian ini dapat dirumuskan sebagai berikut: (3) dimana: ik a iv Fuzzy K-Means Metode Fuzzy K-Means (atau lebih sering disebut sebagai Fuzzy C-Means) mengalokasikan kembali data ke dalam masing-masing cluster dengan memanfaatkan teori Fuzzy. Teori ini mengeneralisasikan metode pengalokasian yang bersifat tegas (hard) seperti yang digunakan pada metode Hard K-Means. Dalam metode Fuzzy K-Means dipergunakan variable membership function, ik u , yang merujuk pada seberapa besar kemungkinan suatu data bisa menjadi anggota ke dalam suatu cluster. Pada Fuzzy K-Means yang diusulkan oleh Bezdek, diperkenalkan juga suatu variabel m yang merupakan weighting exponent dari membership function. Variabel ini dapat mengubah besaran pengaruh dari membership function, ik u, dalam proses clustering menggunakan metode Fuzzy K-Means. m mempunyai wilayah nilai m>1. Sampai sekarang ini tidak ada : Keanggotaan data ke-k ke cluster ke-i : Nilai centroid cluster ke-i

26

ketentuan yang jelas berapa besar nilai m yang optimal dalam melakukan proses optimasi suatu permasalahan clustering. Nilai m yang umumnya digunakan adalah 2. Membership function untuk suatu data ke suatu cluster tertentu dihitung menggunakan rumus sebagai berikut: (4) dimana: ik u iv m : Membership function data ke-k ke cluster ke-i : Nilai centroid cluster ke-i : Weighting Exponent

Membership function, ik u , mempunyai wilayah nilai 0 ik u 1. Data item yang mempunyai tingkat kemungkinan yang lebih tinggi ke suatu kelompok akan mempunyai nilai membership function ke kelompok tersebut yang mendekati angka 1 dan ke kelompok yang lain mendekati angka 0. 2.6 Java. Bahasa java adalah bahasa modern yang berorientasi pada objek. Java merupakan bahasa pemrograman lintas platform yang mampu berjalan diatas berbagai macam arsitektur, tanpa harus mengkompilasi ulang program yang dibuat (Ridwan Sanjaya, 2003:15). Menurut Andino Maseleno (2003,104) java merupakan bahasa pemrograman untuk menciptakan isi yang aktif dalam halaman Web, juga dapat dijalankan dalam semua komputer. Pemilihan bahasa java karena bahasa ini tidak mensyaratkan platform tertentu. 2.7 MySQL. Basisdata yang digunakan dalam Sistem informasi klasifikasi tingkat prestasi mahasiswa berdasarkan seleksi ujian masuk ke perguruan tinggi dengan algoritma k-means dari teknik clustering ini adalah MySQL yang menggunakan bahasa SQL sebagai bahasa dasar untuk mengakses databasenya. MySQL termasuk RDMS (Relational Database Management System) yang berasa dibawah

27

lisensi GNU (General Public Lisence) (Kadir, 2002:353). Dalam bahasa SQL pada umumnya informasi tersimpan dalam tabel-tabel yang secara logika merupakan struktur dua dimensi terdiri dari baris (row atau record) dan kolom (column atau field), dalam sebuah database dapat terdiri dari beberapa tabel. Penggunaan MySQL sebagai database dalam aplikasi ini dikarenakan MySQL: a. b. sangat ideal c. d. windows) e. gratis dan mudah didapat sebagai standard SQL (query) dapat berjalan di berbagai platform (unix, sebagai standar database server sebagai aplikasi kecil dan medium yang