scikit-learning Sử dụng bộ nhớ DBSCAN

Question

CẬP NHẬT: Cuối cùng, giải pháp tôi chọn để sử dụng cho phân cụm tập dữ liệu lớn của tôi là một gợi ý của Anony-Mousse bên dưới. Đó là, bằng cách sử dụng hàm ý DBSCAN của ELKI để làm cụm của tôi hơn là tìm kiếm của scikit. Nó có thể được chạy từ dòng lệnh và với chỉ mục thích hợp, thực hiện nhiệm vụ này trong vòng vài giờ. Sử dụng GUI và các tập dữ liệu mẫu nhỏ để làm việc ra các tùy chọn bạn muốn sử dụng và sau đó đi đến thị trấn. Đáng xem xét. Anywho, đọc cho một mô tả về vấn đề ban đầu của tôi và một số cuộc thảo luận thú vị.

Tôi có tập dữ liệu với ~ 2,5 triệu mẫu, mỗi mẫu có 35 đối tượng (giá trị điểm động) mà tôi đang cố gắng nhóm. Tôi đã cố gắng làm điều này với việc thực hiện scikit-learning của DBSCAN, sử dụng chỉ số khoảng cách Manhattan và giá trị của epsilon được ước tính từ một số mẫu ngẫu nhiên nhỏ được rút ra từ dữ liệu. Càng xa càng tốt. (đây là đoạn trích, để tham khảo)

db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata) 

Vấn đề của tôi tại thời điểm này là tôi dễ dàng hết bộ nhớ. (Tôi hiện đang làm việc với một máy có RAM 16 GB)

Câu hỏi của tôi là, DBSCAN tính toán ma trận khoảng cách hai chiều khi nó chạy, và đó là điều gì làm lung lay bộ nhớ của tôi? (2,5 triệu^2) * 8 byte rõ ràng là ngu ngốc lớn, tôi sẽ hiểu điều đó. Tôi có nên không sử dụng phương pháp fit() không? Và nói chung, có cách nào xung quanh vấn đề này, hay tôi thường sủa cây sai ở đây?

Xin lỗi nếu câu trả lời trở nên rõ ràng. Tôi đã bối rối về điều này trong một vài ngày. Cảm ơn!

Phụ lục: Ngoài ra nếu có ai có thể giải thích sự khác biệt giữa fit(X) và fit_predict(X) với tôi rõ ràng hơn, tôi cũng đánh giá cao điều đó - Tôi e rằng tôi không hiểu rõ.

Phụ lụC# 2: Để chắc chắn, tôi vừa thử trên một máy có ~ 550 GB RAM và nó vẫn bị nổ, vì vậy tôi cảm thấy DBSCAN có khả năng cố gắng tạo ma trận khoảng cách hai chiều hoặc không muốn nó làm. Tôi đoán bây giờ câu hỏi lớn là làm thế nào để ngăn chặn hành vi đó, hoặc tìm các phương pháp khác có thể phù hợp với nhu cầu của tôi nhiều hơn. Cảm ơn vì đã mang theo tôi ở đây.

Phụ LụC# 3 (!): Tôi quên đính kèm traceback, ở đây là,

Traceback (most recent call last): 
    File "tDBSCAN.py", line 34, in <module> 
    db = DBSCAN(eps=float(sys.argv[2]), min_samples=10, metric='cityblock').fit(mydata) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/base.py", line 329, in fit_predict 
    self.fit(X) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 186, in fit 
    **self.get_params()) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 69, in dbscan 
    D = pairwise_distances(X, metric=metric) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 651, in pairwise_distances 
    return func(X, Y, **kwds) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 237, in manhattan_distances 
    D = np.abs(X[:, np.newaxis, :] - Y[np.newaxis, :, :]) 
MemoryError 

Answer 1

Vấn đề rõ ràng là việc triển khai DBSCAN chất lượng thấp trong scikit.

DBSCAN không cần ma trận khoảng cách. Thuật toán được thiết kế xung quanh bằng cách sử dụng cơ sở dữ liệu có thể tăng tốc hàm regionQuery và trả về hàng xóm trong bán kính truy vấn một cách hiệu quả (chỉ mục không gian phải hỗ trợ các truy vấn đó trong O(log n)).

Việc triển khai trong scikit tuy nhiên, rõ ràng, tính toán ma trận khoảng cách O(n^2) đầy đủ, đi kèm với chi phí cả về trí nhớ và thời gian chạy.

Vì vậy, tôi thấy hai lựa chọn:

1. Bạn có thể muốn thử thực hiện DBSCAN trong ELKI thay vào đó, mà khi sử dụng với một R * index -cây thường là nhanh hơn đáng kể so với một thực hiện ngây thơ.

2. Nếu không, bạn có thể muốn reimplement DBSCAN, vì việc triển khai trong scikit dường như không quá tốt. Đừng sợ điều đó: DBSCAN thực sự đơn giản để thực hiện bản thân bạn. Phần khó nhất của việc triển khai DBSCAN tốt thực sự là hàm regionQuery. Nếu bạn có thể nhận được truy vấn này nhanh, DBSCAN sẽ nhanh chóng. Và bạn cũng có thể sử dụng lại chức năng này cho các thuật toán khác.

Cập nhật: bởi bây giờ, sklearn không còn tính toán khoảng cách ma trận và có thể, ví dụ, sử dụng một chỉ số kd-cây. Tuy nhiên, vì "vectorization" nó vẫn sẽ precompute hàng xóm của mọi điểm, do đó, việc sử dụng bộ nhớ của sklearn cho epsilon lớn là O (n²), trong khi để hiểu biết của tôi phiên bản trong ELKI sẽ chỉ sử dụng O (n) bộ nhớ. Vì vậy, nếu bạn hết bộ nhớ, hãy chọn một epsilon nhỏ hơn và/hoặc thử ELKI.

Answer 2

Thuật toán DBSCAN thực sự không tính toán ma trận khoảng cách, vì vậy không có cơ hội ở đây. Đối với nhiều dữ liệu này, tôi khuyên bạn nên sử dụng MiniBatchKMeans. Bạn không thể sử dụng số liệu Manhattan ở ngoài hộp, nhưng bạn có thể thực hiện của riêng bạn. Có thể thử thực hiện tiêu chuẩn với số liệu euclide trước.

Tôi không biết nhiều thuật toán phân cụm không thực hiện khoảng cách hai chiều.

Sử dụng trung tâm dưới cùng mới được gắn cheat-sheet: mặc dù may mắn.

Answer 3

Bạn có thể thực hiện việc này bằng cách sử dụng DBSCAN của scikit-learn với chỉ số haversine và thuật toán cây bóng. Bạn không cần phải tính toán trước ma trận khoảng cách.

Ví dụ này clusters over a million GPS latitude-longitude points với DBSCAN/haversine và tránh các vấn đề sử dụng bộ nhớ:

df = pd.read_csv('gps.csv') 
coords = df.as_matrix(columns=['lat', 'lon']) 
db = DBSCAN(eps=eps, min_samples=ms, algorithm='ball_tree', metric='haversine').fit(np.radians(coords)) 

Lưu ý rằng điều này đặc biệt sử dụng scikit-học v0.15, như một số phiên bản trước/sau dường như đòi hỏi một khoảng cách đầy đủ ma trận để được tính toán, mà thổi lên RAM của bạn thực sự nhanh chóng. Nhưng nếu bạn sử dụng Anaconda, bạn có thể nhanh chóng thiết lập này với:

conda install scikit-learn=0.15 

Hoặc, tạo ra một môi trường ảo sạch cho công việc phân nhóm này:

conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter 
activate clusterenv