Clustering không gian vectơ lớn

Question

Tôi đang thực hiện một số thử nghiệm phân cụm một số lượng lớn các vectơ thưa thớt rất lớn thể hiện tần suất-tần số nghịch đảo-tài liệu của các tài liệu siêu văn bản khác nhau. Bạn sẽ đề xuất thuật toán nào để phân cụm dữ liệu này, có tính đến tỷ lệ của tập dữ liệu? Kích thước của vectơ sẽ là> 3 · 10 và số lượng vectơ có thể là khoảng 10 . Tôi đã xem xét thuật toán dbscan và quang học. Số lượng cụm không được biết đến là một linh mục. Và một chỉ số không gian với chiều cao như vậy có vẻ phức tạp.

Answer 1

Tôi đã có kết quả gần như tốt với một cụm K đơn giản như hầu hết mọi thứ, và nó chắc chắn nhanh hơn hầu hết các lựa chọn thay thế. Tôi cũng đã nhận được kết quả tốt với sự kết hợp hai chiều khôn ngoan, nhưng nó hơi chậm hơn một chút. Đối với K-means, bạn phải bắt đầu với một số cụm ước tính, nhưng bạn có thể điều chỉnh nó theo thuật toán khi bạn đi theo. Nếu bạn tìm thấy hai cụm có nghĩa là quá gần nhau, bạn sẽ giảm số lượng cụm. Nếu bạn tìm thấy các cụm có phạm vi biến thể quá lớn, bạn hãy thử nhiều cụm hơn. Tôi đã tìm thấy sqrt (N) là một điểm khởi đầu hợp lý - nhưng tôi thường bắt đầu với hơn 10^7 tài liệu thay vì 10^9. Đối với 10^9, nó có thể có ý nghĩa để giảm bớt phần nào đó.

Nếu điều đó tùy thuộc vào tôi, tuy nhiên, tôi nghĩ rất khó khăn khi bắt đầu bằng cách giảm thứ nguyên với thứ gì đó như Landmark MDS, rồi thực hiện phân cụm.

Answer 2

Cây quyết định phổ biến để hoạt động hiệu quả trong không gian chiều cao.Kiểm tra Clustering Via Decision Tree Construction.

Ngoài ra, Randomized Forests là những người học cực kỳ hiệu quả và OpenCV implementation exists nếu bạn muốn chơi với nó.

Answer 3

Tôi nghe rằng semantic hashing đạt được kết quả xuất sắc. Tuy nhiên, mạng lưới niềm tin sâu sắc là khá để thực hiện. Bạn có thể muốn thử băm nhỏ (đó là cách tiếp cận xác suất) hoặc locality sensistive hashing for euclidean spaces.

Nói chung, phân cụm trong không gian chiều cao như vậy là khó khăn do lời nguyền của chiều và thực tế là hầu hết các mặt hàng có khoảng cách tương tự với nhau. Các phương pháp chuẩn như K-Means có thể hoạt động nếu bạn giảm kích thước trước qua SOM hoặc PCA.

Answer 4

Khi phân nhóm dữ liệu tôi sẽ luôn cố gắng ít nhất hai thuật toán này theo thứ tự này:

1. K-Phương tiện: cố gắng tinh chỉnh kết quả càng nhiều càng tốt. Nếu bạn có thể có được K-Means để làm việc cho bạn và cung cấp kết quả tốt, bạn sẽ gần như chắc chắn không làm tốt hơn khi bất kỳ thuật toán khác.

2. Tối đa hóa kỳ vọng: thuật toán K-means thực sự được phát triển thành giải pháp thay thế giá rẻ và tốt cho thuật toán EM. Thuật toán EM phức tạp hơn để hiểu và tốn kém hơn để tính toán, nhưng kết quả từ EM là tuyệt vời. Bạn có thể tìm hiểu thêm về EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm. Có một thực OpenCV của EM: http://opencv.willowgarage.com/documentation/expectation-maximization.html

Nếu kết quả không ai trong số hai đều thỏa đáng, tôi sẽ bắt đầu tìm kiếm ở nơi khác, nhưng không cho đến khi bạn đã thử cả hai.