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

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

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

确定模式和聚类的距离测度。当采用欧式距离时,是计算此模式和该类中心的欧式距离;为能反映出类的模式分布结构,可采用马氏距离。

确定评估聚类质量的准则函数。

确定模式划分以及聚类合并或分裂的规则。

基本步骤:

建立初始聚类中心,进行初始聚类

计算模式和类的距离,调整模式的类别

计算各聚类的参数,删除、合并或分裂一些聚类

从初始聚类开始,运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止

C-均值法

条件及约定
设待分类的模式特征矢量集为:{\(\vec x_1, \vec x_2,...,\vec x_N\)},类的数目C是事先取定的。

算法思想
该方法取定C个类别和选取C个初始聚类中心,按最小距离原则将各模式分配到C类中的某一类,之后不断地计算类心和调整各模式的类别,最终使各模式到其判属类别中心的距离平方和最小。

算法原理步骤

(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\)之间的连接损失。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wspfsd.html