注意这里的 fff 是 Sigmoid 函数。令 gj=y^jk(1−y^jk)(yjk−y^jk)g_{j} = \hat{y}_j^{k} (1-\hat{y}_j^{k}) (y_{j}^{k} - \hat{y}_{j}^{k} )gj=y^jk(1−y^jk)(yjk−y^jk) 。将 gjg_{j}gj 和式 (5.8)(5.8)(5.8) 带入式 (5.6)(5.6)(5.6)，就得到了 BP 算法中关于 whjw_{hj}whj 的更新公式：
Δwhj=ηgjbh(5.11)\Delta w_{hj} = \eta g_{j}b_{h} \tag{5.11}Δwhj=ηgjbh(5.11)
类似式 (5.10)(5.10)(5.10) 的推导过程可得其他参数的更新公式：
Δθj=−ηgj(5.12)\Delta \theta_j = -\eta g_j \tag{5.12}Δθj=−ηgj(5.12)
Δvih=−ηehxi(5.13)\Delta v_{ih} = -\eta e_{h}x_{i} \tag{5.13}Δvih=−ηehxi(5.13)
Δθj=−ηeh(5.14)\Delta \theta_j = -\eta e_h \tag{5.14}Δθj=−ηeh(5.14)
vihv_{ih}vih 梯度的详细推导公式如下所示。因为，
所以
Δvih=−η∂Ek∂vih=ηehxi\Delta v_{ih} =-\eta \cfrac{\partial E_k}{\partial v_{ih}} =\eta e_h x_iΔvih=−η∂vih∂Ek=ηehxi
最后一层激活使用
softmax激活和交叉熵损失函数的反向传播推导，可参考这里。 最后一层激活使用sigmoid激活和交叉熵损失函数的反向传播推导，可参考这里。
学习率 η∈(0,1)\eta \in (0,1)η∈(0,1) 控制着算法每一轮迭代中更新的步长，若太大则容易振荡，太小则收敛速度幽会过慢。有时为了做精细调节，可令式(5.11)(5.11)(5.11)与(5.12)(5.12)(5.12)使用 η1\eta_1η1， 式(5.13)(5.13)(5.13)与(5.14)(5.14)(5.14)使用 η2\eta_2η2，两者未必相等。
下图给出了 BP 算法的工作流程：
对每个训练样本，BP 算法操作流程如下：
- 前向传播:将输入样本输入给输入神经元，然后逐层将信号前向传播，直到输出层产生结果。
- 反向传播：计算输出层的误差，沿着输出层到输入层的顺序，依次计算并存储损失函数有关各层的中间变量及参数梯度，并对参数进行调整。
1，2过程循环进行，直到达到某些停止条件为止，如训练误差已达到一个很小的值。
停止条件与缓解
BP过拟合的策略有关。
值得注意的是，BP 算法的目标是要最小化训练集 DDD 上的累计误差：
E=1m∑k=1mEk，(5.16)E = \frac{1}{m}\sum_{k=1}{m}E_k，\tag{5.16}E=m1k=1∑mEk，(5.16)
但是我们前面描述的“标准 BP 算法”的计算过程，其实每次仅针对一个训练样本更新连接权重和阈值的，因此，图5.8中算法发更新规则同样也是基于单个 EkE_kEk 推导而得的。如果类似地推导出基于累计误差最小化的更新规则，就得到了累计误差反向传播（accumulated error backpropagation）算法。
一般来说，标准 BP 算法每次更新仅针对单个样本，参数更新很频繁，而且不同样本对进行更新的效果可能出现“抵消”现象。因此，为了达到同样的累计误差极小点，标准 BP 算法往往需要进行更多次数的迭代。而累计 BP 算法直接将累计误差最小化，它是在读取整个训练集 DDD 一遍（one epoch）后才对神经网络各层权重参数进行更新，其参数更新频率低得多。但是在很多任务中，累计误差下降到一定程度后，进一步下降会非常缓慢，这是标准 BP 往往会更快获得较好的解，尤其是在训练集 DDD 非常大时很明显。
标准 BP 算法和累计 BP 算法的区别类似于随机梯度下降（stochastic gradient descent，简称 SGD）与标准梯度下降之间的区别。
[Hornik et al.,1989] 证明，只需一个包含足够多神经元的隐层（即深度神经网络层数足够多），多层前馈神经网络就能以任意精度逼近任意复杂度的连续函数。但是，深度神经网络层数的选择依然是一个未决问题，在实际应用中通常依靠“试错法”（trial-by-error）调整。
因为神经网络的表示能力太过强大，因此 BP 神经网络在训练过程中经常遭遇过拟合，即训练误差持续降低，但验证集误差却可能上升。目前常用来缓解 BP 网络过拟合问题的策略，有以下两种：
第一种策略是“早停”（early stopping）:将数据分为训练集和验证集，训练集用来更新权重参数，验证集用来估计误差，若训练集误差降低但验证集误差升高，则停止训练，同时返回具有最小验证集误差的权重参数模型。
第二种策略是“正则化”（regulazation）：其基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分，例如连接权重与阈值的平方和。仍令 EkE_kEk 表示第 kkk 个训练样本上的误差，wiw_iwi表示连接权重和阈值，则误差目标函数(5.16)(5.16)(5.16)更改为：
E=λ1m∑kmEk+(1−λ)∑iwi2(5.17)E = \lambda \frac{1}{m}\sum_k^m E_k + (1- \lambda)\sum_{i} w_i^2 \tag{5.17}E=λm1k∑mEk+(1−λ)i∑wi2(5.17)
其中 λ∈(0,1)\lambda \in (0,1)λ∈(0,1)用于对经验误差与网络复杂度这两项进行折中，常通过交叉验证法估计。
常用的刻画模型复杂度 R(w)R(w)R(w) 的函数有两种，一种是 L1L1L1 正则化，即绝对值的之和；另一种是 L2L2L2 正则化，即绝对值平方之和，计算公式如下：
R(w)=∣∣w∣∣1=∑i∣wi∣R(w)=∣∣w∣∣2=∑i∣wi2∣R(w) = ||w||_1 = \sum_i|w_i| \\ R(w) = ||w||_2 = \sum_i|w_i^2|R(w)=∣∣w∣∣1=i∑∣wi∣R(w)=∣∣w∣∣2=i∑∣wi2∣
无论是哪一种正则化，其基本思想都是希望通过限制权重的大小，使得模型不能任意拟合训练数据中随机噪声。L1L1L1 与 L2L2L2 有很大区别，L1L1L1 正则化会让参数变得更加稀疏，而 L2L2L2 不会。所谓参数变得更加稀疏是指会有更多的参数变为 0，这样可以达到类似特征选取的功能。
L2范数正则化（regularization）等价于权重衰减的概念。
5.4 全局最小与局部最小
若用 EEE 表示神经网络在训练集上的误差，则它显然是关于连接权重 www 和阈值 θ\thetaθ 的函数。此使，神经网络的训练过程可看作是一个参数寻优的过程，即在参数空间中，寻找一组最优参数使得 EEE 最小。
显然，参数空间内梯度为零的点，只要其误差函数值小于零点的误差函数值，就是局部极小点；可能存在多个局部极小值，但有且仅有一个全局最小值。
基于梯度的搜索是使用最为广泛的参数寻优方法。在这类方法中，一般先从参数随机初始解出发，迭代寻找最优参数解。每次迭代我们先计算误差函数在当前点的梯度，然后根据梯度确定搜索方向。例如，由于负梯度方向是函数值下降最快的方向，因此梯度下降法就是沿着负梯度方向搜索最优解。若误差函数在当前点的梯度为零，则已达到局部极小，参数更新量也将为零，也意味着参数的迭代更新将在此停止。
在现实任务中，我们常用以下启发式策略（非理论策略）来试图“跳出”局部极小，从而进一步接近全局最小：
- 以多组不同参数值初始化多个神经网络，按标准方法训练后，取其中最小的解作为最终参数。
- 使用”模拟退火“（
simulated annealing）技术。模拟退火在每一步都以一定的概率接受比当前解更差的结果，从而有助于”跳出“局部极小。在每次迭代过程中，接收”次优解“的概率要随着时间的推移而逐渐降低，从而保证算法的稳定性。 - 使用随机梯度下降算法。
5.5 其他常见神经网络
2010 年之前常见的神经网络有 RBF 网络、ART 网络、SOM 网络、级联相关网络、Elman网络、Boltzmann 机。
5.6 深度学习
典型的深度学习模型就是很深层（层数很多）的神经网络。值得注意的是，从增加模型复杂度的角度来看，增加隐藏层的数目显然比增加隐藏层神经元的数目更有效，即网络的“深”比“宽”重要。因为隐藏层层数的增加不仅增加了拥有激活函数神经元的数目，还增加了激活函数嵌套的层数，即非线性能力进一步增强。
第 9 章 聚类
9.1 聚类任务
在“无监督学习”中，训练样本是无标签信息的，目标是通过对无标记训练样本的学习来揭示数据的内在性质和规律，为进一步的数据分析提供基础。这类学习任务中应用最广的就是“聚类”（clustering）算法，其他的无监督学习任务还有密度估计（density estimation）、异常检测（anomaly detection）等。
聚类的任务是将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”（cluster），簇所对应的概念和语义由使用者来把握。
聚类可用作其他学习任务的一个前驱过程。基于不同的学习策略，有着多种类型的聚类算法，聚类算法涉及的两个基本问题是性能度量和距离计算。
9.2 性能度量
聚类性能度量也叫聚类“有效性指标”（validity index），和监督学习的性能度量作用类似，都是用来评估算法的好坏，同时也是聚类过程中的优化目标。
聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型（reference model）”进行比较，称为“外部指标（external index）”；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”（inderna index）。
外部指标包括 Jaccard 指数（简称 JC）、FM 指数（简称 FMI）和 Rand 指数（简称 RI），范围在 [0,1] 之间，且越大越好；内部指标包括 DB 指数（简称 DBI）和 Dunn 指数（简称 DI），DBI 值越小越好，DI 越大越好。
具体计算公式太多了，这里不给出，可以参考原书
199页。
9.3 距离计算
函数 dist(⋅,⋅)dist(\cdot,\cdot)dist(⋅,⋅) 用于计算两个样本之间的距离，如果它是一个“距离度量”（distance measure），则需满足一些基本性质：
- 非负性：dist(xi,xj)≥0dist(x_i,x_j) \geq 0dist(xi,xj)≥0；
- 同一性：dist(xi,xj)=0dist(x_i,x_j)=0dist(xi,xj)=0 当前仅当 xi=xjx_i = x_jxi=xj；
- 对称性：dist(xi,xj)=dist(xj,xi)dist(x_i,x_j) = dist(x_j,x_i)dist(xi,xj)=dist(xj,xi)；
- 直递性：dist(xi,xj≥dist(xi,xk)+dist(xk,xj))dist(x_i,x_j \geq dist(x_i,x_k) + dist(x_k,x_j))dist(xi,xj≥dist(xi,xk)+dist(xk,xj))。
给定样本 xi=(xi1;xi2;...;xin)x_i = (x_{i1};x_{i2};...;x_{in})xi=(xi1;xi2;...;xin) 与 xj=(xj1;xj2;...;xjn)x_j = (x_{j1};x_{j2};...;x_{jn})xj=(xj1;xj2;...;xjn)，最常用的是“闵可夫斯距离”（Minkowski distance）。
distmk(xi,xj)=(∑u=1n∣xiu−xju∣p)1pdist_{mk}(x_i,x_j) = (\sum_{u=1}^{n}\left | x_{iu} - x_{ju} \right |^p)^\frac{1}{p}distmk(xi,xj)=(∑u=1n∣xiu−xju∣p)p1
上式其实就是 xi−xjx_i - x_jxi−xj 的 LpL_pLp 范数 ∥xi−xj∥p\left \| x_i - x_j \right \|_p∥xi−xj∥p。p=2p = 2p=2，上式为欧氏距离。
属性通常划分为“连续属性”（continuous attribute）和“离散属性”（categotical attribute），前者在定义域上有无穷多个可能的取值，后者在定义域上是有限个取值。但是在涉及距离计算时，属性上定义了“序”更为重要。能直接在属性上计算距离：“1” 和 “2” 比较近、和“4”比较远，这样的属性称为“有序属性”（ordinal attribute ）；而定义域为{汽车、人、椅子}这样的离散属性则不能直接在属性上计算距离，称为“无序属性”（non-ordinal atribute）。显然，闵可夫斯距离可用于有序属性。
对无序属性采用 VDM（Value Difference Metric），同时将闵可夫斯距离和 VDM 集合可处理混合属性。
9.4 原型聚类
原型聚类算法假设聚类结构能通过一组原型刻画，这里的原型是指样本空间中具有代表性的点。一般算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。
9.4.1 k 均值算法
K-Means 算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为 KKK 个簇，让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
给定样本集 D={x1,x2,...,xm}D = \{x_1, x_2,...,x_m\}D={x1,x2,...,xm}，假设簇划分为 C={C1,C2,...,Cm}C = \{C_1,C_2,...,C_m\}C={C1,C2,...,Cm}，算法目标是最小化平方误差。
E=∑i=1k∑x∈Ci∥x−ui∥22E = \sum_{i=1}^{k}\sum_{x \in C_{i}}\left \| x - u_i \right \|_2^2E=∑i=1k∑x∈Ci∥x−ui∥22
其中 ui=1Ci∑x∈Cixu_i=\frac{1}{C_i}\sum_{x \in C_{i}}xui=Ci1∑x∈Cix 是簇 CiC_iCi 的均值向量，也称质心。上式一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，EEE 值越小簇内样本相似程度越高。
找到 EEE 的最优解需要靠擦样本集 DDD 所有可能的簇划分，这是一个 NPNPNP 难问题。kkk 均值算法采用了贪心策略，通过迭代优化近似求解，算法流程如图 9.2 所示。其中第 1 行对均值向量进行初始化，4-8 行与 9-16 行依次对当前簇划分即均值向量迭代更新，若更新后聚类结果保持不变，则在第 18 行将当前簇划分结果返回。
参考此文章的代码，我修改为如下精简版的 K-Means 算法代码。
def kmeans(dataset, k): """K-means 聚类算法 Args: dataset ([ndarray]): 数据集，二维数组 k ([int]): 聚簇数量 """ m = np.shape(dataset)[0] # 样本个数 # 1, 随机初始化聚类中心点 center_indexs = random.sample(range(m), k) center = dataset[center_indexs,:] cluster_assessment = np.zeros((m, 2)) cluster_assessment[:, 0] = -1 # 将所有的类别置为 -1 cluster_changed = True while cluster_changed: cluster_changed = False # 4-8，计算样本x_i与各聚类中心的距离，根据距离最近的聚类中心确定x_j的簇标记，并将对应样本x_i划入相应的簇 for i in range(m): # 初始化样本和聚类中心的距离，及样本对应簇 min_dist = inf c = 0 # 确定每一个样本离哪个中心点最近，和属于哪一簇 for j in range(k): dist = distEclud(dataset[i,:], center[j,:]) if dist < min_dist: min_dist = dist c = i # 更新样本所属簇 if cluster_assessment[i, 0] != c: # 仍存在数据在前后两次计算中有类别的变动，未达到迭代停止要求 cluster_assessment[i, :] = c, min_dist # 更新样本所属簇 cluster_changed = True # 9-16 更新簇中心点位置 for j in range(k): changed_center = dataset[cluster_assessment[:,0] == j].mean(axis=0) center[j,:] = changed_center return cluster_assessment, center if __name__ == '__main__': x1 = np.random.randint(0, 50, (50, 2)) x2 = np.random.randint(40, 100, (50, 2)) x3 = np.random.randint(90, 120, (50, 2)) x4 = np.random.randint(110, 160, (50, 2)) test = np.vstack((x1, x2, x3, x4)) # 对特征进行聚类 result, center = kmeans(test, 4, is_kmeans=False, is_random=False) print(center) # 打印簇类中心点 复制代码
参考资料
《机器学习》-周志华
