Modifikasi algoritma maximum standard deviation reduction dan implementasinya pada graph clustering = On the modification of maximum standard deviation reduction algorithm and its Prastiwiimplementation on graph clustering / Diah Prastiwi
Diah Prastiwi;
Kiki Ariyanti Sugeng, supervisor; Titin Siswantining, supervisor; Djati Kerami, examiner; Alhadi Bustamam, examiner
([Publisher not identified]
, 2016)
|
|
ABSTRAK Graph clustering adalah pengelompokkan simpul-simpul pada suatu grafmenjadi cluster-cluster. Ada berbagai macam algoritma graph clustering yangdapat diterapkan pada graf berbobot, di antaranya adalah algoritma yang berbasisMST (Minimum Spanning Tree). Kelebihan dari algoritma graph clustering yangberbasis MST adalah mampu mendeteksi bentuk cluster yang tidak beraturan.Algoritma graph clustering berbasis MST yang dibahas dalam penelitian ini adalahMaximum Standard Deviation Reduction atau disingkat MSDR. Algoritma tersebutbersifat unsupervised, yang artinya banyaknya cluster tidak ditetapkan olehpengguna. MSDR memiliki dua tujuan. Tujuan yang pertama adalah membentukcluster-cluster dimana pada masing-masing cluster, busur-busurnya memiliki nilaibobot yang serupa. Tujuan yang kedua adalah menjaga agar banyaknya clusteryang terbentuk, tidak terlalu banyak. Pada algoritma MSDR, tujuan yang keduadipenuhi melalui suatu proses yang menggunakan regresi polinomial.Dalam penelitian ini, dilakukan modifikasi MSDR dengan menggantikanproses yang menggunakan regresi tersebut dengan suatu proses baru yang disebut?Loncatan Terbesar?, sehingga dihasilkan algoritma baru yang disebut ModifikasiMSDR atau disingkat MMSDR. Dilakukan implementasi MMSDR pada beberapagraf lengkap Euclidean, yaitu graf lengkap yang setiap simpulnya adalah titik disuatu ruang Rn dan setiap busurnya diberi bobot yang berupa jarak Euclideanantara dua titik. Kemudian dilakukan implementasi MMSDR pada graf yangmemodelkan rute penerbangan domestik di Indonesia oleh suatu maskapai X ABSTRACT Graph clustering is the grouping of vertices in a graph into clusters. There arevarious clustering algorithms for weighted graphs, for example a graph clusteringalgorithm which is based on MST (minimum spanning tree). The advantage ofMST-based clustering is that it allows the detection of clusters with irregularboundaries. An MST-based clustering known as MSDR (Maximum StandardDeviation Reduction) is studied in this research. MSDR is an unspervisedclustering, in which the number of clusters is not dictated by the user. There aretwo goals of MSDR. The first goal is to produce clusters such that in each clusterthe edges have similar weights. The second goal is to prevent the formation of toomany clusters. In MSDR, the second goal is met through a process that usespolynomial regression.In this research, MSDR is modified by replacing the process that usespolynomial regression with a new process that is called ?largest jump?. A newalgorithm is produced, which is called Modified MSDR (MMSDR). MMSDR isimplemented on several complete Euclidean graphs, where a Euclidean graph is agraph whose vertices are points in a space Rn and the weight of an edge is thedistance between the endpoints. MMSDR is also implemented on a graph thatmodels domestic flight routes in Indonesia of an unidentified airline X.As a validation, MMSDR is tested on several Euclidean data, and the result iscompared to visually-identified clusters. Afterwards, MMSDR is implemented ona graph that models the domestic flight routes of an airline in Indonesia |
 T46519-Diah Prastiwi.pdf :: Unduh
|
| No. Panggil : | T46519 |
| Entri utama-Nama orang : | |
| Entri tambahan-Nama orang : | |
| Entri tambahan-Nama badan : | |
| Subjek : | |
| Penerbitan : | [Place of publication not identified]: [Publisher not identified], 2016 |
| Program Studi : |
| Bahasa : | ind |
| Sumber Pengatalogan : | LibUI ind rda |
| Tipe Konten : | text |
| Tipe Media : | unmediated ; computer |
| Tipe Carrier : | volume ; online resource |
| Deskripsi Fisik : | xiii, 83 pages : illustration ; 28 cm + appendix |
| Naskah Ringkas : | |
| Lembaga Pemilik : | Universitas Indonesia |
| Lokasi : | Perpustakaan UI, Lantai 3 |
| No. Panggil | No. Barkod | Ketersediaan |
|---|---|---|
| T46519 | 15-18-868828675 | TERSEDIA |
| Ulasan: |
| Tidak ada ulasan pada koleksi ini: 20433791 |
