本站原创
摘要： 鲁棒性不足是传统的基于L2-范数的主成分分析（L2-PCA）的主要问题。为此，提出了一种基于新的L1-范数优化技术的主成分分析（L1-PCA）方法。该方法使用了对异常值和旋转不太敏感的L1-范数。L1-范数优化技术是直观的、简单的和易于实现的，事实上，L1-范数优化技术也被证明是找到本地最大值的一种解决方法。在一些数据集上的实验验证了基于L1-范数优化技术的主成分分析算法的有效性。
关键词： PCA-L1； L1-范数； 优化； 主成分分析； 鲁棒性
1006-8228（2012）12-03-03
Principal component analysis based on L1-norm optimization
Zhang Congcong1， Chen Qi1， Xu Jiaheng2， Ji Binqiong1， Xu Shuhua1
（1. School of Maths and Physics， Shaoxing College， Shaoxing， Zhejiang 312000， China； 2. School of Engineering， Shaoxing College）
Abstract： Lacking robustness is a main problem of the traditional L2-norm （L2-PCA）. In this paper， a method of principal component analysis （PCA） based on a new L1-norm optimization technique is introduced. L1-norm is used， which is less sensitive to abnormal values and rotations. The proposed L1-norm optimization technique is intuitive， simple and easy to be implemented. It is also proven to be a solution to find a local maximum. Simulations on several databases are conducted to verify the validity of L1-PCA.
Key words： PCA-L1； L1-norm； optimization； principal component analysis； robustness
0 引言
在对待大量的输入数据分析的问题上，为了简化问题，同时又不降低性能，通常使用降维来减少输入的数据量，其中，主成分分析是最受欢迎的方法之一。在主成分分析中，试图找到一组能够最大化给定数据的方差的投影。这些投影构成一个低维线性子空间，在此空间中，保留了原始的输入空间中的数据结构。
虽然基于L2范数的PCA（简称L2-PCA）已成功地解决了许多问题，但是它很容易出现异常值，因为L2范数会夸大一个大范数下的异常值的影响力。为了减轻这一问题并实现鲁棒性，很多研究者已经进行了许多研究[2-7]。在文献[5-7]中，检测定每个投影和原始数据点之间的误差主要是遵循拉普拉斯分布而不是高斯分布，通过最大似然估计所给定的数据来制定L1范数PCA（L1-PCA）。为获得L1-PCA的解决方法，文献[5]使用了启发式估计来解决了一般的L1问题，与此同时，文献[6，7]提出了加权中值法和凸面编程法。尽管L1-PCA具有鲁棒性，但它还有一些缺点。首先，由于它是基于线性或二次规划，计算量大；其次，它对旋转是可变的。在文献[4]中，丁等人提出了融合了L1-PCA、L2-PCA的优点的R1-PCA。不像L1-PCA，R1-PCA正如L1-PCA那样成功地抑制了异常值的影响，并且是旋转不变式。然而，该方法是高度依赖于被找到的m维子空间。例如，在m=1时获得的投影向量不可能是在m=2获得的子空间。此外，因为它是一个基于一个连续使用功率法[8]的迭代算法，对于一个大维数的输入空间，它需要花费很多的时间来实现收敛。
然而，上述方法都试着在原始的输入空间对投影和原始数据点之间的误差最小化。如果L2-范数作为距离测量，这个目标可以通过奇异值分解实现[8]，奇异值分解相当于通过在特征空间中最大化方差来找到投影。在本文中，不是使用基于L2-范数最大化方差，而是使用了一种能够最大限度提高特征空间的L1-范数、实现稳健和旋转不变的主成分分析方法。实验表明，基于L1-范数的PCA算法具有好的降维分类性能。⑴ 计算
⑴
式⑴中，是投影矩阵的列构成m维线性子空间（即特征空间），是系数矩阵，（i，j）组件vij对应着xj的第i个
⑵ 求解目标函数
⑵
式⑵中，Sx=XXT是协方差矩阵X和Im的m×m单位矩阵。
通常L2-范数是敏感的异常值，为此文献[5-7]提出将问题转化为找到一个W使得接下来的误差函数能最小化：
⑶
这里，表示L1-范数的矩阵或向量。
虽然公式⑶减少了异常值的影响，但是它并不是固定不变的旋转，并且一个等距离表面的形状变得非常扭曲。文献[4]提出了基于R1-范数近似地解决误差函数最小化的方案，即：⑷
公式⑷中子空间L1-范数估计迭代算法是很困难的，在文献[4]中使用了胡贝尔的M-估计技术。
在本文中，我们在特征空间中L1分散使用L1-范数最大化，即：
⑸
式⑸中，约束条件WTW=Im是为了确保投影矩阵的正交性。
公式⑸存在一个问题：最优的第i个投影在R1-PCA中随着不同的值m而不同，在m>1时找到一个全局最优的解决方案是困难的。为了解决这个问题，我们通过使用一种贪婪的搜索方法简化公式⑸中m=1的问题。如果令m=1，公式⑸就变成了以下的优化问题：
⑹
⑵ 极性检验：对于所有的i∈{1，2，…，n}，如果wT（t）xi<0，pi（t）=-1，否则pi（t）=1。
⑶ 翻转和最大化：令t←t+1，·w（t）←w（t）/。
⑷ 收敛性检验：
（a） 如果w（t）≠w（t-1），则执行第二步；
（b） 否则如果存在i使得wT（t）xi=0，令w（t）←（w（t）+Δw）/，继续执行第二步（这里的Δw是一个小的非零随机向量）；
（c） 否则，令w*=w（t），最后终止。
2 实验
表1实验中使用的UCI数据集
[数据集＼&维数＼&类数＼&样本数＼&Australian＼&14＼&2＼&690＼&Balance＼&4＼&3＼&625＼&Breast cancer＼&9＼&2＼&683＼&Dermatology＼&34＼&6＼&358＼&Heart disease＼&13＼&2＼&297＼&Ionosphere＼&33＼&2＼&351＼&Liver＼&6＼&2＼&345＼&Sonar＼&60＼&2＼&208＼&]
（a） Australian（b） Balance
（c） Breast cancer （d） Dermatology
（e） Heart disease （f） Ionosphere
（g） Liver （h） Sonar
图1多个UCI数据集的实验结果
此外，考虑到计算成本，表2给出了L2-PCA，R1-PCA和PCA-L1所需的平均时间和平均迭代次数。
表2UCI数据集的计算时间和平均迭代次数
[＼& 平均时间（毫秒）＼&平均迭代次数＼&数据集＼&L2-PCA＼&R1-PCA＼&PCA-L1＼&R1-PCA＼&PCA-L1＼&Australian＼&0＼&583＼&343＼&42.29＼&7.14＼&Balance＼&0＼&36＼&47＼&2.00＼&1.00＼&Breast cancer＼&0＼&547＼&266＼&45.44＼&9.78＼&Dermatology＼&62＼&750＼&750＼&45.47＼&12.82＼&Heart disease＼&0＼&239＼&141＼&36.61＼&6.53＼&Ionosphere＼&64＼&816＼&625＼&47.30＼&10.15＼&Liver＼&0＼&125＼&79＼&24.67＼&5.67＼&Sonar＼&47＼&1533＼&734＼&34.50＼&10.
通过分析可以得出，因为R1-PCA的第i个的投影矢量与提取的特征数量的变化有关，所以计算的时间和R1-PCA迭代次数是提取不同数目的特征平均值。另一方面，L2-PCA和PCA-L1的时间和迭代提取的特征的数目等于输入变量个数时获得的数据。例如， R1-PCA时间为25500毫秒=750毫秒×34，而L2-PCA和PCA-L1的平均时间分别为62毫秒和750毫秒。在表2中，我们可以看出在许多情况下用PCA-L1的时间少于R1-PCA，并且在波形的数据集中PCA-L1的迭代次数少于15次。
关键词： PCA-L1； L1-范数； 优化； 主成分分析； 鲁棒性
1006-8228（2012）12-03-03
Principal component analysis based on L1-norm optimization
Zhang Congcong1， Chen Qi1， Xu Jiaheng2， Ji Binqiong1， Xu Shuhua1
（1. School of Maths and Physics， Shaoxing College， Shaoxing， Zhejiang 312000， China； 2. School of Engineering， Shaoxing College）
Abstract： Lacking robustness is a main problem of the traditional L2-norm （L2-PCA）. In this paper， a method of principal component analysis （PCA） based on a new L1-norm optimization technique is introduced. L1-norm is used， which is less sensitive to abnormal values and rotations. The proposed L1-norm optimization technique is intuitive， simple and easy to be implemented. It is also proven to be a solution to find a local maximum. Simulations on several databases are conducted to verify the validity of L1-PCA.
Key words： PCA-L1； L1-norm； optimization； principal component analysis； robustness
0 引言
在对待大量的输入数据分析的问题上，为了简化问题，同时又不降低性能，通常使用降维来减少输入的数据量，其中，主成分分析是最受欢迎的方法之一。在主成分分析中，试图找到一组能够最大化给定数据的方差的投影。这些投影构成一个低维线性子空间，在此空间中，保留了原始的输入空间中的数据结构。
虽然基于L2范数的PCA（简称L2-PCA）已成功地解决了许多问题，但是它很容易出现异常值，因为L2范数会夸大一个大范数下的异常值的影响力。为了减轻这一问题并实现鲁棒性，很多研究者已经进行了许多研究[2-7]。在文献[5-7]中，检测定每个投影和原始数据点之间的误差主要是遵循拉普拉斯分布而不是高斯分布，通过最大似然估计所给定的数据来制定L1范数PCA（L1-PCA）。为获得L1-PCA的解决方法，文献[5]使用了启发式估计来解决了一般的L1问题，与此同时，文献[6，7]提出了加权中值法和凸面编程法。尽管L1-PCA具有鲁棒性，但它还有一些缺点。首先，由于它是基于线性或二次规划，计算量大；其次，它对旋转是可变的。在文献[4]中，丁等人提出了融合了L1-PCA、L2-PCA的优点的R1-PCA。不像L1-PCA，R1-PCA正如L1-PCA那样成功地抑制了异常值的影响，并且是旋转不变式。然而，该方法是高度依赖于被找到的m维子空间。例如，在m=1时获得的投影向量不可能是在m=2获得的子空间。此外，因为它是一个基于一个连续使用功率法[8]的迭代算法，对于一个大维数的输入空间，它需要花费很多的时间来实现收敛。
然而，上述方法都试着在原始的输入空间对投影和原始数据点之间的误差最小化。如果L2-范数作为距离测量，这个目标可以通过奇异值分解实现[8]，奇异值分解相当于通过在特征空间中最大化方差来找到投影。在本文中，不是使用基于L2-范数最大化方差，而是使用了一种能够最大限度提高特征空间的L1-范数、实现稳健和旋转不变的主成分分析方法。实验表明，基于L1-范数的PCA算法具有好的降维分类性能。
1 基于L1-范数最大化的PCA
1.1 理论分析
令为给定的数据，n和d分别表示样本的数量和维数的原始输入空间。在L2-PCA试图通过最小化误差找到一个m（⑴
式⑴中，是投影矩阵的列构成m维线性子空间（即特征空间），是系数矩阵，（i，j）组件vij对应着xj的第i个
源于：论文写作格式www.udooo.com
坐标中的m维特征空间W，是L2-范数的矩阵或向量的表示。⑵ 求解目标函数
⑵
式⑵中，Sx=XXT是协方差矩阵X和Im的m×m单位矩阵。
通常L2-范数是敏感的异常值，为此文献[5-7]提出将问题转化为找到一个W使得接下来的误差函数能最小化：
⑶
这里，表示L1-范数的矩阵或向量。
虽然公式⑶减少了异常值的影响，但是它并不是固定不变的旋转，并且一个等距离表面的形状变得非常扭曲。文献[4]提出了基于R1-范数近似地解决误差函数最小化的方案，即：⑷
公式⑷中子空间L1-范数估计迭代算法是很困难的，在文献[4]中使用了胡贝尔的M-估计技术。
在本文中，我们在特征空间中L1分散使用L1-范数最大化，即：
⑸
式⑸中，约束条件WTW=Im是为了确保投影矩阵的正交性。
公式⑸存在一个问题：最优的第i个投影在R1-PCA中随着不同的值m而不同，在m>1时找到一个全局最优的解决方案是困难的。为了解决这个问题，我们通过使用一种贪婪的搜索方法简化公式⑸中m=1的问题。如果令m=1，公式⑸就变成了以下的优化问题：
⑹
1.2 算法步骤
⑴ 初始化：选择任意的w（0），令，t=0。⑵ 极性检验：对于所有的i∈{1，2，…，n}，如果wT（t）xi<0，pi（t）=-1，否则pi（t）=1。
⑶ 翻转和最大化：令t←t+1，·w（t）←w（t）/。
⑷ 收敛性检验：
（a） 如果w（t）≠w（t-1），则执行第二步；
（b） 否则如果存在i使得wT（t）xi=0，令w（t）←（w（t）+Δw）/，继续执行第二步（这里的Δw是一个小的非零随机向量）；
（c） 否则，令w*=w（t），最后终止。
2 实验
2.1 实验数据
本文采用了部分UCI数据集，具体描述如下表1所示。表1实验中使用的UCI数据集
[数据集＼&维数＼&类数＼&样本数＼&Australian＼&14＼&2＼&690＼&Balance＼&4＼&3＼&625＼&Breast cancer＼&9＼&2＼&683＼&Dermatology＼&34＼&6＼&358＼&Heart disease＼&13＼&2＼&297＼&Ionosphere＼&33＼&2＼&351＼&Liver＼&6＼&2＼&345＼&Sonar＼&60＼&2＼&208＼&]
2.2 实验结果与分析
实验采用最近邻分类（1-NN）。对于每个数据集，我们进行了20次实验并计算平均分类率。实验前，对每个输入变量进行标准化，它们具有零均值和单位方差。测试组中的变量也被标准化。图1给出了具体的实验结果。（a） Australian（b） Balance
（c） Breast cancer （d） Dermatology
（e） Heart disease （f） Ionosphere
（g） Liver （h） Sonar
图1多个UCI数据集的实验结果
此外，考虑到计算成本，表2给出了L2-PCA，R1-PCA和PCA-L1所需的平均时间和平均迭代次数。
表2UCI数据集的计算时间和平均迭代次数
[＼& 平均时间（毫秒）＼&平均迭代次数＼&数据集＼&L2-PCA＼&R1-PCA＼&PCA-L1＼&R1-PCA＼&PCA-L1＼&Australian＼&0＼&583＼&343＼&42.29＼&7.14＼&Balance＼&0＼&36＼&47＼&2.00＼&1.00＼&Breast cancer＼&0＼&547＼&266＼&45.44＼&9.78＼&Dermatology＼&62＼&750＼&750＼&45.47＼&12.82＼&Heart disease＼&0＼&239＼&141＼&36.61＼&6.53＼&Ionosphere＼&64＼&816＼&625＼&47.30＼&10.15＼&Liver＼&0＼&125＼&79＼&24.67＼&5.67＼&Sonar＼&47＼&1533＼&734＼&34.50＼&10.
摘自：写毕业论文经典的网站www.udooo.com
30＼&]通过分析可以得出，因为R1-PCA的第i个的投影矢量与提取的特征数量的变化有关，所以计算的时间和R1-PCA迭代次数是提取不同数目的特征平均值。另一方面，L2-PCA和PCA-L1的时间和迭代提取的特征的数目等于输入变量个数时获得的数据。例如， R1-PCA时间为25500毫秒=750毫秒×34，而L2-PCA和PCA-L1的平均时间分别为62毫秒和750毫秒。在表2中，我们可以看出在许多情况下用PCA-L1的时间少于R1-PCA，并且在波形的数据集中PCA-L1的迭代次数少于15次。
3 结束语
本文提出了基于L1范数的主成分分析方法的优化。该方法使用了对异常值和旋转不太敏感的L1-范数，最大限度地提高L1范数的预计，而不是传统的L2范数的空间。在UCI的实验表明，与基于传统的L2范数的PCA相比，本文所提出的方法计算复杂度正比于样品数量、输入空间的维数和迭代的次数。迭代的次数不依赖于输入空间的维数，该方法对像图像处理那样的高维输入问题具有更好的降维分类和计算性能。L1-规范优化技术是直观的，故相对简单和容易实现。此外，它虽然成功地抑制了异常值，但带来的负面影响是不变的旋转。如何克服这个缺陷是我们下一步的研究工作。摘自：本科毕业论文评语www.udooo.com