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 = {di}
    • 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),…
  1. 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

  1. 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 ci.
        • Tính lại ci 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” mC làm cực tiểu lỗi “lượng tử”  
  • Định hướng
    • Tinh chỉnh mC 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. 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

  1. 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
  1. 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á  L1 gần a nhất, kiểm tra xem L1 có “hấp thụ“ 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:

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