2. User-user Collaborative Filtering 4. Lập trình sẵn Collaborative Filtering trên Python

1. Giới thiệu

Trong Content-based Recommendation Systems, chúng ta đã làm cho quen với cùng 1 Hệ thống gợi nhắc sản phẩm đơn giản dễ dàng dựa trên đặc trưng của mỗi item. Đặc điểm của Content-based Recommendation Systems là vấn đề xây dựng tế bào hình cho từng user không nhờ vào vào các users không giống mà phụ thuộc vào vào profile của từng items. Việc làm này có lợi thế là tiết kiệm bộ lưu trữ và thời gian tính toán. Đồng thời, hệ thống có tác dụng tận dụng những thông tin đặc thù của từng item như được miêu tả trong bản tế bào tả (description) của từng item. Bản mô tả này hoàn toàn có thể được xây dựng vị nhà hỗ trợ hoặc được thu thập bằng cách yêu mong users lắp tags cho items. Việc xây dựng feature vector cho mỗi item thường bao gồm các kỹ thuật xử lý ngôn ngữ tự nhiên và thoải mái (Natural Language Processing - NLP).

Bạn đang xem: Collaborative filtering là gì

Cách có tác dụng trên gồm hai yếu điểm cơ bản. Thứ nhất, lúc xây dựng mô hình cho một user, các hệ thống Content-based ko tận dụng được thông tin từ những users khác. Những thông tin này hay rất có ích vì hành vi mua sắm và chọn lựa của những users thường được đội thành một vài nhóm đối chọi giản; nếu như biết hành vi mua sắm của một vài ba users vào nhóm, hệ thống nên suy luận ra hành vi của những users còn lại. Thứ hai, không hẳn lúc nào chúng ta cũng tất cả bản mô tả cho mỗi item. Việc yêu mong users đính thêm tags còn trở ngại hơn vị không phải ai cũng sẵn sàng làm việc đó; hoặc tất cả làm nhưng mà sẽ mang xu hướng cá nhân. Những thuật toán NLP cũng phức tạp hơn ở việc phải xử lý các từ ngay gần nghĩa, viết tắt, sai chính tả, hoặc được viết ở các ngôn ngữ không giống nhau.

Những điểm yếu phía trên hoàn toàn có thể được giải quyết bằng Collaborative Filtering (CF). Trong bài viết này, tôi sẽ trình bày tới chúng ta một phương pháp CF mang tên là Neighborhood-based Collaborative Filtering (NBCF). Bài tiếp theo sẽ trình bày về một phương thức CF khác có tên Matrix Factorization Collaborative Filtering. Khi chỉ nói Collaborative Filtering, họ sẽ ngầm gọi rằng cách thức được áp dụng là Neighborhood-based.

Ý tưởng cơ bạn dạng của NBCF là xác minh mức độ quan lại tâm của một user cho tới một item dựa trên các users không giống gần giống với user này. Vấn đề gần giống nhau giữa những users hoàn toàn có thể được khẳng định thông qua mức độ quan liêu tâm của những users này tới những items khác mà hệ thống đã biết. Ví dụ, A, B phần lớn thích phim Cảnh sát hình sự, tức đều rate bộ phim truyện này 5 sao. Ta vẫn biết A đều thích Người phán xử, vậy nhiều kỹ năng B cũng thích bộ phim này.

Các chúng ta cũng có thể đã hình dung ra, hai thắc mắc quan trọng duy nhất trong một hệ thống Neighborhood-based Collaborative Filtering là:

Làm nuốm nào xác minh được sự tương tự nhau giữa hai users? lúc đã xác định được những users gần như là nhau (similar users) rồi, làm núm nào dự đoán được mức độ quan tâm của một user lên một item?

Việc xác minh mức độ đon đả của mỗi user cho tới một item dựa trên mức độ thân mật của similar users tới item đó còn gọi là User-user collaborative filtering. Có 1 hướng tiếp cận khác được cho là làm việc kết quả hơn là Item-item collaborative filtering. Trong hướng tiếp cận này, cầm cố vì xác định user similarities, khối hệ thống sẽ khẳng định item similarities. Trường đoản cú đó, hệ thống gợi ý những items gần kiểu như với số đông items nhưng user tất cả mức độ ân cần cao.

Cấu trúc của nội dung bài viết như sau: Mục 2 sẽ trình diễn User-user Collaborative Filtering. Mục 3 đang nêu một trong những hạn chế của User-user Collaborative Filtering và giải pháp khắc phục bởi Item-item Collaborative Filtering. Kết quả của hai phương pháp này đã được trình bày qua ví dụ trên cơ sở dữ liệu MovieLens 100k trong Mục 4. Một vài bàn luận và Tài liệu tham khảo được đến trong Mục 5 với 6.

2. User-user Collaborative Filtering

2.1. Similarity functions

Công việc đặc biệt quan trọng nhất cần làm trước tiên trong User-user Collaborative Filtering là phải xác định được sự tương đương nhau (similarity) thân hai users. Tài liệu duy nhất chúng ta có là Utility matrix (mathbfY), vậy yêu cầu sự như thể nhau này buộc phải được xác minh dựa trên các cột tương ứng với hai users vào ma trận này. Xét lấy ví dụ trong Hình 1.


*
Hình 1: lấy một ví dụ về utility matrix dựa vào số sao một user rate cho 1 item. Một phương pháp trực quan, hành vi của (u_0) giống như với (u_1) rộng là (u_2, u_3, u_4, u_5, u_6). Từ đó rất có thể dự đoán rằng (u_0) sẽ thân thiết tới (i_2) vị (u_1) cũng thân mật tới item này.

Giả sử có các users từ (u_0) đến (u_6) và các items từ (i_0) đến (i_4) trong các số ấy các số trong mỗi ô vuông biểu lộ số sao nhưng mỗi user đang rated cho item với mức giá trị cao hơn nữa thể hiện nay mức độ quan tiền tâm cao hơn. Các dấu hỏi chấm là các giá trị mà khối hệ thống cần đề nghị đi tìm. Đặt mức độ tương đương nhau của nhị users (u_i, u_j) là ( extsim(u_i, u_j)).

Quan cạnh bên đầu tiên chúng ta có thể nhận thấy là những (u_0, u_1) thích (i_0, i_1, i_2) và không thích (i_3, i_4) cho lắm. Điều ngược lại xảy ra ở các users còn lại. Bởi vì vậy, một similiarity function xuất sắc cần đảm bảo:

< extsim(u_0, u_1) > extsim(u_0, u_i), ~forall i > 1.>

Từ đó, để khẳng định mức độ quan tâm của (u_0) lên (i_2), bọn họ nên dựa vào hành vi của (u_1) lên sản phẩm này. Khôn xiết may rằng (u_1) đã thích (i_2) nên hệ thống cần recommend (i_2) mang lại (u_0).

Câu hỏi đề ra là: hàm số similarity như thế nào là tốt? Để đo similarity thân hai users, cách thường làm là xây dừng feature vector cho mỗi user rồi áp dụng một hàm có công dụng đo similarity giữa hai vectors đó. Chăm chú rằng việc xây dựng feature vector này khác với câu hỏi xây dựng chiến thắng profiles như vào Content-based Recommendation Systems. Những vectors này được sản xuất trực tiếp dựa trên Utility matrix chứ không cần dùng dữ liệu ngoài như thành công profiles. Với mỗi user, thông tin duy nhất họ biết là các ratings nhưng user đó đã thực hiện, tức cột tương ứng với user kia trong Utility matrix. Tuy nhiên, trở ngại là các cột này thường có tương đối nhiều mising ratings vày mỗi user thường xuyên chỉ rated một số lượng rất nhỏ tuổi các items. Phương pháp khắc phục là bằng phương pháp nào đó, ta giúp khối hệ thống điền những giá trị này thế nào cho việc điền không làm ảnh hưởng nhiều cho tới sự như thể nhau giữa hai vector. Việc điền này chỉ ship hàng cho việc tính similarity chứ không hẳn là suy luận ra giá trị cuối cùng.

Vậy mỗi lốt ‘?’ đề nghị được thay vày giá trị nào để hạn chế việc sai lệch quá nhiều? Một lựa chọn bạn cũng có thể nghĩ tới là thay các dấu ‘?’ bởi giá trị ‘0’. Điều này không thực sự giỏi vì quý hiếm ‘0’ tương ứng với nút độ thân yêu thấp nhất. Một giá trị an toàn rộng là 2.5 vày nó là trung bình cùng của 0, mức thấp nhất, với 5, nấc cao nhất. Mặc dù nhiên, giá bán trị này còn có hạn chế đối với những users dễ tính hoặc khó tính. Với những users dễ tính, thích khớp ứng với 5 sao, không thích hoàn toàn có thể ít sao rộng 1 chút, 3 sao chẳng hạn. Bài toán chọn quý hiếm 2.5 sẽ làm cho các items còn lại là vượt negative so với user đó. Điều ngược lại xảy ra với hồ hết user khó chịu hơn lúc chỉ đến 3 sao cho các items bọn họ thích cùng ít sao rộng cho đông đảo items bọn họ không thích.

Một quý giá khả dĩ rộng cho bài toán này là trung bình cộng của những ratings nhưng user tương xứng đã thực hiện. Vấn đề này sẽ tránh khỏi việc users quá tức giận hoặc dễ dàng tính, tức dịp nào cũng có những items mà một user say đắm hơn so với số đông items khác.

Hãy cùng xem lấy một ví dụ trong Hình 2a) với 2b).


*

Hình 2: Ví dụ biểu lộ User-user Collaborative Filtering. A) Utility Matrix ban đầu. B) Utility Matrix đang được chuẩn hoá. C) User similarity matrix. D) Dự đoán những (normalized) ratings còn thiếu. E) Ví dụ về phong thái dự đoán normalized rating của (u_1) mang đến (i_1). F) Dự đoán những (denormalized) ratings còn thiếu.

Chuẩn hoá dữ liệu:

Hàng cuối cùng trong Hình 2a) là giá trị trung bình của ratings cho từng user. Quý hiếm cao tương xứng với những user dễ tính với ngược lại. Lúc đó, nếu tiếp tục trừ từ từng rating đi giá trị này với thay các giá trị chưa biết bằng 0, ta sẽ được normalized utility matrix như vào Hình 2b). Chúng ta cũng có thể thắc mắc vì sao bước chuẩn hoá đó lại quan trọng, câu vấn đáp ở ngay lập tức đây:

việc trừ đi trung bình cùng của mỗi cột khiến trong trong những cột bao hàm giá trị dương cùng âm. Hồ hết giá trị dương tương ứng với vấn đề user ham mê item, đều giá trị âm tương ứng với câu hỏi user không ưng ý item. Số đông giá trị bằng 0 khớp ứng với bài toán chưa xác định được liệu user bao gồm thích item xuất xắc không. Về mặt kỹ thuật, số chiều của utility matrix là không nhỏ với hàng nghìn users với items, trường hợp lưu toàn thể các giá trị này trong một ma trận thì kỹ năng cao là sẽ không còn đủ bộ nhớ. Quan gần cạnh thấy rằng vì con số ratings biết trước thường xuyên là một vài rất nhỏ tuổi so với form size của utility matrix, sẽ tốt hơn nếu chúng ta lưu ma trận này dưới dạng sparse matrix, tức chỉ lưu các giá trị khác không và vị trí của chúng. Vị vậy, tốt hơn hết, những dấu ‘?’ đề xuất được thay bằng giá trị ‘0’, tức chưa khẳng định liệu user bao gồm thích item giỏi không. Việc này không những về tối ưu bộ nhớ mà việc đo lường và tính toán similarity matrix sau đây cũng hiệu quả hơn.

Sau lúc đã chuẩn hoá dữ liệu như trên, một vài similiraty function thường xuyên được sử dụng là:

Cosine Similarity:

Đây là hàm được thực hiện nhiều nhất, và cũng rất gần gũi với chúng ta nhất. Nếu các bạn không nhớ bí quyết tính ( extcos) của góc thân hai vector (mathbfu_1, mathbfu_2) trong chương trình phổ thông, thì dưới đó là công thức:

< extcosine_similarity(mathbfu_1, mathbfu_2) = extcos(mathbfu_1, mathbfu_2) = fracmathbfu_1^Tmathbfu_2~~~~ (1)>

Trong đó (mathbfu_1, 2) là vectors tương ứng với users 1, 2 đã được chuẩn hoá như sinh sống trên.

Có một tin vui là python tất cả hàm cung cấp tính toán hàm số này một giải pháp hiệu quả.

Độ similarity của hai vector là một trong những số trong đoạn <-1, 1>. Giá trị bằng 1 biểu thị hai vector trọn vẹn similar nhau. Hàm số ( extcos) của một góc bởi 1 tức thị góc thân hai vector bằng 0, tức một vector bằng tích của một trong những dương cùng với vector còn lại. Quý giá ( extcos) bởi -1 bộc lộ hai vector này trọn vẹn trái ngược nhau. Điều này cũng phải chăng , tức khi hành vi của nhị users là trọn vẹn ngược nhau thi similarity giữa hai vector đó là thấp nhất.

Ví dụ về cosine_similarity của các users vào Hình 2b) được mang đến trong Hình 2c). Similarity matrix (mathbfS) là 1 trong ma trận đối xứng bởi ( extcos) là 1 trong những hàm chẵn, và nếu user A tương đương user B thì điều trái lại cũng đúng. Những ô blue color trên đường chéo đều bởi 1 vì chưng đó là ( extcos) của góc giữa 1 vector và bao gồm nó, tức ( extcos(0) = 1). Khi giám sát và đo lường ở quá trình sau, chúng ta không cần thân thiện tới các giá trị 1 này. Liên tục quan sát những vector hàng tương xứng với (u_0, u_1, u_2), chúng ta sẽ thấy một vài nét thú vị:

(u_0) gần với (u_1) và (u_5) (độ giống như nhau là dương) hơn những users còn lại. Bài toán similarity cao giữa (u_0) cùng (u_1) là dễ dàng nắm bắt vì cả hai đều có xu hướng thân mật tới (i_0, i_1, i_2) hơn các items còn lại. Việc (u_0) gần cùng với (u_5) thoạt đầu có vẻ vô lý bởi (u_5) reviews thấp những items nhưng mà (u_0) review cao (Hình 2a)); tuy nhiên khi quan sát vào ma trận utility đã chuẩn hoá ở Hình 2b), ta thấy rằng vấn đề này là hòa hợp lý. Vị item duy nhất nhưng mà cả hai users này đã đưa thông tin là (i_1) với các giá trị tương ứng đều là tích cực.

(u_1) gần với (u_0) với xa những users còn lại.

(u_2) ngay gần với (u_3, u_4, u_5, u_6) và xa các users còn lại.

Từ similarity matrix này, bạn có thể phân nhóm những users ra làm cho hai đội ((u_0, u_1)) với ((u_2, u_3, u_4, u_5, u_6)). Vì chưng ma trận (mathbfS) này nhỏ tuổi nên chúng ta cũng có thể dễ dàng quan tiếp giáp thấy điều này; khi số users béo hơn, việc xác định bằng mắt thường là ko khả thi. Câu hỏi xây dựng thuật toán phân nhóm những users (users clustering) rất có thể vẫn được trình bày ở một trong các bài viết tiếp theo.

Có một chăm chú quan trọng ở đây là khi số lượng users lớn, ma trận (mathbfS) cũng tương đối lớn và nhiều kĩ năng là không tồn tại đủ bộ lưu trữ để lưu lại trữ, trong cả khi chỉ lưu hơn một phần số các bộ phận của ma trận đối xứng này. Với những trường vừa lòng đó, bắt đầu mỗi user, họ chỉ đề nghị tính cùng lưu công dụng của một hàng của similarity matrix, khớp ứng với việc độ giống nhau thân user đó và những users còn lại.

Trong bài viết này, tôi sẽ sử dụng similarity function này.

Person corelation:

Tôi xin không đi chi tiết về phần này, các bạn đọc đon đả có thể tham khảo thêm Pearson correlation coefficient - Wikipedia

2.2. Rating prediction

Việc xác minh mức độ thân thương của một user lên một item dựa trên các users ngay sát nhất (neighbor users) này khôn xiết giống với gần như gì chúng ta thấy trong bài xích 6: K-nearest neighbors. Khi làm việc với large-scale problems, chúng ta sẽ thấy thêm rằng cách thức lười học K-nearest neighbors (KNN) được sử dụng rất nhiều vì tính dễ dàng của nó. Tất nhiên, bọn họ không thể trực tiếp áp dụng KNN mà lại còn rất cần được làm thêm nhiều bước trung gian nữa.

Tương trường đoản cú như KNN, vào Collaborative Filtering, missing rating cũng rất được xác định dựa trên tin tức về (k) neighbor users. Vớ nhiên, họ chỉ thân yêu tới các users đã rated item sẽ xét. Predicted rating thường xuyên được xác minh là trung bình bao gồm trọng số của những ratings đã chuẩn hoá. Bao gồm một điểm cần lưu ý, trong KNN, những trọng số được khẳng định dựa trên distance thân 2 điểm, và những distance này là những số không âm. Trong những lúc đó, trong CF, các trọng số được khẳng định dựa bên trên similarity giữa hai users, mọi trọng số này có thể nhỏ tuổi hơn 0 như vào Hình 2c).

Công thức thông dụng được sử dụng để tham dự đoán rating của (u) đến (i) là:

(sự khác biết đối với trung bình bao gồm trọng số là chủng loại số có áp dụng trị tuyệt vời để xử lý các số âm).

trong đó (mathcalN(u, i)) là tập hợp (k) users trong neighborhood (tức tất cả similarity cao nhất) của (u) mà lại đã rated (i).

Hình 2d) thể hiện việc điền những giá trị còn thiếu trong normalized utility matrix. Những ô color nền đỏ thể hiện các giá trị dương, tức những itemscó thể users kia quan tâm. Ở đây, tôi đã lấy ngưỡng bởi 0, chúng ta hoàn toàn có thể chọn những ngưỡng khác 0.

Một lấy một ví dụ về vấn đề tính normalized rating của (u_1) mang đến (i_1) được mang đến trong Hình 2e) với số nearest neighbors là (k = 2). Các bước thực hiện nay là:

Xác định những users vẫn rated (i_1), đó là (u_0, u_3, u_5).

Xác định similarities của (u_1) với những users này ta cảm nhận (0.83, -0.40, -0.23). Hai ((k = 2)) giá chỉ trị lớn nhất là (0.83) với (-0.23) tương xứng với (u_0) và (u_5).

Xác định các normalized ratings của (u_0, u_5) mang đến (i_1), ta thu được hai giá trị lần lượt là (0.75) với (0.5).

Dự đoán kết quả:

Việc quy đổi những giá trị ratings đã chuẩn hoá về thang 5 rất có thể được thực hiện bằng cách cộng những cột của ma trận (hatmathbfY) với mức giá trị rating mức độ vừa phải của mỗi user như đang tính vào Hình 2a).

Việc hệ thống quyết định recommend items nào cho từng user có thể được xác minh bằng vô số phương pháp khác nhau. Rất có thể sắp xếp unrated items theo sản phẩm tự tự bự đến bé của những predicted ratings, hoặc chỉ chọn những itemsnormalized predicted ratings dương - tương ứng với việc user này có khá nhiều khả năng say đắm hơn.

Trước khi vào phần lập trình mang đến User-user CF, họ cùng chú ý Item-item CF.

3. Item-item Collaborative Filtering

Một số hạn chês của User-user CF:

Trên thực tế, số lượng users luôn to hơn số lượng items rất nhiều. Kéo theo đó là Similarity matrix là không nhỏ với số bộ phận phải lưu lại là rộng 1 nửa của bình phương con số users (chú ý rằng ma trận này là đối xứng). Vấn đề này, như đang đề cập sinh hoạt trên, để cho việc tàng trữ ma trận này trong vô số trường hợp là ko khả thi.

Ma trận Utility (mathbfY) thường là siêu sparse. Với số lượng users rất to lớn so với con số items, rất nhiều cột của ma trận này sẽ rất sparse, tức chỉ tất cả một vài phần tử khác 0. Vì sao là users thường lười rating. Cũng cũng chính vì việc này, một lúc user đó chuyển đổi rating hoặc rate thêm items, mức độ vừa phải cộng các ratings cũng giống như vector chuẩn chỉnh hoá tương ứng với user này biến hóa nhiều. Kéo theo đó, việc giám sát và đo lường ma trận Similarity, vốn tốn nhiều bộ nhớ lưu trữ và thời gian, cũng cần được tiến hành lại.

Ngược lại, nếu bọn họ tính toán similarity giữa các items rồi recommend phần đa items ngay gần giống với item thương mến của một user thì sẽ sở hữu được những lợi ích sau:

Vì số lượng items thường nhỏ hơn số lượng users, Similarity matrix trong trường hòa hợp này cũng nhỏ dại hơn nhiều, dễ dàng cho việc tàng trữ và thống kê giám sát ở quá trình sau.

Vì số lượng thành phần đã biết trong Utility matrix là giống hệt nhưng số hàng (items) ít hơn số cột (users), đề nghị trung bình, mỗi sản phẩm của ma trận này sẽ có được nhiều thành phần đã biết hơn số phần tử đã biết trong những cột. Việc này cũng dễ dàng nắm bắt vì từng item có thể được rated bởi nhiều users. Kéo theo đó, giá trị trung bình của mỗi hàng ít bị thay đổi hơn khi bao gồm thêm một vài ba ratings. Như vậy, việc update ma trận Similarity Matrix hoàn toàn có thể được tiến hành ít thường xuyên hơn.

Cách tiếp cận thứ hai này được call là Item-item Collaborative Filtering. Hướng tiếp cận này được sử dụng nhiều trong thực tiễn hơn.

Xem thêm: Giờ Trái Đất Là Gì Ngày Nào Và Ý Nghĩa Của Sự Kiện Giờ Trái Đất

Quy trình dự kiến missing ratings cũng tương tự như trong User-user CF. Hình 3 mô tả tiến trình này với lấy ví dụ như nêu ở phần trên.