答：
代码在 10.1
这里用 kd 树实现的 knn，测试了一下，在数据量大的时候 kd 树确实比穷举法要快很多。
关于决策边界：
感觉最大的不同就是决策树的决策边界都是平行特征对应的超平面的，而 knn 则曲线的，这一点很好理解。感觉没啥相同点.
10.2 令 err 、 err* 分别表示最近邻分类器与贝叶斯最优分类器的期望错误率，试证明 $ err^{\ast} \leq err \leq err^{\ast}(2 - \frac{\left| y \right|}{\left| y \right| - 1} ) \times err^{\ast}$ .
答：
先看第一个不等式，由 p226 式 10.2 可知： $ err \simeq 1 - \sum_{c \in Y} {P^2(c|x)} $ , 而 $ err^{\ast} = 1 - P(c^{\ast}|x) $ , 其中 $ c^{\ast} = arg max_{c \in Y} {P(c|x)}$, 由于 $ \sum_{c \in Y} {P^2(c|x)} \leq \sum_{c \in Y} {P(c^{\ast} | x)P(c|x)} = P(c^{\ast}|x)$ , 于是可得 $ err^{\ast} \leq err $.
关于第二个不等式，$ err \simeq 1 - \sum_{c \in Y} {P^2(c|x)} = 1 - P^2{c^{\ast} | x} - \sum_{c \in Y/c^{\ast}} {P^2(c | x)} = (2 - err^{\ast})err^{\ast} - \sum_{c \in Y/c^{\ast}} {P^2(c | x)}$
由 $ \sum_{c \in Y/c^{\ast}} {P(c | x)} = 1 - P(c^{\ast} | x) = err^{\ast} $
可得 $ \sum_{c \in Y/c^{\ast}} {P^2(c | x)} $ 在 $ P(c|x) = \frac{err^{\ast}}{\left| Y \right| - 1}$ 时取得最小值，
具体可通过拉格朗日乘子法求得，很简单，这里不细说；再接着可得
$ \sum_{c \in Y/c^{\ast}} {P^2(c | x)} \geq (\left| Y \right| - 1)(\frac{err^{\ast}}{\left| Y \right| - 1})^2 = \frac{{err^{\ast}}^2}{\left| Y \right| - 1}$
因此
$ err \simeq 1 - \sum_{c \in Y} {P^2(c|x)} = (2 - err^{\ast})err^{\ast} - \sum_{c \in Y/c^{\ast}} {P^2(c | x)} $
$ \leq (2 - err^{\ast})err^{\ast} - \frac{{err^{\ast}}^2}{\left| Y \right| - 1} = err^{\ast}(2 - \frac{\left| y \right|}{\left| y \right| - 1} ) \times err^{\ast}$
得证.
10.3 在对高维数据降维之前应先进行"中心化", 常见的是将协方差矩阵 $ XX^T $ 转化为 $ XHH^TX^T $ ，其中 $ H = I - \frac{1}{m} 11^T $ ，试析其效果.
答：
先说结论，$ XHH^TX^T $ 就是直接求未中心化的数据样本的协方差矩阵。
另外，这里题中表述感觉有点奇异，实际上，$ XX^T $ 是协方差矩阵的前提是 X 经过 “中心化”，当然严格来说其实还要再除以 m ，参考协方差矩阵,对于$ X = (X_1, X_2, ..., X_m) \in R^{d \times m}$, 其协方差矩阵 $ \varSigma $ 有： $ \varSigma_{ij} = cov(X_i, X_j) = E[(X_i - u_i)(X_j - u_j)] = \frac{1}{m} \sum_{k=1}^{m} {(X_{ik} - u_i)(X_{jk} - u_j)}$， 若 X 中心化后，则 $ u_i = 0 $， 于是 $ \varSigma_{ij} = \frac{1}{m} \sum_{k=1}^{m} {X_{ik} X_{jk}} =\frac{1}{m} X_iX_j^T \Longrightarrow \varSigma = \frac{1}{m} XX^T$ , 这也是为什么要进行中心化的原因。
答：
对 $ X $ 奇异值分解有：$ X = U \varSigma V^T $ ， 于是 $ XX^T = U \varSigma V^T V \varSigma U^T = U \varSigma U^T $, 所以对 X 奇异值分解同样可以得到 其协方差矩阵的特征值，这里奇异值分解后的
事实上从奇异值分解的定义出发也是一样的，参考奇异值分解 ，$ U $ 就是由 $ XX^T $ 的特征值分解得到的。
答：
找了些资料、博客，依然不是很明白...待填坑。
答：
代码在：10.6
PCA 代码实现还是很简单的。这里还是直接使用 numpy 的现有函数进行特征值分解的。另外脸部数据是使用的吴恩达老师机器学习课程里的作业数据。
降维前：
降维后：
特征值向量：
答：
联系在于两者都是非线性降维，只不过核化线性降维是通过核方法，流形学习则是通过“领域保持”。
流形学习的缺点，在书中也 10.7 的阅读材料中也有提及：
流形学习欲有效进行邻域保持则需样本密采样，而这恰是高维情形下面临的重大障碍，因此流形学习方法在实践中的降维性能往往没有预期的好 。
另外流形学习计算复杂度更高，并且大部分流形学习算法不能得到从高维到低维的映射关系，常用解决方案是训练回归学习器得到映射关系。
核线性降维不仅需要保存映射关系矩阵，还要保存原始数据，效率不高。
答：
不会。待填坑。
答：
首先寻找新样本在训练集的近邻集
答：
这里仅讨论下书中给出的马氏距离
- 非负性：书中也提到，保持
$M$ 半正定； - 同一性：同样，半正定矩阵只有在
$x = 0$ 时，才会使得 $ x^T M x = 0$； - 对称性：这一点很显然；
- 直递性：没想出来。待填。