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

Chameleon - Thuật toán phân cụm phân cấp dựa trên mô hình động

Giới thiệu Chameleon

Chameleon là thuật toán phân cụm phân cấp sử dụng mô hình động (dynamic modeling) để quyết định độ tương đồng giữa các cặp cụm. Nó được cải tiến dựa trên điểm yếu quan sát được của hai thuật toán phân cụm phân cấp: ROCK và CURE.

Hạn chế của ROCK và CURE

  • ROCK và các thiết kế liên quan: Nhấn mạnh tính liên kết cụm (cluster interconnectivity) nhưng bỏ qua thông tin về độ gần cụm (cluster proximity).
  • CURE và các thiết kế liên quan: Xem xét độ gần cụm nhưng bỏ qua tính liên kết cụm.

Cách tiếp cận của Chameleon

Độ tương đồng cụm được đánh giá dựa trên: (1) mức độ kết nối tốt của các đối tượng bên trong cụm, và (2) độ gần của các cụm. Cụ thể: hai cụm được gộp nếu tính liên kết của chúng cao VÀ chúng gần nhau.

Không dựa trên mô hình tĩnh do người dùng cung cấp, Chameleon tự động thích ứng với đặc điểm nội tại của các cụm đang được gộp. Quy trình gộp hỗ trợ khám phá cụm tự nhiên và đồng nhất, áp dụng cho mọi loại dữ liệu miễn là có thể định nghĩa hàm tương đồng.

Kỹ thuật đồ thị k-nearest-neighbor (k-NN graph)

Chameleon dùng k-NN graph để tạo đồ thị thưa (sparse graph):

  • Mỗi đỉnh = một đối tượng dữ liệu.
  • Cạnh giữa hai đỉnh nếu một đối tượng nằm trong k đối tượng tương đồng nhất của đối tượng kia.
  • Cạnh được gán trọng số phản ánh độ tương đồng giữa đối tượng.

Quy trình phân cụm

  1. Phân vùng đồ thị: Dùng thuật toán phân vùng đồ thị để chia k-NN graph thành số lượng lớn các cụm con (subclusters) nhỏ tương đối.
  2. Gộp agglomerative (hồi quy): Lặp lại gộp các cụm con dựa trên độ tương đồng. Xác định cặp cụm con tương đồng nhất, xem xét cả tính liên kết (interconnectivity) LÀM độ gần (closeness).

Đặc điểm nổi bật

  • Bán kính láng giềng động: Bán kính láng giềng của đối tượng được quyết định bởi mật độ vùng chứa đối tượng. Vùng dày đặc → láng giềng hẹp. Vùng thưa → láng giềng rộng. Kết quả: cụm tự nhiên hơn so với DBSCAN dùng láng giềng toàn cục.
  • Trọng số cạnh ghi nhận mật độ: Cạnh vùng dày đặc có trọng số lớn hơn vùng thưa.
  • Phân vùng đồ thị tối thiểu hóa cắt cạnh (edge cut): Cụm C chia thành Cᵢ, Cⱼ để tối thiểu hóa trọng số cạnh bị cắt. Edge cut EC(Cᵢ, Cⱼ) xác định độ liên kết tuyệt đối giữa hai cụm con.