90分钟 · 100分 · 7道大题。原创自主练习，不是官方考试规格或权重预测。回答所有小问，写清计算与证明，尽量保留精确值；需要小数答案时说明舍入方法；特征向量及配对奇异向量一致反号可接受。以题面分母、定义域及平局规则为准，不可无条件求逆。本练习使用Casio fx-50FH II，可用一张双面A4参考纸；这是练习安排，不是新增官方考试规定。

配套题本 · Revision

评分用于自评；等价正确方法同分。单一算术错误后若方法正确，应保留相应方法分，不反复扣同一错误。请先读题本；以下说明条件与核对，不只列答案。

Q1. 加权多项式回归与唯一性 (20)

配套题本 Q1

(a) [4]

每条记录贡献截距、一次、二次三项。W对称，因此残差范数含W²；展开二次型后求导。Hessian半正定，驻点条件足以全局最优；若正定则进一步唯一。

$$\begin{gathered} M=\begin{pmatrix}1&-2&4\\1&-1&1\\1&1&1\\1&2&4\end{pmatrix},\quad W=\operatorname{diag}(1,2,2,1),\quad y=(2,1,3,4)^T. \\R(c)=(y-Mc)^TW^2(y-Mc)=y^TW^2y-2c^TM^TW^2y+c^TM^TW^2Mc. \\\nabla R(c)=-2M^TW^2y+2M^TW^2Mc=0,\qquad M^TW^2M\widehat c=M^TW^2y. \\\nabla^2R(c)=2M^TW^2M\succeq0. \end{gathered}$$

把每个对象先认清。 未知量不是四个拟合值，而是所有观测共用的三个系数：c是3维列向量，y和残差是4维列向量。M有4行、3列，每一行对应一条观测，每一列对应一个基函数；第一列全为1，所以不能忘记截距。W是4×4的对角矩阵，左乘残差表示分别缩放四条残差；因此WM是4×3，正规方程左边的系数矩阵是3×3，右边是3维列向量。

为什么出现平方权重？ 本题先把第i条残差乘以wᵢ，然后才平方，所以权重2意味着该残差平方被乘以4。展开时两个交叉项互为转置，且都是标量，故能合并成系数−2的一项。第一项不含c，求导为零；对称二次型的导数则给出两倍矩阵乘c。令梯度为零不是随意套公式，而是在求这个特定目标的驻点。

何时可以写逆矩阵？ 半正定只保证凸性，不自动保证唯一性；必须再证明正定或满列秩，才能用逆矩阵表示唯一系数。本题把这一条件留到(c)证明。只写“最小二乘所以可逆”不能代替证明。

评分： M、W共2；加权二次型1；求导方程1。

配套题本 Q1(a)

(b) [7]

横坐标及权重对称，奇数阶加权矩为零。响应决定右端；先解独立一次项，再解二元系统。代入四个输入后算加权而非普通残差平方和。正交检查是MᵀW²r，不要求未加权残差正交。

$$\begin{gathered} \sum w_i^2=10,\quad\sum w_i^2x_i=\sum w_i^2x_i^3=0,\quad\sum w_i^2x_i^2=16,\quad\sum w_i^2x_i^4=40. \\M^TW^2M=\begin{pmatrix}10&0&16\\0&16&0\\16&0&40\end{pmatrix},\quad M^TW^2y=\begin{pmatrix}22\\12\\40\end{pmatrix}. \\10c_0+16c_2=22,\quad16c_1=12,\quad16c_0+40c_2=40,\quad10(40)-16^2=144. \\c_0=\frac{22(40)-16(40)}{144}=\frac53,\quad c_1=\frac34,\quad c_2=\frac{10(40)-16(22)}{144}=\frac13. \\\widehat f(x)=\frac53+\frac34x+\frac13x^2,\quad \widehat y=(3/2,5/4,11/4,9/2)^T,\quad r=(1/2,-1/4,1/4,-1/2)^T. \\R(\widehat c)=\frac14+4\frac1{16}+4\frac1{16}+\frac14=1,\quad W^2r=(1/2,-1,1,-1/2)^T,\quad M^TW^2r=0. \end{gathered}$$

怎样从数据得到矩阵，而不是背答案？ M的三列是1、x、x²；取任意两列相乘，再乘平方权重并求和，就是Gram矩阵对应的条目。因此左上角是1+4+4+1=10，左下角是4+4+4+4=16，右下角是16+4+4+16=40。含奇数次x的条目正负抵消；这里要同时有位置与权重对称，不能只看横坐标。

右端还包含响应y，不能直接套“奇数项为零”：三个分量分别为2+4+12+4=22、−4−4+12+8=12，以及8+4+12+16=40。先用中间一行求一次项，再处理截距和二次项，是利用零条目简化运算，不是忽略其他方程。二元系统行列式144非零，故这两个系数可唯一求出。

代回和核验怎么做？ 例如在x=−2，预测是5/3−3/2+4/3=3/2，所以第一条残差是2−3/2=1/2；其余三条按同一顺序计算。四个加权误差贡献恰好各为1/4，总和为1。检查一次项的加权内积时，四项是−1、1、1、−1，相加为零；截距和二次项的内积也为零。这检查的是最优性，不意味着每条残差必须为零，也不意味着普通未加权RSS等于1。

评分： 矩阵右端2；三个系数3；残差1；加权最小值1。

配套题本 Q1(b)

(c) [5]

二次型是非负加权多项式值平方和。至少三个正权重时，若二次型为零，次数至多二的多项式在三个互异点为零，只能恒零，系数向量为零，故正定。反之，至多两个正权重使WM至多两个非零行，不可能三栏独立；非零零空间向量令Gram矩阵奇异。零权重不提供识别约束。

$$\begin{gathered} q_v(x)=v_0+v_1x+v_2x^2,\quad v^TM^TW^2Mv=\|WMv\|^2=\sum_iw_i^2q_v(x_i)^2\ge0. \\\#\{i:w_i>0\}\ge3,\ v^TM^TW^2Mv=0\Longrightarrow q_v\equiv0\Longrightarrow v=0. \\m=\#\{i:w_i>0\}\le2\Longrightarrow\operatorname{rank}(WM)\le m<3\Longrightarrow\exists v\ne0:WMv=0. \\M^TW^2Mv=0\quad\Longrightarrow\quad M^TW^2M\text{ is singular}. \end{gathered}$$

为什么要把矩阵问题变成多项式问题？ 要证明3×3的Gram矩阵可逆，直接算一般权重的行列式很繁琐。它本来就是一个矩阵转置乘自身，所以先检查二次型是否只在零向量取零最自然。向量v的三个分量可以看作另一个二次以下多项式的系数；Mv就是在全部输入点计算这个多项式的结果。

充分性中的关键一步。 平方和为零时，因为每项非负，所以每一个正权重对应的多项式值都必须为零，不能靠正负抵消。互异输入保证这是三个不同的根；“次数至多二”包括常数、一次及零多项式，只有零多项式能拥有三个不同的根。因此三个系数全零，恰好满足正定的定义。

必要性不是说方程数量看起来少。 至多两个非零行使WM的秩至多为2，但它有3列。秩—零度关系保证存在非零v满足WMv=0，从而Gram矩阵把这个非零v映到零，必然奇异。这里假设权重非负、输入互异；重复横坐标即使重复很多次，也不增加不同根的数量。若某最优解存在，沿这样的零空间方向移动系数不会改变目标，所以系数也不能唯一。

评分： 二次型1；三根充分性2；秩必要性2。

配套题本 Q1(c)

(d) [4]

每折剩n−1个互异正权重点。原有四点时每折剩三个，足够唯一。原有三点时每折只剩u,v；在一条插值多项式上加任意倍在u,v消失的二次式，两预测不变而系数不同。更少点亦秩不足。

$$\begin{gathered} n-1\ge3\Longleftrightarrow n\ge4,\qquad n_{\min}=4. \\f_t(x)=f_0(x)+t(x-u)(x-v),\quad t\in\mathbb R,\quad f_t(u)=f_0(u),\quad f_t(v)=f_0(v). \end{gathered}$$

先区分两个“样本数”。 全数据拟合有n条记录，但留一交叉验证要训练n个模型，每个模型只能使用n−1条；被留出的响应不能拿回来帮助确定系数。要求的是每一折的系数唯一，而不是最后用全数据拟合时唯一。因此上一问的“三个互异正权重点”必须应用于每个训练子集。

为什么三条总记录不够？ 两个保留输入u、v处可以先用一条直线插值，作为f₀。因为(x−u)(x−v)在这两点都等于零，加上它的任意倍数不会改变两个训练预测，也不会改变训练损失；但t不同会改变二次项及其他系数。缺少的正是第三个独立限制。于是n=4既足够又最小；若输入重复或某些权重为零，单凭总记录数4仍不能保证。

评分： 答案1；充分性1；两点非唯一论证2。

配套题本 Q1(d)

Q2. 正则化、训练评分与验证 (14)

配套题本 Q2

(a) [6]

展开求导，二阶导正给唯一解。R²评未惩罚RSS，而优化器权衡RSS与截距自身的惩罚。均值预测RSS更小，但总目标更大，所以单独最小化RSS的OLS基线证明不适用。

$$\begin{gathered} F(a)=4a^2-12a+20,\quad F'(a)=8a-12,\quad F''(a)=8>0,\quad\widehat a=3/2. \\\bar y=3,\quad\mathrm{TSS}=1+1=2,\quad\mathrm{RSS}=(2-3/2)^2+(4-3/2)^2=13/2. \\R^2=1-\frac{13/2}{2}=-9/4,\quad F(3/2)=11<20=F(3),\quad\mathrm{RSS}(3)=2. \end{gathered}$$

先写清正在优化什么。 两个观测共享常数预测a，所以未惩罚误差是(2−a)²+(4−a)²；题目额外加上2a²。展开前两项得到2a²−12a+20，再加惩罚才成为上面的4a²−12a+20。正的二阶导说明驻点是唯一全局极小点，而不是最大点或仅仅一个候选值。

为什么评分负了，优化却没错？ R²的分子只放未惩罚RSS，不把2a²一起放进去。预测都为3/2时，两条误差平方分别是1/4与25/4，所以RSS为13/2。TSS始终围绕观测均值3计算，不能围绕3/2计算。RSS比TSS大，R²自然小于零，意思是在这批数据上，单看预测误差还不如全部预测均值。

但是优化器比较的是另一个量：在3/2处惩罚为9/2，总目标11；在3处惩罚为18，总目标20。缩小截距带来的惩罚下降超过误差增加，所以选择3/2完全符合目标。不要由“在训练集上评分”就断言R²非负；还须检查截距是否受到惩罚。

评分： 最优及极小性2；RSS1；TSS1；R²1；目标区别1。

配套题本 Q2(a)

(b) [4]

取均值截距、零斜率的可行基线，惩罚为零，整个目标等于TSS。全局最优及惩罚非负夹住RSS，再除正TSS。不需满秩，也不需声称罚回归残差与全部设计栏正交。其他非负且零斜率时为零的惩罚同理。

$$\begin{gathered} L(a,b)=\|y-a\mathbf1-Xb\|^2+\lambda\|b\|^2,\quad(a_0,b_0)=(\bar y,0),\quad L(a_0,b_0)=\mathrm{TSS}. \\0\le\mathrm{RSS}(\widehat a,\widehat b)\le L(\widehat a,\widehat b)\le L(a_0,b_0)=\mathrm{TSS}. \\0\le1-\mathrm{RSS}(\widehat a,\widehat b)/\mathrm{TSS}\le1. \end{gathered}$$

这道证明为何不需求出系数？ 我们只需证明最优预测不会比一个特定基准的RSS更差，不需要知道最优参数具体是多少。设X是n×p的特征矩阵，b是p维斜率向量，a是标量；选b=0后，所有特征的贡献都消失，只剩预测常数a。再选a为训练响应均值，就恰好得到TSS基准。

把不等式链逐段读。 RSS是平方和，所以非负；惩罚系数非负，使RSS不大于“RSS加惩罚”；全局最优解的整个目标不大于任意可行比较点的目标；最后比较点的惩罚是零，所以其目标正好为TSS。这里最关键的是截距不受罚，否则最后这一步会像(a)那样失效。随后除以正TSS，先得到RSS/TSS在0和1之间，再用1减去它得到R²的范围。

若TSS=0，所有响应相同，通常的R²分式分母为零，这个证明不能宣称其值为0或1。证明也只针对用于优化的训练数据；另一批测试数据的均值和误差不同，不在这个比较链中。系数是否唯一与这个分数界是不同问题，因此不需要X满秩。

评分： 比较点1；目标TSS1；不等式链1；正TSS及界1。

配套题本 Q2(b)

(c) [4]

第一，均值尺度与PCA方向预先读取测试特征，即使没读标签也泄漏。第二，用测试成绩选参数使测试集充当验证，最好成绩有选择偏差。先隔离最终测试并尊重时间或群组结构；训练内部每折只用该折训练子集拟合缩放、PCA、ridge，固定变换用于验证，再汇总选择惩罚及维数。锁定后全开发数据重拟合整个流程，最后独立测试一次。先全开发数据PCA再CV仍折内泄漏。

先辨认什么算“拟合”。 训练不只是在最后调用ridge。计算均值、标准差、PCA方向也在用数据估计参数；没有使用标签，不等于没有使用测试信息。测试集的目的，是模拟尚未见过的数据，不能让它参与选择表示方式。

可以把正确过程按时间顺序写成四步：①先隔离最终测试集，并按需要采用时间或群组划分；②在开发数据内部划分每个训练折和验证折；③只在训练折估计缩放参数、拟合PCA及ridge，用同一套已固定的变换处理验证折，汇总验证误差后选择惩罚强度与维数；④锁定选择，在全部开发数据上重新估计整条流程，然后对最终测试集评价一次。验证折不能自己重新估计一套均值或PCA，否则坐标系也与训练模型不一致。

两个错误必须分别指出。 即使修正了预处理，反复看测试成绩挑参数仍然会泄漏；即使不调测试成绩，提前全数据PCA也仍然泄漏。如果测试集已被用于选参数，它的最好成绩不能再被描述为独立最终测试结果。评分看的是指出信息进入流程的位置，并说明每一折如何重新拟合，不是只写一句“使用交叉验证”。

评分： 预处理泄漏1；测试调参1；折内流程1；重拟合独立测试1。

配套题本 Q2(c)

Q3. 负主特征值与一次补全 (15)

配套题本 Q3

(a) [4]

矩阵相乘得到原向量及长度。最大绝对值特征值为−3，初值在其方向投影非零。偶数步趋向正第一轴、奇数步趋向负第一轴；有向向量不收敛到一个向量，但直线方向收敛。除以正长度不会使特征值估计必为正。

$$\begin{gathered} Bv^{(0)}=\frac1{\sqrt2}\binom{-3}{1},\quad\|Bv^{(0)}\|=\sqrt5,\quad v^{(1)}=\frac1{\sqrt{10}}\binom{-3}{1}. \\(v^{(1)})^TBv^{(1)}=-3\frac9{10}+\frac1{10}=-\frac{13}5. \\v^{(t)}=\frac1{\sqrt{9^t+1}}\binom{(-3)^t}{1},\quad\frac{-3\cdot9^t+1}{9^t+1}\longrightarrow-3. \end{gathered}$$

按算法顺序，不跳过长度。 B是2×2，迭代向量有两个分量。先用B乘初始向量，再算所得向量的欧氏长度：其长度平方为(9+1)/2=5，所以除以√5后得到分母√10。新向量的平方长度是(9+1)/10=1，因此Rayleigh商的分母已经是1；不能把这个长度当作带符号的特征值。

负号为什么一直出现？ 连续乘B，会使第一分量每次乘−3，第二分量每次乘1。归一化只改变整体长度，不改变分量之比，所以可直接写出第t步表达式。第一分量绝对值相对第二分量越来越大，但符号每步翻转。幂法所需的是初始向量在绝对值最大特征方向上的分量非零，本题满足；若一开始只有第二分量，就不会找到−3。

Rayleigh商使用第一、第二分量的平方作为权重，因此向量统一反号不改变商。第一方向的平方权重趋向1，商便趋向−3。要分别回答“向量是否收敛”“无向直线是否收敛”和“商是否收敛”，不能用其中一个替代其余两个。

评分： 归一化向量1；商1；极限1；符号方向区别1。

配套题本 Q3(a)

(b) [6]

先分解Gram矩阵得奇异值平方；选右向量后用矩阵相乘再除对应奇异值得左向量。原对称矩阵第二特征值为负，因此第二左向量须为右向量负号。对称不代表非负奇异值分解可以U=V；须核对正交及乘积。

$$\begin{gathered} (X^{(0)})^TX^{(0)}=\begin{pmatrix}5&4\\4&5\end{pmatrix},\quad(5-\eta)^2-16=(\eta-9)(\eta-1),\quad\sigma_1=3,\ \sigma_2=1. \\v_1=\frac1{\sqrt2}(1,1)^T,\quad v_2=\frac1{\sqrt2}(1,-1)^T,\quad X^{(0)}v_1=3v_1,\quad X^{(0)}v_2=-v_2. \\u_1=v_1,\quad u_2=-v_2,\quad U=\frac1{\sqrt2}\begin{pmatrix}1&-1\\1&1\end{pmatrix},\quad\Sigma=\begin{pmatrix}3&0\\0&1\end{pmatrix},\quad V=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}. \\U^TU=V^TV=I_2,\qquad U\Sigma V^T=\frac32\begin{pmatrix}1&1\\1&1\end{pmatrix}-\frac12\begin{pmatrix}1&-1\\-1&1\end{pmatrix}=X^{(0)}. \end{gathered}$$

为什么先算Gram矩阵？ 奇异值按定义非负，而原矩阵的特征值可能有负号。右奇异向量是转置乘原矩阵所得Gram矩阵的单位特征向量，奇异值则是其特征值的非负平方根。这里两个特征值9与1分别给出3与1，而不是把9、1直接填进Σ。U、Σ、V都是2×2，每一列的先后次序必须与对应奇异值一致。

左向量不能独立任选。 选定v₁、v₂以后，用原矩阵乘它们，再分别除以3与1，才得到配对的u₁、u₂。第二方向被原矩阵反向，所以负号必须放入第二左向量；若强行取U=V且Σ非负，重构会失去这个负号。可同时把同一对左右向量反号，因为两个负号在外积中抵消，但只改一边会改变乘积。

最后把两个秩一项分别相加：第一项为3/2乘全1矩阵，第二项为−1/2乘交替符号矩阵，因此对角得到1、非对角得到2。正交性检查每列长度为1且两列内积为零；乘积检查确保方向、符号和次序都配对正确。

评分： Gram及谱2；奇异值1；V1；配对U1；验证1。

配套题本 Q3(b)

(c) [5]

软阈值后只留值2的一个奇异分量。恢复时左下角改回观测2，缺失的右上角仍为估计1。低秩估计与满足观测的迭代矩阵用途不同；恢复条目不保持秩，也不必保持对称。不能因初值对称就一起改两处非对角。

$$\begin{gathered} (3-1)_+=2,\quad(1-1)_+=0,\quad Y=U\operatorname{diag}(2,0)V^T=\begin{pmatrix}1&1\\1&1\end{pmatrix}. \\X^{(1)}=\begin{pmatrix}1&1\\2&1\end{pmatrix},\quad\operatorname{rank}(Y)=1,\quad\det X^{(1)}=-1,\quad\operatorname{rank}(X^{(1)})=2. \end{gathered}$$

把两个操作分开。 软阈值作用在奇异值上，不是把矩阵每个条目减1；(s−1)₊表示先减1，再与0取最大值。所以3变2，1变0。只剩第一对奇异向量的外积，得到四个条目均为1的Y。它只有一个非零奇异值，秩为1。

接下来才执行“恢复观测”：检查观测位置的掩码，而不是检查矩阵是否对称。左下角是观测值2，必须写回2；右上角是缺失值，保留Y给出的估计1；两个对角观测本来就是1，不再改变。得到的X⁽¹⁾因此不对称，其行列式为1−2=−1，所以在2×2情形下满秩。

这不矛盾：Y承担低秩收缩估计的角色，X⁽¹⁾承担下一轮输入且满足观测的角色。恢复硬约束会破坏低秩性质；本问只要求这一次更新，不能把Y误报为已恢复矩阵，也不能因一次更新满秩就声称算法失败。

评分： 阈值1；Y1；恢复矩阵1；两秩1；角色解释1。

配套题本 Q3(c)

Q4. 经典多维尺度分析 (9)

配套题本 Q4

(a) [5]

中心化坐标的距离平方等于两个范数平方减两倍内积。左右乘H时因H1=0消去只依赖行或列的范数项，且HGH=G。计算平方距离行均值及总均值可省两次矩阵乘法；行和零检查中心化。先平均再平方是不同操作。

$$\begin{gathered} D_{ij}^2=G_{ii}+G_{jj}-2G_{ij},\quad D^{(2)}=g\mathbf1^T+\mathbf1g^T-2G,\quad H\mathbf1=0,\quad HGH=G. \\HD^{(2)}H=-2G,\quad D^{(2)}=\begin{pmatrix}0&1&9\\1&0&4\\9&4&0\end{pmatrix}. \\(\overline{D^2}_{1\cdot},\overline{D^2}_{2\cdot},\overline{D^2}_{3\cdot})=(10/3,5/3,13/3),\quad\overline{D^2}_{\cdot\cdot}=28/9. \\G_{ij}=-\frac12(D_{ij}^2-\overline{D^2}_{i\cdot}-\overline{D^2}_{\cdot j}+\overline{D^2}_{\cdot\cdot}),\quad G_{11}=16/9,\quad G_{12}=4/9. \\G=\frac19\begin{pmatrix}16&4&-20\\4&1&-5\\-20&-5&25\end{pmatrix},\quad G\mathbf1=0. \end{gathered}$$

双中心化究竟消掉什么？ 设Z的每一行是一点的中心化坐标，G=ZZᵀ是3×3的内积矩阵，g记录G的三个对角元，即各点的平方长度。平方距离展开成“第i点长度平方＋第j点长度平方−两倍内积”。前两项分别只依赖行或列，所以能写成含全1向量的两个外积。

H是3×3的中心化矩阵I−11ᵀ/3。由于H乘全1向量为零，左右乘H就消除了这两个外积；又因为Z已中心化，HZ=Z，故HGH=G，留下的只有−2G。这说明为什么要先逐元素平方距离，再做双中心化，而不是直接中心化距离，也不是计算矩阵乘积D·D。

逐项计算示范。 第一行平方距离0、1、9的平均是10/3；第二行是5/3；第三行是13/3。九个条目总和为28，所以总均值是28/9，不是除以3。算G₁₁时，括号内为0−10/3−10/3+28/9=−32/9，乘−1/2得16/9；算G₁₂时，括号内为1−10/3−5/3+28/9=−8/9，得4/9。其余条目按同样规则算，并用对称性与每行和为零复核。

评分： 距离展开中心化2；平方矩阵1；G2。

配套题本 Q4(a)

(b) [4]

识别秩一外积，唯一正特征值为向量平方范数，其余为零。单位特征向量乘特征值平方根而非特征值。坐标和零并重现所有距离；中心化固定平移，但同时反号的镜像仍可。若不中心化，还可整体平移。

$$\begin{gathered} z=\frac13(-4,-1,5)^T,\quad G=zz^T,\quad\lambda_1=z^Tz=\frac{42}9=\frac{14}3,\quad\lambda_2=\lambda_3=0. \\q_1=\frac1{\sqrt{42}}(-4,-1,5)^T,\quad\sqrt{\lambda_1}q_1=(-4/3,-1/3,5/3)^T=z. \\\sum_i z_i=0,\quad |z_1-z_2|=1,\quad|z_1-z_3|=3,\quad|z_2-z_3|=2,\quad z\longleftrightarrow-z. \end{gathered}$$

如何不用展开三次特征方程？ 已算出的G各行成比例，可尝试写成一个列向量乘其转置。找到z后，直接计算Gz=z(zᵀz)，说明z是特征向量，特征值为它的长度平方。任何与z正交的向量都会被G映成零，因此另外两个特征值都是零。三个对象只需一维，是由秩决定，不是由对象数量直接决定。

为何坐标要乘平方根？ 单位特征向量只规定方向与单位长度，若坐标取αq₁，其Gram矩阵便是α²q₁q₁ᵀ。为了匹配特征值λ₁，必须让α²=λ₁，因此取平方根；直接乘λ₁会把尺度平方错。最后不只检查坐标和为零，还要逐对求绝对差，得到1、3、2，才真正验证重建了全部题设距离。

同时反号相当于一维镜像，所有差的绝对值不变，是同样正确的解；只反号其中一个点则一般不正确。中心化排除了整体平移自由度，但没有排除镜像自由度。

评分： 谱1；向量或外积1；坐标1；镜像与中心化1。

配套题本 Q4(b)

Q5. 指定协方差归一化的LDA (9)

配套题本 Q5

(a) [4]

类内协方差须各点减本类均值。第一类只横向变化，第二类只纵向变化；外积和除指定4，不改n−1或各类样本分母。类间协方差则类均值减总体均值再平均外积。

$$\begin{gathered} \mu_1=(0,0)^T,\quad\mu_2=(3,2)^T,\quad\mu=(3/2,1)^T. \\S_1=\begin{pmatrix}2&0\\0&0\end{pmatrix},\quad S_2=\begin{pmatrix}0&0\\0&8\end{pmatrix},\quad\Sigma_W=\frac{S_1+S_2}{4}=\begin{pmatrix}1/2&0\\0&2\end{pmatrix}. \\\mu_1-\mu=(-3/2,-1)^T,\quad\mu_2-\mu=(3/2,1)^T,\quad\Sigma_B=\begin{pmatrix}9/4&3/2\\3/2&1\end{pmatrix}. \end{gathered}$$

先决定减哪个均值。 每个观测是2维列向量，协方差矩阵是2×2。类内变化描述同类点围绕本类中心的离散，不能先减总体均值，否则类间分离也会混进类内量。第一类偏差是(−1,0)与(1,0)，两个外积各在左上角贡献1；第二类偏差是(0,−2)与(0,2)，两个外积各在右下角贡献4。因此未归一化的散布和分别为2与8。

题面要求把两类散布相加后除以全部样本数4，便得到对角元1/2与2。这是指定定义，不是要自行估计无偏协方差。类间量则以两个类均值为对象，减总体均值后得两个互为相反的向量；相反向量的外积相同，取平均仍是同一个矩阵。其非对角元为(3/2)×1=3/2，而不是零。

检查：两类样本数相同，所以总体均值也是两个类均值的简单平均；两种协方差均应对称且半正定。总体中心化与类内中心化不能互换，分母的修改也不能被当成无关细节，因为下一问的广义特征值会受影响。

评分： 均值1；类内中心化协方差2；类间1。

配套题本 Q5(a)

(b) [3]

类内矩阵正定，可用逆协方差加权。两类等大使类间协方差为均值差外积的四分之一。广义谱为5与0；最大方向单位化并满足符号。不能直接用单位均值差，因为第一特征类内变化较小。漏四分之一不改方向却使特征值错误扩大四倍。

$$\begin{gathered} d=\mu_2-\mu_1=(3,2)^T,\quad\Sigma_B=dd^T/4,\quad\Sigma_W^{-1}d=(6,1)^T,\quad u=\frac1{\sqrt{37}}(6,1)^T. \\\Sigma_W^{-1}\Sigma_B=\begin{pmatrix}9/2&3\\3/4&1/2\end{pmatrix},\quad\begin{pmatrix}9/2&3\\3/4&1/2\end{pmatrix}\binom61=5\binom61. \\\lambda_{\max}=5,\quad u^T\Sigma_Wu=20/37,\quad u^T\Sigma_Bu=100/37,\quad\frac{u^T\Sigma_Bu}{u^T\Sigma_Wu}=5. \end{gathered}$$

为何方向要乘逆类内协方差？ LDA比较投影后的类间变化与类内变化之比。均值差d只告诉我们两类中心隔多远，没有考虑各方向内部有多“散”。第一坐标的类内方差为1/2，第二坐标为2；逆协方差分别乘2与1/2，把低类内噪声方向的权重提高，于是(3,2)变成(6,1)，而不是直接把(3,2)单位化。

正定性保证任意非零方向的分母为正，也保证可以求逆。此处类间矩阵是秩一，所以除最大方向外只剩零特征值；乘积矩阵的迹为9/2+1/2=5，行列式为0，给出特征值5与0，证明找到的不只是某个特征方向，而是最大方向。注意逆矩阵乘类间矩阵不必对称，不能仅凭外观就否认它的用途。

将(6,1)除以√37后长度为1，第一分量为正，符合题设符号约定。再分别算分子100/37与分母20/37，其比为5，提供独立检查。方向缩放不会改变这个比值，但把类间协方差漏掉1/4会把比值整体放大四倍。

评分： 可逆与方向1；单位化符号1；最大特征值1。

配套题本 Q5(b)

(c) [2]

逐点与原始观测取内积，平均应等于总体均值的投影。中心化投影会各减该共同值，虽不改变类间分离，却不是本问指定坐标。

$$\begin{gathered} (u^Tx_1,u^Tx_2,u^Tx_3,u^Tx_4)=\frac1{\sqrt{37}}(-6,6,18,22),\quad\frac14\sum_i u^Tx_i=\frac{10}{\sqrt{37}}=u^T\mu. \end{gathered}$$

把投影看成一个具体算式。 uᵀx是标量：将原始点第一坐标乘6，第二坐标乘1，再把总和除以√37。四个原始点依次为(−1,0)、(1,0)、(3,0)、(3,4)，故分子依次为−6、6、18、22。这里不再另减均值，也不把投影结果再单位化。

利用线性性，先投影再平均应等于先平均再投影，所以四个分子的平均为10，正好与6×(3/2)+1=10一致。若误用中心化数据，分子会全部减10，变成−16、−4、8、12；这能保留相对距离，却不是本问所要的原始投影。这个核验能发现“答案看起来分得开，但整体位置错了”的情况。

评分： 每个投影0.5。

配套题本 Q5(c)

Q6. 层次聚类：链接定义的重要性 (15)

配套题本 Q6

(a) [4]

先列六个原始距离。单链接取跨簇最小距离。合并A、B后重算到C、D距离；B到C较短，使C下一步加入；最后D按到C距离加入。链式吸收不要求C靠近簇内每一点，本例无影响选择的平局。

$$\begin{gathered} \begin{array}{c|rrrrrr}\text{pair}&AB&AC&AD&BC&BD&CD\\d&2&5&17/2&3&13/2&7/2\end{array} \\d_{\rm single}(AB,C)=\min(5,3)=3,\quad d_{\rm single}(AB,D)=\min(17/2,13/2)=13/2,\quad d(C,D)=7/2. \\d_{\rm single}(ABC,D)=\min(17/2,13/2,7/2)=7/2. \\ A+B\text{ at }2;\qquad AB+C\text{ at }3;\qquad ABC+D\text{ at }7/2. \end{gathered}$$

从点距离到簇距离。 点在实数轴上，所以用坐标差的绝对值，不用平方距离。开始每点独立成簇，六个点对中2最小，所以第一步没有争议。合并A、B之后，算法的对象已经变成三个簇，不能继续从旧点对表中机械取下一个尚未用过的数。

单链接的规则是每两个当前簇之间取最短跨簇距离。因此AB到C要比较AC与BC，取3；AB到D比较AD与BD，取13/2；C到D仍为7/2。再比较这三个候选距离，3最小，才得到ABC。最后比较A、B、C各自到D的距离，最小者来自C，给7/2。

合并高度记录当时两个簇的链接距离，不是新簇的直径。例如ABC的直径是5，但它在高度3形成。树状图应先在2连接A、B，再在3接C，最后在7/2接D；三个高度递增，且最终只剩一个簇，可作为流程核验。

评分： 初始与首合并1；更新与第二步2；最终1。

配套题本 Q6(a)

(b) [7]

单点间定义相同，所以首步仍A、B。此后平均所有跨簇点对，不再选最近点对。C、D距离小于AB到C平均，故第二步合并C、D。最后两两大小为2的簇共有四点对，全部平均；树形和高度都与单链接不同，不能改成质心距离。

$$\begin{gathered} d_{\rm av}(AB,C)=\frac{5+3}{2}=4,\quad d_{\rm av}(AB,D)=\frac{17/2+13/2}{2}=15/2,\quad d(C,D)=7/2<4. \\d_{\rm av}(AB,CD)=\frac{d(A,C)+d(A,D)+d(B,C)+d(B,D)}{4} \\=\frac{5+17/2+3+13/2}{4}=23/4. \\ A+B\text{ at }2;\qquad C+D\text{ at }7/2;\qquad AB+CD\text{ at }23/4. \end{gathered}$$

相同的第一步不代表后面相同。 单点簇之间只有一个跨簇点对，所以取最小值与取平均都给原点距离。出现AB这个二点簇后，AB到C有两个点对，平均为4；AB到D也有两个，平均为15/2。此时C到D的7/2比4更小，所以不能沿用上一问的AB吸收C，而要先形成CD。

最后比较AB与CD，跨簇配对是AC、AD、BC、BD，恰好2×2=4个。AB和CD自身内部的距离不属于跨簇和，不可放入分子；分母也不是“两个簇所以除以2”。四个距离总和为23，再除4得到23/4。它位于这四个距离的最小值3与最大值17/2之间，满足平均值的基本范围。

树形也要说明。 单链接在第二步产生一个三点簇；平均链接在第二步产生两个二点簇，最后才合并两边。平均链接的定义是平均全部跨簇点对距离，不能一般地用质心距离替代，即使某些一维分离情形下数值碰巧相同。

评分： 首步1；三个距离3；第二步1；四对平均及高度2。

配套题本 Q6(b)

(c) [4]

把双和拆成S、T两组，每个旧均值先乘对应点对数再合并；共同|U|约去。簇大小相等才对任意旧距离保证简单平均；大小不等时若旧距离恰等亦偶然正确，但不是通则。数值反例显示差别。

$$\begin{gathered} d_{\rm av}(S\cup T,U)=\frac{\sum_{s\in S,u\in U}d(s,u)+\sum_{t\in T,u\in U}d(t,u)}{(|S|+|T|)|U|} \\=\frac{|S||U|d_{\rm av}(S,U)+|T||U|d_{\rm av}(T,U)}{(|S|+|T|)|U|} \\=\frac{|S|d_{\rm av}(S,U)+|T|d_{\rm av}(T,U)}{|S|+|T|}. \\|S|=|T|\Longrightarrow d_{\rm av}(S\cup T,U)=\tfrac12[d_{\rm av}(S,U)+d_{\rm av}(T,U)]. \\|S|=2,\ |T|=1,\ d_{\rm av}(S,U)=4,\ d_{\rm av}(T,U)=10:\quad\frac{2(4)+10}{3}=6\ne7=\frac{4+10}{2}. \end{gathered}$$

为什么必须用簇大小作权重？ 旧距离dₐᵥ(S,U)本身已经是平均数，不是总距离。要把它与另一个平均数合并，先恢复各自的总量：S与U有|S||U|个点对，所以乘这个数量；T与U则乘|T||U|。两份总量相加后，再除新的总点对数(|S|+|T|)|U|。共同的|U|约掉，才得到按|S|与|T|加权的更新式。

这里S、T是互不相交的非空旧簇，U也是另一非空簇，所以分母不为零且拆和不重复计数。简单平均给两个旧簇相同权重，而真正定义给每个跨簇点对相同权重；大簇提供更多点对，理应贡献更大。

例如两份旧平均分别4和10，第一份对应两倍数量的点对，所以合并平均更接近4，得到6，不是中点7。只有簇大小相等才能对任意两份旧距离保证简单平均正确；两份旧距离本身相同也会碰巧正确，但这不是忽略大小的普遍依据。

评分： 拆和1；点对数1；公式1；保证与偶然区别1。

配套题本 Q6(c)

Q7. DBSCAN：共享边界点不是核心桥 (18)

配套题本 Q7

(a) [6]

先列闭邻域，再按至少四点判核心。E仅三邻居，不是核心，但邻近核心D、F，所以是边界不是噪声。J既非核心也不在任何核心半径1内，故噪声。漏自身会改变题设约定。

$$\begin{gathered} \begin{array}{c|l|r}p&N_1(p)&|N_1(p)|\\A&\{A,B,C,D\}&4\\B&\{A,B,C,D\}&4\\C&\{A,B,C,D\}&4\\D&\{A,B,C,D,E\}&5\\E&\{D,E,F\}&3\\F&\{E,F,G,H,I\}&5\\G&\{F,G,H,I\}&4\\H&\{F,G,H,I\}&4\\I&\{F,G,H,I\}&4\\J&\{J\}&1\end{array} \\\text{core}=\{A,B,C,D,F,G,H,I\},\quad\text{border}=\{E\},\quad\text{noise}=\{J\}. \end{gathered}$$

先固定三个容易混淆的定义。 邻域由距离不超过1的点构成，包括自身，也包括距离恰好为1的点；核心点要求邻域数量至少4，不是“除了自身再找4个”；非核心点若邻近某个核心点就是边界点，否则才是噪声。分类应先确定所有核心点，再判断剩余点，不能把所有不足4的点立即标成噪声。

例如D坐标为−0.9，到A、B、C的距离分别为0.9、0.8、0.7，到自身为0，到E为0.9，故共5个；到F已经是1.8，不在邻域。E位于0，只有自身及两边0.9处的D、F共3个，不足核心门槛，但D和F都是核心，所以E是共享边界点。J到最近的I仍为2.2，大于1，只有自身且不邻近任何核心点，所以是噪声。

表中的A、B、C与G、H、I各有四个邻域点，恰好达门槛，不能把“至少4”误读为“超过4”。逐点列邻域比凭图形觉得某点密集更可靠；评分需要数量与分类都正确。

评分： 全部数量3；八核心、E边界、J噪声3。

配套题本 Q7(a)

(b) [4]

从A开始，左核心分量扩张到D并纳入E；E非核心，不能继续到F。处理F时形成右簇，E保留首次归属。若先处理右边，E可能改归右，但两核心分量不会因此合并；区分边界归属依赖顺序与核心连通结构。

$$\begin{gathered} C^{(1)}=\{A,B,C,D,E\},\quad C^{(2)}=\{F,G,H,I\},\quad\text{noise}=\{J\}. \end{gathered}$$

按访问顺序模拟，而不是把所有相邻点直接连通。 先处理A，因为A是核心，它的邻域进入第一簇；B、C、D也都是核心，可继续贡献它们的邻域。D把E带入第一簇，但处理E时发现它只有三个邻居，于是停止从E继续传播。E可以成为队列中被访问的点，却不因此取得核心点的扩张权限。

再走到尚未属于已有簇的F，它是核心，启动第二簇并吸收G、H、I。虽然F也看得到E，但本题“第一次归属保留”规则使E仍留在第一簇。J没有任何核心邻居，最后仍是噪声。最终两个簇的大小为5与4，加上1个噪声，正好覆盖全部10个点且不重复分配。

若反向访问，E可能属于右簇，但左侧四个核心与右侧四个核心仍是两个独立核心分量。这里顺序影响的是共享边界点的标签，不是允许借E把两簇合并。

评分： 左核心1；右核心1；E归左1；J噪声1。

配套题本 Q7(b)

(c) [4]

不等价。D、F核心，所以D–E与E–F均为合法图边，路径把两密集分量接通，虽内部E非核心。无向传递连通忽略该区别。标准扩张可从D到E，却不能由E再发起到F。忠实表示应先只连核心点求核心分量，再按顺序附加边界；边界不负责合并。

$$\begin{gathered} |D-E|=0.9\le1,\quad|E-F|=0.9\le1,\quad D\longleftrightarrow E\longleftrightarrow F. \\\operatorname{component}_{\rm graph}(D)=\{A,B,C,D,E,F,G,H,I\}\ne C^{(1)}. \end{gathered}$$

先确认反例确实符合研究者规则。 这条图规则只要求边的两个端点中至少一个是核心。D–E边有核心端点D，E–F边有核心端点F，两条长度又都不超过1，所以两条都是合法无向边。虽然E本身不是核心，无向图连通性依然允许先走D到E，再走E到F，从而把两边的核心区域合为一个连通分量。

标准DBSCAN的条件却附着在“谁发起下一步扩张”上：从核心D可以把E纳入，但E不是核心，不能再从E走到F。把这种有条件传播替换成无向路径传递，就丢掉了关键限制；不是因为两条边距离算错，而是图模型表达的关系与算法不同。

因此仅写“不等价”不够，要展示两条合法边和合并后的九点分量，并指出E是阻止标准扩张继续的非核心内部点。忠实的构造是先在核心点子图求分量，再按题定顺序把相邻边界点附加进去；不能让边界点充当合并分量的桥。

评分： 不等价1；两图边1；合并分量1；非核心不扩张1。

配套题本 Q7(c)

(d) [4]

排序距离含起始零；第四第五并列不改变至少包含四点的最小半径。E需更宽邻域才有足够密度，将普通长度0.9提高至权重1.6，使稀疏连接在密度层次较晚发生。这只是HDBSCAN构造的一部分，不等于完成最终选簇。

$$\begin{gathered} D:\ 0,0.7,0.8,0.9,0.9,\ldots\quad\Longrightarrow\quad\operatorname{core}_4(D)=0.9. \\E:\ 0,0.9,0.9,1.6,1.6,\ldots\quad\Longrightarrow\quad\operatorname{core}_4(E)=1.6. \\d_{\rm mr}(D,E)=\max\{0.9,1.6,0.9\}=1.6. \end{gathered}$$

核心距离和是否核心是两个相关但不同的问题。 在固定半径1下，E不是核心；它仍然有一个“要把半径扩大到多少才纳入至少4点”的核心距离。排序时含自身的零距离，所以找第4项，而不是跳过零以后再找第4项。D的前三项来自自身、C、B，第四项来自A或E，所以核心距离0.9；E的前三项来自自身、D、F，第四项来自C或G，所以为1.6。

第四、第五项并列，只表示在该半径同时纳入两个点，不需要挑一个打破平局。定义是至少4点的最小半径，不要求恰好4点。互可达距离取三者最大值：两个端点各自的核心距离，以及两点原始距离，所以必须同时尊重两端的密度尺度，最后由E的1.6主导。

原始边D–E只有0.9，看似很近；升到1.6表示这条边受到稀疏端点的限制。在按距离阈值逐渐增大而连接的层次中，它要等到更大的阈值才出现。这里只算一条互可达边，尚未计算完整最小生成树、凝聚层次或稳定性选簇，不能据此报出最终HDBSCAN聚类。

评分： 各核心距离1；互可达1；密度与升权解释1。

配套题本 Q7(d)