Bài giảng Nhập môn khai phá dữ liệu - Chương 6: Phân cụm dữ liệu và hệ thống tư vấn - Hà Quang Thụy

độ tương tự cực tiểu (complete link), cực đại (single link) ⚫ Một số phương pháp điển hình ❑ Phân ly theo trọng tâm Ví dụ: Chế độ, đặc điểm phân cụm web 37 ⚫ Hai chế độ ❑ Trực tuyến: phân cụm kết quả tìm kiếm người dùng ❑ Ngoại tuyến: phân cụm tập văn bản cho trước ⚫ Đặc điểm ❑ Chế độ trực tuyến: tốc độ phân cụm ▪ Web số lượng lớn, tăng nhanh và biến động lớn ▪ Quan tâm tới phương pháp gia tăng ❑ Một lớp quan trọng: phân cụm liên quan tới câu hỏi tìm kiếm ▪ Trực tuyến ▪ Ngoại tuyến [Carpineto09] Carpineto C., Osinski S., Romano G., Weiss D. (2009). A survey of web clustering engines, ACM Comput. Surv. , 41(3), Article 17, 38 pages. Ví dụ 38 Hệ thống tư vấn 39 ⚫ Khái niệm ❑ recommender systems / recommendation engines ❑ Hệ thống tư vấn / gợi ý / khuyến nghị / giới thiệu / v.v. ❑ Mục (item): sản phẩm/bài viết/trang web/bản nhạc/bộ phim/ con người / tổ chức / v.v. ❑ Hệ thống tư vấn là các công cụ phần mềm và kỹ thuật cung cấp các tư vấn về các mục có khả năng cao là hữu ích nhất đối với một người dùng đích. ❑ HT tư vấn “chủ động”, HT hỏi-đáp (question-answering) “bị động” ⚫ Ma trận hữu ích người dùng-mục ❑ Tập m người dùng U, tập n mục I ❑ Ma trận P nguyên cỡ mn ghi mức hữu ích của mục tới người dùng ❑ p(i,j) mức người dùng i đánh giá mục j hoặc “độ hữu ích của mục j đối với người dùng i” ❑ Giá trị p(i,j) đã biết (người dùng i đã đánh giá mục j) hoặc chưa biết (người dùng i chưa đánh giá mục j). Các vị trí có dấu “?” [Aggarwal16] Charu C. Aggarwal. Recommender Systems: The Textbook. Springer, 2016. Ví dụ 40 Hệ thống có thành phần tư vấn Ma trận hữu ích người dùng-mục So sánh lọc và phân lớp 41 [Aggarwal16] Hệ thống tư vấn: Tính chất 42 ⚫ Tính có liên quan ❑ Các mục tư vấn cần liên quan tới người dùng: biện minh ⚫ Tính mới lạ ❑ Tư vấn các mục người dùng chưa hoặc khó quan sát ❑ Tránh tư vấn lặp các mục có tính phổ biến ⚫ Tính “may mắn bất ngờ” ❑ Tạo ngạc nhiên cho người dùng ❑ Không chỉ là chưa quan sát được ⚫ Tính đa dạng gia tăng ❑ Các mục tư vấn cần đa dạng, tránh cùng thuộc một thể loại ❑ Lựa chọn tư vấn mục cùng thể loại theo các tư vấn khác nhau ⚫ Tính giải trình ❑ Nên có giải trình mục được tư vấn ❑ “tư vấn phim”: về đạo diễn, về diễn viên, về thể loại ưa chuộng của người dùng Kỹ thuật lọc trong hệ thống tư vấn 43 ⚫ Các kiểu kỹ thuật ❑ Một vài phân loại. Phân loại trên là phổ biến ❑ Dựa trên cộng tác, nội dung, tri thức, nhân khẩu học, kết hợp ⚫ Kỹ thuật lọc cộng tác ❑ Lọc cộng tác: Chỉ sử dụng ma trận hữu ích; “độc lập miền” ❑ 𝑆𝑢 là tập các mục đã được người dùng u đánh giá, 𝑆𝑖 là tập các người dùng đã đánh giá mục i. [Aggarwal16] Lọc cộng tác hướng người dùng 44 ❑ Xác định tập người dùng láng giềng tới người dùng đích 𝑆𝑢𝑣 = 𝑆𝑢 ∩ 𝑆𝑣 : tập mục cả hai người dùng u và v đã đánh giá N(u) là tập người dùng láng giềng của người dùng u ❑ Tính độ hữu ích của một mục với người dùng u ҧ𝑝𝑢 ( ҧ𝑝𝑣): trung bình đánh giá mục với người dùng u (v): mềm/cứng. ❑ Chọn các mục I có giá trị lớn nhất để tư vấn ❑ Độ đo cosin CV là không xem xét khác biệt u và v cho nên sử dụng độ đo Peason PC phổ biến hơn. Hai người u và v Hai mục Lọc cộng tác hướng mục và mô hình 45 ⚫ Lọc cộng tác hướng mục ❑ Tính độ tương tự giữa các mục 𝑆𝑖𝑗: tập người dùng đã đánh giá cả hai mục i và j ❑ Với mỗi mục i  𝑆𝑢, xác định 𝑄𝑖 𝑢 là tốp-k các mục  𝑆𝑢 tương tự cao nhất với mục i. ❑ Tính độ hữu ích của mục i ❑ Chọn các mục i  𝑆𝑢 có giá trị lớn nhất để tư vấn ⚫ Lọc cộng tác theo mô hình ❑ Lọc cộng tác theo mô hình: xây dựng mô hình mô tả mục tận dụng ít dữ liệu mô tả mục (tên/mã định danh người dùng + giá trị đánh giá của người dùng → một “từ khóa” mô tả mục) ❑ Phân biệt “lọc nội dung thực sự” nhiều dữ liệu mô tả đặc trưng Tổng hợp hệ thống tư vấn lọc cộng tác 46 Kỹ thuật lọc nội dung 47 ⚫ Giới thiệu. ❑ Dữ liệu dạng nội dung ❑ Giả thiết: mối quan tâm mục của người này ít liên quan tới người khác. Mối quan tâm của người theo tính chất của mục. ❑ Nhiều dữ liệu mô tả mục/người dùng. Mục: màu sắc, hình dạng, khối lượng, nhà sản xuất, v.v. Người dùng: đánh giá, hành vi, sở thích, bạn bè, v.v Khung khái quát hệ tư vấn lọc nội dung 48 [Gemmis15] Marco de Gemmis, Pasquale Lops, Cataldo Musto, Fedelucio Narducci, Giovanni Semeraro. Chapter 4. Semantics-Aware Content-Based Recommender Systems. In [Ricci15], pp. 119-159. Hoạt động hệ thống lọc dựa trên nội dung 49 ⚫ Ba thành phần ❑ Bộ phân tích nội dung, Bộ học hồ sơ người dùng, Thành phần lọc ⚫ Bộ phân tích nội dung ❑ Thu thập dữ liệu về các mục ❑ Tìm biểu diễn mục dưới dạng có cấu trúc ❑ Sử dụng kỹ thuật trích xuất đặc trưng (Chương 3) ❑ Cung cấp đầu vào cho Bộ học hồ sơ và Thành phần lọc ⚫ Bộ học hồ sơ ❑ Thu thập dữ liệu phản hồi của người dùng: bao gồm đánh giá ❑ Tổng quát hóa thành mô hình sở thích của người dùng ❑ Sử dụng kỹ thuật học máy ⚫ Thành phần lọc ❑ Đối sánh biểu diễn mục tiền năng với mô hình sở thích người dùng ❑ Độ liên quan và chọn các mục có liên quan nhất Học mô hình sở thích người dùng 50 ⚫ Từ phản hồi người dùng tới mô hình sở thích ❑ Biểu diễn các mục (qua Bộ phân tích) và phản hồi người dùng ❑ Tập ví dụ học nhị phân: thích / không thích ❑ Học máy mô hình sở thích người dùng Phương thức đánh giá hiệu năng HTV 51 ⚫ Người dùng nghiên cứu ❑ Huy động tập người dùng: Dữ liệu tương tác người dùng-hệ thống ❑ Lợi thế: hệ thống chạy thực tế. Hạn chế: tuyển dụng người dùng ⚫ Trực tuyến ❑ Chọn người dùng thực làm việc với hệ thống ❑ Độ đo tỷ lệ chuyển đổi (conversion rate): tần suất người dùng chọn mục do hệ thống đề xuất ❑ Chọn 1 từ 2 thuận toán: kiểm thử A/B (A/B test) chọn ngẫu nhiên hai nhóm người dùng A, B, A một thuật toán, B một thuật toán, như nhau về điều kiện và về cùng khoảng thời gian. ❑ Lợi thế: chọn ngẫu nhiên người dùng → không có thiên vị. Hạn chế: không đủ người dùng (khi hệ thống mới làm việc) ⚫ Ngoại tuyến ❑ Sử dụng bộ dữ liệu lịch sử cho đánh giá: Netflix Prize ❑ Lợi thế: có sẵn khung và độ đo đánh giá chuẩn ❑ Hạn chế: dữ liệu quá khứ+hiện tại không phản ánh xu thể sau này ❑ Chấp nhận rộng rãi và phương pháp phổ biến nhất Đánh giá hiệu năng hệ tư vấn: Độ đo 52 Hướng phân lớp Hướng hồi quy ⚫ Hướng phân lớp. ❑ Hồi tưởng/chính xác: nói chung và k liên quan nhất ⚫ Hướng hồi quy. ❑ sai số toàn phương trung bình (mean squared error: MSE), sai số quân phương trung bình (root mean squared error: RMSE, là căn bậc hai của MSE), sai số quân phương trung bình chuẩn hóa (normalized RMSE: NRMSE), sai số tuyệt đối trung bình (mean- absolute-error: MAE), sai số tuyết đối trung bình chuẩn hóa (normalized MAE: NMAE) Tư vấn xã hội 53 ⚫ Phương tiện xã hội ❑ Dữ liệu phương tiện xã hội: hai chiều bảng trên ❑ Hiện diện tính xã hội, phong phú phương tiện xã hội ❑ Từ trình bày, tự tiết lộ cá nhân ⚫ Tư vấn xã hội ❑ Dữ liệu phương tiện xã hội: hai chiều bảng trên ❑ Định nghĩa hẹp: sử dụng mối quan hệ xã hội. ❑ Định nghĩa rộng: sử dụng mọi dữ liệu từ phương tiện xã hội Tư vấn vị trí di động 54 ❑ Ba thành phần: Hồ sơ người dùng, ngữ cảnh và động cơ HT tư vấn ❑ Đầu ra: máy di động Tư vấn nhóm người dùng 55 ⚫ Nhóm và tích hợp ❑ Kiểu nhóm: chính thức, không thường xuyên, ngẫu nhiên, tự động ❑ Tư vấn cá nhân → tư vấn nhóm ❑ Tích hợp dự đoán và tích hợp mô hình