Tài liệu Nghiên cứu kỹ thuật phân tích ma trận trong các hệ thống khuyến nghị

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HỒNG XUÂN NGHIÊN CỨU KỸ THUẬT PHÂN TÍCH MA TRẬN TRONG CÁC HỆ THỐNG KHUYẾN NGHỊ LUẬN VĂN THẠC SĨ HÀ NỘI - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HỒNG XUÂN NGHIÊN CỨU KỸ THUẬT PHÂN TÍCH MA TRẬN TRONG CÁC HỆ THỐNG KHUYẾN NGHỊ Ngành : Công nghệ thông tin Chuyên ngành : Kỹ thuật phần mềm Mã số : 60480103 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Văn Vinh HÀ NỘI - 2014 Lời cam đoan Tôi xin cam đoan rằng luận văn của tôi hoàn toàn là công trình nghiên cứu của bản thân. Luận văn hoàn toàn không phải là bản sao chép công trình nghiên cứu của một người khác, nó mang tính độc lập nhất định với tất cả các công trình nghiên cứu trước đây. Nếu có vi phạm, tôi xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 05 tháng 06 năm 2014 Học viên Nguyễn Thị Hồng Xuân Lời cảm ơn Đầu tiên, tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo, cán bộ hướng dẫn khoa học TS. Nguyễn Văn Vinh, người thầy đã tận tình hướng dẫn cho tôi từ những buổi đầu tiên khi tiếp cận với đề tài tốt nghiệp. Thầy đã hướng dẫn, chỉ bảo tận tình cho tôi về phương pháp nghiên cứu khoa học, cách làm việc khoa học trong suốt thời gian qua. Tôi xin bày tỏ lòng biết ơn đến các thầy cô giáo ở trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình giảng dạy và tạo mọi điều kiện cho tôi học tập, nghiên cứu và hoàn thành luận văn này. Tôi xin chân thành cảm ơn bạn Nguyễn Tuấn Khoa, các bạn học viên khóa K18 Công nghệ phần mềm đã giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu và thực hiện luận văn. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc nhất đến gia đình, đồng nghiệp và bạn bè tôi, những người đã động viên, tạo mọi điều kiện cho tôi lao động và học tập trong suốt thời gian qua. Hà Nội, ngày 05 tháng 06 năm 2014 Học viên Nguyễn Thị Hồng Xuân Danh mục các từ viết tắt STT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Từ viết tắt Tiếng Anh U User P Product I Items V Items IR Information Retrieval IF Information Filtering RS Recommender Systems CF Collaborative Filtering MF Matrix Factorization MMMF Maximum Margin Matrix Factorization SVD Singular Value Decomposition LSI Latent Semantic Indexing SGD Stochastic Gradient Descent DSGD Distributed Stochastic Gradient Descent FPSGD Fast Parrael Stochastic Gradient Descent Tiếng việt Người dùng Sản phẩm Đối tượng Đối tượng Thu thập thông tin Lọc thông tin Hệ thống khuyến nghị Lọc cộng tác Phân tích ma trận Cực đại hóa biên trong phân tích ma trận Phân giải giá trị đơn Chỉ số ngữ nghĩa ẩn Phương pháp xuống đồi Phương pháp xuống đồi theo cách phân tán Phương pháp xuống đồi theo cách thực hiện nhanh và song song Danh mục hình vẽ trong luận văn Các hình vẽ được sử dụng trong luận văn: Hình 2.1: Trang khuyến nghị của Amazon ................................................................ 12 Hình 2.2: Trang khuyến nghị của MovieLens ............................................................ 13 Hình 2.3: Mô hình Bayes ........................................................................................... 24 Hình 3.1: Thuật toán SGD trong không gian 2 chiều ............................................... 30 Hình 3.2: Ví dụ về vấn đề locking trong DSGD ........................................................ 37 Hình 3.3: Phương pháp chọn ngẫu nhiên các xếp hạng để cập nhật ......................... 37 Hình 3.4: Minh họa các cách chia ma trận thành khối .............................................. 39 Hình 3.5: DoI trên 3 tập dữ liệu ................................................................................ 40 Hình 3.6: Phương pháp sắp thứ tự chọn các xếp hạng để cập nhật .......................... 40 Hình 3.7: So sánh giữa phương pháp ngẫu nhiên và phương pháp sắp thứ tự ........... 41 Hình 3.8: Minh họa phương pháp ngẫu nhiên từng phần .......................................... 41 Hình 3.9: So sánh phương pháp sắp thứ tự, ngẫu nhiên và ngẫu nhiên từng phần ... 42 Hình 4.1: Biểu đồ dữ liệu MovieLens 600K ................................................................ 47 Hình 4.2: Biểu đồ dữ liệu MovieLens với tham số k = 5 và γ = 0.003 ....................... 47 Hình 4.3: Biểu đồ dữ liệu MovieLens với tham số k = 10 và γ = 0.003 ..................... 48 Hình 4.4: Biểu đồ dữ liệu MovieLens với tham số k = 20 và γ = 0.003 ..................... 49 Hình 4.5: Biểu đồ dữ liệu MovieLens với tham số k = 50 và γ = 0.003 ..................... 49 Hình 4.5: Biểu đồ dữ liệu MovieLens với tham số k = 100 và γ = 0.003 ................... 50 Mở đầu Cùng với nhu cầu tìm kiếm thông tin trên Internet ngày càng trở nên phổ biến với một lượng lớn thông tin được đưa lên hằng ngày; một nhu cầu mới đặt ra là một thông tin nên hay không nên được đọc, được chia sẻ cho một đối tượng người sử dụng khác trên Internet? Thông tin nào sẽ có khả năng được đánh giá cao bởi một đối tượng người sử dụng? Và làm thế nào để xác định được thông tin đó có khả năng được người dùng đánh giá cao hay thấp? Để giải quyết vấn đề này đã có rất nhiều nghiên cứu thực hiện trên các lĩnh vực khác nhau, với những đối tượng thông tin khác nhau. Kết quả của các bài nghiên cứu đó nhằm hỗ trợ đưa ra một Hệ thống khuyến nghị (Recommender Systems - RS) phù hợp nhất. Hệ thống khuyến nghị có thể là một chương trình, một tập hợp các kỹ thuật nhằm đưa ra các khuyến nghị về các đối tượng cho người dùng khi nó có khả năng được sử dụng nhiều nhất. Quá trình đưa ra các khuyến nghị là một chuỗi các quá trình đưa ra các quyết định cho nhiều loại đối tượng. Trong những năm gần đây, hệ thống khuyến nghị đã hỗ trợ rất nhiều cho người dùng lựa chọn các thông tin thích hợp. Hệ thống này đã được ứng dụng trong nhiều lĩnh vực như: thương mại điện tử (Amazon, Netflic, Ebay); giải trí (MovieLens, Last.fm, Film-Conseil); tin tức trực tuyến (NetNews, Yahoo, Google); . . . Hệ thống khuyến nghị được phát triển dựa vào cách dự đoán, ước lượng xếp hạng (rating) cho các dữ liệu bằng cách sử dụng học máy, lý thuyết xấp xỉ, các thuật toán trong xác suất thống kê, . . . Từ đó, nó có thể đưa ra các thông tin phù hợp trong số những thông tin khổng lồ chưa có trật tự nào. Hệ thống này sử dụng các kỹ thuật lọc để chọn ra những loại thông tin đặc trưng nhằm hiển thị các phần tử thích hợp với sở thích của người dùng. Nhìn chung, các kỹ thuật lọc trong hệ khuyến nghị được phát triển bởi một trong hai cách tiếp cận là lọc nội dung (content filtering) và lọc cộng tác (collaborative filtering). Hiện nay, phần lớn các hệ thống khuyến nghị phát triển dựa vào lọc cộng tác dựa trên những hành vi quá khứ của người dùng như: lịch sử giao dịch, đánh giá sản phẩm, thời gian xem một mục tin,. . . ; đặc biệt nó không cần phải tạo các hồ sơ tường minh cho người dùng. Có hai nhánh nghiên cứu về lọc cộng tác là: tiếp cận láng giềng (neighborhood approach) và mô hình nhân tố ẩn (latent factor models). Mô hình nhân tố ẩn có dạng tương tự phương pháp phân tích giá trị đơn nhằm chuyển đổi các sản phẩm (items) và người dùng (users) vào cùng một không gian ẩn, do đó chúng có khả năng so sánh dữ liệu trực tiếp với nhau. Chính vì nhờ vào khả năng biểu diễn và so sánh, tiếp cận này có xu hướng cung cấp kết quả dự đoán cao hơn các mô hình láng vi giềng. Vì vậy trong luận văn này, tôi xin được trình bày về mô hình nhân tố ẩn cho hệ thống khuyến nghị. Cụ thể hơn, tôi tập trung nghiên cứu về kĩ thuật phân tích ma trận (một trong những phương pháp hiệu quả cho mô hình nhân tố ẩn) và ứng dụng trong hệ thống khuyến nghị. Trong phạm vi của luận văn, chúng ta nghiên cứu và phân tích các mô hình đang tồn tại, cụ thể là mô hình xác suất kết hợp với ma trận nhân tố cho hệ khuyến nghị sử dụng dự đoán học máy. Nội dung chính của bản luận văn này được chia làm 4 chương: Chương 1: Tổng quan về hệ khuyến nghị (Recommender System). Chương 2: Phương pháp lọc cộng tác. Chương 3: Kĩ thuật phân tích ma trận trong hệ khuyến nghị. Chương 4: Thực nghiệm và demo Cụ thể, trước khi đi vào xem xét trực tiếp mô hình, trong chương 1, chúng ta đi tìm hiểu chung về hệ khuyến nghị, phân tích một số chức năng của các hệ khuyến nghị, các phương pháp khai phá dữ liệu được sử dụng, các hướng tiếp cận như lọc dựa vào nội dung, lọc cộng tác. Trong chương 2, chúng ta nghiên cứu sâu hơn về lọc cộng tác, các phương pháp tiếp cận trong lọc cộng tác. Chương 3 giới thiệu kĩ thuật phân tích ma trận cho hệ khuyến nghị. Chương 4 đưa ra một số ví dụ tính toán và những đánh giá cụ thể để so sánh những kết quả thực nghiệm với mô hình lý thuyết đã nêu trong chương 3. Mục lục Lời Cam Đoan i Lời Cảm Ơn ii Danh mục các từ viết tắt iii Danh mục hình vẽ trong luận văn iv Mở đầu v 1 Tổng quan về hệ thống khuyến nghị 1.1 Mô hình hệ thống khuyến nghị . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Các khái niệm chung về hệ thống khuyến nghị . . . . . . . . . . . 1.1.2 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Các chức năng của hệ thống khuyến nghị . . . . . . . . . . . . . . 1.1.4 Ứng dụng trong hệ thống khuyến nghị . . . . . . . . . . . . . . . 1.2 Các phương pháp khai phá dữ liệu được sử dụng . . . . . . . . . . . . . . 1.2.1 Khuyến nghị dựa trên nội dung (Content-Based Recommendation System) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Khuyến nghị lọc cộng tác (Collaborative Filtering Recomnendation System) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Kết hợp các phương pháp (Hybrid): . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 2 5 6 6 . 7 . . 8 9 . . . . . . . . . . . 11 11 13 14 17 19 20 20 21 22 22 23 2 Phương pháp lọc cộng tác 2.1 Giới thiệu về lọc cộng tác . . . . . . . . . . . . . . . . . 2.1.1 Ưu điểm của lọc cộng tác . . . . . . . . . . . . . 2.1.2 Các hình thức tiếp cận . . . . . . . . . . . . . . . 2.2 Lọc cộng tác dựa trên bộ nhớ . . . . . . . . . . . . . . . 2.2.1 Tính toán độ tương tự . . . . . . . . . . . . . . . 2.2.2 Tính toán dự đoán và khuyến nghị . . . . . . . . 2.3 Lọc cộng tác dựa trên mô hình . . . . . . . . . . . . . . 2.4 Các cách tiếp cận liên quan trong hệ thống khuyến nghị 2.4.1 Ước lượng cơ sở (Baseline Estimates) . . . . . . . 2.4.2 Mô hình láng giềng (Neighborhood models) . . . 2.4.3 Mô hình nhân tố ẩn (Latent factor models) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . MỤC LỤC 2.5 Khó khăn và thách thức trong 2.5.1 Sự thưa thớt dữ liệu . 2.5.2 Khả năng mở rộng . . 2.5.3 Tính đồng nghĩa . . . 2.5.4 Sự mập mờ . . . . . . 2.5.5 Sự tấn công . . . . . . viii lọc . . . . . . . . . . cộng . . . . . . . . . . . . . . . tác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Kĩ thuật phân tích ma trận cho hệ thống khuyến nghị 3.1 Kỹ thuật phân tích ma trận đơn giản . . . . . . . . . . . 3.2 Thuật toán SGD . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Cơ sở lý thuyết . . . . . . . . . . . . . . . . . . . 3.2.2 Phát biểu bài toán . . . . . . . . . . . . . . . . . 3.2.3 Thuật toán SGD dùng cho phân tích ma trận . . 3.3 Thuật toán DSGD . . . . . . . . . . . . . . . . . . . . . 3.3.1 Tính có thể tráo đổi được (interchangeability) . . 3.3.2 Trường hợp đơn giản . . . . . . . . . . . . . . . . 3.3.3 Trường hợp tổng quát . . . . . . . . . . . . . . . 3.4 Thuật toán FPSGD . . . . . . . . . . . . . . . . . . . . . 3.4.1 Vấn đề locking . . . . . . . . . . . . . . . . . . . 3.4.2 Gián đoạn bộ nhớ . . . . . . . . . . . . . . . . . . 3.4.3 Giải quyết vấn đề . . . . . . . . . . . . . . . . . . 4 Thực nghiệm và đánh giá 4.1 Cấu hình thử nghiệm . . . . . 4.1.1 Dữ liệu thử nghiệm . . 4.1.2 Thực hiện thử nghiệm 4.2 Phân tích kết quả và đánh giá 4.2.1 Phân tích kết quả . . . 4.2.2 Nhận xét và đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 24 25 25 26 26 . . . . . . . . . . . . . 28 28 30 30 31 31 32 32 33 35 36 36 37 38 . . . . . . 44 44 44 45 47 47 50 Kết luận 52 Tài liệu tham khảo 53 Chương 1 Tổng quan về hệ thống khuyến nghị 1.1 1.1.1 Mô hình hệ thống khuyến nghị Các khái niệm chung về hệ thống khuyến nghị Hệ thống khuyến nghị là hệ thống bao gồm các kỹ thuật và công cụ phần mềm nhằm đưa ra những gợi ý cho người sử dụng, đáp ứng nhu cầu của họ về một sản phẩm, dịch vụ nào đó trên Internet. Những gợi ý được cung cấp nhằm hỗ trợ người sử dụng đưa ra quyết định lựa chọn những sản phẩm, dịch vụ phù hợp với nhu cầu và thị hiếu của mình, chẳng hạn như: mua sản phẩm nào, nghe thể loại nhạc gì hay tin tức trực tuyến nào nên đọc, ... Item là thuật ngữ chung dùng để chỉ định những gì người dùng cần tương tác trong hệ thống khuyến nghị. Hệ thống khuyến nghị thông thường sẽ tập trung vào một thể loại Item cụ thể nào đó (CD, tin tức) theo thiết kế và giao diện đồ họa người dùng kết hợp với kỹ thuật, thuật toán gợi ý nhằm sinh ra các gợi ý tùy chỉnh, cung cấp những gợi ý có ích và hiệu quả cho Item đó. Hệ thống khuyến nghị nhằm hướng dẫn những người dùng thiếu kinh nghiệm hoặc chưa đủ thẩm quyền để đánh giá số lượng áp đảo các Item thay thế. Ví dụ, hệ thống khuyến nghị giúp người dùng lựa chọn sách trên trang web của Amazon đã sử dụng hệ thống khuyến nghị để cá nhân hóa các cửa hàng trực tuyến cho từng khách hàng (User). Khi hệ thống khuyến nghị được cá nhân hóa thì mỗi người dùng hay nhóm người dùng sẽ nhận được những gợi ý khác nhau từ những cá nhân khác. Mô hình đơn giản nhất của hệ thống khuyến nghị khi được cá nhân hóa là danh sách xếp hạng các Item. Khi thực hiện bảng xếp hạng này, hệ thống khuyến nghị sẽ thử dự đoán những sản phẩm hoặc dịch vụ phù hợp nhất với người dùng dựa trên sở thích và nhu cầu của họ. Để thực hiện được nhiệm vụ đó, RS thu thập sở thích của người dùng được thể hiện qua hệ thống (xếp hạng cho các sản phẩm) hoặc suy ra từ cách giải thích hành động của người dùng - là một tính năng ẩn có ưu tiên cho phần hiển thị của trang hoặc xem xét chuyến hướng đến một trang khác. Hệ thống khuyến nghị bắt đầu phát triển từ một quan sát khá đơn giản: một cá nhân thường dựa trên những gợi ý được cung cấp bởi những người khác trong việc đưa ra 1.1 Mô hình hệ thống khuyến nghị 2 những quyết định. Ví dụ, chúng ta thường dựa trên những gì bạn bè giới thiệu khi lựa chọn một cuốn sách để đọc, một bộ phim để xem; người dùng có khuynh hướng đọc và dựa vào các nhận xét của nhà phê bình phim nào đó viết và xuất hiện trên các trang báo họ đọc. Trong việc tìm kiếm để bắt chước hành vi này, đầu tiên hệ thống khuyến nghị áp dụng các thuật toán tận dụng các gợi ý được cung cấp bởi một cộng đồng người dùng sau đó sẽ cung cấp cho người dùng đang hoạt động (người đang tìm kiếm các đề xuất). Các gợi ý đã cho các hạng mục mà người dùng tương tự (người có sở thích tương tự) đã thích. Phương pháp này được gọi là lọc cộng tác và nguyên lý hoạt động của nó là: nếu người dùng thỏa thuận trong quá khứ với một số người dùng khác, sau đó sẽ sử dụng các gợi ý khác đến từ những người dùng tương tự có cùng sự quan tâm liên quan đến người dùng đang hoạt động. Các website thương mại điện tử ngày càng phát triển, người dùng phải rất khó khăn để tìm kiếm những lựa chọn thích hợp khi mà các Item( sản phẩm và dịch vụ) ngày càng đa dạng và phong phú trên các website;do vậy một nhu cầu cấp bách đặt ra là cung cấp hệ thống khuyến nghị xuất phát từ lọc cộng tác các lựa chọn thay thế có sẵn. Trong những năm gần đây, hệ thống khuyến nghị là một phương tiện có giá trị để đối phó với vấn đề quá tải thông tin. Đích cuối cùng mà hệ thống khuyến nghị muốn hướng tới là hướng dẫn cho một người dùng mới về các Item chưa hoặc không được xem trước đó nhưng lại có liên quan đến tác vụ hiện hành của người dùng. Theo yêu cầu của người dùng, nó có thể được khớp nối hay không phụ thuộc vào phương pháp tiếp cận gợi ý theo bối cảnh và nhu cầu người dùng. Hệ thống khuyến nghị đưa ra các gợi ý sử dụng các biến thể khác nhau của kiến thức và dữ liệu người dùng, các Item có sẵn và các giao dịch trước đó được lưu trong cơ sở dữ liệu tùy biến. Sau đó người dùng có thể duyệt các gợi ý: chấp nhận hay không và ngay lập tức đưa ra thông tin phản hồi ngầm hay rõ ràng ở giai đoạn tiếp theo. Tất cả những hành động và phản hồi của người dùng được lưu trữ trong cơ sở dữ liệu và có thể được sử dụng để đưa ra các khuyến cáo mới trong sự tương tác với người sử dụng hệ thống tiếp theo. Một vài ứng dụng nổi tiếng về hệ thống khuyến nghị như: khuyến nghị sản phẩm của Amazon [26], hệ tư vấn phim của NetFlix [27]. Hệ thống khuyến nghị đã chứng minh được ý nghĩa to lớn trong việc giúp người sử dụng trực tuyến đối phó với tình trạng quá tải thông tin. Chính vì vây, hệ thống khuyến nghị trở thành một trong những công cụ mạnh mẽ và phổ biến trong thương mại điện tử và trên nhiều lĩnh vực khác. Trong hầu hết các trường hợp, bài toán khuyến nghị được coi là bài toán ước lượng xếp hạng (rating) của các Item (phim, cd, nhà hàng . . . ) chưa được người dùng xem xét. Việc ước lượng này thường dựa trên những đánh giá đã có của chính người dùng đó hoặc từ những người dùng khác. Những Item có xếp hạng cao nhất sẽ được dùng để khuyến nghị. Từ đó người dùng có những lựa chọn thích hợp với nhu cầu và thị hiếu của mình. 1.1.2 Phát biểu bài toán Bài toán khuyến nghị được mô tả như sau: Gọi U là tập tất cả người dùng (users); V là tập tất cả các sản phẩm (items) có thể tư 1.1 Mô hình hệ thống khuyến nghị 3 vấn. Tập V có thể rất lớn, từ hàng trăm ngàn (sách, cd. . . ) đến hàng triệu (như website). Hàm r(u, v) đo độ phù hợp (hay hạng) của sản phẩm v với user u: r : U × V 7−→ R Trong đó R là tập các đánh giá (rating) được sắp thứ tự. Với mỗi người dùng u ∈ U , cần tìm sản phẩm v ∈ V sao cho hàm r(u, v) đạt giá trị lớn nhất. Trong hệ thống khuyến nghị có 3 đối tượng dữ liệu chính được sử dụng là: các mục tin trên hệ thống (Items), người sử dụng (Users) và các giao dịch - Transactions (liên quan giữa các item và user) Các mục tin (Items): Items là những đối tượng được đề nghị. Các mục tin có đặc tính phức tạp và có giá trị hữu ích. Giá trị của một item có thể là tích cực nếu nó có ích cho người sử dụng hoặc tiêu cực nếu nó không phù hợp khi người có lựa chọn sai. Lưu ý rằng khi người dùng nhận một item nào đó thì anh ta phải chịu một chi phí bao gồm việc tìm kiếm các item và chi phí thực để trả tiền cho item đó. Khi đó, các nhà thiết kế hệ thống khuyến nghị phải đưa sự phức tạp này của item vào tài khoản người dùng, ví dụ về cấu trúc, văn bản đại diện và thời gian phụ thuộc sự quan trọng của bất kì một item tin tức nào. Nhưng đồng thời các nhà thiết kế phải hiểu rằng thâm chí khi người dùng không trả tiền để đọc tin tức thì luôn có một chi phí nhận thức liên quan đến tìm kiếm và đọc các mục tin. Nếu một sản phẩm được chọn có liên quan đến người dùng chi phí này được chi phối bởi các lợi ích của việc có nên mua lại một thông tin hữu ích nào đó hay không, trong khi đó nếu các item không liên quan đến giá trị thực của sản phẩm thì khi được đề nghị nó sẽ là item tiêu cực. Trong các lĩnh vực khác như xe hơi, đầu tư tài chính thì chi phí tiền tệ thực của sản phẩm trở thành một yếu tố quan trọng để xem xét khi lựa chọn các phương pháp khuyến nghị thích hợp nhất. Một số item được phân loại theo giá trị và chức năng như sau: - Các item phức tạp có giá trị thấp: tin tức, trang web, sách, đĩa CD, phim ảnh. - Các item phức tạp có giá trị cao: máy ảnh kĩ thuật số, điện thoại di động, máy tính, ... - Các item phức tạp nhất là những chính sách bảo hiểm, đầu tư tài chính, phương tiện đi lại, việc làm. Công nghệ cốt lõi của hệ thống khuyến nghị là sử dụng một loạt các tính chất và tính năng của các item. Ví dụ như trong hệ thống khuyến nghị phim bao gồm: thể loại (hài, kinh dị, ...), đạo diễn, diễn viên,... để mô tả một bộ phim và tìm hiểu các tiện ích của một item phụ thuộc vào tính năng của nó. Các item được đại diện bằng cách sử dụng thông tin và đại diện các cách tiếp cận khác nhau, chẳng hạn như một mã id duy nhất hoặc trong hình phức phong phú hơn là tập các thuộc tính, phức tạp hơn là khái niệm đại diện tên miền. 1.1 Mô hình hệ thống khuyến nghị 4 Người sử dụng (Users): Như đã đề cập ở trên, người sử dụng trong hệ thống khuyến nghị là đối tượng để gợi ý có những mục tiêu và đặc điểm rất đa dạng. Để cá nhân hóa các khuyến nghị và tương tác người máy, hệ thống khuyến nghị khai thác một loạt các thông tin về người sử dụng. Những thông tin này có thể được cấu trúc theo nhiều cách khác nhau và việc chọn thông tin phụ thuộc vào kĩ thuật khuyến nghị. Ví dụ, trong lọc cộng tác người dùng được mô hình hóa dưới dạng danh sách đơn giản chứa các xếp hạng được cung cấp bởi người sử dụng đối với một số item. Trong hệ thống khuyến nghị nhân khẩu học, các thuộc tính được sử dụng là tuổi, giới tính, nghề nghiệp, trình độ học vấn. Từ đó, các dữ liệu người dùng sẽ tạo nên mô hình cá nhân người dùng để mã hóa sở thích và nhu cầu của người đó. Người sử dụng cũng có thể được mô tả bằng mô hình hành vi của họ, ví dụ trong mô hình trình duyệt (hệ thống khuyến nghị Website), mô hình tìm kiếm du lịch (hệ thống khuyến nghị du lịch). Ngoài ra, dữ liệu người dùng còn có thể bao gồm mối quan hệ giữa người sử dụng như mức độ tin cậy của các mối quan hệ giữa các người dùng. Hệ thống khuyến nghị có thể sử dụng thông tin này để giới thiệu các item từ một người dùng đáng tin cậy khác đã thích item này. Giao dịch (Transactions): Chúng ta đề cập chung đến một giao dịch là bản ghi tương tác giữa người sử dụng và hệ thống khuyến nghị. Giao dịch là dữ liệu đăng nhập chứa các thông tin quan trọng được tạo ra trong quá trình tương tác người - máy và nó giúp ích cho thuật toán khuyến nghị mà hệ thống đang sử dụng. Trong trường hợp này, một bản ghi giao dịch có thể chứa một tham chiếu đến các sản phẩm được chọn bởi người sử dụng và mô tả ngữ cảnh (mục tiêu sử dụng / truy vấn) cho hệ thống khuyến nghị. Trên thực tế, hình thức phổ biến nhất của dữ liệu giao dịch mà hệ thống khuyến nghị thu thập là các xếp hạng. Những đánh giá này có thể được thu thập một cách rõ ràng hoặc dưới dạng các biến ẩn. Trong trường hợp các xếp hạng là rõ ràng, người dùng sẽ được yêu cầu cung cấp ý kiến của mình về một mục trên thang điểm đánh giá. Các xếp hạng có thể ở các hình thức sau: - Xếp hạng số từ 1 đến 5 sao (hệ thống khuyến nghị sách trên Amazon.com). - Xếp hạng thứ tự chẳng hạn như: hoàn toàn đồng ý; đồng ý; trung lập; không đồng ý. Ở đây, người dùng được yêu cầu chọn thuật ngữ tốt nhất cho ý kiến của mình. - Xếp hạng nhị phân lựa chọn mô hình trong đó người dùng chỉ việc chọn mục nào đó là tốt hay xấu. - Xếp hạng Unary có thể chỉ ra được người dùng đã quan sát hoặc mua một item nào đó hoặc đã đánh giá trực tiếp trên item đó. Trong trường hợp này, sự vắng mặt của đánh giá cho thấy chúng ta không có thông tin liên quan giữa người dùng với item (có thể người đó đã mua ở chỗ khác). 1.1 Mô hình hệ thống khuyến nghị 5 Một hình thức khác để đánh giá là gộp tất cả các thẻ liên quan giữa người dùng với các item của hệ thống. Ví dụ, trong hệ thống khuyến nghị của MovieLens [28] các thẻ biểu diễn việc người dùng cảm thấy thế nào sau khi xem một bộ phim, có thể là "quá dài" hoặc "hành động". Trong các giao dịch xếp hạng dưới dạng ẩn, mục đích của hệ thống là để đưa ra ý kiến người dùng dựa trên các hành động của người dùng đó. Ví dụ, nếu người dùng nhập từ khóa "Yoga" ở Amazon thì anh ta sẽ được cung cấp một danh sách dài các cuốn sách có liên quan. Mặt khác, người dùng có thể click vào một cuốn sách nào đó trong danh sách để nhận được thêm thông tin. Ở điểm này, hệ thống có thể suy ra được người dùng có phần quan tâm đến cuốn sách đó. Với các hệ thống đàm thoại (hệ thống hỗ trợ một quá trình tương tác) mô hình giao dịch sẽ tinh tế hơn (dùng các yêu cầu bằng hành động). 1.1.3 Các chức năng của hệ thống khuyến nghị Như đã đề cập ở trên, hệ thống khuyến nghị là công cụ phần mềm và kỹ thuật cung cấp các đề xuất cho người dùng những sản phẩm, dịch vụ mà họ có thể muốn sử dụng. Dưới đây là một số chức năng của hệ thống: Tăng số lượng các mặt hàng bán ra cho các hệ thống thương mại điện tử: Đây có lẽ là chức năng quan trọng nhất của hệ thống khuyến nghị. Thay vì người dùng chỉ mua một sản phẩm mà họ cần, họ được khuyến nghị mua những sản phẩm "có thể họ cũng quan tâm" mà bản thân họ không nhận ra. Hệ thống khuyến nghị tìm ra những "mối quan tâm ẩn". Bằng cách đó, hệ thống khuyến nghị làm gia tăng nhu cầu của người dùng và gia tăng số lượng mặt hàng bán ra. Tương tự đối với các hệ thống phi thương mại (như các trang báo), hệ thống khuyến nghị sẽ giúp người dùng tiếp cận với nhiều đối tượng thông tin mang tính đa chiều và được nhiều người quan tâm hơn. Bán các mặt hàng đa dạng hơn trên các hệ thống thương mại điện tử: Đây là chức năng quan trọng thứ hai của hệ thống khuyến nghị. Hầu hết các hệ thống thương mại đều có các mặt hàng hết sức đa dạng và phong phú. Do vậy, khi nắm bắt được nhu cầu của người dùng, hệ thống khuyến nghị dễ dàng mang đến sự đa dạng trong sự lựa chọn hàng hóa. Từ đó, đòi hỏi các hệ thống thương mại điện tử cung cấp nhiều mặt hàng đa dạng và phù hợp với người sử dụng hơn. Tăng sự hài lòng người dùng: Vai trò chủ đạo của hệ thống khuyến nghị là hiểu nhu cầu của người dùng, gợi ý cho họ những thứ họ cần...Chính vì vậy hệ thống khuyến nghị tăng sự hài lòng của người dùng trên hệ thống và được lựa chọn ưu tiên khi họ có những băn khoăn hoặc khi chưa có kiến thức về sản phẩm. Tăng độ tin cậy, độ trung thực của người dùng: Hệ thống khuyến nghị cho người dùng những lựa chọn và họ hài lòng về những gợi ý đó thì lòng tin của họ đối với hệ thống (nơi mà giúp họ tìm ra những thứ họ thực sự quan tâm) được nâng lên một cách đáng kể. Đây thật sự là một điều thích thú và thu hút người dùng. Có một điểm quan trọng là hệ thống khuyến nghị hoạt động dựa trên những xếp hạng thật từ chính bản thân người dùng trong quá khứ. Do đó, khi người dùng càng tin cậy vào hệ thống, đưa ra những đánh giá trung thực cho các sản phẩm, hệ thống sẽ mang lại cho người dùng 1.2 Các phương pháp khai phá dữ liệu được sử dụng 6 nhiều gợi ý chính xác hơn, phù hợp với nhu cầu, sở thích trong cộng đồng người sử dụng trên Internet. Hiểu rõ hơn về những gì người dùng muốn: Đây là một chức năng quan trọng khác của hệ thống khuyến nghị được kế thừa từ nhiều ứng dụng khác nhau là thu thập hoặc dự đoán sở thích người dùng thông qua hệ thống. Điều này giúp cho các nhà phát triển dịch vụ có thể quyết định tái sử dụng các Item theo mục tiêu cải thiện quản lý cửa hàng hoặc tiến hành sản xuất. 1.1.4 Ứng dụng trong hệ thống khuyến nghị Chúng ta đã đề cập một số ứng dụng quan trọng của hệ thống khuyến nghị, nhưng ở đây chúng ta sẽ củng cố thêm những ứng dụng cơ bản sau: i) Khuyến nghị sản phẩm: Có lẽ người dùng quan trọng nhất của hệ thống khuyến nghị là các cửa hàng bán hàng trực tuyến. Chúng ta đã biết đến Amazon hoặc các nhà cung cấp trực tuyến tương tự đang phấn đấu để lôi kéo người dùng quan tâm đến những gợi ý sản phẩm họ có thể mua. Những khuyến nghị này không phải ngẫu nhiên mà nó dựa trên các quyết định mua hàng được thực hiện trên các khách hàng tương tự hoặc trên các công nghệ khác. ii) Khuyến nghị phim ảnh: Netflix cung cấp cho khách hàng các khuyến nghị về những bộ phim mà họ thích. Những khuyến nghị này được dựa trên các xếp hạng được cung cấp bởi người sử dụng (biểu diễn dưới dạng ma trận xếp hạng). Các dự đoán xếp hạng chính xác có tầm quan trọng rất lớn, Netflix đã đưa ra giải thưởng một triệu đô la cho người đầu tiên có thuật toán đánh bại 10% hệ thống khuyến nghị của chính họ. Sau 3 năm nghiên cứu, cuối cùng giải thưởng giành chiến thắng trong năm 2009 thuộc về nhóm các nhà nghiên cứu Bellkor’s Pragmatic Chaos. iii) Các trang tin tức: Dịch vụ tin tức đã cố gắng xác định sự quan tâm của độc giả dựa trên các bài viết mà họ đã đọc trong quá khứ. Sự giống nhau có thể dựa trên các từ khóa tương tự trong tài liệu hoặc các bài viết đã được đọc từ người đọc có cùng thị hiếu. Nguyên tắc áp dụng để khuyến nghị là cập nhật thường xuyên nội dung giữa hàng triệu blog có sẵn, video trên YouTube hoặc trên các trang web khác. 1.2 Các phương pháp khai phá dữ liệu được sử dụng 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ác suất, các thuật toán dựa trên kinh nghiệm, . . . Các hệ thống tư vấn thường được phân thành ba loại dựa trên cách nó dùng để ước lượng hạng của sản phẩm: 1.2 Các phương pháp khai phá dữ liệu được sử dụng 1.2.1 7 Khuyến nghị dựa trên nội dung (Content-Based Recommendation System) Khuyến nghị dựa trên nội dung được dựa trên mô tả có sẵn về đối tượng. Phương pháp khuyến nghị dựa trên nội dung, dựa trên độ phù hợp r(u, v) của sản phẩm v với người dùng u được đánh giá dựa trên độ phù hợp r(u, vi ), trong đó vi ∈ V và tương tự như v. Ví dụ, để gợi ý một bộ phim cho người dùng u, hệ thống khuyến nghị 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 đồng 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 (IR - Information Retrieval) và lọc thông tin (IF - Information Filtering). Do đó, rất nhiều hệ thống dựa trên nội dung hiện nay tập trung vào gợi ý các đối tượng chứa dữ liệu text như văn bản, tin tức, website,. . . Những tiến bộ so với hướng tiếp cận cũ của IR là do việ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). Cụ thể hơn, đặt Content(v) là tập thông tin (hay tập các đặc trưng) về sản phẩm v. Do hệ thống dựa trên nội dung được thiết kế chủ yếu để dành cho các sản phẩm là text, nên nội dung sản phẩm thường được biểu diễn bởi các từ khóa (keyword): Content(v) = (w1v , . . . , wkv ) với w1v , . . . , wkv là trọng số của các từ khóa từ 1 đến k. Ví dụ, ở hệ thống khuyến nghị website Fab biểu diễn nội dung các trang web bằng 100 từ quan trọng nhất. Tương tự, hệ thống Syskill & Webert biểu diễn văn bản bằng 128 từ có trọng số cao nhất. Đặt Profile(u) là hồ sơ về người dùng u, bao gồm các thông tin cơ bản về sở thích của u. Những thông tin này có được bằng cách phân tích nội dung của các sản phẩm từng được u đánh giá (rating) trước đó. Phương pháp được sử dụng thường là các kĩ thuật phân tích từ khóa của IR, do đó, Profile(u) cũng có thể được định nghĩa như một vector trọng số: Profile(u) = (w1u , . . . , wku ) với wi u biểu diễn độ quan trọng của từ khóa i với người dùng u. Trong hệ thống khuyến nghị dựa trên nội dung, độ phù hợp r(u, v) được xác định bởi công thức: r(u, v) = score(Profile(u), Content(v)) Cả Profile(u), Content(v) đều có thể được biểu diễn bằng vector trọng số (tương ứng là − →, − → w u wv ) nên có thể đo độ tương đồng của chúng bằng độ đo cosin: − →.− → w u wv →, − →) = r(u, v) = cos(− w w u v −−−→ −−→ kwu k × kwv k Ví dụ, nếu u đọc nhiều bài báo thuộc lĩnh vực sinh học thì các từ khóa liên quan tới sinh học (như: gen, protein, tế bào, ADN, ...) trong Profile(u) sẽ có trọng số cao. Hệ quả là với các bài báo v cũng thuộc lĩnh vực này sẽ có độ phù hợp r(u, v) cao hơn với người dùng u. 1.2 Các phương pháp khai phá dữ liệu được sử dụng 8 Bên cạnh các phương pháp IR, hệ thống khuyến nghị dựa trên nội dung còn sử dụng nhiều phương pháp học máy khác như: phân lớp Bayes, cây quyết định, mạng nowrron nhân tạo, ... Các phương pháp này khác với các phương pháp của IR ở chỗ nó dưa trên các mô hình học được từ dữ liệu nền tảng. Ví dụ, dựa trên tập các trang web đã được người dùng đánh giá là có nội dung "tốt" hoặc "xấu" có thể sử dụng phân lớp Bayes để phân loại các trang web chưa được đánh giá. Khuyến nghị dựa trên nội dung có những ưu điểm: i) Đầu tiên, nó không yêu cầu số lượng người sử dụng lớn để đạt được độ chính xác đề nghị hợp lý. ii) Ngoài ra, các mặt hàng mới có thể được khuyến nghị ngay dựa trên thuộc tính có sẵn. Tuy nhiên, nhược điểm của khuyến nghị dựa trên nội dung là khi thông tin mô tả đối tượng có chất lượng kém và bị lỗi. Trong một số trường hợp, những mô tả về nội dung rất khó để so sánh và rút ra gợi ý, chẳng hạn so sánh nội dung của các file video, audio,. . . Việc phân tích nội dung của các đối tượng sản phẩm để đưa ra các sản phẩm tương tự nhau, từ đó đưa ra các khuyến nghị cho người dùng vẫn chưa phản ánh đúng sở thích của người dùng đó với các sản phẩm. 1.2.2 Khuyến nghị lọc cộng tác (Collaborative Filtering Recomnendation System) Ý tưởng cơ bản của các hệ thống này là dựa vào các đánh giá của những người dùng quá khứ lên các sản phẩm, dịch vụ để dự đoán sự đánh giá của họ lên các sản phẩm, dịch vụ mà họ chưa đánh giá. Bài toán lọc cộng tác (hay đánh giá độ tương quan) dựa trên hành vi quá khứ của người dùng (trong việc đánh giá sản phẩm) để đưa ra dự đoán. Đầu vào của bài toán là ma trận thể hiện những hành vi quá khứ, gọi là ma trận Người dùng - Sản phẩm (ma trận U × V ) có hàng là người dùng, cột là sản phẩm, giá trị mỗi ô là đánh giá của người dùng lên sản phẩm đó. Đầu ra của bài toán là: đánh giá của người dùng lên những sản phẩm mà họ chưa đánh giá. Hệ thống khuyến nghị dựa trên các đánh giá này để xếp hạng các sản phẩm và gợi ý cho người dùng. Hệ thống khuyến nghị lọc cộng tác dự đoán độ phù hợp r(u, v) của một sản phẩm v với người dùng u dựa trên độ phù hợp r(ui , v) giữa người dùng ui và v, trong đó ui là người có cùng sở thích với u. Ví dụ, để gợi ý một bộ phim cho người dùng u, đầu tiên hệ thống cộng tác tìm những người dùng khác có cùng sở thích phim ảnh với u. Sau đó, những bộ phim được họ đánh giá cao sẽ được dùng để tư vấn cho u. Có nhiều hệ thống cộng tác đã được phát triển như: Youtube (video), Amazon (sách), . . . Các hệ thống này có thể chia thành hai loại: dựa trên kinh nghiệm (heuristic-based hay memory-based) và dựa trên mô hình (model-based). 1.2 Các phương pháp khai phá dữ liệu được sử dụng 1.2.3 9 Kết hợp các phương pháp (Hybrid): Các cách tiếp cận khác nhau có những ưu điểm và nhược điểm riêng. Do đó cần kết hợp các kỹ thuật khác nhau tận dụng ưu điểm và nhược điểm của từng cách tiếp cận nhằm có hệ thống khuyến nghị chính xác hơn. Một vài hệ thống khuyến nghị kết hợp cả phương pháp lọc cộng tác và lọc dựa trên nội dung nhằm tránh những hạn chế của cả hai phương pháp. Có thể phân thành bốn cách kết hợp như sau: Cài đặt hai phương pháp riêng rẽ rồi kết hợp dự đoán của chúng với nhau: Có hai kịch bản cho trường hợp này: - Cách 1: Kết hợp kết quả của cả hai phương pháp thành một kết quả chung duy nhất, sử dụng cách kết hợp tuyến tính (linear combination) hoặc thực hiện bỏ phiếu (voting scheme). - Cách 2: Tại mỗi thời điểm, chỉ chọn phương pháp cho kết quả tốt hơn (dựa trên một số độ đo chất lượng tư vấn nào đó). Ví dụ, hệ thống DailyLearner chọn phương pháp nào đưa ra gợi ý với độ chính xác (confidence) cao hơn. Tích hợp các đặc trưng của phương pháp dựa trên nội dung vào hệ thống cộng tác: Một số hệ thống lai (như Fab) chủ yếu dựa trên các kĩ thuật cộng tác nhưng vẫn duy trì hồ sơ về người dùng (theo dạng của mô hình dựa trên nội dung). Hồ sơ này được dùng để tính độ tương đồng giữa hai người dùng, nhờ đó giải quyết được trường hợp có quá ít sản phẩm chung được đánh giá bởi cả hai người. Một lợi ích khác là các gợi ý sẽ không chỉ giới hạn trong các sản phẩm được đánh giá cao bởi những người cùng sở thích (gián tiếp), mà còn cả với những sản phẩm có độ tương đồng cao với sở thích của chính người dùng đó (trực tiếp). Tích hợp các đặc trưng của phương pháp cộng tác vào hệ thống dựa trên nội dung: Hướng tiếp cận phổ biến nhất là dùng các kĩ thuật giảm số chiều trên tập hồ sơ của phương pháp dựa trên nội dung. Ví dụ, [15] sử dụng phân tích ngữ nghĩa ẩn (latent semantic analysis) để tạo ra hướng cộng tác (collaborative view) với tập hồ sơ người dùng (mỗi hồ sơ được biểu diễn bởi một vector từ khóa). Xây dựng mô hình hợp nhất, bao gồm các đặc trưng của cả hai phương pháp: Trong những năm gần đây đã có nhiều nghiên cứu về mô hình hợp nhất. [16] đề xuất kết hợp đặc trưng của cả hai phương pháp vào một bộ phân lớp dựa trên luật (rule-based classifier). Popescul và cộng sự trong [17] đưa ra phương pháp xác suất hợp nhất dựa trên phân tích xác suất ngữ nghĩa ẩn (probabilistic latent semantic analysis). [23] giới thiệu mô hình hồi quy Bayes sử dụng chuỗi Markov Monte Carlo để ước lượng tham số. Độ chính xác của hệ thống khuyến nghị kết hợp có thể được cải tiến bằng cách sử dụng các kĩ thuật dựa trên tri thức (knowledge-based) như case-based reasoning. Ví dụ, hệ thống Entrée dùng những tri thức về nhà hàng, thực phẩm (như: đồ biển không phải là thức ăn chay), ... để gợi ý những nhà hàng phù hợp với người dùng. Hạn chế chính của hệ thống dạng này là nó cần phải thu thập đủ tri thức, đây cũng là nút thắt cổ chai (bottle-neck) của rất nhiều hệ thống trí tuệ nhân tạo khác. Tuy nhiên, các hệ thống 1.2 Các phương pháp khai phá dữ liệu được sử dụng 10 khuyến nghị dựa trên tri thức hiện đang được phát triển trên các lĩnh vực mà miền tri thức của nó có thể biểu diễn ở dạng mà máy tính đọc được (như ontology). Ví dụ, hệ thống Quickstep và Foxtrot sử dụng ontology về chủ đề của các bài báo khoa học để gợi ý những bài báo phù hợp cho người dùng. Một bài báo như [9] đã thực hiện so sánh hiệu năng của hệ thống kết hợp với các hệ thống dựa trên nội dung và cộng tác thuần túy; từ đó cho thấy hệ thống kết hợp cho độ chính xác cao hơn.