Ngoài máy học (Machine Learning), 1 ngành khác cũng được ứng dụng rất nhiều trong XLNNTN là Data mining. Những ngành này luôn có sự liên quan rất mật thiết với nhau. Trong bài viết này, tôi muốn giới thiệu về các thuật toán phân nhóm (clustering), ưu, nhược điểm của từng thuật toán. Tên các thuật toán sẽ được giữ nguyên theo tiếng Anh.
K-means
Tham số : n - số lượng các nhóm.
Khả năng thực thi : số lượng nhóm ở mức trung bình, số lượng mẫu cực lớn.
Đối tượng : Mục đích chung, bất kể kích thước dữ liệu, hình học phẳng.
Cách tính khoảng cách : Khoảng cách hình học.
Đây là thuật toán đơn giản và phổ thông nhất, nhưng lại có ứng dụng rất lớn.
Tham số :
Khả năng thực thi
Đối tượng :
Cách tính khoảng cách :
Tham số : số lượng nút hàng xóm
Khả năng thực thi : số mẫu cực lớn, số nhóm trung bình
Đối tượng : Hình học không phẳng, số lượng mẫu trong 1 nhóm không giới hạn
Cách tính khoảng cách : Khoảng cách giữa những điểm gần nhất.
Thuật toán cơ bản :
2 tham số : eps và minPts. Từ 1 mẫu (nút) chưa được chọn, kiểm tra các điểm gần nhất, nếu số lượng các điểm này lớn hơn giá trị minPts thì bắt đầu 1 nhóm mới. Nếu không sẽ đánh dấu là điểm nhiễu. Điểm nhiễu này vẫn có thể thuộc 1 nhóm khác, khi đó sẽ bỏ đánh dấu điểm nhiễu.
Cứ thế mở rộng ra đến khi không thể tìm thêm điểm mới cho nhóm.
Độ phức tạp : tính toán (N*logN), dữ liệu (N^2)
Ưu điểm :
- Không cần xác định trước số lượng các nhóm. Điều này trái ngược với K-Means.
- DBSCAN có thể tìm được những nhóm có dạng hình học đặc biệt như : 1 nhóm bị bao kín hoàn toàn bởi 1 nhóm khác. Với tham số minPts, DBSCAN giảm được hiệu ứng Single_link (các nhóm khác nhau bị liên kết với nhau bởi 1 đường mỏng).
- DBSCAN có khái niệm về nút (mẫu) nhiễu.
- DBSCAN cần 2 tham số, và không nhạy cảm với sự thay đổi thứ tự trong dữ liệu.
Nhược điểm :
- Kết quả phụ thuộc rất lớn vào cách tính khoảng cách giữa các điểm.
- DBSCAN không hiệu quả khi phân nhóm 1 tập hợp dữ liệu có mật độ phân tán khác nhau.
Clustering performance evaluation
