范文一:一种快速图像特征降维方法_SPCA
第18卷第3期2005年9月
宁波大学学报(理工版)
J OURNAL OF NI NGBO UN I VERS I TY (NSEE)
Vo. l 18N o . 3
Sep t . 2005
文章编号:1001-5132(2005) 03-0336-04
一种快速图像特征降维方法:SPC A
吴贤伟, 岑 杰, 邰晓英
(宁波大学信息科学与工程学院, 浙江宁波315211)
摘要:讨论了几种图像特征降维算法, 着重介绍了一种简单、快速、性能优越的Si m p le PC A (S i m ple Pri n cipa l Co mponentAnalysis , SPC A ) 算法, 并就SPC A 算法、PC A 算法以及广义H ebb(GHA ) 算法等高维数字图像压缩算法进行了比较实验. 实验结果表明:SPCA 算法在保证压缩性能的前提上, 能
有效提高压缩速度.
关键词:维数约简; 主成分分析(PCA ); 简单主成分分析(SPCA); H ebb 广义算法(GHA ) 中图分类号:TP39 文献标识码:B
SPCA:A Fast D i m ensi onality R eduction M ethod for I m age Feat ure
WU X ian -w e, i CEN Jie , TA I X i a o -y i n g
(F acu lt y of Infor m ation Science &Eng i neer i ng , N i ngbo U n i ve rs i ty , N i ngbo 315211, Chi na)
Abst ract :Severalm ethods for i m age feature d i m ensi o n reduction is i n vesgated , and one particu lar exa mp le , SPCA,
is presented . So m e experi m ents of i m age co m pression are perf o r m ed to co m pare the a l g orithm s , and the results sho w that SPC A is satisfy ing no t only i n perfor m ance , but in speed .
K ey w ords :d i m ensi o na lity reduction ; si m ple pri n cipa l component ana l y sis ; pri n cipa l co m ponent analysis ; genera lized hebb i a n algorithm CLC nu m ber :TP39 Docu m ent code :B
随着问题的越来越复杂化, 高维数据处理也变得越来越重要. 一方面, 高维数据使人难以理解数据之间的关系, 另一方面, 高维数据使得存储、传输、处理变得更加困难. 高维数据处理成了问题解决的瓶颈. 因此, 需要维数约简技术来达到有效降维目的. PC A (主成分分析) 方法就是一种非常有效的降维方法. 在PCA 方法中包括PCA 矩阵、SPCA 、GHA 等多种算法, 本文就这些算法在高维图像特征压缩方面的降维性能进行实验比较, 从而突出说明SPCA 算法的简单、快速, 同时又能保持性能. 尽管如此, SP -C A 对于非线性的高维数据降维往往需要结合其他
收稿日期:2005-03-25.
:(), 男, , , .
一些非线性的算法来使用.
1 PCA(主成分分析)
[1]
主成分分析法PC A (Pri n cipa l Co m ponentA na l y -sis) 是模式识别中的一种非参数方法, 通过采用较少数量的特征对样本进行描述以达到降低特征空间的维数. 它的目标是在低维子空间表示高维数据, 使得在最小均方误差意义下低维表示能够最好地描述原始数据, 从而最终达到降维的目的.
具体来说, 假设有一个n 维的向量x, 希望压缩
第3期 吴贤伟等:一种快速图像特征降维方法:SPCA 337
到k 维, 其中k n. 如果我们简单截断x, 所带来的均方误差等于舍掉的各分量的方差之和. 这就要求存在一个可逆的线性变换T, 使得对T x 的截断在均方误差意义下最优, 显然, 变换后的某些分量具有较低的方差.
对于m n 维的输入矩阵X, 则它可以表示为:
T T T
X =t 1p 1+t 2p 2+ +t k p k +E, (1) 其中k n, t i 称为各主元素(pri n c i p al co m ponent scores), p i 称为主元向量(pri n cipa l co m ponent load -i n g s), E 为X 的剩余部分. 上式等价于:
T
X =TP +E, (2) 主元变量T 则为:
T =XP. (3) 可以证明当p i 取为矩阵X 的协方差矩阵由大到小排列的第i 个特征根所对应的特征向量时, T 的方差达到最大. 每一对t i , p i 都是按照相应于特征向量p i 的特征值 i 的降序排列, 则第一对t 1, p 1获得了所有分解的主元向量和主元系数对中最大的信息量, 其余依此类推.
T
对于主元变量T =(t 1, t 2, , t k ) 有:t k 是X 的线性函数; t k 的方差达到最大使得t k 充分反映X 的变化情况; 同时t k 之间尽量不相关, 即提取出的主元变量不含重复信息.
从统计模式识别的观点来看, 主成分分析实际上是降维处理过程, 它忽略了具有较小方差的线性组成部分, 保留了具有较大方差项, 从而减少了有效数据表示的维数. 然而, 它是一种线性算法, 只能提取数据中的线性相关特征.
根据特征向量的计算方式不同, PCA 方法一般分成两类:一类是矩阵型方法, 另一类是数据型方法. 矩阵型方法就是通过矩阵计算来精确求解特征值和特征向量, 从而得到主元向量. 数据型方法通过数值运算而不是矩阵运算来求得近似主元向量, 最大的优点就是当维数规模增大时, 能很好地解决矩阵运算所遇到的计算效率瓶颈问题.
(3) 计算协方差矩阵C , 其中C ij =(Xi -X ) (Xj
-X )
(4) 由协方差矩阵C 得到特征值 和特征向量 , 根据特征值从大到小排列得到对应的特征向量, 一般只要选择前面的k 个(k n ) 特征向量就能近似表示原始的数据.
下面介绍的GHA 和SPC A 都是数据型PCA 方法.
[3]
2. 2广义Hebb 算法(GHA)
该算法是利用无监督单层神经网络来实现的, 输入为n 个神经元x i , 输出为L 个神经元y i , 突触权值为w ji , 其中n 就是维数, L 为选择的主元个数, i =1, 2 , n , j =1, 2, , L.
具体算法如下:
1) 在时刻t =1时, 初始化网络突触权值w ji , 使其取一个小的随机数, 学习因子 赋给一个小的正数.
2) 对于t =1, j =1, 2, , L 和i =1, 2 , n, 计算y j (t) =i w ji (t) x i (t), =1
j
n
(4)
w ji (t) =y j (t)x i (t) -y j (t) k w ki (t) y k (, (5) =1其中x i (t) 是n 1输入向量X (t) 的第i 个分量, L 是期望的主分量个数.
3) t 增加1(t =t +1) 转入到2), 并继续执行直到w ji 达到稳定.
对于较大的t , 神经元j 的突触值w ji 收敛于输入向量X (t) 的协方差矩阵的第j 个特征值对应特征向量的第i 个分量.
[4, 5]
2. 3简单PCA 算法(SPCA )
SPCA 方法是一种基于数据型的PCA 方法, 类似于H ebb 学习方法, 但不同于H ebb 方法的是:不需要动态调整学习因子, 而且循环次数很少就能达到满意结果, 速度很快. 具体算法如下:
1) 获得具有m 点的原始数据集, 其中点x i 是n 维数据, i =1, 2 , m;
2) 用列向量e i 来表示输入与输出之间的连接权重系数, e 1则是用来近似表示第一主元向量, 其他依次类推.
3) (k =1, 2 )
T
y 1=e 1x i ,
x i y 1 0,
(y 1, x i ) =
0 y 1<0,>0,>
k +1
1
2 降维方法
2. 1PCA 矩阵型算法(简称PCA 算法)
(1) 获得一组原始数据X, 其中X i 是第i 个点, 点本身是n 维的, i =1, 2 , m;
(2) 对于每个点进行中心化:计算平均值X = X i i =1m
[2]
(6) (7) (8)
, 然后每个点都X i -X;
i =0 (y 1, x i ) = i 0(y 1, x i ) m
338宁波大学学报(理工版) 2005
由公式(8) 得到的新的e 1, 来重新计算公式(6) 、(7) 再得到新的e 1, 如此循环多次后得到的e 1便是第一主元向量.
4) 利用下面的公式, 来消除第一主元向量对原始数据的影响, 得到的数据x i 作为求下一主元向量的输入数据.
T
x (9) i =x i -(e 1x i ) e 1
然后再利用公式(6) ~(8) 进行多次循环可以得到下一个主元向量, 再运用公式(9) 对原始数据进行
进一步修正, 又可以进行下一轮的求解过程, 如此下去, 一直得到k 个(k m ) 主元向量为止. 算法的时间复杂度O (n *m *k *t), 其中n 为数据维数, m 为数据样本个数, k 为需要的主元个数, t 为迭代次数.
3 实验
本实验使用的是256 256的Lena 标准灰度图像. 首先把图像进行分块(n 1 n 2块), 则每块为
表1 PCA , SPCA , GHA 算法性能比较表
T ab . 1 P erfor mance comparison of PCA , SPCA and GHA
算法PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA PC A SPCA GHA
256
1/4
1010
32 32
8 8
128
1/8
1010
64
1/16
1010
64
1/4
1010
16 16
16 16
32
1/8
1010
16
1/16
1010
16
1/4
1010
8 8
32 32
8
1/8
1010
4
1/16
1010
分块情况
每一分块
主元个数
压缩率
情况1
次数
时间/s0. 10. 10. 30. 10. 20. 60. 10. 41. 28. 20. 41. 28. 20. 92. 48. 71. 74. 7710. 21. 85. 9712. 43. 525. 1715. 87. 049. 7
PS NR 20. 519. 917. 022. 622. 115. 425. 525. 212. 727. 026. 511. 630. 330. 08. 736. 135. 46. 1177. 9103. 46. 7177. 621. 674. 1177. 413. 80. 9
100100
60. 0506. 7
13. 52. 6
100100
30. 4257. 5
21. 75. 0
100100
15. 360. 8
103. 07. 2
100100
14. 747. 1
35. 411. 5
100100
7. 424. 1
30. 013. 7
100100
3. 711. 9
26. 515. 8
100100
3. 7811. 9
25. 218. 5
100100
1. 96. 0
22. 118. 7
100100
1. 03. 1
20. 018. 6
次数
情况2时间/s
PSNR
注:以上数据中PCA 算法是指PC A 的矩阵型算法, 次数指的是迭代次数, GHA 使用的学习因子为0. 0001. 采用时间(s) 和PSNR (Peak S i gna l to N o ise R ati o ) (db) 来衡量算法的差异. 其中PS NR (db) 指标用来衡量重构后的图像与原图像的相似程1M -1N -1
度. 对于8位二进制图像, PS NR =10 l g 10 [I (i -j ) -I (i , j) ]2, 其中(i , j ) 代表像素点坐标, I (i , j ) 和I (i , j ) 分别表示
MN i =0j =0
原始图像和重建原图像各像素点灰度值, M 、N 表示图像的行列数.
第3期算法
吴贤伟等:一种快速图像特征降维方法:SPCA
8 8分块, 4个主元
16 16分块, 16个主元
32 32分块, 64个主元
339
SPCA
PSNR =19. 9PS NR =26. 5PS NR =103.
4
PC A
矩阵
PSNR =20. 5PS NR =27. 0PS NR =172.
9
图1 在相同压缩率(1/16)下, SPCA 与PCA 矩阵型算法直观性能的比较
F ig . 1 In tu ition istic performance co m parison of SPCA and PCA under the sa m e co mpressi on ra ti o(1/16)
d 1 d 2(其中d 1=256/n1, d 2=256/n2) 像素点, 然
后依次提取每块中的第i 个象素点作为映射后新的(n 1 n 2) 维空间的第i 个点x i (也就是x i 本身是n1 n2维的, 它的第一个分量取自原图像的第一块中的第i 个象素, 它的第二个分量取自原图像的第二块中的第i 个象素, 依次类推), 由此得到一组原始数据x i (其中i =1, 2 , d 1 d 2). 有了这些原始数据后, 分别运用上述3种降维算法, 得到主元向量, 并利用主元向量进行原始图像的重构, 并与原图像进行失真比较.
本实验对原始图像进行了3种不同分块情况(8 8, 16 16, 32 32), 并就每一种分块情况, 取不同主元个数进行了比较实验, 记录了各个算法的时间性能与峰值信号噪比(PSNR ). 同时, 还就SP -C A 和GHA 迭代次数不同分了2种情况, 具体数据请见表1.
通过上述实验数据可以看出, 当分块为16 16, 压缩率为1/16情况下, 情况1的SPCA 的PSNR 为26. 5db , 而PCA 的PSNR 为27db , 两者性能差不多, 但是算法时间大不相同, PCA 算法的时间为8. 2s , 而SPCA 仅为0. 4s , 两者相差20倍. 同样情况下的GHA 算法, PSNR 为11. 6db , 时间为1. 2s , 在性能和时间上也都不如SPC A 算法. 在更高维数的情况下, SPCA 算法速度甚至是PCA 算法速度的几百倍. 上述实验的其他情况, 同样也说明了SPCA ) 能差别不大(直观效果见图1), 更主要是, 当原始数据维数达到较大规模时, 矩阵PCA 算法往往显得难以适应, 即使能计算的话, 它的速度也远不如SPC A 算法的速度. 例如, 在表1中, 分块为32 32时, PCA 的运算时间为700多秒, 而SPC A 仅几秒. 对于GHA 算法, 尽管从理论上讲, GHA 经过无穷多次的迭代, 同时逐渐减小学习因子, 就能无限逼进主元的理论值, 但是从上述的实验结果看来, 在迭代次数相同的情况下, GHA 算法的时间多于SPCA 算法的时间, 而且, 性能远不如SPCA 的性能. 总之, SPC A 算法是这几种降维算法中兼具性能和速度的一种降维算法, 尤其适合于较大维数规模的数据, 同时实时性要求较高的场合. 参考文献:
[1] L i ndsay I S m it h . A tutor i a l on Pr i nc i pa l Co m ponents A-na l ys i s [EB /OL].htt p ://www.cs . otago . ac . nz/
cosc453/student_tutorial s /pri nci pa l_com ponents . pd. f [2] Ian T Jo lliffe . P r i ncipa l Co m ponent A na lysis[M].N ew Y ork :Spri nger V e rlag , 1986. [3] S i m on S H ayki n . N eura l N e t w orks :A Co m prehensi v e F oundati on[M].P ren tice H a l, l 1998. [4] 邰晓英, 北研二. 基于向量空间模型的降维方法[A ].第十三届全国信息存储技术学术会议[C ].西安, 2004. [5] M atthe w Pa rtridge , R afae l A Ca l vo . F ast D i m ens i ona li ty
R educ ti on and S i m ple PCA [J].
sis , 1998, 2(1-4):203-214.
Inte lli gent D ata A na l y -
(
范文二:常见的特征选择或特征降维方法
URL:http://dataunion.org/14072.html
特征选择(排序)对于数据科学家、机器学习从业者来说非常重要。好
的特征选择能够提升模型的性能,更能帮助我们理解数据的特点、底层结构,这对进一步改善模型、算法都有着重要作用。
特征选择主要有两个功能:
1. 减少特征数量、降维,使模型泛化能力更强,减少过拟合
2. 增强对特征和特征值之间的理解
拿到数据集,一个特征选择方法,往往很难同时完成这两个目的。通
常情况下,选择一种自己最熟悉或者最方便的特征选择方法(往往目的是降维,而忽略了对特征和数据理解的目的)。
在许多机器学习的书里,很难找到关于特征选择的内容,因为特征选
择要解决的问题往往被视为机器学习的一种副作用,一般不会单独拿出来讨论。本文将介绍几种常用的特征选择方法,它们各自的优缺点和问题。
1 去掉取值变化小的特征 Removing features with low variance 这应该是最简单的特征选择方法了:假设某种特征的特征值只有0和1,并且在所有输入样本中,95%的实例的该特征取值都是1,那就可以认为这个特征作用不大。如果100%都是1,那这个特征就没意义了。当特征值都是离散型变量的时候这种方法才能用,如果是连续型变量,就需要将连续变量离散化之后才能用,而且实际当中,一般不太会有95%以上都取某个值的特征存在,所以这种方法虽然简单但是不太好用。可以把它作为特征选择的预处理,先去掉那些取值变化小的特征,然后再从接下来提到的特征选择方法中选择合适的进行进一步的特征选择。
2 单变量特征选择 Univariate feature selection
单变量特征选择能够对每一个特征进行测试,衡量该特征和响应变量
之间的关系,根据得分扔掉不好的特征。对于回归和分类问题可以采用卡方检验等方式对特征进行测试。 这种方法比较简单,易于运行,易于理解,通常对于理解数据有较好
的效果(但对特征优化、提高泛化能力来说不一定有效);这种方法有许多改进的版本、变种。
2.1 Pearson相关系数 Pearson Correlation 皮尔森相关系数是一种最简单的,能帮助理解特征和响应变量之间关
系的方法,该方法衡量的是变量之间的线性相关性,结果的取值区间为[-1,1],-1表示完全的负相关(这个变量下降,那个就会上升),+1表示完全的正相关,0表示没有线性相关。
Pearson Correlation速度快、易于计算,经常在拿到数据(经过清洗和特征提取之后的)之后第一时间就执行。
Pearson相关系数的一个明显缺陷是,作为特征排序机制,他只对线性关系敏感。如果关系是非线性的,即便两个变量具有一一对应的关系,Pearson相关性也可能会接近0。
2.2 互信息和最大信息系数 Mutual information and maximal information coefficient (MIC)
以上就是经典的互信息公式了。想把互信息直接用于特征选择其实不
是太方便:1、它不属于度量方式,也没有办法归一化,在不同数据及上的结果无法做比较;2、对于连续变量的计算不是很方便(X和Y都是集合,x,
y都是离散的取值),通常变量需要先离散化,而互信息的结果对离散化的方式很敏感。
最大信息系数克服了这两个问题。它首先寻找一种最优的离散化方式,然后把互信息取值转换成一种度量方式,取值区间在[0,1]。minepy提供了MIC功能。
2.3 距离相关系数 (Distance correlation) 距离相关系数是为了克服Pearson相关系数的弱点而生的。在x和x^2这个例子中,即便Pearson相关系数是0,我们也不能断定这两个变量是独立的(有可能是非线性相关);但如果距离相关系数是0,那么我们就可以说这两个变量是独立的。
尽管有MIC和距离相关系数在了,但当变量之间的关系接近线性相关
的时候,Pearson相关系数仍然是不可替代的。第一、Pearson相关系数计算速度快,这在处理大规模数据的时候很重要。第二、Pearson相关系数的取值区间是[-1,1],而MIC和距离相关系数都是[0,1]。这个特点使得Pearson相关系数能够表征更丰富的关系,符号表示关系的正负,绝对值能够表示强度。当然,Pearson相关性有效的前提是两个变量的变化关系是单调的。
2.4 基于学习模型的特征排序 (Model based ranking)
这种方法的思路是直接使用你要用的机器学习算法,针对每个单独的
特征和响应变量建立预测模型。其实Pearson相关系数等价于线性回归里的标准化回归系数。假如某个特征和响应变量之间的关系是非线性的,可以用基于树的方法(决策树、随机森林)、或者扩展的线性模型等。基于树的方法比较易于使用,因为他们对非线性关系的建模比较好,并且不需要太多的调试。但要注意过拟合问题,因此树的深度最好不要太大,再就是运用交叉验证。
3 线性模型和正则化 单变量特征选择方法独立的衡量每个特征与响应变量之间的关系,另一种主流的特征选择方法是基于机器学习模型的方法。有些机器学习方法本身就具有对特征进行打分的机制,或者很容易将其运用到特征选择任务中,例如回归模型,SVM,决策树,随机森林等等。说句题外话,这种方法好像在一些地方叫做wrapper类型,大概意思是说,特征排序模型和机器学习模型是耦盒在一起的,对应的非wrapper类型的特征选择方法叫做filter类型。
下面将介绍如何用回归模型的系数来选择特征。越是重要的特征在模型中对应的系数就会越大,而跟输出变量越是无关的特征对应的系数就会越接近于0。在噪音不多的数据上,或者是数据量远远大于特征数的数据上,如果特征之间相对来说是比较独立的,那么即便是运用最简单的线性回归模型也一样能取得非常好的效果。
在这个例子当中,尽管数据中存在一些噪音,但这种特征选择模型仍然能够很好的体现出数据的底层结构。当然这也是因为例子中的这个问题非常适合用线性模型来解:特征和响应变量之间全都是线性关系,并且特征之间均是独立的。
3.1 正则化模型
正则化就是把额外的约束或者惩罚项加到已有模型(损失函数)上,以防止过拟合并提高泛化能力。损失函数由原来的E(X,Y)变为
E(X,Y)+alpha||w||,w是模型系数组成的向量(有些地方也叫参数
parameter,coefficients),||·||一般是L1或者L2范数,alpha是一个可调的参数,控制着正则化的强度。当用在线性模型上时,L1正则化和L2正则化也称为Lasso和Ridge。
3.2 L1正则化/Lasso L1正则化将系数w的l1范数作为惩罚项加到损失函数上,由于正则项非零,这就迫使那些弱的特征所对应的系数变成0。因此L1正则化往往会使学到的模型很稀疏(系数w经常为0),这个特性使得L1正则化成为一种很好的特征选择方法。
Scikit-learn为线性回归提供了Lasso,为分类提供了L1逻辑回归。 下面的例子在波士顿房价数据上运行了Lasso,其中参数alpha是通过grid search进行优化的。
可以看到,很多特征的系数都是0。如果继续增加alpha的值,得到的模型就会越来越稀疏,即越来越多的特征系数会变成0。
然而,L1正则化像非正则化线性模型一样也是不稳定的,如果特征集合中具有相关联的特征,当数据发生细微变化时也有可能导致很大的模型差异。
3.3 L2正则化/Ridge regression L2正则化将系数向量的L2范数添加到了损失函数中。由于L2惩罚项中系数是二次方的,这使得L2和L1有着诸多差异,最明显的一点就是,L2正则化会让系数的取值变得平均。对于关联特征,这意味着他们能够获得更相近的对应系数。还是以Y=X1+X2为例,假设X1和X2具有很强的关联,如果用L1正则化,不论学到的模型是Y=X1+X2还是Y=2X1,惩罚都是一样的,都是2alpha。但是对于L2来说,第一个模型的惩罚项是2alpha,但第二个模型的是4*alpha。可以看出,系数之和为常数时,各系数相等时惩罚是最小的,所以才有了L2会让各个系数趋于相同的特点。
可以看出,L2正则化对于特征选择来说一种稳定的模型,不像L1正则化那样,系数会因为细微的数据变化而波动。所以L2正则化和L1正则化提供的价值是不同的,L2正则化对于特征理解来说更加有用:表示能力强的特征对应的系数是非零。
回过头来看看3个互相关联的特征的例子,分别以10个不同的种子随机初始化运行10次,来观察L1和L2正则化的稳定性。
4 随机森林
随机森林具有准确率高、鲁棒性好、易于使用等优点,这使得它成为
了目前最流行的机器学习算法之一。随机森林提供了两种特征选择的方法:mean decrease impurity和mean decrease accuracy。
4.1 平均不纯度减少 mean decrease impurity 随机森林由多个决策树构成。决策树中的每一个节点都是关于某个特
征的条件,为的是将数据集按照不同的响应变量一分为二。利用不纯度可以确定节点(最优条件),对于分类问题,通常采用基尼不纯度或者信息增益,对于回归问题,通常采用的是方差或者最小二乘拟合。当训练决策树的时候,可以计算出每个特征减少了多少树的不纯度。对于一个决策树森林来说,可以算出每个特征平均减少了多少不纯度,并把它平均减少的不纯度作为特征选择的值。
4.2 平均精确率减少 Mean decrease accuracy
另一种常用的特征选择方法就是直接度量每个特征对模型精确率的影
响。主要思路是打乱每个特征的特征值顺序,并且度量顺序变动对模型的精确率的影响。很明显,对于不重要的变量来说,打乱顺序对模型的精确率影响不会太大,但是对于重要的变量来说,打乱顺序就会降低模型的精确率。
5 两种顶层特征选择算法
之所以叫做顶层,是因为他们都是建立在基于模型的特征选择方法基
础之上的,例如回归和SVM,在不同的子集上建立模型,然后汇总最终确定特征得分。
5.1 稳定性选择 Stability selection 稳定性选择是一种基于二次抽样和选择算法相结合较新的方法,选择算法可以是回归、SVM或其他类似的方法。它的主要思想是在不同的数据子集和特征子集上运行特征选择算法,不断的重复,最终汇总特征选择结果,比如可以统计某个特征被认为是重要特征的频率(被选为重要特征的次数除以它所在的子集被测试的次数)。理想情况下,重要特征的得分会接近100%。稍微弱一点的特征得分会是非0的数,而最无用的特征得分将会接近于0。
5.2 递归特征消除 Recursive feature elimination (RFE) 递归特征消除的主要思想是反复的构建模型(如SVM或者回归模型)然后选出最好的(或者最差的)的特征(可以根据系数来选),把选出来的特征放到一遍,然后在剩余的特征上重复这个过程,直到所有特征都遍历了。这个过程中特征被消除的次序就是特征的排序。因此,这是一种寻找最优特征子集的贪心算法。
RFE的稳定性很大程度上取决于在迭代的时候底层用哪种模型。例如,假如RFE采用的普通的回归,没有经过正则化的回归是不稳定的,那么RFE就是不稳定的;假如采用的是Ridge,而用Ridge正则化的回归是稳定的,那么RFE就是稳定的。
Sklearn提供了RFE包,可以用于特征消除,还提供了RFECV,可以通过交叉验证来对的特征进行排序。
特征之间存在线性关联关系,每个特征都是独立评价的,因此X1,?X4的得分和X11,?X14的得分非常接近,而噪音特征X5,?,X10正如预期的那样和响应变量之间几乎没有关系。由于变量X3是二次的,因此X3和响应变量之间看不出有关系(除了MIC之外,其他方法都找不到关系)。这种方法能够衡量出特征和响应变量之间的线性关系,但若想选出优质特征
来提升模型的泛化能力,这种方法就不是特别给力了,因为所有的优质特征都不可避免的会被挑出来两次。
Lasso能够挑出一些优质特征,同时让其他特征的系数趋于0。当如需要减少特征数的时候它很有用,但是对于数据理解来说不是很好用。(例如在结果表中,X11,X12,X13的得分都是0,好像他们跟输出变量之间没有很强的联系,但实际上不是这样的)
MIC对特征一视同仁,这一点上和关联系数有点像,另外,它能够找出X3和响应变量之间的非线性关系。
随机森林基于不纯度的排序结果非常鲜明,在得分最高的几个特征之
后的特征,得分急剧的下降。从表中可以看到,得分第三的特征比第一的小4倍。而其他的特征选择算法就没有下降的这么剧烈。
Ridge将回归系数均匀的分摊到各个关联变量上,从表中可以看出,
X11,?,X14和X1,?,X4的得分非常接近。
稳定性选择常常是一种既能够有助于理解数据又能够挑出优质特征的
这种选择,在结果表中就能很好的看出。像Lasso一样,它能找到那些性能比较好的特征(X1,X2,X4,X5),同时,与这些特征关联度很强的变量也得到了较高的得分。
总结
1. 对于理解数据、数据的结构、特点来说,单变量特征选择是个非常好的选择。尽管可以用它对特征进行排序来优化模型,但由于它不能发现冗余(例如假如一个特征子集,其中的特征之间具有很强的关联,那么从中选择最优的特征时就很难考虑到冗余的问题。
2. 正则化的线性模型对于特征理解和特征选择来说是非常强大的工具。L1正则化能够生成稀疏的模型,对于选择特征子集来说非常有用;相比起L1正则化,L2正则化的表现更加稳定,由于有用的特征往往对应系数非零,因此L2正则化对于数据的理解来说很合适。由于响应变量和特征之间往往是非线性关系,可以采用basis expansion的方式将特征转换到一个更加合适的空间当中,在此基础上再考虑运用简单的线性模型。
3. 随机森林是一种非常流行的特征选择方法,它易于使用,一般不需要feature engineering、调整参数等繁琐的步骤,并且很多工具包都提供了平均不纯度下降方法。它的两个主要问题,1是重要的特征有可能得分很低(关联特征问题),2是这种方法对特征变量类别多的特征越有利(偏向问题)。尽管如此,这种方法仍然非常值得在你的应用中试一试。
4. 特征选择在很多机器学习和数据挖掘场景中都是非常有用的。在使用的时候要弄清楚自己的目标是什么,然后找到哪种方法适用于自己的任务。当选择最优特征以提升模型性
能的时候,可以采用交叉验证的方法来验证某种方法是否比其他方法要好。当用特征选择的方法来理解数据的时候要留心,特征选择模型的稳定性非常重要,稳定性差的模型很容易就会导致错误的结论。对数据进行二次采样然后在子集上运行特征选择算法能够有所帮助,如果在各个子集上的结果是一致的,那就可以说在这个数据集上得出来的结论是可信的,可以用这种特征选择模型的结果来理解数据。
Tips 什么是卡方检验?用方差来衡量某个观测频率和理论频率之间差异性的方法
什么是皮尔森卡方检验?这是一种最常用的卡方检验方法,它有两个用途:1是计算某个变量对某种分布的拟合程度,2是根据两个观测变量的Contingency table来计算这两个变量是否是独立的。主要有三个步骤:第一步用方差和的方式来计算观测频率和理论频率之间卡方值;第二步算出卡方检验的自由度(行数-1乘以列数-1);第三步比较卡方值和对应自由度的卡方分布,判断显著性。
什么是p-value?简单地说,p-value就是为了验证假设和实际之间一致性的统计学意义的值,即假设检验。有些地方叫右尾概率,根据卡方值和自由度可以算出一个固定的p-value,
什么是响应变量(response value)?简单地说,模型的输入叫做
explanatroy variables,模型的输出叫做response variables,其实就是要验证该特征对结果造成了什么样的影响
什么是统计能力(statistical power)?
什么是度量(metric)?
什么是零假设(null hypothesis)?在相关性检验中,一般会取“两者之间无关联”作为零假设,而在独立性检验中,一般会取“两者之间是独立”作为零假设。与零假设相对的是备择假设(对立假设),即希望证明是正确的另一种可能。
什么是多重共线性?
什么是grid search?
范文三:降维方法
国内当前流行的文本分类算法有最大熵(MaximumEntropy,ME ),K 近邻法(KNN),朴素贝叶斯法(NB ) ,支持向量机法(SVM),线性最小平分拟合法(LLSF),神经网络法(Nnet)等,其中KNN 、NB 和SVM 的分类效果相对较好。
文本分类由文本表示,特征降维和分类器训练组成,分类算法只是其中的一个环节,另外两个环节也非常重要。目前普遍采用向量空间模型来表示文本,常见的特征词加权方法有:布尔权重、词频权重、TF —IDF 权重等,常见的特征选择方法有文档频率,互信息和统计等。
基于机器学习文本分类的基础技术由文本的表示(representation) 、分类方法及效果(effectiveness)评估3 部分组成。Sebastiani 对文本分类发展历程及当时的技术进行了总结,主要内容包括:
(1) 文本关于项(term)或特征的向量空间表示模型(VSM)及特征选择(selection)与特征提取(extraction)两种表示空间降维(dimensionality reduction) 策略, 讨论了χ2,IG,MI,OR 等用于特征过滤的显著性统计量及项聚类和隐含语义索引(LSI)等特征提取方法;
(2) 当时较成熟的分类模型方法, 即分类器的归纳构造(inductive construction) 或模型的挖掘学习过程;
(3) 分类效果评估指标, 如正确率(precision) 召回率(recall) 均衡点(BEP) F β(常用F1) 和精度(accuracy)等, 以及之前报道的在Reuters 等基准语料上的效果参考比较。
1、 中文评论语料的采集
利用 DOM 构建网页结构树,对结构树的分析实现了中文评论的自动采集的方
法。以及对情感语料进行情感标注,利用中文分词技术对情感语料进行分词等基础性研究。
2、 情感词典的构建
利用 PMI 算法,在基础情感词典和中文宾馆评论语料库的基础上构建宾馆评论领域情感词典的方法。
3、 文本处理中的特征选择、特征权值和向量表示
CHI 统计方法和采用情感词典作为情感特征选择的方法,以及降维的维度选择等相关问题。研究了 3 种特征权值计算方法和特征权值的意义,以及使用矩阵文本表示文本向量的方法。
4、 朴素贝叶斯分类器的构建
研究如何利用朴素贝叶斯方法构建中文文本情感分类器,估计先验概率和后验概率的方法,以及后验概率平滑技术参数设置等问题。实验对比了不同方法构建的分类器的性能,并进行了相关分析。
5、 朴素贝叶斯文本情感分类实验系统的设计与实现
开发了一个基于朴素贝叶斯的中文文本情感分类器,简要介绍了其系统构架、主要功能和工作流程,这个分类器是本文进行分类实验所使用的分类器。 语料的中文分词处理
虽然表示语言的最小粒度是字,但单个字并不能代表所有的语义,一般认为可表示语义的最小粒度为词。本文使用了传统的最大匹配算法对语料库中的中文文本进行分词,该方法属于基于字符串匹配的分词方法,需要分词词典支持。分词词典采用了国家语言文字工作委员会发布的《现代汉语常用词表(草案) 》
(LCWCC)[49],该词典搜集了现在日常生活中使用频率较高的 56008 个词汇,基本能够满足分词的需要。在特征选择步骤,本文采用了情感词典作为特征选择的依据,所以在分词时,实际是采用了 LCWCC 和情感词典的并集作为了分词词典。其中最大匹配的步长设置为 4 个汉字,只对中文内容进行分词处理。
用统计的方法对文本进行分类的关键步骤可以分为以下几步:
1) 文本表示
2) 文本的特征选择
3) 特征对分类的贡献度量计算
4) 分类算法选择
文本的表示
文本表示模型主要有布尔模型,向量空间模型和概率模型,最常用的是向量空间模型。
在向量空间模型中,每个文本都被表示为一组规范化正交特征矢量所组成的空间向量的一个点。该向量中每一维的值表示了一该特征项在文本中的权重。也就是说向量空间模型将文本特征集视为一个高维的空间,特征集中的每一个元素t ,都是高维空间中的一维,文档在该维上的值为哄这样一篇文档就表示成在特征向量空间上的一个向量。向量空间模型中向量间的相似程度可以根据向量之间的夹角大小来反映。在实际应用中常常通过计算向量夹角的余弦来得到相似度。
虽然空间向量模型是一个很好的模型但它也存在着不容忽视的缺点,集合是没有顺序的概念的,所以用空间向量模型来表示文本时丢掉了许多除词的信息以
外的所有重要的信息,比如词语与词语之间的相对位置关系、上下文信息等。在语言中这种关系通常含有重要的意义。例如:
“联合国/n维和部队/n遭到八反/d政府/n武装/nv人员/n袭击/v” “反/d政府/n武装/nv人员/n遭到八联合国/n维和部队/n袭击八” 这两句话用空间向量模型来表示是等价的,但恰恰相反这两句话意思完全不同。这使得向量空间模型所能表达的信息量存在上限,也直接导致了基于这种模型构建的文本分类系统,很难达到人类的分类能力。
文本特征提取 如何有效的降低维数并尽可能的减少噪声数据对分类效果的影响是文本特征提取的关键问题。对于大量的文本在分词后的词汇量是数以万计或者更高的,在分类器中这就表现为数以万计的维数。要处理这么多的数据,需要大量的时间,在对时间复杂度要求较高的系统(比如:在线服务的系统) 中这是无法忍受的。这就要求所选用的分类器时间复杂度要低,尽可能的做到线性,但这是不现实的因为现有的机器学习分类算法很少有随着数据维数的增长时间线性增长的,这种非线性增长对海量数据而是就造成了所谓的“维数灾难”。所以有效的降低数据维数,去除噪音数据是数据降维的主要目的。在文本分类中常用特征选择来进行降维,选取那些对分类贡献高的词作为特征丢掉噪声和对分类贡献低的词。 特征的选取可以有基于人工的方式和基于统计学的方式。基于人工的方式也就是人工选择那种重要的词来作为特征,这需要一定的经验。而基于统计学的方式又可以分为:基于文档频率的特征选择法,信息增益法,χ2统计量等多种方法。国内外很多学者对各种特征选择方法进行研究。结果表明在英文文本分类中表现
比较好的方法在不加修正的情况下,并不适合中文文本分类。
分类器
经过许多学者的努力提出了一些经典的算法。比如:Rocchio算法、K 近邻算法(KNN)、贝叶斯分类器、支持向量机、最大嫡、决策树、人工神经网络等。和规则的方法相比统计的方法需要有较强的数学基础,但是统计的方法在普适性方面要比规则的方法要好。
1) Rocchio 算法
Rocchio 算法的基本思想是使用训练语料为每个类别构造一个原型向量。构造的过程如下:给定一个类,训练集中所有属于这个类加的分量用正数表示,所有不属于这个类别的文档对应向量的分量用负数表示,然后把所有的向量加起来,得到的和向量就是这个类的原型向量,定义两个向量的相似度为两个向量夹角的余弦,逐一计算训练集中所有文档所表示成的向量和原形向量之间的相似度,然后按一定的算法从中挑选某个相似度作为闽值。给定一篇文档与原型向量的相似度较大,则这篇文档属于这个类别,否则这篇文档不属于这个类别。
Rocchio 算法的突出优点就是容易实现,并且计算特别简单,它通常用来实现衡量分类系统性能的对比系统,而实际应用的分类系统很少采用这种算法解决具体的分类问题。
2) K 近邻算法
KNN(KNearestNeighbors,KNN) 原理是计算每个样本数据到待分类数据的距离。KNN 算法又叫k 最近邻方法,总体来说KNN 算法是相对比较容易理解的算法之一,它通过计算待分类文档与所有训练文档的距离来进行分类的。假
设每一个类包含多个样本数据,而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类,KNN 就是计算每个样本数据到待分类数据的距离,取和待分类文本最近的K 各样本数据,那么这K 个样本数据中哪个类别的样本数据占多数,则待分类数据就属于该类别。具体的算法步骤如下:
<1>根据特征集将训练文本表示成向量
<2>用类似于第1) 步的方法将待测文本也表示成向量
<3>选取K 个与待测文本相似度最大的训练文本,相似度计算公式为
:
其中,K 是经验值并不固定,需要在实验中反复试验,以求效果在测试集上效果达到最佳。
<4>在新文本的K 个近邻中,依据的算法确定待分类文本的类别。
3) 贝叶斯分类器
朴素贝叶斯是贝叶斯方法中使用最为普遍的一种。作为一种简单而有效的概率分类器,朴素贝叶斯分类器被广泛应用文本分类中,并且取得了不错的效果。朴素贝叶斯分类算法假设构成文本d 的多个特征之间相互独立。可以通过先验概率和类别的条件概率来估计文档d 对类别c ,的后验概率,以实现对文档d 所属类别的判断。由于文本的多个特征之间相互独立,对每个参数就可以分别估计,这样就大大简化了计算,使它尤其适合属性数量非常大的文本分类问题。
尽管词语在文本中的分布是条件独立的朴素贝叶斯假设在实际语一言中并不成立。然而朴素贝叶斯分类器在实际应用中却能够取得良好的效果。
4) 支持向量机
支持向量机SVM 是由Vapnik 领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术。支持向量机是在统计学习理论框架下产生的一种机器学习算法。它建立在统计学习理论的VC 维理论和结构风险最小化原理的基础上,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以获得最好的推广能力。
SVM 在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,现在己经在许多领域(生物信息学,文本和手写识别等) 都取得了成功的应用。
SVM 是从线性可分情况下的最优分类超平面发展而来的,其基本思想可用图1的二维平面的情况来说明。
在多维的情况下支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。
假设数据点是n 维实空间中的点。我们希望能够把这些点通过一个n-1维的超平面分开。我们希望找到最佳的分类平面,即使得属于两个不同类别的数据点间隔最大的那个超平面,该超平面亦称为最大间隔超平面。
范文四:基于多元图形特征融合原理的降维方法研究
第 32卷 第 5期 燕山大学学报 V ol. 32No. 52008年 9月
Journal of Y anshan University Sept. 2008
0引言
高维数据降维是许多学科面临的实际问题, 如 何采用合理的方法对原始数据进行降维, 以最小信 息损失得到更多的原始数据信息成为重要的学术 问题。目前,各个领域研究的问题进入到复杂系 统。研究对象,如基因表达数据、医学影像分析、 时间序列分析等,提供了有关客观现象的极其丰 富、
详细的信息。 但是, 给随后的数据处理工作带 来了前所未有的困难:数据容量急剧增加, 计算时 间复杂度呈指数型增长。 另外, 高维空间中的数据 分布是“稀疏的” 。这使得以距离为基础的传统判 断方法如
近邻法等方法失效。因此,面
对高维数据, 将数据的维数降低, 这样的做法是非 常有用甚至是必须的 [1-3]
。在当代科学各个领域面
临越来越多的需要处理的高维数据时, 如何表示高 维数据、 如何有效地获得相关数据的信息是急需解 决的难题, 具有重要的理论与应用价值,
正引起越 来越多的关注 [4
]。
降维是将高维模式映射到低维子空间的过程,
通常用于可视化或作为分类的预处理步骤。 可以将 降维过程表示为 =, 这里, ,
?éò?ê???D??ò·???D?ó3é?oˉêy£?ò2?éò??a?à???ò
·??à????·¨
[5-6]
。降维的核心问题是通过优化准则
寻找最优的
1
,
,
共
, 个, 整个高维数据集合可以表示为矩
阵 ,其中 , =1, 2,
。传统方法可以处理的情况是
10
μ??é??£?′?í3′|àí·?·¨2??üè?μ?àí??μ?·?
àà?á1??£?úì??÷??êy???àμ??é????£???éùì??÷??êyò???éù?ú′??oμ££??ó?ì?????ù?è£?ìá??D§?ê£?ê?×??ˉ·?àà?Dμ???òaê????£í¨3£ê???????êy?Y??êy?μμíμ?2维或 3维, 然后用可视化工具来展示数据分布 的情况, 这里称为先降后图的处理方式; 与此相反 的是先把高维数据用可视化的工具展示出来, 再用 合理的算法实现基于可视化的降维处理, 这就是先 图后降的处理方式, 如图 1所示。 本文提出基于图
形特征融合思想的先图后降的方法。
文章编号:1007-791X (2008) 05-0445-06
基于多元图形特征融合原理的降维方法研究
孟
辉 1,洪文学 1,宋佳霖 1,王立强 2
(1. 燕山大学 电气工程学院,河北 秦皇岛 066004; 2. 燕山大学 车辆与能源学院,河北 秦皇岛 066004) 摘 要:降维是将高维模式映射到低维子空间的过程。 在降维后的低维子空间进行分类往往能得到更好的效果。 本文以高维数据为研究对象,采用多元描述图对高维数据进行可视化表达,采用多元图图形特征融合的方法对 高维数据进行降维,用
446燕山大学学报 2008
图 1高维数据集不同处理过程
Fig. 1Differential processing methods of high dimensional
data
1.2高维数据到多元图表示域的映射模型 为了建立高维数据和多元图之间的映射关系,
构建了高维数据域与多元图表示域映射关系模型, 如图 2。
图 2高维数据到多元图表示域的映射模型 Fig. 2Mapping model from high dimensional
data to multivariate
从图 2可以清楚看出, 高维数据与多元图之间 的映射关系是由 3个域——数据域、 映射域、 多元 图表示域和 4个变换器——数据变换器、映射器、 多元图变换器、逆映射器组成。
数据变换器是在数据域间实现数据 /数据的变 换(比如数据的预处理)
。映射器功能是将维数为
的多元图。图变换器功能
是实现不同类型多元图之间的变换。 逆映射器功能 是将图形映射到数据域表示的图形类型或图形的 特征参数的数据表示。
这里给出的模型重要性在于建立了高维数据 与多元图之间的映射关系。
设 待 处理 的 样 本 的集 合 一 般表 示 形
式为
1
,
2
,
1,
,降维后的数
据集的维数为
=1:高维数据的单一变量表示; 2
) :高维数据的降维表示; 3
)
:高维数据的全息表示。
从映射的角度,可以对以上关系做如下解释:设 *=
, 为
为间隔
尺度,
1
,
上的点 *:
当
=
=0
1e
(1)
当 1
时,有
*
=
+1
2
2*
=
=
+12
*
=
1
1e
1, 1
=
*
=(3)
2
)标准化变换:
*
=(5)
4)极差正规化(归一化
)变换:
第 5期 孟 辉 等 基于多元图形特征融合原理的降维方法研究 447
5)
对数变换:
(
,
, =1,2,
为样品数为
=
1
=1
表示
均 值, =
=1,
2,
min ,
表示极差。
另外,如果
量化为数值型信息,以便统一进行处
理, 可以根据具体的情况采取合适的预处理方法。 本文采用归一化方法, 从统计学上讲, 归一化预处 理可使类间距增大, 类内距离减小, 有利于对象的 分类表述。
2基于图形特征融合的高维数据降维方法
在模式识别和信息处理中, 高维数据的处理是 一个比较棘手的问题, 降维是处理的首选方法, 它 作为分类的一个预处理步骤, 能够提高分类性能。 有两类主要的降维方法:特征选择和特征提取。 特 征选择是从一组特征中挑选出一些最有效的特征 以达到降低特征空间维数的目的; 特征提取是通过 映射 (或变换) 的方法将高维数据在低维空间来表 示样本的过程。
特征选择是根据某种准则(如信息度量) ,从 原始特征集中挑选若干(通常为数量最小 )特征, 并不生成新特征。 特征提取方法与特征选择最大的 不同点在于要进行数据变换, 通常是应用某种映射 函数将数据从 维新的特征空
间(
) 。特征选择和特征提取最核心的任务是
从众多特征中找出那些最有代表性、最有效的特 征,并舍弃一些冗余变量,进行有效分类。
比较特征选择和特征提取可知:特征选择方法 的可解释性较强, 而特征提取较多的利用了原始信 息。 为了充分融合两者的优势, 提出将特征选择和 特征提取相融合的方法,如图 3。对变量按重要性 和贡献率进行划分, 选择重要的特征变量进行直接 利用, 不重要的特征变量进行映射变换, 提取出一 个或两个新的特征。
可视化是帮助用户理解和分析数据的很好的
方法。 通过将数据分布可视化, 专家可以应用专业 知识发现感兴趣的聚类。 然而, 将高维数据映射到 可视化的 2维或 3维空间, 同时保持数据的距离信 息是很难的。 雷达图是表示多元数据的一种较好的 形式, 通常被广泛用于简单模式的比较。 这里用雷 达图的功能扩展,将其作为降维和分类的工具。
图 3融合特征选择与特征提取的方法
Fig. 3Method of feature selection and feature extraction
2.1雷达图表示原理
通常,笛卡儿坐标只能表示 2维或 3维数据, 而雷达图能表示 3~10维的数据。传统的雷达图绘 制步骤为:首先,作一个圆,并把圆周
条半径依次定义为各
指标的坐标轴, 并标以适当的刻度; 最后, 对给定 的一次观测值把
边形。 这个
边形,通过图形表现数据的特征。
为进一步挖掘雷达图图形特点, 对雷达图进行 规范化,如图 4所示(以 7变量为例) 。定义外围 圆周上的坐标为周坐标(
) , 圆心到圆周 的方向为变量幅值增加的方向,变量需归一化到 [0,1];定义相邻变量的夹角为
=
,
将原始数据映射到雷达图上,
其中 反映根据变量物理意
义的近似程度或者重要性来分配的变量周坐标的
位置。 2.2
雷达图的图形特征
传统模式识别中, 特征通常包括物理特征, 数 学特征和结构特征。 本文提出一种新的特征:图形
原始数据
特征选择
特征提取
特征集
特征融合
448燕山大学学报 2008
特征。寻找合适的图形特征对分类结果有重要影 响。 对雷达图, 图形特征可以是变量的最大值或最 小值、变量间的角度、多边形形状、多边形面积 等。雷达图的一些重要特征如图 5所示。
图 4标准化雷达图表示原理 Fig. 4Star plot after standardized
图 5雷达图的一些重要特征 Fig. 5Several graphical features of star plot
图形特征对判别类别有其独特的特性。例如, 如果多边形的形状不同或最大变量的方向不同或 多边形面积不同, 则意味着雷达图所表示的类别不 同。
提取图形特征的目的可以分为:①当待分析样 本的变量(维数 )较少时, 可以将提取的图形特征 作为新的变量, 重新加入的原始样本中, 属于增维
的范畴, 这样使一些模式识别算法更有效地对样本 进行分类与识别;②当待分析的样本的变量(维 数 )较多时, 提取图形特征有利于排除对总体分类 贡献小的变量, 将提取的图形特征作为样本的新变 量来处理, 这样可以大大降低算法的运行时间, 而 且保证算法的分类精度与效果, 这种处理方法属于 降维的范畴。 2.3
雷达图的图形特征融合
某些情况下,需要处理的数据集的维数很高,
结构很复杂, 只用一两个图形特征很难取得好的分 类效果。本文提出递阶多层图形特征融合的方法, 如图 6所示。
图 6基于雷达图的递阶多层图形特征融合的方法
Fig. 6Framework of hierarchical multi-layer structure based
on graphical feature fusion of star plot
采用雷达图作为数据融合与信息表达的工具,
辅以数据预处理, 信息重要性检验, 非等间距切分 等方法来对超高维的质谱或基因表达数据进行降 维分析, 最终降到何种维数, 以方便进行分类为目 的, 既要保证分类的精确度, 又要考虑到计算代价 等条件的约束。具体如下:
1)对数据集合进行变量的重要性分析,确定 对象中的无关变量信息, 这样就可以直接排除此类 信息中和分类无关的信息。 然后, 对有意义的信息 段进行非等间距切分;
2)从划分后的各个区间中提取图形特征,将
提取的多个特征作为这个区间的特征表述;
3)将每个区间中提取的图形特征作为雷达图 的变量来绘制雷达图, 按照划分区间的数目, 可以 得到同样数量的雷达图, 将这些雷达图作为整个高
维数据在特征空间的描述;
4)如果上一步骤得到的雷达图数目较少,则 可以从这些雷达图中提取图形特征, 并将这些特征 融合得到一个雷达图, 作为这个数据集的表达。 如 果得到的雷达图的数目较多, 则从每个雷达图中提 取图形特征, 作为下一级雷达图的输入特征, 直到 最后的特征数目满足分类器或者其他分析方法的 要求为止, 也可以在进行多级融合后用一个变量较
变量 6
3
2
×?′ó?μ
í?D?ì??÷
1
2
与
2
夹角
第 5期 孟 辉 等 基于多元图形特征融合原理的降维方法研究 449
多的雷达图来描述整个数据集的特性。 3实验分析
使用机器学习数据集中的卫星图像数据作为 研究对象。 数据集下载自 http://disl.cc.gatech.edu/VISTA/demo_main.html。数据集包括 3×3模板的
卫星图像多光谱像素值, 以及根据每一模板的中心 值进行的分类情况。 目标为根据给定的多光谱像素 值预测其类别。 在给出的数据集中, 类别用数字表 示。类别 1为红色土壤, 类别 2为棉花地,类别 3为灰色土壤, 类别 4为潮湿的灰色土壤, 类别 5为 蔬菜地, 类别 6为很湿的灰色土壤。 数据的顺序是 任意的, 并且去除了一些数据行, 因此不能从这个 数据集重构原始图像。 这个数据集的维数为 36维。 数据集中的 6类变量为数值型,数值范围为 [0,255]。数据集包括 6435个样本,任意抽取其中 的 4435个样本作为训练集,其余的 2000个样本 作为测试集。
数据处理过程包括数据预处理、 数据分割、 特 征选择与提取、特征融合。主要步骤如下:
1)分别绘出原始 6类、 36维数据的雷达图, 如图 7所示。从图 7中可以看出,只有类别 2的 多边形形状与其他类别很不相似;
图 7卫星图像数据集的类别均值雷达图 Fig. 7Star plot of original thirty-six dimensional data
2)为了增强不同类别的差异,使用归一化变 换方法。经过归一化的雷达图如图 8所示。类别 5的形状也与其他类别明显不同。 但是其他四个类别 的多边形形状仍然很相似,不易对它们进行分类;
3)因为很难对整个数据集应用雷达图得到很 好的分类效果, 推测将每类数据分割后再提取图形 特征,可能会对分类有帮助。将 36维数据平均分
割成 3组。 绘制分组后的雷达图如图 9所示。 从图 9可以看出,每一类的 3个雷达图的形状很相似, 这是由数据集的特性导致的, 不具有通用性。 通过 分析, 选择两个直接的图形特征:最大值、 最大值 与水平方向的夹角, 提取了一个图形特征:多边形 面积。 将每一类的 3个雷达图中的这 3个特征绘制 在一个雷达图中, 因此, 新的雷达图的变量数为 9;
图 8标准化后的卫星图像类别均值雷达图 Fig. 8Star plot after data standardized process
图 9特征分段后的卫星图像雷达图
Fig.9Star plot of 3groups for each sample with 36dimension
4)将生成的新的 9维变量特征绘制在一个雷 达图中,得到 6类的雷达图表示如图 10。从图 10中可以看出, 各类的雷达图形状已经具有明显区别 了,因此很容易根据图形形状将它们分类。
图 10特征融合后的卫星图像类别均值雷达图 Fig. 10Star plot with nine graphical features
类别 1
类别 6
类别 5类别 4类别 3
类别 2
类别 1类别 6
类别 5类别 4类别 3
类别 2类别 1类别 6
类别 5类别 4类别 3
类别 2
450燕山大学学报 2008表 1比较了在 2维空间中 Fisher 线性判别
(FLD ) 、非线性主成分分析(NLPCA ) 、自适应线
性投影(ALP ) 、非线性成分分析(NCA )和本文
提出的多变量特征融合(MFF )的降维后,应用
范文五:几种文本特征降维方法的比较分析
1引言
文本数据挖掘在计算机与互联网络技术不断发展的今天 , 发 挥 着 日 趋 重 要 的 作 用 。 文 本 挖 掘 通 常 采 用 向 量 空 间 模 型 (VSM ) 来表达文本特征 , 即通过计算文本中词条出现的频度来 构造文本 -词条矩阵 , 而文本中出现的词条数量众多 , 因此 , 文 本特征矩阵总是表现出成千上万甚至更大的维数 , 使得文本挖 掘处理工作计算非常复杂 , 解决这一问题的方法就是先对文本 特征矩阵进行降维 。
高维矩阵的降维有多种不同的方法 [1 ̄9], 如 :随机映射 RP (Random Projection ) [1 ̄4]、 非 负 矩 阵 分 解 NMF (Non-negative Matrix Factorization ) [5, 6]、 概念索引 CI (Concept Indexing ) [7]、 基于 矩 阵 奇 异 值 分 解 理 论 的 隐 含 语 义 分 析 LSA (Latent Semantic Analysis ) [1, 2, 8]方 法 ; 还 有 多 元 统 计 分 析 理 论 [9]中 的 主 成 分 分 析 PCA (Principal Component Analysis ) 、 因子分析 FA (Factor Analy-sis ) 、 独 立 成 分 分 析 ICA (Independent Component Analysis ) , 以 及其它一些线性和非线性方法 [1]。
本文试图对几种不同的降维方法及其在文本挖掘中的作 用进行探讨 。 为此 , 先在第 2至 5部分介绍随机映射 、 非负矩阵 分解 、 概念索引和隐含语义分析等四种方法 , 然后在第 6部分 分析各种方法的降维原理 , 再在第 7部分通过实验对这四种降 维方法在文本聚类中的作用 、 效率与效果进行对比分析 , 找出 它们的差异 。
2随机映射 (RP )
对于给定的 m ×n 矩阵 X , 其数据维度可以通过将其映射 到一个低维 (r 维 , r
S m ×r =X m ×n ? R n ×r (1) RP 的思想源于 Johnson-Lindenstrauss 引理 [3]:
对于任意 0<><1与整数 n="" ,="" 设="" r="" 为正整数="" ,="" 且使得="">1与整数>
r ≥ 4(ε2-ε3) -r lnn (2)
则对于 R d 中 n 个点的集合 W , 存在一个映射 f :R d → R r , 使 得对所有的 u , v ∈ W :
(1-ε) ‖ u-v ‖ 2≤‖ f (u ) -f (v ) ‖ 2≤ (1+ε) ‖ u-v ‖ 2(3) 引理说明高维欧氏空间可以映射到一个 O (log n ) 维子空 间 , 使得点间距离对于任意 0<><1能近似保留>1能近似保留>
几种文本特征降维方法的比较分析
高茂庭 1, 2王正欧 1
1(天津大学系统工程研究所 , 天津 300072)
2(上海海事大学计算机系 , 上海 200135)
E-mail :mtgao@163.com
摘 要 文本挖掘中采用向量空间模型 (VSM ) 来表达文本特征 , 表现出巨大的维数 , 从而导致处理过程计算复杂 , 为此 , 需要先对文本特征矩阵进行合理的降维处理 。 隐含语义分析 (LSA ) 、 概念索引 (CI ) 、 非负矩阵分解 (NMF ) 和随机映射 (RP ) 是几种有效的降维方法 , 在分析降维空间的含义和计算复杂度后 , 通过文本聚类实验比较和分析了这几种降维方法的差 异 , 实验表明 , 这些方法不仅可以对文本特征空间作有效的降维处理 , 还能在不同程度上凸现文本和词条之间的语义关 系 , 从而提高文本挖掘的效率和准确率 。
关键词 文本挖掘 降维 随机映射 非负矩阵分解 概念索引 隐含语义分析
文章编号 1002-8331(2006) 30-0157-03文献标识码 A 中图分类号 TP183
Comparing Dimension Reduction Methods of Text Feature Matrix GAO Mao-ting 1, 2WANG Zheng-ou 1
1(Institute of System Engineering , Tianjin University , Tianjin 300072)
2(Computer Science Department , Shanghai Maritime University , Shanghai 200135)
Abstract :Vector Space Model is usually used to express text feature in data mining.Text feature matrix has large dimensionality , and leads to complex computation.So it is needed to reduce dimensionality of text feature matrix before mining data.Latent Semantic Analysis , Concept Indexing , Non -negative Matrix Factorization and Random Projection are some dimension reduction methods.After comparing and analyzing the meanings of the reduced space , the computing complexity and their differences , experiments demonstrate these methods not only can reduce dimensionality effectively , but also open out the semantic relations between text and term and improve mining efficiency and accuracy.
Keywords :text mining , dimension reduction , RP , NMF , CI , LSA
基金项目 :国家自然科学基金资助项目 (编号 :60275020) ; 上海市教委科研项目 (编号 :04FB22) ; 上海海事大学重点学科建设项目 (编号 :XL0101) 作者简介 :高茂庭 (1963-) , 男 , 副教授 , 系统分析员 , 博士生 , 主要研究方向 :数据挖掘 , 数据库应用 , 管理信息系统 。 王正欧 (1938-) , 男 , 教授 , 博 , :, , ,
157
计算机工程与应用 2006.30
(1±ε) 的因素 ) 。 而且 , 这个映射可以在多项式时间内找到 [3]。
3非负矩阵分解 (NMF )
文本特征矩阵中各个数据元素的值总是非负的 , 对于这样 的 m ×n 非负矩阵 V=(v
ij
) m ×n , 可以近似地分解为两个非负矩阵 W=(w ij ) m ×r 与 H=(h ij ) r ×n 的乘积 [5, 6], 使得 :
V ≈ WH (4) 其中 r 通常比 m 和 n 都要小得多 , 也即满足 (m+n ) r
即 v
i
=Wh i , 其中 v i 和 h i 是 V 和 H 的第 i 列 , 则每一数据 v i 都是 W 的列的正线性组合 , 组合的系数为 h 的元素值 。 这样 , W= [w 1, w 2, … , w r ]就可看作 是 对 V 进 行 线 性 估 计 而 优 化 了 的 基 向 量 。 用相对较少的 (r 个 ) 基表示许多 (m 个 ) 观测数据 (r
果 这 些 基 (w
1
, w 2, … , w r ) 能 揭 示 出 隐 藏 在 (v 1, v 2, … , v m ) 中 的 数
据结构 , 就可获得对观测数据 v i 好的估计 Wh i 。
非负矩阵分解可以化为优化问题 , 用迭代方法交替求解 W 和 H , 先固定其中的一个矩阵来计算另一个矩阵 , 再固定另 一个来计算这一个矩阵 , 交替进行 。
4概念索引 (CI )
设 W 为 m ×n 文本词条矩阵 (其中 , m 为文本集中文本的数 目 , n 为文本集中不同的词条数目 ) , W 的第 i 行为第 i 个文档 的向量空间表示 (即 W[i , *]=w
i
) , W 的第 j 列为第 j 个词条在各 个文档中出现的频率 , 再设 r 为要降至的维数 。 概念索引先采 用某种简单的聚类算法 (k-means 或层次算法等 ) 对文本集作 r
路聚类 , 将文本集分成 r 个互不相交的子集 S
1
, S 2, … , S r , 然后 ,
对每个集合 S i 分别计算质心点向量 C
i
, 并将它们规格化为单
位向量 C
i
′ , 将每一个单位质心向量 C i ′ 作为降维空间的一个坐 标轴 , 形成一个 r 维子空间 , 每个文本的 r 维 向 量 表 示 可 通 过 将其映射到这个 r 维子空间得到 , 因此 , 降维后的文本向量空 间 W ′ 可通过式 (5) 的矩阵运算得到 :
W m ×r ′ =W m ×n ? C n ×r (5)
其中 , C
n ×r
=(C1′ , C 2′ , … , C r ′ ) 。
5隐含语义分析 (LSA )
隐含语义分析利用奇异值分解来实现降维 , 并凸现矩阵向 量间隐含的语义特征 。
对文本词条矩阵 W
m ×n
, 经奇异值分解 [8], 矩阵 W 可表示为 三个矩阵的乘积 :
W=UAV T (6) 其中 , U 和 V 分别为与矩阵 W 对应的左 、 右奇异向量矩阵 , A 为由矩阵 W 的奇异值按递减顺序排列构成的对角矩阵 。 取 U 和 V 最前面的列构建 W 的 r-秩近似矩阵 W r :
W r =U r A r V r T (7) U r 和 V r 的列向量为正交向量 , 分别作为文本向量和词向
, W r , 6四种降维方法分析
对于 RP 降维 , Johnson-Lindenstrauss 引理说明 , 总可以通 过 RP 将一个高维矩阵变为一个较低维的矩阵 , 并保持一定的 相似度要求 , 而且这个相似度 0<><1是可控的>1是可控的>
对于一个 m ×n 矩阵 , 用 RP 降维至 m ×r , 其计算复杂度为 : O (mnr ) [2, 3], 并且 , 若原矩阵为一个较大的稀疏矩阵 , RP 降维的 计算复杂度可进一步降至 :O (cmr ) [2, 3], 其中 , c
NMF 的基于基向量组合的表示形式具有很直观的语义解 释 , 它反映了人类思维中 “ 局部构成整体 ” 的概念 。 另外 , 基于简 单迭代计算的 NMF 方法具有收敛速度快 、 左右非负矩阵存储 空间小的特点 , 因此 , 适用于处理大规模文本 。
NMF 通过矩阵近似来获取同义词之间的关联 , 将文本向 量转换成概念空间上的表示 。
CI 降维中 , 质心点向量规定了一种对其内容进行概括的 机制 , 尤其是向量主要的维 (即 , 具有高权重的词条 ) 对应于集 合中最重要的词条 。
首先 , 对每一个质心点 , 总存在少量相关词条的权重占其 总值的大部分 。 因此 , 每个质心点能被少量的关键词条所描述 , 每个质心点与一个相似文本聚类相对应 , 而非仅仅为文本集的 随机子集 。 其次 , 这些词条非常有效地提供文本集中所讨论的 主题的概况 , 其权重标明了它们在这些主题中处于什么样的中 心位置 。 第三 , 各质心点的常用词条常常包含着所描述的主题 的上下文起着同义词的词条 。 第四 , 相同的词条常常出现在多 个质心点中 , 这很容易发生在两个质心点为同一个主题的不同 部分时 , 但也可能容易发生在许多词条具有多个意义的情况 。 对 r 个质心点向量集和一个文本 d , d 在 r 维空间中的第 i 维坐标就是其与第 i 个质心点向量之间的余弦相似度 。 因此 , 文 本在降维空间中的不同维对应于每个文本与包含在质心点中概 念的匹配程度 , 这正是将这种降维方法称为概念索引的原因 。 需要注意的是 , 在原空间中相近的文本在降维空间中也是 相近的 , 因为它们在同一程度上匹配不同的概念 。 而且 , 质心点 能够描述概念词条间的隐含关联 , 使得意义相近但使用了不同 词条的文本在降维空间中会更相近 (即使它们在原空间中并不 那么相近 ) , 从而 , 可以改进相关信息的检索 。 类似地 , 在原空间 中由于多义性单词而相近的文本 , 会在降维空间中进一步分 离 , 而消去一些不正确的检索 。
尽管 LSA 也是用文本中包 含 的 词 来 表 示 文 本 的 语 义 , 但 却并不把文本中所有的词看作是文本概念的可靠表示 , 正相 反 , 文本中用词的多样性很大程度上掩盖了文本的语义结构 , LSA 通过奇异值分解和取 r-秩近似矩阵 , 消减了原文本 -词条 矩阵中包含的 “ 噪声 ” 因素 , 更加凸现出文本和词条之间的语义 关系 。
但是 , 奇异值分解存在对数据的变化敏感 、 运算速度慢以 及左 、 右奇异矩阵的存储要求高的不足 。 因此 , 限制了其在大规 模文本信息检索中的应用 ; 此外 , 奇异值分解缺少语义解释的 直观性 。
对 于 一 个 m ×n 矩 阵 , 用 LSA 降 维 至 m ×r , 进 行 SVD 的 时 间复杂度是 O (mn 2) [2], 并且 , 对一个较大的稀疏矩阵 , LSA 降维 的计算复杂度可降至 :O (cmn ) [2, 3], 其中 , c
CI (1) (5) ,
158
2006.30计算机工程与应用
表 1降维用时
r=100 r=200
RP
1.412
2.433
NMF
73.243
196.72
简单 CI
2.043
3.235
复杂 CI
113.76
226.96
LSA 81.848 240.76 s 表 2聚类平均准确率
r=100 r=200 不降维
81.1
RP
84.3
85.2
NMF
87.9
88.4
复杂 CI
89.3
90.7
LSA 91.5 93.1 %
因此 , 这两者的差别主要在于相应的投影矩阵 C n ×r 和 R n ×r
的计
算 。 对 CI 方法 , 若直接选取随机质心点作为降维空间的坐标轴 时 , CI 降维就变成 RP 降维 。 r 个初始聚类划分得越合理 , CI 降 维后就越能准确地代表原矩阵 。
很 显 然 , 由 r
在 Matlab 中 , 有 进 行 SVD 的 svds 函 数 , 也 有 生 成 符 合 正 态分布随机矩阵的 randn 随机函数 , 可以直接用于 LSA 降维和 RP 降维 。
7实验及结果分析
为了对以上四种降维方法进行比较 , 测试选用的文本是海 量公司的文本集 (共 5类 486篇 ) , 分别运用这几种方法作降维 处理 , 然后再采用 SOM 神经网络进行文本聚类分析 , 从处理时 间和聚类准确率两方面来分析和比较这几种降维方法 。 实验中 , 分别记录每种方法进行降维处理所需的运行时 间 , 并计算文本聚类结果的准确率等数据 。
聚类准确率采用平均准确率 (Averaged Accuracy , AA ) 作为 标准 , 即通过考察任意两篇文本之间的隶属关系是否一致来评 价 [10]。
实验运行 环 境 为 :Windows 2000, Matlab 6.5, 196M 内 存 , Celeron 450CPU 。 分别比较降维所用时间和文本聚类的平均 准确率 , 考虑 r=100, r=200的情况 , 得到表 1、 表 2所示的实验 结果 。
分析表 1、 表 2可以得出 :
(1) 几种方法降维后 , 文本聚类的准确率比不降维时都有 不同程度的提高 。
(2) RP 方法计算量最少 , 处理效率是几种方法中最高的 , 但文本聚类的准确率比其它几个相对要低 。
(3) CI 方法降维 , 文本聚类的准确率一般要高于 RP 方法 , 时间复杂度和聚类准确率取决于降维空间的坐标轴 (即 r 个类 质心点向量 ) 的选取 , 当直接随机选取中心点作为降维空间的 坐标轴时 , CI 降维就变成为 RP 降维 。
(4) 简 单 的 CI 方 法 (简 单 划 分 ) 与 稍 复 杂 一 些 的 CI 方 法 (一遍 k-means ) 在效率上有很大的差别 , 但在文本聚类的准确 率上差别却不是特别明显 。 更复杂一些的 CI 方法效率甚至还 可以大于 LSA 方法 。
(5) NMF 方法也有较好的表现 , 文本聚类的准确率要高于 RP 方法 。 时间效率取决于迭代的次数 , 变化幅度也较大 。 (6) LSA 方法降维后 , 更能凸现出文本和词条之间的语义 关系 , 因而 , 进行文本聚类的准确率相对比较高 , 但计算相对较 为复杂 , 限制了其在大规模文本信息检索和处理中的应用 。
(7) 一般 说 来 , r 越 大 , 计 算 代 价 越 大 , 文 本 聚 类 的 准 确 率 也就越高 ; 反之 , r 越小 , 计算代价越小 , 文本聚类的准确率也就 越低 。
8结束语
文本特征矩阵的降维处理是基于向量空间模型的文本数 据挖掘的一个重要的研究内容 。 一个好的降维方法不仅能降低 文本处理的计算复杂度 , 提高文本处理的效率 , 而且 , 还可以提 高文本处理的质量 。
通过以上的理论分析与实验验证 , RP 、 NMF 、 CI 和 LSA 方 法都可以有效地进行降维处理 , NMF 、 CI 和 LSA 等方法能不同 程度上凸现文本与词条的语义特征 , 而 RP 方法却无法凸现文 本与词条的语义联系和有效地过滤噪声 , 但其计算效率最高 。 对于 RP 、 NMF 和 CI 方法 , 合适的降维矩阵对于降维的结 果也有一定的影响 , 降维矩阵的计算与选择 , 如何在速度与质 量之间进行权衡 , 是一个值得研究和探 讨 的 问 题 , 比 如 , CI 方 法中 , 应该花多大的代价去求 r 个聚类及其质心点 。
降维空间的维数 , 对于文本处理的结果有较大的影响 , 如 何确定合理的降维的维数 , 也是一个值得研究的问题 。
(收稿日期 :2006年 5月 )
参考文献
1.Fodor I K.A Survey of Dimension Reduction Techniques[R].LLNL tech-nical report , UCRL-ID-148494, http ://www .llnl.gov/CASC/sapphire/pubs. html , 2002
2.J Lin , D Gunopulos.Dimensionality Reduction by Random Projection and Latent Semantic Indexing[C].In :Text Mining Workshop , at the 3rd SIAM International Conference on Data Mining , 2003
3.Kaski S.Dimensionality Reduction by Random Mapping :Fast Simi-larity Computation for Clustering[C].In :Proceedings of International Joint Conference on Neural Networks (IJCNN'98) , IEEE Service Cen-ter , Piscataway , NJ , 1998:413 ̄418
4.Bingham E , Mannila H.Random Projection in Dimensionality Reduc-tion :Applications to Image and Text Data[C].In :Proc SIGKDD (2001) , 2001:245 ̄250
5.Lee D , Seung H.Algorithms for Non-negative Matrix Factorization[C]. In :Adv Neural Info Proc Syst , 2001; 13:556 ̄562
6.Lee D , Seung H.Learning the Parts of Objects by Nonnegative Ma-trix Factorization[J].Nature , 1999; 401(21) :788 ̄791
7.George Karypis , Eui-Hong (Sam ) Han.Concept Indexing :A Fast Di-mensionality Reduction Algorithm with Applications to Document Retrieval &Categorization[C].In :ACM CIKM Conference , 2000
8.S Dumais , G Furnas , T Landauer et al.Using Latent Semantic Analy-sis to Improve Access to Textual Information[C].In :Proceedings of the Conference on Human Factors in Computing Systems CHI'88, Wash-ington , DC , USA , 1988
9. 于秀林 , 任雪松 . 多元统计分析 [M]. 北京 :中国统计出版社 , 1999 10. 刘少辉等 . 一种基于向量空间模型的多层次文本分类方法 [J]. 中文信 息学报 , 2002; 16(3)
11.Inderjit S D , Dharmendra S M.Concept Decompositions for Large Sparse Text Data using Clustering[J].Machine Learning , 2001; 42(1) : 143 ̄175
159
计算机工程与应用 2006.30
转载请注明出处范文大全网 » 一种快速图像特征降维方法_S
4>3>2>1>