Cosine tương đồng của Vectors, với <O (n^2) phức tạp

Question

Sau khi nhìn xung quanh trang web này cho các vấn đề tương tự, tôi thấy điều này: http://math.nist.gov/javanumerics/jama/ và điều này: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html

Tuy nhiên, có vẻ như những chạy trong thời gian O (n^2). Tôi đã làm một số cụm tài liệu và nhận thấy mức độ phức tạp này không khả thi khi giao dịch với các bộ tài liệu nhỏ. Do, đối với sản phẩm dấu chấm, chúng tôi chỉ cần các thuật ngữ vectơ chứa trong cả hai vec-tơ thì có thể đặt các vectơ trong cây và do đó tính toán sản phẩm chấm với độ phức tạp n log n, trong đó n là số lượng từ duy nhất thấp nhất trong 1 trong 2 tài liệu.

Tôi có thiếu gì đó không? Có một thư viện java mà thực hiện điều này?

cảm ơn

Answer 1

Nếu bạn lưu trữ các phần tử vectơ trong phần bắt buộc, tra cứu chỉ là log n, không? Lặp qua tất cả các khóa trong tài liệu nhỏ hơn và xem chúng có tồn tại trong một khóa lớn hơn không ..?

Answer 2

Hashmap là tốt, nhưng có thể mất rất nhiều bộ nhớ.

Nếu vectơ của bạn được lưu trữ dưới dạng cặp khóa-giá trị được sắp xếp theo khóa thì phép nhân vector có thể được thực hiện trong O (n): bạn chỉ cần lặp song song trên cả hai vectơ (cùng một lần lặp được sử dụng, ví dụ: trong thuật toán sắp xếp hợp nhất). Các giả cho phép nhân:

i = 0 
j = 0 
result = 0 
while i < length(vec1) && j < length(vec2): 
    if vec1[i].key == vec2[j].key: 
    result = result + vec1[i].value * vec2[j].value 
    else if vec1[i].key < vec2[j].key: 
    i = i + 1 
    else 
    j = j + 1 

Answer 3

Nếu bạn chỉ muốn giới thiệu các mặt hàng có hạn, cho các hạng mục ví dụ mét, để tất cả các mục trong một bộ với kích thước của n, sự phức tạp không cần phải là n^2, nhưng m * n. Vì m là hằng số, độ phức tạp là tuyến tính.

Bạn có thể kiểm tra với dự án simbase https://github.com/guokr/simbase, đây là cơ sở dữ liệu vectơ tương tự vectơ.

Simbase sử dụng dưới đây khái niệm:

• Vector thiết lập: một tập hợp các vectơ
• Cơ sở: cơ sở cho vectơ, vectơ trong một bộ vector có cùng sở
• Khuyến nghị: một hướng nhị phân mối quan hệ giữa hai tập hợp vector có cùng một cơ sở

Answer 4

Nếu bạn định sử dụng tính tương tự cosin như một cách tìm các cụm tài liệu tương tự, bạn có thể muốn sider nhìn vào locality-sensitive hashing, một phương pháp dựa trên băm được thiết kế đặc biệt với điều này trong tâm trí. Trực quan, LSH băm các vectơ theo cách có xác suất cao đặt các phần tử tương tự vào cùng một nhóm và các phần tử ở xa thành các nhóm khác nhau. Có các lược đồ LSH sử dụng tính tương tự cosin như khoảng cách cơ bản của chúng, vì vậy để tìm các cụm bạn sử dụng LSH để đưa mọi thứ vào các nhóm và sau đó chỉ tính toán khoảng cách hai chiều của các phần tử trong cùng một nhóm. Trong trường hợp xấu nhất này sẽ là bậc hai (nếu mọi thứ rơi vào cùng một nhóm), nhưng có nhiều khả năng bạn sẽ có một sự sụt giảm đáng kể trong công việc.

Hy vọng điều này sẽ hữu ích!