0

SVD cho hệ thống Recomendation System

1. Khái niệm

SVD (Singular Value Decomposition) là kỹ thuật phân tách một ma trận thành tích của các ma trận nhỏ hơn.

1.1 Full SVD

Giả sử ta có ma trận AA (kích thước m×nm \times n) thì sẽ được phân tách thành:

A=UΣVTA = U \Sigma V^T

  • UU: Ma trận trực chuẩn chứa các vector kỳ dị bên trái (kích thước m×mm \times m).

  • Σ\Sigma: Ma trận đường chéo chứa các giá trị kỳ dị (kích thước m×nm \times n).

  • VV: Ma trận trực chuẩn chứa các vector kỳ dị bên phải (kích thước n×nn \times n).

  • Các cột của UUVV đều trực giao với nhau và là vector đơn vị.

  • Hai vector trực giao với nhau nếu tích chấm của chúng bằng 0. Một vector là vector đơn vị nếu độ dài bằng 1.

  • Chuyển vị của ma trận trực chuẩn là nghịch đảo của nó: UT=U1U^T=U^{-1}, tức là UUT=UTU=IUU^T=U^TU=IVTV=VVT=IV^TV=VV^T=I.

1.2 Reduced SVD / Compact SVD

  • Đây là dạng phân rã kỳ dị rút gọn, chỉ giữ lại các giá trị kỳ dị khác 0 và bỏ các cột dư thừa của UUVV để giảm kích thước và tối ưu lưu trữ.

Công thức:

M=UrΣrVrTM = U_r \Sigma_r V_r^T

  • Σr\Sigma_r: Ma trận đường chéo kích thước r×rr \times r (rr là rank của ma trận MM).
  • UrU_r: Kích thước m×rm \times r.
  • VrTV_r^T: Kích thước r×nr \times n.

1.3 Semi-Orthonormal Matrices (Ma trận bán trực chuẩn)

  • Trong Full SVD: UUVV là ma trận trực chuẩn, tức là UT=U1U^T=U^{-1}, UUT=UTU=IUU^T=U^TU=I, VTV=VVT=IV^TV=VV^T=I.
  • Trong Reduced SVD: UrU_rVrV_r không vuông nên chỉ thỏa mãn UrTUr=I,VrTVr=IU_r^TU_r=I, V_r^TV_r=I.
  • Tuy nhiên UrUrTIU_rU_r^T \ne IVrVrTIV_rV_r^T \ne I.
  • Như vậy, UrU_rVrV_r được gọi là Semi-Orthonormal Matrices (ma trận bán trực chuẩn).

2. Khái niệm User-Based Collaborative Filtering

Là kỹ thuật dự đoán sản phẩm mà người dùng có thể thích dựa vào điểm số do những người dùng khác có cùng sở thích đánh giá.

Bước 1: Tính độ tương đồng giữa các người dùng với người dùng mục tiêu UU.

Độ tương đồng giữa hai người dùng aabb:

Sim(a,b)=p(rapra)(rbprb)(rapra)2(rbprb)2Sim(a, b) = \frac{\sum_p (r_{ap} - \overline{r_a})(r_{bp} - \overline{r_b})} {\sqrt{\sum (r_{ap} - \overline{r_a})^2} \cdot \sqrt{\sum (r_{bp} - \overline{r_b})^2}}

  • rapr_{ap}: Điểm đánh giá của người dùng aa cho sản phẩm pp

  • rbpr_{bp}: Điểm đánh giá của người dùng bb cho sản phẩm pp

  • ra=1PapParap\overline{r_a} = \frac{1}{|P_a|} \sum_{p \in P_a} r_{ap}: Điểm đánh giá trung bình của người dùng aa

  • PaP_a: Tập các mục mà người dùng aa đã đánh giá

  • pp: Một sản phẩm mà cả aabb đều đã đánh giá

  • Giá trị Sim(a,b)[1,1]Sim(a, b) \in [-1, 1]

    • Gần 11: aabb đánh giá giống nhau
    • Gần 1-1: aabb đánh giá ngược nhau
    • 00: Không có mối liên hệ

Bước 2: Xếp hạng các mặt hàng dựa trên tương đồng

Điểm dự đoán cho người dùng uu với sản phẩm pp:

rup=ru+iuserssim(u,i)ripiuserssim(u,i)r_{up} = \overline{r_u} + \frac{\sum_{i \in users} sim(u, i) r_{ip}}{\sum_{i \in users} |sim(u, i)|}

  • rupr_{up}: Dự đoán điểm của uu cho pp
  • ru\overline{r_u}: Trung bình điểm của uu
  • sim(u,i)sim(u, i): Độ tương đồng giữa uuii
  • ripr_{ip}: Điểm thực tế của ii cho pp

Tuy nhiên, trong SVD Recommendation System, ta tập trung vào mối quan hệ tương thích giữa các user để gợi ý.


3. Ứng dụng SVD cho hệ thống gợi ý sản phẩm cho người dùng (User-Based)

Ý tưởng:
Sử dụng Compact SVD để phân rã ma trận Rm×nR_{m \times n} thành:

RUrΣrVrTR \approx U_r \Sigma_r V_r^T

  • UrU_r (m×km \times k): vector biểu diễn user
  • Σr\Sigma_r (k×kk \times k): chứa giá trị kỳ dị
  • VrTV_r^T (k×nk \times n): vector biểu diễn sản phẩm

Lý do dùng Compact SVD:
Giảm chiều dữ liệu, chỉ giữ lại kk thành phần quan trọng.

Dự đoán cho user mới rr (1×n1 \times n):

Tính vector biểu diễn:

Unew=rΣr1VrU_{new} = r \Sigma_r^{-1} V_r

Sau đó tính cosine similarity giữa UnewU_{new} và từng dòng UrU_r:

cosα=UnewUiUnewUi\cos{\alpha} = \frac{U_{new} \cdot U_i}{|U_{new}| \cdot |U_i|}

  • cosα1\cos{\alpha} \to 1: rất giống nhau
  • cosα1\cos{\alpha} \to -1: ngược nhau
  • cosα=0\cos{\alpha} = 0: không liên quan

Chọn user tương đồng nhất để đề xuất sản phẩm mà họ đánh giá cao.


Ví dụ: Ma trận người dùng x sản phẩm

Sản phẩm A Sản phẩm B Sản phẩm C Sản phẩm D
User1 5 4 0 1
User2 4 0 0 1
User3 1 1 0 5
User4 0 0 5 4
User5 0 1 5 4

Ta có:

A=[54014001110500540154]A = \begin{bmatrix} 5 & 4 & 0 & 1 \\ 4 & 0 & 0 & 1 \\ 1 & 1 & 0 & 5 \\ 0 & 0 & 5 & 4 \\ 0 & 1 & 5 & 4 \end{bmatrix}

Code ví dụ SVD cho user-based recommendation:

import numpy as np
# Tạo ma trận người dùng x sản phẩm
A = np.array([
    [5, 4, 0, 1],
    [4, 0, 0, 1],
    [1, 1, 0, 5],
    [0, 0, 5, 4],
    [0, 1, 5, 4]
])

# Thực hiện SVD đầy đủ
U, S, Vt = np.linalg.svd(A, full_matrices=False)

# Chọn k = 2 (rút gọn SVD)
k = 2
U_r = U[:, :k]  # Lấy 2 cột đầu của U
S_r = np.diag(S[:k])  # Chuyển S thành ma trận đường chéo (2x2)
V_r_T = Vt[:k, :]  # Lấy 2 hàng đầu của V^T

print("Ma trận U_r (Người dùng):\n", np.round(U_r, 2))
print("\nMa trận Σ_r (Giá trị kỳ dị):\n", np.round(S_r, 2))
print("\nMa trận V_r^T (Sản phẩm):\n", np.round(V_r_T, 2))

Kết quả ví dụ:

  • Ur=[0.280.790.170.440.410.120.590.320.610.26]U_r = \begin{bmatrix} -0.28 & -0.79 \\ -0.17 & -0.44 \\ -0.41 & -0.12 \\ -0.59 & 0.32 \\ -0.61 & 0.26 \end{bmatrix}
  • Σr=[10.03007.19]\Sigma_r = \begin{bmatrix} 10.03 & 0 \\ 0 & 7.19 \end{bmatrix}
  • VrT=[0.250.220.60.730.810.420.410.07]V_r^T = \begin{bmatrix} -0.25 & -0.22 & -0.6 & -0.73 \\ -0.81 & -0.42 & 0.41 & 0.07 \end{bmatrix}

Dự đoán cho người dùng mới có đánh giá:

r=[5,0,3,4]r = [5, 0, 3, 4]

Tính vector biểu diễn:

r = np.array([[5, 0, 3, 4]])
S_r_inv = np.linalg.inv(S_r)
U_new = r @ V_r_T.T @ S_r_inv
print("\nMa trận U mới (Người dùng):\n", np.round(U_new, 2))

Giả sử Unew=[0.6,0.36]U_{new} = [-0.6, -0.36]

Tính Cosine Similarity với từng user có sẵn:

cosine_similarities = []
for i, U_i in enumerate(U_r):
    cos_alpha = np.dot(U_new, U_i).item() / (np.linalg.norm(U_new) * np.linalg.norm(U_i))
    cosine_similarities.append((i + 1, round(cos_alpha, 2)))
print("\nCosine Similarity với người dùng khác:")
for user, cos_sim in cosine_similarities:
    print(f"Người dùng {user}: {cos_sim}")

Kết quả:
Cos similarity của người dùng mới và người dùng 3 là 0.970.97, rất gần 11.
=> Người dùng mới rất giống user 3, nên có thể đề xuất sản phẩm D (vì user 3 đánh giá D rất cao).


4. Các phương pháp chọn giá trị kk cho Compact SVD

Việc chọn kk tối ưu rất quan trọng vì ảnh hưởng khả năng lưu giữ thông tin gốc sau khi giảm chiều.

4.1 Phương pháp tích lũy (Explained Variance)

  • Giữ lại càng nhiều phương sai của dữ liệu gốc càng tốt.
  • Chọn kk sao cho tổng phương sai tích lũy đạt ngưỡng (thường 90% hoặc 95%).

Công thức:

Cumulative Explained Variance Ratiok=i=1kσi2i=1τσi2\text{Cumulative Explained Variance Ratio}_k = \frac{\sum_{i=1}^k \sigma_i^2}{\sum_{i=1}^\tau \sigma_i^2}

  • σi2\sigma_i^2: Bình phương giá trị kỳ dị thứ ii.
  • τ\tau: Tổng số thành phần kỳ dị.
  • Chọn kk sao cho 0.90Cumulative Explained Variance Ratiok0.950.90 \leq \text{Cumulative Explained Variance Ratio}_k \leq 0.95.

4.2 Phương pháp khuỷu tay (Elbow Method)

  • Chọn kk tại điểm giá trị kỳ dị σi\sigma_i bắt đầu giảm chậm lại.

Độ suy giảm giá trị kỳ dị:

Dk=σkσk+1D_k = \sigma_k - \sigma_{k+1}

Chọn:

k=argmaxk(DkDk+1)k^* = \arg\max_k (D_k - D_{k+1})

  • Khi vẽ biểu đồ, điểm này là "khuỷu tay".

4.3 Phương pháp dựa trên kinh nghiệm (Heuristic)

  • Nếu số đặc trưng nhỏ (<50)(<50): k=min(10,m)k^* = \min(10, m)
  • Nếu số chiều nhỏ hơn 10, giữ nguyên số chiều.
  • Nếu lớn hơn 10, chọn k=10k=10.
  • Nếu số đặc trưng lớn (>50)(>50): k=0.2mk^* = 0.2 \cdot m
  • Trong thực tế, kk thường trong khoảng 1010010-100.
  • Nếu số user lớn (>1000)(>1000), chọn k50100k \approx 50-100.
Phương pháp Cách tiếp cận Ưu điểm Nhược điểm
Explained Variance Chọn kk sao cho tổng phương sai >90% Giữ tối đa thông tin Có thể không có kk rõ ràng
Elbow Method Tìm "khuỷu tay" trên đồ thị kỳ dị Trực quan, dễ áp dụng Không phải lúc nào cũng rõ ràng
Heuristic Quy tắc 10-100 hoặc 20% Dễ, nhanh, dễ áp dụng Không tối ưu từng bộ dữ liệu


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí