Khái niệm
Phân cụm khái niệm (conceptual clustering) là dạng phân cụm trong machine learning: cho tập đối tượng không nhãn, tạo thiết kế phân loại (classification scheme) trên các đối tượng. Khác với clustering truyền thống chỉ nhận diện nhóm đối tượng giống nhau, conceptual clustering tiến xa hơn bằng cách cũng khám phá định nghĩa đặc trưng cho mỗi nhóm, mỗi nhóm định nghĩa một khái niệm/lớp (concept/class).
Do đó conceptual clustering là quy trình 2 bước: phân cụm trước, đặc trưng hóa (characterization) sau. Chất lượng phân cụm không chỉ là hàm của từng đối tượng đơn lẻ. Đa số kỹ thuật conceptual clustering dùng phương pháp thống kê với đo lường xác suất quyết định khái niệm/cụm.
Mô tả xác suất (Probabilistic descriptions)
Dùng mô tả xác suất cho từng khái niệm dẫn xuất. COBWEB là phương pháp conceptual clustering tăng dần (incremental) nổi tiếng và đơn giản. Đầu vào: đối tượng mô tả bởi cặp thuộc tính-giá trị phân loại (categorical attribute-value pairs). COBWEB tạo phân cụm phân cấp dạng cây phân loại (classification tree).
Cây phân loại vs Cây quyết định
Mỗi nút trong classification tree đại diện một khái niệm và chứa mô tả xác suất của khái niệm đó, tóm tắt đối tượng được phân loại dưới nút. Mô tả xác suất chứa:
- Xác suất khái niệm P(Cₖ)
- Xác suất có điều kiện P(Aᵢ = vᵢⱼ | Cₖ) với Aᵢ = vᵢⱼ là cặp thuộc tính-giá trị (thuộc tính i lấy giá trị j), Cₖ là lớp khái niệm.
Thước đo Category Utility (CU) - Hướng dẫn xây dựng cây
COBWEB dùng heuristic evaluation measure Category Utility để hướng dẫn xây dựng cây.
CU = [ Σₖ P(Cₖ) [ Σᵢ Σⱼ P(Aᵢ=vᵢⱼ|Cₖ)² - Σᵢ Σⱼ P(Aᵢ=vᵢⱼ)² ] ] / n
n = số nút/khái niệm/"category" tạo thành phân vùng {C₁,...,Cₙ} tại cấp độ cây cho trước.
Category utility = sự gia tăng số giá trị thuộc tính có thể đoán đúng hoàn hảo nhờ phân vùng (term thứ nhất) so với số lần đoán đúng không có kiến thức (term thứ hai). CU khuyến khích:
- Tương đồng trong lớp (Intraclass similarity): P(Aᵢ=vᵢⱼ|Cₖ) càng cao → tỷ lệ thành viên lớp chia sẻ cặp thuộc tính-giá trị càng lớn → cặp đó càng dự báo được thành viên lớp.
- Khác biệt giữa lớp (Interclass dissimilarity): P(Cₖ|Aᵢ=vᵢⱼ) càng cao → càng ít đối tượng lớp đối lập chia sẻ cặp thuộc tính-giá trị → cặp đó càng dự báo được lớp.
Quy trình đặt đối tượng trong COBWEB
COBWEB đi xuống cây theo đường phù hợp, làm mới đếm dọc theo đường, tìm "best host" (nút tốt nhất) để đặt đối tượng. Quyết định dựa trên: tạm đặt đối tượng vào mỗi nút, tính category utility của phân vùng kết quả. Vị trí cho category utility cao nhất = best host.