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

m mục tiêu
 ❑ PAM: Partition Around Mediods
⚫ Input và Output
 ❑ Input: D = {d} tập dữ liệu, độ đo tương tự sim, k>0 
 ❑ Output: Tập các cụm củaD 
⚫ Thuật toán PAM
 1. Chọn ngẫu nhiên k phần từ trong D làm đại diện ci.
 2. Gán các d D vào Cd mà d tương tự cd nhất trong các ci.
 3. Chọn ngầu nhiên phần từ o không phải là đại diện ccụm j.
 4. Tính hàm chi phí (gia số hàm mục tiêu) nếu thay ci bằng o
 5. Nếu <0 thay ci bằng o.
 6. Quy lại bước 2 cho đến khi quá trình hội tụ (không còn thay 
 thế phần tử đại diện được). 22
 4. Phân cụm phân cấp
⚫ HAC: Hierarchical agglomerative clustering
⚫ Một số độ đo phân biệt cụm
 ❑ Độ tương tự hai dữ liệu
 ❑ Độ tương tư giữa hai cụm
 ⚫ Độ tương tự giữa hai đại diện
 ⚫ Độ tương tự cực đại giữa hai dữ liệu thuộc hai cụm: single-link
 ⚫ Độ tương tự cực tiểu giữa hai dữ liệu thuộc hai cum: complete-link
 ⚫ Độ tương tự trung bình giữa hai dữ liệu thuộc hai cum
⚫ Sơ bộ về thuật toán
 ❑ Đặc điểm: Không cho trước số lượng cụm k, cho phép đưa ra các
 phương án phân cụm theo các giá trị k khác nhau
 ❑ Lưu ý: k là một tham số  “tìm k tốt nhất”
 ❑ Tinh chỉnh: Từ cụ thể tới khái quát
 23
a. Phân cụm phân cấp từ dưới lên
⚫ Input và Output
 ❑ Input: D = {d} tập dữ liệu, độ đo tương tự sim và có thể k>0 và q>0
 ❑ Output: G: Tập các cụm phân cấp của D
⚫ Thuật toán
 1. G  {{d}| d D} // khởi tại G là tập các cụm chỉ một dữ liệu
 2. Nếu |G|<k thì dừng //đủ lượng cụm tối thiếu
 3. Tìm hai cụm iS và Sj sao cho (I, j) = arg max (u,v) sim (Su+, Sv+) // 
 tìm hai cụm tương tự nhau nhất
 4. Nếu sim(Si, Sj)<q thì dừng //độ tương tự các cụm quá bé
 5. Loại bỏ iS , Sj khỏi G 
 6. G G (SiSj)
 7. Quay lại bước2 
⚫ Giải thích
 ❑ G là tập các cụm trong phân cụm
 ❑ Điều kiện |G| < k có thể thay thế bằng |G|=1 24
Phân cụm phân cấp từ dưới lên
⚫ Hoạt động HAC
 ❑ Cho phép với mọi k
 ❑ Chọn phân cụm theo “ngưỡng” về độ tương tự
 25
 HAC với các độ đo khác nhau
⚫ Ảnh hưởng của các độ đo
 ❑ Trên: Hoạt động thuật toán khác nhau theo các độ đo khác nhau: 
 độ tương tự cực tiểu (complete-link) có tính cầu hơn so với cực đại
 ❑ Dưới: Độ tương tự cực đại (Single-link) tạo cụm chuỗi dòng 26
 b. Phân cụm phân cấp BIRCH
⚫ Balanced Iterative Reducing Clustering Using 
 Hierarchies
 ❑ Tính khả cỡ: Làm việc với tập dữ liệu lớn
 ❑ Tính bất động: Gán không đổi đối tượng– > cụm
⚫ Khái niệm liên quan
 ❑ Đặc trưng phân cụm CF: tóm tắt của cụm
 ⚫ CF = , n: số phần tử, LS: vector tổng các thành phần dữ 
 liêu; SS : vector tổng bình phương các thành phần các đối tượng
 ⚫ . Khi ghép cụm không tính lại các tổng 
 ❑ Cây đặc trưng phân cụm CF Tree
 ⚫ Một cây cân bằng
 ⚫ Hai tham số: bề rộng b và ngưỡng t
 ⚫ Thuật toán xây dựng cây
 27
BIRCH: Năm độ đo khoảng cách
 28
 Cây đặc trưng phân cụm CF Tree
❑ Mỗi nút không là lá có
 nhiều nhất là B cành
❑ Mỗi nút lá có nhiều
 nhất L đặc trưng phân
 cụm đảm bảo ngưỡng
 T
❑ Cỡ của nút được xác
 định bằng số chiều
 không gian dữ liệu và
 tham số P kích thước
 trang bộ nhớ
 29
 Chèn vào CF Tree và BIRCH
⚫ Cây ban đầu rỗng
⚫ Chèn một “cụm” a vào cây
 ❑ Xác định lá thích hợp: Duyệt từ gốc xuống một cách đệ quy để tới nút 
 con gần a nhất theo 1 trong 5 khoảng cách nói trên
 ❑ Biến đổi lá: Nếu gặp lá L1 gần a nhất, kiểm tra xem L1 có“ hấp thụ“ được 
 a không (chưa vượt ngưỡng); nếu có thì đặc trưng CF của L1 bổ sung;
 Nếu không, tạo nút mới cho a; nếu không đủ bộ nhớ cho lá mới thì cần 
 chia lá cũ 
 ❑ Biến đổi đường đi tới lá khi bổ sung phần tử mới
 ❑ Tinh chỉnh việc trộn: 
 Tian Zhang, Raghu Ramakrishnan, Miron Livny (1996). BIRCH: An Efficient Data
 Clustering Method for Very Large Databases, SIGMOD Conference 1996: 103-114 30
 Các thuật toán phân cụm khác
 ❑ Nghiên cứu giáo trình
⚫ Phân cụm phân cấp từ trên xuống DIANA
 ❑ Đối ngẫu phân cụm phân cấp từ trên xuống: phần tử khác biệt -> cụm khác biệt S, 
 ❑ Thêm vào S các phần tử có d > 0
⚫ Phân cụm phân cấp ROCK
 ❑ RObust Clustering using linKs: xử lý dữ liệu rời rạc, quyết định “gần” theo
 tập phần tử láng giềng sim (p, q) > >0.
⚫ Phân cụm dựa trên mật độ DBSCAN
 ❑ Density-Based Spatial Clustering of Application with Noise
 ❑ #-neighborhood: vùng lân cận bán kính #
 ❑ | #-neighborhood| > MinPts gọi đối tượng lõi
 ❑ P đạt được trực tiếp theo mật độ từ q nếu q là đối tượng lõi và p thuộc #-
 neighborhood của q. 
 ❑ Đạt được nếu có dãy mà mỗi cái sau là đạt được trực tiếp từ cái trước
⚫ Phân cụm phân cấp dựa trên mô hình
 ❑ Làm phù hợp phân bố cụm với mô hình toán học
 ❑ Phân cụm cực đại kỳ vọng, phân cụm khái niệm, học máy mạng nơron
 ❑ Phân cụm cực đại kỳ vọng: khởi tạo, tính giá trị kỳ vọng, cực đại hóa kỳ vọng 31
 7. Biểu diễn cụm và gán nhãn
⚫ Các phương pháp biểu diễn điển dình
 ❑ Theo đại diện cụm
 ⚫ Đại diện cụm làm tâm
 ⚫ Tính bán kính và độ lệch chuẩn để xác định phạm vi của cụm
 ⚫ Cụm không ellip/cầu hóa: không tốt
 ❑ Theo mô hình phân lớp
 ⚫ Chỉ số cụm như nhãn lớp
 ⚫ Chạy thuật toán phân lớp để tìm ra biểu diễn cụm
 ❑ Theo mô hình tần số
 ⚫ Dùng cho dữ liệu phân loại
 ⚫ Tần số xuất hiện các giá trị đặc trưng cho từng cụm
⚫ Lưu ý
 ❑ Dữ liệu phân cụm ellip/cầu hóa: đại diện cụm cho biểu diễn tốt
 ❑ Cụm hình dạng bất thường rất khó biểu diễn
 32
Gán nhãn cụm
⚫ Phân biệt các cụm (MU)
 ⚫ Chọn đặc trưng tương quan cụm
 ⚫ Nxy (x có đặc trưng t, y dữ liệu thuộc C)
 ⚫ N11 : số dữ liệu chứa t thuộc cụm C
 ⚫ N10 : số dữ liệu chứa t không thuộc cụm C
 ⚫ N01 : số dữ liệu không chứa t thuộc cụm C
 ⚫ N00 : số dữ liệu không chứa t không thuộc cụm C
 ⚫ N: Tổng số dữ liệu
⚫ Hướng “trọng tâm” cụm
 ⚫ Dùng các đặc trưng tần số cao tại trọng tâm cụm
⚫ Tiêu đề
 ⚫ Chon đặc trưng của dữ liệu trong cụm gần trọng tâm nhất 33
Ví dụ: Gán nhãn cụm văn bản
⚫ Ví dụ
 ❑ Ba phương pháp chọn nhãn cụm đối với 3 cụm là cụm 4 (622 tài liệu),
 cụm 9 (1017 tài liệu), cụm 10 (1259 tài liệu) khi phân cụm 10000 tài liệu
 đầu tiên của bộ Reuters-RCV1
 ❑ centroid: các từ khóa có tần số cao nhất trong trọng tâm; mutual
 information (MU): thông tin liên quan phân biệt các cụm; title: tiêu đề tài
 liệu gần trọng tâm nhất.
Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information
Retrieval, Cambridge University Press. 2008. 34
 8. Đánh giá phân cụm
⚫ Đánh giá chất lượng phân cụm là khó khăn
 ❑ Chưa biết các cụm thực sự
⚫ Một số phương pháp điển hình
 ❑ Người dùng kiểm tra
 ▪ Nghiên cứu trọng tâm và miền phủ
 ▪ Luật từ cây quyết định
 ▪ Đọc các dữ liệu trong cụm
 ❑ Đánh giá theo các độ đo tương tự/khoảng cách
 ▪ Độ phân biệt giữa các cụm
 ▪ Phân ly theo trọng tâm
 ❑ Dùng thuật toán phân lớp
 ▪ Coi mỗi cụm là một lớp
 ▪ Học bộ phân lớp đa lớp (cụm)
 ▪ Xây dựng ma trận nhầm lẫn khi phân lớp
 ▪
 Tính các độ đo: entropy, tinh khiết, chính xác, hồi tưởng, độ 35
 đo F và đánh giá theo các độ đo này
 Đánh giá theo độ đo tương tự
⚫ Độ phân biệt các cụm
 ❑ Cực đại hóa tổng độ tương tự nội tại của các cụm
 ❑ Cực tiểu hóa tổng độ tương tự các cặp cụm khác nhau
 ❑ Lấ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
 36
Ví dụ: Chế độ, đặc điểm phân cụm web
 ⚫ 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.
 37
Ví dụ
 38
Hệ thống tư vấn
 ⚫ 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. 39
Ví dụ
 Hệ thống có thành phần tư vấn
 Ma trận hữu ích người dùng-mục 40
So sánh lọc và phân lớp
 [Aggarwal16] 
 41
Hệ thống tư vấn: Tính chất
 ⚫ 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
 42
Kỹ thuật lọc trong hệ thống tư vấn
 [Aggarwal16] 
 ⚫ 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ụci .
 43
Lọc cộng tác hướng người dùng
 ❑ 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ùngu 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ườidù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
 44
Lọc cộng tác hướng mục và mô hình
 ⚫ Lọc cộng tác hướng mục
 ❑ Tính độ tương tự giữa các mục
 푆푖푗: tập ngườidù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
 45
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
 ⚫ 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
 47
Khung khái quát hệ tư vấn lọc nội dung
 [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.
 48
Hoạt động hệ thống lọc dựa trên nội dung
 ⚫ 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
 49
Học mô hình sở thích người dùng
 ⚫ 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
 50
Phương thức đánh giá hiệu năng HTV 
 ⚫ 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 51
Đánh giá hiệu năng hệ tư vấn: Độ đo
 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)
 52
Tư vấn xã hội
 ⚫ 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
 53
Tư vấn vị trí di động
 ❑ 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
 54
Tư vấn nhóm người dùng
 ⚫ 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
 55