基于模糊核学习矢量量化的Sammon非线性映射算法

摘要：提出了一种基于可靠稳定的模糊核学习矢量量化（FKLVQ）聚类的Sammon非线性映射新算法。该方法通过Mercer核，将数据空间映射到高维特征空间，并在此特征空间上进行FKLVQ学习获取数据空间有效且稳定的聚类权矢量，然后在特征空间和输出空间上仅针对各空间的数据样本和它们各自的聚类权矢量进行Sammon非线性核映射。这样既降低了计算的复杂度，又使数据空间和输出空间上数据点与聚类中心间的距离信息保持相似。仿真结果验证了该方法的可靠性和稳定性。

关键词：非线性映射；Sammon投影；距离保持性；计算复杂度；模糊核；学习矢量量化

中图分类号：TP311.13

文献标识码：A

0引言

数据降维映射是数据投影、数据挖掘、可视化或聚类分析的基础。然而，当今数据量及其维数的急剧膨胀使得数据降维面临着巨大挑战。由于人眼视觉对二维或三维空间上数据的分布特性有绝佳的分辨能力，所以通过投影将高维空间的数据映射到尽可能保持原空间数据的某种内在关系的低维空间上进行适当的区分和分类是聚类分析的重要途径之一。Sammon映射就是“几何图像降维”投影法，它通过非线性变换，在低维空间上直观、形象地展现原数据间的结构信息，使得人们能够在低维空间上看到一些高维样本点相互关系的近似图像。但是它存在计算复杂度大，对初值的设定较敏感以及易陷入局部极值等缺点[1]。映射初值的优化设定[2]以及满足AGW条件的线性搜索[3]能较好地解决初值敏感性和局部极值问题。本文重点针对计算复杂度较大的缺点进行讨论。混合FCM聚类的Sammon算法[4]能够较好地解决计算复杂度的问题，它的思想是首先通过模糊C均值（Fuzzy CMean, FCM）算法得到各空间的聚类中心，然后在数据空间和输出空间上仅针对各自空间的数据点和它们各自的聚类中心进行Sammon非线性映射，以尽可能地保证两空间数据点的距离相似性，算法对线性可分数据集的映射接近Sammon映射，从而说明算法可行。但是，FCM算法聚类的缺点极易使Sammon映射扭曲低维输出空间的距离信息以及混合FCMSammon算法对许多现实数据集表现出较差的可靠性和推广能力。为此，本文提出一种Sammon非线性映射的新方法――基于模糊核学习矢量量化（Fuzzy Kernel Learning Vector Quantization, FKLVQ）算法，它应用核思想为原数据空间诱导出一类异于欧氏距离度量的新的灵活的距离度量以提高可靠性和推广能力，应用FKLVQ算法以提高聚类中心的有效性和稳定性。

1模糊核学习矢量量化（FKLVQ）算法

由于FCM具有聚类中心的随机初始化导致最终迭代结果的不稳定，权重指数的选择直接影响聚类有效性，数据点模糊隶属各类中心的非独立性导致算法对噪声数据非常敏感以及每一步迭代均需对整个数据集进行计算导致较大计算量等等缺点[5]，所以混合FCM的Sammon算法[4]处理大容量的多维数据难以取得理想的效果。近年来，Karayiannis和Pai提出的模糊学习矢量量化（FLVQ）[6,7]是基于“winnertakemost”竞争策略的随机梯度学习算法，它在一定程度上克服了FCM算法的缺点，但是FLVQ的稳定性受到学习率的影响，必须通过调整学习率来保证算法稳定地收敛，否则学习率过大导致算法不收敛而远离训练集，学习率过小导致算法在初始值附近徘徊。我们发现，FLVQ出现该问题的原因是：每个非获胜端的隶属函数μik均包含获胜端的贡献，使得获胜端对目标函数的贡献扩大到聚类数目c的倍数，所以获胜端码向量的调整随c增加引起发散，这样只能改变初始学习速率以满足算法有效的必要条件，从而保证算法收敛。尽管文献[8]提出了LVQ的一般模型，其定义的隶属函数克服了对c获胜端码向量调整的影响，但是非获胜型端码向量随c的增加其调整量极小，几乎在初值徘徊，所以该学习规则并非符合FLVQ算法的“winnertakemost”竞争策略。另外，这些算法对c较小且线性可分的数据集的聚类能取得满意的效果，但是对c较大或一些线性不可分但非线性可分的数据集却表现出较差的结果。为此，将原FLVQ算法进行改进，把获胜端i*的隶属度函数扩展c倍并结合原空间核的思想，得到模糊核学习矢量量化（FKLVQ）的目标函数的定义：

α的取值与原始Sammon算法的迭代步长一致，通常取│=0.2～0.4。当然，为避免陷入局部极值，也可参考满足AGW条件的线性搜索方法[3]选择最佳α。另外根据上述的分析，基于FKLVQ的Sammon算法每次迭代的计算复杂度和FCM-Sammon算法的计算复杂度均为O(M•c)，远小于Sammon映射的O(M2)。下面给出基于FKLVQ的Sammon非线性映射算法的具体步骤：

3仿真结果

为了比较Sammon算法、基于FCM聚类的Sammon算法以及基于FKLVQ聚类的Sammon算法间性能,分别用2D非线性合成数据样本集和著名的Iris样本集进行测试。其中2D非线性可分数据样本集由满足均匀分布且半径均值分别取1，6，10的随机环形数据组成，各类数据量分别取100。为了定量比较这些算法间的性能，引入表征将输入空间上任一数据点到其邻域内各数据点的距离分别与输出空间上对应的距离相比所得比值分布的偏离方差(RSD)以刻画两空间上数据间距离的相似程度。表2给出了这些算法的RSD值，表3给出了各算法的代价目标函数值E。根据表2的结果，基于FKLVQ的Sammon算法的RSD值与Sammon映射的RSD值接近且表现稳定，但是基于FCM的Sammon算法的RSD值均偏离Sammon映射的RSD值，表现不稳定，此结果证实了基于FKLVQ的Sammon算法的稳定性优于基于FCM的Sammon算法。另外，基于FKLVQ的Sammon算法的 值均稍小于Sammon映射，说明引入核的混合FKLVQSammon算法具有较好的紧致性和可靠性。根据表3，基于FKLVQ的Sammon算法的E值均与Sammon映射的E值接近，但是基于FCM的Sammon算法的E值对初始值的设定较敏感， E值均偏离Sammon映射的E值，表现不够稳定，此结果也证实了基于〖HJ1.73mm〗FKLVQ的Sammon算法在稳定性能上优于基于FCM的Sammon算法。综上所述，基于FKLVQ聚类的Sammon算法是可靠、有效而且比较稳定的。

4结语

针对大容量数据情况下Sammon映射计算复杂度较大以及混合FCMSammon算法的不稳定性，提出了一种基于有效且稳定的FKLVQ聚类的Sammon映射新算法。它继承了混合FCMSammon算法能降低计算复杂度的优点，克服了混合FCMSammon算法结果不稳定的缺点，并应用核思想从原数据空间诱导出一类异于欧氏距离的新的距离度量，提高了算法的可靠性和推广能力。仿真结果在适宜的参数（如σ和β等）下验证了提出算法的有效性和可行性，其性能优于Sammon算法和混合FCM的Sammon算法。因FKLVQ聚类结果对映射极为重要，其参数的选择直接影响到最终的映射性能，所以如何根据FKLVQ的收敛性和稳定性选择较佳参数的问题还有待深入分析。