Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI 1 Đỗ Thị Liên, 1Nguyễn Xuân Anh, 1Nguyễn Duy Phương, 1Từ Minh Phương 1 Học viện Công nghệ Bưu chính Viễn thông liendt@ptit.edu.vn, anhnx@ptit.edu.vn,phuongnd@ptit.edu.vn, phuongtm@ptit.edu.vn Tóm tắt - Hệ tư vấn (recommender systems) là hệ thống có khả năng cung cấp thông tin phù hợp và gỡ bỏ thông tin không phù hợp cho mỗi người dùng sử dụng các dịch vụ Internet. Hệ tư vấn được xây dựng dựa trên hai kỹ thuật lọc thông tin chính: Lọc cộng tác (collaborative filtering) và lọc nội dung (content-based filtering). Mỗi phương pháp khai thác những khía cạnh riêng liên quan đến đặc trưng nội dung hay thói quen sử dụng sản phẩm của người dùng trong quá khứ để dự đoán một danh sách ngắn gọn các sản phẩm phù hợp nhất đối với mỗi người dùng. Trong bài báo này, chúng tôi đề xuất một phương pháp hợp nhất giữa tư vấn cộng tác và tư vấn nội dung bằng mô hình đồ thị. Mô hình cho phép ta dịch chuyển bài toán tư vấn kết hợp về bài toán tư vấn cộng tác, sau đó xây dựng một độ tương tự mới trên đồ thị để xác định mức độ tương tự giữa các cặp người dùng và sản phẩm để sinh ra kết quả dự đoán. Kết quả thử nghiệm trên các bộ dữ liệu thực về phim cho thấy các phương pháp đề xuất cải thiện đáng kể chất lượng tư vấn. Từ khóa - Tư vấn cộng tác, tư vấn theo nội dung, hệ tư vấn lai, tư vấn dựa vào sản phẩm, tư vấn dựa vào người dùng. I. GIỚI THIỆU HỆ TƯ VẤN Người dùng sử dụng các dịch vụ Internet trực tuyến hiện nay luôn trong tình trạng quá tải thông tin. Để tiếp cận được thông tin hữu ích, người dùng thường phải xử lý, loại bỏ phần lớn thông tin không cần thiết. Hệ tư vấn (recommender systems) cung cấp một giải pháp nhằm giảm tải thông tin bằng cách dự đoán và cung cấp một danh sách ngắn các sản phẩm (trang web, bản tin, phim, video…) phù hợp cho mỗi người dùng. Trên thực tế, hệ tư vấn không chỉ hướng đến vấn đề giảm tải thông tin cho mỗi người dùng mà nó còn là yếu tố quyết định đến thành công của các hệ thống thương mại điện tử [4]. Bài toán tư vấn tổng quát có thể được phát biểu như sau. Cho tập hợp hữu hạn gồm N người dùng U = {u1, u2,…, uN}, P = {p1, p2,.., pM} là tập hữu hạn gồm M sản phẩm. Mỗi sản phẩm px∈P 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 quan hệ giữa tập người dùng U và tập sản phẩm P được biểu diễn thông qua ma trận đánh giá R={ rix: i = 1, 2, ..N; x = 1, 2,..M }. Giá trị rix thể hiện đánh giá của người dùng ui∈U cho một số sản phẩm px∈P. Thông thường giá trị rix nhận một giá trị thuộc miền F = { 1, 2,.., g} đượ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. Giá trị rix = φ được hiểu người dùng ui chưa đánh giá hoặc chưa bao giờ biết đến sản phẩm px. Ma trận đánh giá của các hệ thống tư vấn thực tế thường rất thưa. Mật độ các giá trị rix≠0 nhỏ hơn 1%, hầu hết các giá trị rix còn lại là φ [4]. Ma trận R chính là đầu vào của các hệ thống tư vấn cộng tác [1, 2, 3]. Để thuận tiện trong trình bày, ta viết px∈P ngắn gọn là x∈P; và ui∈U là i∈U. Các ký tự i, j luôn được dùng để chỉ tập người dùng trong các mục tiếp theo của bài báo. Mỗi sản phẩm x∈P được biểu diễn thông qua |C| đặc trưng nội dung C = { c1, c2,.., c|C|}. Các đặc trưng cs∈C nhận được từ các phương pháp trích chọn đặc trưng (feature selection) trong lĩnh vực truy vấn thông tin. Ví dụ x∈P là một phim thì các đặc trưng nội dung biểu diễn một phim có thể là C={thể loại phim, nước sản xuất, hãng phim, diễn viên, đạo diễn…}. Gọi wx = {wx1, wx2,.., wx|C| } là vector trọng số các giá trị đặc trưng nội dung sản phẩm x∈P . Khi đó, ma trận trọng số W ={wxs: x =1, 2, .., M; s =1, 2, .., |C|} chính là đầu vào của các hệ thống tư vấn theo nội dung sản phẩm [2, 3, 17]. Để thuận tiện trong trình bày, ta viết cs∈C ngắn gọn là s∈C.Ký tự s luôn được dùng để chỉ tập đặc trưng nội dung sản phẩm trong các mục tiếp theo của bài báo. Mỗi người dùng x∈P được biểu diễn thông qua |T| đặc trưng nội dung T = {t1, t2,.., t|T|}. Các đặc trưng tq∈T thông thường là thông tin cá nhân của mỗi người dùng (Demographic Information). Ví dụ i∈U là một người dùng thì các đặc trưng nội dung biểu diễn người dùng i có thể là T={giới tính, độ tuổi, nghề nghiệp, trình độ,…}. Gọi vi = {vi1, vi2,.., vi|T|} là vector trọng số biểu diễn các giá trị đặc trưng nội dung người dùng i∈U. Khi đó, ma trận trọng số V ={viq : i = 1, 2, .., N;q = 1, 2, .., |T| } chính là đầu vào của các hệ thống tư vấn theo nội dung thông tin người dùng [3, 13]. Để thuận tiện trong trình bày, ta viết tq∈T ngắn gọn là q∈T. Ký tự q luôn được dùng để chỉ tập đặc trưng nội dung người dùng trong các mục tiếp theo của bài báo. Tiếp đến ta ký hiệu, Pi⊆P là tập các sản phẩm x∈P được đánh giá bởi người dùng i∈U và Ux⊆U là tập các người dùng i∈U đã đánh giá sản phẩm x∈P. Với một người dùng cần được tư vấn i∈U (đượ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), nhiệm vụ của các phương pháp tư vấn là gợi ý K sản phẩm x∈(P\Pi) phù hợp nhất đối với người dùng i. Có nhiều đề xuất khác nhau để giải quyết bài toán tư vấn. Hệ tư vấn theo nội dung xây dựng phương pháp dự đoán dựa trên ma trận trọng số các đặc trưng nội dung sản phẩm W={wxs} hoặc ma trận trọng số các đặc trưng nội dung Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương 431 người dùng V ={viq} [3, 13, 17]. Hệ tư vấn cộng tác đưa ra phương pháp dự đoán dựa trên ma trận đánh giá R={rix} [1, 2, 4]. Hệ tư vấn lai đưa ra phương pháp dự đoán dựa trên cả 3 ma trận R, W và V[3, 9]. II. MỘT SỐ NGHIÊN CỨU LIÊN QUAN Hiệu quả của phương pháp tư vấn lai đã được khẳng định trong nhiều nghiên cứu khác nhau [2, 8]. Hướng tiếp cận phổ biến nhất thường được sử dụng là phương pháp tổ hợp tuyến tính giữa lọc cộng tác và lọc nội dung. Trong hướng tiếp cận này, các tác giả tiến hành xây dựng hai phương pháp lọc cộng tác và lọc nội dung độc lập nhau, sau đó tổ hợp tuyến tính kết quả dự đoán của cả hai hoặc lựa chọn ứng viên tốt nhất từ một trong hai phương pháp [17]. Hướng tiếp cận thứ hai xem xét vấn đề tư vấn lai bằng cách thêm các đặc trưng của lọc nội dung vào lọc cộng tác. Phương pháp được thực hiện bằng cách xây dựng một thủ tục kết hợp dữ liệu để tạo nên dữ liệu đầu vào tổng hợp giữa các giá trị đánh giá của lọc cộng tác và các đặc trưng nội dung. Pazzani [13] đề xuất phương pháp biểu diễn hồ sơ sản phẩm bằng một vector trọng số các đặc trưng nội dung người dùng. Dựa trên biểu diễn này, phương pháp dự đoán được Pazzani thực hiện bằng các kỹ thuật lọc cộng tác thuần túy. Hướng tiếp cận thứ ba xem xét bài toán tư vấn lai bằng cách thêm các đặc trưng của lọc cộng tác vào lọc nội dung. Theo phương pháp này, các đặc trưng nội dung sản phẩm đóng vai trò trung tâm và xem xét đánh giá người dùng của lọc cộng tác như các giá trị đặc trưng giả định để thêm vào quá trình dự đoán [17, 18]. Hướng tiếp cận cuối cùng được cộng đồng quan tâm nghiên cứu là hợp nhất giữa lọc cộng tác và lọc nội dung dựa trên các kỹ thuật học máy. Basu [19] đề xuất việc xây dựng tập các giá trị đặc trưng đại diện cho cả lọc cộng tác và lọc nội dung. Phương pháp dự đoán được tiến hành dựa trên việc xây dựng tập luật suy diễn các giá trị đặc trưng. Popescul [20] đề xuất mô hình phân tích ngữ nghĩa ẩn để hợp nhất giữa lọc cộng tác và lọc nội dung. Balisico và Hofman [21] sử dụng hàm nhân để kết hợp mức độ tương tự từ người dùng đến người dùng, sản phẩm đến sản phẩm, sau đó áp dụng máy vector hỗ trợ để sinh ra dự đoán. Crammer và Singer [22] xem xét bài toán tư vấn lai như việc xếp hạng các sản phẩm bằng việc bổ sung các đặc trưng nội dung sản phẩm. Liên quan đến mô hình đồ thị, nhiều đề xuất khác nhau đã được đưa ra giải quyết bài toán tư vấn. Aggarwal [23] biểu diễn mối quan hệ giữa các cặp người dùng như một đồ thị có hướng, trong đó mỗi cạnh được thiết lập phản ánh mức độ tương tự giữa hai người dùng. Phương pháp dự đoán được thực hiện bằng cách tính toán trọng số đường đi ngắn nhất giữa các cặp người dùng. Lien [7] đề xuất xây dựng độ đo tương tự giữa các cặp người dùng hoặc sản phẩm bằng mô hình đồ thị hai phía có trọng số. Mức độ tương tự giữa các cặp người dùng được thực hiện bằng cách ước lượng tổng trọng số của tất cả các đường đi từ đỉnh người dùng đến đỉnh người dùng, mức độ tương tự giữa các cặp sản phẩm được thực hiện bằng cách ước lượng tổng trọng số của tất cả các đường đi từ sản phẩm dùng đến đỉnh sản phẩm. Phuong [6] đề xuất phương pháp kết hợp giữa lọc cộng tác và lọc nội dung bằng cách xây dựng mối liên hệ giữa người dùng và tập đặc trưng nội dung sản phẩm. Phương pháp dự đoán được thực hiện bằng cách tổ hợp tuyến tính trọng số các đường đi từ đỉnh người dùng đến đỉnh sản phẩm. Sản phẩm nào có tổng trọng số các đường đi lớn nhất đến nó chính là đích của quá trình dự đoán. Trong bài báo này, chúng tôi đề xuất một mô hình hợp nhất giữa lọc cộng tác và lọc nội dung dựa trên biểu diễn đồ thị. Mô hình được xây dựng bằng cách lấy lọc cộng tác làm trung tâm, xây dựng hồ sơ người dùng dựa trên ma trận đánh giá để thiết lập nên mối quan hệ trực tiếp giữa tập người dùng với tập đặc trưng nội dung sản phẩm. Tiếp đến, chúng tôi tiến hành xây dựng hồ sơ sản phẩm cũng dựa trên ma trận đánh giá để thiết lập nên mối quan hệ trực tiếp giữa tập sản phẩm và tập đặc trưng nội dung người dùng. Dựa trên mối quan hệ giữa tập người dùng với tập đặc trưng nội dung sản phẩm và mối quan hệ giữa tập sản phẩm với tập đặc trưng nội dung người dùng, chúng tôi tìm cách xác định được mối quan hệ tiềm ẩn giữa tập đặc trưng sản phẩm và tập đặc trưng người dùng. Bằng cách này, chúng tôi thu gọn mô hình tư vấn kết hợp tổng quát thành mô hình tư vấn cộng tác chuẩn. Về nguyên tắc, sau khi thu được mô hình tư vấn cộng tác chuẩn ta có thể triển khai bất kỳ một phương pháp lọc cộng tác nào đã được đề xuất trước đây. Tuy nhiên để khai thác được thế mạnh của đồ thị, chúng tôi xây dựng một độ tương tự dựa trên đồ thị bằng cách ước lượng mức độ tương tự giữa các cặp người dùng dựa trên tổng trọng số các đường đi từ đỉnh người dùng đến đỉnh người dùng, mức độ tương tự giữa các cặp sản phẩm dựa trên tổng trọng số các đường đi từ đỉnh sản phẩm đến đỉnh sản phẩm. Bằng cách này ta tận dụng được các thuật toán tìm kiếm hiệu quả đã được triển khai trên đồ thị. Để tập trung trình bày phương pháp đề xuất, mục tiếp theo chúng tôi trình bày bày phương pháp dịch chuyển bài toán tư vấn kết hợp về bài toán lọc cộng tác. Mục 4 trình bày về các phương pháp tư vấn lai dựa trên đồ thị. Mục 5 trình bày phương pháp thử nghiệm và so sánh. Mục cuối cùng là kết luận và hướng phát triển tiếp theo của bài báo. III. DỊCH CHUYỂN BÀI TOÁN TƯ VẤN KẾT HỢP VỀ BÀI TOÁN LỌC CỘNG TÁC Như đã giới thiệu ở trên, bài toán tư vấn kết hợp thực hiện dự đoán dựa trên tập đánh giá của người dùng cho các sản phẩm, cùng với tập đặc trưng nội dung sản phẩm và đặc trưng người dùng. Trong mục này, chúng tôi đề xuất phương pháp dịch chuyển bài toán tư vấn kết hợp về bài toán tư vấn cộng tác thuần túy bằng cách xây dựng hồ sơ người dùng và hồ sơ sản phẩm của dựa vào đánh giá tự nhiên của người dùng đối với các sản phẩm trong quá khứ. Trên cơ sở hồ sơ người dùng và hồ sơ sản phẩm đã được xây dựng, chúng tôi tìm cách xác định mối quan hệ tiềm ẩm giữa tập đặc trưng nội dung người dùng và tập đặc trưng nội dung sản phẩm để thu được mô hình giống với mô hình MỘ ỘT MÔ HÌNH ĐỒ Ồ THỊ CHO HỆ TƯ T VẤN LAI 432 4 bài b toán tư vấnn cộng tác. Đểể diễn giải tínnh đúng đắn củ ủa phương ph háp đề xuất, chhúng tôi sử dụụng mô hình đồ đ thị thực hiện h cho bài tooán tư vấn kết hợp. 3.1. 3 Biểu diễn n đồ thị cho lọọc kết hợp Không hạạn chế tính tổnng quát của bàài toán phát biểu trong Mục 1, ta giả thiếtt giá trị đánh ggiá của người dùng i∈U đối đ với sản phhẩm x∈P đượcc xác định theeo công thức (1). ( Mỗi sản phẩm p x∈P đượ ược biểu diễn tthông qua |C | đặc trưng nội n dung C = {c1, c2,..,c|C|} được xác địnnh theo công thức (2). Mỗi người dùng i∈ U được biểuu diễn thông qua q |T| đặc trrưng nội dungg T = {t1, t2,..,, t|T|} được xácc định theo công thức (3). ế ườ ù ẩ ở ứ độ ∈ đá á ả (1) ế ườ ù ư đá á ặ ư ế đế ả ẩ 1 0 ế 1 0 ế ả ế ườ ế ù ẩ ườ ả ù ô ẩ ô ó đặ ó đặ ư ư ó đặ ó đặ ư ư ế ế ế 0 ∶ 0∶ 0∶ (2) (3) Hệ tư vấnn với ma trận đđánh giá R = {{rix:i=1, 2,..,N N; x=1, 2,..,M}}, ma trận đặc trưng nội dunng sản phẩmC C={cxs:x=1, 2, 2 .., M; s =1, 2, ..,|C|}, maa trận đặc trưnng nội dung người n dùng T = {tiq:i=1, 2, .., N; q =1, 22, ..,|T|}có thể ể biểu diễn dưới d dạng đồ thị t trọng số G =(Ω, E), tronng đó Ω là tập đỉnh và E là tập cạnh. Tập đỉnh Ω của đđồ thị được xác c định theo công c thức (4) chính c là hợp ccủa tập người dùng U, tập sản s phẩm P, tậập đặc trưng nnội dung sản pphẩm C và tập p đặc trưng nội n dung ngườ ời dùng T. Tậpp cạnh E của đđồ thị bao gồm m 3 loại cạnh: cạnh (i, x) nnối giữa đỉnh nngười dùng vớ ới đỉnh sản phẩm, p cạnh (xx, s) nối đỉnh ssản phẩm với đặc trưng nội dung sản ph hẩm, cạnh (i, qq) nối giữa đỉỉnh người dùn ng với đỉnh đặc đ trưng nội dung d của ngườ ời dùng. , , , Bảng 1. Ma trrận đánh giá R u1 u2 u3 p1 5 0 0 p2 0 4 5 p3 4 0 4 , , , . . . (5) p4 0 3 0 Bảngg 2. Ma trận đặcc trưng sản phẩẩm C c1 1 1 1 0 p1 p2 p3 p4 c2 0 1 0 1 c3 1 0 1 1 Bảng 3. Ma trận đặc trưng người dùùng T u1 u2 u3 t1 1 1 0 t2 0 0 1 t3 0 1 0 t4 1 0 1 Hìn nh 1. Đồ thị biểểu diễn cho hệ ttư vấn Ví dụ vớii hệ gồm 3 nggười dùng U = {u1, u2, u3},, 4 sản phẩm P = {p1, p2, p 3, p4}. Trongg đó, ma trận đánh đ giá R được đ cho trongg Bảng 1; Maa trận đặc trưnng nội dung sản phẩm C đư ược cho trongg Bảng 2; Ma trận đặc trưng g nội dung người n dùng T được cho tronng Bảng 3. Khhi đó, đồ thị biểu b diễn cho bài b toán tư vấấn tổng quát đđược biểu diễn n như Hình 1. 1 Đồ thị đượcc biểu diễn thàành ba đồ thị con hai phía (bipartie ( praph h). Đồ thị conn hai phía ở giiữa biểu diễn quan điểm của c người dùnng đối với các sản phẩm thôông qua ma trậận đánh giá R =(rix). Các cạạnh nối giữa đđỉnh người dùn ng i∈U với đỉnh đ sản phẩm m x∈P được đáánh trọng số llà rix. Đồ thị con c hai phía trrên cùng biểuu diễn mối quaan hệ giữa sản n phẩm với tập đặc trưng nội n dung sản pphẩm thông qqua ma trận C= =(cxs). Các cạn nh nối giữa đỉỉnh sản phẩm x∈P với đỉnh h đặc trưng nội n dung sản phẩm p s∈C đượ ợc đánh trọng số là 1. Đồ th hị con hai phíaa dưới cùng biiểu diễn mối qquan hệ giữa người n dùng với v tập đặc trư ưng nội dung nngười dùng thhông qua ma trrận T=(tiq). Cáác cạnh nối giữ ữa đỉnh ngườii dùng i∈U vớ ới đỉnh đặc trrưng nội dungg người dùng q∈T cũng đượ ợc đánh trọng số là 1. Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương 433 Dựa trên biểu diễn đồ thị, phương pháp tư vấn cộng tác được thực hiện dựa trên các cạnh nối giữa đỉnh người dùng i∈U và đỉnh sản phẩm x∈P với trọng số rix [5]. Phương pháp tư vấn theo nội dung sản phẩm được thực hiện trên các cạnh nối giữa đỉnh sản phẩm x∈P và đỉnh đặc trưng nội dung sản phẩm s∈C [7]. Phương pháp tư vấn theo nội dung người dùng được thực hiện trên các cạnh nối giữa đỉnh người dùng i∈U và đỉnh đặc trưng nội dung người dùng t∈T [17]. Phương pháp tư vấn kết hợp được thực hiện dựa trên cả ba loại cạnh (i , x), (x, s), và (i, q) [9, 10]. 3.2. Xây dựng hồ sơ người dùng dựa trên ma trận đánh giá Phương pháp tư vấn theo nội dung thực hiện dự đoán các sản phẩm có nội dung thông tin hay mô tả hàng hóa tương tự với những sản phẩm mà người dùng đã từng sử dụng hoặc truy nhập trong quá khứ. Chất lượng của các phương pháp tư vấn theo nội dung phụ thuộc vào phương pháp trích chọn đặc trưng để biểu diễn vector đặc trưng nội dung sản phẩm và vector hồ sơ sử dụng sản phẩm của người dùng. Hạn chế lớn nhất của phương pháp trích chọn đặc trưng hiện nay là nhiều đặc trưng nội dung không đóng góp vào việc xác định mức độ tương tự giữa vector hồ sơ người dùng và vector đặc trưng sản phẩm vẫn được tham gia quá trình tính toán [3, 5]. Để hạn chế điều này, chúng tôi đề xuất phương pháp xây dựng hồ sơ sử dụng sản phẩm của người dùng thông qua các giá trị đánh giá của hệ tư vấn cộng tác, sau đó thiết lập mối quan hệ trực tiếp giữa người dùng và từng đặc trưng sản phẩm để nâng cao hiệu quả tư vấn. Phương pháp được tiến hành như sau. Để xây dựng được hồ sơ sử dụng sản phẩm của người dùng ta cần thực hiện hai nhiệm vụ: xác định được tập các sản phẩm người dùng đã từng truy cập hay sử dụng trong quá khứ và ước lượng trọng số mỗi đặc trưng nội dung sản phẩm trong hồ sơ người dùng [2, 17]. Gọi Pi⊆P được xác định theo công thức (6) là tập sản phẩm người dùng i∈U đã đánh giá các sản phẩm x∈P. Khi đó, Pi chính là tập sản phẩm người dùng đã từng truy cập trong quá khứ được các phương pháp tư vấn theo nội dung sử dụng trong khi xây dựng hồ sơ người dùng. Vấn đề còn lại là làm thế nào ta ước lượng được trọng số mỗi đặc trưng s∈C đối với mỗi hồ sơ người dùng i∈U. ∈ | 0 ∈ , ∈ (6) Gọi ListItem(i, s) là tập các sản phẩm x∈Pi chứa đựng đặc trưng s∈C được xác định theo công thức (7). Khi đó, |ListItem(i , s)| chính là số lần người dùng i∈U sử dụng các sản phẩm x∈P chứa đựng đặc trưng s∈C trong quá khứ. , ∈ | 0 ∈ , ∈ , ∈ (7) Dựa trên Pi và ListItem( i, s) các phương pháp tư vấn theo nội dung ước lượng được trọng số wis phản ánh mức độ quan trọng của đặc trưng nội dung s đối với người dùng i. Phương pháp phổ dụng nhất thường được sử dụng trong xây dựng hồ sơ người dùng là kỹ thuật tf-idf [17]. Giá trị wis là một số thực trải đều trong khoảng [0,1]. Tuy nhiên, trong khi quan sát bài toán tư vấn cộng tác chúng tôi nhận thấy bản thân nó đã tồn tại một phép đánh giá tự nhiên của người dùng đối với sản phẩm thông qua giá trị đánh giá rix. Giá trị rix phản ánh mức độ ưa thích của người dùng sau khi đã sử dụng sản phẩm và đưa ra quan điểm của mình đối với sản phẩm. Ví dụ với hệ tư vấn phim [18], giá trị rix = 1, 2, 3, 4, 5 được hiểu theo các mức quan điểm “rất tồi”, “tồi”, “bình thường”, “hay”, “rất hay”. Chính vì lý do đó, chúng tôi mong muốn có được một phương pháp trích chọn đặc trưng có cùng mức độ đánh giá tự nhiên của rix. Để thực hiện ý tưởng nêu trên, chúng tôi thực hiện quan sát trên tập ListItem(i, s). Nếu giá trị |ListItem(i, s)| vượt quá một ngưỡng θ nào đó thì trọng số đặc trưng nội dung sản phẩm s∈C đối với người dùng i∈U là wis được tính bằng trung bình cộng của tất cả các giá trị đánh giá. Trường hợp |ListItem(i, s)| có giá trị bé hơn θ, giá trị wis được tính bằng tổng của tất cả các giá trị đánh giá chia cho θ. Trong thử nghiệm, chúng tôi tính toán được số lượng trung bình của tất cả người dùng i∈U đã đánh giá các sản phẩm x∈P, sau đó chọn θ tương đương với 2/3 số lượng trung bình các đánh giá của tập người dùng i∈U đã đánh giá sản phẩm x∈P chứa đựng đặc trưng s∈C. Bằng cách này ta có thể hạn chế được một số đặc trưng nội dung ít được người dùng quan tâm nhưng vẫn được đánh giá với trọng số cao. | ∑ ∈ , | ∑ , ∈ ế , ế | | , | , | (8) Giá trị wis được ước lượng theo (8) phản ánh quan điểm của người dùng i∈U đối với các đặc trưng nội dung sản phẩm s∈C cũng chính là hồ sơ người dùng i∈U đã sử dụng các đặc trưng nội dung s∈C trong quá khứ. Dễ dàng nhận thấy wis∈F, trong đó F = { 1, 2, .., g}. Chính vì vậy, ta có thể xem mỗi đặc trưng nội dung sản phẩm đóng vai trò như một sản phẩm phụ bổ sung vào tập sản phẩm. Dựa trên nhận xét này, chúng tôi mở rộng đồ thị hai phía của bài toán tư vấn cộng tác nguyên thủy (đồ thị con ở giữa) bằng cách giữ nguyên tập đỉnh ở phía người dùng U, tập đỉnh phía sản phẩm được mở rộng là P∪C. Liên kết giữa đỉnh người dùng i∈U và đỉnh sản phẩm x∈P được thiết lập nếu rix≠ 0. Liên kết giữa đỉnh người dùng i∈U và đỉnh đặc trưng sản phẩm s∈C được thiết lập nếu wis≠ 0. Ma trận đánh giá mở rộng được xác định theo công thức (9). ế ∈ ế à ∈ à 0 0 (9) MỘ ỘT MÔ HÌNH ĐỒ Ồ THỊ CHO HỆ TƯ T VẤN LAI 434 4 Ví dụ với đồ thị biểu diiễn hệ tư vấn kết hợp được cho trong Hìn nh 1, chọn θ = 2 ta sẽ tính toán được ma a trận đánh giá g mở rộng trrong Bảng 4 vvà đồ thị tư vvấn cộng tác mở m rộng đượcc thể hiện như ư Hình 2. Cácc cạnh màu đỏ ỏ là những cạnh c mới đượcc bổ sung vào đồ thị hai phíía của lọc cộng g tác. B Bảng 4. Ma trậận đánh giá mở rộng R u1 u2 u3 p1 5 0 0 p2 0 4 5 p3 4 0 4 p4 0 3 0 c1 4 2 4 c2 0 3 2 c3 4 1 2 Hình 2. M Mở rộng theo pphía sản phẩm 3.3. 3 Xây dựngg hồ sơ sản ph hẩm dựa trên n ma trận đán nh giá Tương tự như hồ sơ ngư ười dùng, hồ sơ sản phẩm lưu l trữ lại vết tích các đặc ttrưng nội dungg người dùng đã từng sử dụng d sản phẩm m. Để xây dựnng được hồ sơ ơ sản phẩm taa cần thực hiệện hai nhiệm vvụ: xác định đđược tập ngườ ời dùng đã từ ừng sử dụng sản phẩm quáá khứ và ước lượng trọng số mỗi đặc trư ưng nội dung nngười dùng trrong hồ sơ sản n phẩm [3, 13]. 1 Gọi Ux⊆U được xác đinnh theo công thức (10) là tậập người dùng g i∈U đã sử ddụng sản phẩm m x∈P. Khi đó ó, Ux chính là tập người dùùng cần được lưu lại các giáá trị đặc trưng g nội dung tron ng hồ sơ sản pphẩm. Vấn đề còn lại là làm m thế nào ta ước ư lượng đượ ợc trọng số mỗỗi đặc trưng q∈T đối với mỗ ỗi hồ sơ sản phẩm x∈P. ∈ | 0 ∈ , ∈ 0 ∈ , (10) Gọi ListU User (x, q) làà tập người ddùng i∈Uxcó đặc trưng q∈T được xác định theo côông thức (11). Khi đó, |L ListUser(x , q)| q chính là sốố lần sản phẩm m x∈P được tập t người dùn ng i∈U có đặặc trưng nội ddung q∈T sử dụng d trong quá q khứ. , ∈ | ∈ , ∈ , | (11) ư vấn theo nội dung người ddùng ước lượnng được trọng số txq phản Dựa trên Ux và ListUserr( x, q) các phhương pháp tư ánh á mức độ quuan trọng củaa đặc trưng nộội dung q đối với sản phẩm m x. Giống như ư người dùng,, bản thân các c sản phẩm cũng c đã tồn tạii một phép đáánh giá tự nhiêên của tập ngư ười dùng đối với v sản phẩm tthông qua giáá trị đánh giá rix. Do vậy, chúng c tôi đề xuất x phương phháp trích chọnn đặc trưng nộ ội dung người dùng có cùngg mức độ đánhh giá với giá trị đánh giá rix. Để thực hiiện điều này, cchúng tôi tiếnn hành quan sáát trên tập ListtUser(x, q). N Nếu giá trị |ListtItem(i, s)| vượt quá một ngưỡng n θ nào đó thì trọng số đặc trưng nnội dung người dùng q∈T đối với sản pphẩm x∈P là vxq được tính bằng b trung bình b cộng của tất cả các giáá trị đánh giá. Trường hợp |L ListUser(x, q)| có giá trị bé hơn θ, giá trịị vxq được tính h bằng tổng của c tất cả các giá trị đánh ggiá chia cho θ. Trong thử nghiệm, n chúng g tôi tính toánn được số lượợng trung bình h của tất cả sản s phẩm x∈P được đánh ggiá bởi người ddùng i∈U, sau u đó chọn θ tư ương đương vớới 2/3 số lượnng người dùng g i∈U chứa đựng đ đặc trưngg q∈T đã sử ddụng sản phẩm m x∈P. Bằng cách c này ta có thể hạn chế đđược một số đđặc trưng nội người n dùng ítt quan tâm đếnn sản phẩm nhhưng vẫn đượ ợc đánh giá với trọng số cao. | , ∑∈ | ∑∈ , ế , ế | | , | (12) ợng theo (12) biểu diễn hồ sơ sản phẩm x∈P đã được ttập những ngư ười dùng i∈U chứa đựng Giá trị vxq được ước lượ đặc đ trưng q∈T sử dụng. Dễ dàng nhận thấấy vxq∈F, tron ng đó F = { 1, 2, .., g}. Chínnh vì lý do nàyy, ta có thể xe em mỗi đặc trưng nội dunng người dùngg đóng vai tròò như một người dùng phụ ụ bổ sung vàoo tập người dù dùng. Dựa trên n nhận xét này, n chúng tôii mở rộng đồ thị hai phía ccủa bài toán tư t vấn cộng táác đã được m mở rộng trong Mục 2.2 bằng cách giữ nguyên n tập đỉỉnh ở phía sảnn phẩm là P∪ C và mở rộn ng phía ngườ ời dùng thành U∪T. Liên kkết giữa đỉnh sản phẩm x∈P và đỉnh người n dùng i∈U được thiếết lập nếu rix≠ 0. Liên kết giữa g đỉnh sảnn phẩm x∈P vvà đỉnh đặc trưng người dùng d q∈T đượ ợc thiết lập nnếu vxq≠ 0. M a trận đánh giá g mở rộng ghi g lại trọng ssố các cạnh (xx, i) và (x, q)) được xác định đ theo công thức (13). ế ế ế ∈ , ∈ ∈ , ∈ à à ∈ , ∈ à 0 0 0 (13) Ví dụ với đồ thị biểu diiễn hệ tư vấn kết hợp được cho trong Hìn nh 1, chọn θ = 2 ta sẽ tính toán được ma a trận đánh giá g mở rộng trrong Bảng 5 vvà đồ thị tư vấấn cộng tác mở m rộng được thể t hiện như H Hình 3. Các ccạnh màu xanh là những cạnh c mới đượcc bổ sung vào đồ thị hai phíía của lọc cộng g tác. Đỗ Đ Thị Liên, Nguuyễn Xuân Anh, N Nguyễn Duy Phươ ơng, Từ Minh Phư ương 435 Bảng 5. Ma trậận đánh giá mở rộng R u1 u2 u3 t1 t2 t3 t4 p1 5 0 0 2 0 0 2 p2 0 4 5 2 0 2 2 p3 4 0 4 2 2 0 4 p4 0 3 0 1 0 1 0 c1 4 2 4 c2 0 3 2 c3 4 1 2 Hình 3. Mở rộng theo phíaa người dùng 3.4. 3 Xây dựngg mối liên hệ giữa đặc trưn ng người dùn ng và đặc trưn ng sản phẩm Hồ sơ ngư ười dùng đượcc xác định theeo (8), hồ sơ sản s phẩm đượ ợc xác định theeo (12) được thực hiện dựa a trên đánh giá g tự nhiên củủa người dùngg đối với sản phẩm và thói quen sử dụng g sản phẩm củủa người dùngg. Rõ ràng, bả ản thân tập đặc đ trưng nội dung d người dùùng và tập đặcc trưng nội du ung sản phẩm cũng tồn tại m một mối quan hệ tự nhiên nào n đó giữa hồ h sơ người dùùng và hồ sơ ssản phẩm. Ví dụ tại sao trẻ em thích xem m phim hoạt hhình, nữ tuổi teeen thích xem m phim tình cảm, c nam tuổii teen thích xeem phim hànhh động…? Chúng tôi cho rằằng khai thác được mối quaan hệ tiềm ẩn n kể trên sẽ cải c thiện đáng kể chất lượngg dự đoán các sản phẩm phù ù hợp với mỗi người dùng. Để xác địnnh mối liên hệệ tiềm ẩn giữaa đặc trưng q∈T với đặc trư ưng s∈C, chúnng tôi xây dựnng hai kiểu qua an sát khác nhau. n Kiểu quan sát thứ nhấất được tiến hàành từ hồ sơ người n dùng đếến các đặc trư ưng nội dung ssản phẩm. Kiể ểu quan sát th hứ hai được thực t hiện ngư ược lại từ hồ ssơ sản phẩm đến đ các đặc trư ưng người dùùng. Vì cả hai kiểu quan sát chỉ nhằm mục m đính xác định mối quan an hệ tiềm ẩn ggiữa cặp đặc trưng t q∈T vớ ới đặc trưng s∈ C nên chúngg tôi tổ hợp kế ết quả giữa hai h kiểu quán sát s để thu đượ ợc kết quả cuốối cùng. Phươn ng pháp cụ thểể được tiến hànnh như sau. Quan sát từ hồ sơ ngư ười dùng đến các đặc trưng g nội dung sả ản phẩm ung q∈T đượcc xác định the o công thức ( 14). Gọi UserrAttr(i,s) là Gọi Uq là tập người dùnng i∈U có đặcc trưng nội du tập người dùng i∈U có đặcc trưng q∈T đđã đánh giá cáác sản phẩm x∈P chứa đựnng đặc trưng s ∈C được xác c định theo công c thức (15)). Khi đó, mốii liên hệ giữa đặc trưng q∈T và đặc trưn ng s∈C được ư ước lượng theeo công thức (16). Trong đó, đ wis là hồ sơ ơ người dùng i∈U được xácc định theo (8)). ∈ | ∑∈ , | ∑∈ , | , 0 , (14) ∈ | ế | 0 ế | (15) , , | (16) ượng theo (166) phản ánh mức m độ ảnh hư ường của đặc ttrưng s∈C lênn tập người dù ùng có đặc Giá trị aqss được ước lư g đặc trưng trrưng q∈T. Nếếu số lượng tậập người dùngg i∈U có đặc trưng q∈T đãã đánh giá cácc sản phẩm x∈P chứa đựng s∈C vượt quá ngưỡng θ thìì aqs được tínhh bằng giá trị trung bình củaa trọng số cácc đặc trưng s ttrong hồ sơ ng gười dùng. Trong T trường hợp khác, aqss được tính tổnng trọng số cáác đặc trưng s trong hồ sơ người dùng nnhân với 1/θ. Bằng cách này n chúng ta có c thể hạn chhế được các đặc trưng của người dùng hoặc h sản phẩm m ít được ngư ười dùng sử dụ ụng nhưng được đ đánh giá với trọng số ccao. n dùng Quan sát từ hồ sơ sản phẩm đến cáác đặc trưng người m x∈P có đặc trưng nội dun ng s∈C được xác x định theo công thức (17). Gọi ItemA Attr(q, s) là Gọi Ps là tập sản phẩm tập sản phẩm có đặc trưng s∈C đã đượcc đánh giá bởii tập người dù ùng i∈U chứaa đựng đặc trư ưng q∈T đượ ợc xác định th heo công thứcc (18). Khi đóó, mức độ phùù hợp của tập sản phẩm có đặc đ trưng s đốối với tập ngư ười dùng i∈U chứa đựng đặc đ trưng q theeo công thức ((18). Trong đóó, vxq là hồ sơ sản phẩm x∈P được xác địnnh theo (12). ∈ | , 0 (17) ∈ | 0 (18) MỘ ỘT MÔ HÌNH ĐỒ Ồ THỊ CHO HỆ TƯ T VẤN LAI 436 4 | ∑ ∈ , | ∑ , ∈ ế | , , ế | , | (19) Giá trị bqss được ước lư ượng theo (199) phản ánh mức m độ ảnh hư ưởng của đặcc trưng q∈T lêên tập sản ph hẩm có đặc trrưng s∈C. Nếếu số lượng sảản phẩm x∈P có đặc trưng g s∈C đã đánh h giá các sản pphẩm i∈U chhứa đựng đặc trưng q∈T vượt v quá ngưỡ ỡng θ thì bqs đđược tính bằngg giá trị trung bình của trọn ng số các đặc trưng q trongg hồ sơ sản ph hẩm. Trong trrường hợp khhác, bqs được tính tổng trọnng số các đặcc trưng q trong hồ sơ ngườời dùng nhân với 1/θ. Bằng g cách này chúng c ta có thhể hạn chế được các đặc trư ưng của ngườ ời dùng hoặc sản s phẩm ít đư ược người dùn ùng sử dụng nh hưng được đánh đ giá với trrọng số cao. Tổng hợp p giữa các kiểểu quan sát Như đã trìình bày ở trênn, giá trị aqs đư ược xác định theo (16) và bqs được xác đđịnh theo (19) đều phản ánh h thói quen tự ự nhiên sử dụụng sản phẩm ccủa tập người dùng có đặc trưng t q đối vớ ới tập sản phẩm m có đặc trưngg s. Điểm khá ác biệt duy nhất n giữa aqs và v bqs là kiểu qquan sát dựa vvào hồ sơ ngườ ời dùng hay hồ ồ sơ sản phẩm m. Để dung hòòa giữa hai kiểu quan sát, chúng c tôi chọnn giá trị trungg bình giữa aqss và bqs theo công c thức (20)). Trong đó, ggiá trị dqs chỉ đđược thiết lập khi và chỉ khi k aqs và bqs có c giá trị khác 0. Điều này ccó nghĩa, mối quan hệ giữa đặc trưng s∈C và đặc trưngg q∈T được th hiết lập khi và v chỉ khi các sản phẩm có đặc trưng s thhực sự được nh hiều người dù ùng quan tâm vvà ngược lại nnhiều người dù ùng có đặc trrưng q thực sự ự quan tâm đếến các sản phẩẩm có đặc trưn ng s. Điều này y là hoàn toànn phù hợp với tâm lý chung của người sử s dụng sản phhẩm. ế 0 á ườ ư 0 à 0 ợ á (20) mối liên hệ giiữa tập đặc trư ưng người dùn ng và tập đặc ttrưng sản phẩm m, chúng tôi mở m rộng đồ Sau khi xáác định được m th hị hai phía củủa bài toán tư vvấn cộng tác đđã được trình bày trong Mụ ục 2.3 bằng cáách bổ sung ccác liên kết giữ ữa mỗi đặc trrưng s∈C vớii đặc trưng q∈T. Đồ thị cuốối cùng ta nhận n được có tập đỉnh là tập nggười dùng U, tập sản phẩm P, tập đặc trrưng người dùùng T và tập đđặc trưng sản phẩm P. Tập đỉnh của đồ th hị được chia tthành hai phíaa, một phía là U∪T, phía còn c lại là P∪C. C Tập cạnh của đồ thị bao gồm 4 loại cạạnh: cạnh (i , x) x nối giữa đỉnnh người dùngg và đỉnh sản phẩm p được đánh đ trọng số là rix, cạnh (i , s) nối giữa đỉnh người dù ùng và đỉnh đặc đ trưng sản pphẩm được đáánh trọng số là wis, cạnh (q , x) nối giữaa đỉnh đặc trư ưng người dùnng và đỉnh sản n phẩm được đánh trọng sốố là vqx, cạnh ((q , s) nối giữ ữa đỉnh đặc trrưng người dùùng và đỉnh đặặc trưng sản pphẩm được đán nh trọng số là dqs. ế ế ế ế 0 0 0 0 ∈ ∈ ∈ à ∈ à à à ∈ ∈ ∈ ∈ (21) nh 1, chọn θ = 2 ta sẽ tính toán được ma a trận đánh Ví dụ với đồ thị biểu diiễn hệ tư vấn kết hợp được cho trong Hìn giá g mở rộng trrong Bảng 6 vvà đồ thị tư vấấn cộng tác mở m rộng được thể t hiện như H Hình 4. Các ccạnh màu vàng là những cạnh c mới đượcc bổ sung vào đồ thị hai phíía của lọc cộng g tác. Bảng 6. Maa trận đánh giá m mở rộng R u1 u2 u3 t1 t2 t3 t4 p1 5 0 0 2 0 0 2 p2 0 4 5 2 0 2 2 p3 4 0 4 2 2 0 4 p4 0 3 0 1 0 1 0 c1 4 2 4 2 1 1 4 c2 0 3 2 1 1 1 1 c3 4 1 2 1 1 0 3 Hình 4. Đồồ thị biểu diễn bbài toán tư vấn lai Ma trận đánh đ giá mở rộộng được đề xxuất theo (21)) đã tích hợp đầy đ đủ các gi á trị đánh giáá của lọc cộng g tác, hồ sơ người n dùng, hồồ sơ sản phẩm m, mối liên hệệ giữa hồ sơ người n dùng và hồ sơ nội dunng sản phẩm của lọc nội du ung. Trọng số s các đặc trưnng nội dung trrong hồ sơ ngư ười dùng, hồ sơ sản phẩm và v mối liên hệệ giữa các đặcc trưng nội dun ng có cùng metric m với giá trị đánh giá. Chính vì vậy,, các phương pháp tư vấn cộng c tác dựa vvào bộ nhớ [115, 16] hoặc các phương pháp p tư vấn cộộng tác dựa trêên mô hình [6, 11, 12] đều có c thể triển kh hai trên ma trậận đánh giá mởở rộng. Đây là à đóng góp chính c của bài báo b trong xây dựng mô hìnhh hợp nhất giữ ữa tư vấn cộng g tác và tư vấnn theo nội dunng. Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương 437 IV. CÁC PHƯƠNG PHÁP DỰ ĐOÁN TRÊN ĐỒ THỊ KẾT HỢP Sau khi dịch chuyển bài toán tư vấn kết hợp về bài toán lọc cộng tác chuẩn, về nguyên tắc ta có thể triển khai bất kỳ một phương pháp tư vấn cộng tác nào trên ma trận đánh giá mở rộng. Trong khuôn khổ của bài báo này, chúng tôi đề xuất mở rộng các phương pháp tư vấn cộng tác dựa vào bộ nhớ bằng cách mở rộng các độ tương quan trên trên ma trận đánh giá mở rộng. Sau đó, chúng tôi xây dựng một độ đo tương tự mới dựa vào các kỹ thuật tìm kiếm trên đồ thị. Kết quả thử nghiệm trên các bộ dữ liệu thực về phim cho thấy các phương pháp đề xuất cải thiện đáng kể kết quả tư vấn. 4.1. Phương pháp tư vấn kết hợp dựa vào người dùng Phương pháp tư vấn cộng tác dựa vào người dùng (UserBased) thực hiện ước lượng mức độ tương tự giữa các cặp người dùng dựa vào các độ đo tương tự để từ đó sinh ra dự đoán các sản phẩm mới phù hợp với người dùng cần được tư vấn [12, 15]. Hiệu quả của phương pháp UserBased phụ thuộc vào tập giá trị đánh giá R = (rix) được xác định theo (1). Do tính chất thưa thớt của ma trận đánh giá nên việc xác định mức độ tương tự giữa các cặp người dùng gặp nhiều hạn chế [14]. Để khắc phục nhược điểm này, chúng tôi tiến hành mở rộng phương pháp tư vấn kết hợp trên ma trận đánh giá mở rộng R được xác định theo (21). Trong đó, việc ước lượng mức độ tương tự giữa các cặp người dùng không chỉ thực hiện trên ma trận đánh giá mà được mở rộng cho toàn bộ hồ sơ người dùng. Phương pháp được ký hiệu là Hybrid-UserBased và tiến hành thông qua bốn bước như dưới đây. Bước 1. Tính toán mức độ tương tự giữa các cặp người dùng. Tại bước này ta có thể sử dụng các độ đo tương quan hoặc các độ đo tương tự để tính toán mức độ giống nhau giữa các cặp người dùng [15]. Gọi uij là mức độ tương tự giữa người dùng i∈U và người dùng j∈U. Khi đó, độ tương quan Pearson giữa người dùng i∈U và người dùng j∈U được mở rộng trên tập đánh giá người dùng và hồ sơ người dùng theo công thức (22). ∑ ∈ ∩ ∑ ∈ ∩ ∑ ∈ ∩ ∑ ∈ ∩ ∑ ∈ ∩ (22) ∑ ∈ ∩ Trong đó, | ∩ | ∩ | | ∩ | | | ∩ ∑ ∑ ∈ | ∑ | ∑ ∈ ∈ (23) ∩ ∩ ∈ ∩ (24) 0 (25) (26) (27) ∈ ∩ Bước 2. Xác định tập láng giềng cho người dùng cần tư vấn. Tại bước này ta chỉ cần sắp xếp các giá trị uij theo thứ tự giảm dần, trong đó i∈U là người dùng cần được tư vấn các sản phẩm x∈P. Sau đó chọn tập K người dùng đầu tiên làm tập láng giềng của người dùng i [15]. Ký hiệu tập láng giềng của người dùng i∈U là Ki. Bước 3. Dự đoán quan điểm của người dùng đối với các sản phẩm mới. Phương pháp phổ biến nhất để sinh ra dự đoán quan điểm của người dùng i∈U cho sản phẩm mới x∈P theo công thức (28)[15]. ∑ ∈ ∑ ∈ | (28) | Bước 4. Chọn K sản phẩm mới có rix cao nhất tư vấn cho người dùng i. 4.2. Phương pháp tư vấn kết hợp dựa vào sản phẩm Phương pháp tư vấn cộng tác dựa vào sản phẩm (ItemBased) thực hiện ước lượng mức độ tương tự giữa các cặp sản phẩm dựa vào các độ đo tương tự để từ đó sinh ra dự đoán các sản phẩm mới phù hợp với người dùng cần được tư vấn [1, 2, 16]. Hiệu quả của phương pháp ItemBased phụ thuộc vào tập giá trị đánh giá người dùng R = (rix) được xác định theo (1). Do tính chất thưa thớt của ma trận đánh giá nên việc xác định mức độ tương tự giữa các cặp sản phẩm gặp nhiều hạn chế. Để khắc phục nhược điểm này, chúng tôi tiến hành mở rộng phương pháp tư vấn kết hợp trên ma trận đánh giá mở rộng R được xác định theo (21). Trong đó, việc ước lượng mức độ tương tự giữa các cặp sản phẩm không chỉ thực trên ma trận đánh giá mà được mở rộng cho toàn bộ hồ sơ sản phẩm. Phương pháp được viết tắt là Hybrid-ItemBased và tiến hành thông qua bốn bước như dưới đây. Bước 1. Tính toán mức độ tương tự giữa các cặp sản phẩm. Tại bước này ta có thể sử dụng các độ đo tương quan hoặc các độ đo tương tự để tính toán mức độ giống nhau giữa các cặp sản phẩm [16]. Gọi pxy là mức độ tương tự giữa sản phẩm x∈P và sản phẩm y∈P. Khi đó, độ tương quan Pearson giữa sản phẩm x∈P và sản phẩm y∈P được mở rộng trên tập đánh giá người dùng và hồ sơ sản phẩm theo công thức (29). ∑∈ ∑∈ ∩ ∩ ∑∈ ∩ ∑ ∈ ∑ ∈ ∩ ∩ ∑ ∈ (29) ∩ MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI 438 Trong đó, | | | | ∩ | ∩ | ∑∈ ∑∈ ∈ | ∑ ∩ ∩ | | ∑ (30) ∩ ∩ ∈ ∩ ∈ (31) 0 (32) (33) (34) ∩ Bước 2. Xác định tập láng giềng cho sản phẩm cần tư vấn. Tại bước này ta chỉ cần sắp xếp các giá trị pxy theo thứ tự giảm dần. Sau đó chọn tập K sản phẩm đầu tiên làm tập láng giềng của sản phẩm x [16]. Ký hiệu tập láng giềng của sản phẩm x∈P là Kx. Bước 3. Dự đoán quan điểm của người dùng đối với các sản phẩm mới. Phương pháp phổ biến để sinh ra dự đoán quan điểm của người dùng i∈U cho sản phẩm mới x∈P theo công thức (35)[16]. ∑ ∈ ∑ ∈ | (35) | Bước 4. Chọn K sản phẩm mới có rix cao nhất tư vấn cho người dùng i. 4.3. Độ tương tự giữa các cặp người dùng dựa trên đồ thị Phương pháp Hybrid-UserBased được đề xuất trong Mục 3.1 có thể thực hiện dễ dàng trên đồ thị bằng cách xem xét tất cả các đường đi độ dài 2 từ đỉnh người dùng đến đỉnh người dùng trên đồ thị [5, 7]. Ví dụ để xác định mức độ tương tự giữa người dùng u1 và u2 trên đồ thị trong Hình 4 ta dựa vào các đường đi : u1-p1-u2, u1-c1-u2, u1-c3-u2. Trọng số của mỗi đường đi được tính bằng tích của trọng số các cạnh. Tổng trọng số tất cả các đường đi từ đỉnh i∈U đến đỉnh j∈U chính là độ tương tự giữa hai người dùng này. K người dùng có tổng trọng số các đường đi từ đỉnh i∈U đến đỉnh j∈U có trọng số lớn nhất chính là tập láng giềng của người dùng i. Sau đó sử dụng tập láng giềng để sinh ra dự đoán cho người dùng i. Một trong những thách thức lớn nhất của hệ tư vấn là vấn đề dữ liệu thưa [1, 3]. Vấn đề dữ liệu thưa xảy ra khi các giá trị đánh giá rix≠0 rất ít (dưới 1%). Số lượng các cạnh (i, x) thấp làm cho việc xác định các cạnh (i, s) cũng thấp. Điều này làm cho kết quả dự đoán của các phương pháp trên đạt kết quả không cao. Để hạn chế điều này, chúng tôi tiến hành mở rộng độ dài đường đi từ đỉnh người dùng đến đỉnh người dùng để tận dụng mối liên hệ gián tiếp giữa các cặp người dùng và các cặp đặc trưng nội dung khác nhau. Các đường đi có thể là các cạnh đánh giá (i, x), cạnh (i, s), cạnh (q, x) hoặc cạnh (q, s). Ví dụ để xác định mức độ tương tự giữa u2 và u3 với đồ thị biểu diễn bài toán tư vấn kết hợp trong Hình 4, ta có thể sử dụng các đường đi u2-p1-u1-p3-u3, u2-p4-t3-p2-u3, u2-c1-t4-p3-u3. Điều này là hoàn toàn hợp lý vì u2 thích p1, p1 được u1 thích, u1 thích p3 , p3 được u3 thích nên gián tiếp u2 tương tự với u3 ở một mức độ nào đó. Hoặc u2 thích p4, p4 được người dùng có đặc trưng t3 thích, người dùng có đặc trưng t3 thích p2, u3 thích t2 nên gián tiếp u2 tương tự với u3 ở một mức độ nào đó. Hoặc u2 thích đặc trưng c1, c1 phù hợp với tập người dùng có đặc trưng t4, t4 phù hợp với sản phẩm p3, u3 thích p3 nên cũng gián tiếp u2 tương tự với u3 ở một mức độ nào đó. Vì đồ thị tư vấn kết hợp là đồ thị hai phía nên các đường đi từ đỉnh người dùng đến đỉnh người dùng luôn có độ dài chẵn (2, 4, 6, 8) [7]. Trọng số của mỗi đường đi được tính bằng tích các trọng số các cạnh nên đường đi qua các cạnh có trọng số cao vẫn được đánh giá cao, đường đi qua các cạnh có trọng số thập vẫn được đánh giá thấp. Để ưu tiên cho các đường đi ngắn (độ dài 2) chúng tôi sử dụng tham số α (0<α<1) để đánh thấp trọng số các đường đi có độ dài cao. Cụ thể, phương pháp ước lượng tổng trọng số các đường đi độ dài L từ đỉnh người dùng đến đỉnh người dùng được xác định theo công thức (36) [7]. . . . . ế ế 2 4, 6, 8, … (36) Trong đó, L là độ dài đường đi, R là ma trận đánh giá mở rộng được xác định theo (21), RT là ma trận chuyển vị của R. Giá trị L chẵn được xác định khi tất cả ≠0 [7]. Tổng trọng số các đường đi độ dài L từ đỉnh i∈U đến đỉnh j∈U là mức độ tương tự giữa hai người dùng này. K người dùng j∈U có lớn nhất chính là tập láng giềng của người dùng i∈U. Dựa trên nhận xét này, chúng tôi điều chỉnh Bước 1 của thuật toán Hybrid-UserBased trong Mục 3.1 thành thuật toán Hybrid-UserBased-Graph trong Hình 5. Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương 439 Thuật toán Hybrid-UserBased-Graph: Đầu vào: - Ma trận đánh giá mở rộng R= (rix) biểu diễn đồ thị kết hợp được xác định theo (21). - i∈U là người dùng cần được tư vấn. - K là số lượng người dùng của tập láng giềng. Đầu ra: - Dự đoán x: rix| x∈P\Pi( quan điểm của người dùng i đối với các sản phẩm mới x∈P). Các bước tiến hành: Bước 1. Tính toán mức độ tương tự giữa các cặp người dùng trên đồ thị kết hợp: L ⇐2;//Thiết lập độ dài đường đi ban đầu L=2 Repeat ế 2 . ế 4, 6, 8, … . . . L⇐L + 2; //Tăng độ dài đường đi. Until ( ≠0với mọi j∈(U \ i)); Bước 2. Xác định tập láng giềng cho người dùng i∈U. • Sắp xếp ≠0 theo thứ tự giảm dần (i≠j). • Chọn K người dùng j∈U đầu tiên làm tập láng giềng của người dùng i (Ký hiệu tập láng giềng của người dùng i∈U là Ki). Bước 3. Dự đoán quan điểm của người dùng i đối với các sản phẩmx∈P\Pi. ∑∈ ; | | Bước 4. Chọn K sản phẩm có rixcao nhất tư vấn cho người dùng i. Hình 5. Thuật toán Hybrid-UserBased-Graph 4.4. Độ tương tự giữa các cặp sản phẩm dựa trên đồ thị Phương pháp Hybrid-ItemBased được đề xuất trong Mục 3.2 cũng có thể thực hiện dễ dàng trên đồ thị bằng cách xem xét tất cả các đường đi độ dài 2 từ đỉnh sản phẩm đến đỉnh sản phẩm trên đồ thị [7]. Ví dụ để xác định mức độ tương tự giữa sản phẩm p1 và p3 trên đồ thị trong Hình 4 ta dựa vào các đường đi: p1-u1-p3, p1-t1-p3, p1-t2-p3. Trọng số của mỗi đường đi được tính bằng tích của trọng số các cạnh. Tổng trọng số tất cả các đường đi từ đỉnh x∈P đến đỉnh y∈P chính là độ tương tự giữa hai sản phẩm. K sản phẩm có tổng trọng số các đường đi từ đỉnh x∈P đến đỉnh y∈P có trọng số lớn nhất chính là tập láng giềng của sản phẩm x. Sau đó sử dụng tập láng giềng của sản phẩm để dự đoán các sản phẩm phù hợp nhất đối với người dùng i [7]. Để hạn chế ảnh hưởng của vấn đề dữ liệu thưa, chúng tôi tiến hành mở rộng độ dài đường đi từ sản phẩm đến đỉnh sản phẩm để tận dụng mối liên hệ gián tiếp giữa các cặp sản phẩm và các cặp đặc trưng nội dung. Các đường đi có thể là các cạnh đánh giá (i, x), cạnh (i, s), cạnh (q, x) hoặc cạnh (q, s). Ví dụ để xác định mức độ tương tự giữa p1 và p2 với đồ thị biểu diễn bài toán tư vấn kết hợp trong Hình 4, ta có thể sử dụng các đường đi p1-u1-p3-u2-p2, p1-u2-p4-t1-p2, p1t2-c3-u3-p2. Tính hợp lý của phép suy diễn này cũng được lý giải tương tự như trường hợp tính toán mức độ tương tự giữa các cặp người dùng. Vì đồ thị tư vấn kết hợp là đồ thị hai phía nên các đường đi từ đỉnh sản phẩm đến đỉnh sản phẩm luôn có độ dài chẵn (2, 4, 6, 8) [5, 7]. Trọng số của mỗi đường đi được tính bằng tích các trọng số các cạnh nên đường đi qua các cạnh có trọng số cao vẫn được đánh giá cao, đường đi qua các cạnh có trọng số thấp vẫn được đánh giá thấp. Để ưu tiên cho các đường đi ngắn (độ dài 2) chúng tôi sử dụng tham số α (0<α<1) để đánh thấp trọng số các đường đi có độ dài cao. Cụ thể, phương pháp ước lượng tổng trọng số các đường đi độ dài L từ đỉnh sản phẩm đến đến đỉnh sản phẩm được xác định theo công thức (37) [7]. . . . . ế ế 2 4, 6, 8, … (37) Trong đó, L là độ dài đường đi, R là ma trận đánh giá mở rộng được xác định theo (20), RT là ma trận chuyển vị của R. Giá trị L chẵn được xác định khi tất cả ≠0 [7]. Tổng trọng số các đường đi độ dài L từ đỉnh x∈P đến đỉnh y∈P là mức độ tương tự giữa hai người dùng này. K sản phẩm y∈P có lớn nhất chính là tập láng giềng của sản phẩm x∈P. Dựa trên nhận xét này, chúng tôi điều chính Bước 1 của thuật toán Hybrid-ItemBased trong Mục 3.2 thành thuật toán Hybrid-ItemBased-Graph trong Hình 6. MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI 440 Thuật toán Hybrid-ItemBased-Graph: Đầu vào: - Ma trận đánh giá mở rộng R= (rix) biểu diễn đồ thị kết hợp được xác định theo (21). - i∈U là người dùng cần được tư vấn. - K là số lượng sản phẩm của tập láng giềng. Đầu ra: - Dự đoán x: rix| x∈P\Pi (quan điểm của người dùng i đối với các sản phẩm mới x∈P). Các bước tiến hành: Bước 1. Tính toán mức độ tương tự giữa các cặp sản phẩm trên đồ thị kết hợp: L ⇐2;//Thiết lập độ dài đường đi ban đầu L=2 Repeat . ế 2 ế 4, 6, 8, … . . . L⇐L + 2; //Tăng độ dài đường đi. Until ( ≠0với mọi y∈(P \ x)); Bước 2. Xác định tập láng giềng cho sản phẩm x∈P. • Sắp xếp ≠0 theo thứ tự giảm dần (x≠y). • Chọn K sản phẩm y∈P đầu tiên làm tập láng giềng của sản phẩm x (Ký hiệu tập láng giềng của sản phẩm x∈P là Kx). Bước 3. Dự đoán mức độ phù hợp của người dùng i đối với các sản phẩm x∈P\Pi. ∑ ∈ ; | | Bước 4. Chọn K sản phẩm có rix cao nhất tư vấn cho người dùng i. Hình 6. Thuật toán Hybrid-ItemBased-Graph V. THỬ NGHIỆM VÀ GIÁ Để đánh giá hiệu quả của các phương pháp tư vấn kết hợp đề xuất, chúng tôi tiến hành thử nghiệm trên bộ dữ liệu thực về phim [24]. Phương pháp trình bày ở trên được đánh giá và so sánh với các phương pháp khác theo thủ tục mô tả dưới đây. 5.1. Dữ liệu thử nghiệm Thuật toán lọc kết hợp được thử nghiệm trên bộ dữ liệu MovieLens của nhóm nghiên cứu GroupLens thuộc Trường Đại học Minnesota [24]. Bộ dữ liệu gồm 100.000 đánh giá của 943 người dùng cho 1682 phim. Giá trị đánh giá được thực hiện từ 1 đến 5. Mức độ thưa thớt dữ liệu đánh giá là 99.1%. Tập đặc trưng nội dung sản phẩm được chọn là 18 thể loại phim khác nhau [18]. Tập đặc trưng nội dung người dùng cũng được cung cấp kèm theo tập đặc trưng nội dung phim [24]. Chọn giá trị θ = 15 theo phương pháp được mô tả ở trên để xác định wis, vqx, dqs theo công thức (8), (12), và (16) theo thứ tự. Chọn α=0.8 để xác định trọng số đường đi cho các công thức (36), (37). 5.2. Phương pháp thử nghiệm Trước tiên, toàn bộ dữ liệu thử nghiệm được chia thành hai phần, một phần Utr được sử dụng làm dữ liệu huấn luyện, phần còn lại Ute được sử dụng để kiểm tra. Tập Utr chứa 75% đánh giá và tập Ute chứa 25% đánh giá. Dữ liệu huấn luyện được sử dụng để xây dựng mô hình theo thuật toán mô tả ở trên. Với mỗi người dùng i thuộc tập dữ liệu kiểm tra, các đánh giá (đã có) của người dùng được chia làm hai phần Oi và Pi. Oi được coi là đã biết, trong khi đó Pi là đánh giá cần dự đoán từ dữ liệu huấn luyện và Oi[8, 14]. Sai số dự đoán MAEu với mỗi khách hàng u thuộc tập dữ liệu kiểm tra được tính bằng trung cộng sai số tuyệt đối giữa giá trị dự đoán và giá trị thực đối với tất cả mặt hàng thuộc tập Pu. | | ∑ ∈ | ̂ | (38) Sai số dự đoán trên toàn tập dữ liệu kiểm tra được tính bằng trung bình cộng sai số dự đoán cho mỗi khách hàng thuộc Ute.Giá trị MAE nhỏ thì phương pháp dự đoán có độ chính xác cao [8, 14]. ∑ ∈ 5.3. So sánh và đánh giá | | (39) Các phương pháp tư vấn kết hợp Hybrid-UserBased, Hybrid-ItemBased, Hybrid-UserBased-Graph, HybridItemBased-Graph được trình bày trong mục 3.1, 3.2, 3.3 và 3.4 được so sánh với những phương pháp lọc cộng tác sau: - Phương pháp CF-UserBased sử dụng độ tương quan Pearson. Đây là phương pháp tư vấn cộng tác chuẩn dựa vào người dùng chỉ thực hiện dự đoán dựa trên tập giá trị đánh người dùng[15]. Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương - 441 Phương pháp CF-ItemBased sử dụng độ tương quan Pearson. Đây là phương pháp lọc cộng tác chuẩn dựa vào sản phẩm chỉ thực hiện dự đoán dựa trên tập giá trị đánh người dùng[16]. Phương pháp thử nghiệm được thực hiện chọn ngẫu nhiên 300, 600, 900 người dùng trong tập MovieLens làm dữ liệu huấn luyện. Chọn ngẫu nhiên 100, 200, 300 người dùng trong số còn lại để làm tập kiểm tra. Giá trị MAE trong Bảng 7 và Bảng 8 được ước lượng từ trung bình của 10 lần thử nghiệm ngẫu nhiên. Kết quả trong Bảng 7 cho thấy phương pháp lọc dựa vào người dùng thuần túy CF-UserBased cho lại giá trị MAE lớn nhất so với các phương pháp còn lại. Điều này có thể lý giải hạn chế của phương pháp lọc cộng tác khi quá trình huấn luyện chỉ dựa vào tập rất nhỏ các giá trị rix≠0. Khi kích thước tập dữ liệu huấn luyện lớn kết quả dự đoán phương pháp dần được cải thiện. Cụ thể giá trị MAE trên tập dữ liệu gồm 300, 600, 900 người dùng lần lượt là (0.856, 0.834, 0.838), (0.794, 0.775, 0.764), (0.778, 0.745, 0.748) theo thứ tự. Kích cỡ tập láng giềng lớn thực hiện thiếu ổn định. Tập láng giềng lớn không tỉ lệ thuận với kết quả dự đoán. Kết quả này hoàn toàn phù hợp với những nghiên cứu trước đây. Phương pháp Hybrid-UserBased cho lại giá trị MAE thấp hơn nhiều so với phương pháp CF-UserBased. Cụ thể với tập láng giềng K=10 và kích thước tập dữ liệu huấn luyện gồm 300, 600, 900 người dùng thì phương pháp cho lại giá trị MAE lần lượt là 0.642, 0.611, 0.607 so với 0.856, 0.794, 0.788 của phương pháp CF-UserBased; với K=20 giá trị MAE lần lượt là 0.586, 0.597, 0.611 so với 0.834, 0.775, 0.745 của phương pháp CF-UserBased;; với K=30 giá trị MAE lần lượt là 0.513, 0.553, 0.609 so với 0.838, 0.764, 0.748 của phương pháp CF-UserBased. Số lượng người dùng trong tập láng giềng lớn kết quả dự đoán cũng thực hiện ổn định hơn. Điều này có thể giải thích phương pháp HybridUserBased tính toán được mức độ tương tự giữa các cặp người dùng chính xác hơn vì phương pháp được thực hiện trên toàn bộ tập dữ liệu đánh giá và hồ sơ người dùng. Chính vì lý do đó phương pháp xác định được tập láng giềng của người dùng hiện thời tốt hơn để đưa ra kết quả dự đoán. Phương pháp Hybrid-UserBased-Graph cho lại giá trị MAE thấp nhất so với tất cả các phương pháp còn lại. Giá trị MAE trên các tập dữ liệu huấn luyện và tập láng giềng dao động trong khoảng 0.515≤MAE≤0.548. Phương pháp cho lại kết quả khá ổn định trên các tập tập dữ liệu và tập láng giềng có kích cỡ khác nhau. Điều này có thể khẳng định phương pháp xác định độ tương tự dựa trên tập các đường đi từ đỉnh người dùng đến đỉnh người dùng là hoàn toàn tin cậy. Độ tương tự giữa các cặp người dùng trên đồ thị đã tích hợp được tất cả các mối quan hệ giữa người dùng và sản phẩm, người dùng và đặc trưng nội dung sản phẩm, sản phẩm và đặc trưng người dùng, đặc trưng sản phẩm và đặc trưng người dùng. Bảng 7. Giá trị MAE của các phương pháp tư vấn dựa vào người dùng Kích thước tập dữ liệu huấn luyện 300 người dùng 600 người dùng 900 người dùng Phương pháp CF-UserBased Hybrid-UserBased Hybrid-UserBased-Graph Hybrid-CF-UserBased Hybrid-UserBased Hybrid-UserBased-Graph CF-UserBased Hybrid-UserBased Hybrid-UserBased-Graph Kích thước của tập láng giềng 10 20 30 0.856 0.834 0.838 0.642 0.586 0.513 0.521 0.518 0.512 0.794 0.775 0.764 0.611 0.597 0.553 0.515 0.515 0.537 0.788 0.745 0.748 0.607 0.611 0.609 0.548 0.519 0.517 Giá trị MAE trong Bảng 8 của các phương pháp lọc dựa vào sản phẩm cũng có diễn biến tương tự như phương pháp lọc dựa vào người dùng. Giá trị MAE của phương pháp lọc kết hợp Hybrid-ItemBased nhỏ hơn nhiều so với phương pháp CF-ItemBased. Lý do để điều này xảy ra chỉ có thể lý giải phương pháp tính toán mức độtương tựgiữa các cặp sản phẩm được thực hiện trên tập giá trị đánh giá và hồ sơ sản phẩm thực hiện chính xác hơn các phép đo chỉ dựa vào tập giá trị đánh giá. Giá trị MAE của phương pháp Hybrid-ItemBased-Graph thấp hơn đáng kể so với phương pháp Hybrid-ItemBased. Điều này cũng chỉ có thể giải thích độ tương tự giữa các sản phẩm dựa trên đồ thị đã kết hợp được tất cả các mối quan hệ gián tiếp giữa người dùng, sản phẩm, hồ sơ người dùng và hồ sơ sản phẩm. Bảng 8. Giá trị MAE của các phương pháp tư vấn dựa vào sản phẩm Kích thước tập dữ liệu huấn luyện 300 người dùng 600 người dùng 900 người dùng Phương pháp CF-ItemBased Hybrid-ItemBased Hybrid-ItemBased -Graph CF-ItemBased Hybrid-ItemBased Hibrid-ItemBased -Graph CF-ItemBased Hybrid-ItemBased Hybrid-ItemBased -Graph Kích thước của tập láng giềng 5 10 20 0.843 0.837 0.835 0.622 0.622 0.607 0.612 0.589 0.571 0.814 0.816 0.844 0.651 0.637 0.613 0.537 0.525 0.517 0.793 0.786 0.743 0.568 0.587 0.543 0.548 0.519 0.511 MỘT MÔ HÌNH ĐỒ THỊ CHO HỆ TƯ VẤN LAI 442 VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo đã đề xuất một mô hình hợp nhất giữa phương pháp tư vấn cộng tác và tư vấn the nội dung. Mô hình được xây dựng bằng cách dịch chuyển bài toán tư vấn kết hợp về bài toán tư vấn cộng tác thuần túy để tận dụng những ưu điểm của phương pháp này. Phương pháp dịch chuyển được tiến hành bằng cách xây dựng hồ sơ người dùng của lọc nội dung dựa trên đánh giá tự nhiên của người dùng đối với các sản phẩm. Sau đó, thiết lập mối quan hệ trực tiếp giữa người dùng và từng đặc trưng nội dung sản phẩm. Bằng cách này ta mở rộng được ma trận đánh giá của lọc cộng tác về phía các sản phẩm. Tiếp đến, quá trình xây dựng hồ sơ sản phẩm cũng được thực hiện trên thói quen sử dụng sản phẩm một cách tự nhiên của người dùng đối với các sản phẩm. Dựa trên hồ sơ sản phẩm, chúng tôi thiết lập mối quan hệ trực tiếp giữa sản phẩm và mỗi đặc trưng nội dung người dùng. Bằng cách này ta mở rộng được ma trận đánh giá của lọc cộng tác về phía người dùng. Cuối cùng, chúng tôi tìm cách xác định mối quan hệ tiềm ẩn giữa mỗi đặc trưng người dùng với các đặc trưng sản phẩm dựa trên hồ sơ người dùng và hồ sơ sản phẩm. Mô hình cuối cùng nhận được là mở rộng của mô hình tư vấn cộng tác cơ bản. Sau khi thu gọn về bài toán lọc cộng tác, ma trận đánh giá mở rộng được đề xuất trong bài báo đã tích hợp đầy đủ các giá trị đánh giá của lọc cộng tác, hồ sơ người dùng, hồ sơ sản phẩm, mối liên hệ giữa hồ sơ người dùng và hồ sơ nội dung sản phẩm của lọc nội dung. Trọng số các đặc trưng nội dung trong hồ sơ người dùng, hồ sơ sản phẩm và mối liên hệ giữa các đặc trưng nội dung có cùng metric với giá trị đánh giá. Chính vì vậy, các phương pháp tư vấn cộng tác dựa vào bộ nhớ hoặc các phương pháp tư vấn cộng tác dựa trên mô hình đều có thể triển khai trên ma trận đánh giá mở rộng. Để tận dụng ưu thế của mô hình đồ thị, chúng tôi đề xuất xây dựng một độ tương quan khai thác gián tiếp các mối quan hệ giữa người dùng, sản phẩm, đặc trưng người dùng, đặc trưng sản phẩm để nâng cao kết quả dự đoán. Kết quả thử nghiệm các phương pháp tư vấn kết hợp đề xuất cho thấy chất lượng tư vấn được cải thiện đáng kể so với các phương pháp tư vấn cơ bản. Chúng tôi tin tưởng rằng, mô hình cũng sẽ cho lại kết quả tốt đối với các phương pháp tư vấn dựa trên mô hình. Những kết quả này sẽ được trình bày trong những nghiên cứu tiếp theo của bài báo. VII. TÀI LIỆU THAM KHẢO 1. 2. 3. 4. 5. 6. 7. 8. 9. Su X., Khoshgoftaar T. M., “A Survey of Collaborative Filtering Techniques.,”. Advances in Artificial Intelligence ,2009, pp.1-20. Adomavicius G., Tuzhilin A., “Toward the Next Generation of Recommender Systems: A Survey of the State-ofthe-Art and Possible Extensions”, IEEE Transactions On Knowledge And Data Engineering, vol. 17, No. 6, 2005. Robin D. Burke, “Hybrid Recommender Systems: Survey and Experiments”. User Model. User-Adapt. Interact. 12(4): 331-370 (2002). M. D. Ekstrand, J. T. Riedl and J. A. Konstan, “Collaborative Filtering Recommender System”. Foundations and Trends in Human–Computer Interaction, Vol 4, No2, 2010, pp 81:173. Nguyen Duy Phuong, Le Quang Thang, Tu Minh Phuong, “A Graph-Based Method for Combining Collaborative and Content-Based Filtering. PRICAI 2008: 859-869. Nguyen Duy Phuong, Tu Minh Phuong, “Collaborative Filtering by Multi-task Learning”, RIVF 2008, pp: 227232. Do Thi Lien, Nguyen Duy Phuong, “Collaborative Filtering with a Graph-based Similarity Measure”. ComManTel, 2014, pp. 251-256. Asela Gunawardana, Guy Shani, “A Survey of Accuracy Evaluation Metrics of Recommendation Tasks. Journal of Machine Learning Research 10: 2935-2962 (2009). Asela Gunawardana, Christopher Meek, “ A unified approach to building hybrid recommender systems”. RecSys 2009: 117-124. 10. Robin D. Burke, Fatemeh Vahedian, Bamshad Mobasher, “Hybrid Recommendation in Heterogeneous Networks”. UMAP 2014: 49-60. 11. J. Wang, A. P. de Vries, and M. J. T. Reinders., “Unifying user-based and item-based collaborative filtering approaches by similarity fusion.,”. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval (SIGIR '06). ACM, New York, NY, USA, 501-508. 12. Raghavan, S., Gunasekar, S., Ghosh, J. “Review quality aware collaborative filtering”. In Proceedings of the sixth ACM conference on Recommender systems, pp. 123–130. ACM(2012). 13. Pazzani, M. J. “A framework for collaborative, content-based and demographic filtering”, Artificial Intelligence Review 13(5-6), 393–408 (1999). 14. Herlocker J. L., Konstan J. A., Terveen L. G., and Riedl J. T., “Evaluating Collaborative Filtering Recommender Systems”, ACM Trans. Information Systems, vol. 22, No. 1 (2004), pp. 5-53. 15. Breese J. S., Heckerman D., and Kadie C., “Empirical analysis of Predictive Algorithms for Collaborative Filtering”, In Proc. of 14th Conf. on Uncertainty in Artificial (1998). 16. Sarwar B., Karypis G., Konstan J., and Riedl J., “Item-Based Collaborative Filtering Recommendation Algorithms”, Proc. 10th Int’l WWW Conf (2001). Đỗ Thị Liên, Nguyễn Xuân Anh, Nguyễn Duy Phương, Từ Minh Phương 443 17. Claypool, M., Gokhale, A., Miranda, T., Murnikov, P., Netes, D., Sartin, M. “Combining content-based and collaborative filters in an online newspaper”. In: Proceedings of ACM SIGIR workshop on recommender systems, vol. 60. Citeseer (1999). 18. Claypool, M., Gokhale, A., Miranda, T., Murnikov, P., Netes, D., & Sartin, M. : Combining contentbased and collaborative fillters in an online newspaper. Proceedings of ACM SIGIR Workshop on Recommender Systems.(1999). 19. Basu, C., Hirsh, H., And Cohen, W.: Recommendation as classification: Using social and content-based information in recommendation. In Proceedings of the 15th National Conference on Artificial Intelligence, 714– 720. (1998). 20. Popescul A., Ungar L.H., Pennock D.M., and Lawrence S.: Probabilistic Models for Unified Collaborative and Content-Based Eecommendation in Sparse-Data Environments, Proc. 17th Conf. Uncertainty in Artificial Intelligence, (2001). 21. Balisico J., Hofman T.: Unifying collaborative and content-based filtering. In Proceedings. of Int. Conf. on Machine learning (ICML-04) (2004). 22. Crammer, K., and Singer, Y: Pranking with ranking. Advances in Neural Information Processing Systems 14 pp. 641-647. (2002). 23. Aggarwal C.C., Wolf J.L., Wu K.L., and Yu P.S.: Horting Hatches an Egg: A New Graph-Theoretic Approach to Collaborative Filtering, Proc. Fifth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining, Aug. (1999). 24. http://www.grouplens.org/. A GRAPH-BASED MODEL FOR HIBRID RECOMMENDER SYSTEM Do Thi Lien, Nguyen Xuan Anh, Nguyen Duy Phuong, Tu Minh Phuong Abstract - Recommender systems are the capable systems of providing essentialinformation and removing unessentialinformation for Internet users. The recommender systems are built based on two main information filtering techniques: Collaborative filtering and content-based filtering. Each method exploits particular aspects related to content features or product usage habit of users in the past to predict a brief list of the most suitable products with each user. In this paper, we propose a new unify method between collaborative filtering recommendation and content-based filtering recommendation based on graph model. The model allows us to shift hybrid filtering recommender problem to collaborative filtering recommender problem, then build new similar measures based on graph to determine similarities between two users or two items, these similar measures are used to predict suitable products for users in the system. The experimental results on real data sets show that the proposed methods achieve superior performance compared to baseline methods. Keywords - Collaborative Filtering Recommendation, Content-based Filtering Recommendation System, Item-Based Recommendation, User-Based Recommendation. Recommendation, Hybrid Filtering