đặt vấn đề về bài toán dự đoán liên kết, từ đó xác định mục tiêu nghiên cứu và giới hạn phạm vi của nghiên cứu. Ngoài ra, mô tả bố cục và tóm tắt ý nghĩa từng chương. Cơ sở lý thuyết và các công trình nghiên cứu liên quan Trình bày cơ sở lý thuyết và liệt kê các phương pháp tiếp cận của bài toán. Ngoài ra, trình bày một số công trình nghiên cứu liên quan.
Thực nghiệm Giới thiệu thông tin và thống kê mô tả về hai bộ dữ liệu sử dụng thực nghiệm là Movielens Latest-small và Yelp2018. Ngoài ra, mô tả cách thức sử dụng dữ liệu, môi trường thực nghiệm và kết quả từ thực nghiệm các mô hình đã đề xuất. Kết luận Tóm tắt kết quả đạt được từ thực hiện khoá luận tốt nghiệp, hạn chế, đề xuất các hướng phát triển cho công trình và tỷ lệ đóng góp công việc của sinh viên. Tài liệu tham khảo: Trích dẫn các nguồn tài liệu tham khảo được sử dụng để làm cơ sở cho khoá luận tốt nghiệp.
11 CHƯƠNG 2: CƠ SỞ LÝ THUYET VÀ CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN 2. Link Prediction Xem xét một mạng G(V, E) tại một thời điểm nhất định t, với V va E tương ứng là các tập nút và cạnh. Mục đích của dự đoán liên kết là dự đoán các liên kết mới hoặc bị loại bỏ giữa các nút cho một thời điểm trong tương lai t’ (t’ > £), hoặc các liên kết còn thiếu hoặc không được quan sát trong mạng đang quan sát hiện tại. Van đề này được lý giải bởi một mạng xã hội đơn giản bao gồm năm người trong Hình 1.1, với các cạnh nét liền thể hiện những mối liên kết đã tồn tai giữa các thực thể trong mạng tại thời điểm £, và cạnh nét đứt thé hiện những những mối liên kết mới sẽ xuất hiện trong suốt khoảng thời gian [t, t’].
Tại thời điểm t, Alice và Bob là ban, Alice cũng là bạn của Nick. Tại thời điểm £, có khả năng Alice sẽ giới thiệu Bob cho Nick, từ đó Bob và Nick cũng trở thành bạn của nhau. Tương tự, Nick và Amy cũng sẽ trở thành bạn tại thời điểm £'. Mục đích của dự đoán liên kết đối với trường hợp này là dé dự đoán sự xuất hiện của các mối quan hệ bạn bè mới giữa năm người trong mạng đang quan sát này.
Để giải quyết bài toán dự đoán liên kết, cần phải xác định khả năng hình thành hoặc hủy bỏ của các liên kết giữa các cặp nút với nhau. Thông thường, những khả năng này được do bởi mức độ tương đồng hoặc xếp hạng liên quan giữa các cặp nút. Minh họa khuôn khổ chung của bai toán dự đoán liên kết tại Hình 2. Với một mạng khởi tạo ban đầu, có hai cách để dự đoán sự xuất hiện của liên kết là cách tiếp cận dựa trên sự tương đồng (similarity-based approaches) và cách tiếp cận dựa trên học tập (learning-based approaches).
Phương pháp similarity-based sẽ tính toán sự tương đồng của các cặp nút không liên kết với nhau trong một mạng, cụ thể là dựa trên các biện pháp phân tích sự gần gũi của ác nút. Từng cặp nút (x, y) tiềm năng sẽ được gán một số điểm xác suất, với số điểm càng cao thì khả năng càng cao xác suất x và y sẽ được liên kết trong tương lai và ngược lại. Từ đó có được một danh sách được xếp hạng theo thứ tự giảm dần của điểm xác suất và những liên kết xuất hiện ở đầu danh sách có khả năng xuất hiện cao nhất. Phương 12 pháp learning-based lại xem bài toán dự đoán liên kết như một tác vụ phân loại.
Do đó, một số mô hình học máy điển hình như mô hình phân loại (classifier) và mô hình xác suất (probabilistic) có thé được sử dụng đề giải quyết bài toán này. Từng cặp nút không liên kết tương ứng với một thể hiện với các tính năng mô tả các nút và nhãn lớp. Nếu có một liên kết tiềm năng giữa cặp nút, cặp nút đó sẽ được gắn nhãn positive, ngược lại sẽ gắn nhãn negative. Đối với phương pháp learning-based, các đặc trưng bao gồm hai phần: một là các đặc trưng về sự tương đồng từ phương pháp similarity-based, hai là các đặc trưng bắt nguồn từ chính mạng quan sát.
Dự đoán liên kết bị xóa bỏ hoặc biến mất cũng được giải quyết tương tự. Similarity-based approach Similarity ; = >} Order scores —> —. pairs ed earning-based approac! Learning models Similarity ¿2—— Clasifer features / * iti J ~___ | Probabilistic model Positive / Other instances / features _/ ` a Hình 2. Minh hoa khuôn khổ bài toán dự đoán liên kết.
[1] Có rất nhiều công trình nghiên cứu về bài toán dự đoán liên kết mà tập trung vào các kỹ thuật dự đoán liên kết, thảo luận về các vấn đề dự đoán liên kết đặc biệt và sử dụng các kỹ thuật dự đoán liên kết hiện có để ứng dụng vào các mục đích khác nhau. Dé phân loại rõ ràng các công trình hiện có này, một danh mục dự đoán liên kết mới với hai khía cạnh đã được đề xuất: khía cạnh kỹ thuật và khía cạnh dựa vào vấn đề.2 mô tả danh mục của các kỹ thuật dự đoán liên kết và các van đề dự đoán liên kết. Đối với các kỹ thuật dự đoán liên kết, có thé được chia thành bốn cấp độ từ trên xuống dưới: (1) Dựa theo thông tin mạng cơ bản được sử dụng trong dự đoán, cấp độ đầu tiên và cao nhất bao gồm nút, cấu trúc liên kết và lý thuyết xã hội. (3) Mức độ thứ ba bao gồm các kỹ thuật dự đoán liên kết cơ bản phổ biến dựa vào nút, hàng xóm, đường dẫn, bước ngẫu nhiên và lý thuyết xã hội.
(4) Mức độ thứ tư, bao gồm các kỹ thuật dự đoán cơ bản và các thông tin bên ngoài, bao gồm weights, attributes và kho tri thức, cung cấp đặc trưng cho các kỹ thuật learning-based phức tạp, như feature-based classification, kernel-based learning, probabilistic model và matrix factorization. Tất cả các kỹ thuật dự đoán liên kết gần tương tự nhau và có thể được sử dung dé giải quyết các van dé và ứng dung dự đoán liên kết khác nhau. Từ khía cạnh khác, bài toán dự đoán liên kết được sắp xếp theo ba mức độ từ dưới lên trên: (1) Dựa theo đối tượng mà bài toán dự đoán liên kết quan tâm, mức độ đầu tiên và thấp nhất chia bài toán dự đoán liên kết thành mạng (network) liên quan đến đặc tính toàn cầu của mạng, và liên kết (link) liên quan đến đặc tính liên kết của mạng. (3) Mực độ thứ ba là bài toán dự đoán liên kết được dựa trên các kỹ thuật dự đoán liên kết; do đó hai khía cạnh có sự giao thoa ở mức này và có sự liên quan mật thiết.
Đối với các chỉ số đánh giá được sử dụng trong dự đoán liên kết, thông thường chia làm hai loại: chi số ngưỡng cố định (fixed threshold metrics) và đường cong ngưỡng (threshold curves). Precision và recall trên các dự đoán top-N là các chỉ số fixed threshold điển hình. Một loại số liệu khác là các đường cong ngưỡng, chẳng hạn như (ROC) curves và precision-recall curves được sử dụng rộng rãi trong đánh giá dự đoán liên kết. Ngoài ra, AUC (Khu vực dưới ROC) được xem là thước đo mạnh mẽ khi có sự mat cân bằng [6].
AUC có thé được hiểu là xác suất mà một liên kết bị thiếu được chọn ngẫu nhiên có điểm số cao hơn một liên kết không tồn tại được chọn ngẫu nhiên. Khó có thể xác định và giải thích các chiến lược đánh giá dy đoán liên kết hơn so với phân loại tiêu chuẩn trong đó chi 14 định đầy đủ một tập dữ liệu là đủ, do đó các phương pháp đánh giá mới hoặc chỉ số hiệu suất cũng được đề xuất [7]. Link prediction techniques ~ — a : ; Neighbo r Path Random ‘walk Community Triad Structur hole Tie h Homophily al strengtl ⁄ ÀS NN a Node-based ⁄ -Node similarity Neighbor-based cn | = -Katz sed | | Serre] SimRank F Social Theory-based Structural hoe -feudmlaiy | | IC | | PropFtow _ -LHN | | -Friend Link TT | -PA | -ver pcr “RA |= -CST 7. T ¬ External information: weights, attributes, statistics, knowledge repository,.
y PY 4 Learning-based techniques Feature-based classification | Kernel-based | Matrix factorization Probabilistic model Ỳ Ỳ Ỳ Ỳ Ỷ Ỳ Ỷ Link prediction | Link prediction | Link prediction | Link prediction Link prediction Link prediction | Link prediction in in in Í in for for for heterogeneous location temporal bipartite multi-relation | active/unactive | disappearing network network network | network | links links links Heterogeneous Location Temporal Bipartite Multi-relation Active/unactive Disappearing network network network network link link link Hình 2. Danh mục phân loại kỹ thuật và bài toán dự đoán liên kết. Neural Network Neural Network [49] hay con gọi là mạng nơ-ron nhân tao, là một mô hình toán phức tạp được phát triển dựa theo mô hình hoạt động của các tế bào thần kinh não người nhằm tăng độ chính xác cho các thuật toán học máy. Mô phỏng mô hình than kinh con người.
16 Kiến trúc mạng nơ-ron là việc đi mô phỏng các tế bào thần kinh bằng các nút và các dây thần kinh liên kết các nút với nhau. Các nút x„ va a, mô phỏng cho các tế bao thần kinh và đường liên kết mô phỏng cho các dây thần kinh nối, một mô hình mạng nơ-ron bao gồm ba tầng chính: © Tang vào (Input Layer): Tang này nhận các dit liệu đầu vào tương ứng cho các nút. © Tang ẩn (Hidden Layer): Tầng nay thể hiện cho quá trình xử lý thông tin và suy luận của mạng, tại đây nhận các thông tin đầu vào và trả kết quả đầu ra thông qua các hàm kích hoạt. e Tầng ra (Output Layer): Tang này thé hiện cho đầu ra của mạng nơ-ron sau khi trải qua quá trình tổng hợp và xử lý ở các hidden layers.
17 Giá trị các nút là: a? )= = 9(W,An ) ro + Wey + Wer + Wes) a?) = = g(Wj)zo +W,Oo, + Wx. + WLas) a?) = g WL) 29 Wray Wo x5 Ws) at) = g(WĐzg Wray Wax. Was) g= a3 = = 9 WY a2 + Ww a) + wj al) + w a’) + Ww? at) Với W* là ma trận hệ số giữa lớp (k— 1) và lớp k, trong đó wh là hệ số kết nối từ node thứ i của layer (k — 1) đến node thứ j của layer k, x, là nút input đầu vào tương ứng với từng layer, vector aŸ là giá trị của nút trong layer k khi áp đụng activation function. Mạng nơ-ron được sử dụng nhằm giải quyết tính tuyến tính của các thuật toán học máy thông thường, tăng độ phức tạp và chính xác cho các mô hình.