模式识别与机器学习(三)

最大最小距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后续的算法过程中就不再改变了，而简单聚类算法中类心一旦选定后，在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。

为解决该问题，可以采用动态聚类法: 使用动态聚类法的要点：

1. 确定模式和聚类的距离测度。当采用欧式距离时，是计算此模式和该类中心的欧式距离；为能反映出类的模式分布结构，可采用马氏距离。
2. 确定评估聚类质量的准则函数。
3. 确定模式划分以及聚类合并或分裂的规则。

基本步骤：

1. 建立初始聚类中心，进行初始聚类
2. 计算模式和类的距离，调整模式的类别
3. 计算各聚类的参数，删除、合并或分裂一些聚类
4. 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止

C-均值法

1. 条件及约定 设待分类的模式特征矢量集为：{\(\vec x_1, \vec x_2,...,\vec x_N\)}，类的数目C是事先取定的。
2. 算法思想 该方法取定C个类别和选取C个初始聚类中心，按最小距离原则将各模式分配到C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方和最小。
3. 算法原理步骤

(1) 任选C个模式特征矢量作为初始聚类中心： \(\vec z_1^{(0)}, \vec z_2^{(0)},...,\vec z_C^{(0)}\)，令\(k = 0\)。

(2) 将待分类的模式特征矢量集{\(\vec x_i\)}中的模式逐个按最小距离原则分划给C类中的某一类，于是产生了新的聚类。

(3) 计算重新分类后的各类心

(4) 如果两次类心重合，则停止迭代，否则转至(2)

C均值算法的分类结果受到取定的类别数和初始聚类中心的影响，通常结果只是局部最优的，但其方法简单，结果尚令人满意，故应用较多。

C均值算法优化 类别数C的调整

• 利用先验知识选取
• 让类别数递增重复进行聚类，选取\(J-c\)曲线曲率变化最大点所对应的类数(\(J\)为准则函数)

初始聚类中心的选取可采用的方式

• 凭经验选取
• 将模式随机分为C类计算每类类心
• 按密度大小选取
• 选取相距最远的C个特征点
• 随机地从N个模式中取出部分用谱系聚类法聚成C类，以各类类心作为初始类心
• 由C-1类问题得出C-1个类心，再找出最远点

进一步的动态聚类可以采用ISODATA算法，其基本思想是每轮迭代时，样本重新调整类别之后，计算类内及类间有关参数，通过和门限比较确定两类的合并或分裂，不断地“自组织”，在满足设计参数条件下，使模式到类心的距离平方和最小。

C均值算法较适用于球状或团状分布的样本。如果我们有类的模式分布的某些先验知识，可以构造能反映类的模式分布情况的核函数，那么就以和函数来代表类。如果实际中不能确定核函数或不能用简单的函数表示核函数时，可以采用近邻函数法。这种算法特别适用于类的模式分布是条状或线状的情况

类的各种线状分布

近邻函数法 近邻函数 对于一个样本集中的任意两个样本\(\vec x_i\)核\(\vec x_j\)，如果\(\vec x_i\)是\(\vec x_j\)的第I个近邻点，则定义\(\vec x_i\)对\(\vec x_j\)的近邻系数为I，记为\(d(i ,j) = I\) 同理，如果\(\vec x_j\)是\(\vec x_i\)的第J个近邻点，则定义\(\vec x_j\)对\(\vec x_i\)的近邻系数为J，记为\(d(j, i) = J\) 于是，\(\vec x_i\)核\(\vec x_j\)之间的近邻函数值定义为 \[ \alpha_{ij} = d(i,j) + d(j,i) - 2 = I + J - 2 \]

当\(\vec x_i\)核\(\vec x_j\)互为最近邻时，有\(\alpha_{ij} = 0\) 显然，样本间的近邻函数值越小，说明它们彼此越近，意味着它们越相似。

如果样本集包含N个样本，那么近邻系数总是小于或等于N-1，因此，\(\vec x_i\)核\(\vec x_j\)之间的近邻函数值满足 \[ \alpha_{ij} \leq 2N - 4 \]

连接损失 在聚类过程中，如果\(\vec x_i\)核\(\vec x_j\)被聚为一类，就称\(\vec x_i\)与\(\vec x_j\)是互相连接的。 对于每个连接，都应定义一个指标，用以刻划这两个样本是否适于连接，称其为连接损失。 由两个样本的近邻函数值\(\alpha_{ij}\)的定义可知，\(\alpha_{ij}\)越小，表明它们越相似。若把它们连接起来，损失也就越小。因此可以将近邻函数值\(\alpha_{ij}\)作为\(\vec x_i\)和\(\vec x_j\)之间的连接损失。

在聚类过程中，当考虑样本\(\vec x_i\)时，计算它与其它各样本间的近邻函数值，如果 \[ \alpha_{ik} = min_j \lfloor \alpha_{ij} \rfloor \] 则把\(\vec x_i\)和\(\vec x_k\)连接起来，并有连接损失\(\alpha_{ik}\)

若把\(\vec x_i\)与\(\vec x_j\)不实际连接，则不存在连接损失，即 \[ \alpha_{ij} \triangleq 0 \]

近邻聚类准则函数 在定义了两样本间的连接损失之后，还要区分出类内连接损失和类间连接损失。 设共有c类：\(w(p = 1,2,...,c)\)，总的类内连接损失定义为: \[ L_w = \sum^c_{p=1} \sum_{\vec x_i \in w_p \ \\ \vec x_j \in w_p} \lfloor \alpha_{ij} \rfloor \] 记\(w_j\)类的类内最大近邻函数值： \[ \alpha_{p max} = max_{\vec x_i \in w_p \ \\ \vec x_j \in w_p} \lfloor \alpha_{ij} \rfloor \]

设聚类\(w_p\)和\(w_q (p,q=1,2,3,....,c;p \neq q)\)的样本之间的最小近邻函数值为\(\gamma_{pq}\)，即 \[ \gamma_{pq} = min_{\vec x_i \in w_p \ \\ \vec x_j \in w_q} \lfloor a_{ij} \rfloor \] 设\(\gamma_{pk}\)为聚类\(w_p\)与其它各聚类\(w_q\)的最小近邻函数值的最小值，即 \[ \gamma_{pk} = min_{q \ \\ q \neq p} \lfloor \gamma_{pq} \rfloor \] 上式表明，除\(w_p\)类内样本外，只有\(w_k\)中的某一个样本与\(w_p\)中某一个样本最近邻，近邻函数值为\(\gamma_{pk}\)

\(w_p\)类与\(w_k\)类的类间最小连接损失有如下四种情况

1. \(\Beta_p = (\alpha_{p\ max} - \gamma_{pk}) + (\alpha_{k \ max} - \gamma_{pk})\), 若$\gamma_{pk} > \alpha_{p max} and \gamma_{pk} > \alpha_{k max} $ 该情况：类内最大近邻函数值小于类间最小近邻值，说明聚类是合理的，这种情况不应付出代价，\(\Beta_p\) 可赋予负值，即损失函数为负数
2. \(\Beta_p = \alpha_{p\ max} - \gamma_{pk}\)，若\(\gamma_{pk} \leq \alpha_{p\ max} \ and\ \alpha_{pk} > \alpha_{k\ max}\) 该情况下：\(w_p\)类的类内最大近邻函数值大于类间最小近邻值，说明这两类合并应付出代价，\(\Beta_p\)赋予一个正值，即损失为\(\alpha_{p\ max} - \gamma_{pk}\)
3. \(\Beta_p = \alpha_{k\ max} - \gamma_{pk}\)，若\(\gamma_{pk} > \alpha_{p\ max} \ and\ \alpha_{pk} \leq \alpha_{k\ max}\) 该情况下：\(w_p\)类的类内最大近邻函数值大于类间最小近邻值，说明这两类合并也应付出代价，\(\Beta_p\)赋予一个正值，即损失为\(\alpha_{k\ max} - \gamma_{pk}\)
4. \(\Beta_p = \alpha_{p\ max} + (\alpha_{k \ max} - \gamma_{pk})\), 若$\gamma_{pk} \leq \alpha_{p max} and \gamma_{pk} \leq \alpha_{k max} $ 该情况：\(w_p\)和\(w_k\)类内的类内最大近邻函数值都大于类间最小近邻值，说明这两类合并应付出的代价更大，\(\Beta_p\)赋予连接损失为\(\alpha_{p\ max} + (\alpha_{k \ max} - \gamma_{pk})\)

然后，我们可以定义总的类间损失：\(L_B = \sum_{p=I}^c \Beta_p\)。 聚类的目标是使各\(\gamma_{pk}\)尽可能地大，使各\(\alpha_{p\ max}\)尽可能地小，因而构造聚类的准则函数为 \[ J_L = L_W + L_B \Rightarrow min \]

近邻函数法算法步骤

(1) 对于给定的待分类样集$x = $ { $ \vec x_1, \vec x_2, ..., \vec x_N $ }，计算距离矩阵D，D的阵元为：\(D_{ij} = d(\vec x_i, \vec x_j) (i,j=1,2,...,N)\)，\(d(\vec x_i, \vec x_j)\)表示样本\(\vec x_i\)和\(\vec x_j\)间的距离。

(2) 利用矩阵D，计算近邻矩阵M，其元素\(M_{ij}\)为样本\(\vec x_i\)对\(\vec x_j\)的近邻系数

(3) 生成近邻函数矩阵L,其阵元为\(L_{ij}=M_{ij}+M_{ji}-2\)，置矩阵L的主对角线上阵元\(L_{ii}=2N\)，如果\(\vec x_i\)和\(\vec x_j\)有连接，则\(L_{ij}\)给出它们非零近邻函数值，即连接损失

(4) 搜索矩阵L，将每个点与和它有最小近邻函数值的点连接起来，形成初始聚类

(5) 对于(4)所形成的聚类，计算\(\gamma_{pk},\alpha_{pw},\alpha_{kw}\)。若\(\gamma_{pk}\)小于或等于\(\alpha_{pw}\)或\(\alpha_{kw}\)，则合并\(w_k\)和\(w_p\)，它们的样本间建立连接关系，转至(5)，否则结束

上述迭代过程，最终将使准则函数\(J_L\)达到极小值。

注：对于链状的模式分布，合并后的类内最大连接损失不应重新计算，而是取\(\alpha_1\ max, \alpha_2\ max, \gamma_{12}\)的最大值

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=28uqs0ghrj0g0