thư viện phân cụm quy mô lớn có thể với các ràng buộc python

Question

Tôi đã cố gắng nhóm một số tập dữ liệu lớn hơn. bao gồm 50000 vector đo với kích thước 7. Tôi đang cố gắng tạo ra khoảng 30 đến 300 cụm để xử lý tiếp.

Tôi đã cố gắng triển khai phân nhóm sau đây không có may mắn:

• Pycluster.kcluster (cho chỉ 1-2 cụm không trống trên bộ dữ liệu của tôi)
• scipy.cluster.hierarchy.fclusterdata (chạy quá dài)
• scipy.cluster.vq.kmeans (chạy ra khỏi bộ nhớ)
• sklearn.cluster.hierarchical.Ward (chạy quá lâu)

Có bất kỳ triển khai nào khác mà tôi có thể bỏ sót không?

Answer 1

50000 trường hợp và 7 thứ nguyên không thực sự lớn và không được thực thi.

Mặc dù không có ràng buộc python, hãy thử dùng thử ELKI. Các thiết lập tiêu chuẩn họ sử dụng trên trang chủ của họ là 110250 trường hợp trong 8 kích thước, và họ chạy k-có nghĩa là nó trong 60 giây rõ ràng, và OPTICS cao cấp hơn nhiều trong 350 giây.

Tránh phân cụm theo cấp bậc. Nó thực sự chỉ dành cho các tập dữ liệu nhỏ. Cách nó thường được triển khai trên các hoạt động ma trận là O(n^3), là thực sự là không hợp lệ đối với các tập dữ liệu lớn. Vì vậy, tôi không ngạc nhiên khi hai người này hẹn giờ cho bạn.

DBSCAN và OPTICS khi được triển khai với hỗ trợ chỉ mục là O(n log n). Khi được triển khai một cách ngây thơ, chúng nằm trong số O(n^2). K-nghĩa là thực sự nhanh, nhưng thường kết quả là không thỏa đáng (bởi vì nó luôn tách ở giữa). Nó sẽ chạy trong O(n * k * iter) thường hội tụ trong không quá nhiều lần lặp (iter<<100). Nhưng nó sẽ chỉ hoạt động với khoảng cách Euclide, và không hoạt động tốt với một số dữ liệu (các chiều cao, rời rạc, nhị phân, các cụm với các kích thước khác nhau, ...)

Answer 2

OpenCV có k-means thực hiện, Kmeans2

Dự kiến ​​thời gian chạy là vào thứ tự của O(n**4) - cho một xấp xỉ lệnh của độ richter, xem phải mất bao lâu để cụm 1000 điểm, sau đó nhân lên rằng bằng cách bảy triệu (50 ** 4 làm tròn).

Answer 3

Vì bạn đã thử tìm hiểu : sklearn.cluster.KMeans nên quy mô tốt hơn Ward và hỗ trợ lắp song song trên các máy đa lõi. MiniBatchKMeans vẫn tốt hơn, nhưng sẽ không thực hiện khởi động lại ngẫu nhiên cho bạn.

>>> from sklearn.cluster import MiniBatchKMeans 
>>> X = np.random.randn(50000, 7) 
>>> %timeit MiniBatchKMeans(30).fit(X) 
1 loops, best of 3: 114 ms per loop 

Answer 4

My gói milk xử lý vấn đề này một cách dễ dàng:

import milk 
import numpy as np 
data = np.random.rand(50000,7) 
%timeit milk.kmeans(data, 300) 
1 loops, best of 3: 14.3 s per loop 

Tôi tự hỏi liệu bạn có nghĩa là để viết 500.000 điểm dữ liệu, vì 50k điểm không phải là nhiều. Nếu vậy, sữa sẽ mất nhiều thời gian hơn (~ 700 giây), nhưng vẫn xử lý tốt vì nó không phân bổ bất kỳ bộ nhớ nào khác ngoài dữ liệu của bạn và các centroid.