Luận án Phát triển một số phương pháp xây dựng hệ tư vấn

đình”,”Đối tác”). - Tình huống ngữ cảnh là thuật ngữ dùng để chỉ một bộ giá trị điều kiện ngữ cảnh của các chiều ngữ cảnh tƣơng ứng đƣợc đánh giá bởi ngƣời dùng, ví dụ ngƣời dùng đánh giá 5 cho sản phẩm trong tình huống ngữ cảnh (“Cuối tuần”,”Tại nhà”,”Trẻ em”). Bảng 2.4. Ma trận đánh giá đa chiều của lọc cộng tác theo ngữ cảnh Ngƣời dùng Sản phẩm Đánh giá Thời gian Địa điểm Bạn đồng hành 5 Cuối tuần Tại nhà Trẻ em 4 Trong tuần Tại nhà Gia đình 3 Cuối tuần Tại rạp Đối tác 4 Trong tuần Tại nhà Gia đình 3 Cuối tuần Tại rạp Đối tác 2 Cuối tuần Tại rạp Đối tác 64 2.3.3. Các hƣớng tiếp cận giải quyết bài toán tƣ vấn theo ngữ cảnh Các cách tiếp cận để sử dụng thông tin về ngữ cảnh trong quá trình tƣ vấn có thể đƣợc phân thành 3 hƣớng tiếp cận [6][7]: 1) Lọc trƣớc theo ngữ cảnh; 2) Lọc sau theo ngữ cảnh và 3) Mô hình hóa ngữ cảnh. Hình 2.3 minh họa trực quan cơ chế tích hợp ngữ cảnh vào hệ tƣ vấn theo 3 hƣớng này. Dữ liệu U x I x C x R (a) Lọc trƣớc theo ngữ cảnh Dữ liệu theo ngữ cảnh U x I x R Xử lý tƣ vấn với ma trận đánh giá 2 chiều U x I à R Gợi ý danh sách sản phẩm phù hợp ngữ cảnh c u Dữ liệu U x I x C x R (b) Lọc sau theo ngữ cảnh Xử lý tƣ vấn với ma trận đánh giá 2 chiều U x I à R Gợi ý danh sách sản phẩm Gợi ý danh sách sản phẩm phù hợp ngữ cảnh c u Dữ liệu U x I x C x R (c) Mô hình hóa ngữ cảnh Xử lý tƣ vấn với ma trận đa chiều U x I x C à R Gợi ý danh sách sản phẩm phù hợp ngữ cảnh c u Hình 2.3. Các mô hình kết hợp ngữ cảnh vào hệ tƣ vấn [6] 2.3.3.1. Lọc trƣớc theo ngữ cảnh Hƣớng tiếp cận lọc trƣớc theo ngữ cảnh (Contextual Prefiltering) thực hiện nhƣ sau: Từ tập dữ liệu đầu vào của hệ tƣ vấn dựa trên ngữ cảnh là ma trận đánh giá đa chiều, hệ thống sẽ sử dụng thông tin ngữ cảnh của ngƣời dùng hiện thời để lọc tập dữ liệu ban đầu nhằm chỉ giữ lại những dữ liệu phù hợp với ngữ cảnh yêu cầu [88]. Một số phƣơng pháp lọc trƣớc theo ngữ cảnh đƣợc đƣa ra nhƣ: Phƣơng pháp phân chia dữ liệu (Splitting) [89], phƣơng pháp sử dụng một tập con các chiều ngữ cảnh để lọc (Context Relaxation) [90], phƣơng pháp lọc dựa trên ngữ nghĩa (Semantic Filtering) [91] hoặc phƣơng pháp phân cụm ngƣời dùng và sản phẩm dựa trên điều kiện ngữ cảnh [80]. 65 Sau khi lọc thông tin ngữ cảnh, bài toán tƣ vấn theo ngữ cảnh dựa trên ma trận đánh giá đa chiều (theo công thức (2.8)) sẽ chuyển về bài toán tƣ vấn truyền thống dựa trên ma trận đánh giá hai chiều (theo công thức (2.7)). Tập dữ liệu lọc đƣợc sẽ dùng để huấn luyện và tƣ vấn. Một trong những lợi ích quan trọng nhất của hƣớng tiếp cận này là việc có thể sử dụng lại các phƣơng pháp tƣ vấn truyền thống hai chiều đã đƣợc đề cập trong Mục 1.5 của Chƣơng 1 để áp dụng cho hệ tƣ vấn theo ngữ cảnh. Tuy nhiên vấn đề đặt ra với hƣớng tiếp cận lọc trƣớc theo ngữ cảnh cho hệ tƣ vấn là vấn đề dữ liệu thƣa và ít khai thác đƣợc thông tin ngữ cảnh vào quá trình dự đoán và tƣ vấn. Ví dụ trong hệ tƣ vấn phim, nếu một ngƣời dùng muốn xem một bộ phim vào thứ 7 thì chỉ những bộ phim đƣợc chiếu vào thứ 7 đã đƣợc xếp hạng mới đƣợc dùng để gợi ý cho ngƣời dùng. 2.3.3.2. Lọc sau theo ngữ cảnh Trái ngƣợc với hƣớng tiếp cận lọc trƣớc ngữ cảnh, lọc sau theo ngữ cảnh (Contextual Postfiltering) sử dụng toàn bộ ma trận đánh giá đã loại bỏ đi các chiều ngữ cảnh để huấn luyện và tƣ vấn. Do vậy, các phƣơng pháp tƣ vấn truyền thống sẽ đƣợc sử dụng để đƣa ra tƣ vấn ngay từ đầu mà không phụ thuộc vào ngữ cảnh. Kết quả tƣ vấn sẽ đƣợc lọc lại một lần nữa theo ngữ cảnh của ngƣời dùng hiện thời để thu đƣợc kết quả tƣ vấn cuối cùng. Tuy nhiên, do sử dụng toàn bộ ma trận đánh giá đã loại bỏ đi các chiều ngữ cảnh để huấn luyện và tƣ vấn nên các thông tin ngữ cảnh cũng không đƣợc khai thác, đồng thời một số dữ liệu trùng lặp và nhiễu có thể ảnh hƣởng tới chất lƣợng của các phƣơng pháp tƣ vấn truyền thống. Ví dụ trong hệ tƣ vấn phim, nếu một ngƣời dùng muốn xem một bộ phim vào cuối tuần. Sau khi thực hiện dự đoán danh sách phim gợi ý theo các phƣơng pháp tƣ vấn truyền thống (bỏ qua yếu tố thông tin ngữ cảnh), hệ thống sẽ lọc loại bỏ các bộ phim không đƣợc chiếu vào cuối tuần từ danh sách phim gợi ý. 2.3.3.3. Mô hình hóa ngữ cảnh 66 Hƣớng tiếp cận mô hình hóa ngữ cảnh (Contextual Modeling) cho phép thông tin ngữ cảnh, ngƣời dùng và sản phẩm đƣợc biểu diễn trực tiếp trong cùng một mô hình. Khi đó ma trận đánh giá đa chiều sẽ đƣợc sử dụng trực tiếp cho quá trình huấn luyện và tƣ vấn. Với hƣớng tiếp cận này, một số thuật toán tƣ vấn theo ngữ cảnh đƣợc đƣa ra có độ phức tạp lớn hơn các phƣơng pháp tƣ vấn truyền thống. Các phƣơng pháp mô hình hóa dựa vào ngữ cảnh đƣợc phân chia thành hai nhóm chính: Mô hình hóa ngữ cảnh độc lập và mô hình hóa ngữ cảnh phụ thuộc [88]. Phân rã Ten-xơ (Tensor Decomposition) [92] là một phƣơng pháp điển hình thuộc nhóm phƣơng pháp mô hình hóa ngữ cảnh độc lập. Phƣơng pháp này cho phép biểu diễn ngƣời dùng, sản phẩm và các chiều ngữ cảnh trong một không gian đa chiều, mỗi chiều là độc lập nhau. Một vấn đề đối với phƣơng pháp phân rã Ten- xơ là không gian lƣu trữ cùng xử lý sẽ rất phức tạp khi số lƣợng chiều ngữ cảnh quá lớn, đồng thời mối liên quan giữa các chiều ngữ cảnh không đƣợc khai thác. Không giống nhƣ phƣơng pháp mô hình hóa ngữ cảnh độc lập coi ngữ cảnh không phụ thuộc vào ngƣời dùng và sản phẩm, phƣơng pháp mô hình hóa ngữ cảnh phụ thuộc sẽ mô tả và khai thác sự phụ thuộc giữa ngƣời dùng, sản phẩm và ngữ cảnh tƣơng ứng. Hai kỹ thuật đƣợc sử dụng trong phƣơng pháp này đó là mô hình hóa dựa trên độ chênh lệch và mô hình hóa dựa trên độ tƣơng tự [6]. Kỹ thuật mô hình hóa dựa trên độ chênh lệch sẽ thiết lập một mức chênh lệch cộng thêm vào đánh giá không có ngữ cảnh để suy ra đánh giá của ngƣời dùng cho sản phẩm trong một tình huống ngữ cảnh cụ thể. Kỹ thuật mô hình hóa dựa trên độ tƣơng tự sẽ thiết lập một mức độ tƣơng tự nhân với đánh giá không có ngữ cảnh để điều chỉnh đánh giá của ngƣời dùng cho sản phẩm trong một tình huống ngữ cảnh cụ thể. Theo đó, để đƣa ra dự đoán đánh giá của ngƣời dùng với sản phẩm trong từng tình huống ngữ cảnh, có hai việc cần thực hiện đó là: (1) Lựa chọn phƣơng pháp dự đoán đánh giá của ngƣời dùng với sản phẩm khi không có ngữ cảnh và (2) Lựa chọn độ đo tính mức chênh lệch hoặc mức tƣơng tự giữa các tình huống ngữ cảnh. Với việc (1) về cơ bản chúng ta có thể sử dụng tất cả các phƣơng pháp tƣ vấn truyền thống để thực hiện, trong đó hai phƣơng pháp tƣ vấn cộng tác theo ngữ cảnh dựa trên Matrix 67 Factorization [77] và SLIM [93][94] đƣợc đánh giá là mang lại hiệu quả tƣơng đối tốt. Với việc (2) chúng ta có thể sử dụng những độ đo khoảng cách Euclid, Minkowski, độ đo tƣơng tự Cosin, Entropy, độ đo tƣơng quan Pearson, Spearman, Kendal, để tính toán mức độ chênh lệch hoặc tƣơng tự giữa các tình huống ngữ cảnh. Thực nghiệm cho thấy các phƣơng pháp mô hình hóa ngữ cảnh phụ thuộc cho kết quả tốt hơn phƣơng pháp mô hình hóa ngữ cảnh độc lập trong nhiều trƣờng hợp [95]. Tuy nhiên vấn đề đặt ra với các phƣơng pháp mô hình hóa ngữ cảnh phụ thuộc khi tích hợp ngữ cảnh vào hệ tƣ vấn truyền thống là vấn đề dữ liệu thƣa và khả năng mở rộng của nó. Một hƣớng tiếp cận khác để tích hợp ngữ cảnh vào hệ tƣ vấn là dựa trên mô hình đồ thị. Nhiều nghiên cứu đã chỉ ra rằng mô hình đồ thị giải quyết khá tốt vấn đề dữ liệu thƣa và khả năng mở rộng dữ liệu [96]. Neves ARM và các cộng sự của mình [97] đã đƣa ra đề xuất phƣơng pháp tƣ vấn theo ngữ cảnh trên cơ sở Ontology và kỹ thuật kích hoạt lan truyền (Spreading Activation). Punam Bedi và Richa [98] đề xuất một phƣơng pháp tiếp cận mới nâng cao hiệu quả tƣ vấn cho ngƣời dùng trong các nhà hàng dựa vào Ontology và kỹ thuật kích hoạt lan truyền. Emrah và các cộng sự [99] đề xuất một hệ tƣ vấn theo ngữ cảnh dựa trên một mô hình đồ thị cộng tác cho các chƣơng trình trên ti vi. Z. Bahramian và các cộng sự [100] đề xuất hệ tƣ vấn địa điểm du lịch theo ngữ cảnh dựa trên mô hình kích hoạt lan truyền. Tuy nhiên các nghiên cứu đã có này chủ yếu tập trung vào việc xây dựng các mô hình biểu diễn đồ thị áp dụng riêng lẻ cho từng bài toán tƣ vấn theo ngữ cảnh cụ thể, mà hầu nhƣ chƣa có một giải pháp tổng thể chung cho các bài toán tƣ vấn theo ngữ cảnh. Qua phần trình bày ở trên về các phƣơng pháp tích hợp ngữ cảnh vào hệ tƣ vấn đã chỉ ra rằng mỗi phƣơng pháp đều có những ƣu nhƣợc điểm riêng, việc lựa chọn phƣơng pháp nào sẽ phụ thuộc vào hiệu quả cho từng bộ dữ liệu của bài toán nghiệp vụ khác nhau. Căn cứ vào kết quả thực nghiệm nhiều nghiên cứu đã chỉ ra rằng không có phƣơng pháp nào là tốt cho mọi trƣờng hợp dữ liệu [76], nhƣng hai hƣớng tiếp cận lọc trƣớc theo ngữ cảnh và mô hình hóa ngữ cảnh đã và đang thu hút đƣợc sự quan tâm đặc biệt của cộng đồng nghiên cứu về hệ tƣ vấn theo ngữ cảnh, với số 68 lƣợng bài báo công bố lớn hơn hƣớng tiếp cận còn lại và chứng minh cho hiệu quả tƣ vấn cao trong nhiều trƣờng hợp. Mặc dù vậy, một số vấn đề chính còn tồn tại với phƣơng pháp thuộc hƣớng tiếp cận lọc trƣớc ngữ cảnh và mô hình hóa ngữ cảnh là vấn đề dữ liệu thƣa. Ngoài ra việc tích hợp các thông tin ngữ cảnh vào quá trình huấn luyện và tƣ vấn khiến cho các phƣơng pháp mô hình hóa ngữ cảnh còn gặp phải vấn đề là tăng độ phức tạp tính toán khi số chiều dữ liệu tăng lên. Để giảm thiểu những hạn chế nêu trên, luận án đề xuất một phƣơng pháp tƣ vấn cộng tác theo ngữ cảnh mới thuộc hƣớng tiếp cận lọc trƣớc ngữ cảnh, nhằm phát huy tính đơn giản trong cài đặt và tận dụng đƣợc các phƣơng pháp tƣ vấn truyền thống đã có. Đồng thời phƣơng pháp đề xuất cũng nhằm giải quyết hạn chế còn tồn tại phổ biến đối với hƣớng tiếp cận lọc trƣớc ngữ cảnh, đó là vấn đề dữ liệu thƣa và tích hợp hiệu quả thông tin ngữ cảnh vào quá trình tƣ vấn theo ngữ cảnh. Phƣơng pháp đề xuất đƣợc trình bày chi tiết trong Mục 2.3.4 phát triển từ độ đo tƣơng tự cho lọc cộng tác dựa trên mô hình đồ thị đề xuất trong Mục 2.2 của tác giả. 2.3.4. Phƣơng pháp đề xuất Nội dung phần này trình bày đề xuất về phƣơng pháp tƣ vấn cộng tác mới cho hệ tƣ vấn theo ngữ cảnh đƣợc phát triển từ độ đo tƣơng tự cho lọc cộng tác dựa trên mô hình đồ thị trình bày trong Mục 2.2. Về cơ bản phƣơng pháp đề xuất đƣợc thực hiện bằng cách kết hợp hai phƣơng pháp: 1) Lọc trƣớc theo ngữ cảnh; 2) Phƣơng pháp k-láng giềng gần nhất với độ đo tƣơng tự tính toán dựa trên mô hình đồ thị đề xuất (Mục 2.2). Sự kết hợp của hai phƣơng pháp này trong phƣơng pháp đề xuất đƣợc thể hiện qua bốn bƣớc: 1) Phân tách sản phẩm theo ngữ cảnh; 2) Biểu diễn đồ thị cho lọc cộng tác; 3) Tính độ tƣơng tự cho lọc cộng tác dựa trên biểu diễn đồ thị; 4) Sinh tƣ vấn. Bốn bƣớc này kết hợp với nhau trong một bộ khung đề xuất về triển khai phƣơng pháp lọc cộng tác dựa trên mô hình đồ thị cho hệ tƣ vấn theo ngữ cảnh trong Hình 2.5 dƣới đây. 69 C P U Phân tách sản phẩm theo ngữ cảnh U T Biểu diễn đồ thị cho lọc cộng tác Đồ thị hai phía Tính độ tƣơng tự cho lọc cộng tác dựa trên biểu diễn đồ thị Sinh tƣ vấn Ma trận tƣơng tự giữa các cặp ngƣời dùng Ma trận tƣơng tự giữa các cặp sản phẩm Danh sách Top-N sản phẩm tƣ vấn Hình 2.4. Bộ khung triển khai phƣơng pháp lọc cộng tác dựa trên mô hình đồ thị cho hệ tƣ vấn theo ngữ cảnh Việc thực hiện các bƣớc đƣợc miêu tả chi tiết trong các phần dƣới đây. 2.3.4.1. Phân tách sản phẩm theo ngữ cảnh Thông tin đầu vào cho bài toán tƣ vấn theo ngữ cảnh đƣợc miêu tả trong 2.3.2 gồm có: Tập hợp hữu hạn gồm ngƣời dùng , sản phẩm và K chiều ngữ cảnh , mỗi chiều ngữ cảnh có tƣơng ứng điều kiện ngữ cảnh. Từ thông tin đầu vào trên, việc phân tách sản phẩm theo ngữ cảnh sẽ chuyển hóa sản phẩm ban đầu theo ngữ cảnh thành các sản phẩm giả lập. Mỗi sản phẩm giả lập đƣợc tạo ra từ sự kết hợp sản phẩm ban đầu với một tình huống ngữ cảnh cụ thể, thủ tục này gọi là “Item Splitting” [101]. Thủ tục “Item Splitting” trƣớc đây chỉ sử dụng một chiều ngữ cảnh duy nhất để phân tách sản phẩm theo ngữ cảnh, việc chọn chiều ngữ cảnh này dựa vào độ đo thống kê, nhƣ độ lợi thông tin (Information gain) [77][102] . Điều này trong nhiều 70 trƣờng hợp khiến cho khá nhiều thông tin từ các chiều ngữ cảnh khác không đƣợc khai thác triệt để vào quá trình tƣ vấn sau này. Từ lập luận đƣa ra ở trên, luận án đề xuất phƣơng pháp phân tách sản phẩm theo ngữ cảnh cải tiến nhằm khắc phục hạn chế nêu trên của phƣơng pháp phân tách sản phẩm theo ngữ cảnh nguyên thủy. Phƣơng pháp phân tách sản phẩm theo ngữ cảnh cải tiến cho phép tích hợp đầy đủ thông tin ngữ cảnh trong việc chuyển hóa sản phẩm ban đầu thành sản phẩm giả lập. Các bƣớc thực hiện cụ thể nhƣ sau: - Bƣớc 1. Tạo ra 1 chiều ngữ cảnh mới đại diện cho chiều ngữ cảnh bằng cách lấy tích Đề-các của tất cả các chiều ngữ cảnh. Khi đó, mỗi điều kiện ngữ cảnh của là sự kết hợp các điều kiện ngữ cảnh của các chiều tƣơng ứng. Số lƣợng điều kiện ngữ cảnh của là , với . - Bƣớc 2. Tạo ra tập sản phẩm giả lập bằng cách lấy tích Đề-các của tập sản phẩm và chiều ngữ cảnh . Khi đó, mỗi sản phẩm giả lập thuộc là sự kết hợp của một sản phẩm ban đầu thuộc với một điều kiện ngữ cảnh thuộc . Số lƣợng sản phẩm trong tập là , với . - Bƣớc 3. Chuyển đổi ma trận đánh giá đa chiều về ma trận đánh giá hai chiều bằng việc loại bỏ đi tập ngữ cảnh, thay tập sản phẩm ban đầu bằng tập sản phẩm giả lập . Ví dụ áp dụng phƣơng pháp phân tách sản phẩm theo ngữ cảnh lên ma trận đánh giá đa chiều của lọc cộng tác theo ngữ cảnh (Bảng 2.4) ta thu đƣợc ma trận đánh giá hai chiều (Bảng 2.5), với là sản phẩm giả lập đƣợc tạo ra bởi sự kết hợp của sản phẩm và tình huống ngữ cảnh (“Cuối tuần”,”Tại nhà”,”Trẻ em”). Với ví dụ đƣợc đƣa ra trong Bảng 2.4, hệ tƣ vấn có 2 sản phẩm và 12 tình huống ngữ cảnh có thể có, do vậy số lƣợng sản phẩm giả lập đƣợc sinh ra theo phƣơng pháp phân tách sản phẩm theo ngữ cảnh cải tiến là 24. Ma trận đánh giá hai chiều nhận đƣợc thể hiện trong Bảng 2.5, luận án sắp xếp những cặp ngƣời dùng - sản phẩm có đánh giá trong những dòng trên cùng của ma trận và những cặp còn lại không có đánh giá 71 ở bên dƣới. Để tiết kiệm không gian trình bày, những cặp ngƣời dùng - sản phẩm không có đánh giá không nêu đầy đủ trong Bảng 2.5. Bảng 2.5. Ma trận đánh giá hai chiều nhận đƣợc sau phân tách sản phẩm theo ngữ cảnh Ngƣời dùng Sản phẩm giả lập Đánh giá 5 4 3 4 3 2 0 0 Quá trình phân tách sản phẩm theo ngữ cảnh sẽ biến đổi ma trận đánh giá đa chiều (biểu diễn đánh giá của ngƣời dùng với sản phẩm trong các tình huống ngữ cảnh khác nhau) về ma trận đánh giá hai chiều (biểu diễn đánh giá của ngƣời dùng với sản phẩm giả lập). Trên thực tế, số lƣợng các đánh giá ban đầu đƣa ra bởi ngƣời dùng cho các sản phẩm trong các tình huống ngữ cảnh là rất ít, khiến cho ma trận rất thƣa. Khi áp dụng thủ tục phân tách sản phẩm theo ngữ cảnh cải tiến lên , với việc giới thiệu các sản phẩm giả lập, sẽ càng khiến ma trận thu đƣợc càng thƣa thớt hơn nữa. Ví dụ: Thông tin thu thập đƣợc cho hệ tƣ vấn theo ngữ cảnh thể hiện qua Bảng 2.4, có 6 đánh giá cho 2 sản phẩm cho trƣớc. Sau quá trình phân tách sản phẩm theo ngữ cảnh đƣợc Bảng 2.5, có 6 đánh giá cho 24 sản phẩm giả lập. Nhƣ vậy, rất nhiều sản phẩm giả lập chƣa đƣợc đánh giá, điều này khiến ma trận đánh giá 2 chiều nhận đƣợc sau phân tách ngữ cảnh càng thƣa thớt hơn nữa. Để hạn chế những vấn đề dữ liệu thƣa của lọc cộng tác áp dụng cho ma trận đánh giá hai chiều , luận án sử dụng phƣơng pháp tính toán toán mức độ tƣơng tự giữa các cặp ngƣời dùng hoặc sản phẩm dựa trên mô hình đồ thị đề xuất trong Mục 72 2.2. Mô hình cho phép biểu diễn tất cả quan điểm của ngƣời dùng đối với các sản phẩm giả lập bằng một đồ thị. Khi đó, mức độ tƣơng tự cho lọc cộng tác dựa trên mô hình đồ thị đƣợc tính toán trên cơ sở khai thác tất cả những mối quan hệ trực tiếp và bắc cầu giữa các cặp ngƣời dùng hoặc các cặp sản phẩm giả lập. Việc khai thác đầy đủ mối quan hệ bắc cầu giữa các đối tƣợng trong hệ thống trên đồ thị sẽ góp phần giải quyết vấn đề thƣa dữ liệu và nâng cao hiệu quả dự đoán của phƣơng pháp cộng tác cho hệ tƣ vấn theo ngữ cảnh. Các nội dung này lần lƣợt đƣợc đề cập đến trong Mục 2.3.4.2 và Mục 2.3.4.3 sau đây. 2.3.4.2. Biểu diễn đồ thị cho lọc cộng tác Trƣớc tiên, áp dụng công thức (2.1) đƣợc trình bày trong Mục 2.2.1 nhằm chuyển đổi dạng biểu diễn cho ma trận đánh giá hai chiều từ Bảng 2.5 về Bảng 2.6 dƣới đây (Các cột cuối không có đánh giá). Bảng 2.6. Ma trận đánh giá chuyển đổi cho ma trận đánh giá 2 chiều của Bảng 2.5 1 0 0.8 0 0 0 0 0.6 0.8 0 0 0 0 0.6 0 0.4 0 0 Áp dụng phƣơng pháp biểu diễn đồ thị cho lọc cộng tác đề xuất trong Mục 2.2.1 cho ma trận đánh giá hai chiều (Bảng 2.6). Khi đó, đồ thị hai phía biểu diễn cho lọc cộng tác đƣợc thể hiện trong Hình 2.5. Hình 2.5. Đồ thị biểu diễn cho lọc cộng tác gồm tập ngƣời dùng và tập sản phẩm giả lập 0.4 0.6 0.8 0.6 0.8 1.0 𝑡 𝑡 𝑡 𝑡 𝑢 𝑢 𝑢 𝑡 .. 𝑡 73 Đồ thị hai phía nhận đƣợc không có các liên kết tới các đỉnh sản phẩm bởi vì các sản phẩm giả lập này không đƣợc đánh giá bởi bất kỳ ngƣời dùng nào. 2.3.4.3. Tính độ tƣơng tự cho lọc cộng tác dựa trên biểu diễn đồ thị Việc tính toán mức độ tƣơng tự cho lọc cộng tác dựa vào biểu diễn đồ thị nêu trên đƣơc chia thành 2 cách tiếp cận theo đề xuất trong 2.2.2, đó là: 1) Tính toán mức độ tƣơng tự giữa các cặp ngƣời dùng dựa trên đồ thị; 2) Tính toán mức độ tƣơng tự giữa các cặp sản phẩm dựa trên đồ thị. Việc làm này đƣợc xác định thông qua ma trận trọng số tổng quát biểu diễn đồ thị dƣới đây. ( ) (2.9) Với là ma trận trọng số biểu diễn đồ thị . Khi đó ma trận vuông sẽ đƣợc chia thành bốn phần theo công thức (2.9). Trong đó, đƣợc xác định theo công thức (2.3) biểu diễn mối quan hệ giữa ngƣời dùng và sản phẩm giả lập, là chuyển vị của biểu diễn mối quan hệ giữa sản phẩm giả lập và ngƣời dùng, ma trận vuông biểu diễn mối quan hệ giữa ngƣời dùng và ngƣời dùng, biểu diễn mối quan hệ giữa sản phẩm giả lập với sản phẩm giả lập. Các phần tử của ma trận , ban đầu đều có giá trị 0, tƣơng ứng với mức độ tƣơng tự giữa các cặp ngƣời dùng hoặc giữa các cặp sản phẩm giả lập không xác định tại thời điểm ban đầu. Sau khi xây dựng đƣợc ma trận việc tính mức độ tƣơng tự giữa các cặp ngƣời dùng hoặc các cặp sản phẩm theo công thức (2.5), (2.6) đề xuất trong mục 2.2.2 của luận án. 2.3.4.4. Sinh tƣ vấn 74 Áp dụng phƣơng pháp kNN để sinh danh sách các sản phẩm tƣ vấn phù hợp với ngƣời dùng hiện thời với độ đo tƣơng tự trình bày trong Mục 2.3.4.3 ở trên trong 2 trƣờng hợp dƣới đây. - Trƣờng hợp độ đo tƣơng tự giữa các cặp ngƣời dùng đƣợc sử dụng bởi phƣơng pháp User-Based k-NN để sinh tƣ vấn Với mỗi ngƣời dùng hiện thời , gọi là tập gồm ngƣời dùng tƣơng tự nhất với . Khi đó, đánh giá chƣa biết của ngƣời dùng với sản phẩm giả lập (gọi là ) đƣợc dự đoán căn cứ vào trung bình đánh giá của các ngƣời dùng trong tập với sản phẩm . ∑ { } (2.10) - Trƣờng hợp độ đo tƣơng tự giữa các cặp sản phẩm đƣợc sử dụng bởi phƣơng pháp Item-Based k-NN để sinh tƣ vấn Với mỗi sản phẩm giả lập chƣa đƣợc đánh giá bởi ngƣời dùng hiện thời , gọi là tập gồm sản phẩm tƣơng tự nhất với và đã đƣợc đánh giá bởi . Khi đó đánh giá chƣa biết của ngƣời dùng với sản phẩm đƣợc dự đoán căn cứ vào trung bình đánh giá của ngƣời dùng với các sản phẩm thuộc tập . ∑ { } (2.11) Từ dự đoán đánh giá đƣợc xác định theo một trong hai công thức (2.10) hoặc (2.11), hệ thống sẽ chọn ra các sản phẩm có dự đoán đánh giá cao để tƣ vấn cho ngƣời dùng hiện thời. Trên cơ sở bộ khung triển khai phƣơng pháp lọc cộng tác dựa trên mô hình đồ thị cho hệ tƣ vấn theo ngữ cảnh với 4 bƣớc thực hiện trình bày ở trên, luận án đề xuất hai thuật toán mới cho hệ tƣ vấn cộng tác theo ngữ cảnh là: 1) Thuật toán lọc cộng tác theo ngữ cảnh dựa vào mức độ tƣơng tự giữa các cặp ngƣời dùng trên mô hình đồ thị (IS-UserBased-Graph); 2) Thuật toán lọc cộng tác theo ngữ cảnh dựa 75 vào mức độ tƣơng tự giữa các cặp sản phẩm trên mô hình đồ thị (IS-ItemBased- Graph). Phần trình bày dƣới đây sẽ trình bày đầy đủ hai thuật toán này. Thuật toán lọc cộng tác theo ngữ cảnh dựa vào mức độ tƣơng tự giữa các cặp ngƣời dùng trên mô hình đồ thị Đầu vào: - Ma trận đánh giá đa chiều (chứa thông tin ngữ cảnh). - là người dùng hiện thời cần được tư vấn. - là ngữ cảnh ứng với người dùng hiện thời. - là số lượng người dùng trong tập láng giềng với . - là số lượng sản phẩm cần tư vấn cho . Đầu ra: - Danh sách sản phẩm tư vấn tới người dùng trong tình huống ngữ cảnh . Các bƣớc thực hiện: Bƣớc 1. Chuyển đổi ma trận đánh giá dạng đa chiều về dạng hai chiều Theo phƣơng pháp phân tách sản phẩm theo ngữ cảnh ( Mục 2.3.4.1). Bƣớc 2. Tính mức độ tương tự giữa các cặp người dùng dựa trên mô hình đồ thị Biểu diễn đồ thị cho hệ tƣ vấn (Mục 2.3.4.2).  ; //Thiết lập độ dài đƣờng đi ban đầu giữa các cặp ngƣời dùng Repeat {  ; // Tăng độ dài đƣờng đi. Until ( với mọi ); - Bƣớc 3. Sinh tư vấn cho người dùng hiện thời trong ngữ cảnh .  Với mỗi ngƣời dùng hiện thời , chọn ngƣời dùng có mức độ tƣơng tự cao nhất với làm tập láng giềng. Kí hiệu là tập láng giềng của gồm ngƣời dùng.  Dự đoán đánh giá chƣa biết của ngƣời dùng với sản phẩm 76 ∑ { }  Chuyển đổi ma trận dự đoán đánh giá hai chiều chứa sản phẩm giả lập (trong tập ) về ma trận dự đoán đánh giá đa chiều chứa sản phẩm thực (thuộc tập ) và tình huống ngữ cảnh đi kèm (thuộc tập ).  Chọn sản phẩm thực trong có đánh giá dự đoán cao nhất để tƣ vấn cho ngƣời dùng trong tình huống ngữ cảnh . Thuật toán 2.1. Thuật toán IS-UserBased-Graph Thuật toán lọc cộng tác theo ngữ cảnh dựa vào mức độ tƣơng tự giữa các cặp sản phẩm trên mô hình đồ thị Đầu vào: - Ma trận đánh giá đa chiều (chứa thông tin ngữ cảnh). - là người dùng hiện thời cần được tư vấn. - là ngữ cảnh ứng với - là số lượng sản phẩm trong tập láng giềng với sản phẩm được đánh giá. - là số lượng sản phẩm cần tư vấn cho . Đầu ra: - Danh sách sản phẩm tư vấn tới người dùng trong tình huống ngữ cảnh . Các bƣớc thực hiện: Bƣớc 1. Chuyển đổi ma trận đánh giá dạng đa chiều về dạng hai chiều Theo phƣơng pháp phân tách sản phẩm theo ngữ cảnh ( Mục 2.3.4.1). Bƣớc 2. Tính mức độ tương tự giữa các cặp sản phẩm dựa trên mô hình đồ thị Biểu diễn đồ thị cho hệ tƣ vấn (Mục 2.3.4.2).  ; //Thiết lập độ dài đƣờng đi ban đầu giữa các cặp sản phẩm Repeat {  ; // Tăng độ dài đƣờng đi. Until ( với mọi ); 77 - Bƣớc 3. Sinh tư vấn cho người dùng hiện thời trong ngữ cảnh .  Thực hiện lặp: với mỗi sản phẩm giả lập chƣa đƣợc đánh giá bởi ngƣời dùng o Chọn sản phẩm có mức độ tƣơng tự cao nhất với làm tập láng giềng. Kí hiệu là tập láng giềng của gồm sản phẩm. o Dự đoán đánh giá chƣa biết của ngƣời dùng với ∑ { }  Chuyển đổi ma trận dự đoán đánh giá hai chiều chứa sản phẩm giả lập (trong tập ) về ma trận dự đoán đánh giá đa chiều chứa sản phẩm thực (thuộc tập ) và tình huống ngữ cảnh đi kèm (thuộc tập ).  Chọn sản phẩm thực trong có đánh giá dự đoán cao nhất để tƣ vấn cho ngƣời dùng trong tình huống ngữ cảnh . Thuật toán 2.2. Thuật toán IS-ItemBased-Graph Tại bƣớc 2 của thuật toán IS-UserBased-Graph và IS-ItemBased-Graph, điều kiện dừng để tính đƣợc mức độ tƣơng tự giữa các cặp ngƣời dùng hoặc các cặp sản phẩm đƣợc xác định căn cứ vào Định lý 2.1 và Định lý 2.2 nêu ra tại Mục 2.2.2. 2.4. Thực nghiệm và kết quả Nội dung phần này trình bày đánh giá hiệu quả của phƣơng pháp đề xuất trong sự so sánh với các phƣơng pháp tƣ vấn theo ngữ cảnh phổ biến. 2.4.1. Dữ liệu thực nghiệm Để thấy rõ hiệu quả của phƣơng pháp đề xuất, tác giả thực hiện tiến hành thực nghiệm trên ba bộ dữ liệu DepaulMovie [103], MovieLens (https://grouplens.org/), InCarMusic [103]. - Bộ dữ liệu DepaulMovie chứa 5043 đánh giá từ 97 ngƣời dùng cho 79 phim trong các tình huống ngữ cảnh khác nhau. Bộ dữ liệu này có 3 chiều ngữ cảnh là Time, Location, Companion. Chiều ngữ cảnh Time có 2 điều kiện ngữ cảnh (“Weekend”, “Weekday”), chiều ngữ cảnh Location có 2 điều kiện ngữ cảnh 78 (“Home”, “Cinema”), chiều ngữ cảnh Companion có 3 điều kiện ngữ cảnh (“Alone”, “Family”, “Partner”). Các mức đánh giá nằm trong dải từ 1 đến 5, mức độ thƣa thớt của dữ liệu là 94,516%. Các mức đánh giá 1, 2, 3, 4, 5 đƣợc chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0. - Bộ dữ liệu MovieLens 100K chứa 100000 đánh giá từ 973 ngƣời dùng, 1682 phim trong các tình huống ngữ cảnh khác nhau. Bộ dữ liệu này có 2 chiều ngữ cảnh là TimeOfDay, TimeOfWeek. Chiều ngữ cảnh TimeOfDay có 5 điều kiện ngữ cảnh (“Morning”, “Noon”, “Afternoon”, “Evening”, “Night”), chiều ngữ cảnh TimeOfWeek có 2 điều kiện ngữ cảnh (“Weekend”, “Weekday”). Các mức đánh giá nằm trong dải từ 1 đến 5,