Luận văn Hệ thống đề xuất địa điểm sử dụng phương pháp lai ( Hybrid ) trên dữ liệu Foody.vn

hiều người dùng có sở thích tương tự nhau nhưng lại không xác định được bằng các độ đo tương quan do chưa cùng đánh giá một số sản phẩm. Ngược lại, nhiều cặp người dùng kém tương tự nhau nhưng vẫn được xác định trong tập láng giềng. + Lọc cộng tác dựa vào mô hình (Model Based Collaborative Filtering): Phương pháp sử dụng tập người dùng và tập sản phẩm để xây dựng mô hình huấn luyện. Mô hình dự đoán sau đó sẽ sử dụng kết quả của mô hình huấn luyện để sinh ra đề xuất cho người dùng. Phương pháp lọc cộng tác dựa vào mô hình có ưu điểm dễ tiếp cận, xử lý tốt hơn các vấn đề của Lọc cộng tác như dữ liệu thưa, khả năng xử lý dữ liệu lớn. Trong đề tài chúng tôi lựa chọn phương pháp lọc cộng tác dựa vào mô hình. 2.5 Phương pháp lọc dựa trên nội dung 2.5.1 Giới thiệu Trong phương pháp lọc dựa trên nội dung, hệ thống sẽ phân tích và so sánh nội dung của các thông tin, các sản phẩm từ đó đánh giá khả năng người dùng sẽ thích sản phẩm đó. Phương pháp lọc dựa trên nội dung dựa trên nguyên lý người dùng thích 13 sản phẩm hay thông tin A sẽ thích sản phẩm hay thông tin B tương tự với sản phẩm A. Phương pháp lọc dựa trên nội dung còn so sánh nội dung của sản phẩm hay thông tin với sở thích mà người dùng cung cấp. Chẳng hạn người dùng quan tâm tới những thông tin về chứng khoán thì sẽ được đề xuất những bản tin nói về chứng khoán Tuy nhiên, phương pháp lọc dựa trên nội dung cũng gặp một số khó khăn. Với những thông tin mà nội dung không có sẵn (chẳng hạn như một đoạn video, một bản nhạc) thì sẽ rất khó phân tích, và khó có thể đề xuất được. Người dùng Thích Màu: đỏ, xanh Hình: vuông, tròn Trích chọn đặc trưng Hồ sơ người dùng So sánh Đề xuất Hình 2. 6: Minh họa lọc theo nội dung 14 2.5.2 Phát biểu bài toán Bài toán lọc theo nội dung được phát biểu như sau: Cho P = {p1, p2, , pN} là tập gồm N sản phẩm. Nội dung sản phẩm p∈P được ký hiệu là Content(p) được biểu diễn thông qua tập K đặc trưng nội dung của P. Tập các đặc trưng sản phẩm p được xây dựng bằng các các kỹ thuật truy vấn thông tin để thực hiện mục đích dự đoán những sản phẩm khác tương tự với p. Cho U = {u1, u2, , uM} là tập gồm M người dùng. Với mỗi người dùng u∈U, gọi ContentBasedProfile(u) là hồ sơ người dùng u. Hồ sơ của người dùng u thực chất là lịch sử truy cập hoặc đánh giá của người dùng đó với sản phẩm. ContentBasedProfile(u) được xây dựng bằng cách phân tích nội dung các sản phẩm mà người dùng u đã từng truy cập hoặc đánh giá dự trên các các kỹ thuật truy vấn thông tin. Bài toán lọc theo nội dung khi đó là dự đoán những sản phẩm mới có nội dung thích hợp với người dùng dựa trên tập hồ sơ sản phẩm Content(p) và hồ sơ người dùng ContendBasedProflle(u). 2.5.3 Các phương pháp trong lọc theo nội dung Trong phương pháp này, nội dung sản phẩm phải được mô tả rõ ràng dưới dạng văn bản hoặc thông qua một số thao tác để trích chọn đặc trưng. Có nhiều phương pháp khác nhau để giải quyết bài toán lọc theo nội dung. Tuy vậy ta có thể phân loại các phương pháp thành hai cách tiếp cận chính là: Lọc nội dung dựa vào bộ nhớ (Memory Based Content Filtering) và lọc nội dung dựa vào mô hình (Model Based Content Filtering). Trong đề tài chúng tôi sẽ sử dụng lại kết quả của lọc cộng tác tới mối quan hệ Người dùng Sản phẩm kết hợp với mối quan hệ Sản phẩm Nội dung. Xây dựng mô hình đồ thị kết hợp để phát sinh đề xuất sẽ mô tả ở tiểu mục tiếp theo. 15 2.6 Phương pháp lai 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 thiết 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 các cách tiếp cận để có được hệ thống khuyến nghị chính xác hơn. 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: 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. + 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 đó). - 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 dựa chủ yếu trên các kỹ thuật cộng tác nhưng vẫn duy trì hồ sơ về người dùng. 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 đặc trưng: 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. - 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. 16 2.7 Đồ thị hai phía trong hệ thống đề xuất 2.7.1 Đồ thị hai phía (Biparties Graph) Các tên gọi đồ thị hai phía, đồ thị lưỡng phân, đồ thị phân đôi, đồ thị đối sánh hai phần v.v... [1] là để chỉ chung một dạng đơn đồ thị vô hướng G = (V, E) với E là tập cạnh và tập đỉnh của nó có thể chia làm hai tập con X, Y rời nhau sao cho bất kỳ cạnh nào của đồ thị cũng nối một đỉnh của X với một đỉnh thuộc Y. Khi đó người ta còn ký hiệu G là (X∪Y, E) và gọi một tập (chẳng hạn tập X) là tập các đỉnh trái và tập còn lại là tập các đỉnh phải của đồ thị hai phía G. Các đỉnh thuộc X còn gọi là các X_đỉnh, các đỉnh thuộc Y gọi là các Y_đỉnh. P1 P2 P3 P4 P5 P6 P7 U1 U2 U3 U4 U5 Hình 2. 7: Mô hình đồ thị hai phía 2.7.2 Tổng quan về tình hình nghiên cứu - Năm 2004 Huang và cộng sự [6] đề xuất mô hình đồ thị hai phía tính trọng số đường đi từ một đỉnh người dùng đến đỉnh sản phẩm. VD: Ma trận đồ thị hai phía Bảng 2. 2: Ví dụ ma trận trọng số của đồ thị hai phía [6] Người dùng Sản phẩm P1 P2 P3 P4 U1 0 1 0 1 17 U2 0 1 1 1 U3 1 0 1 0 P1 P2 P3 P4 C1 C2 C3 Hình 2. 8: Ví dụ đồ thị hai phía Trong ví dụ, các đường đi từ C1 đến P2 C1->P2 (1) C1->P4->C2->P2 (2) Tổng trọng số của (1) và (2) ta sẽ được trọng số đường đi từ người dùng C1 đến sản phẩm P2. Tính đường đi đến các sản phẩm còn lại. So sánh trọng số ta sẽ được sản phẩm có khả năng cao người dùng thích. Tác giả đề xuất ma trận đánh giá quy về 2 giá trị: 1 nếu người dùng đã chọn sản phẩm, và ∅ trong trường hợp ngược lại. Đồ thị trong phương pháp do Huang và cộng sự đề xuất [6] có trọng số bằng 1 cho tất cả các cạnh. - Năm 2012 TS Nguyễn Duy Phương và cộng sự [3] cải tiến mô hình đề xuất của Huang. Mỗi người dùng đưa ra các đánh giá của mình về các sản phẩm theo thang bậc (vd {1, 2, 3, 4, 5}). Trong đó với đánh giá bằng 5 được hiểu là người dùng đánh giá sản phẩm ở mức độ “rất tốt”; đánh giá bằng 4 được hiểu là người dùng đánh giá sản phẩm là “tốt”; đánh giá bằng 3 được hiểu là người dùng đánh giá sản phẩm ở mức độ “bình thường”; đánh giá bằng 2 được hiểu là người dùng đánh giá sản phẩm ở mức 18 độ “kém”; đánh giá bằng 1 được hiểu là người dùng đánh giá sản phẩm ở mức độ “rất kém”. Chúng tôi sẽ làm rõ trong mục tiếp theo. 2.7.3 Sử dụng đồ thị hai phía trong hệ thống đề xuất Ví dụ ma trận đánh giá của người dùng như sau: Bảng 2. 3: Ma trận đánh giá Người dùng Sản phẩm P1 P2 P3 P4 P5 P6 P7 U1 4 1 5 1 U2 5 2 5 1 2 U3 2 4 5 1 4 U4 1 2 5 2 U5 4 1 4 5 Trong ma trận đánh giá trên, các đánh giá có giá trị từ 1 đến 5. Trong [7] Huang xem tất cả các đánh giá như nhau và đều bằng 1. Tuy nhiên trong thực tế có đánh giá là tốt và có đánh giá là kém. Trong [3] TS Nguyễn Duy Phương đề xuất chuyển đổi giá trị đánh giá thấp thành các giá trị âm và đánh giá cao thành các giá trị dương và tách ma trận đánh giá ban đầu thành 2 ma trận đánh giá khác nhau. Một ma trận gồm các đánh giá âm thể hiện đánh giá là “kém”. Một ma trận gồm các đánh giá dương thể hiện đánh giá là “tốt”. 19 Cụ thể các đánh giá 1; 2 thành các giá trị tương ứng là -0,1; -0,2; 3 thành ∅ và 4;5 thành 0,1; 0,2. Ta có ma trận sau: Bảng 2. 4: Ma trận biến đổi từ ma trận đánh giá Người dùng Sản phẩm P1 P2 P3 P4 P5 P6 P7 U1 0.1 Ø -0.2 0.2 Ø -0.2 Ø U2 Ø 0.2 -0.1 0.2 -0.2 Ø -0.1 U3 -0.1 0.1 0.2 -0.2 Ø Ø 0.1 U4 -0.2 -0.1 Ø Ø 0.2 -0.1 Ø U5 Ø 0.1 Ø -0.2 0.1 0.2 Ø Đồ thị hai phía tương ứng: Gọi G là đồ thị hai phía có 2 tập đỉnh U đại diện cho người dùng và P đại diện cho sản phẩm. P1 P2 P3 P4 P5 P6 P7 U1 U2 U3 U4 U5 +0.1 +0.2 +0.2 +0.1 +0.1 +0.2 +0.2 +0.2 +0.1 +0.2 +0.1 -0.1 -0.2 -0.1 -0.1 -0.2 -0.2 -0.2 -0.2 -0.1 -0.2 -0.1 Hình 2. 9: Mô hình đồ thị hai phía chuyển đổi từ đồ thị đánh giá 20 Gọi G+ tương ứng với đồ thị trọng số dương, G- tương ứng với đồ thị trọng số âm được tác ra từ G. L là độ dài đường đi từ đỉnh người dùng i ∈ U đến đỉnh sản phẩm x ∈ P. Ma trận G+ Bảng 2. 5: Ma trận đánh giá trọng số dương Người dùng Sản phẩm P1 P2 P3 P4 P5 P6 P7 U1 0.1 0.2 U2 0.2 0.2 U3 0.1 0.2 0.1 U4 0.2 U5 0.1 0.1 0.2 Đồ thị G+ P1 P2 P3 P4 P5 P6 P7 U1 U2 U3 U4 U5 +0.1 +0.2 +0.2 +0.1 +0.1 +0.2 +0.2 +0.2 +0.1 +0.2 +0.1 Hình 2. 10: Đồ thị hai phía trọng số dương 21 Ma trận G- Bảng 2. 6: Ma trận đánh giá trọng số âm Người dùng Sản phẩm P1 P2 P3 P4 P5 P6 P7 U1 -0.2 -0.2 U2 -0.1 -0.2 -0.1 U3 -0.1 -0.2 U4 -0.2 -0.1 -0.1 U5 -0.2 Đồ thị G- P1 P2 P3 P4 P5 P6 P7 U1 U2 U3 U4 U5 -0.1 -0.2 -0.1 -0.1 -0.2 -0.2 -0.2 -0.2 -0.1 -0.2 -0.1 Hình 2. 11: Đồ thị hai phía trọng số âm Vì G+, G- là đồ thị hai phía nên mỗi đường đi độ dài L từ đỉnh người dùng i ∈ U đến đỉnh sản phẩm x ∈ P đều có độ dài lẻ (L=1,3, 5, 7,...). 22 Trọng số đường đi độ dài L trên đồ thị G+, G- được tính bằng tích các trọng số 𝑊𝑖𝑥 +, 𝑊𝑖𝑥 −. Do 0 ≤ 𝑊𝑖𝑥 + ≤ 1 ; -1 ≤ 𝑊𝑖𝑥 − ≤ 0 nên đường đi có độ dài L lớn sẽ có trọng số thấp, đường đi độ dài L nhỏ sẽ có trọng số cao. Ví dụ trên Hình 2. 9, đường đi u5-p2-u2-p4 có trọng số là 𝑊54 + = 0.1x0.2x0.2 = 0.004; u5-p2-u3-p7 có trọng số là 𝑊57 + = 0.1x0.1x0.1= 0.001. Ngược lại, đường đi u1-p3-u2-p5 có trọng số là 𝑊15 + = (-0.2)x(-0.1)x(-0.2) = -0.004; u1-p3- u2-p7 có trọng số là 𝑊17 + = (-0.2)x(-0.1)x(-0.1) = -0.002. Trong phương pháp lọc cộng tác sử dụng đồ thị hai phía để xếp hạng các sản phẩm đề xuất cho người dùng. Mấu chốt của phương pháp là bài toán tìm và tính trọng số tất cả các đường đi từ User đến tất cả các sản phẩm P. Những sản phẩm có trọng số cao sẽ được đề xuất cho người dùng. Trong đồ thị G+ ta có kết quả sau: Bảng 2. 7: Tổng trọng số tất cả các đường đi trên đồ thị G+ Stt Người dùng Sản phẩm Đường đi Trọng số 1 U1 P1 U1->P1 0.1 2 U1 P4 U1->P4 0.2 3 U1 P2 U1->P4->U2->P2 0.008 4 U1 P3 U1->P4->U2->P2->U3->P3 0.00016 5 U1 P7 U1->P4->U2->P2->U3->P7 0.00008 6 U1 P5 U1->P4->U2->P2->U5->P5 0.00008 7 U1 P6 U1->P4->U2->P2->U5->P6 0.00016 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U2 P2 U2->P2 0.2 23 2 U2 P4 U2->P4 0.2 3 U2 P1 U2->P4->U1->P1 0.004 4 U2 P3 U2->P2->U3->P3 0.004 5 U2 P7 U2->P2->U3->P7 0.002 6 U2 P5 U2->P2->U5->P5 0.002 7 U2 P6 U2->P2->U5->P6 0.004 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U3 P2 U3->P2 0.1 2 U3 P3 U3->P3 0.2 3 U3 P7 U3->P7 0.1 4 U3 P4 U3->P2->U2->P4 0.004 5 U3 P1 U3->P2->U2->P4->U1->P1 0.00008 6 U3 P5 U3->P2->U5->P5 0.001 7 U3 P6 U3->P2->U5->P6 0.002 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U4 P5 U4->P5 0.2 2 U4 P6 U4->P5->U5->P6 0.004 3 U4 P2 U4->P5->U5->P2 0.002 4 U4 P4 U4->P5->U5->P2->U2->P4 0.00008 5 U4 P1 U4->P5->U5->P2->U2->P4->U1- >P1 0.0000016 6 U4 P3 U4->P5->U5->P2->U3->P3 0.00004 24 7 U4 P7 U4->P5->U5->P2->U3->P7 0.00002 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U5 P6 U5->P6 0.2 2 U5 P5 U5->P5 0.1 3 U5 P2 U5->P2 0.1 4 U5 P4 U5->P2->U2->P4 0.004 5 U5 P1 U5->P2->U2->P4->U1->P1 0.00008 6 U5 P3 U5->P1->U3->P3 0.002 7 U5 P7 U5->P1->U3->P7 0.001 Trong đồ thị G- ta có kết quả sau: Bảng 2. 8: Tổng trọng số tất cả các đường đi trên đồ thị G- Stt Người dùng Sản phẩm Đường đi Trọng số 1 U1 P3 U1->P3 -0.2 2 U1 P6 U1->P6 -0.2 3 U1 P5 U1->P3->U2->P5 -0.004 4 U1 P7 U1->P3->U2->P7 -0.002 5 U1 P2 U1->P6->U4->P2 -0.002 6 U1 P1 U1->P6->U4->P1 -0.004 7 U1 P4 U1->P6->U4->P1->U3->P4 -0.00008 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U2 P3 U2->P3 -0.1 25 2 U2 P5 U2->P5 -0.2 3 U2 P7 U2->P7 -0.1 4 U2 P6 U2->P3->U1->P6 -0.004 5 U2 P2 U2->P3->U1->P6->U4->P2 -0.00004 6 U2 P1 U2->P3->U1->P6->U4->P1 -0.00008 7 U2 P4 U2->P3->U1->P6->U4->P1- >U3->P4 -0.0000016 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U3 P1 U3->P1 -0.1 2 U3 P4 U3->P4 -0.2 3 U3 P2 U3->P1->U4->P2 -0.002 4 U3 P6 U3->P1->U4->P6 -0.002 5 U3 P3 U3->P1->U4->P6->U1->P3 -0.00008 6 U3 P5 U3->P1->U4->P6->U1->P3- >U2->P5 -0.0000016 7 U3 P7 U3->P1->U4->P6->U1->P3- >U2->P7 -0.0000008 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U4 P6 U4->P6 -0.1 2 U4 P2 U4->P2 -0.1 3 U4 P1 U4->P1 -0.2 26 4 U4 P4 U4->P1->U3->P4 -0.004 5 U4 P3 U4->P6->U1->P3 -0.004 6 U4 P5 U4->P6->U1->P3->U2->P5 -0.00008 7 U4 P7 U4->P6->U1->P3->U2->P7 -0.00004 Stt Người dùng Sản phẩm Đường đi Trọng số 1 U5 P4 U5->P4 -0.2 2 U5 P1 U5->P4->U3->P1 -0.004 3 U5 P2 U5->P4->U3->P1->U4->P2 -0.00008 4 U5 P6 U5->P4->U3->P1->U4->P6 -0.00008 5 U5 P3 U5->P4->U3->P1->U4->P6- >U1->P3 -0.0000032 6 U5 P5 U5->P4->U3->P1->U4->P6- >U1->P3->U2->P5 -0.000000064 7 U5 P7 U5->P4->U3->P1->U4->P6- >U1->P3->U2->P7 -0.0000000320 Tổng trọng số trên cả hai đồ thị G+ và G- Bảng 2. 9: Tổng trọng số tất cả các đường đi trên đồ thị G+ và G- không theo User Stt Sản phẩm Trọng số 1 P2 0.3058800000 2 P5 0.0989983360 3 P4 0.0039984000 4 P7 0.0010591680 27 5 P6 -0.0959200000 6 P3 -0.0978832000 7 P1 -0.2039184000 Bảng 2. 10: Tổng trọng số tất cả các đường đi trên đồ thị G+ và G- theo User Stt User Sản phẩm Trọng số 1 U2 P4 0.1999984000 2 U2 P2 0.1999600000 3 U1 P4 0.1999200000 4 U3 P3 0.1999200000 5 U4 P5 0.1999200000 6 U5 P6 0.1999200000 7 U5 P5 0.0999999360 8 U3 P7 0.0999992000 9 U5 P2 0.099