Apr 22, 2026

miniyuan

特征值和特征向量的计算

---

题 4.1

使用位移反幂法。

取初始向量 $\mathbf x^{(0)}=(1,1,1)^{\!T}$，位移量 $\mu=9.6$。

令

$$A = \begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 4\\ 3 & 4 & 5 \end{bmatrix}$$ $$B=A-\mu I = \begin{bmatrix} -8.6 & 2 & 3\\ 2 & -6.6 & 4\\ 3 & 4 & -4.6 \end{bmatrix}$$

迭代一次 $\mathbf y^{(1)} = B^{-1} \mathbf x^{(0)}$，也即方程组

$$\begin{cases} -8.6\,y_1+2\,y_2+3\,y_3=1\\[4pt] 2\,y_1-6.6\,y_2+4\,y_3=1\\[4pt] 3\,y_1+4\,y_2-4.6\,y_3=1 \end{cases}$$

解得：

$$\mathbf y^{(1)}= \begin{bmatrix} \dfrac{55}{2}\\[8pt] 40\\[4pt] \dfrac{105}{2} \end{bmatrix}$$

因为 $\lambda \approx \mu + 1/y_j,\quad j = \argmax_i |y_i|$，所以特征值的估计为：

$$\lambda\approx \mu+\frac{1}{y_j} = 9.6 + \frac{2}{105}=\frac{202}{21}\approx 9.6190$$

对应单位特征向量的估计为：

$$\mathbf x^{(1)}=\frac{\mathbf y^{(1)}}{\|\mathbf y^{(1)}\|_\infty} = \begin{bmatrix} \dfrac{11}{21}\\[8pt] \dfrac{16}{21}\\[8pt] 1 \end{bmatrix} \approx \begin{bmatrix} 0.5238\\0.7619\\1.0000 \end{bmatrix}.$$

题 4.2

$$A^{(0)}= \begin{bmatrix} 4 & 2 & 2\\ 2 & 5 & 1\\ 2 & 1 & 6 \end{bmatrix}$$

取最大非对角元 $a_{21}^{(0)} = 2$，则：

$$\begin{aligned} \cot \theta^{(1)} &:= \tau^{(1)} = \frac{4-5}{2 \times 2} = -\frac{1}{4} \\ \tan \theta^{(1)} &:= t^{(1)} = -\frac{\text{sign}(\tau^{(1)})}{|\tau^{(1)}| + \sqrt{1+(\tau^{(1)})^2}} \approx 0.7808 \\ \cos \theta^{(1)} &:= c^{(1)} = \frac{1}{\sqrt{1 + (t^{(1)})^2}} \approx 0.7882 \\ \sin \theta^{(1)} &:= s^{(1)} = c^{(1)} t^{(1)} \approx 0.6154 \end{aligned}$$

从而旋转矩阵为：

$$J^{(1)}= \begin{bmatrix} c^{(1)} & -s^{(1)} & 0\\ s^{(1)} & c^{(1)} & 0\\ 0 & 0 & 1 \end{bmatrix} \approx \begin{bmatrix} 0.7882 & 0.6154 & 0\\ -0.6154 & 0.7882 & 0\\ 0 & 0 & 1 \end{bmatrix}.$$

一次 Jordan 变换后：

$$A^{(1)}=(J^{(1)})^\top A^{(0)}J^{(1)} \approx \begin{bmatrix} 2.4384 & 0 & 0.9610\\ 0 & 6.5616 & 2.0190\\ 0.9610 & 2.0190 & 6 \end{bmatrix}$$

取最大非对角元 $a_{32}^{(1)} \approx 2.0190$，则：

$$\begin{aligned} \cot \theta^{(2)} &:= \tau^{(2)} \approx 0.1391\\ \tan \theta^{(2)} &:= t^{(2)} = -\frac{\text{sign}(\tau^{(2)})}{|\tau^{(2)}| + \sqrt{1+(\tau^{(2)})^2}} \approx -0.8706 \\ \cos \theta^{(2)} &:= c^{(2)} = \frac{1}{\sqrt{1 + (t^{(2)})^2}} \approx 0.7542 \\ \sin \theta^{(2)} &:= s^{(2)} = c^{(2)} t^{(2)} \approx -0.6566 \end{aligned}$$

从而旋转矩阵为：

$$J^{(2)}= \begin{bmatrix} 1 & 0 & 0 0 & c^{(2)} & -s^{(2)}\\ 0 & s^{(2)} & c^{(2)}\\ \end{bmatrix} \approx \begin{bmatrix} 1 & 0 & 0\\ 0 & 0.7542 & 0.6566\\ 0 & -0.6566 & 0.7542 \end{bmatrix}.$$

两次 Jordan 变换后：

$$A^{(2)}=(J^{(2)})^\top A^{(1)}J^{(2)} \approx \begin{bmatrix} 2.4384 & 0.6310 & 0.7248\\ 0 & 8.3192 & 0\\ 0.7248 & 0 & 4.2423 \end{bmatrix}$$

特征值近似为：

$$\lambda_1 \approx 8.3192,\quad \lambda_2 \approx 4.2423,\quad \lambda_3 \approx 2.4384$$

使用了如下 python 代码帮助计算：

import numpy as np

np.set_printoptions(precision=4, suppress=True)

A = np.array([[4, 2, 2],
              [2, 5, 1],
              [2, 1, 6],], dtype=float)

k = 0
n = A.shape[0]
V = np.eye(n)
N = 1000
EPS = 1e-6

while k < N:
    k += 1
    print(f"===iteration {k} start===")

    # 选最大非对角元
    p, q = 0, 1
    max_off = 0
    for i in range(n):
        for j in range(i + 1, n):
            if abs(A[i, j]) > max_off:
                max_off = abs(A[i, j])
                p, q = i, j
    print(f"A^({k-1})[{p}, {q}] = {A[p, q]:.4f}")

    if max_off < EPS:
        print("")
        print("===all iteration done===")
        break

    # 计算旋转参数
    tau = (A[p, p] - A[q, q]) / (2 * A[p, q])
    if tau >= 0:
        t = -1 / (tau + np.sqrt(1 + tau**2))
    else:
        t = 1 / (-tau + np.sqrt(1 + tau**2))
    c = 1 / np.sqrt(1 + t**2)
    s = c * t
    print(f"cot2^({k}) = {tau:.4f}")
    print(f"tan^({k}) = {t:.4f}")
    print(f"cos^({k}) = {c:.4f}")
    print(f"sin^({k}) = {s:.4f}")

    # 更新 A
    a_pp, a_qq, a_pq = A[p, p], A[q, q], A[p, q]
    A[p, p] = c**2 * a_pp + s**2 * a_qq - 2*s*c*a_pq
    A[q, q] = s**2 * a_pp + c**2 * a_qq + 2*s*c*a_pq
    A[p, q] = A[q, p] = 0

    for i in range(n):
        if i != p and i != q:
            a_ip, a_iq = A[i, p], A[i, q]
            A[i, p] = A[p, i] = c*a_ip - s*a_iq
            A[i, q] = A[q, i] = s*a_ip + c*a_iq
    print(f"A^({k}) = {A}")

    # 累积 V
    for i in range(n):
        v_ip, v_iq = V[i, p], V[i, q]
        V[i, p] = c*v_ip - s*v_iq
        V[i, q] = s*v_ip + c*v_iq
    print(f"V^({k}) = {V}")
    print("")

eigvals = np.diag(A)
idx = np.argsort(eigvals)[::-1]  # 从大到小排序
eigvals = eigvals[idx]
eigvecs = V[:, idx]

print(f"eigvals:")
for i in range(n):
    print(f"  lambda_{i} = {eigvals[i]:.4f}")

题 4.3

令：

$$A^{(0)} = \begin{bmatrix} -4 & -3 & -7 \\ 2 & 3 & 2 \\ 4 & 2 & 7 \end{bmatrix}, \quad Q^{(0)} = I_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

第一次迭代：

$$\mathbf{x}^{(0)} = A^{(0)}[0:3, 0] = \begin{bmatrix} -4 \\ 2 \\ 4 \end{bmatrix}, \quad \|\mathbf{x}^{(0)}\|_2 = 6$$ $$\mathbf{y}^{(0)} = \begin{bmatrix} -\mathrm{sign}(\mathbf{x}_1^{(0)}) \cdot \|\mathbf{x}^{(0)}\|_2 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix}$$ $$\mathbf{v}^{(0)} = \mathbf{x}^{(0)} - \mathbf{y}^{(0)} = \begin{bmatrix} -10 \\ 2 \\ 4 \end{bmatrix}, \quad \|\mathbf{v}^{(0)}\|_2 = 2\sqrt{30}$$ $$\mathbf{w}^{(0)} = \frac{\mathbf{v}^{(0)}}{\|\mathbf{v}^{(0)}\|_2} = \begin{bmatrix} -\frac{5}{\sqrt{30}} \\ \frac{1}{\sqrt{30}} \\ \frac{2}{\sqrt{30}} \end{bmatrix} \approx \begin{bmatrix} -0.9129 \\ 0.1826 \\ 0.3651 \end{bmatrix}$$ $$H^{(0)} = I - 2\mathbf{w}^{(0)}(\mathbf{w}^{(0)})^T$$ $$\begin{aligned} A^{(1)}[0:3, 0:3] &= A^{(0)}[0:3, 0:3] - 2 \cdot \mathbf{w}^{(0)} \cdot \bigl((\mathbf{w}^{(0)})^T A^{(0)}[0:3, 0:3]\bigr) \\ &= \begin{bmatrix} 6 & 4.3333 & 10 \\ 0 & 1.5333 & -1.4 \\ 0 & -0.9333 & 0.2 \end{bmatrix} \end{aligned}$$ $$\begin{aligned} Q^{(1)}[:, 0:3] &= Q^{(0)}[:, 0:3] - 2 \cdot (Q^{(0)}[:, 0:3] \mathbf{w}^{(0)}) \cdot (\mathbf{w}^{(0)})^T \\ &= \begin{bmatrix} -0.6667 & 0.3333 & 0.6667 \\ 0.3333 & 0.9333 & -0.1333 \\ 0.6667 & -0.1333 & 0.7333 \end{bmatrix} \end{aligned}$$

第二次迭代：

$$\mathbf{x}^{(1)} = A^{(1)}[1:3, 1] = \begin{bmatrix} 1.5333 \\ -0.9333 \end{bmatrix}, \quad \|\mathbf{x}^{(1)}\|_2 \approx 1.7951$$ $$\mathbf{y}^{(1)} = \begin{bmatrix} -\mathrm{sign}(\mathbf{x}_1^{(1)}) \cdot \|\mathbf{x}^{(1)}\|_2 \\ 0 \end{bmatrix} = \begin{bmatrix} -1.7951 \\ 0 \end{bmatrix}$$ $$\mathbf{v}^{(1)} = \mathbf{x}^{(1)} - \mathbf{y}^{(1)} = \begin{bmatrix} 3.3284 \\ -0.9333 \end{bmatrix}, \quad \|\mathbf{v}^{(1)}\|_2 \approx 3.4568$$ $$\mathbf{w}^{(1)} = \frac{\mathbf{v}^{(1)}}{\|\mathbf{v}^{(1)}\|_2} \approx \begin{bmatrix} 0.9628 \\ -0.2700 \end{bmatrix}$$ $$H^{(1)} = I - 2\mathbf{w}^{(1)}(\mathbf{w}^{(1)})^T$$ $$\begin{aligned} A^{(2)}[1:3, 1:3] &= A^{(1)}[1:3, 1:3] - 2 \cdot \mathbf{w}^{(1)} \cdot \bigl((\mathbf{w}^{(1)})^T A^{(1)}[1:3, 1:3]\bigr) \\ &= \begin{bmatrix} -1.7951 & 1.2999 \\ 0 & -0.5571 \end{bmatrix} \end{aligned}$$ $$\begin{aligned} Q^{(2)}[:, 1:3] &= Q^{(1)}[:, 1:3] - 2 \cdot (Q^{(1)}[:, 1:3] \mathbf{w}^{(1)}) \cdot (\mathbf{w}^{(1)})^T \\ &= \begin{bmatrix} 0.0619 & 0.7428 \\ -0.8666 & 0.3714 \\ 0.4952 & 0.5571 \end{bmatrix} \end{aligned}$$

最终分解：

$$Q = Q^{(2)} = \begin{bmatrix} -0.6667 & 0.0619 & 0.7428 \\ 0.3333 & -0.8666 & 0.3714 \\ 0.6667 & 0.4952 & 0.5571 \end{bmatrix}$$ $$R = A^{(2)} = \begin{bmatrix} 6 & 4.3333 & 10 \\ 0 & -1.7951 & 1.2999 \\ 0 & 0 & -0.5571 \end{bmatrix}$$

使用了如下 python 代码帮助计算：

import numpy as np

np.set_printoptions(precision=4, suppress=True)

A = np.array([[-4, -3, -7],
              [2, 3, 2],
              [4, 2, 7],], dtype=float)

n = A.shape[0]
Q = np.eye(n)

for k in range(n - 1):
    x = A[k:, k]  # (n - k,)
    norm_x = np.linalg.norm(x)

    if norm_x < 1e-15:  # 全 0
        continue

    y = np.zeros((n - k,))  # (n - k,)
    y[0] = -np.sign(x[0]) * norm_x
    w = (x - y) / np.linalg.norm(x - y)  # (n - k,)

    # H = np.eye(n) - 2 * np.outer(w, w)
    sub_A = A[k:, k:]  # (n - k, n - k)
    sub_Q = Q[:, k:]  # (n, n - k)

    sub_A -= 2 * np.outer(w, w @ sub_A)
    sub_Q -= 2 * np.outer(sub_Q @ w, w)

print("Q =")
print(f"{Q}")
print("R =")
print(f"{A}")
print("QR =")
print(f"{Q @ A}")

题 4.4

要求 1

记 $n$ 阶矩阵 $\mathbf A$ 为 $\mathbf A^{(n)}$，对应的特征多项式为 $p^{(n)}$。 归纳证明 $p^{(n)}$ 满足题示形式。

当 $n = 2$ 时，$\mathbf A^{(2)}$ 的特征多项式为：

$$p^{(2)}(\lambda) = \det(\lambda \mathbf{I} - \mathbf{A}^{(2)}) = \begin{vmatrix} \lambda + c_1 & c_2 \\ -1 & \lambda \\ \end{vmatrix} = \lambda^2 + c_1 \lambda + c_2$$

成立！

假设 $n = k-1$ 时成立，下证 $n=k$ 时也成立。

$\mathbf A^{(k)}$ 的特征多项式为：

$$p^{(k)}(\lambda) = \det(\lambda \mathbf{I} - \mathbf{A}^{(k)}) = \begin{vmatrix} \lambda + c_1 & c_2 & c_3 & \cdots & c_{k-1} & c_k \\ -1 & \lambda & 0 & \cdots & 0 & 0 \\ 0 & -1 & \lambda & \cdots & 0 & 0 \\ 0 & 0 & -1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda & 0 \\ 0 & 0 & 0 & \cdots & -1 & \lambda \\ \end{vmatrix}$$

行列式按最后一列展开得：

$$\begin{aligned} p^{(k)}(\lambda) &= \det(\lambda \mathbf{I} - \mathbf{A}^{(k)}) \\ &= \lambda \begin{vmatrix} \lambda + c_1 & c_2 & c_3 & \cdots & c_{k-2} & c_{k-1} \\ -1 & \lambda & 0 & \cdots & 0 & 0 \\ 0 & -1 & \lambda & \cdots & 0 & 0 \\ 0 & 0 & -1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda & 0 \\ 0 & 0 & 0 & \cdots & -1 & \lambda \\ \end{vmatrix} + c_k \\ &= \lambda p^{(k-1)}(\lambda) + c_k \\ &= \lambda (\lambda^{k-1} + c_1\lambda^{k-2} + \cdots + c_{k-2}\lambda + c_{k-1}) + c_k \\ &= \lambda^{k} + c_1\lambda^{k-1} + \cdots + c_{k-1}\lambda + c_k \end{aligned}$$

也成立！

要求 2

整体算法：

1. 初始化：令 $p_0(x)=p(x)$，次数为 $n$。
2. 迭代求根：对 $i=1,2,\dots,n-1$，
   • 构造 $p_{i-1}(x)$ 的伴随矩阵 $\mathbf A_{i-1}$，用幂法求 $\mathbf A_{i-1}$ 的按模最大特征值，得到 $p_{i-1}(x)$ 按模最大根 $x_i$；
   • 对 $p_{i-1}(x)$ 做综合除法，除以 $(x-x_i)$ 得到降阶后的商式 $p_i(x)$。
3. 终止：当多项式降为 1 次时，$p_{n-1}(x)=x+c$，直接得最后一个根 $x_n=-c$。

综合除法：

设当前 $m$ 次多项式为

$$p_{n-m}(x)=x^{m}+c_1x^{m-1}+c_2x^{m-2}+\cdots+c_{m}$$

设已求得近似根 $x=x_i$，做带余除法：

$$p_{n-m}(x)=(x-x_i)\,q(x)+r,$$

其中商式 $q(x)$ 为 $m-1$ 次多项式，记为

$$q(x)=x^{m-1}+d_1x^{m-2}+d_2x^{m-3}+\cdots+d_{m-1}$$

比较 $(x-r)q(x)$ 与 $p_{n-m}(x)$ 的系数，得到系数递推关系：

$$\begin{aligned} d_0 &= 1,\\ d_k &= c_k + x_i\cdot d_{k-1},\qquad k=1,2,\dots,m-1,\\ r &= c_m + x_i\cdot d_{m-1} \approx 0 \end{aligned}$$

其中 $r$ 约为 0，直接舍去即可。用这些新系数构造下一次迭代的伴随矩阵，继续求根。

题 4.5

系统总输入与总输出

总输入：

• 用户集合 $U=\{u_1,\dots,u_N\}$，共 $N$ 位匿名用户
• 原始树洞帖子集合 $P=\{p_1,\dots,p_L\}$，每个帖子 $p_l$ 包含匿名用户 ID $u(p_l)$ 与文本内容
• 食堂菜品名称库 $M=\{d_1,\dots,d_M\}$

总输出：

• 完整预测矩阵 $\hat{\mathbf{A}}\in\mathbb{R}^{N\times |M'|}$，其中 $M'\subseteq M$ 为帖子中出现过的有效菜品集合
• 每位用户的 Top-$K$ 推荐列表（从 $M'$ 中选取）

阶段一：NLP 文本量化系统

菜品筛选与用户-菜品帖子聚合

• 输入：原始树洞帖子集合 $P$；菜品名称库 $M$。
• 输出：

  • 有效菜品集合 $M'=\{d_j\in M:\exists\, p\in P,\; d_j\in p\}$，即至少被一个帖子提及的菜品子集。

  • 对每个用户 $u_i$ 和菜品 $d_j\in M'$， 聚合得到 $u_i$ 发布的所有提及 $d_j$ 的帖子文本集合 $D_{ij}=\bigcup_{\substack{p\in P\\u(p)=u_i,\,d_j\in p}} p$。

    若 $u_i$ 从未提及 $d_j\in M'$，则 $D_{ij}=\emptyset$。绝大多数 $(i,j)$ 对满足 $D_{ij}=\emptyset$，导致后续口碑矩阵极度稀疏。

实现方式：

1. 菜品筛选：遍历所有帖子，对菜品库 $M$ 中每个名称做子串匹配，统计被至少一个帖子提及的菜品，构成有效菜品集合 $M'$。对未在帖子中出现的菜品，系统无法获得任何信息，故不纳入后续预测。
2. 规则匹配：对 $M'$ 中每个 $d_j$，在帖子文本中做子串匹配。
3. 用户归属：按帖子附带的匿名用户ID，将匹配到的文本片段归入对应 $D_{ij}$。

word2vec 语义空间构建

• 输入：所有帖子文本拼接成的长词序列。
• 输出：词向量矩阵 $\mathbf{E}\in\mathbb{R}^{|V|\times d}$，词表 $V$ 中每个词 $w$ 对应稠密向量 $\mathbf{e}_w\in\mathbb{R}^d$。

算法实现：

使用 Skip-gram 进行训练。将高维稀疏的 one-hot 空间压缩到低维稠密语义空间。

对于中心词 $w_t$，定义其上下文窗口为 $C(w_t)=\{w_{t-c},\dots,w_{t-1},w_{t+1},\dots,w_{t+c}\}$，其中 $c$ 为窗口半径。

目标函数为：

$$\mathcal{L} =\sum_{t=1}^{T}\sum_{w\in C(w_t)}\log\frac{\exp(\mathbf{e}_w^{\prime\mathsf{T}}\mathbf{e}_{w_t})} {\sum_{v\in V}\exp(\mathbf{e}_v^{\prime\mathsf{T}}\mathbf{e}_{w_t})}$$

实际训练中常采用负采样或层次 Softmax 加速优化。

情感语义聚类

• 输入：词向量矩阵 $\mathbf{E}$；少量人工正面种子词 $S^+$ 与负面种子词 $S^-$。
• 输出：正面语义簇 $V^+$、负面语义簇 $V^-$；种子词向量集合 $S^+, S^-$ 作为后续相似度计算基准。

算法实现：

$$V^+ = \bigcup_{s\in S^+}\{w\in V : \cos(\mathbf{e}_w,\mathbf{e}_s)>\theta\},\quad V^- = \bigcup_{s\in S^-}\{w\in V : \cos(\mathbf{e}_w,\mathbf{e}_s)>\theta\}$$

其中 $\theta$ 为相似度阈值。

用户-菜品语义特征提取

• 输入：用户-菜品聚合文本 $D_{ij}$（$d_j\in M'$）；词向量矩阵 $\mathbf{E}$；种子词集合 $S^+, S^-$.
• 输出：二维语义特征向量 $\mathbf{x}_{ij}=(x_{ij}^+, x_{ij}^-)^\mathsf{T}$。若 $D_{ij}=\emptyset$，则特征缺失。

算法实现：

对 $D_{ij}$ 中每个词 $w$，计算其与正、负面种子词的最大余弦相似度作为情感权重，累加得到加权和特征：

$$x_{ij}^+ = \sum_{w\in D_{ij}}\max_{s\in S^+}\cos(\mathbf{e}_w,\mathbf{e}_s),\qquad x_{ij}^- = \sum_{w\in D_{ij}}\max_{s\in S^-}\cos(\mathbf{e}_w,\mathbf{e}_s)$$

用户-菜品口碑量化

• 输入：语义特征 $\mathbf{x}_{ij}=(x_{ij}^+, x_{ij}^-)^\mathsf{T}$（仅对 $D_{ij}\neq\emptyset$ 的项，且 $d_j\in M'$）。
• 输出：稀疏口碑矩阵 $\tilde{\mathbf{A}}=[\tilde{a}_{ij}]\in\mathbb{R}^{N\times |M'|}$， 其中 $\tilde{a}_{ij}\in[1,5]$ 为用户 $u_i$ 对菜品 $d_j$ 的文本推断评分；若 $D_{ij}=\emptyset$，则 $\tilde{a}_{ij}$ 缺失。

算法实现：

直接基于正面、负面情感权重的比例进行映射，并做拉普拉斯平滑避免除零：

$$\tilde{a}_{ij}=1+4\cdot\frac{x_{ij}^+ + 1}{x_{ij}^+ + x_{ij}^- + 2}$$

阶段二：SVD 个性化推荐系统

稀疏口碑矩阵的 SVD 补全

• 输入：稀疏口碑矩阵 $\tilde{\mathbf{A}}=[\tilde{a}_{ij}]$，由阶段一输出，尺寸 $N\times |M'|$。
• 输出：
  • 完整预测矩阵 $\hat{\mathbf{A}}\in\mathbb{R}^{N\times |M'|}$
  • 每位用户的 Top-$K$ 推荐列表（从 $M'$ 中选取）

算法实现：

记观测索引集 $\Omega=\{(i,j): D_{ij}\neq\emptyset\}$。首先计算全局均值、用户偏差与菜品偏差：

$$\begin{aligned} \mu &= \frac{1}{|\Omega|}\sum_{(i,j)\in\Omega}\tilde{a}_{ij} \\ \alpha_i &= \frac{1}{|M_i|}\sum_{j\in M_i}\tilde{a}_{ij} - \mu,\; M_i=\{j:(i,j)\in\Omega\} \\ \beta_j &= \frac{1}{|U_j|}\sum_{i\in U_j}\tilde{a}_{ij} - \mu,\; U_j=\{i:(i,j)\in\Omega\} \end{aligned}$$

构造去均值矩阵 $\mathbf{B}\in\mathbb{R}^{N\times |M'|}$：

• 若 $(i,j)\in\Omega$，$b_{ij}=\tilde{a}_{ij}-\mu-\alpha_i-\beta_j$。
• 否则 $b_{ij}=0$。

对 $\mathbf{B}$ 做截断 SVD：

$$\mathbf{B} \approx \mathbf{U}_k\mathbf{\Sigma}_k\mathbf{V}_k^{\mathsf{T}}.$$

最终预测公式为：

$$\hat{a}_{ij}=\mu+\alpha_i+\beta_j+\mathbf{u}_i^{\mathsf{T}}\mathbf{\Sigma}_k\mathbf{v}_j,$$

其中 $\mathbf{u}_i^{\mathsf{T}}$ 与 $\mathbf{v}_j$ 分别为 $\mathbf{U}_k$ 与 $\mathbf{V}_k$ 的第 $i$、$j$ 行。

Top-$K$ 推荐生成：

• 输入：完整预测矩阵 $\hat{\mathbf{A}}=[\hat{a}_{ij}]\in\mathbb{R}^{N\times |M'|}$；用户-菜品聚合关系 $D_{ij}$；有效菜品集合 $M'$。
• 输出：每位用户 $u_i$ 的 Top-$K$ 推荐列表 $\text{Rec}(u_i)=\{d_{j_1},\dots,d_{j_K}\}\subseteq M'$。

算法实现：

对每位用户 $u_i$，筛选其未产生过文本提及的有效菜品（即 $d_j\in M'$ 且 $D_{ij}=\emptyset$ 的项），按预测评分 $\hat{a}_{ij}$ 降序排列，取前 $K$ 个菜品构成个性化推荐列表：

$$\text{Rec}(u_i) = \mathop{\mathrm{Top}\text{-}K}_{d_j\in M',\, D_{ij}=\emptyset}\hat{a}_{ij}$$

其中 $\mathop{\mathrm{Top}\text{-}K}$ 表示取前 $K$ 个最大值的索引集合。