对角矩阵指数优化的局部保持映射算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　对角矩阵指数优化的局部保持映射算法　安亚静　，王士同　ＡＮ　Ｙａｊｉｎｇ　，ＷＡＮＧ　Ｓｈｉｔｏｎｇ　１．江南大学物联网工程学院，江苏无锡２１４１２２　２．江南大学数字媒体学院，江苏无锡２１４１２２　１．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｔｅｒｎｅｔ　ｏｆ　Ｔｈｉｎｇｓ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ　２１４１２２，Ｃｈｉｎａ　２．Ｓｃｈｏｏｌ　ｏｆ　Ｄｉｇｉｔａｌ　Ｍｅｄｉａ，Ｊｉａｎｇｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ　２１４１２２，Ｃｈｉｎａ　

ＡＮ　Ｙａｊｉｎｇ，ＷＡＮＧ　Ｓｈｉｔｏｎｇ．Ｉｍｐｒｏｖｅｄ　ｌｏｃａｌ　ｐｒｅｓｅｒｖｉｎｇ　ｐｒｏｊｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｅｘｐｏｎｅｎｔｉａｌ　ｄｉａｇｏｎａｌ　ｍａｔｒｉｘ．Ｃｏｍ—　ｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１１，４７（３６）：１９７－２０２．　

Ａｂｓｔｒａｃｔ：Ｌｏｃａｌ　Ｐｒｅｓｅｒｖｉｎｇ　Ｐｒｏｊｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ（ＬＰＰ）ｏｂｔａｉｎｓ　ｔｈｅ　ｄｉａｇｏｎａｌ　ｍａｔｒｉｘ　ｂｙ　ｃｏｍｐｕｔｉｎｇ　ｔｈｅ　ｓｕｍ　ｏｆ　ｔｈｅ　Ｅｕｃｌｉｄｅａｎ　ｄｉｓｔａｎｃｅ　ａｎｄ　ｉｔ　ｃａｎ　ｍａｋｅ　ｕｓｅ　ｏｆ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｔｏ　ｒｅｄｕｃｅ　ｄｉｍｅｎｓｉｏｎｓ．Ｈｏｗｅｖｅｒ，ｉｔ　ｉｓ　ｗｏｒｔｈ　ｔｏ　ｄｏ　ｆｕｒｔｈｅｒ　ｉｎｖｅｓｔｉｇａｔｉｏｎ　ｗｈｅｔｈｅｒ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｂｅ　ｏｐｔｉｍｉｚｅｄ．Ｉｎ　ｔｈｅ　ｐａｐｅｒ，ｓｏｍｅ　ｍｏｄｉｆｉｃａｔｉｏｎ　ａｒｅ　ｍａｄｅ　ｔｏ　ｔｈｅ　ｆｏｒｍｕｌａ　ｗｈｉｃｈ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｒｅｓｔｓ　ｏｎ．Ｗｉｔｈ　ａｄｄｉｎｇ　ｔｈｅ　ｅｘｐｏｎｅｎｔｉａｌ　ｐａｒａｍｅｔｅｒ，ｔｈｅ　ｉｍｐｒｏｖｅｄ　ｌｏｃａｌ　ｐｒｅｓｅｒｖｉｎｇ　ｐｒｏｊｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｅｘｐｏｎｅｎｔｉａｌ　ｄｉａｇｏｎａｌ　ｍａｔｒｉｘ　Ｃａｌｌ　ｂｅ　ｇｏｔ．Ｔｈｒｏｕｇｈ　ａ　ｌｏｔ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔｓ　ｉｔ　ｈａｓ　ａｎ　ａｆｆｅｃｔ　ｏｎ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｔｈｅ　ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　ｒｅｄｕｃｔｉｏｎ．Ｉｔ　ｉｓ　ｅａｓｉｅｒ　ｔｏ　ａｐ—　ｐｒｏａｃｈ　ｔｈｅ　ｉｎｔｒｉｎｓｉｃ　ｄｉｍｅｎｓｉｏｎ　ｏｆ　ｔｈｅ　ｄａｔａｓ．Ｉｔ　ａｌｓｏ　ｃｈｅｃｋｓ　ｔｈｅ　ｄｉｓｃｒｉｍｉｎａｔｉｏｎ　ａｆｔｅｒ　ｒｅｄｕｃｉｎｇ　ｔｈｅ　ｄｉｍｅｎｓｉｏｎｓ　ａｎｄ　ｔｈｅ　ｓｅｎｓｉｔｉｖｉｔｙ　ｏｆ　ｎｏｉｓｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　ｒｅｄｕｃｔｉｏｎ；ｌｏｃａｌ　ｐｒｅｓｅｒｖｉｎｇ　ｐｒｏｊｅｃｔｉｏｎ；ｄｉａｇｏｎａｌ　ｍａｔｒｉｘ；ｅｘｐｏｎｅｎｔｉａｌ　ｐａｒａｍｅｔｅｒ；ｎｏｉｓｅ　

摘要：局部保持映射（ＬＰＰ）算法利用欧几里德距离求得权值累加得到对角矩阵，利用结果进行降维。对于这个算法是否可以进　一步优化还值得进一步探讨。对该算法所依据的公式进行修改，在对角矩阵上引入指数参数，形成对角距阵指教优化的局部保　持映射算法。通过实验可以证明，对角距阵指数优化的局部保持映射算法能够影响降维的结果，可以使得降维更容易得到接近　本征维数的投影向量，通过实验验证降雏后的识别效果和对噪声的敏感度。　关键词：维数约简；局部保持映射（ＬＰＰ）；对角矩阵；指数参数；噪声　ＤＯＩ：１０．３７７８￣．ｉｓｓｎ．１００２．８３３１．２０１１．３６．０５５　文章编号：１００２—８３３ｌ（２０１１）３６．０１９７．０６　文献标识码：Ａ　中图分类号：ＴＰ３９１　

１引言　维数约简可以看成是挖掘嵌入在高维数据中的低维线性　或非线性流形，这种嵌入保留了原始数据的几何特征，即在高　维空间中靠近的点在嵌入空间中也相互靠近。流形学习是一　个基础性的研究方向，其广阔的应用前景使得流形学习近几　年发展很快。流形学习可以分为基于局部的方法和基于全局　的方法，比较经典的算法有以所有样本的最优重构为目的的　ＰＣＡ算法、以样本可区分性为主要目标的有监督学习的ＬＤＡ　算法”　、基于谱图理论的Ｌａｐｌａｃｉａｎ　Ｅｉｇｅｎｍａｐ算法　、局部线性　嵌入ＬＬＥ算法［３１以及为更有效发现流形空问非线性结构采用　的核方法［４－５１等。　局部保持映射算法ＬＰＰ　是一种最近提出的能够较好保　持非线性子流形局部特征的流行学习算法，可以找出高位数　据空间在低维空问中的投影，它的优点一是保留了数据之问　的相关性，能够更有效地描述流形架构的数据，二是做出的投　影是线性的，能够得出一组投影矩阵，在新增数据时也可以轻　

松找出对应的低维空间的表示。正由于此，对于ＬＰＰ的改进　研究或者与其他算法的组合应用研究也是层出不穷　。　ＬＰＰ算法中，首先根据数据点的距离得到权值矩阵，然后　利用权值矩阵计算得到对角矩阵和拉普拉斯矩阵，本文中对　得到对角矩阵做指数优化修改，得到新的对角矩阵和拉普拉　斯矩阵以及约束条件，最后利用改进的ＬＰＰ算法查看降维结　果。实验表明，改进后的ＬＰＰ算法能够取得更好的降维结果，　而且对多个数据库进行测试，发现改进后的算法都可以对其　进行优化，实验还考虑了指数参数对噪声的敏感度。　

２传统局部保持映射（ＬＰＰ）算法　２．１　ＬＰＰ算法原理　ＬＰＰ算法是线性投影算法，根据得到的投影方向来进行维　数的约简。　线性投影：给定Ｒ”空间的数据集Ｘ　，Ｘ　，…，Ｘ　，找到一个　

转换矩阵Ａ，把这Ⅳ个数据样本点投影到Ｒ　空间的点，这样　

基金项目：国家自然科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．６０７０４０４７）；国家自然科学基金重大研究计划　（Ｎｏ．９０８２００２）。　作者简介：安亚静（１９８６一），女，硕士研究生，主要研究方向：人工智能与模式识别；王士同（１９６４一），男，教授，博士生导师。Ｅ－ｍａｉｈｙａｊｉｎｇａｎ＠１２６・ｃｏｍ　收稿日期：２０１０．０８—２０；修回日期：２０１０—１１—２９；ＣＮＫＩｆｌｌ￣：２０ｕ．０２．２４；ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＲ２０１１０２２４．１５４６．０２５・ｈｔｍｌ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　当Ｙ　＝　就能够用Ｙｆ表示　ｆ。　ＬＰＰ算法步骤如下：　（１）重构邻接图　根据样本集利用欧几里德距离函数求出各个样本点问的　距离，判断两点之间是否有边相连有两种方式可依据需求进　行选择。　ｓ．近邻：若两点之间的距离小于某个常数ｓ，则两点之间　有边相连。　ｋ近邻：若某一点在另一点的最近的ｋ个点中，则两点之　间有边相连。　（２）权值矩阵（样本点之间的相关性）　若两点之间没有边相连，则权值设为０。否则给一定权值，　有两种方式可供选择。　简单给定：直接设置　，＝１；根据距离给定：　＝ｅ　。　（３）根据相关性找到投影矩阵Ａ　盯ｇ　ｎ∑（　一ＡＴｘｓ）　因为每组投影向量都独立作　用，所以改为考虑ａｒｇ　∑（口　）ｃ　一口　）　其中ｎ代表某一　个投影向量，令　＝　则：　Ｚ（Ｙ　一　）　＝∑　一２∑　＋∑　＝　ｑ　ｑ　２Ｚｙ２ｌＤ　－２Ｚｙｔｙ｛ｗｊ＝２ｙ　（Ｄ－ｗ）．ｖ＝２ｙ　Ｌｙ　ｉ　其中Ｄ是—个对角矩Ｉ砗，Ｄ　＝∑　，Ｌ＝Ｄ－　是拉普拉劳　，　所求的最优值的式子可以改写成如下形式：ａｒｇ　ｍｉｎ　ａＴＸＬＸ　ａ，　口Ｔ．　ｘ　：１　最小值出现在导　ＸＬＸａ一２ａ　ＸＤＸａ）＝０。这样问题简化成　“　为普遍的特征向量问题，且ａＴＸＬＸ　ａ＝２ａ　ＸＤＸ　ａ＝　，希望　ａＴＸＬＸ　ａ越小越好，所以取ａ为特征值最小的，个非零特征　向量。　’　２．２　ＬＰＰ算法的不足之处　在ＬＰＰ中，对角矩阵Ｄ代表了与之相关联的点的个数和　权值，在一定程度上反应了此点的重要性。在此，计算的方法　是Ｄ　＝∑　，对于权值矩阵确定后，只有一种计算方法得到　，　对角矩阵Ｄ和拉普拉斯矩阵￡，缺乏灵活性，不能在需要时对　对角矩阵做出调整，有很大的限制。本文设想能否通过改变　此式，进而改变对角矩阵Ｄ和拉普拉斯矩阵三的取值而影响　到降维效果。　３改进的ＬＰＰ算法　３．１　ＬＰＰ中目标函数的求解　ＬＰＰ算法目标函数：ａｒｇ叫ｎ∑　一　）　，等价于　ａｒｇ　ｎ∑（口　一ｎ　，）２　，其中　代表某一个投影向量，　＝　。对于∑（Ｊ，　－Ｙｓ）　＝２ｙ　一Ｗ）ｙ＝ｅｙ　Ｌｙ，由于拉普拉　斯矩阵三、对角矩阵Ｄ都是对称和正半正定的，所以得到的　ＸＬＸ　和ＸＤＸ　都是对称和正半正定的。在紧凑黎曼流形中，　对于有限图拉普拉斯矩阵和拉普拉斯贝尔特拉米算子是相似　的。对于流形拉普拉斯贝尔特拉米算子是根据贝尔特拉米度　量来得到的，对于图是由邻接关系得到的。Ｂｅｌｋｉｎ和Ｎｉｙｏｇｉ提　出流形上的最优局部保持映射可以通过解决下面的最优函数　一　２　一　ｒａ，ｉｎ：　￣ＩＩＶＦＩＩ得到，此式等价于：　ｍ，ｉｎ：　ｉ，ｙ￣ｉ。其中￡　’’Ｌ。【　）　。　Ｌ。Ｉ　）　是流形上的拉普拉斯贝尔特拉米算子ｅ（厂）＝一ｄｉｖ　Ｖ（厂），因此最　优厂是￡的特征函数，如果假定厂是线性的，有ｒ（ｘ）＝Ｗ　Ｘ。　由生成图理论，最终归结为求下面的特征值问题：ＸＬＸ　ｎ＝　２ＸＤＸ‘ａ，然后求解此式即可得到投影向量，进而得到目标　

函数。　３．２影响目标函数的因素　根据目标函数的原理来求得最优值可以知道，影响目　标函数的主要有两个方面，一是权值　的改变，一是约束　ａＴＸＤＸ　口＝１的调整，调节的目的都是改变数据点对整个数据　集的贡献率，进而改造投影方向，这样来控制降维的效果。　３．３改进的方向　这里保持权值　不变，修整Ｄ的取值，也就是改进一个　数据点与相关数据点的关系。加入指数参数ｍ，即把Ｄ　改为Ｄ　ｍ　：　，这样约束变为：ａＴＸＤ　Ｘ　ａ＝ｌ，而Ｌ　＝　７　“７　

Ｄ　一　是改进后的拉普拉斯矩阵，Ｄ　是带指数参数的对角　矩阵Ｄｍ　＝　，它是权值矩阵列（或者行）的求和，在ＬＰＰ中　‘‘』一　

Ｄ权衡的就是数据点在整个样本数据中的重要性，也就是Ｄ　越大重要性更高。这里的　起到一样的作用，可以通过调整　ｍ的取值来改变样本数据点的重要性。改进后的公式加入了　指数参数，这样避免了ｍ只能取ｌ的情况，对于等价的目标　函数ａｒｇ　ｍｉ　ａＴ　Ｘ　口和约束条件ａＴＸＤ　Ｘ　口＝１，利用　ａ　‘Ｘ　ｎ：１　Ｏ　ｍ：　来决定数据分布的稠密程度。通过改变ｍ的取值　”７