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 $A$ (kích thước $m \times n$) thì sẽ được phân tách thành:

$$A = U \Sigma V^T$$

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

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

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

• Các cột của $U$ và $V$ đề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ó: $U^T=U^{-1}$, tức là $UU^T=U^TU=I$ và $V^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 $U$ và $V$ để giảm kích thước và tối ưu lưu trữ.

Công thức:

$$M = U_r \Sigma_r V_r^T$$

• $\Sigma_r$: Ma trận đường chéo kích thước $r \times r$ ($r$ là rank của ma trận $M$).
• $U_r$: Kích thước $m \times r$.
• $V_r^T$: Kích thước $r \times n$.

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

• Trong Full SVD: $U$ và $V$ là ma trận trực chuẩn, tức là $U^T=U^{-1}$, $UU^T=U^TU=I$, $V^TV=VV^T=I$.
• Trong Reduced SVD: $U_r$ và $V_r$ không vuông nên chỉ thỏa mãn $U_r^TU_r=I, V_r^TV_r=I$.
• Tuy nhiên $U_rU_r^T \ne I$ và $V_rV_r^T \ne I$.
• Như vậy, $U_r$ và $V_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 $U$.

Độ tương đồng giữa hai người dùng $a$ và $b$:

$$Sim(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}}$$

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

• $r_{bp}$: Điểm đánh giá của người dùng $b$ cho sản phẩm $p$

• $\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 $a$

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

• $p$: Một sản phẩm mà cả $a$ và $b$ đều đã đánh giá

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

  • Gần $1$: $a$ và $b$ đánh giá giống nhau
  • Gần $-1$: $a$ và $b$ đánh giá ngược nhau
  • $0$: 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 $u$ với sản phẩm $p$:

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

• $r_{up}$: Dự đoán điểm của $u$ cho $p$
• $\overline{r_u}$: Trung bình điểm của $u$
• $sim(u, i)$: Độ tương đồng giữa $u$ và $i$
• $r_{ip}$: Điểm thực tế của $i$ cho $p$

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 $R_{m \times n}$ thành:

$$R \approx U_r \Sigma_r V_r^T$$

• $U_r$ ($m \times k$): vector biểu diễn user
• $\Sigma_r$ ($k \times k$): chứa giá trị kỳ dị
• $V_r^T$ ($k \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 $k$ thành phần quan trọng.

Dự đoán cho user mới $r$ ($1 \times n$):

Tính vector biểu diễn:

$$U_{new} = r \Sigma_r^{-1} V_r$$

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

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

• $\cos{\alpha} \to 1$: rất giống nhau
• $\cos{\alpha} \to -1$: ngược nhau
• $\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

Ta có:

$$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ụ:

• $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}$
• $\Sigma_r = \begin{bmatrix} 10.03 & 0 \\ 0 & 7.19 \end{bmatrix}$
• $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]$$

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ử $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.97$, rất gần $1$.
=> 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ị $k$ cho Compact SVD

Việc chọn $k$ 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 $k$ sao cho tổng phương sai tích lũy đạt ngưỡng (thường 90% hoặc 95%).

Công thức:

$$\text{Cumulative Explained Variance Ratio}_k = \frac{\sum_{i=1}^k \sigma_i^2}{\sum_{i=1}^\tau \sigma_i^2}$$

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

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

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

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

$$D_k = \sigma_k - \sigma_{k+1}$$

Chọn:

$$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)$: $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=10$.
• Nếu số đặc trưng lớn $(>50)$: $k^* = 0.2 \cdot m$
• Trong thực tế, $k$ thường trong khoảng $10-100$.
• Nếu số user lớn $(>1000)$, chọn $k \approx 50-100$.