这个方法可被看作是一个有约束版本的 K 均值聚类，其中尽可能使原型点位于一个特征空间上的一维或二维的流形（manifold）上。因为原始高维的观测样本可以被映射到二维的坐标系中，这个产生的流形也被称为一个 有约束拓扑映射（constrained topological map）。原本自组织映射（self-organizing map）算法是一个在线算法，即对观测样本是一个个地进行处理的；之后出现了批处理的版本。这个方法也与下一节中介绍的主曲线和主曲面存在紧密的关系。
我们考虑一个二维方形网格（可能使用其他的选择，例如六边形网格）的 $K$ 个原型点 $m_j\in\mathbb{R}^p$ 的自组织映射。$K$ 个原型点的每一个都根据一对整数坐标进行参数化，$\ell_j\in\mathcal{Q}_1\times\mathcal{Q}_2$。其中 $\mathcal{Q}_1=\{1,2,\dots,q_1\}$，$\mathcal{Q}_2$ 的定义类似，并且 $K=q_1\cdot q_2$。举例而言，将 $m_j$ 初始化在样本的一个二维主成分平面上（见下一节）。我们可以想象这些原型点是被按找一个常规模式“缝”在主成分平面上的一些“纽扣”。自组织映射方法是在弯曲这个平面，从而使这些“纽扣”尽可能地接近样本点。模型拟合好后，观测样本点可被映射到这个二维网格上。
每次会处理一个观测样本点 $x_i$。我们找到在 $\mathbb{R}^p$ 上与 $x_j$ 欧式距离最近的原型点 $m_j$，然后将 $m_j$ 的所有邻域原型点 $m_k$ 向 $x_i$ 的方向按下式的更新进行移动：
$$m_k \leftarrow m_k + \alpha (x_i - m_k)\tag{14.46}$$$m_j$ 的领域是所有的 $\ell_j$ 和 $\ell_k$ 之间距离较小的 $m_k$ 点。最简单的方法是使用欧式距离，以及用一个阈值 $r$ 来定义“较小”。这个邻域总会包括了最近的原型点 $m_j$ 本身。
请注意这里的距离是定义在原型点的整数拓扑坐标系空间 $\mathcal{Q}_1\times\mathcal{Q}_2$ 上的，而不是在特征空间 $\mathbb{R}^p$ 上。更新步骤（式 14.46）的效果是将原型点向接近数据的方向移动，但也同时保持了原型点之间的一个平滑的二维空间关系。
自组织映射算法的表现依赖于学习率 $\alpha$ 和距离阈值 $r$。通常 $\alpha$ 会在几千次迭代（每次一个观测样本）中从 1.0 降低至 0.0。阈值类似，$r$ 会在几千次迭代中从起始值 $R$ 线性地下降到 1。在下面的示例中我们会演示选取 $R$ 的方法。
以上介绍的是最简单版本的自组织映射。更复杂的版本会根据距离来修改更新步骤：
$$mk \leftarrow m_k + \alpha h(\|\ell_j - \ell_k\|)(x_i - m_k) \tag{14.47}$$其中的 邻域函数（neighborhood function） $h$ 为索引坐标 $\ell_k$ 距离 $\ell_j$ 更近的原型点 $m_k$ 赋予更高的权重。
如果我们使用一个足够小的距离 $r$，以至于每个邻域中只包含一个原型点，那么原型点之间的空间关系就失去了意义。这时可证明自组织映射算法就是一个在线版本的 K 均值聚类，并最终会稳定在由 K 均值得出的一个局部最优处。由于自组织映射是一个有约束版本的 K 均值聚类，所以在每个问题中对这个约束的合理性检验是很重要的。可以对两个方法计算重构误差（reconstruction error）$\|x-m_j\|^2$ 在样本上的求和。K 均值的必然会比自组织映射的更小一些，但如果后者是一个合理的近似，这个差距不会很大。
作为一个演示例子，我们在三维空间上半径为 1 的半球表面附近生成 90 个数据样本点。样本点有三个簇，红色、绿色、和蓝色，分别位于 $(0,1,0)$、$(0,0,1)$、和 $(1,0,0)$ 三个点附近。图 14.15 展示了这些数据。
按（数据模拟）设计红色类别要比绿色和蓝色类别分布更紧密。（模拟数据生成的具体细节在练习 14.5。）使用了 $5\times5$ 网格的原型点，初始的网格（邻域）大小为 $R=2$；这意味着初始化时大概有三分之一的原型点出现在每个邻域中。我们对 90 个观测样本的数据集进行了共 40 次遍历，并且令 $r$ 和 $\alpha$ 在这 3600 次迭代中线性地下降。
图 14.16 中，圆圈代表着原型点，映射到每个原型点的数据点被随机地画在相应的圆圈中。左图展示了初始时的样子，而右图展示了结束时的样子。
这个算法成功地分离了不同类别；然而被分隔开的红色类别说明了这个流形（manifold）自身折叠了起来（见图 14.17）由于并没有使用到二维展示中的距离，在自组织映射的映射结果中无法看出红色类别要比其他两个类别更紧凑。
图 14.18 展示了重构误差，即每个数据样本点与其原型点的误差平方和。作为对比，我们也进行了 25 个中心点 K 均值聚类，图中水平线代表了它的重构误差。可见自组织映射显著地降低了误差，几乎到了 K 均值聚类解的水平。这说明了在这个特定的数据集上自组织映射使用的二维约束条件是合理的。
在批处理版本的自组织映射中，按下式更新每个 $m_j$：
$$m_j = \frac{\sum w_k x_k}{w_k} \tag{14.48}$$其中的求和是对所有映射到（距离最近）$m_j$ 的邻域点 $m_k$ 上的样本点 $x_k$。权重函数可以是方形的，即只在 $m_j$ 的邻域上为 1，或者可以和之前那样随距离 $\|\ell_k-\ell_j\|$ 平滑递减的。如果邻域的大小选择得足够小，以至于其中只有 $m_j$ 自己，并且使用方形权重函数，则这就变成了之前介绍过的 K 均值聚类。自组织映射也可以被理解为第 14.5 节介绍的主曲线和主曲面的离散版本。
例：文档的组织和获取
随着互联网的快速发展，文档检索越来越重要，自组织映射在组织和索引大型全文库中被验证过是有效的。 这个例子来自 WEBSOM 的首页 http://websom.hut.fi/[^1] (Kohonen et al., 2000)。
图 14.19 是新闻组 comp.ai.neural-nets 的 12,088 篇文章进行的自组织映射拟合。标签是由 WEBSOM 软件自动生成的，可作为一个节点中典型内容的导览。
在这样的应用中，需要对文档进行预处理从而创建出特征向量。然后创建一个 术语文档矩阵（term document matrix），其中每行代表了一个文档。每一行中的内容是一个预定义术语集合中每一个的相对频率。这些术语可以是一个字典词条的大集合（50,000 个词），或是二元语言模型（单词对）的甚至更大的集合，或是以上这些的子集。这些矩阵一般非常稀疏，所以通常通过做一些预处理来降低特征（列）的数量。有时会使用奇异值分解（SVD）来为矩阵降维（见下节）；Kohonen et al. (2000) 则使用了一个随机化的变体。然后将这些降维的向量输入到自组织映射模型中。
在这个应用中，作者开发了一个“缩放”功能，可以让用户与映射图进行交互以获得更多细节信息。最后一级的缩放会获取到实际的新闻文章，然后就可以阅读。
本节练习
练习 14.5
生成三个特征变量的样本数据，有三个类别，每个类别中有 30 个数据点，具体如下：
$$\begin{align} \theta_1 &= U(-\pi/8, \pi/8) \\ \phi_1 &= U(0, 2\pi) \\ x_1 &= \sin(\theta_1) \cos(\phi_1) + W_{11} \\ y_1 &= \sin(\theta_1) \sin(\phi_1) + W_{12} \\ z_1 &= \cos(\theta_1) + W_{13} \\ & \\ \theta_2 &= U(\pi/2 - \pi/4, \pi/2 + \pi/4) \\ \phi_2 &= U(-\pi/4, \pi/4) \\ x_2 &= \sin(\theta_2) \cos(\phi_2) + W_{21} \\ y_2 &= \sin(\theta_2) \sin(\phi_2) + W_{22} \\ z_2 &= \cos(\theta_2) + W_{23} \\ & \\ \theta_3 &= U(\pi/2 - \pi/4, \pi/2 + \pi/4) \\ \phi_3 &= U(\pi/2 - \pi/4, \pi/2 + \pi/4) \\ x_3 &= \sin(\theta_3) \cos(\phi_3) + W_{31} \\ y_3 &= \sin(\theta_3) \sin(\phi_3) + W_{32} \\ z_3 &= \cos(\theta_3) + W_{33} \end{align}$$这里 $U(a,b)$ 代表在 $[a,b]$ 上的一个均匀分布随机变量，$W_{jk}$ 为标准差 $0.6$ 的独立正态分布随机变量。因此数据位于一个半球表面附近的三个簇中心点 $(1,0,0)$、$(0,1,0)$、和 $(0,0,1)$ 周围。
编写一个程序来对这些数据进行一个自组织映射模型的拟合，使用文中的学习率。对同样的数据应用一个 K 均值聚类，并且与文中的结果做对比。
练习 14.6
编写程序，实现 K 均值聚类和原型点位于二维网格上的自组织映射。在人类肿瘤微阵列数据（human tumor microarray data）上应用这两个模型，两者的中心点个数都为 $K=2,5,10,20$。随着自组织映射中邻域变得越来越小，演示自组织映射的解变得与 K 均值的解越来越相似。