流形学习算法综述

Ｃｏｍｐｕｔｅｒ

ＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

２００８，４４（３５）

９

流形学习算法综述

王自强１，钱旭１，孔敏２

ＷＡＮＧＺｉ－ｑｉａｎ９１．ＱＩＡＮＸｕｌ，ＫＯＮＧＭｉｎ２

１．中国矿业大学（北京）机电与信息工程学院，北京ｌＯ００８３２．山东省曲阜市职业中等专业学校，山东曲阜２７３１００

１．ＣｏｌｌｅｇｅｏｆＭｅｃｈａｎｉｃａｌＥｌｅｃｔｒｏｎｉｃ

ａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙ

ｏｆ

Ｍｉｎｉｎｇａｎｄ

Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ

１０００８３，Ｃｈｉｎａ

２．Ｑｕｆｕ

Ｖｏｃａｔｉｏｎａｌ

ＳｃｈｏｏｌｏｆＳｈａｎｄｏｎｇ

Ｐｒｏｖｉｎｃｅ，Ｑｕｆｕ，Ｓｈａｎｄｏｎｇ

２７３１００，Ｃｈｉｎａ

Ｅ－ｍａｉｌ：ｗｚｑｂｅｘＣａ吟ａｈｏｏ．ｃａ

ＷＡＮＧＺｉ－－ｑｉａｎｇ．ＱｔＡＮ２００８．４４（３５）：９—１２．

Ｘｕ．ＫＯＮＧ

Ｍｉｎ．Ｓｕｒｖｅｙ

Ｏｎ

ｍａｎｉｆｏｌｄｌｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ。

Ａｂｓｔｒａｃｔ：Ａｓｍａｎｉｆｏｌｄｔａｔｉｏｎ．Ａｔ

ａ

ｎｏｖｅｌｄｉｍｅｎｓｉｏｎａｌｉｔｙｗｈｉｃｈｉｓ

ｅｍｂｅｄｄｅｄ

ｒｅｄｕｃｔｉｏｎｔｅｃｈｎｉｑｕｅ，ｍａｎｉｆｏｌｄｉｎ

ｔｈｅｈｉｇｈ

ａ

ｌｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍ

ａｉｍｓ

ａｔ

ｄｉｓｃｏｖｅｒｉｎｇｔｈｅ

ｌｏｗｅｒｄｉｍｅｎｓｉｏｎａｌ

ｓｔｒｕｃｔｕｒｅ

ｄｉｍｅｎｓｉｏｎａｌｉｔｙｈｏｔｉｓｓｕｅｉｎ

ｄａｔａ

ｓｐａｃｅ，ａｎｄ

ｄｅｒｉｖｅｓ

ａｎｅｆｆｉｃｉｅｎｔｌｏｗｅｒｄｉｍｅｎｓｉｏｎａｌｒｅｐｒｅｓｅｎ－

ｌｅａｒｎｉｎｇ

ａｎｄｄａｔａ

ｍｉｎｉｎｇ．ｐｍｂ－

ｐｒｅｓｅｎｔ，ｍａｎｉｆｏｌｄ

ｌｅａｒｎｉｎｇｈａｓｂｅｃｏｍｅ

ｌａｔｅｓｔｒｅｓｅａｒｃｈ

ｔｈｅｆｉｅｌｄ

ｏｆｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ，ｍａｃｈｉｎｅ

Ｔｈｅｆｕｎｄａｍｅｎｔａｌｉｄｅａｓ，ｓｏｍｅｌｅｍｓＫｅｙ

ｆｏｒｆｕｒｔｈｅｒｒｅｓｅａｒｃｈ

ａｌｅ

ｒｅｓｕｔｌｓａｎｄ

ａｌｇｏｒｉｔｈｍａｎａｌｙｓｉｓ

ｏｆｍａｎｉｆｏｌｄ

ｌｅａｆｉｎｇ小ｉｎｔｒｏｄｕｃｅｄ．Ｂｅｓｉｄｅｓ，ｓｏｍｅ

ｐｒｅｓｅｎｔｅｄａｎｄａｎａｌｙｚｅｄ．

ｒｅｄｕｃｔｉｏｎ；ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ；ｍａｃｈｉｎｅ

ｌｅａｒｎｉｎｇ

ｗｏｒｄｓ：ｍａｎｉｆｏｌｄ

ｌｅａｒｎｉｎｇ；ｄｉｍｅｎｓｉｏｎａｌｉｔｙ

摘要：流形学习算法作为一种新的维数降维方法工具。其目标是发现嵌入在高维数据空间中的低维流形结构．并给出一个有效的低维表示。目前，流形学习已成为模式识别、机器学习和数据挖掘领域的研究热点问题。介绍了流形学习的基本思想、一些最新研究成果及其算法分析，并提出和分析了有待进一步研究的问题。关键词：流形学习；维数降维；模式识别；机器学习

ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００８．３５．００３

文章编号：１００２—８３３１（２００８）３５—０００９—０４文献标识码：Ａ中图分类号：ＴＰｌ８１

１

引占

在人工智能、模式识别、机器学习和数据挖掘等众多研究

维数降维方法闭。ＰＣＡ的关键思想来源于Ｋ—Ｌ变换，其主要目标是通过线性变换寻找一组最优的单位正交向量基，并用它们的线性组合来重构原样本，以使重建构后的样本和原样本的误差最小。尽管ＰＣＡ在许多模式识别应用中取得了较好的效果，但是由于它是以所有样本的最优重构为目的，并且ＰＣＡ是一种无监督的学习方法，因ＩＥｘ－Ｉｉ寸于描述不同类别样本之间的差异而言，它不一定是最优的描述。相对于无监督的ＰＣＡ方法而言，ＬＤＡ是一种有监督的学习方法，它是以样本的可区分性为主要目标，通过寻找一组线性变换以达到类内散度最小且类间散度最大的目的。在模式识别应用中，基于ＬＤＡ的算法通常要优于基于ＰＣＡ的算法。但是ＬＤＡ的不足之处在于存在“奇异值”问×题，也既是：当数据样本来自高维空间时，样本的维数要

领域中，人们经常要面临的—个问题是持续增长的模式空间维数１１ｌｏ例如在人脸识别应用中，—幅具有分辨率为１２８ｘ１２８的人脸图像町以表示成具有１６３８４维的人脸空间，考虑到高维人脸空间引起的“维数灾难”问题，人们通常首先把把高维人脸空间投影到低维特征子空间。然后在降维后的低维特征空间中利用分类器进行分类识别。维数降维可以有效地避免“维数灾难”、提高后继分类器的性能和计算效率、抑制噪声、节省计算和存储资源。事实上，高维数据空ｌ＇日Ｊ的内在维数是很低的，通过维数降维，可以有效地发现高维数据空间内在的结构特征。因

此维数降维问题在模式识别、机器学习和计算机视觉等众多领

域受到了广泛地关注，并且随着高维海量数据（如：Ｗｅｂ数据、图像和视频等）的不断增加，维数降维问题正日益成为新的研究热点。

主成分分析（Ｐｒｉｎｃｉｐｌｅ鉴别分析（Ｌｉｎｅａｒ

Ｃｏｍｐｏｎｅｎｔ

远大于样本数，从而导致ＬＤＡ中散度矩阵的奇异性。为了有效

地解决ＬＤＡ的奇异性问题，有关学者提出了多种解决方法，如：ＰＣＡ＋ＬＤＡ法、零空间法ＬＤＡ、伪逆ＬＤＡ法、正则法ＬＤＡ

Ａｎａｌｙｓｉ８。ＰＣＡ）和线性等，具体内容详见文献【３－４】。

针对ＰＣＡ和ＬＤＡ都是基于训练样本的二阶统计信息，而

Ｄｉｓｃｒｉｍｉｎａｎｔ

Ａａｎｌｙｓｉｓ，ＬＤＡ）是两种最著名的

基金项日：教育部科学技术研究赖目（ｔＩｌｅ

学习与信息融合。

收稿日期：２００８－０９－０３

ＫｅｙＳｃｉｅｎｔｉｆｉｃａｎｄＴｅｃｈｎｉｃａｌＲｅｓｅａｒｃｈ

ＰｒｏｊｅｃｔｏｆＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮａ１０７０２１）。

作者简介：王自强（１９７３一），男．博士研究生，主要研究方向：机器学习与模式识别；钱旭（１９６２一），男，博士．教授，博士生导师，主要研究方向：机器

傣回日期：２００８—１０－０６

万方数据　

１０

２００８，４４（３５）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

忽视了高阶统计信息的不足，独立成分分析（Ｉｎｄｅｐｅｎｄｅｎｔ

Ｃｏｍｐｏｎｅｎｔ

Ａｎａｌｙｓｉｓ，ＩＣＡ）嘲除了能够分离像ＰＣＡ中的二阶矩。

而且能够分离输入数据的高阶矩，从而使数据的二阶统计和高阶统计信息都得到了有效利用。ＩＣＡ的丰要思想是通过线性变换，从训练样本中找到一组相互独立的基来描述样本数据，因此可以认为ＰＣＡ是ＩＣ …… 此处隐藏：16749字，全部文档内容请下载后查看。喜欢就下载吧 ……