Perpustakaan Digital ITB

Knowledge graph digunakan untuk menyimpan sekumpulan fakta dalam bentuk triple SPO (subjek, predikat, objek) atau (entitas, relasi, entitas). Salah satu masalah yang umum terjadi pada KG adalah KG tidak lengkap yaitu terdapat salah satu bagian entitas atau relasi yang hilang. Penggunaan KG tidak lengkap dapat menurunkan akurasi suatu task. Relasi yang hilang merupakan salah satu permasalahan yang sering terjadi pada KG tidak lengkap. Untuk melengkapi link atau relasi yang hilang dapat menggunakan prediksi link. Seiring bertambahnya fakta yang perlu disimpan, ukuran KG juga bertambah besar, terdiri dari jutaan entitas dan relasi. Semakin besar KG, maka semakin besar juga peluang KG tersebut tidak lengkap dan waktu yang dibutuhkan untuk memprediksi relasi yang hilang juga semakin meningkat. Oleh karena itu, akurasi hasil prediksi dan efisiensi waktu prediksi pada metode prediksi link perlu ditingkatkan. Embedding merupakan salah satu pendekatan yang digunakan pada prediksi link. Embedding mengubah representasi entitas dan relasi sebagai vektor dalam ruang dimensi tertentu. Proses utama prediksi link berbasis embedding terdiri atas tiga tahap yaitu embedding, scoring, dan pemeringkatan. Embedding mengubah entitas dan relasi menjadi nilai vektor. Scoring menghitung skor setiap triple menggunakan scoring function tertentu dan pemeringkatan mengurutkan triple berdasarkan skor dari yang tertinggi hingga terendah. Hasil prediksi ditentukan dari skor setiap triple. Semakin tinggi skor, semakin besar kemungkinan triple tersebut valid. Clustering digunakan untuk mengelompokkan data berdasarkan kesamaan tertentu. Teknik ini dapat diterapkan pada prediksi link berbasis embedding untuk mengelompokkan vektor sehingga prediksi link dilakukan pada cluster tertentu. Dengan membatasi jumlah vektor yang perlu diproses pada proses scoring dan pemeringkatan triple, waktu yang dibutuhkan untuk proses prediksi menjadi lebih efisien dan meningkatkan peluang hasil prediksi yang lebih akurat. Eksperimen penelitian dilakukan pada tiga dataset: WN18RR, WN11 dan FB13. Teknik prediksi link berbasis embedding yang digunakan sebagai metode baseline adalah TransE dan eksperimen menggunakan beberapa dimensi embedding rentang 50 hingga 200. Pengelompokan vektor menggunakan dua skema yaitu Balanced Iterative Reducing and Clustering Using Hierarchies (BIRCH) dan pengelompokan berdasarkan kesamaan relasi. Kualitas cluster dievaluasi menggunakan Silhouette Coefficient (SC) dan akurasi prediksi link menggunakan Hits@N, Mean Rank (MR), Mean Reciprocal Rank (MRR). Pengukuran efisiensi waktu berdasarkan waktu yang digunakan untuk memprediksi seluruh data uji pada setiap dataset. Metode prediksi link berbasis embedding dengan pengelompokan vektor diberi nama Link Prediction Clustering (LPC). Hasil eksperimen menunjukkan bahwa kualitas cluster memiliki nilai rentang 0,86 hingga 0,93. Nilai ini mengindikasikan bahwa pengelompokan vektor mendekati nilai 1, yang berarti kualitas cluster yang dihasilkan bagus. Oleh karena itu pengelompokan vektor dapat digunakan untuk membatasi area prediksi link. Pemilihan kelompok vektor menggunakan pengukuran jarak terdekat antara triple yang akan diprediksi dengan cluster yang ada, menggunakan Euclidean dan Mahalanobis. Berdasarkan hasil perhitungan relatif terhadap metode baseline, penerapan kelompok vektor terbukti dapat meningkatkan akurasi hasil prediksi Hits@1 rentang 10% – 98% dan mempersingkat waktu prediksi rentang 62% - 99,96%. Berdasarkan hasil penelitian, LPC terbukti berhasil meningkatkan akurasi hasil prediksi link sekaligus mengurangi waktu prediksi link pada KG tidak lengkap dan berukuran besar. Kebaharuan dan orisinalitas penelitian ini terletak pada penerapan pengelompokan vektor hasil embedding. Kontribusi utama disertasi ini adalah menghasilkan metode prediksi link berbasis embedding yang lebih akurat dan waktu prediksi lebih efisien dengan pengelompokan vektor hasil embedding.