Tạo 'hàng xóm' cho người dùng dựa trên xếp hạng

Question

Tôi đang tìm các kỹ thuật để tạo 'hàng xóm' (những người có hương vị tương tự) cho người dùng trên trang web tôi đang làm việc; một cái gì đó tương tự như cách last.fm hoạt động.

Hiện tại, tôi có chức năng tương thích với người dùng có thể tham gia. Nó xếp hạng người dùng khi có 1) đánh giá các mục tương tự 2) đã xếp hạng mục tương tự. Hàm này nặng 2 điểm và điều này sẽ quan trọng nhất nếu tôi chỉ sử dụng một trong những yếu tố này khi tạo ra 'hàng xóm'.

Một ý tưởng tôi đã có thể chỉ là tính toán sự tương thích của mọi kết hợp người dùng và chọn người dùng được xếp hạng cao nhất làm người hàng xóm cho người dùng. Nhược điểm của điều này là khi số lượng người dùng tăng lên thì quá trình này mất rất nhiều thời gian. Đối với chỉ 1000 người dùng, nó cần 1000C2 (0.5 * 1000 * 999 = = 499 500) các cuộc gọi đến chức năng tương thích mà có thể rất nặng trên máy chủ cũng.

Vì vậy, tôi đang tìm kiếm bất kỳ lời khuyên, liên kết đến bài viết nào vv về cách tốt nhất để đạt được một hệ thống như thế này.

Answer 1

Sự cố có vẻ như là 'vấn đề phân loại'. Có rất nhiều giải pháp và cách tiếp cận.

Để bắt đầu kiểm tra thăm dò này: http://en.wikipedia.org/wiki/Statistical_classification

Answer 2

Trong Lập trình cuốn sách Collective Intelligence
http://oreilly.com/catalog/9780596529321

Chương 2 "Làm khuyến nghị" không một công việc thực sự tốt của phác thảo phương pháp giới thiệu sản phẩm đến người dựa về sự tương đồng giữa người dùng. Bạn có thể sử dụng các thuật toán tương tự để tìm 'hàng xóm' mà bạn đang tìm kiếm. Chương này có sẵn trên tìm kiếm sách của Google tại đây:
http://books.google.com/books?id=fEsZ3Ey-Hq4C&printsec=frontcover

Answer 3

Bạn đã nghe nói về kohonen networks chưa?

Thuật toán học tập tự tổ chức của nó tập hợp các biến tương tự vào các vị trí tương tự. Mặc dù hầu hết các trang web giống như trang web tôi liên kết bạn để hiển thị mạng dưới dạng giá thầu có ít tham gia vào việc mở rộng thuật toán thành siêu dữ liệu nhiều chiều.

Với cấu trúc dữ liệu tìm và lưu trữ hàng xóm có thị hiếu tương tự là tầm thường vì người dùng tương tự nên lưu trữ vào các vị trí tương tự (gần giống như mã băm đảo ngược).

Điều này làm giảm vấn đề của bạn trong việc tìm kiếm các biến xác định sự giống nhau và thiết lập khoảng cách giữa các giá trị liệt kê có thể, ví dụ như cổ điển và âm thanh gần nhau trong khi kim loại chết và reggae khá xa (ít nhất là trong ý kiến ​​của tôi)

Bằng cách này để tìm các biến chia tốt, thuật toán tốt nhất là decision tree. Các nút gần gũi hơn với gốc sẽ là các biến quan trọng nhất để thiết lập 'sự gần gũi'.

Answer 4

Dường như bạn cần đọc khoảng clustering algorithms. Ý tưởng chung là thay vì so sánh mọi điểm với mỗi điểm khác mỗi khi bạn chia chúng thành các cụm điểm tương tự. Sau đó, khu phố có thể là tất cả các điểm trong cùng một cụm. Số lượng/kích thước của các cụm thường là một tham số của thuật toán phân cụm.

Bạn có thể tìm thấy video about clustering trong chuỗi Google về cluster computing and mapreduce.

Answer 5

Mối quan tâm về hiệu suất có thể được giảm nhẹ đáng kể nếu bạn coi vấn đề này là vấn đề xây dựng/mẻ thay vì truy vấn thời gian thực.

Biểu đồ có thể được tính toán tĩnh, sau đó được cập nhật gần đây, ví dụ: hàng giờ, hàng ngày, v.v. để sau đó tạo các cạnh và dung lượng được tối ưu hóa cho truy vấn thời gian chạy, ví dụ: top 10 người dùng tương tự cho mỗi người dùng.

+1 cho lập trình tập thể dục thông minh quá - nó là rất nhiều thông tin - muốn nó không phải (hoặc tôi đã!) Như Python theo định hướng, nhưng vẫn còn tốt.

Answer 6

Hãy chắc chắn xem Collaborative Filtering. Nhiều hệ thống đề xuất sử dụng tính năng lọc cộng tác để đề xuất các mục cho người dùng. Họ làm điều đó bằng cách tìm kiếm 'hàng xóm' và sau đó đề xuất các mặt hàng mà hàng xóm của bạn đánh giá cao nhưng bạn chưa xếp hạng. Bạn có thể đi xa như việc tìm kiếm hàng xóm, và ai biết được, có thể bạn sẽ muốn các khuyến nghị trong tương lai.

GroupLens là phòng thí nghiệm nghiên cứu tại Đại học Minnesota nghiên cứu kỹ thuật lọc cộng tác. Họ có rất nhiều nghiên cứu được xuất bản cũng như một vài tập dữ liệu mẫu.

Netflix Prize là cuộc cạnh tranh để xác định ai có thể giải quyết vấn đề này một cách hiệu quả nhất. Theo các liên kết ngoài số LeaderBoard của chúng. Một vài đối thủ cạnh tranh chia sẻ các giải pháp của họ.

Theo như một giải pháp tính toán tốn kém, bạn có thể thử này:

• Tạo mục cho các mục của bạn. Nếu chúng ta đang nói về âm nhạc, chúng có thể là nhạc cổ điển, rock, jazz, hip-hop ... hoặc đi xa hơn: Grindcore, Math Rock, Riot Grrrl ...
• Bây giờ, mỗi khi người dùng xếp hạng một mục, hãy tăng xếp hạng của họ lên cấp danh mục. Vì vậy, bạn biết 'Người dùng A' thích Honky Tonk và Acid House bởi vì họ cung cấp cho những mục này xếp hạng cao thường xuyên. Tần suất và sức mạnh có lẽ quan trọng đối với điểm tổng hợp danh mục của bạn.
• Khi đến lúc tìm hàng xóm, thay vì bay qua tất cả các xếp hạng, chỉ cần tìm điểm tương tự trong các danh mục.

Phương pháp này sẽ không chính xác nhưng nhanh.

Chúc mừng.

Answer 7

Điều bạn cần là thuật toán phân cụm, thuật toán này sẽ tự động nhóm những người dùng tương tự lại với nhau. Khó khăn đầu tiên mà bạn đang phải đối mặt là hầu hết các thuật toán phân cụm mong đợi các mục mà chúng nhóm lại được biểu diễn dưới dạng các điểm trong không gian Euclide. Trong trường hợp của bạn, bạn không có tọa độ của các điểm. Thay vào đó, bạn có thể tính giá trị của hàm "giống nhau" giữa các cặp.

Một khả năng tốt ở đây là sử dụng spectral clustering, cần chính xác những gì bạn có: ma trận tương tự. Nhược điểm là bạn vẫn cần phải tính toán chức năng tương thích của bạn cho mỗi cặp điểm, i. e. thuật toán là O (n^2).

Nếu bạn hoàn toàn cần thuật toán nhanh hơn O (n^2), thì bạn có thể thử phương pháp được gọi là dissimilarity spaces. Ý tưởng rất đơn giản. Bạn đảo ngược chức năng tương thích của bạn (e. G. Bằng cách lấy nghịch đảo của nó) để biến nó thành một thước đo không giống nhau hoặc khoảng cách. Sau đó, bạn so sánh mọi mục (người dùng, trong trường hợp của bạn) với một tập hợp các mục nguyên mẫu và xử lý khoảng cách kết quả dưới dạng tọa độ trong không gian. Ví dụ, nếu bạn có 100 nguyên mẫu, thì mỗi người dùng sẽ được biểu diễn bằng một vectơ gồm 100 phần tử, i. e. bởi một điểm trong không gian 100 chiều.Sau đó, bạn có thể sử dụng bất kỳ thuật toán phân cụm chuẩn nào, chẳng hạn như K-means.

Câu hỏi bây giờ là làm thế nào để bạn chọn nguyên mẫu và số lượng bạn cần. Tuy nhiên, nhiều chẩn đoán khác nhau đã được thử, đây là một số dissertation cho rằng việc chọn nguyên mẫu ngẫu nhiên có thể là đủ. Nó cho thấy các thí nghiệm trong đó sử dụng 100 hoặc 200 nguyên mẫu được lựa chọn ngẫu nhiên tạo ra kết quả tốt. Trong trường hợp của bạn nếu bạn có 1000 người dùng và bạn chọn 200 người trong số họ là nguyên mẫu, thì bạn sẽ cần đánh giá chức năng tương thích của mình 200.000 lần, đây là yếu tố cải thiện 2,5 so với mỗi cặp. Tuy nhiên, lợi thế thực sự là đối với 1.000.000 người dùng, 200 nguyên mẫu sẽ vẫn đủ, và bạn sẽ cần phải thực hiện 200.000 so sánh, thay vì 500.000.000.000 một cải tiến của một hệ số 2500. Điều bạn nhận được là thuật toán O (n), tốt hơn O (n^2), mặc dù có một yếu tố không đổi lớn.