tương đồng giữa người dùng dựa trên Votes

Question

phép nói rằng tôi có một tập hợp người dùng, một tập hợp các bài hát, và một tập hợp các phiếu trên mỗi bài hát:

=========== =========== ======= 
User  Song  Vote 
=========== =========== ======= 
user1  song1  [score] 
user1  song2  [score] 
user1  song3  [score] 
user2  song1  [score] 
user2  song2  [score] 
user2  song3  [score] 
user3  song1  [score] 
user3  song2  [score] 
user3  song3  [score] 
user-n  song-n  [score] 
=========== =========== ======= 

whats cách hiệu quả nhất để tính toán sử dụng tương tự dựa trên bài hát-phiếu bầu? có cách nào tốt hơn so với lặp lại trên mọi người dùng và mọi phiếu bầu cho mỗi bài hát không?

Answer 1

Có hai chỉ số phổ biến mà có thể được sử dụng để tìm điểm tương đồng giữa người sử dụng:

1. Euclide cách, đó là chính xác những gì bạn đang suy nghĩ: hãy tưởng tượng một đồ thị n chiều có cho mỗi trục một bài hát được xem xét bởi hai người dùng liên quan (u1 và * u2) và giá trị trên trục của nó là điểm số. Bạn có thể dễ dàng tính toán độ tương tự bằng cách sử dụng công thức:

   cho mỗi bài hát được u1 và u2 đánh giá, tính pow(u1.song.score - u2.song.score, 2) và thêm tất cả lại với nhau thành sum_of_powers. Hệ số tương tự sau đó được đưa ra bởi 1/1 + (sqrt(sum_of_powers)).

2. Tương quan Pearson (hoặc hệ số tương quan): đó là cách tiếp cận tốt hơn để tìm xem có bao nhiêu bộ dữ liệu có liên quan với nhau. Cách tiếp cận này sử dụng các công thức phức tạp hơn và một ít nền thống kê, kiểm tra nó ở đây: wiki. Bạn sẽ có biểu đồ cho mỗi vài người dùng, sau đó bạn vẽ điểm theo điểm số .. ví dụ: nếu aSong đã được bỏ chọn 2 từ u1 và 4 từ u2, nó sẽ vẽ điểm (2,4) (giả sử rằng user1 là trục x và u2 là trục y).

Chỉ cần làm rõ, bạn sử dụng tuyến tính hồi quy để tìm hai hệ số A và B, mô tả dòng giảm thiểu khoảng cách từ tất cả các điểm của đồ thị. Dòng này có công thức: y = Ax + B. Nếu hai bộ là các điểm tương tự nên gần với đường chéo chính để A nên có xu hướng 1 trong khi B đến 0. Không giả định giải thích này là đầy đủ hoặc như một tham chiếu vì nó thiếu tính chính xác và điển hình toán học, nó chỉ để cung cấp cho bạn một ý tưởng.

EDIT: được viết bởi những người khác, các thuật toán phức tạp hơn như số liệu cụm tồn tại, như k-means nhưng tôi khuyên bạn nên bắt đầu từ những cái đơn giản (trên thực tế bạn nên cần một cái gì đó khó khăn hơn ngay khi bạn nhận ra rằng kết quả này không đủ).

Answer 2

Bạn sẽ có thể tìm thấy một thuật toán tốt trong sách này: The Algorithm Design Manual bởi Steven Skiena.

Sách có toàn bộ các thuật toán cho các mục đích khác nhau. Bạn muốn có một thuật toán phân cụm đồ thị, tôi nghĩ vậy. Tôi không có bản sao của cuốn sách tiện dụng, vì vậy tôi không thể tìm kiếm nó cho bạn.

Tìm kiếm nhanh trên Google đã tìm thấy trang Wikipedia: http://en.wikipedia.org/wiki/Cluster_analysis Có lẽ điều đó sẽ hữu ích, nhưng tôi nghĩ cuốn sách giải thích rõ ràng hơn về thuật toán.

Answer 3

Tôi giới thiệu sách Programming Collective Intelligence từ Toby Segaran. Chương 3 mô tả các phương pháp phân cụm khác nhau như Hierarchical Clustering và K-means Clustering.

Các mã nguồn cho các ví dụ có sẵn here

Answer 4

Nếu bạn muốn có kết quả chính xác nhất, thì không, bạn phải lặp lại mọi thứ.

Nếu cơ sở dữ liệu của bạn đủ lớn, bạn chỉ có thể lấy mẫu thống kê, giả sử có từ 1.000 đến 10.000 người dùng và khớp với điều đó.

Bạn cũng sẽ tốt hơn để thêm một số bảng khác vào cơ sở dữ liệu, lưu trữ kết quả và chỉ cập nhật nó thường xuyên, thay vì tính toán điều này một cách nhanh chóng.

Answer 5

Ilya Grigorik đã thực hiện một loạt các thuật toán đề xuất, mặc dù ông tập trung vào Ruby. Dường như nằm trong phần máy học trong số archives của mình, nhưng không có liên kết phần trực tiếp.

Answer 6

Tôi nghĩ rất nhiều người ở đây thiếu tính đơn giản của câu hỏi. Anh ta không nói gì về việc tạo ra một hệ thống dự đoán xếp hạng. Anh chỉ muốn tính toán sự giống nhau giữa hành vi xếp hạng bài hát của từng người dùng và hành vi xếp hạng bài hát của người dùng khác. Hệ số tương quan Pearson cho chính xác điều đó. Có, bạn phải lặp qua từng cặp người dùng/người dùng.

EDIT:

Sau khi suy nghĩ về vấn đề này nhiều hơn một chút:

Pearson là tuyệt vời nếu bạn muốn sự tương đồng giữa thị hiếu hai người sử dụng, nhưng không phải mức độ 'opinionatedness' ... một người dùng tỷ lệ một loạt các bài hát 4, 5 và 6 sẽ tương quan hoàn hảo với người dùng khác có cùng mức độ bài hát 3, 6 và 9. Nói cách khác, họ có cùng "sở thích" (họ sẽ xếp hạng các bài hát theo cùng thứ tự), nhưng người dùng thứ hai được nhiều ý kiến ​​hơn. Nói cách khác, hệ số tương quan xử lý bất kỳ hai vectơ xếp hạng nào có mối quan hệ tuyến tính bằng nhau.

Tuy nhiên, nếu bạn muốn sự giống nhau giữa xếp hạng thực tế mà người dùng đã đưa ra cho mỗi bài hát, bạn nên sử dụng sai số bình phương gốc giữa hai vectơ xếp hạng. Đây là một số liệu hoàn toàn dựa trên khoảng cách (mối quan hệ tuyến tính không phát vào điểm tương đồng), vì vậy, 4,5,6 và 3,6,9 người dùng sẽ không có điểm tương đồng hoàn hảo.

Quyết định đi xuống theo ý bạn là "tương tự" ...

Đó là tất cả.

Answer 7

Nếu bạn muốn thực hiện theo cách gần đúng mà không cần truy cập tất cả các bản ghi, bạn có thể sử dụng Hệ số Jaccard. Có lẽ cần một số thích ứng nếu bạn muốn xem xét điểm số. Nhưng tôi đoán đó là giải pháp tốt nhất nếu hệ thống của bạn quá lớn và bạn không có thời gian để kiểm tra tất cả các bản ghi.