基于图的半监督降维算法_杨格兰

第４１卷　第４期２０１４年４月计算机科学

Ｃｏｍｕｔｅｒｃｉｅｎｃｅ　ＳＶｏｌ．４１Ｎｏ．４

Ａｒ２０１４　基于图的半监督降维算法

杨格兰１　金辉霞２　孟令中３　朱幸辉４

１２

（））湖南城市学院信息科学与工程学院　益阳４湖南城市学院通信与电子工程学院　益阳４１３０００１３０００　（

３

（）中国科学院软件研究所基础软件测评实验室　北京１００１９０

４

（）湖南农业大学信息科学工程学院　长沙４１０１２８

摘　要　非线性降维和半监督学习都是近年来机器学习的热点。将半监督的方法运用到非线性降维中，提出了基于图的半监督降维的算法。该算法用等式融合的方法推出了标记传播算法的另一种表达形式，用标记传播的结果作为初始的数据映射，然后在图谱张成的线性空间中寻找最逼近初始映射的数据作为最后的半监督降维的结果。实验表明，所提算法可以获得平滑的数据映射，更接近于理想的降维效果。与标记传播算法、图谱逼近算法、无监督的降维算法的比较也体现出本算法的优越性。

关键词　半监督学习，流形学习，标记传播，图谱理论中图法分类号　ＴＰ３０１　　　文献标识码　Ａ　

ＧｒａｈｂａｓｅｄＳｅｍｉｓｕｅｒｖｉｓｅｄＤｉｍｅｎｓｉｏｎａｌｉｔＲｅｄｕｃｔｉｏｎＡｌｏｒｉｔｈｍ－　－　　ｐｐｙｇ　

１２３４

ＹＡＮＧＧｅｌａｎＩＮ　ＨｕｉｘｉａＮＧＬｉｎｚｈｏｎＨＵ　Ｘｉｎｈｕｉ　－　Ｊ－　ＭＥ　－－　ｇｇ　Ｚｇ

１（，，）ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｉｎｅｅｒｉｎＨｕｎａｎＣｉｔＵｎｉｖｅｒｓｉｔＹｉａｎ４１３０００，Ｃｈｉｎａ　　　　　　ｇｇｙｙｙｇ　　２（，，）ＳｃｈｏｏｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎａｎｄＥｌｅｃｔｒｏｎｉｃＥｎｉｎｅｅｒｉｎＨｕｎａｎＣｉｔＵｎｉｖｅｒｓｉｔＹｉａｎ４１３０００，Ｃｈｉｎａ　　　　　　ｇｇｙｙｙｇ　　

３（，，，）ＬａｂｏｒａｔｏｒｏｆＦｕｎｄａｍｅｎｔａｌＳｏｆｔｗａｒｅＴｅｓｔｉｎａｎｄＥｖａｌｕａｔｉｏｎＩｎｓｔｉｔｕｔｅｏｆＳｏｆｔｗａｒｅＣｈｉｎｅｓｅＡｃａｄｅｍｏｆＳｃｉｅｎｃｅｓＢｅｉｉｎ１００１９０，Ｃｈｉｎａ　　　　　　　　ｙｇｙｊｇ　　　　

４（，，）ＩｎｓｔｉｔｕｔｅｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｉｎｅｅｒｉｎＨｕｎａｎＡｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔＣｈａｎｓｈａ４１０１２８，Ｃｈｉｎａ　　　　　　ｇｇｇｙｇ

Ａｂｓｔｒａｃｔｏｎｌｉｎｅａｒｄｉｍｅｎｓｉｏｎａｌｉｔｒｅｄｕｃｔｉｏｎａｎｄｓｅｍｉｓｕｅｒｖｉｓｅｄｌｅａｒｎｉｎａｒｅｂｏｔｈｈｏｔｉｓｓｕｅｓｉｎｍａｃｈｉｎｅｌｅａｒｎｉｎａｒｅａ．　Ｎ　　　－　　　　　　　ｙｐｇｇ　　　，Ｂａｓｅｄｏｎｓｅｍｉｓｕｅｒｖｉｓｅｄｍｅｔｈｏｄｔｈｅａｒｔｉｃｌｅｓｏｌｖｅｄｎｏｎｌｉｎｅａｒｄｉｍｅｎｓｉｏｎａｌｉｔｒｅｄｕｃｔｉｏｎｒｏｂｌｅｍｔｏｍａｋｅｕｆｏｒｔｈｅ　　－　　　　　　　　　　ｐｙｐｐ　　，ｏｆｏｒｄｉｎａｒｍｅｔｈｏｄｓ．Ｂｕｓｉｎｉｎｔｅｒａｔｉｏｎｏｆｅｕａｌｉｔｉｅｓａｎｏｖｅｌｅｘｒｅｓｓｉｏｎｏｆｌａｂｅｌｒｏａａｔｉｏｎａｌｏｒｉｔｈｍ　ｗａｓｓｈｏｒｔｆａｌｌ　　　　　　　　　　ｙｙｇｇｑｐｐｐｇｇ　　　，ｒｏｏｓｅｄ．Ｗｅｕｓｅｄｔｈｅｌａｂｅｌｒｅｓｕｌｔａｓｔｈｅｉｎｉｔｉａｌｖａｌｕｅｍａｉｎａｎｄｔｈｅｎｆｏｕｎｄｔｈｅｂｅｓｔａｒｏｘｉｍａｔｉｏｎｔｏｉｔｒｏａａｔｉｏｎ　　　　　　　　　　　　　　　　　ｐｐｐｐｇｐｐｐｐｇｔｈｅｓｅｃｔｒａｌｓａｃｅ．Ｔｈｅｅｘｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｏｕｒｓｅｍｉｓｕｅｒｖｉｓｅｄｄｉｍｅｎｓｉｏｎａｌｉｔｒｅｄｕｃｔｉｏｎｍｅｔｈｏｄｃａｎａｉｎｒａｈ　　　　　　　　　－　　　　－ｐｐｐｐｙｇｐ　ｃｈｉｅｖｅｓｍｏｏｔｈｄａｔａｍａｉｎｔｈａｔｉｓｃｌｏｓｅｒｔｏｔｈｅｉｄｅａｌｅｆｆｅｃｔ．　　　　　　　　　ｐｐｇ　

，，，ｒｏａａｔｉｏｎｒａｈＫｅｗｏｒｄｓｅｍｉｓｕｅｒｖｉｓｅｄｌｅａｒｎｉｎＭａｎｉｆｏｌｄｌｅａｒｎｉｎＬａｂｅｌＳｅｃｔｒａｌｔｈｅｏｒ　Ｓ－　　　　　ｐｐｇｇｐｐｇｇｐｙｙ　

［［４］５］

）、）、图册化流形（基于局部切空ｍａｓＣｈａｒｔｉｎａＭａｎｉｆｏｌｄ　ｐｇ　［６］

等，这些算法能较好地解决数据处理中的非线间（ＬＴＳＡ）

１　引言

随着信息技术的飞速发展，信息数据具有一些新的特点，如维数高、属性强相关、样本数巨大但标签样本很少等，这使得传统的机器学习方法难以直接用来分析来源于真实世界的高维和非线性数据。故产生了很多解决高维数据问题的方法。降维是从高维观测空间通过线性或非线性映射投影到一个低维特征空间，发现隐藏在高维观测数据中有意义的低维结构，来研究数据特性。传统的线性降维算法有主分量分析（、、独立分量分析（线性判别分析（等，这些ＰＣＡ）ＩＣＡ）ＬＤＡ）算法产生简单的变换函数，运算简便，尤其对线性结构降维效

１］

。但是现实中的高维数据大多是非线性的，果好［用线性方

性高维数位问题，保持原始数据的拓扑结构不变。

由于图和流形有很多相近的性质，最重要的一点就是都可以嵌入到Ｅ因此很多研究人员都使用图的方法ｕｃｌｉｄ空间，逼近流形，并利用图的理论求解低维嵌入。流谱图理论在流很多流形降维的算法都是形学习中已经得到了广泛的应用，

以谱理论为基础的。图谱分解方法更加促进了非线性降维的］发展，文献［用对齐不同流形内在关系的方法，对两组流形１０数据之间的降维问题进行了探讨，阐明了怎样根据一些附加的关于这些数据集之间的映射信息来对齐它们的低维表达，很好地解决了两个流形降维后在同一个坐标系中的排列问题。但是在流形降维算法实现中，提出用标记传播（ｌａｂｅｌ）做半监督降维的算法，存在的问题是定义的状态ｒｏａａｔｉｏｎｐｐｇ转移矩阵是能量消耗型，降维易导致标记点在外围，未标记点

法很难发现高维数据的内在性质，于是近年来涌现了许多基

［２］

、于流形的非线性降维方法，如等度规映射（局部ＩＳＯＭＡＰ）［３］

、线性嵌入（拉普拉斯特征映射（ＬＬＥ）ＬａｌａｃｉａｎＥｉｅｎ　－ｐｇ

），）到稿日期：湖南省教育厅优秀青年项目（资助。２０１３０５１１２０１３０７２９２０１２ＢＡＤ３５Ｂ０７１２Ｂ０２３－－　返修日期：－－　　本文受国家科技支撑计划课题（，：；，杨格兰（男，硕士，副教授，主要研究方向为机器学习、模式识别，孟令中（男，博士，主要研１９７５－）Ｅ－ｍａｉｌｌａｎａｉｌ．ｕｓｔｃ．ｅｄｕ．ｃｎ１９８１－）ｇｙｇ＠ｍ究方向为软件可信性、软件测试。

·２８０·