在一些应用中，被研究的实体天然地比较抽象，也不好确定要如何定义它的特征向量。不过只要在数据集中可以得出实体之间两两的相似程度的 $N\times N$ 相似性（proximity）矩阵，我们就可以通过将相似性作为内积的方式继续使用之前已经介绍过的很多分类方法。蛋白质结构就属于这类问题，下面的第 18.5.1 节将介绍一个例子。
在另一些应用中，比如文档分类，特征变量是可得的但可能会是极高维度。在这样的场景中，我们可能不会用这么高维度的数据进行计算，而时记录文档两两之间的内积。这些内积通常可以通过采样的方法来近似。
逐点之间的距离也是为了相似的目的，因为它们可以被转化为中心化的内积。更多关于相似性矩阵的细节可参考第十四章。
18.5.1 例：字符串核函数和蛋白质分类问题
在计算生物学（computational biology）中的一个重要的问题是根据蛋白质的序列相似程度将蛋白质按功能性和结构性进行分类。蛋白质分子可以表述为氨基酸的字符串，有不同的长度和组合。在我们研究的例子中，蛋白质的长度是从 75 到 160 个氨基酸的分子，每个氨基酸可能是 20 个不同类型中的一个，每个氨基酸类型由字母来标记。下面是两个例子，长度分别为 110 和 153：
IPTSALVKETLALLSTHRTLLIANETLRIPVPVHKNHQLCTEEIFQGIGTLESQTVQGGTVERLFKNLSLIKKYIDGQKKKCGEERRRVNQFLDYLQEFLGVMNTEWI
PHRRDLCSRSIWLARKIRSDLTALTESYVKHQGLWSELTEAERLQENLQAYRTFHVLLARLLEDQQVHFTPTEGDFHQAIHTLLLQVAAFAYQIEELMILLEYKIPRNEADGMLFEKKLWGLKVLQELSQWTVRSIHDLRFISSHQTGIP
对两个蛋白质分子之间相似性的测量已经有了很多建议的方法。本节我们关注的是一个基于相同子字符串个数的测度，例如上面例子中的 LQE（Leslie et al., 2004）。
为构建特征变量，我们记录在输入字符串中一个长度为 $m$ 的字符序列出现的次数，并且对所有可能的长度为 $m$ 的字符序列都计算出这个次数。严格来说，对一个字符串 $x$，定义一个特征变量映射：
$$\Phi_m(x) = \{\phi_a(x)\}_{a\in\mathcal{A}_m} \tag{18.25}$$其中的 $\mathcal{A}_m$ 是长度为 $m$ 的子序列集合，$\phi_a(x)$ 是字符序列 $a$ 在输入字符串 $x$ 中出现的次数。利用这个定义，可以定义内积为：
$$K_m(x_1, x_2) = \langle \Phi_m(x_1), \Phi_m(x_2) \rangle \tag{18.26}$$它衡量了两个字符串 $x_1$ 和 $x_2$ 之间的相似程度。这个相似度可被用在（例如）支持向量分类器中，从而将字符串分配到不同的蛋白质类别中。
不过可能的字符序列 $a$ 的个数是 $|\mathcal{A}_m|=20^m$，对中等大小的 $m$ 来说这也可能是很大的数字，而且这些字符序列中的绝大部分不会在训练集中出现。实际上并不需要计算出每一个向量，利用树结构可以高效地计算出 $N\times N$ 的内积矩阵，或式 18.26 中的 字符串基函数（string kernel） $\mathbf{K}_m$。这个方法以及后续的数据集都来自 Leslie et al. (2004)1。
数据包含了两个类别的 1708 个蛋白质：1663 个阴性（negative）和 45 个阳性（positive）。上文中的两个例子就来自于这个数据集，之后将分别标记为 $x_1$ 和 $x_2$。在两个蛋白质（字符序列）中都出现了子序列 LQE，用红色标记了它的位置。共有 $20^3$ 个可能的子序列，所以 $\Phi_3(x)$ 会是一个长度为 8000 的向量。在这个例子中，$\phi_\text{LQE}(x_1)=1$，$\phi_\text{LQE}(x_2)=2$。
利用了 Leslie et al. (2004) 中的软件，我们计算了 $m=4$ 的字符串核函数，然后将其用在一个支持向量分类器中，在这个 $20^4=160,000$ 维度的特征空间上寻找最大间隔解。我们在所有的特征数据上用十折交叉验证来计算支持向量机的预测结果。
图 18.9 中的橙色曲线展示了支持向量分类器的交叉验证 ROC 曲线；交叉验证后的支持向量分类器会得到实数取值的预测结果，通过改变分类临界点可计算出 ROC 曲线。曲线下面积是 0.84。Leslie et al. (2004) 展示了字符串核函数方法与其他专门用于蛋白质字符串比对的方法一样有竞争力，但可能没有它们准确。
只利用基函数矩阵中的信息也可以计算很多其他的分类器；下一段会介绍更多的细节。图 18.9 中也展示了最近中心分类器（绿色）和距离加权的一最近邻（蓝色）的结果。它们的表现与支持向量分类器类似。
18.5.2 使用内积核函数和逐点距离的分类问题和其他模型
除支持向量机外还有一些其他的分类器，它们的计算实现只需要使用内积矩阵即可。这就意味着它们也可以像 SVM 一样利用核函数。
由于可以将逐点（pairwise）内积转换成逐点距离，所以最近邻分类模型是一个明显的例子：
$$\| x_i - x_{i'} \|^2 = \langle x_i, x_i \rangle + \langle x_{i'}, x_{i'} \rangle - 2 \langle x_i, x_{i'} \rangle \tag{18.27}$$图 18.9 中用到了 1-最近邻分类模型的一个变体，它可得出构建 ROC 曲线所需要的一个连续的判别得分值。这个距离加权 1 最近邻模型利用了一个测试点与每个类别中最近点的距离；可参考练习 18.14。
最近中心点分类模型的处理也很简单。给定训练集数据点 $(x_i,g_i)$，$i=1,\dots,N$，一个测试点 $x_0$，和类别的中心点 $\bar{x}_k$，$k=1,\dots,K$：
$$\| x_0 - \bar{x}_k \|^2 = \langle x_0, x_0 \rangle - \frac{2}{N_k} \sum_{g_i=k} \langle x_0, x_i \rangle - \frac{1}{N_k^2} \sum_{g_i=k} \sum_{g_{i'}=k} \langle x_i, x_{i'} \rangle $$ $$\tag{18.28}$$因此就可以计算一个测试点与每个类别中心点之间的距离，并使用最近中心点分类方法。这也意味着像 K 均值这类的方法也可以如此进行计算，即只需要使用到数据点之间的内积。
二次正则化的对数几率和多项回归也可以通过内积核函数来计算实现；可参考第 12.3.3 节和练习 18.13。练习 12.10 利用一个内积核函数推导出了线性判别分析。
主成分分析也可通过内积核函数来计算；因为这个方法比较常用，我们在这里展开一些细节。假设首先有一个中心化的数据矩阵 $\mathbf{X}$，并且令 $\mathbf{X}=\mathbf{U}\mathbf{D}\mathbf{V}^T$ 为它的奇异值分解（SVD，式 18.12）。那么 $\mathbf{Z}=\mathbf{U}\mathbf{D}$ 就是主成分变量矩阵（参考第 14.5.1 节）。不过如果有 $\mathbf{K}=\mathbf{X}\mathbf{X}^T$，则可得出 $\mathbf{K}=\mathbf{U}\mathbf{D}^2\mathbf{U}^T$，所以就可以通过 $\mathbf{K}$ 的特征分解计算出 $\mathbf{Z}$。如果 $\mathbf{X}$ 不是中心化的，则可以对其进行中心化 $\tilde{\mathbf{X}}=(\mathbf{I}-\mathbf{M})\mathbf{X}$，其中的 $\mathbf{M}=\frac{1}{N}\mathbf{1}\mathbf{1}^T$ 是均值算子。所以，当有一个非中心化的内积矩阵，主成分分析就需要计算双重中心化的核矩阵 $(\mathbf{I}-\mathbf{M})\mathbf{K}(\mathbf{I}-\mathbf{M})$ 的特征分解。练习 18.15 进一步地探讨了这个问题，第 14.5.4 节介绍了使用了例如 SVM 中的径向核函数等更一般性核函数的核主成分方法。
而假如只有观测点之间的逐点（平方）欧式距离：
$$\Delta_{ii'}^2 = \| x_i - x_{i'} \|^2 \tag{18.29}$$那么上述的操作仍然可行。关键在于先将逐点距离转化成中心化的内积，然后再核之间一样操作。可将距离写为：
$$\Delta_{ii'}^2 = \| x_i - \bar{x} \|^2 + \| x_{i'} - \bar{x} \|^2 - 2 \langle x_i - \bar{x}, x_{i'} - \bar{x} \rangle \tag{18.30}$$定义 $\mathbf{B}=\{\Delta_{ii’}^2/2\}$，然后对其进行双重中心化：
$$\tilde{\mathbf{K}} = (\mathbf{I} - \mathbf{M}) \mathbf{B} (\mathbf{I} - \mathbf{M}) \tag{18.31}$$则易验证得出 $\tilde{K}_{ii’}=\langle x_i-\bar{x},x_{i’}-\bar{x}\rangle$，即为中心化的内积矩阵。
距离和内积也可用来计算每个类别的中心点（medoid），即在一个类别中与其他观测点的平均距离最小的观测点。它可以被用于分类方法（最近中心点），也是 K 中心点聚类方法的基础（第 14.3.10 节）。在像蛋白质这种抽象的数据样本中，中心点相对均值点在实践上有一些优势。中心点也是训练样本中的一个点，并可以被展示出来。在下一节的例子中尝试了最近中心点方法（参考表 18.3），不过它的表现并不理想。
同时也有必要注意到内积核函数和距离所无法满足的地方：
- 无法对特征变量进行标准化。在下一节的例子中，标准化可以显著地提升模型的表现。
- 无法直接获得单个特征变量的贡献度。具体来说，我们无法使用单变量的 t 检验、拟合最近收缩中心模型、或拟合任意使用了套索惩罚项的模型。
- 无法区分出噪声和有效的特征变量，所有的变量都被同等对待。如果有效变量与无效变量的比例较小（实际情况通常是符合这个假设的），那么使用核函数的方法可能不如使用特征选择的方法表现好。
18.5.3 例：摘要分类
这是一个用来演示核函数方法局限性的有点怪诞的例子。我们从 Bradley Efron（BE）、Trevor Hastie 和 Rob Tibshirani（HT，两位合著频繁）、以及 Jerome Friedman（JF）各搜集了 16 篇论文，共 48 篇论文的摘要。从这些摘要中提取出不重复的所有单词，然后将特征 $x_{ij}$ 定义为单词 $j$ 在摘要 $i$ 中出现的次数。这就是所谓的 词袋（bag of words，BOW） 模型。首先将引号、括号、和特殊字符从摘要中剔除，然后将所有字母都转化为小写。同时也排除了单词“we”（我们），因为它可能会直接判别出 HT 的摘要。
共有 4492 个单词，其中有 $p=1310$ 个不重复的单词。我们试图基于特征变量 $x_{ij}$ 来将摘要文档分类到 BE、HT、或 JF。尽管这是一个虚拟的例子，但它可以让我们看到如果不使用原始特征中的特定信息可能会带来模型效果的退化。
| 方法 | CV Error (SE) |
|---|---|
| 1. 最近收缩中心 | 0.17(0.05) |
| 2. 支持向量机 | 0.23(0.06) |
| 3. 最近中心点（medoid） | 0.65(0.07) |
| 4. 1-最近邻 | 0.44(0.07) |
| 5. Nearest centroids | 0.29(0.07) |
表 18.3：摘要例子的交叉验证误差率。最近收缩中心最后选择了没有收缩，但使用了逐单词的标准化（第 18.2 节）。这个标准化给它带来了其他方法所不具备的优势。
我们先在数据上使用了最近收缩中心分类器，并且进行了了十折交叉验证。它基本上选择了不收缩，因此使用了所有的特征；表 18.3 的第一行展示了结果。误差率为 17%；在不会引起准确率太多下降的前提下，特征的数量可以被降低至 500 个左右。需要注意最近收缩中心分类器需要原始的特征变量矩阵 $\mathbf{X}$ 才能对单个的特征变量进行标准化。
图 18.10 展示了最有辨别力的前 20 个单词，正得分（score）表示这个单词在这个类别中比在其他类别中更经常地出现。
这些词中有一些是有道理的：例如“frequentist”（频率学派）和“bayesian”（贝叶斯学派）就反映出了 Efron 对统计推断方向的更多关注。然而也有一些出人意料的单词，反映出了个人写作风格：例如 JF 对“presented”的使用和 HT 对“propose”的使用。
然后我们使用了无正则化的线性核函数的支持向量分类器，在处理三个类别时使用了两两对比（OVO）的方法（SVM 的正则化没有改善它在这里的表现）。表 18.3 展示了它的结果。它比最近收缩中心分类器的表现差一些。
如上所述，表 18.3 第一行代表了最近收缩中心方法（无收缩）。令 $s_j$ 代表特征变量 $j$ 的混合组内（within-class）标准差，$s_0$ 代表 $s_j$ 取值的中位数。则在预先把每个特征用 $s_j+s_0$ 进行标准化后，第一行也对应着最近中心点（nearest centroid）分类方法（参考 652 页的式 18.4）。
从第三行可见最近中心点（nearest medoid）方法的表现很差，这出乎了我们的意料。这可能是因为样本量比较小而维度比较高，中心点的方差就要比均值大很多。一最近邻分类器的表现也比较差。
表 18.3 第五行也展示了最近中心点（nearest centroid）分类器的结果：它比最近中心点（nearest medoid）好一些，但比最近收缩中心差一些，即使并没有收缩。它们的区别可能是来自在最近收缩中心方法中对每个特征进行的标准化操作。此例子中这个标准化操作很关键，而它需要基于每个特征变量的取值。最近中心点（nearest centroid）使用了球面的距离度量，从而依赖于所有特征变量都使用了相似的测量单位。支持向量机是对特征的线性组合进行估计，所以能更好地处理非标准化特征变量的问题。
本节练习
练习 18.14
Distance weighted 1-NN classification.
Consider the 1-nearestneighbor method (Section 13.3) in a two-class classification problem. Let $d_+(x_0)$ be the shortest distance to a training observation in class +1, and likewise $d_−(x_0)$ the shortest distance for class −1. Let N− be the number of samples in class −1, N+ the number in class +1, and N = N− + N+.
- Show that $$\delta(x_0) = \log \frac{d_-(x_0)}{d_+(x_0)} \tag{18.57}$$ can be viewed as a nonparametric discriminant function corresponding to 1-NN classification. [Hint: Show that $\hat{f}_+(x_0)=\frac{1}{N_+d_+(x_0)}$ can be viewed as a nonparametric estimate of the density in class +1 at x0].
- How would you modify this function to introduce class prior probabilities π+ and π− different from the sample-priors N+/N and N−/N?
- How would you generalize this approach for K-NN classification?
练习 18.15
Kernel PCA
In Section 18.5.2 we show how to compute the principal component variables Z from an uncentered inner-product matrix K. We compute the eigen-decomposition (I − M)K(I − M) = UD 2 U T , with M = 11 T /N , and then Z = UD. Suppose we have the inner-productExercises vector k 0 , containing the N inner-products between a new point x 0 and each of the x i in our training set. Show that the (centered) projections of x 0 onto the principal-component directions are given by
$$\mathbf{z}_0 = \mathbf{D}^{-1}\mathbf{U}^T (\mathbf{I} - \mathbf{M}) [\mathbf{k}_0 - \mathbf{K}\mathbf{1} / N] \tag{18.58}$$-
原文脚注 4：我们感谢 Christina Leslie 的帮助和提供的数据，数据可从本书的网站获取。 ↩︎