Chương 1. HỆ THỐNG GỢI Ý VÀ GIẢI THUẬT CBR 1. Giới thiệu hệ thống gợi ý 1. Hệ thống gợi ý Hệ thống gợi ý [1] là một hệ thống có khả năng dự đoán và đưa ra sự gợi ý cho một items tới người sử dụng.
Sự gợi ý liên quan đến việc đưa ra quyết định của người dùng, chẳng hạn như chọn sản phẩm nào để mua, chọn nghe bài hát nào hay chọn địa điểm nào để đi du lịch… Thuật ngữ “Items” sử dụng để đại diện cho bất cứ một đối tượng, nội dung nào mà hệ thống gợi ý cho người dùng. Các lĩnh vực ứng dụng: Thương mại điện tử, Giáo dục, Học tập, Giải trí, Mạng xã hội… Các hệ thống điển hình: Amazon.com, Pandora Radio, Netflix… 4 1. Các phương pháp gợi ý truyền thống 1. Lọc cộng tác (Collaborative filtering) Đây là phương pháp được thực hiện dựa trên việc thu thập và phân tích một lượng lớn những thông tin về thói quen, hành vi hay sở thích của người dùng và từ đó dự đoán những item mà người dùng có khả năng hài lòng thông qua việc so sánh sự giống nhau của họ với những người dùng khác.
Điểm mạnh chính của phương pháp lọc cộng tác (collaborative filtering) [1] đó là nó không thực sự phụ thuộc vào khả năng phân tích nội dung của máy tính và do đó, phương pháp này có khả năng gợi ý một cách chính xác những item phức tạp. Chẳng hạn như hệ thống có thể xem xét một bộ phim mà không cần “hiểu” về nội dung của bộ phim đó. Có khá nhiều thuật toán đã được sử dụng để đo lường độ tương tự giữa những người dùng hoặc giữ các item với nhau trong một hệ thống gợi ý. Điển hình như: k-nearest neighborhood (k-NN) và Pearson Correlation.
Minh họa về lọc cộng tác (Collaborative filtering) [3] 5 Việc xây dựng một mô hình mẫu từ hồ sơ của người dùng thường được thực hiện giữa hai phương pháp thu thập dữ liệu tường mình và không tường minh. Một vài ví dụ về việc thu thập dữ liệu tường minh: - Yêu cầu người dùng bầu chọn một item theo một thang điểm nào đó - Yêu cầu người dùng xếp hạng một hoặc một nhóm các item mà người đó yêu thích nhất - Đưa ra cho người sử dụng hai item, yêu cầu họ chọn một item tốt hơn - Yêu cầu người dụng tạo ra danh mục sản phẩm yêu thích của riêng họ Một vài ví dụ về việc thu thập dữ liệu không tường minh: - Theo dõi những item mà người dùng đã xem - Phân tích thời gian mà người dùng xem một item - Lưu giữ thông tin về những sản phẩm mà người dùng đã mua trực tuyến - Thu thập danh sách những item mà người dùng đã xem trên máy tính của họ - Phân tích người dùng trên mạng xã hội để biết họ thích, không thích điều gì Nhược điểm: - Phụ thuộc nhiều vào lượng lớn thông tin từ phía người dùng, khó khăn với một hệ thống mới, gặp khó khăn với những item mới 1. Lọc dựa trên nội dung (Content-based filtering) Lọc dựa trên nội dung (Content-based filtering) [1] là phương pháp dựa trên những đặc điểm của chính item. Nói cách khác, thuật toán cho phương pháp này cố gắng gợi ý những item có những điểm giống với những item mà người dùng đã từng quan tâm trong quá khứ.
Item được đề xuất là những item 6 được chọn ra với độ tương đồng lớn nhất bằng việc so sánh với những item đã được người dùng xếp hạng, đánh giá trước đó. Về cơ bản, phương pháp này sử dụng một hồ sơ các đặc điểm về một item ở bên trong hệ thống. Hệ thống tạo một hồ sơ của người dùng dựa trên một véc-tơ trọng số các thuộc tính của item. Mỗi trọng số biểu thị cho mức độ quan trọng của mỗi thuộc tính tương ứng đối với người sử dụng và có thể được tính toán từ véc-tơ xếp hạng nội dung bằng nhiều công nghệ khác nhau.
Phương pháp tiếp cận đơn giản nhất là sử dụng giá trị trung bình từ véc- tơ xếp hạng item. Bên cạnh đó có một số phương thức phức tạp hơn sử dụng kỹ thuật học máy chẳng hạn như Bayesian Classifiers, Cluster Analysis, Decision Trees và Artificial Neural Networks để ước lượng xác xuất mà người dùng có khả năng thích một item nào đó. Sự phản hồi trực tiếp từ người dùng (thường là nút like, dislike) cũng có thể được sử dụng để gán thiết đặt những trọng số cho những thuộc tính nhất định (using Rocchio Classification or other similar techniques) Nhược điểm chính của lọc dựa trên nội dung đó là liệu rằng hệ thống có khả năng học những sở thích từ những hoạt động của người dùng liên quan đến một nguồn nội dung và sử dụng chúng cho những kiểu nội dung khác. Khi hệ thống bị giới hạn bởi việc gợi ý các nội dung cùng loại mà người dùng đã sử dụng, các sản phẩm gợi ý từ hệ thống có thể ít hơn nhiều so với các kiểu nội dung từ những dịch vụ khác.
Giải thuật CBR 1. Khái niệm CBR CBR (Case –Based Reasoning) [2, 3] có thể được coi như một hệ thức phương pháp luận hoạt động dựa trên sự tái sử dụng những kinh nghiệm, được mô hình hóa như một tình huống (case). Bên cạnh đó, CBR có thể được 7 hiểu như một mô hình bậc cao mô hình hóa quá trình nhận thức, hay một dạng thức tính toán để giải quyết một bài toán phát sinh. Giải thuật CBR áp dụng trong hệ tư vấn được tập trung chủ yếu theo cách hiểu thứ hai.
Trong đó, như Amoodt và Plaza [3] đã khẳng định, CBR được coi như một qui trình tìm lời giải cho một vấn đề, qui trình này sử dụng một nguồn tri thức cụ thể được thu thập qua những tình huống cố định đã phát sinh. Điều này đối nghịch với những phương pháp luận truyền thống chỉ dựa trên những nguồn tri thức phổ quát thuộc về một miền vấn đề nhất định. Những tri thức này được thể hiện bằng cách sử dụng một trong những ngôn ngữ biểu diễn tri thức như những qui tắc, dạng logic (first-order logic), hay các mạng ngữ nghĩa (semantic networks),. Giải thuật CBR Để có thể áp dụng qui trình giải lập luận tình huống CBR, vấn đề căn bản đầu tiên liên quan đến việc sử dụng ngôn ngữ mô tả tình huống (case representation language) và phạm vi sử dụng của những khái niệm trong mô tả tình huống.
Những khái niệm xuất hiện trong một ứng dụng CBR bao gồm nội dung tình huống, cấu trúc thích hợp mô tả một tình huống, cách thức sắp xếp các tri thức về tình huống đã diễn ra. Trong đó, nội dung tình huống phụ thuộc vào lĩnh vực mà tình huống đó diễn ra. Một tình huống có thể được biểu diễn bằng cách sử dụng véc-tơ đặc điểm tuyến tính (linear featured vector), văn bản bán cấu trúc (semi-structured text), hay các đối tượng có cấu trúc phức tạp như đồ thị (graph), mẫu đối tượng (object pattern) trong ngôn ngữ hướng đối tượng. Trong phương pháp sử dụng véc-tơ đặc điểm tuyến tính, một tình huống được mô tả như một danh sách cố định những đặc điểm không đồng nhất (heterogeneous features) bao gồm những chuỗi (string), số thực, số nguyên, Boolean,.
Về cơ bản, phương pháp mô tả tình huống với véc-tơ tuyến tính 8 được bắt nguồn từ các phương pháp học máy (machine learning) hay nhận dạng mẫu (pattern recognition), và được định nghĩa như một phương pháp sao chép (exemplar), ánh xạ (instance) hay ghi nhớ (memory). Đối với những phương pháp này, quá trình giải quyết vấn đề có thể được coi như một bài toán phân loại (classification) hay một tác vụ phỏng đoán chức năng (function approximation). Trong phương pháp thứ hai, thông tin đầu vào của một tình huống được biểu diễn dưới dạng văn bản. Bản thân những dữ liệu văn bản đầu vào đã trải qua quá trình tiền xử lý.
Ví dụ, quá trình tiền xử lý có thể bao gồm việc xây dựng chỉ mục (index), thông tin siêu dữ liệu (metadata), tóm lược cho dữ liệu văn bản. Quá trình này gắn kết CBR với các phương pháp thu thập dữ liệu (information retrieval). Trong phương pháp cuối cùng, một tình huống có thể là sự kết hợp giữa mô tả văn bản (text-based) với mô tả véc- tơ (vector-based representation) hoặc có thể được biểu diễn bằng những mô hình dữ liệu đồ thị. Phương pháp này thường được sử dụng trong trường hợp tình huống có cấu trúc phức tạp, bao gồm nhiều thành phần phân cấp (hierarchy).
Những tình huống xuất hiện trong tư vấn tour du lịch có thể được coi như những tình huống có cấu trúc phức tạp với sự xuất hiện của nhiều thành phần dạng cây như địa điểm (location), chỗ ở (accomodation), sự kiện (event), hoạt động (activity),. Vấn đề biểu diễn một tình huống tour cụ thể sẽ được đề cập chi tiết trong mục 2.1 của chương 2 với việc sử dụng XML là ngôn ngữ mô hình hóa dữ liệu chính. Tóm lại, một tình huống thường bao gồm ba thành phần chính: Mô tả vấn đề (problem description), giải pháp (solution) và kết quả (outcome). Thành phần thứ nhất chứa đựng những thông tin cần thiết miêu tả một tình huống phát sinh, mô tả này biểu thị khả năng tái sử dụng dữ liệu của những tình huống đã xảy ra để giải quyết vấn đề mới.
Nếu coi quá trình tìm lời giải cho một tình huống vấn đề mới như một hàm ước đoán thì phần mô tả dữ liệu 9 được xem như miền xác định của hàm, trong khi giải pháp và kết quả xác định các miền giới hạn tương đồng (codomain). Giải pháp biểu thị lượng thông tin cần thiết để giải quyết vấn đề, ví dụ như xây dựng một kế hoạch hợp lý để có thể đưa du khách đến địa điểm đúng thời điểm. Cuối cùng, kết quả được coi như một đánh giá tổng kết mức độ hữu ích của giải pháp được áp dụng giải quyết vấn đề phát sinh. Trong trường hợp giải thuật CBR của hệ tư vấn du lịch được trình bày trong chương này, tình huống tour sẽ được mô tả với những thành phần phức tạp, đồng nghĩa với không có sự khác biệt rõ ràng giữa những thành phần mô tả vấn đề với những thành phần biểu thị giải pháp.
Trong quá trình xử lý, giải pháp giải quyết vấn đề tìm kiếm, gợi ý điểm đến (destination) có thể được dùng như mô tả của vấn đề gợi ý địa điểm thắng cảnh (attraction) du khách nên đến. Về cơ bản, qui trình giải quyết vấn đề theo phương pháp lập luận tình huống CBR có thể được diễn tả bởi hình 1.2: Input New problem 1. Retrieve Learned Case Case Library Retrieved Cases 5. Reuse Model Retrieved Solution (s) Outcome 3.
Review Solution Hình 1.