Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Phân cụm bán giám sát (Semi-Supervised Cluster Analysis)

Khái niệm

Phân cụm bán giám sát (semi-supervised clustering) là phương pháp phân vùng dữ liệu không nhãn (unlabeled) bằng cách sử dụng kiến thức miền (domain knowledge). Thường biểu diễn dưới dạng ràng buộc cặp (pairwise constraints) giữa các instance hoặc tập hợp thêm các instance có nhãn.

Chất lượng phân cụm không giám sát có thể cải thiện đáng kể bằng hình thức giám sát yếu, ví dụ ràng buộc cặp (cặp đối tượng gắn nhãn thuộc cùng cụm hoặc cụm khác). Quy trình phân cụm phụ thuộc vào phản hồi người dùng hoặc ràng buộc hướng dẫn gọi là semi-supervised clustering.

Hai lớp phương pháp chính

1. Phân cụm bán giám sát dựa trên ràng buộc (Constraint-based)

Sử dụng nhãn hoặc ràng buộc do người dùng cung cấp để hướng thuật toán về phân vùng dữ liệu phù hợp hơn. Bao gồm: sửa đổi hàm mục tiêu theo ràng buộc, hoặc khởi tạo và ràng buộc quy trình phân cụm dựa trên đối tượng có nhãn.

2. Phân cụm bán giám sát dựa trên khoảng cách (Distance-based)

Sử dụng thước đo khoảng cách thích ứng (adaptive distance measure) được huấn luyện để thỏa mãn nhãn/ràng buộc trong dữ liệu giám sát. Các thước đo thích ứng: khoảng cách chỉnh sửa chuỗi (string-edit distance) huấn luyện bằng Expectation-Maximization (EM), khoảng cách Euclidean sửa đổi bằng thuật toán khoảng cách ngắn nhất.

Phương pháp CLTree (CLustering based on decision TREEs)

Phương pháp thú vị tích hợp phân cụm không giám sát với khái niệm phân loại giám sát. Là ví dụ của constraint-based semi-supervised clustering.

Quy trình:

  1. Chuyển bài toán phân cụm thành bài toán phân loại: tập điểm cần phân cụm coi như thuộc một lớp, nhãn "Y".
  2. Chèn tập điểm "phi tồn tại" (nonexistence points) phân bố đều tương đối, nhãn lớp "N".
  3. Bài toán phân chia không gian dữ liệu thành vùng dữ liệu (dày đặc) và vùng rỗng (thưa) → bài toán phân loại.
  4. Dùng phương pháp quy nạp cây quyết định (decision tree induction) phân chia không gian 2 chiều.
  5. Nhận diện 2 cụm từ điểm "Y" בלבד.

Hạn chế

Chèn số lượng lớn điểm "N" gây chi phí tính toán không cần thiết. Xác suất điểm chèn thực sự phân bố đều trong không gian chiều rất cao rất thấp (cần số điểm mũ).