ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA PHAN PHƯƠNG LAN HỆ TƯ VẤN DỰA TRÊN MỨC ĐỘ QUAN TRỌNG HÀM Ý THỐNG KÊ LUẬN ÁN TIẾN SĨ KỸ THUẬT Đà Nẵng - Năm 2019 ii ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA PHAN PHƯƠNG LAN HỆ TƯ VẤN DỰA TRÊN MỨC ĐỘ QUAN TRỌNG HÀM Ý THỐNG KÊ Chuyên ngành: Khoa học máy tính Mã số: 9480101 LUẬN ÁN TIẾN SĨ KỸ THUẬT Người hướng dẫn khoa học: PGS TS Huỳnh Xuân Hiệp TS Huỳnh Hữu Hưng Đà Nẵng - Năm 2019 LỜI CAM ĐOAN Tơi xin cam đoan cơng trình nghiên cứu thực hiện, hướng dẫn PGS.TS Huỳnh Xuân Hiệp TS Huỳnh Hữu Hưng Tôi cam đoan kết nghiên cứu trình bày luận án trung thực không chép từ cơng trình nghiên cứu khác Một số kết nghiên cứu thành tập thể đồng tác giả đồng ý cho sử dụng luận án Mọi trích dẫn luận án có ghi nguồn gốc xuất xứ rõ ràng đầy đủ Tác giả NCS Phan Phương Lan LỜI CẢM ƠN Trước tiên, tơi xin bày tỏ lịng biết ơn sâu sắc gửi lời tri ân đến PGS TS Huỳnh Xuân Hiệp TS Huỳnh Hữu Hưng tận tình hướng dẫn, truyền đạt kiến thức kinh nghiệm nghiên cứu khoa học cho suốt trình học tập, nghiên cứu hồn thành luận án Tơi xin chân thành cảm ơn Phịng Đào tạo Khoa Công nghệ thông tin Trường Đại học Bách khoa tạo điều kiện thuận lợi cho thời gian làm nghiên cứu sinh Xin cảm ơn Ban Lãnh đạo trường Đại học Cần Thơ, Khoa Công nghệ thông tin Truyền thông, Bộ môn Công nghệ phần mềm hỗ trợ tạo điều kiện tốt để tơi tập trung nghiên cứu Tơi xin bày tỏ lịng biết ơn chân thành đến GS TS Régis Gras cung cấp cho tơi nhiều tài liệu lý thuyết phân tích hàm ý thống kê có góp ý sâu sắc cho nghiên cứu Xin chân thành cảm ơn nhà khoa học dành thời gian công sức đọc đưa góp ý quý báu để luận án hồn chỉnh Cuối cùng, tơi xin gửi lời cảm ơn sâu sắc đến gia đình bạn thân - người ln bên cạnh, giúp đỡ động viên suốt thời gian học tập, nghiên cứu hoàn thành luận án Đà Nẵng, ngày 09 tháng 11 năm 2019 NCS Phan Phương Lan i MỤC LỤC MỤC LỤC I DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT VI DANH MỤC BẢNG VIII DANH MỤC HÌNH IX MỞ ĐẦU CHƯƠNG TỔNG QUAN .7 1.1 Mức độ quan trọng hàm ý thống kê 1.1.1 Định nghĩa mức độ quan trọng hàm ý thống kê 1.1.2 Mức độ quan trọng hàm ý thống kê cho liệu nhị phân 1.1.2.1 Mối quan hệ hàm ý thống kê liệu nhị phân 1.1.2.2 Chỉ số hàm ý cường độ hàm ý 10 1.1.2.3 Cường độ hàm ý có entropy 12 1.1.2.4 Chỉ số gắn kết 13 1.1.2.5 Chỉ số đóng góp 13 1.1.2.6 Chỉ số tiêu biểu 14 1.1.3 Mức độ quan trọng hàm ý thống kê cho liệu phi nhị phân 14 1.1.3.1 Mối quan hệ hàm ý thống kê liệu phi nhị phân 15 1.1.3.2 Mức độ quan trọng hàm ý thống kê cho liệu phi nhị phân 15 1.2 Mức độ quan trọng xếp hạng hàm ý thống kê 17 1.3 Hệ tư vấn hướng nghiên cứu 18 1.3.1 Hệ tư vấn 18 1.3.2 Phân loại hệ tư vấn 21 1.3.2.1 Hệ tư vấn thuộc nhóm cá thể 22 1.3.2.2 Hệ tư vấn thuộc nhóm cộng tác/cộng đồng 22 1.3.2.3 Hệ tư vấn thuộc nhóm chuyên gia 23 1.3.2.4 Hệ tư vấn thuộc nhóm lai ghép 24 ii 1.3.2.5 Hệ tư vấn thuộc nhóm theo ngữ cảnh 25 1.3.3 Các hướng nghiên cứu hệ tư vấn 26 1.3.3.1 Nghiên cứu liệu 26 1.3.3.2 Nghiên cứu đề xuất cải tiến phương pháp tư vấn 27 1.3.3.3 Nghiên cứu đánh giá hệ tư vấn 29 1.4 Kỹ thuật tư vấn lọc cộng tác 29 1.4.1 Kỹ thuật lọc cộng tác dựa nhớ (láng giềng) 29 1.4.2 Kỹ thuật lọc cộng tác dựa mơ hình 30 1.4.2.1 Tư vấn lọc cộng tác dựa luật kết hợp 30 1.4.2.2 Mơ hình nhân tố tiềm ẩn 31 1.5 Đánh giá hiệu tư vấn 32 1.5.1 Phương pháp đánh giá chéo k tập 35 1.5.2 Tính xác gợi ý 36 1.5.3 Tính xác xếp hạng dự đốn 37 1.5.4 Tính xác gợi ý thứ tự 38 1.6 Phương pháp tư vấn theo mức độ quan trọng hàm ý thống kê 39 1.6.1 Tư vấn dựa phân tích hàm ý thống kê có 40 1.6.2 Tư vấn dựa mức độ quan trọng hàm ý thống kê 41 1.7 Kết luận chương 43 CHƯƠNG TƯ VẤN THEO MỨC ĐỘ QUAN TRỌNG HÀM Ý THỐNG KÊ TRÊN LUẬT KẾT HỢP 44 2.1 Mơ hình tư vấn theo mức độ quan trọng hàm ý thống kê luật SIR 44 2.1.1 Mơ hình tư vấn SIR 44 2.1.2 Mơ hình tư vấn SIR cải tiến 48 2.2 Hoạt động mơ hình tư vấn theo mức độ quan trọng hàm ý thống kê luật 49 2.2.1 Hoạt động mơ hình tư vấn SIR 49 2.2.2 Hoạt động mơ hình tư vấn SIR cải tiến 53 2.3 Đánh giá hiệu tư vấn mơ hình SIR 54 2.3.1 Dữ liệu thực nghiệm mơ hình SIR 54 2.3.2 Công cụ thực nghiệm mơ hình SIR 56 iii 2.3.3 Hiệu tư vấn mơ hình SIR liệu nhị phân 57 2.3.3.1 Các giá trị tham số phù hợp 58 2.3.3.2 Thời gian xây dựng mơ hình tư vấn trước sau cải tiến 60 2.3.3.3 Tính xác gợi ý qua so sánh nội liệu nhị phân 62 2.3.3.4 Tính xác gợi ý qua so sánh ngoại liệu nhị phân 66 2.3.3.5 Mơ hình tư vấn SIR gợi ý đăng ký học phần 69 2.3.4 Hiệu tư vấn mơ hình SIR liệu phi nhị phân 69 2.3.4.1 Tính xác gợi ý qua so sánh nội liệu phi nhị phân 70 2.3.4.2 Tính xác gợi ý qua so sánh ngoại liệu phi nhị phân 73 2.4 Kết luận chương 75 CHƯƠNG TƯ VẤN THEO MỨC ĐỘ QUAN TRỌNG XẾP HẠNG HÀM Ý THỐNG KÊ TRÊN NGƯỜI DÙNG .77 3.1 Định nghĩa mức độ quan trọng xếp hạng hàm ý thống kê người dùng 78 3.2 Mơ hình tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê người dùng UIR 79 3.3 Hoạt động mơ hình tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê người dùng 81 3.4 Đánh giá hiệu tư vấn mơ hình UIR 85 3.4.1 Dữ liệu thực nghiệm mơ hình UIR 85 3.4.2 Công cụ thực nghiệm mơ hình UIR 86 3.4.3 Đánh giá mơ hình UIR qua tính xác gợi ý 86 3.4.3.1 Tính xác mơ hình UIR qua so sánh ngoại 87 3.4.3.2 Tính xác mơ hình UIR qua so sánh nội 92 3.4.4 Đánh giá mơ hình UIR qua tính xác xếp hạng dự đoán 95 3.4.4.1 Sai số mơ hình UIR qua so sánh ngoại 95 3.4.4.2 Sai số mơ hình UIR qua so sánh nội 98 3.4.5 Đánh giá mơ hình UIR qua tính xác gợi ý thứ tự 99 3.4.5.1 Độ lợi tích lũy giảm dần mơ hình UIR liệu nhị phân 100 3.4.5.2 Độ lợi tích lũy giảm dần mơ hình UIR liệu phi nhị phân 101 3.5 Kết luận chương 103 iv CHƯƠNG TƯ VẤN THEO MỨC ĐỘ QUAN TRỌNG XẾP HẠNG HÀM Ý THỐNG KÊ TRÊN MỤC 104 4.1 Định nghĩa mức độ quan trọng xếp hạng hàm ý thống kê mục liệu 105 4.2 Mơ hình tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê mục IIR 106 4.3 Hoạt động mơ hình tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê mục 109 4.4 Đánh giá hiệu tư vấn mơ hình IIR 111 4.4.1 Dữ liệu công cụ thực nghiệm mơ hình IIR 111 4.4.2 Thời gian xây dựng ma trận mục trực tiếp gián tiếp 112 4.4.3 Đánh giá mơ hình IIR qua tính xác gợi ý 113 4.4.3.1 Tính xác mơ hình IIR qua so sánh nội 114 4.4.3.2 Tính xác mơ hình IIR qua so sánh ngoại 116 4.4.3.3 Tính ổn định mơ hình IIR 118 4.4.4 Đánh giá mơ hình IIR qua tính xác xếp hạng dự đốn 121 4.4.4.1 Sai số mơ hình IIR qua so sánh nội 122 4.4.4.2 Sai số mơ hình IIR qua so sánh ngoại 126 4.4.5 Đánh giá mơ hình IIR qua tính xác gợi ý thứ tự 128 4.5 So sánh hiệu tư vấn mô hình đề xuất 130 4.5.1 So sánh thời gian tư vấn 130 4.5.2 So sánh tính xác mơ hình 132 4.5.3 Đánh giá chung mơ hình đề xuất 136 4.6 Kết luận chương 138 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 139 Kết luận 139 Hướng phát triển 140 DANH MỤC CÁC CƠNG TRÌNH KHOA HỌC ĐÃ CƠNG BỐ 141 TÀI LIỆU THAM KHẢO 143 PHỤ LỤC Phụ lục 1: Công cụ Interestingnesslab tập liệu DKHP v Công cụ Interestingnesslab Tập liệu DKHP Phụ lục 2: Giải thuật tư vấn theo mức độ quan trọng hàm ý thống kê luật kết hợp Sinh tập luật dựa ngưỡng hỗ trợ, ngưỡng tin cậy độ dài tối đa luật Biểu diễn tập luật theo phân tích hàm ý thống kê Tính cường độ hàm ý, số gắn kết luật Lọc tập luật theo ngưỡng cường độ hàm ý số gắn kết Phụ lục 3: Giải thuật tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê người dùng 10 Biểu diễn mối quan hệ hai người dùng theo phân tích hàm ý thống kê 10 Tính cường độ hàm ý hai người dùng 11 Tìm láng giềng gần người cần tư vấn 12 Xác định số tiêu biểu mục mối quan hệ hàm ý hai người dùng 12 Dự đoán xếp hạng người dùng cho mục liệu 14 Phụ lục 4: Giải thuật tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê mục liệu 15 Xây dựng ma trận mục liệu - gián tiếp 15 Xây dựng ma trận mục liệu - trực tiếp 16 Dự đoán xếp hạng người dùng cho mục liệu 17 Phụ lục 5: Giải thuật đánh giá hệ tư vấn 18 Phụ lục 6: Xác định giá trị tham số phù hợp mơ hình SIR, AR IBCF 21 Ngưỡng tin cậy hỗ trợ mơ hình SIR, AR 21 Độ dài tối đa luật mơ hình SIR, AR 22 Số láng giềng gần mô hình IBCF 25 vi DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT Thuật ngữ Cường độ hàm ý Tiếng Anh Implication/Implicative intensity Propension intensity Cường độ hàm ý có entropy Entropic version of implicative intensity Chỉ số gắn kết Cohesion measure Chỉ số hàm ý Viết tắt Implication/Implicative index Propesion index Chỉ số tiêu biểu Typicality measure Chỉ số đóng góp Contribution measure Độ đo hấp dẫn khách quan Objective interestingness measure Độ lợi tích lũy giảm dần Normalized discounted cumulative gain nDCG Hệ tư vấn Recommender/Recommendation systems RS Mơ hình tư vấn theo mức độ quan trọng hàm ý thống kê luật Statistical implicative rules based model SIR Mô hình tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê mục Item implicative rating based model IIR Mơ hình tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê người dùng User implicative rating based model UIR Mục/Mục liệu Item Phân tích hàm ý thống kê Statistical implicative analysis Phản ví dụ Counter-example Sai số bình phương trung bình Root of mean squared error RMSE Sai số tuyệt đối trung bình Mean absolute error MAE SIA 12 } else { qab_= (nab_ - lambda) / sqrt(lambda) Sum = pnorm(qab_) } /* Tính cường độ hàm ý mối quan hệ (ua,uj) theo công thức cường độ hàm ý Chương 1*/ Iintensity[uj]=1-Sum; } return(Iintensity); Tìm láng giềng gần người cần tư vấn Giải thuật 3.4 trình bày cách thức tìm 𝑘𝑛𝑛 láng giềng gần người cần tư vấn 𝑢 Trong q trình thực hiện, sử dụng giá trị cường độ hàm ý hai người dùng tính Giải thuật 3.3 Giải thuật 3.4: Tìm knn láng giềng gần người cần tư vấn findKNearestNeighbors Đầu vào: vector Iintensity chứa giá trị cường độ hàm ý (𝑢 , 𝑢 ) với 𝑢 ∈ 𝑈 số láng giềng gần knn cần tìm Đầu ra: vector Neighbors chứa định danh 𝑢 láng giềng gần ua Các bước xử lý: /* Sắp xếp lại vector Iintensity theo giá trị cường độ hàm ý giảm dần */ Sortedlist= sortList(Iintensity); /* Trích xuất knn định danh người dùng có cường độ hàm ý cao */ Neighbors=extractID(Sortedlist,knn); return(Neighbors); Xác định số tiêu biểu mục mối quan hệ hàm ý hai người dùng Giải thuật 3.5 trình bày cách thức tính số tiêu biểu mục liệu 𝑖 ∈ 𝐼 mối quan hệ hàm ý hai người dùng (𝑢 , 𝑢 ) với 𝑢 ∈ 𝑈 13 Giải thuật 3.5: Tính số tiêu biểu mục mối quan hệ hàm ý hai người dùng - calculateTypicality Đầu vào: Vector A lưu thông tin xếp hạng ua, vector Neighbors chứa knn láng giềng gần ua, ma trận xếp hạng có tên R vector Iintensity chứa giá trị cường độ hàm ý (𝑢 , 𝑢 ) với 𝑢 ∈ 𝑈 Đầu ra: ma trận có tên Typicality chứa số tiêu biểu mục liệu 𝑖 ∈ 𝐼 mối quan hệ (𝑢 , 𝑢 ) 𝑢 knn láng giềng gần ua Các bước xử lý: /* Lọc lại ma trận xếp hạng R cho R chứa thông tin k láng giềng gần ua */ R=R[Neighbors,]; /* Lọc lại vector Iintensity cho Iintensity chứa cường độ hàm ý ua với knn láng giềng gần */ Iintensity=Iintensity[Neighbors]; /* Xác định số đóng góp mục liệu 𝑖 ∈ 𝐼 tồn mối quan hệ (𝑢 , 𝑢 ) 𝑢 knn láng giềng gần ua theo cơng thức Chương 1; sau tính khoảng cách từ 𝑖 ∈ 𝐼 đến (𝑢 , 𝑢 ) công thức Chương */ for each ujNeighbors for each item iI { if (R[uj,i]=1) Contribution[uj,i]=1.0; else if (A[i]=1 and R[uj,i]=0) Contribution[uj,i]=0.0; else if (A[i]=0 and R[uj,i]=0) Contribution[uj,i]=0.5; Dist[uj,i]=sqrt((Iintensity[uj] - Contribution[uj,i])^2 / (1-Iintensity[uj])); } /* Xác định số tiêu biểu mục liệu 𝑖 ∈ 𝐼 tồn mối quan hệ (𝑢 , 𝑢 ) công thức Chương */ Typicality=; for each uiNeighbors { 14 Rowmax=maxRow(dist[ui,]); Typic=1- Dist[ui,]/Rowmax; Typicality=bindRow(Typicality,Typic) } rowNames(Typicality)=rowNames(Neighbors); columnNames(Typicality)=columnNames(R); return(Typicality); Dự đoán xếp hạng người dùng cho mục liệu Mức độ quan trọng xếp hạng hàm ý thống kê UIR sử dụng để dự đoán xếp hạng người cần tư vấn 𝑢 cho mục liệu 𝑖 ∈ 𝐼 thực Giải thuật 3.6 Giải thuật 3.6: Dự đoán giá trị xếp hạng người dùng cho mục liệu predictRating Đầu vào: Vector Neighbors chứa knn láng giềng gần ua, ma trận xếp hạng có tên R vector Typicality chứa số tiêu biểu mục liệu 𝑖 ∈ 𝐼 mối quan hệ (𝑢 , 𝑢 ) 𝑢 knn láng giềng gần ua Đầu ra: vector có tên KnnUIR lưu giá trị xếp hạng ua cho mục liệu 𝑖 ∈ 𝐼 Các bước xử lý: /* Xác định giá trị xếp hạng KnnUIR ua cho mục liệu 𝑖 ∈ 𝐼 theo công thức Chương */ for each item iI KIR[ua,i]=sumColumn(Typicality[Neighbors,i]*R[Neighbors,i]); KnnUIR[ua,]=KIR[ua,]/maxRow(KIR[ua,]); return(KnnUIR); 15 Phụ lục 4: Giải thuật tư vấn theo mức độ quan trọng xếp hạng hàm ý thống kê mục liệu Xây dựng ma trận mục liệu - gián tiếp Giải thuật 4.2 𝑐𝑟𝑒𝑎𝑡𝑒𝑀𝑎𝑡𝑟𝑖𝑥 sử dụng để xây dựng ma trận mục liệu 𝑉 Dữ liệu đầu vào giải thuật ma trận xếp hạng 𝑅 số láng giềng gấn 𝑘𝑛𝑛 Giải thuật thực bước xử lý: - Gán ngưỡng hỗ trợ 𝑠 = 0, tin cậy 𝑐 = độ dài tối đa luật 𝑙 = - Sinh tập luật dựa ngưỡng hỗ trợ, tin cậy dùng giải thuật Apriori Ở đây, chúng tơi tìm luật có độ dài (có dạng 𝑖 → 𝑖 với 𝑖 ∈ 𝐼, 𝑖 ∈ 𝐼); - Biểu diễn tập luật theo phân tích hàm ý thống kê, theo luật biểu diễn bốn giá trị {𝑛, 𝑛 , 𝑛 , 𝑛 }; thực tính giá trị cường độ hàm ý luật tập luật Giải thuật thực bước trình bày Phụ lục - Tạo ma trận 𝑉 lưu giá trị cặp mục theo cơng thức (4.2) Trong đó, cường độ hàm ý độ tin cậy luật xác định bước - Lọc lại ma trận mục cho với mục liệu 𝑖, giữ lại 𝑘𝑛𝑛 mục 𝑖 có mối quan hệ mạnh với 𝑖 thông qua giá trị 𝑣 Giải thuật 4.2 createMatrix: Tạo ma trận mục liệu lưu giá trị mối quan hệ (𝒊𝒋 , 𝒊) lọc lại ma trận theo knn láng giềng gần Đầu vào: ma trận xếp hạng 𝑅, số láng giềng gần knn Đầu ra: ma trận 𝑉 chứa giá trị mối quan hệ (𝑖 , 𝑖) createMatrix(ratingmatrix R; int knn) { /* Gán ngưỡng cần cho hoạt động sinh luật kết hợp */ float s=0; float c=0; int l=2; /* Sinh tập luật tính giá trị tin cậy luật */ Ruleset = createRules(R,s,c,l); /* Biểu diễn tập luật theo phân tích hàm ý thống kê tính cường độ hàm ý luật */ Ruleset = presentRules(Ruleset,R); for luật rk có dạng ij  i thuộc tập luật Ruleset { /* Lấy giá trị cường độ hàm ý lưu Ruleset */ 16 IInt[ij,i] = getImplicativeIntensity(Ruleset,rk) /* Lấy giá trị tin cậy lưu Ruleset */ Conf[ij,i] = getConfidence(Ruleset,rk); /* Tính giá trị luật theo công thức (4.2) */ V[ij,i] = IInt[ij,i] * Conf[ij,i]; } /* Lọc lại ma trận V: với mục liệu, lấy knn láng giềng gần */ V = filteredMatrix(V,knn); return V; } Xây dựng ma trận mục liệu - trực tiếp Giải thuật 4.3 𝑐𝑟𝑒𝑎𝑡𝑒_𝑀_𝑀𝑎𝑡𝑟𝑖𝑥 sử dụng để xây dựng trực tiếp ma trận mục liệu 𝑉 Dữ liệu đầu vào giải thuật ma trận xếp hạng 𝑅 số láng giềng gần 𝑘𝑛𝑛 Giải thuật 4.3 thực bước xử lý sau: Với cặp mục liệu 𝑖 , 𝑖, - Biểu diễn mối quan hệ (𝑖 , 𝑖) theo bốn giá trị {𝑛, 𝑛 , 𝑛 , 𝑛 ̅ } - Tính giá trị tin cậy c(𝑖 , 𝑖)=1-𝑛 ̅/𝑛 - Tính giá trị cường độ hàm ý ((𝑖 , 𝑖) - Tính V[(𝑖 , 𝑖] = ((𝑖 , 𝑖)* c((𝑖 , 𝑖) Ta bổ sung ngưỡng tin cậy 𝑐 tham số đầu vào để lọc lại mối quan hệ có độ tin cậy ≥c Mặc nhiên, V[(𝑖 , 𝑖] có giá trị - Lọc lại ma trận mục cho với mục liệu 𝑖, giữ lại knn mục 𝑖 có mối quan hệ mạnh (giá trị 𝑣) với 𝑖 Giải thuật 4.3 create_M_Matrix: Tạo ma trận mục liệu lưu giá trị mối quan hệ (𝒊𝒋 , 𝒊) lọc lại ma trận theo knn láng giềng gần Đầu vào: ma trận xếp hạng 𝑅, ngưỡng tin cậy 𝑐, số láng giềng gần knn Đầu ra: ma trận 𝑉 chứa giá trị mối quan hệ (𝑖 , 𝑖) (𝑖 → 𝑖 với 𝑖 ∈ 𝐼 𝑖 ∈ 𝐼) create_M_Matrix(ratingmatrix R; float c=0; int knn) { V = Khoitaomatran(0, m, m); for muc du lieu ijI for muc du lieu iI { 17 card = Timbobanso(R); c[ij,i] = Tinhdotincay(card); if (c[ij,i] ≥ c) then { [ij,i] = Tinhcuongdohamy(card); V[ij,i] = [ij,i] * c[ij,i]; } } /* Lọc lại ma trận V: với mục liệu, lấy knn láng giềng gần */ V = filteredMatrix(V,knn); return V; } Dự đoán xếp hạng người dùng cho mục liệu Giải thuật 4.4 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑅𝑎𝑡𝑖𝑛𝑔𝑠 dự đoán xếp hạng người cần tư vấn 𝑢 cho mục liệu 𝑖 ∈ 𝐼 Đầu vào giải thuật vector 𝐴 có kích thước 𝑚 lưu xếp hạng người dùng 𝑢 cần tư vấn; ma trận 𝑉 xác định giải thuật 𝑓𝑖𝑙𝑡𝑒𝑟𝑒𝑑𝑀𝑎𝑡𝑟𝑖𝑥 Đầu giải thuật vector 𝐾𝑛𝑛𝐼𝐼𝑅 có kích thước 𝑚 lưu xếp hạng dự đoán người dùng 𝑢 cho mục liệu 𝑖 ∈ 𝐼 Giải thuật 4.4 predictRatings: Dự đoán giá trị xếp hạng người dùng cho mục liệu Đầu vào: ma trận 𝑉, vector 𝐴 chứa xếp hạng thực 𝑢 Đầu ra: vector có tên 𝐾𝑛𝑛𝐼𝐼𝑅 lưu giá trị xếp hạng dự đoán ua cho mục liệu 𝑖 ∈ 𝐼 predictRatings(vector A; matrix IInt_Conf, ) { for mục i I { AIR1[ua,i] = sum(A[ij]*V[ij,i]) với ij I; AIR2[ua,i] = sum((A[ij]!=0)*V[ij,i]) với ij I; if (getDatatype(A)==”binary”) KnnIIR[ua, i] = AIR1[ua, i]/AIR2[ua, i]); } if (getDatatype(A)==”binary”) KnnIIR[ua, ] = AIR1[ua, ]/max(AIR1[ua, ]); return KnnIIR; } 18 Phụ lục 5: Giải thuật đánh giá hệ tư vấn Giải thuật evaluateModels thực đánh giá hiệu tư vấn mơ hình theo nhóm độ đo tính xác gợi ý Dữ liệu đầu vào giải thuật ma trận xếp hạng, tên mơ hình tư vấn tham số cần có mơ hình để xây dựng hệ tư vấn, số tập 𝑘 cần cho việc phân tách liệu phương pháp k-fold, số xếp hạng biết trước người dùng tập truy vấn 𝑔𝑖𝑣𝑒𝑛 vector lưu số mục cần gợi ý 𝑛 Dữ liệu đầu tập tin định dạng 𝑐𝑠𝑣 lưu giá trị độ đo đánh giá theo số mục mục gợi ý mơ hình có định dạng Bảng Phụ lục 5.1, biểu đồ vẽ đường cong ROC biểu đồ vẽ đường cong Precision – Recall Bảng Phụ lục 5.1: Định dạng tập tin lưu giá trị độ đo đánh giá hệ tư vấn theo số mục gợi ý Tên mơ hình: Số mục gợi ý TP FP FN TN Precision Recall TPR FPR F1 Accuracy Giải thuật evaluateModels: Đánh giá hệ tư vấn Đầu vào: ma trận xếp hạng có tên R, tên mơ hình tư vấn tham số cần thiết cho mơ hình để xây dựng hệ tư vấn, số tập k cần cho việc phân tách liệu, số mục biết trước given tập truy vấn vector n lưu số mục cần gợi ý Đầu ra: tập tin lưu giá trị độ đo đánh giá hệ tư vấn, biểu đồ vẽ đường cong ROC biểu đồ vẽ đường cong Precision - Recall Các bước xử lý: /* Phân tách liệu theo phương pháp k-fold */ sets=splitKFolds(R,k); /* Lập danh sách mơ hình tư vấn so sánh */ Modellist=createModelList(list(Modelname,Modelparams),…, list(Modelname,Modelparams)); 19 /* Tính giá trị độ đo đánh giá cho mơ hình tư vấn danh sách Modellist */ for m=1 to length( Modellist) { /* Thực lần đánh giá k lần */ for r=1 to k { /* Lấy tập liệu huấn luyện, truy vấn đích*/ Trainset=getData(sets,r); Queryset=getData(sets,r); Targetset=getData(sets,r); /* Học mơ hình tư vấn */ Model=createModel (Trainset,getName(Modellist[m]), getParams(Modellist[m])); /* Thực gợi ý tính giá trị theo độ đo đánh giá */ for i=1 to length(n) { TopN=n[i]; /* Gợi danh sách TopN mục cho người dùng tập truy vấn Queryset */ Reclist=recommendTopItems(Model,Queryset,TopN); /* Tính giá trị theo độ đo đánh giá TN, FP, FN, TP, precision, recall, TPR, FPR, accuracy F1 */ Result=calculateValues(Reclist,Targetset); if (i=1) Resultlist=Result; else Resultlist=bindRow(Resultlist,Result); } /* Ghép kết lần thực thi vào cuối ma trận CMatrix */ if (r=1) Cmatrix=Resultlist; else Cmatrix=bindColumn(Cmatrix,Resultlist); } /* Tính giá trị trung bình k lần thực thi */ Mcmatrix=getAverage(Cmatrix); /* Ghép kết mơ hình lại với */ 20 if (m=1) Evaluationmatrix=Mcmatrix; else Evaluationmatrix=bindRow(Evaluationmatrix,Mcmatrix); } /* Lưu giá trị vào tập tin Vẽ biểu đồ */ write.csv(Evaluationmatrix,”Evaluationmatrix.csv”); plot(FPR(Evaluationmatrix),TPR(Evaluationmatrix), xlab=”FPR”,ylab=”TPR”,title=”ROC Curve”); plot(Recall (Evaluationmatrix), Precision (Evaluationmatrix), xlab=”Recall”,ylab=”Precision”,title=”Recall- Precision Curve”); Để đánh giá hiệu tư vấn mơ hình theo nhóm độ đo tính xác xếp hạng dự đoán (RMSE, MAE, MSE) hay theo độ đo tính xác gợi ý thứ tự (nDCG), ta làm tương tự 21 Phụ lục 6: Xác định giá trị tham số phù hợp mơ hình SIR, AR IBCF Ngưỡng tin cậy hỗ trợ mơ hình SIR, AR Với tập liệu MSWeb(875x135), Hình Phụ lục 6.1.a hiển thị đường cong ROC trung bình 30 lần chạy (times=30) phương pháp k tập (k=5) hệ tư vấn (s001c002 RS, s001c005 RS, s001c01 RS, s005c005 RS, s005c01 RS, s01c005 RS, s01c01 RS) Những hệ thống sử dụng mơ hình đề xuất có ngưỡng (hỗ trợ 𝑠, tin cậy 𝑐) (0,01, 0,02), (0,01, 0,05), (0,01, 0,1), (0,05, 0,05), (0,05, 0,1), (0,1, 0,05) (0,1, 0,1); số Vroot biết trước người dùng tập truy vấn (𝑔𝑖𝑣𝑒𝑛) 7; độ dài luật tối đa (𝑙) 2; số Vroot cần gợi ý cho người dùng 1, 2, 4, 6, 8, 10 12 Hình Phụ lục 6.1.b hiển thị đường cong ROC hệ tư vấn với (times, given, l) thay đổi (8, 5, 7) Hình Phụ lục 6.2 hiển thị đường cong Precision - Recall hệ tư vấn với (times, given, l) thay đổi (30, 3, 4) Hình Phụ lục 6.1.a Hình Phụ lục 6.1.b cho thấy diện tích đường cong ROC ba hệ tư vấn s001002 RS, s001005 RS s001c0 RS lớn diện tích nằm đường cong ROC khác Hình Phụ lục 6.2 cho thấy độ xác độ bao phủ ba hệ tư vấn s001002 RS, s001005 RS s001c01 RS cao so với hệ tư vấn lại Khi thay đổi giá trị (times, given, l), ta nhận kết tương tự hình Bên cạnh đó, với ngưỡng hỗ trợ 0,01, kích thước tập luật kết hợp tạo ngưỡng tin cậy 0,02 0,05 lớn kích thước tập luật tạo ngưỡng tin cậy 0,1 Do đó, ngưỡng hỗ trợ tin cậy chọn cho tập liệu MSWeb(875x135) 0,01 0,1 tương ứng Với cách làm tương tự tập liệu MSWeb(875x135), ngưỡng hỗ trợ tin cậy chọn cho tập DKHP(1.130x57) 0,01 0,1 tương ứng 22 Số Vroot gợi ý cho người dùng (a): (times, given, l) = (4, 6, 2) (b): (times, given, l) = (8, 5, 7) Hình Phụ lục 6.1: Đường cong ROC bẩy hệ tư vấn tập MSWeb(875x135) Số Vroot gợi ý cho người dùng (a): (times, given, l) = (2, 1, 4) (b): (times, given, l) = (6, 3, 5) Hình Phụ lục 6.2: Đường cong Precision - Recall bẩy hệ tư vấn tập MSWeb(875x135) Độ dài tối đa luật mơ hình SIR, AR Với ngưỡng tin cậy hỗ trợ xác định cho tập DKHP(1.130x57), ta thay đổi độ dài tối đa luật để quan sát hiệu hệ tư vấn từ đề nghị 23 ngưỡng độ dài luật phù hợp Bẩy hệ tư vấn mà độ dài tối đa luật thay đổi từ đến (Maxlength2 RS, Maxlength3 RS, Maxlength4 RS, Maxlength5 RS, Maxlength6 RS, Maxlength7 RS MaxRule Length8 RS) xây dựng Những hệ thống sử dụng mơ hình tư vấn dựa luật có ngưỡng hỗ trợ s=0,01 ngưỡng tin cậy c=0,1 Hình Phụ lục 6.3.a Hình Phụ lục 6.3.b hiển thị đường cong Precision - Recall trung bình lần đánh giá phương pháp k tập số học phần biết trước sinh viên cần tư vấn tương ứng Vì sinh viên đăng ký tối đa học phần nên số học phần cần gợi ý cho sinh viên (1, 2, 3, 4, 5) cho given=2 (1, 2) cho given=5 Hình Phụ lục 6.4.a Hình Phụ lục 6.4.b hiển thị đường cong ROC hệ tư vấn với (times, given) thay đổi (2, 2), (2, 4) Số học phần gợi ý cho sinh viên (a): (times, given) = (4, 3) (b): (times, given) = (4, 5) Hình Phụ lục 6.3: Đường cong Precision - Recall bẩy hệ tư vấn tập DKHP(1.130x57) 24 Số học phần gợi ý cho sinh viên (a): (times, given) = (2, 2) (b): (times, given) = (2, 4) Hình Phụ lục 6.4: Đường cong ROC bẩy hệ tư vấn tập DKHP(1.130x57) Hình Phụ lục 6.3 cho thấy: Khi sinh viên cần tư vấn đăng ký học phần (given=3), độ xác độ bao phủ hệ tư vấn có độ dài tối đa luật từ đến cao so với hệ tư vấn Maxlength2 RS, Maxlength3 RS; given đạt giá trị cao (given=5), độ xác độ bao phủ hệ tư vấn có độ dài tối đa luật từ đến cao so với hệ tư vấn cịn lại Bên cạnh đó, Hình Phụ lục 6.4 cho thấy: given=2, đường cong ROC hệ tư vấn có độ dài tối đa luật từ đến trùng nằm đường cong ROC hệ tư vấn Maxlength2 RS; given=4, đường cong ROC hệ tư vấn có độ dài tối đa luật từ đến trùng nằm đường cong hai hệ tư vấn cịn lại Ngồi ra, độ dài tối đa luật tăng số luật sinh tăng, từ làm tăng thời gian đưa gợi ý Do đó, trường hợp ngưỡng độ dài tối đa luật chọn Với tập liệu MSWeb(875x135), ta thực theo cách làm DKHP(1.130x57) Kết quả, với ngưỡng hỗ trợ tin cậy chọn trên, độ dài tối đa luật cho tập liệu MSWeb(875x135) 25 Số láng giềng gần mơ hình IBCF Trên tập liệu MSWeb(875x135), bảy hệ tư vấn xây dựng k20 IBCFRS, k40 IBCFRS, k60 IBCFRS, k80 IBCFRS, k100 IBCFRS, k120 IBCFRS k135 IBCFRS Các hệ thống sử dụng mơ hình IBCF dùng độ đo Jaccard có giá trị 𝑘 thay đổi 20, 40, 60, 80, 100, 120 135 tương ứng Tất hệ thống có: - Dãy số mục liệu (Vroot) cần gợi ý cho người dùng 𝑟𝑒𝑐𝑠: đến 12 - Số xếp hạng biết trước người dùng tập truy vấn 𝑔𝑖𝑣𝑒𝑛: đến Các hệ thống đánh giá 𝑡𝑖𝑚𝑒𝑠 lần lần đánh giá sử dụng phương pháp đánh giá chéo k tập Hình Phụ lục 6.5.a Hình Phụ lục 6.5.b hiển thị đường cong Precision - Recall đường cong ROC hệ tư vấn (times, given) (5, 4) (30, 2) tương ứng Các kết cho thấy: Đường cong ROC hệ tư vấn sử dụng k=135 nằm đường cong ROC hệ thống lại; đồng thời giá trị xác giá trị bao phủ hệ tư vấn số mục cần gợi ý 𝑟𝑒𝑐𝑠 cao so với hệ khác Số Vroot cần gợi ý cho người dùng (a): (times, given) = (5, 4) (b): (times, given) = (30, 2) Hình Phụ lục 6.5: Đường cong Precision - Recall ROC bẩy hệ tư vấn sử dụng mơ hình IBCF tập MSWeb(875x135) (times, given) (5, 4), (30, 2) 26 Hình Phụ lục 6.6.a hiển thị biểu đồ giá trị 𝐹1 bẩy hệ thống số mục cần gợi ý recs=10 số xếp hạng biết trước given=3 theo nhiều lần đánh giá times=5, 15, 30 Hình Phụ lục 6.6.b hiển thị biểu đồ giá trị 𝐹1 trung bình tất 𝑟𝑒𝑐𝑠 (từ đến 12) hệ thống số xếp hạng biết trước given=6 theo nhiều lần đánh giá times = 5, 15, 30 Các kết cho thấy giá trị điều hòa độ xác độ bao phủ (𝐹1) hệ tư vấn sử dụng k=135 cao giá trị 𝐹1 hệ thống lại Giá trị F1 recs=10, given=3 0.460 0.455 0.400 Giá trị F1 tất recs given=6 0.395 0.450 0.390 0.445 0.385 0.440 0.380 0.435 0.375 0.430 times=5 times=15 k135 IBCFRS k120 IBCFRS k100 IBCFRS k60 IBCFRS k40 IBCFRS k20 IBCFRS times=5 times=30 k80 IBCFRS times=15 k135 IBCFRS k120 IBCFRS k100 IBCFRS k60 IBCFRS k40 IBCFRS k20 IBCFRS times=30 k80 IBCFRS Hình Phụ lục 6.6: Biểu đồ giá trị F1 hệ tư vấn sử dụng mơ hình IBCF tập MSWeb(875x135) cho recs cụ thể (a) tất recs (b) theo nhiều lần đánh giá Khi thay đổi giá trị 𝑡𝑖𝑚𝑒𝑠 𝑔𝑖𝑣𝑒𝑛, ta nhận kết tương tự Cụ thể, hệ thống sử dụng k=135 có hiệu cao so với hệ thống so sánh Vậy, giá trị phù hợp tham số 𝑘 cho 𝑔𝑖𝑣𝑒𝑛 xét sử dụng tập liệu MSWeb(875x135) 135 Với tập DKHP(1.130x57), ta thực theo cách tương tự tập MSWeb(875x135) Kết quả, 57 giá trị phù hợp tham số 𝑘 cho 𝑔𝑖𝑣𝑒𝑛 xét ...