Đăng ký Đăng nhập
Trang chủ Nghiên cứu hệ thống khuyến nghị người dùng dựa vào lọc cộng tác...

Tài liệu Nghiên cứu hệ thống khuyến nghị người dùng dựa vào lọc cộng tác

.PDF
57
1419
100

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ     PHẠM THỊ MY   NGHIÊN CỨU HỆ THỐNG KHUYẾN NGHỊ NGƯỜI DÙNG DỰA VÀO LỌC CỘNG TÁC LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN       HÀ NỘI - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ       PHẠM THỊ MY       NGHIÊN CỨU HỆ THỐNG KHUYẾN NGHỊ NGƯỜI DÙNG DỰA VÀO LỌC CỘNG TÁC Ngành:   Công nghệ thông tin   Chuyên ngành:  Kỹ thuật phần mềm   Mã số:   60480103        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 VĂN VINH                HÀ NỘI – 2014 1      Lời cam đoan Tôi xin cam đoan luận văn này là  công trình nghiên cứu hoàn toàn của bản thân.  Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân tôi  hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất  xứ rõ ràng và được trích dẫn hợp pháp.  Tôi xin chịu hoàn toàn trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho  lời cam đoan của mình.     Nam Định, ngày 28 tháng 09 năm 2014  Người cam đoan      Phạm Thị My     2    Lời cảm ơn   Đầu tiên, tôi xin chân thành cảm ơn thầy giáo Nguyễn Văn Vinh là cán bộ hướng  dẫn khoa học, thầy đã tận tình giúp đỡ và hướng dẫn tôi về cả chuyên môn, nghiên cứu  và định hướng phát triển trong suốt quá trình làm luận văn.    Để hoàn thành luận văn tốt nghiệp là cả một quá trình đầy khó khăn và thử thách  trong học tập và nghiên cứu tại trường Đại học Công Nghệ. Và để có được những thành  quả như ngày hôm nay, ngoài những nỗ lực của bản thân, không thể không nhắc tới là  sự động viên, giúp đỡ của các Thầy, Cô giáo, bạn bè, đồng nghiệp và người thân trong  gia đình.     Tôi cũng xin gửi lời cám ơn tới các Thầy, Cô giáo của Khoa Công Nghệ Thông  Tin, vì đã tận tình giảng dạy những kiến thức bổ ích, hiện đại về lĩnh vực Kỹ thuật phần  mềm tôi học tập và tạo mọi điều kiện cho tôi học tập nghiên cứu và hoàn thành luận văn  này.    Với gia đình, tôi xin bày tỏ lòng biết ơn sâu sắc vì gia đình đã luôn ở bên và ủng  hộ tôi trên con đường học tập và nghiên cứu.     Cuối cùng, tôi cũng xin gửi lời càm ơn đến đồng nghiệp và bạn bè tôi là những  người đã động viên, tạo mọi điều kiện cho tôi lao động và học tập trong suốt thời gian  qua.     Nam Định, ngày 28 tháng 09 năm 2014  Học viên   Phạm Thị My   3    Bảng các ký hiệu và chữ viết tắt STT Ký hiệu 1  U  User  Người dùng  2  I  Item  Sản phẩm  3  R  Rating  Đánh giá  4  IR  Information Retrieval  Thu thập thông tin  5  IF  Information Filtering  Lọc thông tin  6  RS  Recommender Systems  Hệ thống khuyến nghị  7  CF  Collaborative Filtering  Lọc cộng tác  8  KNN  K-nearest neighbor  K-hàng xóm gần nhất  9  RMSE  Root Mean Square Error  Hàm sai số bình phương trung bình  10  MAE  Mean absolute error  Sai số tuyệt đối trung bình  11  MF  Matrix Factorization  Ma trận thừa số  12  GD  Gradient descent  Giảm độ lệch  13  SGD  Stochastic gradient descent  Giảm độ lệch ngẫu nhiên        Diễn giải Tiếng Việt 4    Danh mục bảng và biểu đồ Bảng 2.1: Ví dụ 1 về người dùng đánh giá sản phẩm ................................................................ 17  Bảng 2.2: Ví dụ 2 về người dùng đánh giá sản phẩm ................................................................ 20  Bảng 2.3: Ví dụ 3 về người dùng đánh giá sản phẩm ................................................................ 23  Bảng 2.4: Ma trận đánh giá dày đặc ........................................................................................... 32  Bảng 2.5: Ma trận đánh giá thưa thớt ......................................................................................... 32  Bảng 2.6: So sánh giữa GD và SGD .......................................................................................... 43  Bảng 3.1: Định dạng các bộ dữ liệu huấn luyện và kiểm tra của Movielens ............................. 48  Bảng 3.2: Giá trị RMSE và RMSEtb thực nghiệm trên tập dữ liệu Movielens .......................... 50  Danh mục hình ảnh Hình 1.1: Mô hình hệ thống lọc thông tin .................................................................................... 9  Hình 1.2: Một ví dụ về mô hình khuyến nghị sản phẩm ............................................................ 10  Hình 1.3: Mô hình kỹ thuật lọc dựa theo nội dung .................................................................... 12  Hình 2.1: Mô hình đồ thị tính khoảng cách Manhattan .............................................................. 18  Hình 2.2: Mô hình đồ thị tính khoảng cách Euclidean ............................................................... 19  Hình 2.3: Mô hình đồ thị tính hệ số tương quan Pearson ........................................................... 22  Hình 2.4: Mô hình đồ thị tính hệ số tương tự Cosine ................................................................. 24  Hình 2.5: Phương pháp tiếp cận vùng lân cận ............................................................................ 30  Hình 2.6: Định hướng người dùng đối với phim ảnh ................................................................. 31  Hình 2.7: Phương pháp ma trận thừa số ..................................................................................... 35  Hình 2.8: Mô hình phương pháp Gradient descent .................................................................... 36  Hình 2.9: Đồ thị biểu thị thuật toán SGD thử nghiệm trên tập dữ liệu của Netflix ................... 42    5    MỤC LỤC Lời cam đoan .............................................................................................................................. 1  Lời cảm ơn .................................................................................................................................. 2  Bảng các ký hiệu và chữ viết tắt ................................................................................................ 3  Danh mục bảng và biểu đồ ........................................................................................................ 4  Danh mục hình ảnh .................................................................................................................... 4  Mở đầu ......................................................................................................................................... 7  CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ HỆ THỐNG KHUYẾN NGHỊ .................. 9  1.1. Khái niệm chung: ............................................................................................................ 9  1.1.1. Lọc thông tin (Information Filtering _IF)............................................................... 9  1.1.2. Hệ thống khuyến nghị (Recommender System) .................................................... 10  1.1.3. Giới thiệu bài toán về hệ thống khuyến nghị: ...................................................... 11  1.2. Các kỹ thuật lọc cho hệ thống khuyến nghị [4] ............................................................ 11  1.2.1. Kỹ thuật lọc dựa theo nội dung: ........................................................................... 12  1.2.2. Kỹ thuật lọc cộng tác  (Collaborative Filtering) ................................................... 12  1.2.3, Kỹ thuật Hybrid ..................................................................................................... 13  1.3. Các phương pháp lọc cộng tác ..................................................................................... 13  1.3.1, Lọc cộng tác dựa vào bộ nhớ ................................................................................. 14  1.3.2, Lọc cộng tác dựa vào mô hình (Model-Based Collaborative Filtering) .............. 14  CHƯƠNG 2: KỸ THUẬT LỌC CỘNG TÁC ....................................................................... 16  2.1.  Giới thiệu bài toán lọc cộng tác ............................................................................... 16  2.2.  Các phương pháp tính độ tương tự giữa các người dùng ..................................... 16  2.2.1.  Khoảng cách Manhattan.................................................................................. 16  2.2.2.  Khoảng cách Euclidean. ................................................................................... 18  2.2.3.  Hệ số tương quan Pearson. .............................................................................. 20  2.2.4.  Hệ số tương tự Cosine. ..................................................................................... 22  2.3.  Phương pháp cải tiến K-hàng xóm gần nhất (k-nearest neighbor) ..................... 24  2.3.1  Thuật toán KNN dựa trên người dùng. ............................................................ 25  2.3.2  Thuật toán KNN dựa trên sản phẩm: ............................................................... 27  2.4.  Mô hình nhân tố ẩn. ................................................................................................. 29  2.4.1  Phương pháp tiếp cận vùng lân cận (the neighborhood approach) .............. 29  2.4.2  Mô hình nhân tố ẩn (latent factor models) [3] .................................................. 30  2.4.2.1. Cơ sở lý thuyết ................................................................................................. 30  2.4.2.2. Bài toán: ........................................................................................................... 31  2.4.3. Phương pháp ma trận thừa số (Matrix Factorization Methods) [6] ................... 32  2.4.4. Thuật toán gradient descent ngẫu nhiên. ............................................................. 35  2.4.4.1. Thuật toán Gradient descent (GD) ................................................................ 35  2.4.4.2. Thuật toán gradient descent ngẫu nhiên ....................................................... 37  2.4.4.3. Thuật toán SGD dùng cho phân tích ma trận (ma trận thừa số) ............... 41    6    2.4.4.4. So sánh giữa thuật toán GD và SGD ............................................................. 43  2.5. Tiêu chuẩn đánh giá ...................................................................................................... 44  2.5.1. Mean absolute error (MAE) .................................................................................. 44  2.5.2. Root mean square error (RMSE) .......................................................................... 44  CHƯƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ VỚI DỮ LIỆU PHIM ẢNH .................. 46  3.1. Dữ liệu thực nghiệm. ..................................................................................................... 46  3.1.1. Tập dữ liệu thực nghiệm. ....................................................................................... 46  3.1.2. Thông tin chi tiết về định dạng của bộ dữ liệu của Movielens[15] ....................... 47  3.2.  Phương pháp thực nghiệm ...................................................................................... 49  3.2.1. Môi trường thực nghiệm ........................................................................................ 49  3.2.2. Phương pháp tiến hành thực nghiệm ................................................................... 49  3.3. So sánh và đánh giá kết quả thực nghiệm ................................................................... 50  3.3.1. Kết quả thực nghiệm .............................................................................................. 50  3.3.2. So sánh và đánh giá ................................................................................................ 52  3.3.2.1. Các phương pháp cơ sở ................................................................................... 52  3.3.2.2. Thuật toán SGD ............................................................................................... 52  KẾT LUẬN ............................................................................................................................... 54  TÀI LIỆU THAM KHẢO ....................................................................................................... 55                        7    Mở đầu   Tương tác cá nhân là hoạt động/ sự việc diễn ra trên toàn thế giới, thậm chí có từ  hàng  trăm  năm  trước  cho  đến ngày  nay. Những  năm 1990, tương  tác  cá  nhân ít  nhiều  cũng đã có mặt. Theo thường lệ, khi đi vào một cửa hàng sách quen thuộc, chủ hàng sẽ  chào  đón  như:  “Có  báo  mới  ngày  hôm  nay  đấy!”,  chủ  hàng  biết  rằng  khách  hàng  của  mình  muốn  điều  gì  khi  đến  đây.  Hoặc  chủ  hàng  có  thể  giới  thiệu  cho  một  vài  quyển  sách mà khách hàng của mình có thể quan tâm dựa trên những sở thích của khách. Hoặc  khi đi vào quán nước quen, người phục vụ sẽ hỏi: “Như thường lệ chứ?”    Khoảng 30 năm về trước, khi bạn muốn mua chiếc tivi ở cửa hàng điện máy thì  có vài sự lựa chọn phổ biến cho bạn: Panasonic và Samsung hay LG. Những năm sau  đó, bạn có nhiều sự lựa chọn phong phú hơn, bạn chọn hãng Samsung thì trong đó còn  nhiều lựa chọn như: LED hay LCD, bao nhiêu inch?…    Hàng ngày có hàng trăm bài hát được thu âm, hàng trăm đầu sách được xuất bản  trên thế giới, trong khi đó các cửa hàng chỉ có giới hạn các đầu sách hoặc các bài hát,  các bộ phim… Từ đó, các dịch vụ trực tuyến được ra đời và đáp ứng nhu cầu ngày càng  cao của người dùng.    Cho đến ngày nay, sự tương tác cá nhân vẫn luôn tồn tại, thậm chí bạn có hàng  triệu  sự  lựa  chọn.  Mỗi  giây  các  phương  tiện  truyền  thông  được  thêm  vào  mạng.  Mỗi  phút 100 tập tin mới có sẵn trên usenet.  24/24 giờ video được tải lên YouTube. Mỗi giờ  180 cuốn sách mới được xuất bản. Mỗi ngày càng có thêm nhiều lựa chọn các sản phẩm  để mua trong thế giới thực.    Bạn muốn mua một số bài nhạc?  iTunes có khoảng 11 triệu bài hát để lựa chọn  và họ đã bán được 16 tỷ bài hát  vào tháng 10 năm 2011. Nếu bạn muốn nhiều hơn sự  lựa chọn thì có thể đi đến Spotify với 15 triệu bài hát. Bạn muốn mua một cuốn sách,  Amazon cung cấp hơn 2 triệu cuốn sách để bạn lựa chọn.    Trong cuộc sống của chúng ta ngày nay, với sự phát triển không ngừng của công  nghệ thông tin, nguồn thông tin quá phong phú làm cho bạn không có đủ thời gian để  xem xét lựa chọn tất cả các cuốn sách, phim, tạp chí hay bài hát… bạn không biết mình  nên xem phim gì, đọc cuốn sách nào phù hợp với sở thích, nhu cầu của bản thân.     Vấn đề cấp thiết  đặt  ra  là cần  một  hệ thống hỗ  trợ  người  dùng chọn  lựa  những  sản  phẩm  phù  hợp  với  nhu  cầu  của  người  dùng,  từ  đó  hệ  thống  khuyến  nghị  được    8    nghiên cứu và phát triển không ngừng nhằm đạt hiệu quả nhất trong việc tương tác với  người dùng. Hệ thống khuyến nghị (Recommender Systems - RS) là giải pháp hiệu quả  nhất giải quyết vấn đề trên.     Chính  vì  vậy  trong  luận  văn  này,  chúng  tôi  xin  được  trình  bày  về  hệ  thống  khuyến nghị. Trong phạm vi luận văn, chúng tôi tập trung nghiên cứu về kỹ thuật lọc  cộng tác và phân tích các phương pháp cơ bản để tìm một người hoặc một nhóm người  gần nhất với người dùng hiện tại cần khuyến nghị. Để giảm thiểu sai số trong dự đoán  chúng tôi trình bày nghiên cứu của mình về phương pháp ma trận thừa số cụ thể hơn là  thuật toán gradient descent ngẫu nhiên. Nội dung chính của luận văn này được chia làm  3 chương:  Chương 1: Giới thiệu tổng quan về hệ thống khuyến nghị  Chương 2: Kỹ thuật lọc cộng tác  Chương 3: Thực nghiệm và đánh giá với dữ liệu phim ảnh    Trong  chương 1, chúng  tôi  đi  tìm  hiểu  chung  về hệ  thống  khuyến  nghị,  các kỹ  thuật lọc thông tin trong hệ thống khuyến nghị: lọc dựa vào nội dung, lọc cộng tác và kỹ  thuật  kết  hợp  Hybrid, các  phương  pháp  lọc  cộng  tác  như:  Lọc  dựa  vào  bộ  nhớ  và  lọc  dựa vào mô hình. Trong chương 2, chúng tôi trình bày chi tiết hơn về kỹ thuật lọc cộng  tác, các phương pháp tính độ tương tự giữa các người dùng, phương pháp ma trận thừa  số, thuật toán gradient descent ngẫu nhiên và các tiêu chuẩn đánh giá dự đoán. Chương  3, chúng tôi tiến hành thực nghiệm trên bộ dữ liệu của Movielens với 100.000 đánh giá,  sau đó dựa vào kết quả thực nghiệm để đánh giá, phân tích và so sánh tính hiệu quả của  từng phương pháp và thuật toán đã nêu trong chương 2.    9    CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ HỆ THỐNG KHUYẾN NGHỊ 1.1. Khái niệm chung: 1.1.1. Lọc thông tin (Information Filtering _IF)   Hình 1.1: Mô hình hệ thống lọc thông tin Giảm quá tải thông tin là mục tiêu chính của lọc thông tin (Information Filtering _IF) và nó đã được công nhận là một trong những ưu tiên trong việc phát triển hệ thống  thông  tin  dựa  trên  web  hiện  nay. Cung  cấp các  tài  liệu  có  liên  quan  dựa  trên  sở  thích  khách hàng. Công nghệ khuyến nghị được trình bày như là một mô hình mới của sự tìm  kiếm nơi mà các mặt hàng có liên quan tìm ra người sử dụng thay vì người sử dụng tìm  kiếm  chúng. Xu  hướng  mới trong  công nghệ  thông tin  như  mạng  xã hội  và  thiết  bị  di    10    động  đang  thực  hiện  nghiên  cứu  cá  nhân  được  ưu  tiên  hàng  đầu.  Nghiên  cứu  khách  hàng và tiếp thị có một truyền thống lâu đời. Với những tiến bộ trong công nghệ thông  tin,  nó  đã  phát  triển  và  ngày  càng  tinh  vi  mang  lại  hiệu  quả  cho  các  hệ  thống  trực  tuyến. Lọc  cộng  tác,  hệ  thống  khuyến  nghị,  hệ  thống  trợ  giúp  cá  nhân,  lọc  xã  hội,  hệ  thống khai thác dữ liệu xã hội, và các hệ thống thích nghi người dùng có thể được gọi  chung là hệ thống lọc thông tin (IF ). Ngày nay, hệ thống lọc thông tin ở khắp mọi nơi,  trong mọi ngành công nghiệp và dịch vụ, từ tiếp thị cho sức khỏe, du lịch, giáo dục, giải  trí,...  Vậy, hệ thống lọc thông tin là một hệ thống loại bỏ thông tin dư thừa hoặc không  mong muốn từ một luồng thông tin sử dụng tự động trên máy vi tính  Mục tiêu chính của nó là quản lý của tình trạng quá tải thông tin và tăng tỷ lệ ngữ  nghĩa của tín hiệu trên nhiễu. Để thực hiện các hồ sơ này được so sánh với một số đặc  tính tham khảo.  1.1.2. Hệ thống khuyến nghị (Recommender System)   Hệ thống khuyến nghị (Recommender System)[7] là một loại hình cụ thể của kỹ  thuật  lọc  thông  tin  (như  phim  ảnh,  âm  nhạc,  trang  web,  tin  tức)  mà  người  dùng  quan  tâm. Nó rất quan trọng cho sự thành công của thương mại điện tử và ngành công nghiệp  CNTT hiện nay, và dần dần trở nên phổ cập trong các ứng dụng khác nhau (ví dụ như  dự án Netflix, Google tin tức, Amazon). Là một hệ thống khuyến nghị chuyên nghiệp  xây  dựng  dựa  trên  hồ  sơ  quá  khứ  của  người  dùng,  hệ  thống  so  sánh  hồ  sơ  của  người  dùng  với  một  số  đặc  điểm  tài  liệu  tham  khảo,  và  tìm  cách  để  dự  đoán  “đánh  giá”  mà  người dùng sẽ cung cấp cho một mục mà người dùng đó vẫn chưa đánh giá . Trong hầu  hết các trường hợp, hệ thống khuyến nghị tương ứng với một vấn đề khai thác dữ liệu  quy mô lớn. Là hệ thống có khả năng tự động phân tích, phân loại, lựa chọn và cung cấp  cho người dùng những thông tin, hàng hóa hay dịch vụ mà họ quan tâm.    Hình 1.2: Một ví dụ về mô hình khuyến nghị sản phẩm   11    1.1.3. Giới thiệu bài toán về hệ thống khuyến nghị:   Cho  U  là  tập  tất  cả  người  dùng;  P  là  tập  tất  cả  các  sản  phẩm(sách,  bài  hát,  phim…) có thể tư vấn. Tập P có thể rất lớn, từ hàng trăm ngàn đến hàng triệu sản phẩm.  Tập U trong một số trường hợp cũng có thể lên tới hàng triệu người dùng. Hàm r(u,p) là  những đánh giá mức độ phù hợp (xếp hạng) của sản phẩm p với người dùng u, r: UxP  R. Với mỗi người dùng u ∈ U cần tìm sản phẩm p’  ∈ P sao cho hàm r(u,p’) đạt giá trị  lớn nhất: ∀u ∈U,p’=arg maxp∈ P r(u,p)    Trong hệ thống khuyến nghị, những đánh giá  được thể hiện bằng các hình thức  thông  thường  như:  thích  và  không  thích  (hình  bàn  tay  với  ngón  trỏ:  youtube.com),  số  sao (thường từ 1- 5 sao)…  1.2. Các kỹ thuật lọc cho hệ thống khuyến nghị [4] Trong việc lựa chọn sản phẩm hoặc dịch vụ (gọi chung là Item), người dùng thường gặp  phải những khó khăn là:    Lượng  Item:  Mỗi  ngày,  có  hàng  triệu  thông  tin  được  đăng  tải  lên  internet  mỗi  ngày, người dùng không biết mình nên và không nên sử dụng Item nào?    Thông  tin  về  Item:  do lượng  Item  là  vô  cùng lớn, nên User  không  thể  tìm  hiểu  được tất cả các Item về nội dung, chức năng cũng như Item có phù hợp với nhu  cầu của user không?...  Gợi ý đặt ra để giải quyết các vấn đề khó khăn trên là:   Khai thác những khía cạnh cạnh liên quan đến nội dung thông tin sản phẩm hoặc  người dùng đã từng sử dụng hay truy nhập trong quá khứ để khuyến nghị. Đây là  kỹ thuật lọc dựa theo nội dung (Content-Based Filtering)   Lựa  chọn  dựa  trên  ý  kiến  hay  lời  khuyên  của  những  người  dùng  khác  về  các  Item. Hệ thống khuyến nghị áp dụng các thuật toán tận dụng các gợi ý được cung  cấp  bởi  một  cộng  đồng  người  dùng  tương  tự  sau  đó  cung  cấp  cho  người  dùng  đang hoạt động (người đang tìm kiếm các đề xuất). Phương pháp này được gọi là  lọc cộng tác (Collaborative Filtering _CF)  So với lọc theo nội dung, lọc cộng tác có một số ưu điểm như đơn giản trong cài đặt và  có thể lọc được mọi loại thông tin hay hàng hoá mà không cần phải biểu diễn dưới dạng  văn bản.    12    1.2.1. Kỹ thuật lọc dựa theo nội dung: Với kỹ thuật khuyến nghị dựa trên nội dung[10], mức độ phù hợp r(u,p) của sản phẩm  phẩm p với người dùng u được đánh giá dựa trên mức độ phù hợp r(u,pj), trong đó pj    P và tương tự như p. Ví dụ, để gợi ý một bộ phim cho người dùng u, hệ thống tư vấn sẽ  tìm  các  đặc  điểm  của  những  bộ  phim  từng  được  u  đánh  giá  cao  (như  diễn  viên,  đạo  diễn…); sau đó chỉ những bộ phim tương đồng với sở thích của c mới được giới thiệu.  Hướng tiếp cận dựa trên nội dung bắt nguồn từ những nghiên cứu về thu thập thông  tin  (IR  -  information  retrieval)  và  lọc  thông  tin  (IF  -  information  filtering).  Do  đó,  rất  nhiều hệ thống dựa trên nội dung hiện nay tập trung vào tư vấn các đối tượng chứa dữ  liệu text như văn bản, tin tức, website… Những tiến bộ so với hướng tiếp cận cũ của IR  là do việc sử dụng hồ sơ về người dùng (chứa thông tin về sở thích, nhu cầu…). Hồ sơ  này được xây dựng dựa trên những thông tin được người dùng cung cấp trực tiếp (khi  trả lời khảo sát) hoặc gián tiếp (do khai phá thông tin từ các giao dịch của người dùng).    Hình 1.3: Mô hình kỹ thuật lọc dựa theo nội dung 1.2.2. Kỹ thuật lọc cộng tác  (Collaborative Filtering)   Kỹ thuật lọc cộng tác  (Collaborative Filtering)  dựa trên nguyên tắc hoạt động là  các khuyến nghị dựa trên ảnh hưởng của nhiều người khác nhau, các cộng tác của nhiều  người  này  sẽ  trở  thành  khuyến  nghị.  Khác  so  với  kỹ  thuật  lọc  cộng  tác  dựa  trên  nội  dụng, hệ thống cộng tác dự đoán mức độ phù hợp r(u,p) của một sản phẩm p với người  dùng u dựa trên mức độ phù hợp r(ui, p) giữa người dùng ui và p, trong đó ui là người có  cùng sở thích với u. Ví dụ, để gợi ý một bộ phim cho người dùng u, đầu tiên hệ thống    13    cộng tác tìm những người dùng khác có cùng sở thích phim ảnh với u. Sau đó, những bộ  phim được họ đánh giá cao sẽ được dùng để tư vấn cho u. Chi tiết cụ thể về kỹ thuật này  sẽ được tôi trình bày trong chương 2.  1.2.3, Kỹ thuật Hybrid   Kỹ thuật Hybrid[9] là phương pháp kết hợp của cả hai kỹ thuật trên. Một số ứng  dụng  kết  hợp  cả  hai  kỹ  thuật  lọc  cho  hệ  thống  khuyến  nghị  dựa  theo  nội  dung  và  lọc  cộng tác. Mỗi kỹ thuật đều có những ưu điểm và nhược điểm riêng, do đó khi kết hợp  có thể khắc phục những hạn chế của từng kỹ thuật. Nó cải thiện hiệu suất dự đoán, quan  trọng  hơn,  từ  đó  vượt  qua  những  vấn  đề  lọc  thông  tin  như  thưa  thớt  và  mất  thông  tin. Tuy  nhiên,  sự  kết  hợp  của  hai  kỹ  thuật  để  thực  hiện  sẽ  gia  tăng  phức  tạp  và  giá  thành  cao.  Thông  thường  hầu  hết  các  hệ  thống  khuyến  nghị  thương  mại  là Hybrid,  ví  dụ: hệ thống khuyến nghị tin tức của Google  Thông thường có 4 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 với nhau: Có hai  kịch bản cho trường hợp này là:  + 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ọn một phương pháp cho kết quả tốt hơn (ví dụ:  Hệ thống Dailylearner)   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.   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  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.  1.3. Các phương pháp lọc cộng tác   Với số lượng quá lớn các sản phẩm có trên internet thì thông thường một người  dùng  chỉ  đánh  giá  hữu  hạn  m  sản  phẩm  (với  m  sản  phẩm  được  đánh  giá  nhỏ  hơn  rất  nhiều so với tập M sản phẩm). Khó khăn đặt ra là dự đoán đánh giá một người dùng cho  tập M sản phẩm là điều rất khó khăn, hơn nữa tập M sản phẩm luôn luôn thay đổi và  theo thời gian thì ngày càng tăng lên. Ngoài ra để dự đoán đánh giá của N người dùng  với  M  sản  phẩm  sẽ  gây  ra  tốc  độ  xử  lý  chậm  =>  mất  nhiều  thời  gian,  lãng  phí  tài    14    nguyên…  Một  trong những  giải pháp  đặt  ra  để  giải  quyết  vấn  đề trên là: kỹ thuật  lọc  cộng tác (Collaborative Filtering)     Lọc  cộng  tác  cho  hệ  thống  khuyến  nghị  được  tiếp  cận  theo  hai  phương  pháp  chính:  Lọc  cộng  tác  dựa  vào  bộ  nhớ  (Memory-Based  Collaborative  Filtering)  và  lọc  cộng tác dựa vào mô hình (Model-Based Collaborative Filtering) . Điểm khác biệt quan  trọng trong hai phương pháp tiếp cận là: Lọc dựa vào bộ nhớ tiến hành xây dựng đồng  thời mô hình huấn luyện và mô hình dự đoán. Ngược lại, lọc dựa vào mô hình xây dựng  mô hình huấn luyện và mô hình dự đoán độc lập nhau. So với lọc cộng tác dựa vào mô  hình, lọc cộng tác dựa vào bộ nhớ được áp dụng rộng rãi hơn do tính hiệu quả, đơn giản  và có độ chính xác khá cao.  1.3.1, Lọc cộng tác dựa vào bộ nhớ   Phương pháp lọc cộng tác dựa vào bộ nhớ  [11] thường sử dụng toàn bộ dữ liệu đã  có của người dùng để dự đoán đánh giá của người đó về một sản phẩm mới. Là phương  pháp có khả năng đưa trực tiếp dữ liệu mới vào bảng dữ liệu nên nó đạt khá nhiều thành  công khi được áp dụng vào các ứng dụng thực tế. Đặc biệt, kỹ thuật này phát huy tính  hiệu quả cao trong các hệ thống trực tuyến (là nơi luôn có dữ liệu mới được cập nhật)  thường đưa ra các dự đoán chính xác hơn.    Lọc cộng tác dựa vào bộ nhớ (Memory-Based Collaborative Filtering) được thực  hiện theo hai phương pháp chính: Lọc dựa vào người dùng (User-Based Collaborative  Filtering) và lọc dựa vào sản phẩm (Item-Based Collaborative Filtering) . Hiệu quả của  các phương pháp lọc dựa vào bộ nhớ phụ thuộc vào độ đo tương tự giữa các cặp người  dùng hoặc sản phẩm. Phương pháp lọc cộng tác dựa vào bộ nhớ, tôi sẽ trình bày cụ thể  hơn trong chương 2.  1.3.2, Lọc cộng tác dựa vào mô hình (Model-Based Collaborative Filtering)   Phương pháp tiếp cận dựa trên mô hình [17] không sử dụng tất cả dữ liệu đã có để  đưa ra dự đoán, thay vào đó chúng nắm bắt thông tin trong từng bước giống như một sự  thỏa thuận về mô hình các sở thích người dùng. Các mô hình được phát triển bằng cách  sử dụng phương thức khai thác dữ liệu, thuật toán học máy để tìm mô hình dựa trên dữ  liệu  huấn  luyện. Chúng  được  sử  dụng  để  đưa  ra  dự  đoán  cho  dữ  liệu  thực  tế. Có  rất  nhiều thuật toán CF dựa trên mô hình như: mạng Bayes , mô hình phân nhóm , mô hình  ngữ nghĩa tiềm ẩn.    15      Ưu điểm của mô hình này là xử lý dữ liệu thưa thớt tốt hơn so với lọc dựa trên bộ  nhớ. Điều này giúp với khả năng mở rộng với các tập dữ liệu lớn, nó cải thiện hiệu suất  dự đoán. Những nhược điểm của phương pháp này là giá thành cao trong việc xây dựng  mô hình, cần phải có một sự cân bằng giữa hiệu suất và khả năng mở rộng dự đoán, có  thể bị mất thông tin hữu ích do mô hình giảm và một số mô hình có khó khăn trong việc  giải nghĩa các dự đoán.    16    CHƯƠNG 2: KỸ THUẬT LỌC CỘNG TÁC   Phương  pháp  khuyến  nghị  tôi  đang  xem  xét  trong  chương  này  được  gọi  là  lọc  cộng  tác.  Nó  được  gọi  là  cộng  tác  bởi  vì  nó  đưa  ra  các  khuyến  nghị  dựa  trên  những  người dùng khác trong thực tế, mọi người cộng tác để đưa ra khuyến nghị. Nguyên lý  hoạt động của hệ thống khuyến nghị là: giả sử để giới thiệu một cuốn sách cho bạn. Tôi  tìm  kiếm  những  người  sử  dụng  khác  của  trang  web  để  tìm  một  trong  số  đó  là  người  tương tự như bạn dựa trên những cuốn sách mà bạn và người sử dụng đó thích.   2.1. Giới thiệu bài toán lọc cộng tác Cho một tập hữu hạn gồm có N người dùng U = { u1,u2,…,uN }, một tập  gồm M sản phẩm P = { p1,p2,…,pM }. Mỗi sản phẩm pj ∈  P có thể là phim, ảnh, tạp  chí, tài liệu, sách, báo,hàng hóa, dịch vụ hoặc bất kỳ dạng thông tin nào mà người dùng  cần đến. Một ma trận R = ( rij ) với i = 1,…N ; j = 1,…,M thể hiện mối quan hệ giữa tập  người  dùng  U  và  tập  sản  phẩm  P. Trong  đó  rij  là đánh  giá  của  người  dùng  ui  cho  sản  phẩm pj.     Các giá trị rij nhận giá trị theo các hình thức: thu thập trực tiếp ý kiến đánh giá  của người dùng ui về sản phầm pj hoặc thu thập gián tiếp thông qua cơ chế phản hồi của  người dùng.     Gọi  ux  là  người  dùng  hiện  thời  cần  được  khuyến  nghị  sản  phẩm  py,  với  rxy=Ø  (nghĩa là người dùng ux chưa đánh giá hoặc chưa từng biết đến sản phẩm py). Bài toán  lọc cộng tác có nhiệm vụ dự đoán đánh giá rxy của người dùng ux với sản phẩm py. Từ  đó,  giới  thiệu  cho  người  dùng  ux  những  sản  phẩm  phù  hợp  nhất  dựa  trên  giá  trị  rxy,  những sản phẩm được khuyến nghị cho người dùng ux là những sản phẩm có đánh giá  cao.  2.2. Các phương pháp tính độ tương tự giữa các người dùng   Cho ui là người dùng hiện thời, ua là người dùng cần tính độ tương tự với người  dùng ui, rip là đánh giá của người dùng ui cho sản phẩm p và rap là đánh giá của người  dùng ua cho sản phẩm p. Với tập m sản phẩm là những sản phẩm mà người dùng ui và  người dùng ua cùng đánh giá.  2.2.1. Khoảng cách Manhattan   17      Một trong những cách đơn giản nhất để đo khoảng cách giữa hai điểm dữ liệu là  khoảng cách Manhattan[1].  Tính  độ  tương  tự  giữa  người  dùng  ua  và  ui  sử  dụng  phương  pháp  khoảng  cách  Manhattan được tính bằng công thức sau:  m d Manhattan  ua ,  ui    rip  rap p 1   Trong không gian 2 chiều, mỗi người dùng được đại diện bởi một điểm (x,y), tôi  sẽ  bổ  sung  thêm  subscript  cho  x  và  y  để  tham  khảo những  người  dùng  khác  nhau. Vì  vậy, ta có (x1,y1) và (x2,y2) lần lượt là các điểm dữ liệu thể hiện đánh giá của ua và  ui  cho 2 sản phẩm khác nhau x và y. Khi đó khoảng cách Manhattan được tính bằng công  thức sau:  | x1 - x2| + | y1 - y2 |  Cho bảng ví dụ 1 sau:    The Hobbit  Harry Potter  John   2  2  Peter  4  4  Bảng 2.1: Ví dụ 1 về người dùng đánh giá sản phẩm Khi  đó,  khoảng  cách  Manhattan  được  định  nghĩa  lại  và  biểu  diễn  trong  không  gian  2  chiều như sau:    18      Hình 2.1: Mô hình đồ thị tính khoảng cách Manhattan  dManhattan(Peter, John)=|2-4|+|2-4|=2+2=4   Giá trị khoảng cách giữa Peter và John khi áp dụng phương pháp tính khoảng  cách Manhattan là: dManhattan=4. Áp dụng tương tự phương pháp này để tính khoảng cách  với người dùng khác, sau đó sẽ chọn người dùng có giá trị khoảng cách nhỏ nhất với  người dùng hiện tại.  2.2.2. Khoảng cách Euclidean.    Ưu điểm rất rõ ràng khi sử dụng công thức tính khoảng cách Manhattan là tính  toán đơn giản và rất nhanh. Tuy nhiên, khoảng cách Euclidean[1] thay vì đi xung quanh  các khối thì bạn chỉ cần vẽ một đường thẳng giữa hai điểm dữ liệu và đo khoảng cách  giữa hai điểm bằng cách sử dụng định lý Pythagorean.    Công thức tính khoảng cách Euclidean tổng quát:  m d Euclidean  ua ,  ui   r p 1   ip  rap  2  
- Xem thêm -

Tài liệu liên quan