Luận văn Phương pháp lọc cộng tác và ứng dụng trong hệ thống gợi ý bán hàng trực tuyến

ép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. Học viên Đỗ Thị Thanh Hà ii LỜI CẢM ƠN Trước hết, tôi xin được tỏ lòng biết ơn và gửi lời cám ơn chân thành đến thầy PGS.TS Đoàn Văn Ban, người trực tiếp hướng dẫn luận văn, đã tận tình chỉ bảo và hướng dẫn tôi tìm ra hướng nghiên cứu, tiếp cận thực tế, tìm kiếm tài liệu, xử lý và phân tích số liệu, nhờ đó tôi mới có thể hoàn thành luận văn cao học của mình. Tôi xin chân thành cảm ơn quý thầy cô Khoa Công nghệ thông tin - trường Đại học Công nghệ Thông tin và Truyền thông, Đại học Thái Nguyên đã truyền đạt cho tôi những kiến thức bổ ích trong suốt hai năm học vừa qua. Xin chân thành cảm ơn các anh chị em lớp cao học Khoa học máy tính khoá 17 và các bạn đồng nghiệp luôn động viên, hỗ trợ tôi trong quá trình học tập và nghiên cứu và thực hiện đề tài. Cuối cùng, tôi xin gửi đến cha mẹ và những người thân trong gia đình đã hỗ trợ, tạo điều kiện thuận lợi cho tôi trong suốt thời gian qua và đặc biệt trong thời gian tôi theo học khóa thạc sỹ tại trường Đại học Công nghệ Thông tin và Truyền thông, Đại học Thái Nguyên. Xin chân thành cảm ơn! Người thực hiện Đỗ Thị Thanh Hà iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................................................ i LỜI CẢM ƠN ............................................................................................................................. ii MỤC LỤC .................................................................................................................................. iii DANH MỤC CÁC BẢNG ........................................................................................................ iv DANH MỤC HÌNH VẼ...............................................................................................................v MỘT SỐ THUẬT NGỮ .......................................................................................................... viii MỞ ĐẦU .....................................................................................................................................1 CHƯƠNG 1. HỆ THỐNG TƯ VẤN VÀ CÁC PHƯƠNG PHÁP LỌC THÔNG TIN ......5 1.1. Hệ tư vấn ...............................................................................................................................5 1.1.1. Giới thiệu hệ thống tư vấn .................................................................................................5 1.1.2. Bài toán tư vấn người dùng ...............................................................................................7 1.1.3. Qui trình xây dựng hệ tư vấn .............................................................................................9 1.2. Các phương pháp lọc tin .....................................................................................................10 1.2.1. Phân loại hệ thống tư vấn ................................................................................................10 1.2.2. Phương pháp tư vấn dựa trên nội dung ...........................................................................11 1.2.3. Phương pháp tư vấn dựa trên lọc cộng tác ......................................................................17 1.2.4. Tư vấn dựa trên cách tiếp cận kết hợp .............................................................................23 1.3. Kiến trúc tổng quát của hệ thống lọc thông tin ..................................................................25 1.4. Ứng dụng của phương pháp lọc tin trong hệ thống tư vấn ................................................26 1.5. Kết luận chương 1 ...............................................................................................................28 CHƯƠNG 2.PHƯƠNG PHÁP THUẬT LỌC CỘNG TÁC DỰA TRÊN SẢN PHẨM ..29 2.1. Các phương pháp lọc cộng tác ............................................................................................29 2.1.1. Giới thiệu về các phương pháp lọc cộng tác ...................................................................29 2.1.2. Ưu và nhược điểm của phương pháp lọc cộng tác ..........................................................30 2.2. Lọc cộng tác dựa trên sản phẩm .........................................................................................32 2.3. Các thuật toán tính độ tương tự ..........................................................................................34 iv 2.4. Tính toán dự đoán và tư vấn ...............................................................................................37 2.4.1. Dự đoán dựa trên trung bình đánh giá sản phẩm lân cận ................................................37 2.4.2. Dự đoán dựa trên tổng trọng số (Weighted Sum) ...........................................................38 2.4.3. Dự đoán dựa trên tổng trọng số với đánh giá trung bình của người dùng ................................38 2.4.4. Dự đoán dựa trên tổng trọng số với trung bình đánh giá lên sản phẩm .................................39 2.5. Đánh giá các yếu tố ảnh hưởng đến độ chính xác kết quả tư vấn ......................................40 2.5.1. Đánh giá độ tin cậy của thuật toán ..................................................................................40 2.5.2. Các yếu tố ảnh hưởng đến độ chính xác tư vấn ..............................................................42 2.6. Kết luận chương 2 ...............................................................................................................44 CHƯƠNG 3. ỨNG DỤNG PHƯƠNG PHÁP LỌC CỘNG TÁC DỰA TRÊN SẢN PHẨM TRONG HỆ THỐNG GỢI Ý BÁN HÀNG TRỰC TUYẾN .................................................45 3.1. Xây dựng hệ thống gợi ý cho website bán hàng trực tuyến ...............................................45 3.1.1. Đặc tả hệ thống ................................................................................................................45 3.1.2. Môi trường phát triển .......................................................................................................46 3.1.3. Thiết kế bảng dữ liệu .......................................................................................................46 3.2. Ví dụ về lọc cộng tác dựa trên sản phẩm ............................................................................49 3.3. Thuật toán xử lý chính trong hệ thống ...............................................................................53 3.3.1. Thuật toán khách hàng đánh giá sản phẩm ......................................................................53 3.3.2. Thuật toán khách hàng chấm điểm sản phẩm .................................................................54 3.3.3. Thuật toán gợi ý sản phẩm cho khách hàng ....................................................................55 3.4. Các giao diện chính của hệ thống .......................................................................................56 3.5. Kết luận chương 3 ...............................................................................................................60 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................................61 TÀI LIỆU THAM KHẢO .......................................................................................................62 ivv DANH MỤC BẢNG BIỂU Bảng 1: Bảng đánh giá người dùng với các sản phẩm .............................................. 33 Bảng 2: Dữ liệu đánh giá các sản phẩm .................................................................... 49 Bảng 3: Ma trận utility matrix ................................................................................... 50 Bảng 4: Giá trị trung bình đánh giá của các item ...................................................... 50 Bảng 5: Ma trận chuẩn hóa Ŷ51 Bảng 6: Độ tương tự giữa các item S ........................................................................ 51 Bảng 7: Ma trận sau khi được dự đoán ŷ .................................................................. 52 Bảng 8: Ma trận dự đoán thang điểm 5 ..................................................................... 53 v vi DANH MỤC HÌNH VẼ Hình 1.1: Một số lĩnh vực ứng dụng của hệ thống gợi ý ............................................ 6 Hình 1.2. Ví dụ ma trận đánh giá tổng quát ................................................................ 8 Hình 1.3: Phân loại hướng tiếp cận xây dựng hệ thống gợi ý ................................... 11 Hình 1.4. Minh họa phương pháp tư vấn dựa trên lọc nội dung ............................... 12 Hình 1.5: Minh họa phương pháp tư vấn dựa trên lọc cộng tác ............................... 18 Hình 1.6: Quy trình của hệ thống tư vấn dựa trên lọc cộng tác ................................ 19 Hình 1.7: Kiến trúc tổng quát của hệ thống lọc thông tin ......................................... 25 Hình 1.8: Hệ thống gợi ý sản phẩm của Amazon ..................................................... 28 Hình 2.1: Tách các sản phẩm cùng được đánh giá và tính toán độ tương tự ............ 34 Hình 2.2: Giải thuật lọc cộng tác dựa trên sản phẩm, tính dự đoán .......................... 37 Hình 2.3: Mô hình hệ thống lọc cộng tác dựa trên sản phẩm ................................... 40 Hình 3.1: Giải thuật khách hàng đánh giá sản phẩm ................................................ 54 Hình 3.2: Khách hàng chấm điểm sản phẩm ............................................................ 55 Hình 3.3: Giải thuật xử lý gợi ý sản phẩm ................................................................ 56 Hình 3.4: Giao diện trang chủ ................................................................................... 58 Hình 3.5: Giao diện trang danh sách sản phẩm ......................................................... 58 Hình 3.6: Giao diện gợi ý sản phẩm cho sản phẩm chưa có đánh giá ...................... 59 Hình 3.7: Giao diện gợi ý sản phẩm cho sản phẩm đã có đánh giá .......................... 59 Hình 3.8: Giao diện gợi ý sản phẩm cho một thành viên cụ thể ............................... 59 vivii MỘT SỐ THUẬT NGỮ STT Tiếng Anh Tiếng Việt Giải thích Chỉ những người dùng hệ thống để tìm 1 User Người dùng, người sử dụng kiếm lựa chọn sản phẩm Chỉ những sản phẩm trên hệ thống như: 2 Item Sản phẩm, mục sản phẩm, phim, ảnh, bản nhạc, trang web, đoạn văn bản, Chỉ mức độ thích của một người dùng với sản phẩm. Rating có thể có nhiều biểu 3 Rating Đánh giá hiện: như đánh giá thích hoặc không thích, hay đánh già theo mức độ từ 1-5 đại diện từ không thích đến rất thích. CF có tên là Neighborhood-based Collaborative Filtering (NBCF). Khi chỉ 4 CF Lọc cộng tác nói CF, chúng ta sẽ ngầm hiểu rằng phương pháp được sử dụng là Neighborhood-based. MỞ ĐẦU  Lí do chọn đề tài Sự phát triển mạnh mẽ của thương mại điện tử (E-Commerce) là một trong những tác nhân chính đem lại nhiều lợi ích to lớn cho nền kinh tế toàn cầu. Nhờ có thương mại điện tử, rất nhiều loại hình kinh doanh mới được hình thành, trong đó có mua bán hàng trực tuyến. Với hình thức mới này, người tiêu dùng có thể tiếp cận với hàng hóa một cách dễ dàng và nhanh chóng hơn rất nhiều so với phương thức mua bán truyền thống. Hiện nay, với phương châm phục vụ khách hàng một cách tốt nhất, các hệ thống bán hàng trực tuyến luôn tạo nhiều điều kiện thuận lợi để người mua hàng có thể tiếp cận nhiều mặt hàng cùng lúc. Tuy nhiên, việc trình bày và trang trí quá nhiều các mặt hàng trên một website sẽ gây ra không ít khó khăn cho người mua. Họ khó có thể chọn ra cho mình một sản phẩm ưng ý nhất. Trong kinh doanh, để khách hàng có thể đến và mua được một sản phẩm ưng ý thì một lời tư vấn, một sự trợ giúp là rất quan trọng. Với phương thức bán hàng truyền thống những lời tư vấn như thế từ một người bán hàng sẽ tạo ra một lợi thế rất lớn cho cửa hàng. Do đó, để phương thức bán hàng qua mạng phát triển thực sự hiệu quả thì bên cạnh các lợi thế vốn có của mình, việc có thêm một “người trợ giúp” là hết sức cần thiết. Vì vậy, cần thiết phải sử dụng một hệ thống gợi ý (Recommender Systems - RS) đóng vai trò như một người hỗ trợ khách hàng đưa ra các quyết định mua hàng đúng đắn. Bằng cách xác định mục đích và nhu cầu của khách hàng, hệ thống có thể đưa ra tập các gợi ý giúp cho người mua dễ dàng chọn lựa sản phẩm yêu thích hơn. Qua đó hiệu suất của việc mua bán hàng trực tuyến được tăng cao một cách đáng kể [6]. Hệ thống gợi ý được phát triển theo nhiều cách tiếp cận khác nhau. Một trong những hướng tiếp cận được tập trung nghiên cứu và được áp dụng khá 2 thành công trong nhiều hệ gợi ý đó là phương pháp lọc cộng tác (Collaborative filtering). Thực chất, lọc cộng tác là một hình thức tư vấn tự động bằng cách dựa trên sự tương tự giữa những người dùng hoặc giữa những sản phẩm trong hệ thống và đưa ra dự đoán sự quan tâm của người dùng tới những sản phẩm, hoặc đưa ra gợi ý một sản phẩm mới cho người dùng. Việc xây dựng hệ thống gợi ý cũng là vấn đề được nhiều nhà khoa học trong nước quan tâm [4, 7]. Trong hệ thống gợi ý, lọc cộng tác là một kỹ thuật được dùng để đánh giá độ quan tâm của người dùng trên các sản phẩm mới (từ mức độ tìm hiểu thuật toán [2] cho đến việc cải tiến [5] cũng như áp dụng trong việc xây dựng website bán hàng trực tuyến [6]). Kỹ thuật này được áp dụng thành công trong nhiều ứng dụng. Trong các hệ thống lọc cộng tác, sở thích của người dùng trên các sản phẩm mới được dự đoán dựa trên dữ liệu về sở thích của người dùng – sản phẩm (hoặc đánh giá của người dùng trên sản phẩm) trong quá khứ. Các nghiên cứu trong và ngoài nước đã góp phần rất lớn cho việc xây dựng những website bán hàng trực tuyến như website mua sắm trực tuyến Amazon (www.amazon.com) cung cấp cho khách hàng những sản phẩm mà họ có thể quan tâm, cổng video clip YouTube (www.youtube.com), gợi ý phim của MovieLens (www.movielens.org) [10]. Tuy nhiên, để phát triển mạnh hơn nữa thuật toán lọc cộng tác trong hệ thống gợi ý nói chung hay hệ thống gợi ý sản phẩm nói riêng còn rất nhiều câu hỏi cần lời giải đáp. Cụ thể như: Khi xây dựng hệ thống gợi ý bán hàng trực tuyến, tiếp cận theo hướng dựa trên bộ nhớ (Memory-based) hay dựa trên mô hình (Model- based) hiệu quả hơn? Trong hướng tiếp cận theo Memory-based thì nên tư vấn dựa trên người dùng (User based) hay sản phẩm (Items based)? Nếu tiếp cận theo hướng Model-based thì nên sử dụng mô hình mạng Nơ ron hay Mạng Bayessian? Trong mỗi cách tiếp cận, sử dụng độ đo nào để nắm bắt chính xác việc khách 3 hàng cho rằng sản phẩm tốt? Làm thế nào để dự báo tốt và gợi ý tốt trong đồng thời, [1, 10]. Với những lý do trên, tác giả đã chọn đề tài “Phương pháp lọc cộng tác và ứng dụng trong hệ thống gợi ý bán hàng trực tuyến” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành Khoa học máy tính.  Mục tiêu nghiên cứu Nghiên cứu ứng dụng các phương pháp lọc cộng tác trong bài toán xây dựng hệ thống tư vấn. Tập trung vào phân tích, so sánh, đánh giá hiệu quả của phương pháp lọc cộng tác dựa trên người dùng và lọc cộng tác dựa trên sản phẩm ứng dụng trong bài toán xây dựng hệ thống gợi ý bán hàng trực tuyến.  Đối tượng và phạm vi nghiên cứu Đối tượng: Phương pháp lọc cộng tác, hệ thống gợi ý bán hàng trực tuyến Phạm vi nghiên cứu: Khảo sát và đánh giá thuật hiệu quả của thuật toán lọc cộng tác dựa trên người dùng và thuật toán lọc cộng tác dựa trên sản phẩm đối với hệ thống gợi ý bán hàng trực tuyến. Quá trình đánh giá được thực hiện trên một số bộ mẫu dữ liệu chuẩn có sẵn trong [15].  Phương pháp nghiên cứu - Đọc tài liệu, phân tích, tổng hợp. - Thu thập dữ liệu, thống kê, phân tích dữ liệu. - Mô phỏng và đánh giá kết quả. - Kết hợp nghiên cứu lý thuyết, tìm hiểu tình hình ứng dụng, đánh giá khả năng ứng dụng và đề xuất giải pháp.  Ý nghĩa khoa học và thực tiễn của đề tài Nghiên cứu các phương pháp lọc cộng tác. Chứng minh khả năng ứng dụng của lọc cộng tác cho bài toán xây dựng hệ thống gợi ý sản phẩm trong bán hàng trực tuyến. Khuyến nghị phương pháp tiếp cận hiệu quả nhất trong các phương pháp lọc cộng tác. 4 Đề tài nghiên cứu các bước trong quá trình tư vấn, các giải pháp khắc phục các yếu tố ảnh hưởng đến chất lượng, nhằm cải thiện kết quả tư vấn sản phẩm phù hợp với yêu cầu thực tế của người dùng. Với mục tiêu trên, luận văn được trình bày trong ba chương Chương 1: Hệ thống tư vấn và phương pháp lọc thông tin Chương này giới thiệu bài toán tư vấn và hệ thống gợi ý, phân tích các ứng dụng của hệ thống gợi ý trong thực tế. Các phương pháp lọc tin và ứng dụng trong hệ thống gợi ý. Chương 2: Phương pháp thuật lọc cộng tác dựa trên sản phẩm Chương này trình bày phương pháp lọc cộng dựa vào người dùng, lọc cộng tác dựa trên sản phẩm, phương pháp lọc cộng tác dựa trên mô hình và khả năng ứng dụng trong bài toán xây dựng hệ thống gợi ý Chương 3: Ứng dụng phương pháp lọc cộng tác dựa trên sản phẩm trong hệ thống gợi ý bán hàng trực tuyến. Chương này cài đặt thử nghiệm phương pháp lọc cộng tác trên sản phẩm cho website bán hàng thời trang 5 CHƯƠNG 1. HỆ THỐNG TƯ VẤN VÀ CÁC PHƯƠNG PHÁP LỌC THÔNG TIN 1.1. Hệ tư vấn 1.1.1. Giới thiệu hệ thống tư vấn Hệ thống tư vấn (Recommender Systems – RS) [8] phân tích thông tin về sở thích của người dùng (user) về các sản phẩm (item) để cung cấp các khuyến nghị đối với các item phù hợp nhất với mong muốn và sở thích của người dùng. Trên thực tế, hệ thống gợi ý cố gắng thu thập những sở thích của người dùng và mô hình hóa sự tương tác giữa người dùng và sản phẩm. Hệ thống gợi ý sử dụng các thông tin về sản phẩm và các tri thức của chuyên gia hay tri thức khai phá dữ liệu được học từ hành vi của người dùng để đưa ra những gợi ý về sản phẩm mà họ thích trong hàng ngàn hàng vạn sản phẩm có trong hệ thống. Các website thương mại điện tử ví dụ như: sách, phim, nhạc, báo,... sử dụng hệ thống gợi ý để cung cấp các thông tin giúp cho người dùng quyết định sẽ lựa chọn sản phẩm nào. Các sản phẩm được gợi ý dựa trên số lượng sản phẩm đó đã được bán, dựa trên các thông tin cá nhân của người dùng, dựa trên sự phân tích hành vi mua hàng trước đó của người dùng để đưa ra các dự đoán về hành vi mua hàng trong tương lai của chính khách hàng đó. Các dạng gợi ý bao gồm: gợi ý các sản phẩm tới người tiêu dùng, các thông tin sản phẩm mang tính cá nhân hóa, tổng kết các ý kiến cộng đồng, và cung cấp các chia sẻ, các phê bình, đánh giá mang tính cộng đồng liên quan tới yêu cầu, mục đích của người dùng đó [10, 13, 16]. Rất nhiều hệ thống lớn thu thập thông tin phản hồi từ khách hàng một cách tường minh, như Ebay, Amazon, LastFM, NetFlix, Youtube,... ở đó người dùng sẽ trực tiếp đánh giá trên sản phẩm, như bình chọn từ ★ (không thích) đến ★ 6 ★★★ (rất thích); hay Youtube thu thập thông tin qua like/disklike, và các hệ thống khác [10, 13, 16]. Thông qua việc thu thập phản hồi tường minh, hệ thống dễ dàng xác định mức độ yêu thích của người dùng trên sản phẩm, từ đó dự đoán các sản phẩm tiếp theo mà người dùng có thể thích để gợi ý cho họ. Tuy nhiên, điều này có thể gây bất lợi do không phải người dùng lúc nào cũng sẵn sàng/vui lòng để lại các phản hồi của họ, vì vậy hệ thống phải nên tự xác định người dùng cần gì thông qua phản hồi tiềm ẩn. Một số ứng dụng hệ tư vấn nổi tiếng trên thế giới được giới thiệu trong Hình 1.1 [14]. Hình 1.1: Một số lĩnh vực ứng dụng của hệ thống gợi ý Trong kỹ thuật lọc cộng tác CF (Collaborative Filtering), việc đưa ra những khuyến nghị về các sản phẩm đối với người dùng được xác định dựa trên những quan điểm của những người dùng có cùng sở thích với người dùng đó. Hệ thống lọc cộng tác biểu diễn người dùng dựa trên những đánh giá của họ 7 đối với tập các sản phẩm. Hệ thống sẽ lựa chọn những người dùng cùng sở thích tùy thuộc vào độ đo tương tự hoặc tương quan. Sau đó, đưa ra những dự đoán đối với những sản phẩm chưa từng được người dùng đánh giá hoặc quan tâm. Cuối cùng hệ thống sẽ gợi ý những sản phẩm nào với mức độ dự đoán cao nhất cho người dùng mục tiêu. Kỹ thuật CF đã được khẳng định sự thành công bởi rất nhiều nghiên cứu và thực nghiệm trong nhiều ứng dụng thực tế [8, 11, 12]. Hệ thống gợi ý là một dạng của hệ hỗ trợ ra quyết định, cung cấp giải pháp mang tính cá nhân hóa mà không phải trải qua quá trình tìm kiếm phức tạp. Hệ gợi ý học từ người dùng và gợi ý các sản phẩm tốt nhất trong số các sản phẩm phù hợp. 1.1.2. Bài toán tư vấn người dùng Cho tập hợp hữu hạn gồm 푁 người dùng 푈 = {푢1, 푢1, , 푢푁} và 푀 sản phẩm 푃 = {푝1, 푝2, , 푝푀}. Mỗi người dùng 푢푖 ∈ 푈 (với 푖 = 1, 2, , 푁) được biểu diễn thông qua |푇| đặc trưng nội dung 푇 = {푡1, 푡2, , 푡|푇|}. Các đặc trưng 푡푞 ∈ 푇 thông thường là thông tin cá nhân của mỗi người dùng. Ví dụ 푢푖 ∈ 푈 là một người dùng thì các đặc trưng nội dung biểu diễn người dùng 푢푖 có thể là T={giới tính, độ tuổi, nghề nghiệp, trình độ,}. Mỗi sản phẩm 푝푥 ∈ 푃 (với 푥 = 1, 2, 푀) có thể là hàng hóa, phim, ảnh, tạp chí, tài liệu, sách, báo, dịch vụ hoặc bất kỳ dạng thông tin nào mà người dùng cần đến. Mỗi sản phẩm 푝푥 ∈ 푃 được biểu diễn thông qua |퐶| đặc trưng nội dung 퐶 = { 푐1, 푐2, , 푐|퐶|}. Các đặc trưng 푐푠 ∈ 퐶 nhận được từ các phương pháp trích chọn đặc trưng trong lĩnh vực truy vấn thông tin. Ví dụ 푝푥 ∈ 푃 là một phim thì các đặc trưng nội dung biểu diễn phim 푝푥 có thể là 퐶 = {thể loại phim, nước sản xuất, hãng phim, diễn viên, đạo diễn, }. Mối quan hệ giữa tập người dùng 푈 và tập sản phẩm 푃 được biểu diễn thông qua ma trận đánh giá 푅 = [푟푖푥] với 푖 = 1, 2, , 푁; 푥 = 1, 2, , 푀 (Hình 1.2). 8 Sản phẩm 1 2 i 푀 1 5 3 0 1 2 0 2 0 2 0 0 0 4 0 0 5 0 0 0 u 3 4 0 2 1 0 Người dùng 0 0 0 0 4 0 N 0 0 3 2 0 0 푎 3 5 0 ? 1 0 Hình 1.2. Ví dụ ma trận đánh giá tổng quát Giá trị 푟푖푥 thể hiện đánh giá của người dùng 푢푖 ∈ 푈 cho một số sản phẩm 푝푥 ∈ 푃. Thông thường giá trị 푟푖푥 nhận một giá trị thuộc miền 퐹 = { 1, 2, , 푔} được thu thập trực tiếp bằng cách hỏi ý kiến người dùng hoặc thu thập gián tiếp thông qua cơ chế phản hồi của người dùng. Những giá trị 푟푖푥 = 0 được hiểu là người dùng 푢푖 ∈ 푈 chưa biết đến hoặc không đánh giá sản phẩm 푝푥 ∈ 푃, những ô điền ký tự “?” là giá trị cần hệ tư vấn đưa ra dự đoán đánh giá. Tiếp đến, ta ký hiệu 푃푖  푃 là tập các sản phẩm 푝푥 ∈ 푃 được đánh giá bởi người dùng 푢푖 ∈ 푈 và 푢푎 ∈ 푈 được gọi là người dùng hiện thời, người dùng cần được tư vấn hay người dùng tích cực. Khi đó, tồn tại hai dạng bài toán điển hình của hệ tư vấn là: - Dự đoán đánh giá của người dùng 푢푎 với các sản phẩm chưa có đánh giá trước đó. - Tư vấn danh sách ngắn các sản phẩm phù hợp với người dùng hiện thời. Cụ thể đối với người dùng 푢푎, hệ tư vấn sẽ chọn ra 퐾 sản phẩm mới 푝푥 ∈ (푃\푃푎) phù hợp với người dùng 푢푎 nhất để gợi ý cho họ. 9 Việc giải quyết bài toán tư vấn sẽ được thực hiện theo qui trình xây dựng hệ tư vấn trong mục 1.1.3. 1.1.3. Qui trình xây dựng hệ tư vấn Qui trình tổng quát để giải quyết bài toán tư vấn [14] thông thường gồm có 3 giai đoạn chính được thể hiện như sau: Giai đoạn 1: Thu thập thông tin Ba loại thông tin chính thường được thu thập cho hệ tư vấn, gồm có: - Người dùng (User) biểu diễn thông qua các đặc trưng là thông tin cá nhân. Thông qua biểu diễn này, hệ thống cho phép xây dựng hồ sơ người dùng (user’s profile) nhằm lưu trữ lại dấu vết các đặc trưng nội dung sản phẩm đã từng được sử dụng bởi người dùng. - Sản phẩm (Item) biểu diễn thông qua các đặc trưng là thông tin về sản phẩm. Thông qua biểu diễn này, hệ thống cho phép xây dựng hồ sơ sản phẩm (item’s profile) nhằm lưu trữ lại dấu vết các đặc trưng người dùng đã từng sử dụng sản phẩm. - Phản hồi của người dùng với sản phẩm (Feedback), biểu diễn thông qua các giá trị đánh giá của người dùng với sản phẩm. Giai đoạn 2: Xây dựng mô hình Giai đoạn xây dựng mô hình tư vấn có thể thực hiện bằng nhiều hướng tiếp cận khác nhau nhằm so sánh, đánh giá mối liên hệ giữa các thông tin thu thập được ở giai đoạn 1. Một số hướng tiếp cận điển hình được biết đến như: dựa vào kinh nghiệm, học máy, lý thuyết xấp xỉ,...[1]. Mỗi hướng tiếp cận sẽ khai thác thông tin đầu vào theo những cách khác nhau hình thành những phương pháp tư vấn khác nhau. Giai đoạn 3: Dự đoán đánh giá / Đưa ra tư vấn Dữ liệu đầu ra của giai đoạn 2 sẽ được dùng để dự đoán các đánh giá của người dùng với các sản phẩm chưa có đánh giá trước đó và chọn ra 퐾 sản phẩm mới phù hợp nhất đối với người dùng hiện thời để gợi ý cho họ. 10 1.2. Các phương pháp lọc tin 1.2.1. Phân loại hệ thống tư vấn Lọc thông tin là lĩnh vực nghiên cứu các quá trình phân bổ thông tin thích hợp và gỡ bỏ thông tin không thích hợp đến với mỗi người dùng. Lọc thông tin cho các hệ tư vấn được tiếp cận theo hai xu hướng chính, đó là lọc dựa vào nội dung sản phẩm và lọc dựa vào thói quen sử dụng sản phẩm của người hay còn được gọi là lọc cộng tác. So với lọc theo nội dung, lọc cộng tác cho lại kết quả tốt hơn và có thể lọc bất kỳ dạng thông tin nào. Tuy nhiên, lọc cộng tác gặp phải vấn đề dữ liệu thưa, người dùng mới và sản phẩm mới cần được tiếp tục nghiên cứu giải quyết. Kết hợp giữa lọc cộng tác và lọc nội dung để nâng cao chất lượng dự đoán và tránh hiện trạng dữ liệu thưa của lọc cộng tác được tập trung nghiên cứu nhiều trong thời gian gần đây. Các phương pháp lọc kết hợp hiện nay vẫn hạn chế trong biểu diễn và ước lương mức độ ảnh hưởng của mỗi đặc trưng nội dung đến thói quen sử dụng sản phẩm của người dùng [2, 5, 10, 12, 14]. Có rất nhiều cách để dự đoán, ước lượng hạng/điểm cho các sản phẩm như sử dụng học máy, lý thuyết xấp xỉ, các thuật toán dựa trên kinh nghiệm, Theo [8], các hệ thống gợi ý thường được phân thành ba loại theo các phương pháp lọc tin (xem Hình 1.3): Tư vấn dựa trên nội dung, tư vấn dựa trên cộng tác, tư vấn dựa trên cách tiếp cận kết hợp. Tư vấn dựa trên nội dung: Cách tiếp cận lọc nội dung tạo ra một hồ sơ cho mỗi người dùng hoặc sản phẩm để mô tả bản chất của nó. Ví dụ, một hồ sơ phim có thể bao gồm các thuộc tính liên quan đến thể loại của nó, các diễn viên tham gia, sự phổ biến của phòng vé, v.v. Hồ sơ người dùng có thể bao gồm thông tin nhân khẩu học hoặc câu trả lời được cung cấp trên bảng câu hỏi phù hợp. Các hồ sơ cho phép các chương trình liên kết người dùng với các sản phẩm phù hợp. Tất nhiên, chiến lược dựa trên nội dung yêu cầu thu thập thông tin bên ngoài có thể không có sẵn hoặc khó thu thập. 11 Tư vấn dựa trên cộng tác: Cách này chỉ dựa trên hành vi của người dùng trước đây. Ví dụ: Giao dịch trước đó hoặc xếp hạng sản phẩm, mà không yêu cầu tạo hồ sơ rõ ràng. Chiến thuật này phân tích mối liên quan giữa người dùng và các thuộc tính của sản phẩm để định nghĩa quan hệ giữa người dùng – sản phẩm. Ưu điểm của lọc cộng tác so với lọc nội dung là không bị giới hạn miền, dẫn đến có thể giải quyết các khía cạnh dữ liệu thường khó nắm bắt và khó khăn để đưa vào khi sử dụng lọc nội dung. Tuy nhiên không hiệu quả khi phải xử lý với dữ liệu mới được thêm vào, điều mà lọc nội dung lại hiệu quả hơn. Tư vấn dựa trên cách tiếp cận kết hợp: Kết hợp hai phương pháp tiếp cận dựa trên nội dung và cộng tác. Hình 1.3: Phân loại hướng tiếp cận xây dựng hệ thống gợi ý 1.2.2. Phương pháp tư vấn dựa trên nội dung Lọc theo nội dung là phương pháp thực hiện dựa trên việc so sánh nội dung thông tin hay mô tả hàng hóa, để tìm ra những sản phẩm tương tự với 12 những gì mà người dùng đã từng quan tâm để giới thiệu cho họ những sản phẩm này. Các phương pháp tiếp cận cho lọc theo nội dung được chia thành hai phương pháp chính: lọc nội dung dựa vào bộ nhớ và lọc nội dung dựa vào mô hình. Những vấn đề cần tiếp tục nghiên cứu của lọc nội dung là vấn đề trích chọn đặc trưng và người dùng mới [1, 8, 12]. Với phương pháp tư vấn dựa trên nội dung, độ phù hợp r(u, i) của sản phẩm i với người dùng u được đánh giá dựa trên độ phù hợp r(u, i’) trong đó và “tương tự” như i. Ví dụ, để gợi ý một bộ phim cho người dùng u, hệ thống gợi ý sẽ tìm các đặc điểm của những bộ phim từng được u đánh giá cao như diễn viên, đạo diễn, sau đó chỉ những bộ phim tương tự với sở thích của u mới được giới thiệu. Hướng tiếp cận dựa trên nội dung bắt nguồn từ những nghiên cứu về thu thập thông tin và lọc thông tin. Do đó, rất nhiều hệ thống dựa trên nội dung hiện nay tập trung vào tư vấn các đối tượng chứa dữ liệu văn bản như tin tức, website. Những tiến bộ so với hướng tiếp cận cũ của phương pháp tìm kiếm thông tin là do có sử dụng hồ sơ về người dùng (chứa thông tin về sở thích, nhu cầu,...). Hồ sơ này được xây dựng dựa trên những thông tin được người dùng cung cấp trực tiếp (khi trả lời khảo sát) hoặc gián tiếp (do khai phá thông tin từ các giao dịch của người dùng). Hình 1.4. Minh họa phương pháp tư vấn dựa trên lọc nội dung Giả sử ta xem Content(i) là một thông tin riêng của sản phẩm, nghĩa là một tập các đặc tính đặc trưng cho sản phẩm i. Nó thường được tính toán thông qua việc trích rút từ tập các đặc tính của sản phẩm i (nội dung của nó) và ứng 13 với mỗi mục đích tư vấn sẽ xác định ra sản phẩm thích hợp. Dễ dàng nhận thấy những hệ thống gợi ý dựa trên nội dung thường thiết kế cho hầu hết những sản phẩm được tư vấn dựa trên text (văn bản) và nội dung của những hệ thống này được mô tả như là một từ khóa (keyword). Một trong những thước đo phổ biến để xác định mức độ quan trọng của từ khóa trong việc truy vấn thông tin là đo tần suất xuất hiện của mục từ trong tài liệu (Term Frequency) và tần số nghịch đảo của tần suất xuất hiện các tài liệu (Inverse Document Fr...đơn giản và một lượng dữ liệu sẵn có từ người dùng trên các website này. Một số hạn chế: - Không thể gợi ý nếu khách hàng chưa có dữ liệu về lịch sử tương tác mặt hàng. - Khi lượng sản phẩm lớn và số lượng khách hàng đánh giá không nhiều thì phương pháp này không hiệu quả. - Phương pháp này cũng không thể gợi ý được các sản phẩm mới hoặc những sản phẩm chưa được ai đánh giá. 31 - Phương pháp này sẽ cho độ chính xác kém nếu như sở thích của người dùng thay đổi. Một số hạn chế của User-user CF: - Trên thực tế, số lượng users luôn lớn hơn số lượng items rất nhiều. Kéo theo đó là Similarity matrix là rất lớn với số phần tử phải lưu giữ là hơn 1 nửa của bình phương số lượng users (chú ý rằng ma trận này là đối xứng). Việc này, như đã đề cập ở trên, khiến cho việc lưu trữ ma trận này trong nhiều trường hợp là không khả thi. - Ma trận Utility Y thường là rất sparse. Với số lượng users rất lớn so với số lượng items, rất nhiều cột của ma trận này sẽ rất sparse, tức chỉ có một vài phần tử khác 0. Lý do là users thường lười rating. Cũng chính vì việc này, một khi user đó thay đổi rating hoặc rate thêm items, trung bình cộng các ratings cũng như vector chuẩn hoá tương ứng với user này thay đổi nhiều. Kéo theo đó, việc tính toán ma trận Similarity, vốn tốn nhiều bộ nhớ và thời gian, cũng cần được thực hiện lại. Ngược lại, nếu chúng ta tính toán similarity giữa các items rồi recommend những items gần giống với item yêu thích của một user thì sẽ có những lợi ích sau: - Vì số lượng items thường nhỏ hơn số lượng users, Similarity matrix trong trường hợp này cũng nhỏ hơn nhiều, thuận lợi cho việc lưu trữ và tính toán ở các bước sau. - Vì số lượng phần tử đã biết trong Utility matrix là như nhau nhưng số hàng (items) ít hơn số cột (users), nên trung bình, mỗi hàng của ma trận này sẽ có nhiều phần tử đã biết hơn số phần tử đã biết trong mỗi cột. Việc này cũng dễ hiểu vì mỗi item có thể được rated bởi nhiều users. Kéo theo đó, giá trị trung bình của mỗi hàng ít bị thay đổi hơn khi có thêm một vài ratings. Như vậy, việc cập nhật ma trận Similarity Matrix có thể được thực hiện ít thường xuyên hơn. Cách tiếp cận thứ hai này được gọi là Item-item Collaborative Filtering. Hướng tiếp cận này được sử dụng nhiều trong thực tế hơn. 32 2.2. Lọc cộng tác dựa trên sản phẩm Lọc cộng tác khai thác những khía cạnh liên quan đến thói quen sở thích của người dùng sản phẩm để đưa ra dự đoán các sản phẩm mới cho người dùng này. So với lọc theo nội dung, lọc cộng tác không phải phân tích, bóc tách, hiểu, đánh chỉ mục cho các đặc trưng nội dung sản phẩm. Chính vì vậy, lọc cộng tác có thể lọc hiệu quả trên nhiều dạng sản phẩm khác nhau như hàng hóa, sữa, ảnh, tài liệu. Cùng trên một hệ tư vấn, người dùng sẽ được tư vấn nhiều loại mặt hàng khác nhau cho dù các mặt hàng này có thể biểu diễn trên không gian các đặc trưng nội dung khác nhau Ý tưởng của phương pháp này được thực hiện bằng việc thay vì tính mức độ tương tự giữa users trong hệ thống với người dùng hiện thời 푢푎, hệ tư vấn sẽ tính toán mức độ tương tự giữa sản phẩm cần dự đoán đánh giá bởi 푢푎 với các sản phẩm đã được 푢푎 đánh giá. Việc tính toán mức độ tương tự giữa hai sản phẩm được xem xét dựa vào tập người dùng cùng đánh giá cả hai sản phẩm đó. Trên cơ sở đó chọn ra một tập sản phẩm láng giềng với sản phẩm cần dự đoán đánh giá bởi 푢푎. Kết hợp các đánh giá của 푢푎 với tập sản phẩm láng giềng này để đưa ra dự đoán đánh giá của 푢푎 với sản phẩm cần dự đoán [9, 12]. Bài toán lọc cộng tác: Cho danh sách người m người dùng U = {푢1, 푢2, , 푢푚} và một danh sách n sản phẩm I = {푖1, 푖2,, 푖푛}. 푟푢푖 là đánh giá sản phẩm i của người dùng u. r nhận giá trị từ 0 đến 5. Với r = 0 khi sản phẩm i chưa được đánh giá bởi người dùng u. Mỗi người dùng u có danh sách các sản phẩm 퐼푢, mà người dùng đã đánh giá về những sản phẩm đó. Yêu cầu: - Dự đoán giá trị số 푃푢,푖 dự đoán khả năng sản phẩm i 퐼푢 cho người dùng u. - Tư vấn danh sách 퐼푝 gồm N sản phẩm mà người dùng u thích nhất (퐼푝 ∩ 퐼푢 = Ø). 33 Cho một ví dụ có 9 người dùng đánh giá 9 sản phẩm, với mức độ từ 1 đến 5, nếu người dùng không đánh giá sản phẩm thì giá trị là 0. Bảng 1: Bảng đánh giá người dùng với các sản phẩm User Item i1 i2 i3 i4 i5 i6 i7 i8 i9 u1 1 2 1 5 0 0 0 0 0 u2 2 1 3 0 0 1 0 0 0 u3 2 3 0 2 3 1 0 0 4 u4 5 0 2 0 1 0 0 0 2 u5 0 0 3 5 0 3 4 0 0 u6 0 1 1 0 3 5 4 1 0 u7 0 0 0 0 3 4 2 1 0 u8 0 0 0 0 0 5 1 2 2 u9 0 0 0 1 0 0 0 2 4 Các bước trong quá trình tư vấn theo phương pháp lọc cộng tác dựa trên sản phẩm: Bước 1: Tiền xử lý dữ liệu: Dữ liệu được thu thập là những đánh giá sản phẩm của người dùng. Dữ liệu thu thập thường rất lớn tuy nhiên một số đánh giá có thể không có ích trong quá trình tư vấn theo phương pháp lọc cộng tác. Đề xuất được đưa ra để tối ưu dữ liệu đầu vào: một số sản phẩm hoặc người dùng sẽ được loại bỏ nếu người dùng đó đánh giá quá ít sản phẩm, hoặc sản phẩm được quá ít đánh giá. Bước 2: Xây dựng Ma trận đánh giá: Hàng là users, Cột là các items. Bước 3: Tính độ tương tự của 2 item: xây dựng ma trận tương tự của các sản phẩm. Bước 4: Tính dự đoán của người dùng đối với sản phẩm dựa trên những sản phẩm lân cận với sản phẩm dự đoán. 34 2.3. Các thuật toán tính độ tương tự Để dự đoán một sản phẩm cho một người dùng sử dụng phương pháp lọc cộng tác cần xem xét đánh giá của người dùng lên những sản phẩm tương tự với sản phẩm đó, độ tương tự được xác định dựa vào đánh giá của users khác đã đánh giá cả 2 sản phẩm. Độ tương tự 2 sản phẩm là 1 xác suất thể hiện 2 sản phẩm đó có tương tự nhau trên khía cạnh đánh giá của người dùng hay không? Độ tương tự ở đây được hiểu là nếu 2 sản phẩm tương tự nhau thì 1 người dùng thích sản phẩm này sẽ thích sản phẩm kia và ngược lại. Bước quan trọng trong giải thuật lọc cộng tác dựa trên sản phẩm là tính toán độ tương tự giữa các sản phẩm và sau đó chọn những sản phẩm mà tương đương nhất để sử dụng trong công thức dự đoán. Ý tưởng cơ bản trong tính toán độ tương tự giữa hai sản phẩm i và j là: chọn các cặp người dùng mà đã đánh giá cả 2 sản phẩm và sau đó áp dụng kỹ thuật tính toán độ tương tự để mô tả độ tương tự 푆푖,푗. Hình 2.1: Tách các sản phẩm cùng được đánh giá và tính toán độ tương tự 35 2.3.1. Độ tương tự Cosine (Cosine-based Similarity) Trong trường hợp này, cả 2 sản phẩm được biểu diễn thông qua 2 véc tơ m chiều không gian đánh giá của người dùng. Độ tương tự giữa chúng được đo dựa trên tính toán cosine góc giữa 2 véc tơ đó. Trong ma trận đánh giá m x n, độ tương tự giữa hay sản phẩm i và j, biểu diễn là sim(i, j) được cho bởi công thức: 푖 . 푗 ∑푢∈푆 푅푢푖 × 푅푢푗 푆푖푚(푖, 푗) = = |푖 |2 × |푗 |2 2 2 (2.1) √∑푢∈푆 푅푢푖 × √∑푢∈푆 푅푢푗 Trong đó: - 푅푢푖 là đánh giá của người dùng u với sản phẩm i - 푅푢푗 là đánh giá của người dùng u với sản phẩm j - S là tập users đã đánh giá cả 2 sản phẩm i, j Mỗi một sản phẩm được đánh giá bởi n người dùng và được xác định như là 1 véc tơ n chiều trong công thức này, ở đây những người dùng được chọn là những người đã đánh giá cả 2 sản phẩm i và j. Như vậy theo công thức ở trên, kết quả là cosine của góc hợp giữa 2 véc tơ đó. Và vì các đánh giá là dương nên, cosine của 2 véc tơ bằng 1 thể hiện 2 sản phẩm tự nhau hoàn toàn với những đánh giá của người dùng, cosine của 2 véc tơ bằng 0, thể hiện 2 sản phẩm này không tương tự nhau. 2.3.2. Độ tương tự dựa theo khoảng cách Euclidean điều chỉnh (Adjusted Euclidean Distance similarity) Theo [8], khi phân tích độ đo tương tự cosine phương pháp này xem các sản phẩm như cách véc tơ để đánh giá, tuy nhiên lại không xét đến độ dài của chúng. Cho một phần của ma trận đánh giá (phạm vi từ 1 đến 5) và được biểu diễn như sau. 36 2.3.3. Độ tương tự tương quan (correlation-based similarity) Trong trường hợp này, độ tương tự giữa 2 sản phẩm i và j là được đo dựa trên tính toán độ tương quan Pearson-r là: corr(i, i). Để tính toán độ tương quan này một cách chính xác, đầu tiên phải xét các cặp sản phẩm đã được đánh giá bởi người dùng u, biểu diễn trong hình 2.1. Độ tương tự của 2 sản phẩm i, j được cho bởi công thức sau: ∑푢∈푆(푅푢푖 − 푅̅푖) × ∑푢∈푆(푅푢푗 − 푅̅푗) 푆푖푚(푖, 푗) = 2 2 (2.2) √∑푢∈푆(푅푢푖 − 푅̅푖) × √∑푢∈푆(푅푢푗 − 푅̅푗) Trong đó: - 푅푢푖 là đánh giá của người dùng u với sản phẩm i - 푅̅푖 là đánh giá trung bình sản phẩm i của users - 푅푢푖 là đánh giá của người dùng u với sản phẩm j - 푅̅푗 là đánh giá trung bình sản phẩm j của users - S là tập users đã đánh giá cả 2 sản phẩm i, j 2.3.4. Độ tương tự cosine điều chỉnh (Adjusted Cosine similarity) Tính toán độ tương tự sử dụng độ đo cosine trong trường hợp dựa trên sản phẩm có một sự trở ngại quan trọng: những sự khác nhau trong thang đánh giá giữa users khác nhau không được đưa vào tài khoản. Độ tương tự cosine điều chỉnh khắc phục nhược điểm này bằng cách trừ trung bình người dùng tương ứng với mỗi cặp đánh giá. Độ tương tự giữa sản phẩm i và j được cho bởi công thức sau: ∑푢∈푆(푅푢푖 − 푅̅̅̅푢̅) × ∑푢∈푆(푅푢푗 − 푅̅̅̅푢̅) 푆푖푚(푖, 푗) = 2 2 (2.3) √∑푢∈푆(푅푢푖 − 푅̅̅̅푢̅) × √∑푢∈푆(푅푢푗 − 푅̅̅̅푢̅) Trong đó: - 푅푢푖 là đánh giá của người dùng u với sản phẩm i 37 - 푅푢푗 là đánh giá của người dùng u với sản phẩm j - 푅̅̅̅푢̅ là đánh giá trung bình của người dùng u - S là tập users đã đánh giá cả 2 sản phẩm i, j 2.4. Tính toán dự đoán và tư vấn Đưa ra được những dự đoán hoặc lời gợi ý là một bước quan trọng trong hệ tư vấn lọc cộng tác. Sau khi tính toán độ tương tự giữa các người dùng hay giữa các sản phẩm, chúng ta có thể dự đoán đánh giá của người dùng u trên sản phẩm i. Phần trên đã đưa ra những sản phẩm tương tự nhất dựa trên độ tương tự, bước tiếp theo là nghiên cứu kỹ mục tiêu xếp hạng của người dùng và sử dụng kỹ thuật để thu được dự đoán. Dự đoán đánh giá của một người dùng lên một sản phẩm được suy ra từ các đánh giá của người dùng đó trên các sản phẩm lân cận. Hình 2.2: Giải thuật lọc cộng tác dựa trên sản phẩm, tính dự đoán 2.4.1. Dự đoán dựa trên trung bình đánh giá sản phẩm lân cận Dựa vào [8] công thức đơn giản nhất để dự đoán của 1 người dùng u lên 1 sản phẩm i là dựa vào những người dùng lân cận của u mà đã đánh giá sản phẩm i. 38 1 푃 = ∑ 푟 ′ 푎푖 푁 푎푖 (2.4) 푖′푇푖∩푆푎 Trong đó: - N là tổng các sản phẩm lân cận của i đã được a đánh giá. - 푇푖 là tập hợp users i’ lân cận với i mà u đã đánh giá - 푆푎: các sản phẩm mà người dùng a đã đánh giá Vấn đề là chọn ra các sản phẩm 푖′ lân cận với sản phẩm i với các tiêu chí nhưthế nào, trong bài toán này, kết quả phụ thuộc vào tiêu chí chọn ra các lận cận của sản phẩm i. 2.4.2. Dự đoán dựa trên tổng trọng số (Weighted Sum) Dự đoán đánh giá của người dùng a với sản phẩm i được cho bởi công thức sau: ∑푗∈푆 ∩푇 푠푖푚(푖, 푗) × 푟푎푗 푃 = 푎 푖 (2.5) 푎푖 ∑ | | 푗∈푆푎∩푇푖 푠푖푚(푖, 푗) - 푆푎: các sản phẩm mà người dùng a đã đánh giá - 푟푎푗 là đánh giá sản phẩm j của người dung a - sim(i, j) là độ tương tự của 2 sản phẩm i, j - 푇푖: Tập các sản phẩm lân cận của item i Công thức tính toán đánh giá của người dùng a lên sản phẩm i dựa vào những đánh giá của người dùng a lên các sản phẩm tương tự với i. Giá trị dự đoán sẽ nằm trong khoảng [1, 5]. Trường hợp dự đoán sẽ cho kết quả cao (người dùng a thích sản phẩm i) khi những sản phẩm lân cận với i (có độ tương tự cao) được người dùng a đánh giá cao. 2.4.3. Dự đoán dựa trên tổng trọng số với đánh giá trung bình của người dùng ∑푗∈푆 ∩푇 푠푖푚(푖, 푗) × (푟푎푗 − 푅̅̅̅푎̅) 푃 = 푅̅̅̅̅ + 푎 푖 (2.6) 푎푖 푎 ∑ | | 푗∈푆푎∩푇푖 푠푖푚(푖, 푗) - 푆푎: các sản phẩm mà người dùng a đã đánh giá - 푟푎푖:là đánh giá sản phẩm j của người dung a - sim(i, j) là độ tương tự của 2 sản phẩm i, j 39 - 푇푖: Tập các sản phẩm lân cận của sản phẩm i - 푅̅̅̅푎̅ là đánh giá trung bình của người dùng a Công thức tính toán đánh giá của người dùng a lên sản phẩm i dựa vào những đánh giá của người dùng a lên các sản phẩm tương tự với i. Giá trị đánh giá trung bình của người dùng a là푅̅nhằm làm tăng tính cân đối của người dùng a lên sản phẩm. Giá trị 푅̅ của mỗi người dùng là một mức để xác định người dùng đó đánh giá cao hay không cao một sản phẩm. Giá trị dự đoán sẽ nằm trong khoảng [1, 5]. Trường hợp dự đoán sẽ cho kết quả cao (người dùng a thích sản phẩm i) khi những sản phẩm lân cận với i (có độ tương tự cao) được người dùng a đánh giá cao. 2.4.4. Dự đoán dựa trên tổng trọng số với trung bình đánh giá lên sản phẩm ∑푗∈푆 ∩푇 푠푖푚(푖, 푗) × (푟푎푗 − 푅̅푗) 푃 = 푅̅ + 푎 푖 (2.7) 푎푖 푖 ∑ | | 푗∈푆푎∩푇푖 푠푖푚(푖, 푗) - 푆푎: các sản phẩm mà người dùng a đã đánh giá - 푟푎푗là đánh giá sản phẩm j của người dung a - sim(i, j) là độ tương tự của 2 sản phẩm i, j - 푇푖: Tập các sản phẩm lân cận của sản phẩm i - 푅̅푖 là đánh giá trung bình sản phẩm i - 푅̅푗 là đánh giá trung bình sản phẩm j Công thức tính toán đánh giá của người dùng a lên sản phẩm i dựa vào những đánh giá của người dùng a lên các sản phẩm tương tự với i. 푅̅푖 là giá trị đánh giá trung bình sản phẩm i của người users. Giá trị 푅̅ của mỗi sản phẩm là một mức để xác định khi 1 người dùng đánh giá sản phẩm i, thì so với tất cả users, đánh giá của người đó cho sản phẩm i đó là cao hay không cao. Giá trị dự đoán sẽ nằm trong khoảng [1, 5]. Trường hợp dự đoán sẽ cho kết quả cao (người dùng a thích sản phẩm i) khi những sản phẩm lân cận với i (có độ tương tự cao) được người dùng a đánh giá cao. 40 2.5. Đánh giá các yếu tố ảnh hưởng đến độ chính xác kết quả tư vấn Phần trên đã giới thiệu các bước của 1 quá trình tư vấn sử dụng phương pháp lọc cộng tác dựa trên sản phẩm. Sau khi thực hiện quá trình xử lý, hệ thống có thể đưa ra các dự đoán đánh giá của người dùng với 1 sản phẩm, hoặc đề xuất danh sách các sản phẩm mà người dùng thích (đưa ra sản phẩm được dự đoán có đánh giá cao). Một hệ tự vấn tốt khi đề xuất được những sản phẩm mà người dùng đó sẽ thích và lựa chọn. Dữ liệu đầu vào Tư vấn danh sách sản phẩm cho Đánh giá chất người dùng Tiền xử lý dữ liệu lượng dự đoán Tính toán sai số Chọn TopN Ma trận đánh Đánh giá sản phẩm giá Dự đoán đánh giá Dự đoán và tư của người dùng lên Tính toán độ tương tự vấn sản phẩm Ma trận độ Chọn lân cận tương tự Hình 2.3: Mô hình hệ thống lọc cộng tác dựa trên sản phẩm 2.5.1. Đánh giá độ tin cậy của thuật toán Trong thực tế để đánh giá chính xác của 1 thuật toán tư vấn, các chuyên gia xây dựng bộ dữ liệu và kết quả kiểm tra thực tế, so sánh các kết quả dự đoán từ bộ dữ liệu với kết quả thực tế để đánh giá chất lượng của tư vấn. Một giải thuật tư vấn tốt là giải thuật đưa ra các dự đoán đánh giá gần chính xác với đánh giá thật sự của người dùng trong thực tế. Để đánh giá hiệu quả của việc gợi ý, người ta thường dùng các độ đo liên quan đến sự “phù hợp trên kết quả trả về” tương tự như trong truy tìm thông tin. Gợi ý được xem là phù hợp khi người dùng chọn mục tin từ danh sách các 41 mục tin đã được hệ thống gợi ý cho người dùng. Độ phù hợp này có thể được đánh giá qua các độ đo như MAE , Precision, Recall, F-Measure [9], mỗi phương pháp đánh giá sẽ thích hợp cho từng lĩnh vực cụ thể. Sai số tuyệt đối (Mean Absolute Error - MAE) giữa đánh giá và dự đoán. MAE là độ đo lệch của tư vấn với giá trị chính xác trên thực tế. Mỗi dự đoán là một cặp , độ đo sai số tuyệt đối giữa chúng là |푝푖− 푞푖|. MAE tính toán tổng những sai số tuyệt đối của N cặp tương ứng với đánh giá dự đoán và sau đó tính giá trị trung bình. ∑푁 |푝 − 푞 | 푀퐴퐸 = 푖=1 푖 푖 (2.8) 푁 Các chỉ số này thích hợp cho một cơ sở dữ liệu không phải nhị phân và cho một giá trị dự đoán là số. Nó giúp đo lường mức độ sai số của các dự đoán. Các giá trị đo lường này bằng 0 khi hệ thống đạt được hiệu quả tốt nhất. Giá trị này càng cao thì hiệu quả của hệ thống càng thấp. Precision là tỷ lệ giữa số lượng các gợi ý phù hợp và tổng số các gợi ý đã cung cấp (đã tạo ra). Precision bằng 100% có nghĩa là tất cả các kiến nghị đều phù hợp. 푆ố 푙ượ푛푔 푔ợ푖 ý 푝hù hợ푝 Precision = (2.9) 푆ố 푙ượ푛푔 푔ợ푖 ý 푡ạ표 푟푎 Recall được định nghĩa bởi tỉ lệ giữa số lượng các gợi ý phù hợp và số lượng các mục dữ liệu mà người dùng đã chọn lựa (xem, nghe, mua, đọc). Recall được sử dụng để đo khả năng hệ thống tìm được những mục dữ liệu phù hợp so với những gì mà người dùng cần. 푆ố 푙ượ푛푔 푔ợ푖 ý 푝hù hợ푝 Recall = (2.10) 푆ố 푙ượ푛푔 푠ả푛 푝hẩ푚 푚푢푎 푏ở푖 푛푔ườ푖 푑ù푛푔 Precision và Recall được xem là hữu ích trong việc đánh giá một gợi ý. Tuy nhiên, trong một số trường hợp thì precision và recall có giá trị tỉ lệ nghịch 42 với nhau. Ví dụ như số lượng gợi ý mà hệ thống tạo ra là 10, số lượng gợi ý phù hợp là 3, số lượng sản phẩm mua bởi người dùng là 3 thì độ chính xác thấp (30%), tuy nhiên giá trị recall lại cao (100%) nghĩa là độ chính xác thấp nhưng người dùng lại hài lòng bởi vì họ mua có 3 sản phẩm và hệ thống gợi ý đúng cả 3 sản phẩm đó. F-Measure được sử dụng để đánh giá hiệu quả tổng thể của hệ thống bằng cách kết hợp cả hai chỉ số Recall và Precision. 2 × Precison × Recall F − Measure = (2.11) Precision + Recall 2.5.2. Các yếu tố ảnh hưởng đến độ chính xác tư vấn - Ảnh hưởng của dữ liệu đầu vào: Trong nhiều hệ thống tư vấn, số những đánh giá thu được thường rất nhỏ so với số những đánh giá cần có cho dự đoán. Sự thành công của hệ thống tư vấn lọc cộng tác phụ thuộc vào giá trị của đại đa số những người dùng chính. Chẳng hạn, trong hệ thống tư vấn điện ảnh, có rất nhiều bộ phim đã được đánh giá chỉ bởi một vài người và những bộ phim này khả năng được tư vấn là rất ít, thậm chí ngay cả khi trong số đó có những người dùng đưa ra đánh giá rất cao về chúng. Cũng như vậy, đối với những người dùng mà thị hiếu của họ khác thường so với một số đông người khác thì sẽ không có người dùng nào được tư vấn về những thị hiếu giống họ, dẫn đến việc tư vấn nghèo nàn. Một phương pháp vượt qua tính thưa thớt trong đánh giá là sử dụng thông tin cá nhân của người dùng khi tính toán sự tương tự giữa những người dùng. Hai người dùng được xem là giống nhau không khi được đánh giá có sở thích về các bộ phim là giống nhau mà chúng còn phải thuộc cùng một đối tượng. Chẳng hạn, sử dụng giới tính, tuổi, địa chỉ khu vực, nền giáo dục và thông tin công việc của những người dùng trong việc tư vấn nhà hàng. Sự mở rộng của những kỹ thuật lọc cộng tác thường được gọi là “lọc demographic”. 43 Một vấn đề trước khi xây dựng ma trận đánh giá, với những sản phẩm ít được đánh giá, hoặc những người dùng ít đánh giá sản phẩm, những người dùng và sản phẩm này sẽ không hữu ích trong quá trình tư vấn. Vấn đề cần chọn lọc ra những sản phẩm và người dùng để tham gia trong quá trình tư vấn. Rõ ràng những sản phẩm mới hoặc người dùng mới không thể tham gia trong quá trình dự đoán, hoặc những sản phẩm hay người dùng có đánh giá ít hơn 1 ngưỡng nào đó cũng được loại ra. - Ảnh hưởng của thuật toán tính độ tương tự: Để xây dựng ma trận tương tự, các giá trị được tính toán theo một công thức được đề xuất ở trên hoặc một công thức khác. Các công thức tính toán khác nhau sẽ cho ra các ma trận đánh giá khác nhau, dẫn đến kết quả tư vấn không đồng nhất. Nhiều chuyên gia đánh giá, với thuật toán có sự tham gia của đánh giá trung bình sẽ có kết quả tốt hơn. Chương 3 sẽ thí nghiệm kết quả tư vấn với các thuật toán tính độ tương tự và đưa ra nhận xét về độ chính xác của kết quả tư vấn khi áp dụng các độ tương tự khác nhau. - Ảnh hưởng của số lượng lân cận tham gia vào dự đoán: Thông qua quá trình tính ma trận tương tự, hệ thống tư vấn sử dụng những sản phẩm lân cận nhất với sản phẩm đang xét để đưa vào dự đoán, số lượng lân cận ảnh hưởng đến chất lượng của kết quả tư vấn. Chọn số lượng lân cận có thể dựa vào số lượng lân cận của sản phẩm hoặc dựa vào giá trị của độ đo tương tự. Ví dụ: Trong hệ thống tư vấn phim với số bộ phim là 1000 bộ phim, khi cần tư vấn 1 bộ phim, có thể sẽ xét trên 100 bộ phim lân cận với bộ phim đang xét, hoặc là xét với những bộ phim lân cận có độ tương tự lớn 0.75. Số lượng lân cận tham gia vào dự đoán ảnh hưởng đến quá trình đưa ra dự đoán, nhiều chuyên gia lựa chọn những sản phẩm có độ tương tự 0.75 để tham gia vào dự đoán. 44 2.6. Kết luận chương 2 Trong chương này, luận văn đã trình bày về phương pháp lọc cộng tác dựa trên sản phẩm, minh họa quá trình xử lý để đưa ra các kết quả tư vấn dựa trên các thuật toán khác nhau. Vấn đề là cần đánh giá chất lượng thuật toán để có thể đưa ra tư vấn chính xác nhất, các yếu tố nào có thể nâng cao được chất lượng tư vấn. Trong chương tiếp theo, luận văn sẽ thử nghiệm các thuật toán tư vấn với bộ dữ liệu tư vấn phim, để đưa ra các kết quả tư vấn, so sánh đánh giá các thuật toán áp dụng trong quá trình tư vấn. 45 CHƯƠNG 3. ỨNG DỤNG PHƯƠNG PHÁP LỌC CỘNG TÁC DỰA TRÊN SẢN PHẨM TRONG HỆ THỐNG GỢI Ý BÁN HÀNG TRỰC TUYẾN 3.1. Xây dựng hệ thống gợi ý cho website bán hàng trực tuyến 3.1.1. Đặc tả hệ thống Hệ thống giới thiệu và bán sản phẩm thời trang trực tuyến cho phép khách hàng bất kỳ có thể tìm kiếm và xem các sản phẩm thời trang. Hệ thống sẽ hiển thị các sản phẩm được ưa thích nhất và các sản phẩm bán chạy nhất. Hệ thống có chức năng cho khách hàng chấm điểm, đánh giá sản phẩm và có thể đặt hàng thông qua hệ thống này. Đặc biệt hệ thống sẽ gợi ý các sản phẩm cho khách hàng trong quá trình chọn sản phẩm sử dụng kỹ thuật lọc cộng tác và hiển thị các sản phẩm tương tự với sản phẩm mà khách hàng đang xem. Đây là giải thuật có độ tin cậy cao vì đã được kiểm nghiệm qua nhiều công trình nghiên cứu nên việc gợi ý sử dụng kỹ thuật lọc cộng tác có thể sẽ tốt hơn các gợi ý thông thường như gợi ý sản phẩm bổ trợ sản phẩm vừa mua, gợi ý sản phẩm tương tự với sản phẩm mà khách hàng ưa thích, gợi ý sản phẩm theo giá chênh lệch với sản phẩm mà khách hàng đang xem... Khách hàng muốn thực hiện các chức năng trên chỉ khi khách hàng là thành viên của hệ thống. Muốn trở thành viên của hệ thống, khách hàng phải đăng ký tài khoản thông qua hệ thống. Sau khi đăng nhập vào hệ thống, nếu là khách hàng mới thì hệ thống sẽ dựa vào thông tin về tính cách và mùi hương ưa thích của khách hàng để tư vấn những sản phẩm theo thông tin vừa thu thập. Tuy nhiên, nếu khách hàng đã có chấm điểm cho sản phẩm, hệ thống sẽ gợi ý các sản phẩm theo giải thuật lọc cộng tác. Ngoài ra, hệ thống còn cung cấp các công cụ quản trị như: quản trị khách hàng, quản trị thông tin về thương hiệu và sản phẩm, quản trị đơn đặt hàng. 46 3.1.2. Môi trường phát triển Hệ thống bán sản phẩm thời trang trực tuyến được phát triển trên môi trường mã nguồn mở PHP & My SQL. Hệ thống được phát triển dựa trên nền tảng mã nguồn mở WordPress tích hợp và phát triển thêm các modul hệ thống gợi ý dựa trên phương pháp lọc cộng tác dựa trên sản phẩm. Nền tảng mã nguồn mờ WordPress được rất nhiều website thương mại điện tử sử dụng, vì vậy chúng ta có thể dễ dàng tích hợp hệ thống gợi ý vào những website có sẵn. 3.1.3. Thiết kế bảng dữ liệu Website bán hàng sẽ được xây dựng trên nền tảng Wordpress để có thể tận dụng hệ thống plugin hỗ trợ và các tính năng nổi bật về quản lý, thống kê. Đối với mô hình website bán hàng, các items tương ứng với các sản phẩm, các users được chia thành hai loại: user có đăng kí tài khoản, được phân biệt bằng user_id và có lưu các thông tin liên quan trong cơ sở dữ liệu và user không đăng kí tài khoản, chỉ xem sản phẩm thông thường. Ta gọi user loại đầu là thành viên và loại còn lại là khách viếng thăm. Sau khi chọn một sản phẩm bất kì để xem chi tiết sản phẩm, chỉ có thành viên đăng kí và đăng nhập mới được nhận xét. Mức độ đánh giá thay đổi từ 1 đến 5 sao, với 1 sao là mức ít yêu thích nhất và 5 sao là rất yêu thích. Trong cơ sở dữ liệu, ta sẽ quan tâm đến các bảng sau: wp_comments, wp_commentmeta, wp_user_rating, wp_predict. Bảng wp_comments: lưu trữ các nhận xét cho mỗi sản phẩm và id của những user đã nhận xét sản phẩm đó. STT Tên thuộc tính Kiểu dữ liệu Ghi chú 1 comment_ID int (20) id của nhận xét 2 comment_post_ID int (20) id của sản phẩm đã được nhận xét. 3 user_id int (20) id của user đã nhận xét. 47 Bảng wp_commentmeta: lưu trữ giá trị yêu thích (tức là số sao mà từng user đã đánh giá trong mỗi nhận xét). STT Tên thuộc tính Kiểu dữ Ghi chú liệu 1 comment_id int (20) id của nhận xét 2 meta_key varchar (255) 3 meta_value longtext Số sao mà user đã đánh giá Từ hai bảng trên ta tạo bảng wp_user_rating để truy vấn những thông tin cần thiết bao gồm: - comment_post_ID: ID của sản phẩm đã được nhận xét. - user_id: ID của user đã nhận xét. - meta_value: số sao mà user đã đánh giá. Trong WordPress có lưu hai giá trị meta_value là rating và verified, ở đây ta chỉ quan tâm đến các giá trị rating (meta_key = “rating”). STT Tên thuộc tính Kiểu dữ liệu Ghi chú 1 comment_post_ID int (20) id của sản phẩm đã được nhận xét. 2 user_id int (20) id của user đã nhận xét.. 3 meta_value longtext số sao mà user đã đánh giá Mỗi khi có một nhận xét mới từ thành viên, dữ liệu sẽ được tự động cập nhật vào bảng wp_user_rating. Dựa vào bảng này, chúng ta sẽ xây dựng Utility matrix tính độ tương tự (similarity) giữa các sản phẩm đã được nhận xét. Utility matrix được lưu trong bảng wp_predict gồm các cột: - item_id1: id của sản phẩm được nhận xét. - item_id2: id của sản phẩm được dự đoán gợi ý cho user 48 - times: số user đã đánh giá cả item_id1 và item_id2 - rating: độ chênh lệch giá trị rating của item_id1 và item_id2. Sau khi có Utility matrix, ta sẽ sử dụng dự đoán để hoàn thiện các giá trị còn thiếu, từ đó dùng truy vấn SQL để tìm id của những sản phẩm có thể gợi ý cho user hiện tại. Tên Kiểu STT Ghi chú thuộc tính dữ liệu 1 item_id1 int (11) id của sản phẩm đã được nhận xét. id của sản phẩm được dự đoán gợi ý cho 2 item_id2 int (11) user. 3 times int (11) số user đã đánh giá cả item_id1 và item_id2 4 Rating float Độ chênh lệch giá trị rating của item_id1 và item_id2 Hệ thống sử dụng CF dựa trên ratings có nhược điểm là chỉ áp dụng với những user đã nhận xét hoặc sản phẩm phải được đánh giá từ trước. Vậy với khách viếng thăm thì ta phải gợi ý cho họ như thế nào? Chúng ta có hai phương án: Nếu khách viếng thăm xem thông tin giới thiệu của một sản phẩm chưa có nhận xét nào, hệ thống sẽ giới thiệu cho khách viếng thăm những sản phẩm có cùng thể loại. Nếu khách viếng thăm xem thông tin của sản phẩm đã có nhận xét, hệ thống sẽ giới thiệu cho họ những sản phẩm có độ tương tự cao nhất với sản phẩm đó. 49 3.2. Ví dụ về lọc cộng tác dựa trên sản phẩm Khi người dùng đăng nhập vào hệ thống và đánh giá các sản phẩm, kết quả đánh giá sẽ được lưu trữ trong bảng wp_user_rating trong cơ sở dữ liệu. Trong bảng 2 là dữ liệu do 6 người dùng (u0, u1, u2, u3, u4, u5) đánh giá 5 sản phẩm (i0, i1, i2, i3, i4). Những sản phẩm chưa được đánh giá thì sẽ không xuất hiện trong bảng này. Bảng 2: Dữ liệu đánh giá các sản phẩm Mã sản phẩm Mã người dùng Đánh giá (comment_post_ID) (user_id) (meta_value) 0 0 5 1 0 4 3 0 2 4 0 2 1 1 5 3 1 4 4 1 2 5 1 4 1 2 2 3 2 1 4 2 3 5 2 4 1 3 3 2 3 4 4 3 4 1 4 1 4 4 4 2 5 2 3 5 1 3 5 1 4 5 4 5 5 5 Dựa vào dữ liệu trong Bảng 2, chúng ta xây dựng utility matrix như trong bảng 3. Trong bảng này, các ô có giá trị 0 là các sản phẩm chưa được đánh giá. 50 Bảng 3: Ma trận utility matrix u0 u1 u2 u3 u4 u5 u6 i0 5 5 2 3 1 0 0 i1 4 0 0 4 0 2 0 i2 0 4 1 0 0 1 1 i3 2 2 3 4 4 0 4 i4 2 4 4 0 0 0 5 Bảng 4: Giá trị trung bình đánh giá của các item Item Giá trị trung bình i0 3.20 i1 3.33 i2 1.75 i3 3.17 i4 3.75 Trong bảng 4 là giá trị trung bình đánh giá (rating) của user cho mỗi item (sản phẩm). Khi đó, nếu tiếp tục trừ từ mỗi rating đi giá trị này, ta sẽ được ma trận chuẩn hóa như trong bảng 5. 51 Việc trừ đi trung bình cộng của mỗi cột khiến trong trong mỗi cột có những giá trị dương và âm. Những giá trị dương tương ứng với việc user thích item, những giá trị âm tương ứng với việc user không thích item. Những giá trị bằng 0 tương ứng với việc chưa xác định được liệu user có thích item hay không. Bảng 5. Ma trận chuẩn hóa 푌̂ u0 u1 u2 u3 u4 u5 u6 i0 1.80 1.80 -1.20 -0.20 -2.20 0 0 i1 0.67 0 0 0.67 0 -1.33 0 i2 0 2.25 -0.75 0 0 -0.75 -0.75 i3 -1.17 -1.17 -0.17 0.83 0.83 0 0.83 i4 -1.75 0.25 0.25 0 0 0 1.25 Sử dụng độ do cosine để tính độ tượng tự giữa các item, chúng ta thu được dữ liệu như Bảng 6. Bảng 6: Độ tương tự giữa các item S i0 i1 i2 i3 i4 i0 1 0.18 0.53 -0.76 -0.38 i1 0.18 1.00 0.24 -0.06 -0.33 i2 0.53 0.24 1.00 -0.55 -0.10 i3 -0.76 -0.06 -0.55 1.00 0.57 i4 -0.38 -0.33 -0.10 0.57 1.00 52 Dự đoán tỷ lệ đánh giá là việc xác định mức độ quan tâm của một user lên một item dựa trên các users gần nhất. Ví dụ về việc tính tỷ lệ đánh giá của u1 cho i1 được cho trong bảng 5 với số nearest neighbors là k = 2. Các bước thực hiện là: - Xác định các item đã được đã u1 đánh giá, đó là: i0, i2, i3, i4. - Xác định độ tượng tự của i1 với các item này ta nhận được 0.18, 0.24, -0.06, -0.33. Hai (k=2) giá trị lớn nhất là 0.18 và 0.24 tương ứng với i0 và i2. - Xác định các đánh giá (chuẩn hoa) của u1 cho i0, i2, ta thu được hai giá trị lần lượt là 1.80, 2.25. - Dự đoán kết quả: 0.18 × 2.25 + 0.24 × 2.24 푦̂ = = 2.244 푖1,푢1 |0.18| + |0.24| Bảng 7: Ma trận sau khi được dự đoán 푌̂ u0 u1 u2 u3 u4 u5 u6 i0 1.80 1.80 -1.20 -0.20 -2.20 -0.30 -0.54 i1 0.67 2.22 -2.25 0.67 -0.15 -1.33 -0.22 i2 0.45 2.25 -0.75 -0.07 -0.53 -0.75 -0.75 i3 -1.17 -1.17 -0.17 0.83 0.83 0.236 0.83 i4