Tài liệu Chọn lọc thông tin dựa trên nội dung ứng dụng xây dựng hệ thống gợi ý tin tức theo nhu cầu người dùng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THẠC HUY CHỌN LỌC THÔNG TIN DỰA TRÊN NỘI DUNG ỨNG DỤNG XÂY DỰNG HỆ THỐNG GỢI Ý TIN TỨC THEO NHU CẦU NGƯỜI DÙNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2013 i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THẠC HUY CHỌN LỌC THÔNG TIN DỰA TRÊN NỘI DUNG ỨNG DỤNG XÂY DỰNG HỆ THỐNG GỢI Ý TIN TỨC THEO NHU CẦU NGƯỜI DÙNG Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Việt Anh HÀ NỘI - 2013 ii 1 Mục lục Lời cảm ơn ............................................................................................................................ 3 Lời cam đoan ........................................................................................................................ 4 Lời mở đầu............................................................................................................................ 5 Danh mục hình minh hoạ ..................................................................................................... 6 Danh mục Bảng biểu và Đồ thị ............................................................................................ 7 Chương 1: Đặt vấn đề ........................................................................................................... 8 1.1 Bài toán ...................................................................................................................... 8 1.2 Bố cục luận văn ....................................................................................................... 10 1.3 Phương pháp nghiên cứu ......................................................................................... 11 1.4 Kết quả thu được ..................................................................................................... 12 Chương 2: Các nghiên cứu có liên quan ............................................................................ 13 2.1 Báo điện tử .............................................................................................................. 13 2.2 Gợi ý tin tức ............................................................................................................. 14 2.2.1 Thu thập thông tin (Information Retrieval) .................................................... 14 2.2.2 Lọc thông tin (Information Filtering) ............................................................. 15 2.2.3 Phân loại các hệ thống gợi ý .......................................................................... 15 2.2.3.1 Các hệ thống dựa trên nội dung ....................................................................................18 2.2.3.2 Các hệ thống lọc có hợp tác ........................................................................... 22 2.2.3.3 Các hệ thống lai ........................................................................................... 25 2.2.4 Các đặc trưng riêng của tin tức ...................................................................... 28 Chương 3: Hệ thống gợi ý tin tức tiếng Việt xenoNews..................................................... 30 3.1 Hướng tiếp cận và Kiến trúc hệ thống..................................................................... 30 3.1.1 Hướng tiếp cận ............................................................................................... 30 3.1.2 Kiến trúc hệ thống .......................................................................................... 31 2 3.2 Yêu cầu hệ thống ..................................................................................................... 32 3.2.1 Các yêu cầu chức năng ................................................................................... 33 3.2.2 Các yêu cầu phi chức năng............................................................................. 35 3.3 Thiết kế và cài đặt chi tiết các thành phần hệ thống ............................................... 36 3.3.1 Hồ sơ đối tượng tin tức (News Item Profile) ................................................. 36 3.3.2 Hồ sơ người dùng (User profile) .................................................................... 37 3.3.2.1 Mô hình hoá Sở thích ngắn hạn với thuật toán Láng giềng gần nhất ...................... 39 3.3.2.2 Mô hình hoá Sở thích dài hạn với Bộ phân lớp Naïve Bayes ................................ 40 3.3.2.3 Thông tin tự mô tả của người dùng .................................................................. 43 3.3.2.4 Kết hợp các mô hình vào quy trình ra quyết định ............................................... 45 3.3.3 Lõi xử lý - Back-end ...................................................................................... 46 3.3.4 Tầng giao tiếp trung gian – Middle-level....................................................... 48 3.3.5 Ứng dựng Web – Front-end ........................................................................... 49 3.3.5.1 Công nghệ Web được sử dụng để xây dựng Front-end ................................................49 3.3.5.2 Thiết kế giao diện và Thiết kế tương tác Web – con người là yếu tố trung tâm ........ 52 Chương 4: Các thử nghiệm và kết quả ............................................................................... 56 4.1 Các độ đo và Quá trình chuẩn bị thử nghiệm .......................................................... 56 4.1.1 Các độ đo dùng để đánh giá ........................................................................... 56 4.1.2 Quá trình chuẩn bị thử nghiệm....................................................................... 57 4.2 Hiệu quả gợi ý của Hồ sơ người dùng kết hợp ........................................................ 58 4.3 Cơ chế phản hồi ẩn time-coded ............................................................................... 61 Kết luận............................................................................................................................... 63 Phụ lục ................................................................................................................................ 64 Tài liệu tham khảo .............................................................................................................. 66 6 Danh mục hình minh hoạ Minh hoạ 1.1: Ví dụ về giao diện một chuyên mục cá nhân hoá trên BáoMới.com .......... 10 Minh hoạ 3.1: Kiến trúc 3-tầng của hệ thống xenoNews ................................................... 32 Minh hoạ 3.2: Quy trình thiết kế lặp được sử dụng để xây dựng xenoNews ..................... 33 Minh hoạ 3.3: Các Module chính của Back-end ................................................................ 46 Minh hoạ 3.4: Chi tiết tương tác giữa các Module của Back-end ..................................... 48 Minh hoạ 3.5: Kiến trúc Web theo kiểu Server-based ....................................................... 50 Minh hoạ 3.6: Kiến trúc Web theo kiểu Client-based ........................................................ 51 Minh hoạ 3.7: Cách Youtube giúp người dùng phân biệt các video họ đã xem ................ 54 Minh hoạ 3.8: Chức năng Watch Later của Youtube ......................................................... 55 Minh hoạ PL.1: Giao diện hiển thị tin dạng List ............................................................... 64 Minh hoạ PL.2: Giao diện hiển thị tin dạng Grid .............................................................. 64 Minh hoạ PL.3: Màn hình đọc tin chi tiết .......................................................................... 65 7 Danh mục Bảng biểu và Đồ thị Bảng biểu: Bảng 2.1: Ví dụ về một phần ma trận đánh giá cho hệ thống gợi ý phim .......................... 17 Bảng 2.2: Phân loại các hệ thống gợi ý ............................................................................. 27 Bảng 3.1: Các mục tin tức của hệ thống ............................................................................ 36 Bảng 3.2: Ma trận các vector thuộc tính Boolean dùng để xây dựng mô hình dài hạn .... 41 Bảng 4.1: Bảng số liệu trung bình trên tất cả người dùng, sau mỗi phiên huấn luyện ..... 59 Bảng 4.2: Kết quả đánh giá tự động của cơ chế phản hồi ẩn Time-coded ........................ 61 Đồ thị: Đồ thị 4.1: Sự biến đổi các độ đo Precision, Recall, F1 sau từng phiên huấn luyện ........ 60 Đồ thị 4.2: Hiệu quả hoạt động của hệ thống, thể hiện qua độ đo F1 ............................... 60 8 Chương 1: Đặt vấn đề Chương đầu tiên sẽ bắt đầu từ việc giải thích lý do, động lực thực hiện đề tài luận văn này. Nội dung của chương xoay quanh trình bày bối cảnh và sự cần thiết của một Hệ thống gợi ý tin tức tiếng Việt, mô tả các nội dung nghiên cứu trong luận văn, cùng với sơ lược các kết quả đã đạt được. 1.1 Bài toán Kể từ khi ra đời cho đến nay, Internet vẫn liên tục phát triển với tốc độ đáng kinh ngạc, song hành và đóng vai trò to lớn vào sự tiến bộ của nhân loại, đặc biệt là trong những lĩnh vực như khoa học, công nghệ, giao lưu văn hoá, ... Quan trọng nhất là Internet đã tạo nên một “thế giới phẳng”, cho phép mọi cá nhân, tổ chức có thể dễ dàng kết nối với nhau bất chấp thời gian hay khoảng cách địa lý. Tuy vậy, trở thành một công dân Internet thường đồng nghĩa với yêu cầu (hoặc nhu cầu) tiếp nhận, xử lý một lượng lớn thông tin hằng ngày, từ rất nhiều nguồn khác nhau. Điển hình nhất trong các loại thông tin này phải kể đến tin tức được cập nhật từ báo điện tử, vốn xuất hiện ngày một nhiều những năm gần đây. Báo điện tử có rất nhiều ưu điểm so với báo in truyền thống, không những sinh động hơn với hình ảnh, video, hay các liên kết tới bài viết khác, mà còn cho phép người dùng chủ động hơn trong việc nắm bắt thông tin mọi lúc mọi nơi, miễn là có Internet. Các trang báo điện tử thường xuyên cập nhật nhanh chóng tin tức mới, và người sử dụng thì có thể nhận thông báo khi có tin mới thông qua RSS, hoặc đọc trực tiếp trên website. Vài năm gần đây, rất nhiều tờ báo/tạp chí lâu đời đã buộc phải thay đổi vì sự phát triển như vũ bão của công nghệ số và sự thay đổi nhu cầu đọc của độc giả. Hầu hết các báo giấy lớn bây giờ đều đã điện tử hoá phiên bản giấy của mình. Sự tương tác giữa độc giả và báo điện tử cũng dễ dàng hơn, bởi vì độc giả có thể để lại những phản hồi dưới mỗi bài, hay chia sẻ cho nhiều người khác cùng đọc, … Đó chỉ là một vài trong số rất nhiều ưu điểm khiến cho báo điện tử ngày càng phát triển mạnh. Hệ quả tất yếu là, gần đây rất nhiều tờ báo giấy đã phải ngừng hoạt động hoặc phá sản do thua lỗ, hay chuyển hoàn toàn sang báo điện tử. Một ví dụ điển hình là tạp chí Newsweek danh tiếng của Mỹ, kết thúc năm 2012 đã chính thức đóng cửa báo in để tập trung phát triển phiên bản điện tử. Điều này phản ảnh xu thế của nền báo chí thế giới trong kỷ nguyên công nghệ số, không thay đổi sẽ bị đào thải. 9 Với khối lượng tin tức cần xử lý mỗi ngày tăng lên với tốc độ chóng mặt, trong khi đó thời gian của mỗi người lại có hạn, điều này tạo ra thách thức với khả năng xử lý của con người. Những cỗ máy tìm kiếm như Google, Yahoo có thể đáp ứng nhu cầu thông tin khi chúng ta cần giải đáp một thắc mắc nào đó. Nhưng nhiều khi, người dùng thậm chí còn không biết họ đang tìm kiếm gì, đó chính là trường hợp đối với tin tức. Kết quả là mỗi người thường phải truy cập nhiều nguồn báo khác nhau như VienamNet, Dân trí, Tinh tế, … để tìm kiếm những thông tin có thể khiến họ quan tâm. Nhưng do mỗi người có sở thích, nhu cầu và quan tâm đến những lĩnh vực khác nhau, nên hiệu quả của quá trình tìm kiếm, tiếp nhận và xử lý tin mới sẽ bị ảnh hưởng bởi nhiều “nhiễu” – nhằm chỉ những tin tức không còn/không có, hoặc gần như không có giá trị đối với họ. Chính nguyên do đó dẫn tới sự cần thiết phải cho ra đời các Hệ thống gợi ý tin tức. Bởi vì sự cá nhân hoá (personalization) là một trong những ưu điểm lớn nhất của báo điện tử so với báo giấy. Trong những năm qua, đã có nhiều nghiên cứu liên quan tới gợi ý tin tức cho người dùng, nhằm tối ưu hoá khoảng thời gian họ dùng để đọc tin mỗi ngày. Và trên thế giới, nhiều Hệ thống gợi ý tin tức đã ra đời, như iCurrent, Pulse, … và không thể không nhắc đến Google News của Google. Thế nhưng, những hệ thống hay dịch vụ tương tự cho báo điện tử tiếng Việt còn rất ít, và khả năng nắm bắt nhu cầu của người dùng còn nhiều mặt hạn chế. Theo những gì tôi được biết, hiện nay tại Việt Nam, chỉ có trang web BáoMới.com (Minh hoạ 1.1) là có những đặc điểm tương tự với hệ thống mà tôi mong muốn xây dựng thông qua nghiên cứu luận văn này. BáoMới.com cho phép người dùng tự tạo các chuyên mục theo nhu cầu cá nhân, bằng cách khai báo một số từ khoá, sau đó gợi ý cho người dùng những tin tức liên quan từ nhiều trang báo điện tử khác nhau. Trang web đó cũng có khả năng tự động phân tích thói quen độc giả và đưa ra gợi ý tin tức mới. Tuy nhiên qua quá trình sử dụng, tôi cảm thấy không thực sự hài lòng với hệ thống gợi ý tin tức đó do một số lý do sau: - Qua thời gian sử dụng khá dài, trang web vẫn gợi ý ra quá nhiều tin tức mà tôi không quan tâm. - Chức năng gợi ý tin tức từ các từ khoá đã khai báo nhiều khi không chính xác, vì từ khoá đó có thể xuất hiện trong nhiều ngữ cảnh khác nhau, và trong tin tức thuộc những chuyên mục khác nhau. - Giao diện hiển thị tin chưa sinh động, chưa thu hút độc giả. - Khả năng gợi ý tin tức chưa bắt kịp với sự thay đổi nhanh chóng thị hiếu độc giả. 10 Minh hoạ 1.1: Ví dụ về giao diện một chuyên mục cá nhân hoá trên BáoMới.com Chính vì những lý do trên, tôi nhận thấy sự cần thiết xây dựng một Hệ thống gợi ý tin tức tiếng Việt. Nội dung quá trình nghiên cứu nhằm hiện thực hoá Hệ thống này được trình bày trong phần tiếp theo. 1.2 Bố cục luận văn Nội dung nghiên cứu của luận văn gồm: Chương 2: thảo luận các nghiên cứu liên quan về Thu thập thông tin (Information Retrieval), Lọc thông tin (Information Filtering), tìm hiểu về các Hệ thống gợi ý (Recommendation Systems) cũng như những đặc tính riêng, cần biết của tin tức so với các dạng thông tin khác. 11 Chương 3: mô tả quá trình tôi ứng dụng hướng tiếp cận chọn lọc thông tin dựa trên nội dung vào thực tế, thông qua hệ thống gợi ý tin tức tiếng Việt xenoNews. Nội dung chương này bao gồm: o Các yêu cầu với hệ thống cần xây dựng o Mô tả hồ sơ đối tượng thông tin – trong trường hợp cụ thể của tin tức o Trình bày về việc mô hình hoá thông tin ngắn hạn, dài hạn riêng rẽ; đồng thời, có sử dụng thêm các luật người dùng tự mô tả. Từ đó, tôi đề xuất xây dựng một Hồ sơ người dùng dạng kết hợp, thống nhất, là trung tâm trong việc gợi ý (chọn lọc) thông tin dựa trên nội dung. o Mô tả thiết kế hệ thống gợi ý tin tức tiếng Việt, dựa trên nội dung, bao gồm ba phần chính: Lõi xử lý Back-end, Tầng giao tiếp trung gian Middle-level, và giao diện người dùng là ứng dụng Web ở Front-end. Chương 4: Chương này sẽ trình bày các thử nghiệm nhằm đánh giá hiệu quả hoạt động tổng thể của hệ thống gợi ý dựa trên nội dung, với thành phần then chốt là Hồ sơ người dùng kết hợp đã nêu trong Chương 3. Do đó, thử nghiệm cũng xem xét đóng góp của từng thành phần trong hồ sơ người dùng kết hợp (gồm mô hình ngắn hạn, mô hình dài hạn, các luật tự mô tả). Thêm vào đó, một thử nghiệm để đánh giá tính hiệu quả của cơ chế thu thập phản hồi time-coded trên Front-end (website) cũng được đưa ra xem xét. Chương 5: Tổng kết nội dung và đánh giá lại kết quả nghiên cứu luận văn, đề xuất hướng nghiên cứu để hoàn thiện hệ thống trong tương lai. 1.3 Phương pháp nghiên cứu Để hoàn thành nội dung nghiên cứu đã đề ra, đầu tiên, tôi tiến hành tìm hiểu kiến thức cơ bản về các mô hình hệ thống gợi ý nói chung. Sau đó, dựa trên những đặc điểm riêng của tin tức và điều kiện thực tế mà chọn hướng tiếp cận phù hợp. Khi đã xác định được hướng tiếp cận, tôi tiến hành nghiên cứu các thuật toán và xây dựng hệ thống. Song song với đó, các thói quen đọc tin tức, báo chí trực tuyến của mọi người cũng được điều tra, thông qua hình thức hỏi đáp trực tiếp. Các thông tin này sẽ giúp ích rất nhiều cho quá trình xây dựng hệ thống thử nghiệm, đặc biệt là giao diện và tương tác trên website. Cuối cùng, một số thử nghiệm khác nhau sẽ được tiến hành, nhằm đánh giá khả năng của hệ thống, từ đó, đề xuất các hướng nghiên cứu tiếp theo trong tương lai. 12 1.4 Kết quả thu được Sau quá trình nghiên cứu cơ bản, tôi đã quyết định xây dựng một hệ thống gợi ý (hay chọn lọc) tin tức tiếng Việt, hoàn chỉnh, theo hướng tiếp cận dựa trên nội dung (content-based approach). Trong đó, thành phần quan trọng nhất là một Hồ sơ người dùng kết hợp (Hybrid User Profile), có khả năng: mô hình hoá thông tin sở thích ngắn hạn, dài hạn của độc giả, một cách độc lập; cộng với việc sử dụng thêm thông tin người dùng cung cấp (dưới dạng các luật họ mô tả về nội dung tin tức họ quan tâm). Qua thử nghiệm, Hồ sơ người dùng kết hợp đã chứng tỏ rằng nó hoạt động hiệu quả hơn so với từng mô hình thông tin (ngắn hạn, dài hạn) độc lập, có khả năng nắm bắt nhanh sở thích của người dùng và theo dõi được những gì họ đã đọc. Do hiệu năng hoạt động của hệ thống dạng này phụ thuộc nhiều vào phản hồi, tương tác của người dùng, nên một cơ chế thu thập phản hồi ẩn (implicit feedback) từ Front-end cũng được đề xuất. Cơ chế đó được gọi là time-coded. Và kết quả thử nghiệm có trong chương 4 một lần nữa khẳng định những phán đoán của tôi khi quyết định cài đặt time-coded vào hệ thống thử nghiệm. 13 Chương 2: Các nghiên cứu có liên quan 2.1 Báo điện tử Sự ra đời của báo điện tử bắt đầu vào giữa những năm 1990 của thế kỷ trước, khi McAdams lập nên phiên bản trực tuyến của báo The Washington Post. Cô và đội của mình là những người đầu tiên thiết lập một tờ báo điện tử, do vậy họ có rất nhiều khó khăn cần vượt qua. Một mô hình kiến trúc với tên gọi Newspaper metaphor đã được xây dựng. Newspaper metaphor có thể được hiểu theo nghĩa tiếng Việt là “hình thức ẩn dụ về Báo chí” (Báo chí ở đây là báo giấy, báo truyền thống). Tên gọi này ám chỉ rằng mô hình đó phải thật sự thân thiện và dễ hiểu, sao cho bất kỳ ai biết đọc đều có thể tự chỉ ra cách sử dụng phiên bản điện tử. Mô hình Newspaper metaphor cũng sử dụng trang chủ (front page) làm điểm khởi đầu của hệ thống, một thuật ngữ vẫn còn được sử dụng phổ biến trên hầu hết các website cho tới ngày nay. McAdams và các đồng nghiệp cũng đã đưa ra kết luận rằng báo điện tử không thể là một bản sao trực tiếp của báo in. Hơn nữa, họ cũng nhận thấy rất khó để xác định cần giữ những gì và loại bỏ những gì dựa trên phiên bản in giấy. Vậy nên thay vì các biên tập viên của tờ báo giấy, trang báo trực tuyến được vận hành bởi một đội ngũ biên tập viên hoàn toàn mới. Do ấn phẩm điện tử của báo có tính tương tác hai chiều, nên những biên tập viên mới này phải suy nghĩ, làm việc theo những phương thức khác với kiểu truyền thông một chiều của báo chí truyền thống. Báo điện tử cũng xuất hiện từ khá sớm ở Việt Nam, tờ báo trực tuyến đầu tiên là tạp chí Quê hương, phiên bản điện tử ra đời từ năm 1997. Đây là tờ tạp chí của Uỷ ban về người Việt Nam ở nước ngoài, trực thuộc Bộ Ngoại giao, phát hành số đầu tiên ngày 6/2/1997, chính thức khai trương ngày 3/12/1997. Tiếp sau đó, năm 1998, báo điện tử VietnamNet ra đời; năm 1999, báo Nhân dân điện tử ra đời, … Cho tới nay, mặc dù tôi không có con số thống kê chính xác, nhưng chỉ tính riêng ở Việt Nam thì số lượng báo điện tử được cấp phép hoạt động ước tính cũng lên tới vài trăm. Hằng ngày, theo cách này hay cách khác, hầu hết người sử dụng Internet đều truy cập ít nhất một hoặc nhiều website tin tức khác nhau. Và tất nhiên họ chỉ tìm kiếm đọc những tin tức mà họ nghĩ là thú vị hay có giá trị với họ, giống như với báo in. Dù cho báo in luôn có những ưu điểm riêng như thoải mái hơn khi đọc, dễ dàng ghi chú, …, nhưng báo chí online lại có một thứ vũ khí còn lợi hại hơn – đó chính là khả năng cá nhân hoá (personalization). Với sự cá nhân hoá, việc tạo nên một tờ báo chỉ chứa những tin phù hợp với sở thích của từng người là 14 hoàn toàn có thể. Hệ thống của tác giả Kamba và các đồng nghiệp khai thác khả năng cá nhân hoá mà không cần sự can thiệp có chủ ý của người dùng, sử dụng những kỹ thuật như điều khiển động, tương tác và phản hồi ẩn. Từ đó hệ thống này hiển thị tin tức một cách linh hoạt, đồng thời có thể được chỉnh sửa bởi người dùng qua một tập hợp các cơ chế điều khiển. Thông qua những cơ chế này, độc giả có thể sắp xếp lại tin tức theo thứ tự họ mong muốn. 2.2 Gợi ý tin tức Khả năng Gợi ý (Recommendation) thường được sử dụng rộng rãi trong nhiều hệ thống thương mại khác nhau, nơi mà mỗi hệ thống đều có cơ sở dữ liệu riêng, và các thuật toán tiêu chuẩn như K-láng giềng gần nhất (K-Neareast Neighbours - KNN) được sử dụng để tối ưu kết quả gợi ý. Trong phần này, trước tiên tôi sẽ trình bày những nét chính của hai chủ đề nghiên cứu liên quan là Thu thập thông tin (Information Retrieval - IR) và Lọc thông tin (Information Filtering - IF). Dựa trên cơ sở đó, các mô hình hệ thống gợi ý khác nhau sẽ được phân tích. 2.2.1 Thu thập thông tin (Information Retrieval) Thu thập thông tin đã trở thành một chủ đề nghiên cứu từ những năm 1950, khi con người bắt đầu có thể lưu trữ nhiều thông tin vào máy tính và việc tìm ra thông tin hữu ích trong máy trở thành vấn đề bức thiết. Các hệ thống IR ra đời từ sớm sử dụng logic kiểu Boolean có nhiều khuyết điểm, như khó tạo được các truy vấn tốt hay không thể xếp hạng tài liệu. Ngày nay người dùng của các hệ thống IR yêu cầu khả năng sắp thứ tự kết quả tìm kiếm, bởi vậy mà các mô hình không gian vector, mô hình xác suất và mô hình ngôn ngữ được sử dụng. Mô hình không gian vector sử dụng các vector để đại diện cho tài liệu. Tất cả các tài liệu được xem như một tập hợp vector trong không gian. Và để xác định độ giống nhau giữa hai tài liệu, cosine của góc hoặc tích vô hướng của hai vector tương ứng sẽ được tính toán. Các mô hình xác suất chỉ ước lượng độ liên quan giữa các tài liệu được truy vấn, bởi vì xác suất thực là khái niệm không tồn tại trong các hệ thống IR. Giá trị ước lượng này cũng sẽ được sử dụng để sắp hạng các tài liệu, đó là khái niệm cơ bản của Nguyên lý xếp hạng xác suất (Probability Ranking Principle). Các mô hình ngôn ngữ lại bắt nguồn từ ý tưởng cho rằng tài liệu sẽ là kết quả phù hợp với truy vấn nếu như từ mô hình của tài liệu có thể tạo ra truy vấn. Điều này xảy ra khi các từ khoá của truy vấn thường xuyên xuất hiện trong tài liệu. Với mỗi tài liệu, một mô hình xác suất ngôn ngữ được xây dựng và dùng để ước lượng xác suất có thể tạo ra được truy vấn. Tương tự như trên, giá trị xác suất này sau đó lại được sử dụng để xếp hạng tài liệu. 15 Để cài đặt các hệ thống IR bằng các mô hình kể trên thì trước tiên cần tạo chỉ mục cho dữ liệu. Trước khi dữ liệu được tạo chỉ mục, ta cần phải thêm, xoá hoặc chỉnh sửa thông tin trong tài liệu, ví dụ như loại bỏ stopword, trích xuất thông tin về tác giả, … Sau quá trình xử lý đó, việc tạo chỉ mục dữ liệu sẽ tạo ra cấu trúc có thể tìm kiếm được, gọi chung là Chỉ mục (Index). Chỉ mục này chứa tham chiếu đến nội dung, được dùng để yêu cầu thông tin thông qua truy vấn. Các hệ thống IR cho phép người dùng tạo truy vấn từ khoá mô tả thông tin họ cần. Các từ khoá này sẽ dùng để tìm kiếm tham chiếu trong chỉ mục và hiển thị kết quả đến người dùng. Hệ thống cần trả lại các kết quả có liên quan nhất dựa trên nội dung yêu cầu. 2.2.2 Lọc thông tin (Information Filtering) Các hệ thống Lọc thông tin (IF) tập trung vào quá trình lọc nội dung dựa trên hồ sơ người dùng. Hồ sơ người dùng có thể được tạo ra bằng cách (a) để người dùng khai báo trực tiếp, hoặc (b) hệ thống tự tạo dựa trên việc ngầm giám sát hoạt động của họ. Người dùng sẽ nhận được thông tin họ cần dựa trên hồ sơ của chính mình từ hệ thống, một cách tự động. Một trong số các ưu điểm của hệ thống IF là khả năng thích nghi với sở thích mang tính dài hạn (long-term interest) của người dùng. Các thông tin có thể được chuyển tới người dùng dưới hình thức các thông báo, hoặc hệ thống sẽ tự động thực hiện hành động nào đó thay cho người dùng. Lọc thông tin và Thu thập thông tin khác nhau ở cách thức yêu cầu của người dùng được biểu diễn. Thay vì để người dùng phải kéo (pull) thông tin họ cần từ hệ thống thông qua truy vấn, một hệ thống Lọc thông tin (IR system) sẽ cố gắng mô hình hoá sở thích của người dùng và tự đẩy (push) thông tin liên quan về cho họ. 2.2.3 Phân loại các hệ thống gợi ý Nghiên cứu về các đơn vị xử lý thông tin thông minh đã nhận được nhiều sự quan tâm từ rất sớm. Do khối lượng thông tin trên Internet ngày càng nhiều, con người sẽ bị quá tải trong khả năng duyệt thông tin và các loại dữ liệu đa phương tiện. Quá tải thông tin đã không còn chỉ là một thuật ngữ nữa, mà trở thành thực tế đối với mọi người. Điều này dẫn tới nhu cầu tất yếu cần tìm ra các phương pháp tự động hoá quá trình tìm kiếm thông tin. Và kết quả là sự ra đời của Các đơn vị xử lý thông tin thông minh (Intelligent Information Agents), có khả năng xác định và khai thác thông tin dựa trên đặc điểm riêng của từng cá nhân [1]. Các hệ thống gợi ý đã trở thành một chuyên đề nghiên cứu độc lập từ đầu những năm 1990, khi Goldberg và các cộng sự phát triển một hệ thống thử nghiệm có khả năng lọc email. Tuỳ vào người dùng cụ thể, bộ lọc của Goldberg có thể phân biệt được các email quan trọng và không quan trọng. Đó là do họ đã sử dụng phương pháp lọc 16 hợp tác cho hệ thống của mình, bằng cách lưu lại phản ứng với mỗi email được đọc, mọi người đã gián tiếp hỗ trợ nhau lọc email. Vấn đề gợi ý thông tin thường được đơn giản hoá thành bài toán ước lượng đánh giá cho một đối tượng thông tin mà người dùng chưa từng xem. Ước lượng này thường dựa vào đánh giá của người dùng về các đối tượng khác. Một khi chúng ta đã có thể ước lượng điểm cho một đối tượng chưa biết, chúng ta sẽ có thể gợi ý cho người dùng những đối tượng thông tin với điểm đánh giá cao nhất. Vấn đề này có thể được trình bày theo mô tả toán học sau. Gọi C là tập hợp chứa tất cả người sử dụng và S là tập chứa tất cả các đối tượng có thể được gợi ý, như sách báo, phim ảnh, hay nhà hàng, … Không gian S của các đối tượng có thể rất lớn, từ vài trăm, vài nghìn, thậm chí nhiều triệu. Tương tự như vậy với không gian tập người sử dụng. Ta có u là hàm hiệu dụng dùng để đo tính hữu ích của một đối tượng s đối với người dùng c, có thể viết dưới dạng u : C  S  R , trong đó R là tập tất cả các giá trị có thể (ví dụ: tập các số nguyên không âm, hoặc số thực với giá trị trong khoảng nhất định). Sau đó với mỗi người dùng c  C , chúng ta muốn chọn ra những đối tượng s  S tối đa hoá lợi ích đối với người sử dụng: c  C , sc  arg max u (c, s) sS (2.1) Trong các hệ thống gợi ý, tính hiệu dụng (hay lợi ích) của một đối tượng thường được đại diện bởi điểm đánh giá (rating), chỉ ra một người sử dụng nhất định thích/quan tâm như thế nào tới một đối tượng cụ thể, ví dụ: người dùng tên Hải đánh giá bộ phim “The Avengers” đạt điểm 7/10. Tuy nhiên tuỳ thuộc vào ứng dụng, giá trị u có thể do người dùng đưa ra, hoặc được tính toán tự động bởi hệ thống. Mỗi phần tử của một không gian người dùng C có thể được định nghĩa bởi một hồ sơ (profile) bao gồm các đặc điểm khác nhau của người dùng, như tuổi, giới tính, thu nhập, tình trạng hôn nhân, … Và phần tử của tập đối tượng S cũng có thể được định nghĩa bởi nhiều thuộc tính. Ngoài ra, hồ sơ người dùng c còn có thể chứa trong đó lịch sử, đánh giá của người dùng về các đối tượng họ đã tương tác, … Vấn đề trung tâm của các hệ thống gợi ý chính là việc giá trị lợi ích u không được định nghĩa trong toàn không gian C  S , mà chỉ trên một số tập con không gian đó. Có nghĩa là giá trị u cần phải được ngoại suy tới toàn miền không gian C  S . Như đã nói, với các hệ thống gợi ý, giá trị lợi ích thông thường được đại diện bởi điểm mà chỉ có sẵn trên một vài đối tượng người dùng đã đánh giá trước đó. Ví dụ, trong một ứng dụng gợi ý 17 phim (MovieLens.org), ban đầu người dùng sẽ đánh giá về các phim họ đã xem, ví dụ: xem Bảng 2.1, trong đó điểm đánh giá được định nghĩa trên thang từ 1 đến 5. Biểu tượng  có nghĩa là người dùng không đánh giá bộ phim đó. Bởi vậy, bộ máy gợi ý phải có khả năng đoán trước điểm của những bộ phim người dùng chưa đánh giá và đưa ra gợi ý dựa vào những giá trị tiên đoán này. Bảng 2.1: Ví dụ về một phần ma trận đánh giá cho hệ thống gợi ý phim Life of Pi The Hobbit Wreck-it Ralph Kung Fu Panda Huy 4 4 3 3 Long  3 5 3 Linh 2 4 3  Sơn 3  5 2 Việc ngoại suy từ các giá trị đánh giá đã biết tới các giá trị chưa biết thường được thực hiện bằng cách (a) định nghĩa một hàm hiệu dụng dựa vào kinh nghiệm rồi xác định khả năng hoạt động của hàm dựa vào thực nghiệm, hoặc (b) ước lượng một hàm hiệu dụng có khả năng tối ưu hoá tiêu chí nào đó, ví dụ như sai số bình phương trung bình (Mean square error - MSE). Sau khi ước lượng xong, quá trình gợi ý một đối tượng cho một người dùng được thực hiện bằng cách chọn ra những giá trị cao nhất, tuân theo công thức (2.1). Giá trị ước lượng có thể có được bằng những phương pháp khác nhau trong học máy, nguyên lý xấp xỉ hay hàm kinh nghiệm. Các hệ thống gợi ý thường được phân loại dựa vào hướng tiếp cận của phương pháp ước lượng, trong các mục con của phần này, tôi sẽ giới thiệu về cách phân loại được đề xuất đó và cung cấp một cái nhìn tổng quan về các loại hệ thống gợi ý khác nhau. Việc phân loại lần đầu tiên được đề cập trong các tài liệu [2] và đã được nghiên cứu mở rộng trong nhiều nghiên cứu sau đó, ví dụ như theo nghiên cứu của hai tác giả M. Balabanovic và Y. Shoham:  Gợi ý dựa trên nội dung (Content-based recommendations): người dùng được gợi ý những gì “tương tự” với nội dung họ quan tâm trong quá khứ.  Gợi ý có hợp tác (Collaborative recommendations): những gì người dùng được gợi ý là có sự kết hợp từ những nội dung mà người dùng khác - với sở thích và đặc điểm tương tự. 18  Hướng tiếp cận lai/kết hợp (Hybrid approaches): kết hợp cả hai loại hình gợi ý trên. 2.2.3.1 Các hệ thống dựa trên nội dung Với các phương pháp dựa trên nội dung, giá trị lợi ích u(c,s) của đối tượng s cho người dùng c được ước lượng dựa trên các giá trị u(c,si) của người dùng c với các đối tượng si  S “tương tự” với s. Ví dụ, trong một ứng dụng gợi ý phim, để có thể gợi ý cho người dùng c, hệ thống cố gắng “hiểu” sự tương đồng giữa các bộ phim mà người c đã đánh giá cao trong quá khứ (dựa trên những đặc tính như diễn viên, đạo diễn, thể loại, …). Sau đó, chỉ những bộ phim có độ tương đồng cao với sở thích của người dùng được đưa vào kết quả gợi ý. Hướng tiếp cận dựa vào nội dung này có nguồn gốc từ những nghiên cứu trong lĩnh vực khai thác thông tin và lọc thông tin. Nhờ những nghiên cứu sớm trong hai cộng đồng đó, và do tầm quan trọng của các ứng dụng dựa trên dữ liệu text, nên nhiều hệ thống dựa vào nội dung ngày nay tập trung vào việc gợi ý các đối tượng chứa thông tin text, như văn bản, website, hay tin tức. Việc cải tiến các hướng khai thác thông tin truyền thống thường dựa trên sự khác nhau trong cách thức sử dụng hồ sơ người dùng (user profile), có chứa các thông tin về sở thích, đặc tính và yêu cầu của họ. Những thông tin này có thể được yêu cầu trực tiếp từ người dùng, thông qua các form yêu cầu hay bảng câu hỏi; hoặc một cách âm thầm bằng cách theo dõi hành vi người dùng. Ta gọi Content(s) là hồ sơ đối tượng (item profile) bao gồm các đặc tính của đối tượng dữ liệu s. Đó thường là một tập đặc điểm trích xuất từ s và được sử dụng để xác định sự tương đồng với các mục đích gợi ý. Như đã nói, do các hệ thống dựa trên nội dung được thiết kế chủ yếu để gợi ý các loại đối tượng chứa text, nên các đặc trưng trong hồ sơ đối tượng (item profile) thường là các từ khoá (keyword). Có thể lấy ví dụ từ Fab [3], một hệ thống gợi ý website cho người dùng, trong đó các website được đại diện bởi 100 từ khoá quan trọng nhất. Tương tự, hệ thống Syskill & Webert của M. Pazzani và cộng sự [1] đại diện mỗi tài liệu với 128 từ khoá chứa nhiều thông tin nhất. Tầm quan trọng của một từ khoá ki trong tài liệu dj được quyết định bởi trọng số wij , có thể định nghĩa theo nhiều cách khác nhau. Một trong những độ đo thông dụng nhất để xác định trọng số từ khoá trong Thu thập thông tin là TF-IDF (Term frequency/Inverse document frequency), được định nghĩa như sau: giả sử N là tổng số tài liệu có thể được gợi ý đến người sử dụng và từ khoá ki xuất hiện trong số ni tổng số đó. Thêm nữa, gọi fi,j là số lần từ khoá ki xuất hiện trong tài 19 liệu dj. Thì khi đó TFi,j, còn gọi là tần số (đã chuẩn hoá) của từ khoá ki trong tài liệu dj được tính theo công thức 2.2: TFi , j  fi , j max z f z , j (2.2) với giá trị max được tính dựa trên tần suất fz,j của tất cả các từ khoá kz xuất hiện trong tài liệu dj. Tuy nhiên, các từ khoá xuất hiện trong nhiều tài liệu lại không hữu ích trong việc xác định tài liệu phù hợp và không phù hợp. Bởi vậy, độ đo IDFi của từ khoá ki được sử dụng cùng với TFi,j. Giá trị IDF này được định nghĩa: IDFi  log N ni (2.3) Từ đó, trọng số TF-IDF của từ khoá ki trong tài liệu dj có thể được viết dưới dạng: wi , j  TFi , j  IDFi (2.4) và nội dung của tài liệu dj là Content (d j )  (wij ,...wkj ) . Như đã trình bày, các hệ thống dựa vào nội dung (content-based system) gợi ý các đối tượng thông tin tương tự với những gì người dùng đã thể hiện sự quan tâm trong quá khứ [1]. Cụ thể hơn, nhiều đối tượng thông tin sẽ được đem ra so sánh với các đối tượng cũ đó, và những gì phù hợp nhất sẽ được dùng làm gợi ý. Có thể hình thức hoá như sau, gọi ContentBasedProfile(c) là hồ sơ của người dùng c, có chứa các đặc tính và sở thích của người này. Hồ sơ này có được qua phân tích nội các đối tượng người sử dụng quan tâm, và thường được xây dựng bằng kỹ thuật phân tích từ khoá trong IR (Information Retrieval – Thu thập thông tin). Ví dụ, ContentBasedProfile(c) có thể được định nghĩa là vector các trọng số (wc1,… wck ), với mỗi giá trị wci đại diện cho tầm quan trọng của từ khoá ki đối với người dùng c, và có thể được tính toán từ vector các đối tượng người sử dụng đã đánh giá. Nhiều kỹ thuật khác nhau có thể được sử dụng, có cách tiếp cận dựa thì vào giá trị trung bình, ví dụ như thuật toán Rocchio có thể được dùng để tính ContentBasedProfile(c) dưới dạng vector “giá trị trung bình” của các vector đối tượng, phương pháp này đã được nghiên cứu bởi hai nhóm nghiên cứu độc lập của K. Lang [4] và M. Balabanovic, Y. Shoham [3]. Trong một trường hợp khác, M. Pazzani và cộng sự D. Billsus [1] lại sử dụng bộ phân loại Bayesian để ước lượng xác suất một tài liệu có thể sẽ được quan tâm. Thuật toán Winnow cũng đã chứng tỏ hoạt động tốt cho mục đích này, đặc biệt trong trường hợp số lượng thuộc tính lớn. 20 Trong các hệ thống content-based, hàm hiệu dụng u(c,s) thường được định nghĩa: u(c, s)  score(ContentBasedProfile(c), Content (s)) (2.5) Sử dụng mô hình đã đề cập ở trên về gợi ý trong các hệ thống sử dụng text (như website, tin tức, …), cả hồ sơ người dùng c - ContentBasedProfile(c) và hồ sơ đối tượng Content(s) của tài liệu s có thể được chuyển thành vector TF-IDF wc và ws , chứa trọng số các từ khoá. Còn hàm hiệu dụng u(c,s) thường được định nghĩa dưới dạng hàm đánh giá heuristic của hai vector wc và ws , sử dụng độ đo tương tự cosine (cosine similarity): K wc .ws u (c, s)  cos( wc , ws )  wc 2  ws  2 w i ,c i 1 K w i 1 2 i ,c wi ,s K  wi2,s (2.6) i 1 với K là tổng số tất cả từ khoá trong hệ thống. Bên cạnh các hàm heuristic truyền thống (dựa chủ yếu vào các phương pháp Thu Thập thông tin), cũng có các kỹ thuật khác, như phân lớp Bayesian và nhiều kỹ thuật học máy, bao gồm phân cụm, cây quyết định, mạng nơ-ron nhân tạo. Những kỹ thuật này khác với hướng tiếp cận IR ở chỗ: chúng không tính toán độ lợi thông tin dựa trên các hàm heuristic (như công thức độ tương tự cosine ở trên – công thức 2.6), mà dựa vào mô hình được học từ dữ liệu, sử dụng nhiều loại kỹ thuật thống kê và học máy. Ví dụ, dựa trên một tập các trang web đã được đánh giá là “có liên quan” và “không liên quan” bởi người sử dụng, Pazzani và cộng sự của mình [1] sử dụng phân lớp naïve Bayes để phân lớp trang web chưa được đánh giá. Cụ thể bộ phân lớp này sẽ ước lượng xác suất mà website pj thuộc vào lớp Ci nào đó (ví dụ: lớp “có liên quan” và “không liên quan”), khi đã biết trước tập từ khoá k1,j,…,kn,j của trang web: P(Ci | k1, j ...kn, j ) (2.7) thuật toán naïve Bayes còn giả định rằng các từ khoá là độc lập, bởi vậy xác suất trên có thể được xấp xỉ thành P(Ci ) P(k x , j | Ci ) x (2.8) 21 Ngay cả khi giả định về tính độc lập của các từ khoá là không hề đúng trong phần lớn các trường hợp thực tế, nhưng các kết quả thử nghiệm đều chỉ ra rằng các bộ phân lớp naïve Bayes vẫn đạt độ chính xác phân lớp cao. Đồng thời, cả hai xác suất P(k x, j | Ci ) và P(Ci ) có thể được ước lượng dễ dàng từ dữ liệu huấn luyện. Bởi vậy, với mỗi trang web pj, xác suất P(Ci | k1, j ...kn, j ) được tính cho từng lớp Ci , và pj sẽ được coi là thuộc lớp Ci có xác suất cao nhất. Thu thập thông tin từ dữ liệu text (text retrieval) đã đóng góp nhiều nghiên cứu cho các hệ thống gợi ý content-based. Một trong những nghiên cứu đó là lọc thích nghi (adaptive filtering), tìm hiểu cách xác định các tài liệu liên quan chính xác dần lên theo thời gian, bằng cách coi mỗi tài liệu là thành phần của một luồng liên tục. Các phương pháp khai phá dữ liệu text khác được D. A. Hull mô tả trong báo cáo “The TREC-7 Filtering Track: Description and Analysis”. Tài liệu [3] chỉ ra các hệ thống dựa trên nội dung (content-based) có nhiều hạn chế. - Hạn chế về hình thức của đối tượng. Các kỹ thuật content-based bị giới hạn bởi các thuộc tinh gắn với đối tượng mà hệ thống gợi ý. Bởi vậy, để có đủ tập hợp các thuộc tính, nội dung phải nằm dưới dạng có thể sử dụng trích xuất tự động bằng máy tính (như dữ liệu text), hoặc các tính năng có thể được gán tự động theo một cách thức nào đó. Mặc dù các kỹ thuật khai thác thông tin hoạt động tốt trong việc tách thuộc tính văn bản, nhưng nhiều kiểu dữ liệu lại khó trích xuất thuộc tính tự động (như dữ liệu đa phương tiện: ảnh, âm thanh, video). Một vấn đề khác nữa là nếu hai đối tượng được biểu diễn với một tập thuộc tính giống nhau thì chúng trở nên khó phân biệt. Ví dụ, khi hai bài viết được thể hiện bằng các từ khoá giống nhau, các hệ thống content-based sẽ khó phân biệt bài viết hay với bài viết dở. - Vấn đề “phù hợp quá mức”. Khi hệ thống chỉ có thể gợi ý các tài liệu có điểm số cao đối với một hồ sơ người dùng, người dùng đó bị giới hạn trong không gian đối tượng tương tự những gì họ từng xem. Vấn đề này thường được giải quyết bằng cách đưa thêm tính ngẫu nhiên vào hệ thống. Giải thuật gen (genetic algorithm) cũng được đề xuất để giải quyết hạn chế này. Cần lưu ý, trong nhiều trường hợp, các đối tượng được gợi ý không nên quá giống những gì người sử dụng đã từng biết (như trường hợp của tin tức). Bởi vậy, nhiều hệ thống gợi ý dựa trên nội dung như DailyLearner, sẽ lọc và loại bỏ không chỉ những gì quá khác biệt với sở thích