Thuật toán đối sánh n-chiều

Question

Tìm kiếm một số lời khuyên tại đây. Có ai biết một nơi tốt để bắt đầu nhìn vào thuật toán phù hợp trong một không gian n chiều. Ví dụ: bất kỳ trang web hẹn hò nào đều phải sử dụng một số loại thuật toán để khớp với 2 người. Những gì tôi đã đọc là chúng ta có thể ánh xạ các đặc điểm của một người trong một mảng n chiều với một hệ thống điểm cho mỗi đặc tính. Khi chúng ta có tất cả các đặc tính (có sẵn) của một người, chúng ta có thể biểu diễn người này ở một điểm trong một mảng n chiều. Sau đó, để phù hợp với 2 người sẽ đơn giản như tìm khoảng cách ngắn nhất giữa 2 điểm trong mảng n-dim này. Có ai có bất kỳ tài liệu tham khảo trong việc thực hiện các loại thuật toán? Ngôn ngữ tốt nhất để viết những loại nội dung này là gì?

Answer 1

Trước hết, hãy chọn ngôn ngữ bạn quen thuộc nhất. Các thuật toán để xử lý này khá đơn giản, và nên làm việc trong bất kỳ ngôn ngữ hiện đại nào. (Miễn là có một số khái niệm về mảng, và có khả năng là một thư viện ma trận, bạn nên được tốt.) Tôi đã thực hiện nhiều trong số này trong C, C++, và C# trước, nhưng thấy triển khai trong python, vb.net, vv

Tùy thuộc vào những gì bạn đang cố gắng làm, có một vài tùy chọn.

Điều đó đang được nói, những gì bạn muốn làm tùy thuộc vào mục tiêu của bạn. Nếu bạn chỉ muốn tìm kết quả phù hợp nhất, bạn có thể sử dụng phép tính khoảng cách đơn giản (ví dụ: sqrt tổng bình phương cho mỗi thứ nguyên/thuộc tính trong mảng n chiều), tùy chọn cân trọng lượng khoảng cách của mỗi thuộc tính và sử dụng điểm gần nhất.

Nếu bạn muốn nhóm người với nhau, bạn sẽ muốn xem clustering algorithms. Đối với dữ liệu như thế này, tôi sẽ nghi ngờ rằng một số dạng K-Means clustering hoặc fuzzy c-means clustering sẽ hoạt động tốt nhất.

Answer 2

Nếu bạn muốn tìm đối sánh gần nhất cho một người, Bentley & Shamos đã xuất bản phương pháp phân chia và chinh phục đa chiều: Chia và chinh phục trong thời gian O (N log N): Divide-and-conquer in multidimensional space trong Kỷ yếu của Hội nghị chuyên đề ACM hàng năm lần thứ 8 về Lý thuyết tính toán năm 1976. Nếu bạn không thể nhận được một bản sao this cũng có thể hữu ích.

Tuy nhiên đối với ứng dụng ví dụ của bạn thực sự tìm thấy người hàng xóm gần nhất dường như không phải là vấn đề lớn nhất - điều phức tạp hơn nhiều là lập bản đồ đầu vào thành các thứ nguyên. Ví dụ: nếu một thứ nguyên là "thích động vật", bạn cung cấp giá trị nào cho người thích chó & mèo nhưng không thể chịu được ngựa? Điều gì về một người yêu ngựa, nghĩ rằng chó là OK, là khó chịu bởi mèo và là ambivalent về cá vàng?

Answer 3

Quy trình bạn đề cập đến được gọi là hàng xóm gần nhất k, với k = 1. Đó là cách tiếp cận trực quan nhất để tìm các véc tơ tương tự.

http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

Answer 4

Giải pháp sau đây.

Giả sử người dùng là U1, U2, U3, U4, U5 .... Un. Thuộc tính là A1, A2, A3, A4, A5 ..... Am

cửa hàng này như

A1 - U1, U2, U3 ... A2 - U4, U6, U7 ... . A3 -

Thuộc tính tiểu sử là chỉ mục và lưu trữ tất cả người dùng. Bây giờ, nếu một Người dùng mới đến, hãy xem các thuộc tính của nó và cho các thuộc tính đó, hãy tìm những người phổ biến. số lần một người tồn tại trong các danh sách này - xếp hạng cao hơn.

Answer 5

Những gì bạn mô tả với ví dụ của mình không phải là đối sánh n-dimentional, mà là bipartite matching các nút có nhiều tính năng. (Bạn sẽ cần phải cung cấp một chức năng mà sẽ, cho hai người tính toán khoảng cách này). Nên có thuật toán rất hiệu quả cho điều đó. Trong kết hợp n-dimentional bạn sẽ cố gắng để phù hợp với các nút từ nhiều hơn hai bộ (trong ví dụ của bạn, giả sử bạn có thể cắt người để cơ thể, linh hồn, và sở thích âm nhạc, sau đó kết hợp chúng để làm cho người mới. cắt những người khác nhau, và tái kết hợp chúng để những người mới thiết kế sẽ thực hiện các cặp vợ chồng thực sự tốt đẹp: D) Đây là wikipedia article for 3-dimentional matching, đó là np-hoàn thành.

Ngoài ra, như được ghi chú bởi người khác, nếu mục tiêu của bạn không phù hợp với từng người, mà là tìm các nhóm tương thích, bạn nên cân nhắc phân nhóm chúng thành các nhóm. Điều này có thể được thực hiện với ví dụ: Unsupervised Learning