5.9.1 运动连续性AP与标准AP性能比较
1.主观评价
选取连续7帧的药液图像对异物目标进行识别，在实验室中涉及的一些参数初始化如下：a=1.5，λ=0.9，tmax=1000，tconv=100，δ=2.5。如图5.65所示，给出了5个不同的药液序列的聚类结果。左边一列是连续7帧图像提取到的目标累积图，其中同一种颜色标记的目标来自同一帧图像，图中共用7种不同的灰度分别代表来自7帧图像的目标；中间一列是采用标准AP算法进行聚类的结果，右边一列是采用运动连续性AP算法进行聚类的结果。其中，聚类结果图中的序号表示类标号，为了方便辨别，属于同一聚类的目标统一采用相同的灰度进行标记，细线箭头指向的是该类的最佳类代表点。对比结果可以看出，只有当异物目标之间的运动轨迹相隔比较远时，标准AP聚类才能得到比较好的分类结果。如果不同的运动轨迹相近甚至重叠时，为了使数据集内部相似度平方误差最小化，标准AP算法就会打破原本属于同一运动轨迹的数据，形成类似团簇形成的聚类。然而，改进后的运动连续性AP聚类就能维持数据集原本的自然形态，得到正确的分类结果。这是因为测地距离比欧式距离更能反映出数据集内部的拓扑结果，并且新的模型结构和约束方程能够促使AP按照运动轨迹形成的方式进行聚类。
图5.65 标准AP与运动连续性AP(MCAP)聚类结果对比
聚类图像应该是由来自不同帧图像中的目标组成。计算每个聚类内部相邻帧数据的相似度之和S，然后统计7 0 0个不同药液序列的聚类结果，如图5.6 6所示。从图中可以明显观察到，MCA P聚类得到的相似度之和分布比较集中，且主要集中在中上部，这说明MCA P形成的聚类内部比较紧凑。偶尔出现散落在底部的聚类是因为MCAP将一些随机噪声点划分到同一类中，由于噪声点位置的无规律性，导致它们内部的相似度之和过大。和MCAP相比，标准AP形成聚类的相似度之和分布比较散乱，在相似度之和的各个区间都有较多的分布，这是因为AP在欧式距离和没有运动连续性约束的情况下，倾向于形成团簇结构，这就导致了聚类相似度之和的波动性。另外，在MCAP中有很多相似度之和为0的结果，这是因为MCAP将孤立的噪声点单独划分为一类，而AP通常不会得到这样的结果。
图5.66 AP与MCAP相似度之和分布对比
2.客观评价
为了更加客观地评价算法，采用归一化互信息[77](Normalized Mutual Information，NMI)和分类正确率(Classification Rate，CR)来衡量运动连续性AP算法的性能，这两个指标都能反映算法分类结果与正确分类结果的匹配程度。
(1)归一化互信息
给定一个大小为N 的待分类数据集，得到聚类标签为π的c个聚类，正确的分类结果是标签为ξ的c⌒个聚类。首先建立混淆矩阵，在(i，j)上的元素
表示本来属于第j类却被错误分到第i类的数据个数。那么归一化互信息NMI就可以计算如下：
其中，H(π)和H(ξ)分别是聚类π和正确分类ξ的香农熵，计算公式为：(https://www.daowen.com)
其中，ni表示聚类结果中属于第i类的数据个数，n(j)表示正确分类结果中属于第j 类的数据个数。NMI 的值越大，说明聚类结果和正确分类结果越相近。
(2)分类正确率
分类正确率作为一个衡量聚类结果好坏的外部准则，其定义形式相对而言比较直观：
其中，N 是待分类数据集的大小，nc是分类正确的数据个数。CR越大，说明聚类结果与真实情况越接近。
本节对100个不同药液图像序列进行试验，计算每个分类结果的归一化互信息NMI和分类正确率CR，结果如图5.67所示。从图中可以看出，无论是归一化互信息NMI还是分类正确率CR，和AP相比，MCAP都能得到更加准确和稳定的分类结果。
在修正测地距离的过程中，参数δ用来决定需要截取的路径的长短。参数δ的取值对MCAP生成聚类的结果也会产生影响，适合的参数δ将大大提高聚类质量和迭代的收敛速度。本节通过对100个不同药液图像序列进行试验，得到了归一化互信息NMI和分类正确率CR在参数δ不同取值情况下的均值，如图5.68所示，δ的取值范围是0.5～2.0。观察可以发现，当δ的值过小时，MCAP的聚类质量比较差。这是因为，数据点之间很多不需要修正的距离被截去(δ的值过小)，导致了很多数据点之间的相似度被赋为无穷小值，所以无法得到正确的聚类结果。当参数δ的取值超过1时，MCAP的聚类效果也会越来越好，当δ=1.3时，各项指标达到最好。随着δ值的增加，聚类质量虽有下降但是最终趋于稳定。这是因为，当参数δ取值最优时，修正后的测地距离可以促进MCAP生成又快又好的聚类，当参数δ的取值越来越大时，其发挥的作用也就越来越不明显，最终MCAP会在自身约束方程的作用下生成聚类结果。
图5.67 AP与MCAP归一化互信息与分类正确率对比
(a)归一化互信息对比；(b)分类正确率对比
图5.68 AP与MCAP归一化互信息与分类正确率随δ的变化情况
(a)归一化互信息对比；(b)分类正确率对比
