Tìm hiểu về Collaborative Filtering

Collaborative Filtering (CF – hay tạm dịch là lọc cộng tác) là một kỹ thuật hay trong xử lý dữ liệu mà cụ thể là trong mảng Recommender Systems (hay tạm dịch là hệ thống tư vấn). Đã bao giờ bạn vào Youtube và nhìn thấy một vài video mà Youtube tự đề xuất cho riêng bạn ví dụ như hình bên dưới (chú ý tới dòng chữ “Được đề xuất cho bạn“)?

Hình 1: Ví dụ về sản phẩm được người bán đề xuất cho người mua

Không chỉ Youtube, hầu như tất cả các trang web kinh doanh như Amazon hay Netflix đều cần phải sử dụng Collaborative Filtering để gợi ý tới khách hàng những sản phẩm mà người bán cho rằng rất thích hợp với người mua. Trong bài viết này, mình muốn tìm hiểu về Collaborative Filtering để có một cái nhìn sâu hơn về thuật toán hay và có tính ứng dụng rất cao này.

Bài viết được lấy cảm hứng từ bài giảng Collaborative Filtering của Standford University. Nội dung của bài viết phần lớn được lược dịch từ bài giảng này.

Giới thiệu về Collaborative Filtering

Hình 2: Biểu đồ Collaborative Filtering

Hình 2 là một biểu đồ đơn giản của Collaborative Filtering. Giả sử rằng bạn là một nhà phân tích dữ liệu khách hàng của một hệ thống rạp chiếu phim và bạn đang muốn tìm hiểu xem liệu một bộ phim X nào đó có gây hứng thú cho một người dùng A nào đó (User A) hay không?

Quá trình tìm hiểu và đánh giá này bao gồm các bước:

[1] Chọn đối tượng đánh giá là người dùng cho phim (A chưa xem phim X).

[2] Tìm một nhóm {N} bao gồm những người đã xem phim đồng thời trước kia đã từng cùng với A chấm điểm các bộ phim khác với điểm số tương tự nhau. Ví dụ, trước đây nhóm {N} và A đều đã xem “Kong: Skull Island” và đều chấm bộ phim này 5 điểm (thang điểm xếp hạng phim là từ 1 đến 5). Đồng thời, trước đây những người trong nhóm {N} và người dùng A đều đã xem phim “The Mummy” và tất cả bọn họ đều chấm phim này 1 điểm → đó là lý do tại sao nhóm {N} được xem là “tương tự” với người dùng A.

[3] Ước lượng điểm số mà người dùng A sẽ chấm cho phim X dựa trên điểm số mà nhóm {N} đã chấm cho phim X.

→ Yếu tố quan trọng nhất quyết định thành công của thuật toán là làm sao chúng ta có thể tìm ra nhóm {N} này. Để có thể làm được điều đó, chúng ta cần tìm ra “độ tương tự” (similarity) giữa những người dùng với nhau.

Ví dụ về Collaborative Filtering

Chúng ta có một data table như bên dưới.

 ABCD
HP145  
HP2 5 3
HP3 4  
TW5 2 
SW11 4 
SW2  5 
SW3   3

Chúng ta có 4 user là A, B, CD. Chúng ta có 7 bộ phim là HP1 (Harry Porter 1), HP2 (Harry Porter 2), HP3 (Harry Porter 3), TW (Twilight), SW1 (Star Wars 1), SW2 (Star Wars 2) và SW3 (Star Wars 3).

User A chấm phim HP1 4 điểm, TW 5 điểm và SW1 1 điểm. User B chấm phim HP1 5 điểm, HP2 5 điểm và HP3 4 điểm. User C chấm phim TW 2 điểm, phim SW1 4 điểm và phim SW2 5 điểm. Những ô bỏ trống là những phim mà người dùng chưa chấm (vì họ chưa xem bộ phim đó).

Điểm chấm phim là từ 1 điểm đến 5 điểm tăng theo mức độ từ thấp đến cao. Nghĩa là, 1 điểm là mức điểm chấm thấp nhất và 5 điểm là mức điểm chấm cao nhất.

Với mỗi user chúng ta xác định vector chấm phim của user đó. Với user A, vector chấm phim là rA. Với user B, vector chấm phim là rB. Chúng ta cần tính được giá trị của độ tương tự sim(A, B).

Nếu đánh giá một cách trực quan thì một phần nào đó chúng ta có thể nói được là “độ tương tự” giữa A và B lớn hơn “độ tương tự” giữa A và C – hay sim(A,B) > sim(A,C). Mặc dù A và B chỉ chấm điểm chung một phim (HP1) nhưng điểm số họ chấm là khá tương tự nhau (4 vs 5). Trong khi đó, A và C cùng chấm chung hai phim (TW và SW1) nhưng số điểm họ cho lại trái ngược nhau (5 vs 2 và 1 vs 4). Vấn đề là làm sao chúng ta có thể quy đổi thành giá trị số cho “độ tương tự” này. Bài viết này sẽ đi qua 3 phương pháp khác nhau để đánh giá độ tương tự.

Option 1: Jaccard Similarity

Công thức tính độ tương tự theo phương pháp Jaccard là:

sim(A,B) = \frac{r_{A}\bigcap r_{B}}{r_{A}\bigcup r_{B}}

User A và user B đều cho điểm phim HP1 nên rA ∩ rB = 1. User A và user B cho điểm tổng cộng 5 phim nên rA U rB = 5. Do đó, sim(A,B) = 1/5.

Tương tự, sim(A,C) = 2/4. Kết quả là : sim(A,B) < sim(A,C) → Kết quả này ngược với điều chúng ta mong muốn bởi mặc dù A và B chỉ chấm điểm chung cho một phim nhưng số điểm họ cho là tương tự nhau. Ngược lại, A và C chấm điểm chung cho hai phim nhưng số điểm cho mỗi phim của mỗi người lại ngược nhau.

Hạn chế : Phương pháp Jaccard không đề cập đến số điểm chấm, do đó kết quả tính được không chính xác.

Option 2: Cosine Similarity

Công thức tính Cosine Similarity giữa user A và user B được thể hiện như bên dưới.

sim(A,B) = cos(r_{A},r_{B})

cos(r_{A},r_{B}) = \frac{\sum_{i=1}^{n}(r_{Ai}\times r_{Bi})}{\sqrt{\sum_{i=1}^{n}r_{Ai}^{2}}\times\sqrt{\sum_{i=1}^{n}r_{Bi}^{2}}}

Ở phương pháp này, chúng ta gán giá trị 0 cho những bộ phim mà người dùng chưa cho điểm. Từ đó, ta có vector chấm phim của user A là rA = (4, 0, 0, 5, 1, 0, 0), vector chấm phim của user B là rB = (5, 5, 4, 0, 0, 0, 0) và vector chấm phim của user C là rC = (0, 0, 0, 2, 4, 5, 0).

Chúng ta tính được giá trị cosine cho vector rA và vector rB như bên dưới.

\large cos(r_{A},r_{B})=\frac{4\times 5}{\sqrt{4^{2}+5^{2}+1^{2}}\times \sqrt{5^{2}+5^{2}+4^{2}}}=0.379

Tương tự, ta có giá trị cos(rA, rC) = 0.322.

Như vậy, tính toán độ tương tự bằng phương pháp Cosine Similarity cho ta kết quả sim(A, B) > sim(A, C) nhưng kết quả không quá chênh lệch (0.379 vs 0.322).

Hạn chế: Nhược điểm của phương pháp Cosine Similarity chính là việc gán điểm 0 cho những giá trị còn thiếu. Điều này không đúng – chúng ta hãy xem xét user A. User A chấm điểm 5 cho phim HP1 và do đó sẽ có xác suất rất lớn rằng người dùng A cũng sẽ chấm điểm cao cho các phim HP2 và HP3. Nhưng với phương pháp Cosine Similarity, những giá trị còn thiếu đều bằng 0 là mức điểm số không tồn tại trong khung điểm và điều này đi ngược lại với suy luận của chúng ta.

Option 3: Centered cosine

Nhược điểm của phương pháp Cosine Similarity thông thường có thể được khắc phục bằng cách “chuẩn hóa” điểm chấm của từng user cho mỗi phim họ chấm. Điểm chấm “chuẩn hóa” của một user cho một phim bằng số điểm mà user đó chấm cho bộ phim trừ đi điểm chấm trung bình của tất cả các phim mà user đó đã chấm.

Điểm chấm trung bình của user A được tính như hình bên dưới.

\large m_{a}=\frac{4+0+0+5+1+0+0}{7}=3.333

Tương tự ta có điểm chấm trung bình của user B là mb = 4.667 và điểm chấm trung bình của user C là mc = 3.667.

Điểm chấm sau khi được chuẩn hóa của các user như sau.

 ABCD
HP10.6666670.33333300
HP200.33333300
HP30-0.6666700
TW1.6666670-1.666670
SW1-2.3333300.3333330
SW2001.3333330
SW30000

Chúng ta có thể thấy rằng với việc chuẩn hóa điểm chấm, giá trị 0 bây giờ được xem là giá trị điểm chấm trung bình, điểm số âm là điểm chấm dưới trung bình (nghĩa là người dùng xếp hạng thấp – tiêu cực cho phim) và điểm số dương là điểm số trên trung bình (nghĩa là người dùng chấm phim điểm cao – tích cực).

Tính toán giá trị cosine similarity với điểm chấm được chuẩn hóa, ta có cos(rA, rB) = 0.09cos(rA, rC) = -0.56. Do đó ta có thể kết luận rằng sim(A, B) > sim(A, C) và sự khác nhau này trực quan hơn rất nhiều so với phương pháp Cosine Similarity ở option 2. Phương pháp Centered Cosine đã khắc phục được nhược điểm của phương pháp Cosine Similarity thông thường với kết quả tính toán thể hiện được sự khác nhau về “tính tương tự” rõ ràng hơn giữa các đối tượng. Đồng thời, phương pháp này cũng xem các giá trị còn thiếu như là “giá trị trung bình” – điều này mang tính trung dung hơn rất nhiều so với phương pháp Cosine Similarity thông thường. Hơn thế nữa, phương pháp này cũng xử lý được vấn đề điểm chấm bị thiên lệch gây ra bởi “những người chấm điểm khó” và “những người chấm điểm dễ” bằng cách chuẩn hóa điểm chấm của họ. “Những người chấm điểm khó” là những người mà range điểm của họ thấp hơn thông thường. Ví dụ, một người dùng bình thường sẽ chấm một bộ phim hay 5 điểm nhưng “một người chấm điểm khó” sẽ chỉ cho bộ phim đó 3 điểm. Tương tự, một người dùng bình thường sẽ chấm một bộ phim dở 1 điểm nhưng “một người chấm điểm dễ” sẽ chấm bộ phim đó 3 điểm. Bằng cách chuẩn hóa điểm chấm của người dùng, điểm chấm trung bình cho mọi người đều sẽ là 0 điểm và sự ảnh hưởng do “những người chấm điểm khó và dễ” sẽ bị loại trừ.

Phương pháp Centered Cosine còn được gọi là phương pháp tương quan Pearson (Pearson Correlation) trong khoa học thống kê.

Dự đoán điểm chấm của người dùng cho một bộ phim

Chúng ta quay trở lại với vấn đề làm thế nào để dự đoán điểm chấm của một người dùng  (hay khách hàng) cho một bộ phim

1/ Gọi \large r_{A} là vector chấm phim của người dùng A.

2/ Gọi {N} là nhóm gồm có số lượng k người dùng và tương tự với người dùng A nhất và những người trong nhóm {N} này đã chấm phim X.

3/ Chúng ta cần dự đoán điểm của người dùng chấm cho phim X. Chúng ta có thể sử dụng hai công thức dưới đây để tính toán điểm chấm dự đoán này.

Cách 1:

\large r_{AX}= \frac{\sum_{y=1}^{k}r_{yX}}{k}

Ở cách một, điểm chấm của người dùng A cho bộ phim X sẽ bằng trung bình cộng điểm chấm của tất cả người dùng trong nhóm {N} cho bộ phim X. Nhược điểm của cách tính này là mặc dù nhóm {N} bao gồm những người dùng tương tự với người dùng nhưng “độ tương tự” của từng người trong nhóm {N} với người dùng thì khác nhau.

Cách 2:

\large r_{AX}=\frac{\sum_{y=1}^{k}s_{Ay}\times r_{yX}}{\sum_{y=1}^{k}s_{Ay}}

Cách 2 khắc phục nhược điểm của cách thứ nhất bằng cách thêm trọng số là “độ tương tự” \large s_{Ay} của người dùng A và người dùng y trong nhóm {N}. Việc thêm trọng số sẽ giúp cho kết quả tính được chính xác hơn.

Chia sẻ bài viết

Leave a Comment

Your email address will not be published. Required fields are marked *