Bài 10 - PHÂN CỤM DỮ LIỆU

PHÂN CỤM DỮ LIỆU

1. Giới thiệu bài toán phân cụm

Bài toán

• • Tập dữ liệu D = {d_i}
  • Phân các dữ liệu thuộc D thành các cụm
    • Các dữ liệu trong một cụm: “tương tự” nhau (gần nhau)
    • Dữ liệu hai cụm: “không tương tự” nhau (xa nhau)
  • Đo “tương tự” (gần) nhau ?
    • Tiên đề phân cụm: Nếu người dùng lựa chọn một đối tượng d thì họ cũng lựa chọn các đối tượng cùng cụm với d
    • Khai thác “cách chọn lựa” của người dùng
    • Đưa ra một số độ đo “tương tự” theo biểu diễn dữ liệu

Một số nội dung liên quan

• • Xây dựng độ đo tương tự
  • Khai thác thông tin bổ sung
  • Số lượng cụm cho trước, số lượng cụm không cho trước

Sơ bộ tiếp cận phân cụm

• Phân cụm mô hình và phân cụm phân vùng
  • Mô hình: Kết quả là mô hình biểu diễn các cụm dữ liệu
  • Vùng: Danh sách cụm và vùng dữ liệu thuộc cụm
• Phân cụm đơn định và phân cụm xác suất
  • Đơn định: Mỗi dữ liệu thuộc duy nhất một cụm
  • Xác suất: Danh sách cụm và xác suất một dữ liệu thuộc vào các cụm
• Phân cụm phẳng và phân cụm phân cấp
  • Phẳng: Các cụm dữ liệu không giao nhau
  • Phân cấp: Các cụm dữ liệu có quan hệ phân cấp cha- con
• Phân cụm theo lô và phân cụm tăng
  • Lô: Tại thời điểm phân cụm, toàn bộ dữ liệu đã có
  • Tăng: Dữ liệu tiếp tục được bổ sung trong quá trình phân cụm

Các phương pháp phân cụm

• Các phương pháp phổ biến
  • Phân vùng, phân cấp, dựa theo mật độ, dựa theo lưới, dựa theo mô hình, và phân cụm mờ
• Phân cụm phân vùng (phân cụm phẳng)
  • Xây dựng từng bước phân hoạch các cụm và đánh giá chúng theo các tiêu chí tương ứng
  • Tiếp cận: từ dưới lên (gộp dần), từ trên xuống (chia dần)
  • Độ đo tương tự / khoảng cách
  • K-mean, k-mediod, CLARANS, …
  • Hạn chế: Không điều chỉnh được lỗi
• Phân cụm phân cấp
  • Xây dựng hợp (tách) dần các cụm tạo cấu trúc phân cấp và đánh giá theo các tiêu chí tương ứng
  • Độ đo tương tự / khoảng cách
  • HAC: Hierarchical agglomerative clustering
  • CHAMELEON, BIRRCH và CURE, …
• Phân cụm dựa theo mật độ
  • Hàm mật độ: Tìm các phần tử chính tại nơi có mật độ cao
  • Hàm liên kết: Xác định cụm là lân cận phần tử chính
  • DBSCAN, OPTICS…
• Phân cụm dựa theo lưới
  • Sử dụng lưới các ô cùng cỡ: tuy nhiên cụm là các “ô” phân cấp
  • Tạo phân cấp ô lưới theo một số tiêu chí: số lượng đối tượng trong ô
  • STING, CLIQUE, WaweCluster…
• Phân cụm dựa theo mô hình
  • Giải thiết: Tồn tại một số mô hình dữ liệu cho phân cụm
  • Xác định mô hình tốt nhất phù hợp với dữ liệu
  • MCLUST…
• Phân cụm mờ
  • Giả thiết: không có phân cụm “cứng” cho dữ liệu và đối tượng có thể thuộc một số cụm
  • Sử dụng hàm mờ từ các đối tượng tới các cụm
  • FCM (Fuzzy CMEANS),…

2. Một số độ đo cơ bản

Độ đo tương đồng

• • Biểu diễn: vector n chiều
  • Giá trị nhị phân: Ma trận kề, độ đo Jaccard
  • Giá trị rời rạc [0,m]: Chuyển m giá trị thành nhị phân, độ đo Jaccard
  • Giá trị thực : độ đo cosin hai vector

Độ đo khác biệt

• • Đối ngẫu độ đo tương đồng
  • Thuộc tính nhị phân: đối cứng, không đối xứng
  • Giá trị rời rạc: hoặc tương tự trên hoặc dạng đơn giản (q thuộc tính giống nhau)
  • Giá trị thực: Khoảng cách Manhattan, Euclide, Mincowski
  • Tính xác định dương, tính đối xứng, tính bất đẳng thức tam giác

Ví dụ về độ khác biệt

• • CSDL xét nghiệm bệnh nhân
  • Quy về giá trị nhị phân: M/F, Y/N, N/P
  • Lập ma trận khác biệt cho từng cặp đối tượng.
  • Ví dụ, cặp (Nam, Vân): a=2, b=1, c=1, d=3

D(Nam, Vân) =(1+1)/(2+1+1)=0.5

3. Thuât toán K-mean gán cứng

Một số lưu ý

• • Điều kiện dừng
    1. Sau bước 2 không có sự thay đổi cụm
    2. Điều kiện dừng cưỡng bức
       1. Khống chế số lần lặp
       2. Giá trị mục tiêu đủ nhỏ
  • Vấn đề chọn tập đại diện ban đầu ở bước Khởi động
  • Có thể dùng độ đo khoảng cách thay cho độ đo tương tự
• Thuât toán K-mean gán cứng

• Một số lưu ý (tiếp) và ví dụ
  • Trong bước 2: các trọng tâm có thể không thuộc S
  • Thực tế: số lần lặp £ 50
  • Thi hành k-mean với dữ liệu trên đĩa
    • Toàn bộ dữ liệu quá lớn: không thể ở bộ nhớ trong
    • Với mỗi vòng lặp: duyệt CSDL trên đĩa 1 lần
      • Tính được độ tương tự của d với các c_i.
      • Tính lại c_i mới: bước 2.1 khởi động (tổng, bộ đếm); bước 2.2 cộng và tăng bộ đếm; bước 2.3 chỉ thực hiện k phép chia.

Thuât toán K-mean mềm

• Input
  • Số nguyên k > 0: số cụm biết trước
  • Tập dữ liệu D (cho trước)
• Output
  • Tập k “đại diện cụm” m_C làm cực tiểu lỗi “lượng tử”  
• Định hướng
  • Tinh chỉnh m_C dần với tỷ lệ học h (learning rate) 

• Ưu điểm
  • Đơn giản, dễ sử dụng
  • Hiệu quả về thời gian: tuyến tính O(tkn), t số lần lặp, k số cụm, n là số phần tử
  • Một thuật toán phân cụm phổ biến nhất
  • Thường cho tối ưu cục bộ. Tối ưu toàn cục rất khó tìm
• Nhược điểm
  • Phải “tính trung bình được”: dữ liệu phân lớp thì dựa theo tần số
  • Cần cho trước k : số cụm
  • Nhạy cảm với ngoại lệ (cách xa so với đại đa số dữ liệu còn lại): ngoại lệ thực tế, ngoại lệ do quan sát sai (làm sạch dữ liệu)
  • Nhạy cảm với mẫu ban đầu: cần phương pháp chọn mẫu thô tốt
  • Không thích hợp với các tập dữ liệu không siêu-ellip hoặc siêu cầu (các thành phần con không ellip/cầu hóa)

Trái: Nhạy cảm với chọn mẫu ban đầu

Phải: Không thích hợp với bộ dữ liệu không siêu ellip/cầu hóa

1. 2. Thuât toán PAM (K-mediod)

• • K-mediod
    • Biến thể của K-mean: thay trọng tâm bằng một phần tử của D
    • Hàm mục tiêu
    • PAM: Partition Around Mediods

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 tài 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

1. Phân cụm phân cấp từ dưới lên

• 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

• 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ự

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

2. 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, LS, SS>, 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
    • <3, (9,10), (29,38)>. 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

BIRCH: Năm độ đo khoảng cách

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à đả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ớ

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á  L₁ gần a nhất, kiểm tra xem L₁ có “hấp thụ“ a không (chưa vượt ngưỡng); nếu có thì đặc trưng CF của L₁ 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:

Các thuật toán phân cụm khác

• 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) > 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

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

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

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.

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, độ đ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

Ví dụ: Chế độ và đặ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

Ví dụ

Phân cụm kết quả tìm kiếm