ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THỊ HỒNG PHƯƠNG NGHIÊN CỨU ỨNG DỤNG THUẬT TỐN TỐI ƯU BẦY ĐÀN VÀO HỆ THỐNG GỢI Ý LUẬN VĂN THẠC SĨ NGÀNH KHOA HỌC MÁY TÍNH Đà Nẵng, năm 2018 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THỊ HOÀNG PHƯƠNG NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN TỐI ƯU BẦY ĐÀN VÀO HỆ THỐNG GỢI Ý Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: TS Nguyễn Văn Hiệu Đà Nẵng, năm 2018 i LỜI CAM ĐOAN Tơi cam đoan cơng trình nghiên cứu riêng Các số liệu, kết nêu luận văn trung thực chưa cơng bố cơng trình khác Tác giả luận văn Nguyễn Thị Hoàng Phương ii TĨM TẮT LUẬN VĂN NGHIÊN CỨU ỨNG DỤNG THUẬT TỐN TỐI ƯU BẦY ĐÀN VÀO HỆ THỐNG GỢI Ý Học viên: Nguyễn Thị Hồng Phương Mã số: 60480101 Khóa: K33 Chuyên ngành: Khoa học máy tính Trường Đại học Bách khoa – ĐH Đà Nẵng Tóm tắt – Với bùng nổ thông tin internet ngày nay, việc lựa chọn đưa định người dùng trở nên vơ khó khăn, tạo nhu cầu cần phải xây dựng hệ thống gợi ý nhằm cung cấp đề xuất mục tin cần thiết cho người dùng Luận văn trình bày lý thuyết hệ thống gợi ý, thuật toán tối ưu bầy đàn để làm sở xây dựng mơ hình gợi ý hiệu Có nhiều phương pháp lọc thơng tin hệ thống gợi ý, luận văn đề cập đến phương pháp lọc cộng tác theo mơ hình láng giềng, lọc cộng tác sử dụng kỹ thuật phân cụm Spectral, lọc cộng tác sử dụng PSO việc cải tiến kỹ thuật để xây dựng phương pháp lọc hiệu liệu nhị phân Trên sở đó, mơ hình triển khai thực nghiệm thành cơng, đánh giá kết cho thấy mơ hình cải tiến có hiệu suất cao mơ hình khác Từ khóa: hệ thống gợi ý, lọc cộng tác, mơ hình láng giềng, phân cụm Spectral, tối ưu bầy đàn Abstract – Today, with a huge amount of information on the internet, the choice and decision-making of users becomes extremely difficult, leads to the nessesary of recommender systems to suggest for user In this thesis, recommender systems, particle swarm optimization’s theory is presented as the basis of the effective recommender model There are many filtering information methods, this thesis refers to the neighbor-based collaborative filtering, Spectral-based collaborative filtering, collaborative filtering using PSO methods and improve these techniques to one for binary dataset From that, the models are successfully implemented, and the results shows that the improvement model is more effective than other models Keywords: recommender system, collaborative filtering, neighborhood model, Spectral clustering, particle swarm optimization iii MỤC LỤC LỜI CAM ĐOAN i TÓM TẮT LUẬN VĂN ii MỤC LỤC iii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT v DANH MỤC CÁC BẢNG vi DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ vii PHẦN MỞ ĐẦU 1 Lý chọn đề tài Mục đích – Mục tiêu nghiên cứu Đối tượng – Phạm vi nghiên cứu Phương pháp nghiên cứu Ý nghĩa khoa học thực tiễn Dàn ý nội dung CHƯƠNG TỔNG QUAN VỀ HỆ THỐNG GỢI Ý VÀ THUẬT TOÁN PSO 1.1 Tổng quan hệ thống gợi ý 1.1.1 Giới thiệu số khái niệm .4 1.1.2 Ứng dụng lợi ích hệ thống gợi ý 1.1.3 Các cách tiếp cận hệ thống gợi ý 1.1.4 Các kĩ thuật lọc thông tin 1.1.5 Các giai đoạn hệ thống gợi ý .11 1.1.6 Phương pháp đánh giá mơ hình hệ thống gợi ý 11 1.2 Tổng quan thuật toán tối ưu bầy đàn PSO 13 1.2.1 Giới thiệu 13 1.2.2 Các khái niệm thuật toán PSO .14 1.2.3 Thuật toán PSO 17 Kết chương 19 CHƯƠNG ỨNG DỤNG THUẬT TOÁN TỐI ƯU BẦY ĐÀN VÀO HỆ THỐNG GỢI Ý 20 2.1 Phương pháp lọc cộng tác sử dụng mô hình láng giềng 20 2.2 Phương pháp lọc cộng tác sử dụng kỹ thuật phân cụm Spectral 21 2.3 Phương pháp lọc cộng tác sử dụng PSO 24 2.4 Cải tiến phương pháp phân cụm lọc cộng tác sử dụng kỹ thuật Spectral 28 2.5 Cải tiến phương pháp gợi ý dựa lọc cộng tác tối ưu trọng số PSO 29 Kết chương 33 CHƯƠNG HỆ THỐNG THỬ NGHIỆM VÀ ĐÁNH GIÁ 34 iv 3.1 Giới thiệu tập liệu 34 3.2 Kịch thực nghiệm 35 3.3 Kết chạy thử nghiệm 35 3.3.1 Lọc cộng tác người dùng theo phương pháp mơ hình láng giềng gần phương pháp tối ưu trọng số sử dụng PSO cải tiến 35 3.3.2 Lọc cộng tác mục tin theo phương pháp mô hình láng giềng gần phương pháp tối ưu trọng số sử dụng PSO cải tiến 39 3.3.3 Lọc cộng tác kết hợp người dùng – mục tin theo phương pháp mơ hình láng giềng gần phương pháp tối ưu trọng số sử dụng PSO cải tiến 42 3.4 Hướng dẫn thực nghiệm 48 Kết chương 49 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 50 TÀI LIỆU THAM KHẢO QUYẾT ĐỊNH GIAO ĐỀ TÀI (BẢN SAO) v DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ACM ACO AI ICCF NBCF PSO RS SI : Association for Computing Machinery : Ant Colony Optimization Tối ưu đàn kiến : Artificial Intelligence Trí thuệ nhân tạo : Iteration Clustering Collaborative Filtering : Nearest Neighbor Collaborative Filtering : Particle Swarm Optimization Tối ưu bầy đàn : Recommender System Hệ thống gợi ý : Swarm Intelligence Bầy đàn thông minh vi DANH MỤC CÁC BẢNG Số hiệu bảng 3.1 3.2 Tên bảng Mô tả tập liệu thực nghiệm Tổng hợp kết thực nghiệm Trang 45 45 vii DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ Số hiệu hình đồ thị 1.1 1.2 1.3 1.4 1.5 1.6 2.1 2.2 2.3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 Tên hình đồ thị Minh họa ma trận người dùng – sản phẩm lọc cộng tác Các cá thể không gian lời giải (trước sau đạt mục tiêu) Vận tốc vị trí cập nhật khơng gian tìm kiếm Các topology lân cận hình sao, dạng vịng bánh xe PSO Vị trí vận tốc cá thể cập nhật tồn cục Vị trí vận tốc cá thể cập nhật cục Giải thuật User_KNN Item_KNN Mơ hình hệ thống phân cụm lọc cộng tác Mơ hình lọc cộng tác tối ưu trọng số Mô tả biểu diễn người dùng, mục tin đánh giá tập liệu Giá trị thang đo MAE RMSE UserNBCF MAE RMSE userICCF - PSO FW (25 75) MAE RMSE userICCF - PSO FW (50 100) MAE RMSE userICCF - PSO FW (150 200) MAE RMSE userICCF - PSO FW (175 220) MAE RMSE userICCF - PSO FW (275 350) MAE RMSE ItemNBCF MAE RMSE itemICCF - PSO FW (25 75) Trang 10 15 15 16 16 17 21 23 27 34 36 36 37 37 38 38 39 39 viii Số hiệu hình đồ thị 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 Tên hình đồ thị MAE RMSE itemICCF - PSO FW (50 100) MAE RMSE itemICCF - PSO FW (150 200) MAE RMSE itemICCF - PSO FW (175 220) MAE RMSE itemICCF - PSO FW (275 350) MAE RMSE UserItemNBCF MAE RMSE useritemICCF - PSO FW (25 - 75) MAE RMSE useritemICCF - PSO FW (50 - 100) MAE RMSE useritemICCF - PSO FW (150 - 200) MAE RMSE useritemICCF - PSO FW (175 - 220) MAE RMSE useritemICCF - PSO FW (275 - 350) MAE NBCF ICCF-PSO FW (50-100) RMSE NBCF ICCF-PSO FW (50-100) MAE NBCF ICCF-PSO FW (275-350) RMSE NBCF ICCF-PSO FW (275-350) Trang 40 40 41 41 42 42 43 43 44 44 46 46 47 47 PHỤ LỤC Script_01.py from Collaborative_Filltering import uuCF from pso_v1 import PSO from CF_PSO_FW import CF_PSO import time import numpy as np import pandas as pd from loadData import LoadData path1 = 'ml-100k/ua.base' 10 path2 = 'ml-100k/ua.test' 11 load_data = LoadData(path1, path2) 12 13 n_user = [25, 50, 150, 175, 275] 14 n_item = [75, 100, 200, 220, 300] 15 16 for i in range(len(n_user)): 17 rateTrain, rateTest = load_data.Data(n_user[i], n_item[i]) 18 rateTrain[:, :2] -= 19 rateTest[:, :2] -= 20 nTest = rateTest.shape[0] 21 userNBCF = uuCF(rateTrain, k = 2) 22 userNBCF.fit() 23 SE_1 = 24 SE_2 = 25 for n in range(nTest): 26 pred = userNBCF.predict(rateTest[n, 0], rateTest[n, 1]) 27 SE_1 += np.abs(pred - rateTest[n , 2]) 28 SE_2 += (pred - rateTest[n, 2])**2 29 MAE = SE_1/nTest 30 RMSE = np.sqrt(SE_2/nTest) 31 print("MAE of userNBCF "+str(n_user[i]) + " user "+str(n_item[i]) + " i tem: ", MAE) 32 print("RMSE of userNBCF "+str(n_user[i]) + " user "+str(n_item[i]) + " item: ", RMSE) Script_02.py from Collaborative_Filltering import uuCF import time import numpy as np import pandas as pd from CF_PSO_FW import CF_PSO from loadData import LoadData from pso_v1 import PSO path1 = 'ml-100k/ua.base' 10 path2 = 'ml-100k/ua.test' 11 load_data = LoadData(path1, path2) 12 13 """ 14 n_user = [25, 50, 150, 175, 275] 15 n_item = [75, 100, 200, 220, 300] 16 """ 17 18 rateTrain, rateTest = load_data.Data(25, 75) 19 rateTrain[:, :2] -= 20 rateTest[:, :2] -= 21 22 """ PSO wI """ 23 24 def funcMAE(w): 25 userICCF = CF_PSO(rateTrain, w, 4) 26 userICCF.fitness() 27 n = rateTest.shape[0] 28 SE = 29 for i in range(n): 30 pred = userICCF.predict(rateTest[i, 0], rateTest[i, 1]) 31 SE += np.abs(pred - rateTest[i, 2]) 32 return (SE/n) 33 34 def funcRMSE(w): 35 userICCF = CF_PSO(rateTrain, w, 4) 36 userICCF.fitness() 37 n = rateTest.shape[0] 38 SE = 39 40 41 42 43 44 45 46 47 48 49 50 51 for i in range(n): pred = userICCF.predict(rateTest[i, 0], rateTest[i, 1]) SE += (pred - rateTest[i, 2])**2 return np.sqrt(SE/n) def runPSO_FW(fx, filenameCSV): wI_dim = int(max(rateTrain[:, 1])) + wI_PSO = PSO(fx, wI_dim, 30, 80) wI_PSO.fit(filenameCSV) wI_PSO.plot_Gbest_fx('Iteration', 'MAE - RMSE of ICCF PSO FW') runPSO_FW(funcMAE, "MAEwI.csv") runPSO_FW(funcRMSE, "RMSEwI.csv") Script_03.py from Collaborative_Filltering import uuCF from pso_v1 import PSO from CF_PSO_FW import CF_PSO import time import numpy as np import pandas as pd from loadData import LoadData path1 = 'ml-100k/ua.base' 10 path2 = 'ml-100k/ua.test' 11 load_data = LoadData(path1, path2) 12 13 14 15 16 n_user = [25, 50, 150, 175, 275] 17 n_item = [75, 100, 200, 220, 300] 18 19 for i in range(len(n_user)): 20 rateTrain, rateTest = load_data.Data(n_user[i], n_item[i]) 21 rateTrain = rateTrain[:, [1, 0, 2]] 22 rateTest = rateTest[:, [1, 0, 2]] 23 rateTrain[:, :2] -= 24 rateTest[:, :2] -= 25 nTest = rateTest.shape[0] 26 itemNBCF = uuCF(rateTrain, k = 2) 27 itemNBCF.fit() 28 SE_1 = 29 SE_2 = 30 for n in range(nTest): 31 pred = itemNBCF.predict(rateTest[n, 0], rateTest[n, 1]) 32 SE_1 += np.abs(pred - rateTest[n , 2]) 33 SE_2 += (pred - rateTest[n, 2])**2 34 MAE = SE_1/nTest 35 RMSE = np.sqrt(SE_2/nTest) 36 print("MAE of itemNBCF "+str(n_user[i]) + " user "+str(n_item[i]) + " i tem: ", MAE) 37 print("RMSE of itemNBCF "+str(n_user[i]) + " user "+str(n_item[i]) + " item: ", RMSE) Script_04.py from Collaborative_Filltering import uuCF import time import numpy as np import pandas as pd from CF_PSO_FW import CF_PSO from loadData import LoadData from pso_v1 import PSO path1 = 'ml-100k/ua.base' 10 path2 = 'ml-100k/ua.test' 11 load_data = LoadData(path1, path2) 12 13 """ 14 n_user = [25, 50, 150, 175, 275] 15 n_item = [75, 100, 200, 220, 300] 16 """ 17 18 rateTrain, rateTest = load_data.Data(150, 200) 19 rateTrain[:, :2] -= 20 rateTest[:, :2] -= 21 rateTrain = rateTrain[:, [1, 0, 2]] 22 rateTest = rateTest[:, [1, 0, 2]] 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 """ PSO wU """ def funcMAE(w): itemICCF = CF_PSO(rateTrain, w, 4) itemICCF.fitness() n = rateTest.shape[0] SE = for i in range(n): pred = itemICCF.predict(rateTest[i, 0], rateTest[i, 1]) SE += np.abs(pred - rateTest[i, 2]) return (SE/n) def funcRMSE(w): itemICCF = CF_PSO(rateTrain, w, 4) itemICCF.fitness() n = rateTest.shape[0] SE = for i in range(n): pred = itemICCF.predict(rateTest[i, 0], rateTest[i, 1]) SE += (pred - rateTest[i, 2])**2 return np.sqrt(SE/n) def runPSO_FW(fx, filenameCSV): wI_dim = int(max(rateTrain[:, 1])) + wI_PSO = PSO(fx, wI_dim, 30, 80) wI_PSO.fit(filenameCSV) wI_PSO.plot_Gbest_fx('Iteration', 'MAE - RMSE of ICCF PSO FW') runPSO_FW(funcMAE, "MAEwU.csv") runPSO_FW(funcRMSE, "RMSEwU.csv") Script_05.py from Collaborative_Filltering import uuCF import time import numpy as np import pandas as pd from loadData import LoadData from CF_PSO_FW import CF_PSO 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 from pso_v1 import PSO path1 = 'ml-100k/ua.base' path2 = 'ml-100k/ua.test' load_data = LoadData(path1, path2) n_user = [25, 50, 150, 175, 275] n_item = [75, 100, 200, 220, 300] for i in range(len(n_user)): rTrain1, rTest1 = load_data.Data(n_user[i], n_item[i]) # using userNBCF rTrain1[:, :2] -= rTest1[:, :2] -= rTrain2 = rTrain1[:, [1, 0, 2]] # using itemNBCF rTest2 = rTest1[:, [1, 0, 2]] nTest = rTest1.shape[0] userNBCF = uuCF(rTrain1, k=2) userNBCF.fit() itemNBCF = uuCF(rTrain2, k=2) itemNBCF.fit() alpha = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9] MAE = [] RMSE = [] for a in (alpha): SE_1 = SE_2 = for n in range(nTest): predU = userNBCF.predict(rTest1[n, 0], rTest1[n, 1]) predI = itemNBCF.predict(rTest2[n, 0], rTest2[n, 1]) pred = a*predU + (1-a)*predI SE_1 += np.abs(pred - rTest1[n, 2]) SE_2 += (pred - rTest1[n, 2])**2 MAE.append(SE_1/nTest) RMSE.append(np.sqrt(SE_2/nTest)) index1 = np.argmin(MAE) index2 = np.argmin(RMSE) 46 alphaMAE = alpha[index1] 47 alphaRMSE = alpha[index2] 48 49 """ predict with alpha """ 50 SE_1 = 51 SE_2 = 52 for n in range(nTest): 53 predU = userNBCF.predict(rTest1[n, 0], rTest1[n, 1]) 54 predI = itemNBCF.predict(rTest2[n, 0], rTest2[n, 1]) 55 predMAE = alphaMAE*predU + (1-alphaMAE)*predI 56 predRMSE = alphaRMSE*predU + (1 - alphaRMSE)*predI 57 58 SE_1 += np.abs(predMAE - rTest1[n, 2]) 59 SE_2 += (predRMSE - rTest1[n, 2])**2 60 MAE = SE_1/nTest 61 RMSE = np.sqrt(SE_2/nTest) 62 print("MAE of useritemNBCF with alpha= "+str(alphaMAE)+\ 63 " user "+str(n_user[i])+" item "+str(n_item[i])+": ", MAE) 64 print("RMSE of useritemNBCF with alpha= "+str(alphaRMSE)+\ 65 " user "+str(n_user[i])+" item "+str(n_item[i])+": ", RMSE) Script_06.py from Collaborative_Filltering import uuCF import time import numpy as np import pandas as pd from loadData import LoadData from CF_PSO_FW import CF_PSO from pso_v1 import PSO path1 = 'ml-100k/ua.base' 10 path2 = 'ml-100k/ua.test' 11 load_data = LoadData(path1, path2) 12 13 """ 14 n_user = [25, 50, 150, 175, 275] 15 n_item = [75, 100, 200, 220, 350] 16 """ 17 18 rTrain1, rTest1 = load_data.Data(175, 220) 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 rTrain1[:, :2] -= rTest1[:, :2] -= rTrain2 = rTrain1[:, [1, 0, 2]] rTest2 = rTest1[:, [1, 0, 2]] def funcMAE(w): Dim_wI = int(max(rTrain2[:, 0])) + userICCF = CF_PSO(rTrain1, w[:Dim_wI], 4) userICCF.fitness() itemICCF = CF_PSO(rTrain2, w[Dim_wI : -1], 4) itemICCF.fitness() n_test = rTest1.shape[0] SE = for n in range(n_test): predU = userICCF.predict(rTest1[n, 0], rTest1[n, 1]) predI = itemICCF.predict(rTest2[n, 0], rTest2[n, 1]) pred = w[-1]*predU + (1 - w[-1])*predI SE += np.abs(pred - rTest1[n, 2]) MAE =(SE/n_test) return MAE def funcRMSE(w): Dim_wI = int(max(rTrain2[:, 0])) + userICCF = CF_PSO(rTrain1, w[:Dim_wI], 4) userICCF.fitness() itemICCF = CF_PSO(rTrain2, w[Dim_wI : -1], 4) itemICCF.fitness() n_test = rTest1.shape[0] SE = for n in range(n_test): predU = userICCF.predict(rTest1[n, 0], rTest1[n, 1]) predI = itemICCF.predict(rTest2[n, 0], rTest2[n, 1]) pred = w[-1]*predU + (1 - w[-1])*predI SE += (pred - rTest1[n, 2])**2 RMSE =np.sqrt(SE/n_test) return RMSE def runPSO_FW(fx, filenameCSV): w = int(max(rTrain1[:, 0]) + 1) +int(max(rTrain1[:, 1]) + 1) + 58 59 60 61 62 63 iuCFPSO = PSO(fx, w, 30, 80) iuCFPSO.fit('w_Pbest.csv') iuCFPSO.plot_Gbest_fx('Iteration', 'MAE - RMSE of ICCF PSO FW') runPSO_FW(funcMAE, "MAEw.csv") runPSO_FW(funcRMSE, "RMSEw.csv") ... để nghiên cứu việc ứng dụng thuật toán PSO vào hệ thống gợi ý chương 20 CHƯƠNG ỨNG DỤNG THUẬT TOÁN TỐI ƯU BẦY ĐÀN VÀO HỆ THỐNG GỢI Ý Chương trình bày phương pháp lọc thơng tin hệ thống gợi ý: ... giá hệ thống 4 CHƯƠNG TỔNG QUAN VỀ HỆ THỐNG GỢI Ý VÀ THUẬT TỐN PSO Chương trình bày tổng quan vấn đề hệ thống gợi ý thuật toán tối ưu bầy đàn PSO Trong đó, kĩ thuật lọc thơng tin hệ thống gợi ý, ... nên hệ thống gợi ý chất lượng cao, phục vụ tốt số toán gợi ý thực tế, giúp người dùng đưa định xác Xuất phát từ lý trên, chọn đề tài ? ?Nghiên cứu ứng dụng thuật toán tối ưu bầy đàn vào hệ thống gợi