Tính hiệu quả của khoảng cách euclide

Question

Tôi có một mảng MxN, trong đó M là số quan sát và N là thứ nguyên của mỗi véc tơ. Từ mảng vectơ này, tôi cần tính toán khoảng cách giữa các vectơ mean và minimum euclide.

Trong tâm trí của tôi, điều này đòi hỏi tôi phải tính toán _M C khoảng cách, mà là một O (n ^{min (k, n-k)}) thuật toán. My M là ~ 10.000 và N của tôi là ~ 1.000, và tính toán này mất ~ 45 giây.

Có cách nào hiệu quả hơn để tính toán các khoảng cách mean và min không? Có lẽ một phương pháp xác suất? Tôi không cần nó chính xác, chỉ cần đóng.

Answer 1

Bạn không mô tả nơi vectơ của bạn đến từ đâu, cũng không gì sử dụng bạn sẽ đặt mean và median tới. Dưới đây là một số quan sát về trường hợp chung. Phạm vi hạn chế, dung sai lỗi và các giá trị rời rạc có thể thừa nhận một cách tiếp cận hiệu quả hơn.

Khoảng cách giữa các điểm M có âm thanh bậc hai, O (M^2). Nhưng M/N là 10, khá nhỏ, và N là rất lớn, vì vậy dữ liệu có thể giống như một quả cầu lông trong 1e3-không gian. Tính toán centroid của M điểm, và sau đó tính toán M khoảng cách đến centroid, có thể trở nên hữu ích trong lĩnh vực vấn đề của bạn, khó nói.

Khoảng cách minimum khoảng cách giữa các điểm M thú vị hơn. Chọn một số lượng nhỏ các cặp ngẫu nhiên, giả sử 100, tính toán khoảng cách của chúng và mất một nửa mức tối thiểu là ước tính khoảng cách tối thiểu toàn cầu. (Xác thực bằng cách so sánh với một vài khoảng cách nhỏ nhất tiếp theo, nếu muốn.) Bây giờ hãy sử dụng không gian UB-tree để mô hình từng điểm là một số nguyên dương. Điều này liên quan đến việc tìm kiếm N minima cho các giá trị M x N, thêm các hằng số để min trở thành 0, tỉ lệ ước tính khoảng cách min toàn cầu tương ứng với ít nhất 1.0, và sau đó cắt ngắn thành số nguyên.

Với các vectơ đã biến đổi này trong tay, chúng tôi sẵn sàng biến chúng thành một đại diện UB-cây mà chúng ta có thể sắp xếp và sau đó thực hiện các truy vấn không gian lân cận gần nhất trên các giá trị được sắp xếp. Đối với mỗi điểm tính một số nguyên. Chuyển bit thứ tự thấp của giá trị của từng thứ nguyên vào kết quả, sau đó lặp lại. Tiếp tục lặp qua tất cả các kích thước cho đến khi các bit khác không được tiêu thụ và xuất hiện trong kết quả và tiến tới điểm tiếp theo. Sắp xếp số lượng các giá trị kết quả số nguyên, tạo ra một cấu trúc dữ liệu tương tự như chỉ mục PostGIS.

Bây giờ bạn có một đại diện cụ thể hỗ trợ các truy vấn hợp lý hiệu quả cho những người hàng xóm gần nhất (mặc dù thừa nhận N = 1e3 là bất tiện lớn). Sau khi tìm thấy hai hoặc nhiều hạt lân cận lân cận, bạn có thể truy vấn biểu diễn vector ban đầu để có được khoảng cách có độ phân giải cao giữa chúng, để phân biệt đối xử tốt hơn. Nếu phân phối dữ liệu của bạn hóa ra là có một số lượng lớn các điểm cho phép giảm bớt một chút từ hàng xóm gần nhất, ví dụ: vị trí của các nguyên tử oxy trong đó mỗi nguyên tử có một người bạn, sau đó tăng ước lượng khoảng cách tối thiểu toàn cầu để các bit đặt hàng thấp cung cấp sự phân biệt đối xử đầy đủ.

Cách tiếp cận cụ thể hóa tương tự sẽ được chia tỷ lệ thích hợp, ví dụ: Đầu vào 2 chiều và đánh dấu lưới trống ban đầu, sau đó quét các vùng lân cận ngay lập tức. Điều này phụ thuộc vào min toàn cầu nằm trong một khu vực "nhỏ", do quy mô thích hợp. Trong trường hợp của bạn, bạn sẽ đánh dấu một lưới N chiều.