Hasil Pencarian  ::  Simpan CSV :: Kembali

" ABSTRAKClustering adalah salah satu topik penting pada bidang Data Mining. Teori graf dapat digunakan untuk membantu clustering dengan cara membuat graf yang mewakili data-data yang akan di-cluster. Salah satu metode graf clustering adalah k-way spectral clustering yang memanfaatkan sebanyak k nilai eigen dan vektor eigen pertama dari matriks Laplacian suatu graf untuk melakukan clustering dengan k adalah banyaknya cluster yang diinginkan. Pada skripsi ini dibahas mengenai algoritma k-way spectral clustering merujuk kepada Ng, Jordan, dan Weiss (2002) dan von Luxburg (2007).

---

ABSTRACT

Clustering is one of the most important topic in Data Mining. Graph can be used to do clustering by forming a representation graph data which is needed to be clustered. K-way spectral clustering is one of many methods of graph clustering. This method uses first-k eigen values and eigen vectors of a Laplacian matrix to cluster with k is the number of desired clusters. In this skripsi, it will be discussed a k-way spectral clustering algorithm by Ng, Jordan, and Weiss (2002) and von Luxburg (2007)."

"Penelitian ini bertujuan untuk mengimplementasikan spectral clustering-PAM dengan menggunakan algoritma similaritas serial dan mengimplementasikan algoritma similaritas paralel berbasis CUDA dalam metode spectral clustering pada data microarray gen karsinoma. Implementasi dibantu dengan perangkat lunak R berbasis open source yang digunakan pada algoritma spectral clustering-PAM dengan algoritma similaritas serial dan CUDA yang digunakan pada algoritma similaritas paralel. Pengelompokan data microarray gen karsinoma diawali dengan menormalisasi data menggunakan normalisasi min-max. Pada algoritma spectral clustering-PAM, pertama-tama similaritas antar gen karsinoma dihitung. Selanjutnya, membentuk matriks Laplacian ternormalisasi dari matriks diagonal dan matriks Laplacian tak ternormalisasi. Langkah berikutnya yaitu menghitung eigenvalue dari matriks Laplacian ternormalisasi dan menentukan eigenvector dari eigenvalue terkecil matriks Laplacian ternormalisasi yang disusun menjadi dataset baru untuk dipartisi setiap barisnya menggunakan metode PAM. Berdasarkan running time, waktu yang dibutuhkan untuk menghitung nilai similaritas secara paralel di CUDA 378 kali lebih cepat daripada secara serial di R. Hasil penelitian menunjukkan bahwa spectral clustering-PAM mengelompokkan data microarray gen karsinoma menjadi dua cluster dengan nilai rata-rata silhouette yaitu 0,6458276.

---

This research aims to implement the spectral clustering PAM using serial similarity algorithm and implement parallel similarity algorithm based on CUDA in spectral clustering method on microarray data of carcinoma genes. Implementation assisted with software based on open source R used in spectral clustering algorithm PAM with serial similarity algorithm and CUDA used to parallel similarity algorithm. Clustering microarray data of carcinoma genes preceded by normalizing the data using min max normalization. In the spectral clustering PAM algorithm, first of all, similarity between genes of carcinoma calculated. Furthermore, forming the normalized Laplacian matrix from diagonal matrix and unnormalized Laplacian matrix. The next step is to calculate the eigenvalues of normalized Laplacian matrix and determine the eigenvectors of k smallest eigenvalues of normalized Laplacian matrix is organized into a new dataset to be partitioned each line using PAM. Based on the running time, the time required to calculate the value of parallel similarity in CUDA is 378 times faster than a serial in R. The results showed that spectral clustering PAM classify microarray data of carcinoma genes into two clusters with an average silhouette value is 0,6458276."

"ABSTRAKMengolah data dalam bentuk graf dapat dilakukan dengan cara clustering graf, yaitu mengelompokkan graf ke dalam cluster-cluster dimana data pada satu cluster memiliki karakter yang relatif sama. Two way spectral clustering adalah salah satu cara clustering graf yang menggunakan informasi dari dua nilai eigen untuk mendapatkan dua cluster setiap melakukan proses clustering. Pada skripsi ini akan dibahas bagaimana cara clustering graf dengan metode two way spectral clustering berdasarkan kriteria partisi graf dan akan dilakukan simulasi untuk melihat hasil clustering menggunakan graf terhubung dan graf tidak terhubung.

---

ABSTRACT

Data processing of graph data can be done by graph clustering, where data are grouped into clusters which data on each cluster have the similar characteristic. Two way spectral clustering is one of a graph clustering which using the smallest two eigenvalues to obtain two clusters. This skripsi will discuss how to clustering graph with two way spectral clustering method based on graph partitioning criteria and moreover data simulations will be conducted to see the results of clustering using a connected and disconnected graphs."

"Spectral clustering adalah salah satu algoritma clustering modern yang paling terkenal. Sebagai teknik clustering yang efektif, metode spectral clustering muncul dari konsep teori graf spektral. Metode spectral clustering membutuhkan algoritma partisi. Ada beberapa metode partisi termasuk PAM, SOM, Fuzzy c-means, dan k-means. Berdasarkan penelitian yang telah dilakukan oleh Capital dan Choudhury pada 2013, ketika menggunakan Euclidian distance, k-means memberikan akurasi yang lebih baik dibandingkan dengan algoritma PAM. sehingga, makalah ini menggunakan algoritma k-means. Keuntungan utama dari spectral clustering adalah mengurangi dimensi data, terutama dalam hal ini untuk mengurangi dimensi yang besar dari data microarray. Microarray data adalah chip berukuran kecil yang terbuat dari slide kaca yang berisi ribuan bahkan puluhan ribu jenis gen dalam fragmen DNA yang berasal dari cDNA. Aplikasi data microarray secara luas digunakan untuk mendeteksi kanker, misalnya adalah karsinoma, di mana sel-sel kanker mengekspresikan kelainan pada gen-nya. Proses spectral clustering dimulai dengan pengumpulan data microarray gen karsinoma, preprocessing, menghitung similaritas, menghitung , menghitung nilai eigen dari , membentuk matriks , dan clustering dengan menggunakan k-means. Dari hasil pengelompokan gen karsinoma pada penelitian ini diperoleh dua kelompok dengan nilai rata-rata Silhouette maksimal adalah 0.6336247. Proses clustering pada penelitian ini menggunakan program open source R.

---

Spectral clustering is one of the most famous modern clustering algorithms. As an effective clustering technique, spectral clustering method emerged from the concepts of spectral graph theory. Spectral clustering method needs partitioning algorithm. There are some partitioning methods including PAM, SOM, Fuzzy c means, and k means. Based on the research that has been done by Capital and Choudhury in 2013, when using Euclidian distance k means algorithm provide better accuracy than PAM algorithm. So in this paper we use k means as our partition algorithm. The major advantage of spectral clustering is in reducing data dimension, especially in this case to reduce the dimension of large microarray dataset.

Microarray data is a small sized chip made of a glass plate containing thousands and even tens of thousands kinds of genes in the DNA fragments derived from doubling cDNA. Application of microarray data is widely used to detect cancer, for the example is carcinoma, in which cancer cells express the abnormalities in his genes. The spectral clustering process is started with collecting microarray data of carcinoma genes, preprocessing, compute similarity matrix, compute , compute eigen value of , compute , clustering using k means algorithm. In this research, Carcinoma microarray data using 7457 genes. The result of partitioning using k means algorithm is two clusters clusters with maximum Silhouette value 0.6336247."

"ABSTRAKClustering adalah metode pembagian data ke dalam kelompok homogen yang disebut cluster. Spectral clustering merupakan salah satu algoritma clustering modern yang memiliki kelebihan dapat mereduksi dimensi data. Pada penelitian ini metode partisi yang diterapkan pada spectral clustering yaitu self-organizing map SOM . SOM memiliki keunggulan tahan terhadap data noise dan outlier, serta SOM dapat mengatasi dataset yang besar. Penelitian ini bertujuan untuk mengimplementasikan spectral clustering-self organizing map pada data microarray ekspresi gen karsinoma yang terdiri dari 7457 gen dari 18 sampel normal dan 18 sampel penderita kanker karsinoma. Sebelum dilakukan spectral clustering-SOM, data microarray ekspresi gen karsinoma dinormalisasi menggunakan normalisasi min-max. Spectral clustering-SOM dilakukan dengan tahapan-tahapan berikut: menghitung matriks similaritas W , menghitung matriks laplacian ternormalisasi Lsym , menghitung eigenvalue dari Lsym, membentuk matriks U yang terdiri dari k eigenvector terkecil, membentuk vektor unit Unorm dari vektor baris pada matriks U sehingga vektor unit memiliki norm 1, mengelompokkan gen pada matriks Unorm menggunakan SOM dan menghitung nilai indeks Davies-Bouldin IDB k . Penentuan jumlah cluster terbaik berdasarkan nilai indeks Davies-Bouldin yang paling minimum. Dengan menggunakan perangkat lunak R, hasil penelitian ini menunjukkan bahwa data microarray ekspresi gen karsinoma terbagi menjadi dua cluster dengan nilai indeks Davies-Bouldin yaitu 0,5843429. Berdasarkan indeks Davies-Bouldin, hasil clustering menggunakan metode spectral clustering-SOM lebih baik daripada hasil clustering yang menggunakan metode SOM tanpa spectral clustering.

---

ABSTRACTClustering is a method the dividing data into a homogeneous group called a cluster. Spectral clustering is one of the modern clustering algorithms that has the advantage of reducing dimensions of data. In this study the partitioning method applied to spectral clustering is self organizing map. SOM has the advantage of robust to noise and outlier, and SOM can handle large datasets. This study aims to implement spectral clustering self organizing map on microarray data of carcinoma gene expression consisting of 7457 genes from 18 normal samples and 18 samples of carcinoma cancer patients. Before spectral clustering SOM, the microarray data of carcinoma genes expression was normalized using min max normalization. The Spectral clustering SOM is done by the following steps calculate similarity matrix W , calculate the normalized Laplacian matrix Lsym , calculate the eigenvalue of Lsym , forming a vector unit Unorm of the row vector of the matrix U so that the vector unit has norm 1, grouping the genes in the matrix Unorm and calculate the Davies Bouldin index values IDB k . Determination of the best number of clusters based on the minimum value of the Davies Bouldin index. By using software R, the result of this research is microarray data of carcinoma gene expression is divided into two clusters with Davies Bouldin index value is 0.5843429. Based on the Davies Bouldin index values, clustering using spectral clustering SOM is better than clustering using only SOM method without spectral clustering."

"

Pendeteksian topik adalah suatu proses yang digunakan untuk menganalisis kata-kata pada suatu koleksi data tekstual untuk menentukan topik-topik yang ada pada koleksi tersebut. Salah satu metode standar yang digunakan untuk pendeteksian topik adalah metode clustering. Deep embedded clustering (DEC) adalah algoritma clustering dengan pendekatan deep learning yang menyatukan pembelajaran fitur dan clustering menjadi satu kerangka kerja sehingga dapat menghasilkan kinerja yang lebih baik. Namun metode DEC memiliki kelemahan, yaitu terjadinya penyimpangan ruang embedded ketika melakukan pembelajaran yang didapat ketika membuang decoder. Kelemahan tersebut diatasi dengan tidak membuang decoder, sehingga diperoleh metode yang lebih baik lagi yaitu Improved Deep Embedded Clustering (IDEC). Proses mempertahankan decoder disebut sebagai pelestarian struktur lokal. Pada penelitian ini, metode IDEC diadaptasi untuk masalah pendeteksian topik data tekstual berbahasa Indonesia. Selanjutnya kinerja metode IDEC dibandingkan dengan metode penelitian lain yang menggunakan DEC untuk masalah pendeteksian topik yaitu dengan cara membandingkan nilai dari coherence. Nilai coherence yang dihasilkan menunjukkan bahwa metode DEC lebih cocok jika dibandingkan dengan metode IDEC untuk permasalahan pendeteksian topik. Hal tersebut terjadi karena bagian decoder pada metode IDEC diperbarui sehingga parameter decoder sudah tidak sesuai untuk mengembalikan data ke dimensi semula. Sedangkan pada metode DEC bagian decoder dibuang sehingga parameter tidak diperbarui.

---

Topic detection is a process that is used to analyze words in a textual data collection to determine the topics within that collection. One of this standard topic detection method is clustering method. Deep embedded clustering (DEC) is a clustering algorithm with a deep learning approach that combines feature learning and clustering into one framework to obtain a better performance. However, DEC method has a weakness namely the distortion of embedded space that is caused by removing the decoder during the learning process. This weakness can be overcome by preserving the decoder, hence a better method is acquired, namely Improved Deep Embedded Clustering (IDEC). The process of preserving the decoder is called local structure preservation. In this research we adapt IDEC method for topic detection problem in Indonesian textual dataset. Furthermore, we compare the performance of IDEC method and other research using DEC by comparing the coherence value. The acquired coherence value shows that DEC method is more suitable compared to IDEC method for topic detection problems. This happens because of the decoder part in IDEC method is updated, so that the decoder parameters are no longer suitable to return the data into the original dimension. While in the DEC method the decoder was removed, therefore the parameters are not updated.

"

"Pencacahan clique maksimal adalah suatu metode graph clustering yang bertujuan untuk mencari simpul mana saja yang memiliki peranan paling besar dalam suatu graf. Pencacahan clique maksimal ini telah banyak diaplikasikan, diantaranya analisis pada jaringan sosial, pendeteksian hierarki melalui jaringan email, analisis statistik jaringan finansial, clustering pada jaringan dinamis, dan komputasi biologi. Algoritma Bron-Kerbosch merupakan salah satu algoritma tercepat dalam pencarian clique maksimal, maka pada penelitian ini, digunakanlah algoritma Bron-Kerbosch. Dalam mencacah semua clique maksimal dari suatu graf, matriks yang biasa digunakan adalah matriks ketetanggaan dari graf tersebut, sehingga dapat diperoleh simpul mana saja pada graf yang memiliki peranan paling besar. Selain matriks ketetanggaan, penelitian ini juga menggunakan matriks komplemen dalam mencacah clique maksimal. Data yang digunakan dalam penelitian ini adalah graf yang merepresentasikan rute jalur penerbangan domestik dari salah satu maskapai penerbangan di Indonesia. Dengan menerapkan algoritma Bron-Kerbosch, semua clique maksimal dari graf terkait akan didaftar, sehingga dapat diperoleh simpul yang memiliki peranan paling besar dalam graf ini. Graf tersebut direpresentasikan dalam bentuk matriks ketetanggaan dan juga matriks komplemen. Hasil penerapan algoritma Bron-Kerbosch pada data, baik yang menggunakan matriks ketetanggaan maupun matriks komplemen, keduanya memberikan hasil yang sama dalam menentukan simpul yang memiliki peranan paling besar dari graf terkait. Selain itu, melalui hasil penerapan yang menggunakan matriks komplemen, dapat diketahui pula simpul-simpul yang hanya bertetangga langsung dengan simpul yang memiliki peranan paling besar.

---

Maximal clique enumeration is a graph clustering method for finding all vertices that have the most influence in a graph. This maximal clique enumeration has largely been applied, including social network analysis, hierarchy detection through email networks, statistical analysis of financial networks, clustering in dynamic networks, and computational biology. The Bron-Kerbosch algorithm is one of the fastest algorithms to find all maximal cliques, hence this research will focus on that algorithm to find all maximal cliques. Counting all maximal cliques of a graph usually uses an adjacency matrix of the graph to find all vertices in the graph that have the most influence. Other than adjacency matrix, this research will also use a complement matrix in counting all maximal cliques. This research uses a graph that represents a domestic flight route of one of the airlines in Indonesia. By using Bron-Kerbosch algorithm, all maximal cliques of the graph will be listed, so that it will come up with the vertices which are the most influential in this graph. The graph will be represented in an adjacency matrix as well as a complement matrix. The result of applying the Bron-Kerbosch algorithm both the adjacency and the complement matrix?will give the same result in determining vertices that have the most influence in the graph. Besides that, by using a complement matrix, the result gives more information on the vertices which are only connected to the vertices that have the most influence."

"Pengklasteran clustering yang dilakukan dengan menggunakan metode graf disebut dengan pengklasteran graf graph clustering . Pengklasteran graf dengan memperhatikan bobot dapat diselesaikan dengan menggunakan pohon rentangan minimum. Salah satu algoritma yang dapat digunakan untuk menyelesaikan pengklasteran graf berbobot berdasarkan pohon rentangan minimum adalah algoritma maximum standard deviation reduction MSDR . Pada algoritma MSDR tidak perlu ditentukan banyaknya klaster yang terbentuk, karena terdapat perhitungan untuk menentukan banyak klaster secara otomatis. Namun dalam penelitian lanjutan algoritma MSDR cukup sulit dikerjakan karena sulitnya dalam menentukan nilai kandidat klaster terbaik, sehingga dilakukan modifikasi untuk menentukan nilai -nya. Modifikasi ini disebut dengan modifikasi MSDR MMSDR. Penelitian ini merupakan implementasi dari algoritma MMSDR pada masalah rute penerbangan di Indonesia yang disebut maskapai X, dengan menggunakan input matriks komplemen. Dengan menggunakan input matriks dari komplemen graf didapatkan pengklasteran berdasarkan jarak antar bandara. Penelitian ini juga menganalisis perubahan nilai epsilon dan perubahan matriks input. Hasil analisis menunjukkan bahwa perubahan nilai epsilon tidak mempengaruhi banyaknya klaster dan anggota klaster, sedangkan perubahan matriks input dapat mempengaruhi perbedaan anggota klaster.

---

Clustering is done by using graph method called graph clustering. Graph clustering with weights can be solved by using a minimum spanning tree. One of the algorithms that can be used to complete a weighted graph clustering based on a minimum spanning tree is the maximum standard deviation reduction MSDR algorithm. In the MSDR algorithm there is no need to determine the number of clusters that are formed, because there are calculaions to determine many clusters automically. However, in advanced research MSDR algorithm is quite difficult to do because of the difficulty in determining the value of best cluster candidates, so modifications are made to determine the value of. This modification is called the modification MSDR MMSDR. This research is an implementation of MMSDR algorithm on flight route problem in Indonesia called airline X, by using input complement matrix. Using the matrix input from the complement graph obtained clustering based on the distance between airports. This research also analyzed changes in epsilon value and changes in input matrix. The results of the analysis show that the change in epsilon value does not affect the number of clusters and clusters members, whereas the change in input matrix may affect the cluster members."

"Pengiriman barang dari depot terakhir menuju ke lokasi pelanggan adalah pengiriman last mile. Pengiriman last mile sering dianggap sebagai tahap yang paling mahal dan kurang efisien. Beberapa permasalahan yang dihadapi dalam pengiriman last mile adalah biaya yang tinggi, waktu pengiriman yang lama, dan kemungkinan barang rusak. Penggunaan sistem kendaraan truck-drone dalam pengiriman last mile dapat dijadikan sebagai solusi untuk mengatasi permasalahan dalam last mile. Tujuan dari penelitian ini adalah menemukan rute pengiriman barang yang meminimalkan biaya pengiriman dengan menggunakan sistem truck-drone dalam last mile. Pendekatan yang diusulkan untuk mencari rute optimal terdiri dari dua fase yaitu fase clustering dan routing. Dalam fase clustering menggunakan mean shift clustering untuk mengelompokkan lokasi pelanggan dan mencari lokasi parkir (pusat cluster). Dalam fase routing menggunakan algoritma genetika untuk menemukan rute optimal. Implementasi pada 90 pelanggan didapatkan penggunaan metode mean shift clustering diikuti oleh algoritma genetika, dapat menghasilkan rute optimal yang meminimalkan total biaya. Hal ini ditunjukkan dari penurunan biaya pada rute mean shift clustering mencapai 3,51% dibandingkan clustering dengan metode intuitif. Selain itu, analisis hasil juga mencerminkan bahwa penerapan mean shift clustering mampu mengurangi total jarak sebesar 27,93 % dan waktu tempuh sebesar 25,83 % delivery.

---

Last-mile delivery is often considered the most expensive and less efficient stage. Some challenges in last-mile delivery include high costs, long delivery times, and the possibility of damaged goods. The use of a truck-drone system in last-mile delivery can be a solution to address these challenges. The objective of this research is to find delivery routes that minimize delivery costs using a truck-drone system in the last mile. The proposed approach to finding optimal routes consists of two phases: clustering and routing. In the clustering phase, mean shift clustering is used to group customer locations and identify parking locations (cluster centers). In the routing phase, a genetic algorithm is employed to find the optimal routes. The implementation on 90 customers showed that the use of mean shift clustering followed by a genetic algorithm could generate optimal routes that minimize the total cost. This is evident from the cost reduction in mean shift clustering routes by 3,51% compared to the initial clustering solution with intuitif method. Furthermore, the results analysis also reflects that the implementation of Mean Shift Clustering can reduce the total distance by 27.93% and travel time by 25.83%."