Dự đoán liên kết trên cơ sở dữ liệu đồ thị

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN TRỌNG NHÂN

DỰ ĐOÁN LIÊN KẾT TRÊN SƠ SỞ DỮ LIỆU ĐỒ THỊ

Chuyên ngành: Khoa học máy tính

Mã số: 8480101

Người hướng dẫn: TS. Trần Thiên Thành

LỜI CAM ĐOAN

Tôi cam đoan các kết quả tìm hiểu đưa ra trong luận văn này dựa trên

các kết quả thu được trong quá trình tìm hiểu của riêng tôi. Các kết quả

nghiên cứu và các kết luận trong luận văn là trung thực, không sao chép từ bất

kỳ một nguồn nào và dưới bất kỳ hình thức nào. Việc tham khảo các nguồn

tài liệu (nếu có) đã được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo

đúng quy định.

Quy Nhơn, tháng 09, năm 2021

Nguyễn Trọng Nhân

LỜI CẢM ƠN

Luận văn Thạc Sỹ này được thực hiện tại Trường Đại học Quy Nhơn.

Để hoàn thành luận văn này, tôi xin tỏ lòng biết ơn sâu sắc và gửi lời cảm ơn

chân thành đến Thầy TS. Trần Thiên Thành, đã tận tình hướng dẫn, giúp đỡ

cho tôi trong suốt quá trình thực hiện luận văn. Tôi xin chân thành cảm ơn

quý Thầy, cô trong khoa Khoa học máy tính và phòng sau đại học của Trường

Đại học Quy Nhơn đã tận tình truyền đạt kiến thức, tạo điều kiện thuận lợi về

mặt thủ tục cho hoạt động học tập và thực hiện luận văn của tôi. Cuối cùng tôi

cũng xin gửi lời cảm ơn tới các anh chị và các bạn lớp cao học Khóa 22 luôn

động viên, khích lệ tinh thần, giúp tôi rất nhiều trong quá trình học tập cũng

như hoàn thành luận văn thạc sỹ.

Quy Nhơn, tháng 09, năm 2021

Nguyễn Trọng Nhân

MỤC LỤC

LỜI CAM ĐOAN

LỜI CẢM ƠN

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

DANH MỤC CÁC BẢNG

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

MỞ ĐẦU .......................................................................................................... 1

1. Lý do chọn đề tài..................................................................................... 1

2. Mục tiêu nghiên cứu ............................................................................... 1

3. Đối tượng và phạm vi nghiên cứu........................................................... 1

3.1. Đối tượng nghiên cứu. ..................................................................... 1

3.2. Phạm vi nghiên cứu. ........................................................................ 2

4. Phương pháp nghiên cứu. ....................................................................... 2

5. Nội dung nghiên cứu............................................................................... 2

Chương 1: CƠ SỞ DỮ LIỆU ĐỒ THỊ.......................................................... 3

1.1. Đồ thị.................................................................................................... 3

1.2. Cơ sở dữ liệu đồ thị.............................................................................. 7

1.2.1. Các mô hình cơ sở dữ liệu đồ thị.................................................. 9

1.2.2. Ứng dụng của cơ sở dữ liệu đồ thị. ............................................ 12

1.2.3. Một số hệ quản trị cơ sở dữ liệu đồ thị tiêu biểu............................ 14

1.3. Cơ sở dữ liệu đồ thị Neo4J. ............................................................... 15

1.3.1. Giới thiệu. ................................................................................... 15

1.3.2. Mô hình dữ liệu........................................................................... 16

1.3.3. Ngôn ngữ truy vấn Cyper............................................................ 22

1.3.4. Khoa học dữ liệu đồ thị............................................................... 26

1.4. Tiểu kết chương 1. ............................................................................. 29

Chương 2: BÀI TOÁN DỰ ĐOÁN LIÊN KẾT TRÊN CƠ SỞ DỮ

LIỆU NEO4J ................................................................................................. 30

2.1. Bài toán dự đoán liên kết ................................................................... 30

2.1.1. Giới thiệu bài toán...................................................................... 30

2.1.1. Ứng dụng .................................................................................... 31

2.1.2. Phương pháp dự đoán liên kết.................................................... 31

2.2. Dự đoán liên kết trên cơ sở dữ liệu đồ thị Neo4j............................... 33

2.2.1. Ưu điểm của cơ sở dữ liệu đồ thị đối với bài toán dự đoán liên

kết.......................................................................................................... 33

2.2.2. Phương pháp sử dụng................................................................. 33

2.2.3. Ví dụ minh họa............................................................................ 42

2.3. Xây dựng bô phân loại học máy trong bài toán dự đoán liên kết...... 45

2.3.1. Xây dựng mô hình học máy......................................................... 45

2.3.2. Tập huấn luyện và tập kiểm tra .................................................. 47

2.3.3. Các metrics đánh giá mô hình:................................................... 48

2.4. Tiểu kết chương 2. ............................................................................. 52

Chương 3: CÀI ĐẶT MÔ PHỎNG THỰC NGHIỆM.............................. 53

3.1. Môi trường và Công cụ thực nghiệm................................................ 53

3.1.1. Môi trường và ngôn ngữ lập trình.............................................. 53

3.1.2. Công cụ và thư viện .................................................................... 53

3.2.3. Bộ dữ liệu.................................................................................... 54

3.2. Bài toán dự đoán đồng tác giả............................................................ 55

3.3. Cài đặt mô phỏng. .............................................................................. 57

3.2.1. Kết nối Neo4j:................................................................................. 57

3.2.2. Nạp cơ sở dữ liệu DBLP vào Neo4j............................................ 57

3.2.3. Xây dựng biểu đồ đồng tác giả................................................... 58

3.2.4. Tạo tập dữ liệu huấn luyện và kiểm tra...................................... 58

3.2.5. Xây dựng mô hình học máy......................................................... 61

3.2.6. Xây dựng các tính năng dự đoán liên kết. .................................. 62

3.2.7. Đánh giá mô hình. ...................................................................... 63

3.2.8. Xây dựng một số tính năng đồ thị khác. ..................................... 64

3.3. Đánh giá kết quả đạt được ................................................................ 67

3.4. Tiểu kết chương 3. ............................................................................. 69

KẾT LUẬN.................................................................................................... 70

DANH MỤC TÀI LIỆU THAM KHẢO..................................................... 71

QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ (BẢN SAO)

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

CSDL : Cơ sở dữ liệu.

RDBMS : Hệ quản trị cơ sở dữ liệu quan hệ.

SQL : Structured Query Language.

NoSQL : Not only SQL.

API : Application Programming Interface.

RDF : Resource Description Framework.

URI : Uniform Resource Identifier

IDE : Integrated Development Environment

APOC : Awesome Procedures on Cypher

CN : Hàng xóm chung

JC : Hệ số Jaccard

AA : Adamic Adar

PA : Kết nối ưu tiên

TN : Tổng số lân cận

BSD : Berkeley Software Distribution

DANH MỤC CÁC BẢNG

Bảng 2.1: Các thông số cú pháp thư viện thuật toán Adamic Adar................ 34

Bảng 2.2: Các thông số cú pháp thư viện thuật toán hàng xóm chung........... 35

Bảng 2.3: Các thông số cú pháp thư viện thuật toán đính kèm thích hợp ...... 35

Bảng 2.4: Các thông số cú pháp thư viện thuật toán phân bổ tài nguyên....... 36

Bảng 2.5: Các thông số cú pháp thư viện thuật toán cùng cộng đồng............ 36

Bảng 2.6: Các thông số cú pháp thư viện thuật toán tổng số lân cận ............. 37

Bảng 2.7: Các thông số cú pháp thuật toán đếm số tam giác ......................... 38

Bảng 2.8: Cấu hình chung để thực thi thuật toán trên đồ thị đã đặt tên.......... 39

Bảng 2.9: Kết quả............................................................................................ 39

Bảng 2.10: Các thông số cú pháp thuật toán hệ số phân cụm cục bộ............. 40

Bảng 2.11: Cấu hình chung để thực thi thuật toán trên đồ thị đã đặt tên........ 40

Bảng 2.12: Cấu hình cụ thể của thuật toán ..................................................... 41

Bảng 2.13: Kết quả.......................................................................................... 41

Bảng 2.14: Các chỉ số của Positive và Negative............................................. 49

Bảng 3.1: Bảng kết quả đánh giá mô hình. ..................................................... 67