第41卷第3期2014年3月
计算机科学
Computer
Science
V01.41No.3
Mar
2014
高维数据空间的性质及度量选择
何进荣丁立新胡庆辉李照奎
(武汉大学计算机学院软件工程国家重点实验室
武汉430072)
摘要高维数据分析是机器学习和数据挖掘研究中的主要内容,降维算法通过寻找数据表示的最优子空间来约减
维数,在降低计算代价的同时,也提高了后续分类或者聚类算法的性能,从而成为高维数据分析的有效手段。然而,目前缺乏高维数据分析的理论指导。对高维数据空间的统计和几何性质进行了综述,从不同的角度给出了高维数据空
间中“度量集中”现象的直观解释,并讨论了通过度量选择的方式来提高经典的基于距离度量的机器学习算法在分析
高维数据时的性能。实验表明,分数距离度量方式可以显著提高K近邻和K1Tlearls算法的性能。关键词
高维数据,维数灾难,度量集中
文献标识码A
中图法分类号TPl81
P】叫peni箦ofHigh-dimensionalDataSpaceandMetricChoice
HEJimmng
DINGLi-xin
HUQing-hui
LIZhao-kui
(StateKeyLaboratoryofSoftwareEngineering,SchoolofComputer。WuhanUniversity,Wuhan430072,CKm)
Al葛traet
space
High-dimensionaldataanalysisisthe
core
taskofmachinelearninganddatamining.Byfindingoptimalsub—
cailt
fordatarepresentation,dimensionalityreductionalgorithms
or
reducecomputational
cost
andimprovetheper-
formanceofsubsequentclassification
analysis.However.thereisverylittle
clusteringalgorithms,leadingtoeffectivetechniquesforhigh-dimensionaldata
fortheoreticalanalysis
oil
guidancehigh-dimensionaldata.TlliS
gave
paper
reviewed
on“con-
somestatisticalandgeometricalpropertiesofhigh-dimensionaldataspace.and
centrationofmeasure”phenomenonfromdifferentperspectives.Inordertolearningalgorithmsbased
on
someintuitiveexplanations
impmveperformancesofclassicalmachine
on
distancemetric,thispaper
discussedtheeffectsofmetricchoice
high-dimensionaldata
analysis.Empirical
resultsshowthatfractionaldistancemetriccan
improveperformances
ofKNearestNeighborand
Knleanssignificantly.
Keywotds
High-dimensionaldata,Curseofdimensionality,Concentrationofmeasure
1
引言
随着大数据时代的来临,高维数据分析已经成为应用驱
了研究,并讨论了降维算法在高维数据分类中的必要性。文献[133在化学信息学中分析分子之间的相似性度量时,讨论
高维分子描述空间的一些现象,比如空空问现象、距离度量集中现象等等。
动的热点研究问题It,2]。机器学习算法在直接处理高维数据
时,无可避免会遇到“维数灾难”问题[3],即要达到同样的精
然而,国内外研究文献中关于高维数据空间的性质方面的专题研究非常少见,从而导致对高维数据的理论分析和算法设计缺乏指导。基于此,本文从几何和统计的角度,总结归
纳了高维数据空间的性质,当数据空间的样本维数无限增长
度,学习模型所需要的样本数随着样本维数的增加呈指数增
长,在算法应用研究中表现为“小样本”问题[4],在数学分析上则表现为“度量集中”现象[5]。
由于在计算机处理中,数据通常是作为向量进行运算,因
此高维数据空间本质上就是向量空间。目前关于高维数据空间性质的讨论,主要集中于数据库技术中相似性检索方法的研究睁9|,当数据库中每条记录的属性较多时,欧氏度量下的
时,本文从各个侧面给出了“度量集中”现象的直观解释。最后通过实验分析,讨论了不同的距离度量对机器学习算法性
能的影响。
2高维数据空间的统计性质
大数定律和集中不等式是分析高维数据空间统计性质的
基本工具。下面给出分析高维数据空间统计性质的相关定义和结论。
最近邻就失去意义。文献Et03在分析基因和蛋白质表达数据
时,以此为例解释了高维数据数据空间中的一些性质。文献
[11,12]以超光谱数据分析为例,对高维数据空间的特性进行
到稿日期:2013-05—19返惨日期:2013-09-16
本文受中央高校基本科研业务费专项资金(2012211020209),广东省省部产学研结合专项
(20118090400477),珠海市产学研合作专项资金(2011A050101005,2012D0501990016),珠海市重点实验室科技攻关项目(2012D0501990026)资助。何进荣(1984--),男,博士生,主要研究方向为特征提取、高维数据分析,E-mail:}Iejinrong@1whILedu.crl!丁立新(1967一),男,教授,博士生导师,主要研究方向为智能信息处理、云计算;胡庆辉(1976一),男,博士生,主要研究方向为机器学习;李照蠢(1976一),男,博士生,主要研究方向为机器学习。・212・
2.1高维数据空间中的度量
定义1
d维向量空间中的某点z一(z‘1’,zQ’,…,z∽)
定理5E213
(O,1)。
Vz∈X,∑(z(。)2~癌,且lkn∑(z“’)2~Nd—+十∞l—l
f=l
∈础的矿范数定义为:
d
Ilz忆一(墨(z“’)’)告
当户<1时,该范数又称为分数范数‘“]。定理1[151
定理6[2z]
Vz∈x川z忆二N(√d一丢,丢)≈N
z
任给是>o,如果睡誉襻一o,则姆P
、”一“枷E(|I
(佰,百I)。即当维数d趋向于无穷大时,lI
态分布。
IIz近似服从正
。7一h(塑巫性业车身咚岐业<。)一1。min(II1|p)
、
该定理表明,d维标准高斯空间中的绝大部分概率集中于一个超球壳上,即
z
(型必矫芈<£)_1.贝m]~lirain(
、
定理2[163假设样本数目理足够大,使得E(IIz雌)2∈
[,ra≤确in||Xi忪,。m≤酶ax||Xi吣]成立。如果扣lkn
||z||p)
z
此处型坚山{黑音艿野掣称为范数的相对差异,
RⅥ一誉揣称为相对方差。
o。
黜一
P
佰一£<ll
z
II。<瓶+e
例如:当d一1000,£一3.46时:P(28.16<l|zll<35.08)≥1—10“
I|;)2
3高维数据空间的几何性质
投影法和截面法是分析高维数据空间几何性质的基本工具。类比于平面几何和立体几何中的概念,我们可以定义如下的高维几何体,并推导出高维几何体的一些奇特性质,这些性质可以看作是“度量集中”现象的几何直观解释。3.1超立方体3.1.1相关定义
定义3中心在坐标原点、边长为2r的d维超立方体C4(r)为
∥(r)一{(zn’,…,z‘田)I—r≤z“’≤,-foralli}垒[一r,
该定理表明,随着数据空间维数的增加,样本点范数的相对差异和相对方差都趋于0。在高维数据空间中,某个样本点到其最近邻居点和最远邻居点之间的距离趋于相等,从而导致一些基于距离度量的机器学习算法性能降低。这种现象通常称为“度量集中”,最早由Milman在描述高维概率分布时引入[5I。随着维数的增长,欧氏空间中任意两点间距离度量的差异性变得越来越弱,从而导致数据趋向于均匀分布。
已有相关研究表明F17-20],高维空间中数据点之间的相似性度量对矿范数中P值的选取比较敏感。图1显示了IIz忆一1在二维情形下的图形,P值越小,其边界越靠近坐标轴,在机器学习算法中越容易导致稀疏解。
r]。
特别地,0维立方体就是一个点,1维立方体是一条线段,二维立方体是一个正方形。显然,超立方体Cd(,.)共有24个
顶点,2d个d一1维侧面,2‘鸬个d一是维的侧面(鸬表示d
中取出k个的排列数),且每个侧面可看作是超立方体。超立
方体的顶点为u一(±,.,…,士r),到坐标原点的距离为r仃。
图蓦堕兰囵
图l不I司扩范数下的单位圆
单位超立方体可以表示为∥(÷),其直径(超立方体上任意
两点之间距离的最大值)为√万。
定义4超立方体Cd(r)的赤道面为
Ho一{z:Ez‘i’一O}
定理3L20]
给定咒个d维样本点,其每个分量相互独立
则Hc一{z:∑z“’一c)就表示与H。平行的超平面,点z一(zn’,…,z“’)到Ho的垂直距离为
且来自于均匀分布,则存在常数C,使得
c・√赤≤恕E(警皆)≤c嘞_1)・
r弋一
dist(x,Ho)一去l∑z“’I
4d
1=1
√—2p+—1
这里dist‰和出s缔。分别表示"个样本点之间的最大扩距离
度量和最小矿距离度量。
此定理表明,由分数距离度量所计算的样本点之间的相对差异性更大。2.2高斯空间
定义2
d维标准高斯空间由各个分量相互独立且来源
定义5
d维超立方体C4(r)的体积为:
V(Cy(r))一(2r)×(2r)×…×(2r)一(2r)4
\—————————————、/’——————————一df岫
注意到,超立方体的体积随着维数呈指数增长。定义6体积之和,即
S(Cd(r))=(2d)×V(Cy~1(r))
d维超立方体C。(r)的表面积为其所有侧面的
于标准正态分布的d维随机向量构成,即
X一{(z‘”,z‘∞,…,z‘d’):z‘;’~N(O,1),i一1,…,d}
3.1.2重要性质
其概率密度函数为
如)一士(2n)2exp(一掣)
定理4
VxEx,E(||zI|;)一d・E((z“’)。)一d。
定理7恕cos‘1r新,el>一0,其中ei表示坐标轴上的
单位向量。
该定理说明,随着维数的增长,超立方体的对角线逐渐正交于所有的坐标轴。
・
213
・
定理8V。一(z(1),…,z(田)∈鼎,且z(i)2三,【,(一0.5,
0.5),则
E(disfl(x,/40))一百1
证明:根据定义4,可知
E哮I量∥’I)2=吉%r(量∥’)=i1蚤d%r(∥’)
=上di§=1f上12、一上12
该定理说明,单位超立方体内任一点到其赤道面H0的
平均平方距离为壶。
fo,
K专
定理9枷lh[11V(Cd(r))={1,r一号t—
●
【o。,r>丢
定理10
e∈(o,
4_.∞
1坠y(∥(专)一∥(专一专))一1,v
o
■
厶
1)。
该定理表明,单位超立方体的体积主要集中在其外壳上。
这也启发我们,原始高维数据的某个度量实际上分布在某个
维数较低的子空间,这也是降维算法实施的依据之一。
定理11
—e~,V£∈
厶厶o“
(0,d)。
定理12璺窭笺g詈寻=o,V
r∈(o,+。。)。
3.2超球体3.2.1相关定义
定义7圆心在坐标原点、半径为r的d维超球体定义
为
B。(7.):{(z<1),…,z(由)I∑d(z(t’)z≤户}
i=1
其体积‘233为
v(∥(r))一鱼鸳
dr(要)
r∞
1这里r(s)=}e-tt’1dt是Gamma函数,且r(寺)一J0
厶
压,r(1)=1,r(z+1)一zr(z)。
特别地,单位超球体的体积为:
寿一
d=2p
v(∥(1))一_
f
【
d=2p+1
显然,V(∥(r))=V(Bd(1))・一。于是,超立方体∥
(r)的外接球为Bd(r扭),内切球为Bd(r)。
定义8超球体∥(r)的表面称为球面,记作a(∥(r)),
即
d
a(Ba(r))一{(z(u,…,X‘d))I∑(z‘‘’)2=r2)
注意,a(Bd(r))可以看作是d维欧氏空间中的d一1维流形。从拓扑观点来看,d维球面可以表示为a(Ba+1(口))一
剐U{。o),其局部同构于d维欧氏空间R4。
定义9超球体Ba(r)的表面积定义为
・214・
S(B4(r))一S(∥(1))∥-1
等价地,d维单位超球体可以看作是对d一1维球壳的积分,
即
V(Bd(1))=I
S(∥(1))一-1dr
J0
于是
’
.s(∥(r))一芋(v(∥(力))一d・V(∥(1))・∥1
dr
定义10超球体的中心切片定义为
剧(r)={z:0
z
If≤r,一g◇n’≤e,s∈(o,r))
3.2.2重要性质
根据上面的定义,容易导出如下的相关定理。
定理13与d维超立方体的每个d一1维侧面相交的d维超球体不一定包含超立方体的中心。如图2所示。
夕/\\
、
●
起立方体.
中心
/
\
/
,
图2定理13的几何解释
考虑下面的反例。假设中心点在坐标原点的单位超立方体,当d=16时,假设超球体的球心在(O.2,…,0.2)处,该点
到坐标原点的欧氏距离为/16・0.22一o.8,此时定义该超球体的半径为0.7,则该超球体与单位超立方体的所有15个侧面相交。显然,超立方体的中心点并不包含在超球体中。
定理14
v(∥(1))一墅譬粤卫,s(B抖・(1))一2nV
(∥一1(1)),v(∥(1)):姿v(∥一2(1)),s(酽(1)):笔s
a
口一二
(Ba一2(1))。
该定理容易由定义7和定义9得出,反映了单位超球体
的体积与其表面积之间的递归关系。
定理15limV(∥(r))=O,limS(∥(r))一O。
定理1
6[24]!酬脚励:jo’≤专。~
l嗡r>去
上面两个定理表明,任给超立方体∥(r)(r>—柰=),随
着维数d的增加,其外接超球体的体积趋向于无穷大,而内切
超球体的体积趋向于0。
定理17恕嬲_o。
该定理表明,高维超球体的体积集中在球壳上。例如,当
d≥500时,至少99%的体积包含在厚度为1%的球壳上。
定理18恕弋面酊笋-e_三。
v(B。(r一{))
证明:根据定义7,可得
罂—氓萨矿一撄
,.V(∥(r一言”
,.
2(r--d)。寇州导)
dr(d)2一老
:1inl(1一Z6-5)4一e一手d—一
ra
定理19地潞黑_00
该定理表明,随着维数的增加,超立方体的体积主要集中于超立方体的边角上,即其内切超球体的体积所占比重越来越小。因此,在高维数据空间的结构分析中,其内部中心往往是“空”的,这种现象被称为“空空间”现象。
4.1
人工数据集上的距离度量选择
实验中,随机生成1000个d维样本点,每个维度分量相
互独立且服从[o,1]区间上的均匀分布。随着维数d的增加,
样本点的矿范数(实验中分别取p=O.5,1,1.5,2四种情形)的分布呈现出较大的差异,如图3所示,维数d越高,范数分布的集中效应越明显,且P越大,这种集中趋势越突出。另外随着维数d的增加,其均值以不同的方式增大,其中P一0.5时呈先慢后快增长趋势,p一1时呈线性增长趋势,p>l时呈先快后慢增长趋势(见图4(a));当p<2时,其方差随着维数增加而增加,p=2时,方差呈现减小趋势(见图4(b));而相对方差和相对差异随着维数增加而快速减zb(见图4(c)和(d))。
由图3和图4所示的实验结果可以看出,当采用分数范数(即p<l时)的距离度量方式时,样本间的“度量集中”现象比声>1时较弱。
p=0.5
p=l
I产15
定理20您潞端-1,地器湍一1。
该定理表明,高维超球体的体积、表面积主要集中于中心切片上。
3.3其他高维几何体
下面再介绍几类具有解析形式的体积计算公式的高维几何体。
3.3.1超长方体
d维的超长方体R4(Ⅱ)定义如下:
尺d(Ⅱ)={(z‘u,…,z‘由)I一乜“’≤≤z“’≤≤以“’,口“’∈R+}其体积为:
V(Ro)=24Ⅱn‘i’
萨2
3.3.2超平行几何体
超平行几何体是平行四边形和平行六面体概念在高维空间中的推广,可定义为:
‰,一坛淼筹宰}
超平行几何体∥(口)可以看作是由超长方体掣(n)经过
可逆线性变换得到的,因此
V(P(n))一Idet(A叫)l・V(副(口))
3.3.3超单纯形
d维超单纯形是三角形概念在高维的推广,可以定义为9一{z:O≤z‘1’≤z‘2’≤…≤z‘田≤1}
显然,超单纯形铲具有如下形式的d+1个顶点:
{(O,o,…,O),(o,1,o,…,o),(o,1,1,…,o),…,(1,1,…,1))
下面推导其体积计算公式。注意到在超立方体{z:o≤z“’≤1}内共有d!种不同的顶点坐标排列。下面考虑另一个超单纯形,其(f+1个顶点如下:
掰一{(O,o,…,O),(1,0,o,…,O),(O,1,o,…,O),…,(O,
o,…,o,1))
根据顶点xE∥和Y∈S}的关系:
d
l=l
d
l二Z
d
z‘1’一j,‘西,z‘2’一∑y‘订,.27‘3’=∑y‘n,…,.27‘由=∑Y‘i’l=d—l
可知此处的线性变换矩阵的行列式为1,即V(9)一V(研),因此超单纯形9的体积为
V(9)=击
4实验结果
根据以上对高维数据空间的奇特性质的综述可以看出,“度量集中”现象是高维数据分析的一大难点,传统的基于欧氏距离度量的算法不适合高维数据分析。维数约减是克服这一困难的常规方法,然而维数约减无可避免地会导致数据中蕴含的某些信息的损失,本文主要研究度量选择对机器学习算法性能的影响。下面通过实验来讨论高维数据空问中不同距离度量的分布,及其对经典的基于距离度量的机器学习算法(如KNN和Kmeans)的影响。
・
誊囫{1盟"霰5
02
噩0.070.06网
;№州
g
l|
215
・
£g
g{}j
E
均值,算法性能比较结果见表3和表4。
02
:035
n1
。0.05=
O
篓n
(C)范数的相对方差
表3扩范数度量下的KNN分类结果
oF2寄—‘
表4扩范数度量下的K—means聚类结果
(d)范数的相对差异
图4高维空间中样本点范数的均值(a)、方差(b)、相对方差(c)和
相对差异(d)
4.2
UCI数据集上的距离度量选择
为了验证不同范数的选择对机器学习算法性能的影响,
实验表明,分数范数度量可以显著提高经典的分类算法KNN和聚类算法K—means在高维数据集上的性能。4.3人脸数据集上的距离度量选择
人脸图像数据是典型的高维数据,在人脸识别实验中,首先将图像数据拉直变成向量形式,假设经过裁剪之后的人脸图像长为32个像素,宽为32个像素,则在算法处理中通常将其转换为1024(32×32)维的向量。实验中选取了Yale、Oli-vetti、UMIST和GeorgiaTeeh等人脸数据集(见表5),分别在不同的距离度量设置下,采用KNN算法(五取1)进行人脸识别,其中每个人脸随机抽取T张图片作为训练集,其余的作为测试集。每次实验重复进行50次,平均识别准确率见表6一表9,当p=0.5时,KNN算法取得最高的识别准确率。
表5人脸数据集描述
名称
维数
102425766441800
我们选用来自于真实世界的UCI测试数据集n,数据集相关描述如表1所列。对于原始数据集中属性有缺失的情形,实验中直接对其赋值一1。同时,实验中首先对每个维度上的数据按照下面的公式规范化为0到1之间:
bE(/)一min(z‘i’)‘m。。。‘‘。a。。。x。。。。。(’。。x。。。。(。。/)。。。。。)。。。。-。。’’’。。。m。。‘。。。i。。n。。。。(。。。x。。。。。(。。I。——)
表1数据集描述
样本数
165400575750
类别数
15402050
实验中,我们首先计算了各个数据集上不同范数度量下的相对差异。由表2的计算结果可知,p=O.5时,样本范数的相对差异最大,这也意味着在该范数度量下的机器学习算法的性能也应该是最好的。
表2
UCI数据集上的样本扩范数相对差异
Yalez)Olivettis)U ̄Ⅱgr4)
c,eorgi【aTech5)
表6扩范数度量下的KNN人脸识别结果(Yale)
表7扩范数度量下的KNN人脸识别结果(Olivetti)
在分类任务的实验中,我们采用基于不同的范数度量的KNN算法,实验中k取3,对样本集进行随机划分,50%作为训练集,50%作为测试集,其评价指标为误分率;在聚类任务的实验中,我们采用基于不同的范数度量的K-means算法,初始聚类中心随机选择,最大迭代次数为1000,其评价指标为RandIndex。每个数据集上的算法重复执行50次后取平
表8扩范数度量下的KNN人脸识别结果(UMIST)
1)http://archive.ics.uci.edu/ml/datasets.html
毡http:||恻.es.nyu.edu/~roweis/data.html
・216・
∞CVC.yale.edu/projects/yalefaees/yalefaces.html
4)http://images.ee.umist.ac.uk/danny/database.html5)http://www.anefian.corn/research/facereco.htm
表9扩范数度量下的KNN人脸识别结果(GeorgiaTech)
结束语本文对高维数据空间的统计性质和几何性质进行了系统的综述,这些性质都可以看作是“度量集中”现象的
具体表现。当样本的维数增大时,数据集呈现出“度量集中”现象,即不同样本之问的距离度量的相对差异在逐渐减小,这使得基于样本间距离度量的机器学习算法的性能大大降低。
因此,距离度量的选择对于机器学习算法至关重要,本文通过
大量实验讨论了不同距离度量的选择对经典的机器学习算法(如KNN和Kmenns)的影响,实验结果表明分数范数的距离度量可以显著提高算法性能。
参考文献
[1]Skillicom
D
RUnderstandingHigh-DimensionedSpaces[M1.
Springer-VerlagNewYorkIncorporated,2013
[2]Donoho
D
L
High-dimensionaldataanalysis:The
curses
and
blessingsofdimensionality[刀.AMSMathChallengesLecture,
2000:1-32
[3]BellmanRAdaptiveControlProcess:AGuideTour[M].Prin-
cetonUniversityPress,Princeton,NewJersey,1961
[4]FukunagaK
Introduction
to
StadsticalPatternRecognition(2nd
ed)[M].NewYork:Academic,1990,39-40(31—34);220-221
[5]Mil’manVD.NewproofofthetheoremofADvoretzkyon
in-
tersections
ofconvex
bodies[J].FunctionalAnalysisanditsAp
plications,1971,5(4):288-295
[6]WeberR,SchekH-J,BlottSAquantitativeanalysisandper-
formancestudyforsimilarity-smrdl
metlxMsin
hit出-dimmsicml
spaces[C]//Proceedingsof
the24rdInternationalConference
on
VeryLaI_geDataBases,set'.VLDB’98.SanFrancisco,CA,
USA:MorganKanfmarmPublishers
Inc,1998:194-205
[7]GaedeV,GEmtherQ
Multidimensional
ac1L'egs
methods[J].
ACMComputingSurveys(C:SUR),1998。30(2):170-231
[8]FrancoisD,WertzV,Verleysen腿Non-euclidean
metricsfor
similarity
searchinnoisy
datasets[C]//Proc.of琰iANN.2005
[9]Kouiroukidis
N,EvangelidisG.TheEffectsofDimensionality
Cursein
High
DimensionalkNNSearch[C]//Informaties
(1)CI),201115thPanhellenie
Conferenceoil.口EEE。2011:41-45
[i03ClarkeR,RessomHW,WangA。eta1.ThepropertiesoflIigh-
dimensionaldataspaces:implicationsforexploringgeneand
pro-
teinexpressiondata[J].NatureReviewsCancer,2008,8(1):37—
49
[11]Jimenez
L,LandgrebenSupervisedClassificationinHighDi—
mensional
Space:Geometrical,Statistical
and
Asymptoticsl
PropertiesofMultivariatedata[j].IEEETrsnsactions
on
Geo-
scienceandRemoteSensing,1999,37(6)
[12]Jimenez
L,LandgrebeD.Highdimensionalfeaturereductionvia
projectionpursuit[C]//GeoscienceandRemoteSensingSympo-
sium,1994.IGARSS’94.Surfaceand
Atmospheric
Remote
Sensing:Technologies,DataAnalysisandInterpretation.Inter-
national.IE匝,1994,2:1145—1147
[13]RuppM,SchneiderP,SchneiderG.Distancephenomena
in
high-
dimensionalchemicaldescriptorspaces:Consequences
forsimi—larity-based
approaches[J].Journalof
Computational
Chemis—
try,2009,30(14):2285—2296
[14]FrancoisD,WertzV,VerleysenM
The
concentrationoffrac-
tionaldistances[J].IEEETransactions
on
KnowledgeandData
Engineering,2007,19(7):873-886
[15]DurrantRJ,Kab6nAWhen
is‘nearest
neighbor’meaningful:
A
converse
theoremandimplications[J].Journal
ofComplexity,
2009,25(4):385-397
[16]Beyer
neighbor”m锄angfd?[M]//Datahase‰巧rICDT’99.
K,GoldsteinJ,RamakrishnanR,eta1.Whenis。nearest
Springer
BerlinHeidelberg,1999:217-235
[17]HinneburgA,Agga,walCC,KeimDAwhatisthene.arest
neighborin
high
dimensionalspaces?[M].Bibliothekder
UIliversit豆tKonstanz。2000
[18]FrancoisD,Werta
V,Verleysen
MNon-euclideen
metricsfor
similaritysearchinnoisydatasetsEC-]//Proc
ofESANN.2005
[19]Hsu
C
M,ChenMSOnthedesignandapplicabilityofdistance
functionsinhigh-dimensionaldata
spaee[J].IEEETransactions
on
KnowledgeandDataEngineering,2009,21(4):523-536
[20]A鼹啪l
CC,HinneburgA,Keim
D八On
the
surprising
be-
haviorofdistancemetricsinhighdimensionalspaces[C]//P挣
ceedingsofthe8thInternational
Conference
on
Database
Theo-
ry,Ser.ICDT’01.London,UKISpringer-Verlag,20011420-434
[21]CanalLAnormalapproximationforthechi-squaredistribution
[J].ComputationalStatistics&Data
Analysis,2005,48(4):
803—808
[223
KatafygiotisLS。ZuevKM
Geometricinsightintothechallen-
gesof
solving
high-dimensionalreliabilityproblemsEJ].Pmbabi—
listicEngineeringMechanics,2008,23(2):208-218
D3]Wang
liar卜zhong.Crl帕metricStructureofHigh-Dimensiona/Da-
taandDimensionalityReduction[C]//Higher
EducationPress
(China)andSpringer.Beijing,2011
[241HoperoftJ。KennanRComputerScienceTheoryfortheInfor-
mation
AgeEM].Spring,2012:7-27
・217・
高维数据空间的性质及度量选择
作者:
作者单位:刊名:英文刊名:年,卷(期):
何进荣, 丁立新, 胡庆辉, 李照奎, HE Jin-rong, DING Li-xin, HU Qing-hui, LI Zhao-kui武汉大学计算机学院软件工程国家重点实验室 武汉430072计算机科学
Computer Science2014,41(3)
本文链接:http://d.wanfangdata.com.cn/Periodical_jsjkx201403046.aspx
第41卷第3期2014年3月
计算机科学
Computer
Science
V01.41No.3
Mar
2014
高维数据空间的性质及度量选择
何进荣丁立新胡庆辉李照奎
(武汉大学计算机学院软件工程国家重点实验室
武汉430072)
摘要高维数据分析是机器学习和数据挖掘研究中的主要内容,降维算法通过寻找数据表示的最优子空间来约减
维数,在降低计算代价的同时,也提高了后续分类或者聚类算法的性能,从而成为高维数据分析的有效手段。然而,目前缺乏高维数据分析的理论指导。对高维数据空间的统计和几何性质进行了综述,从不同的角度给出了高维数据空
间中“度量集中”现象的直观解释,并讨论了通过度量选择的方式来提高经典的基于距离度量的机器学习算法在分析
高维数据时的性能。实验表明,分数距离度量方式可以显著提高K近邻和K1Tlearls算法的性能。关键词
高维数据,维数灾难,度量集中
文献标识码A
中图法分类号TPl81
P】叫peni箦ofHigh-dimensionalDataSpaceandMetricChoice
HEJimmng
DINGLi-xin
HUQing-hui
LIZhao-kui
(StateKeyLaboratoryofSoftwareEngineering,SchoolofComputer。WuhanUniversity,Wuhan430072,CKm)
Al葛traet
space
High-dimensionaldataanalysisisthe
core
taskofmachinelearninganddatamining.Byfindingoptimalsub—
cailt
fordatarepresentation,dimensionalityreductionalgorithms
or
reducecomputational
cost
andimprovetheper-
formanceofsubsequentclassification
analysis.However.thereisverylittle
clusteringalgorithms,leadingtoeffectivetechniquesforhigh-dimensionaldata
fortheoreticalanalysis
oil
guidancehigh-dimensionaldata.TlliS
gave
paper
reviewed
on“con-
somestatisticalandgeometricalpropertiesofhigh-dimensionaldataspace.and
centrationofmeasure”phenomenonfromdifferentperspectives.Inordertolearningalgorithmsbased
on
someintuitiveexplanations
impmveperformancesofclassicalmachine
on
distancemetric,thispaper
discussedtheeffectsofmetricchoice
high-dimensionaldata
analysis.Empirical
resultsshowthatfractionaldistancemetriccan
improveperformances
ofKNearestNeighborand
Knleanssignificantly.
Keywotds
High-dimensionaldata,Curseofdimensionality,Concentrationofmeasure
1
引言
随着大数据时代的来临,高维数据分析已经成为应用驱
了研究,并讨论了降维算法在高维数据分类中的必要性。文献[133在化学信息学中分析分子之间的相似性度量时,讨论
高维分子描述空间的一些现象,比如空空问现象、距离度量集中现象等等。
动的热点研究问题It,2]。机器学习算法在直接处理高维数据
时,无可避免会遇到“维数灾难”问题[3],即要达到同样的精
然而,国内外研究文献中关于高维数据空间的性质方面的专题研究非常少见,从而导致对高维数据的理论分析和算法设计缺乏指导。基于此,本文从几何和统计的角度,总结归
纳了高维数据空间的性质,当数据空间的样本维数无限增长
度,学习模型所需要的样本数随着样本维数的增加呈指数增
长,在算法应用研究中表现为“小样本”问题[4],在数学分析上则表现为“度量集中”现象[5]。
由于在计算机处理中,数据通常是作为向量进行运算,因
此高维数据空间本质上就是向量空间。目前关于高维数据空间性质的讨论,主要集中于数据库技术中相似性检索方法的研究睁9|,当数据库中每条记录的属性较多时,欧氏度量下的
时,本文从各个侧面给出了“度量集中”现象的直观解释。最后通过实验分析,讨论了不同的距离度量对机器学习算法性
能的影响。
2高维数据空间的统计性质
大数定律和集中不等式是分析高维数据空间统计性质的
基本工具。下面给出分析高维数据空间统计性质的相关定义和结论。
最近邻就失去意义。文献Et03在分析基因和蛋白质表达数据
时,以此为例解释了高维数据数据空间中的一些性质。文献
[11,12]以超光谱数据分析为例,对高维数据空间的特性进行
到稿日期:2013-05—19返惨日期:2013-09-16
本文受中央高校基本科研业务费专项资金(2012211020209),广东省省部产学研结合专项
(20118090400477),珠海市产学研合作专项资金(2011A050101005,2012D0501990016),珠海市重点实验室科技攻关项目(2012D0501990026)资助。何进荣(1984--),男,博士生,主要研究方向为特征提取、高维数据分析,E-mail:}Iejinrong@1whILedu.crl!丁立新(1967一),男,教授,博士生导师,主要研究方向为智能信息处理、云计算;胡庆辉(1976一),男,博士生,主要研究方向为机器学习;李照蠢(1976一),男,博士生,主要研究方向为机器学习。・212・
2.1高维数据空间中的度量
定义1
d维向量空间中的某点z一(z‘1’,zQ’,…,z∽)
定理5E213
(O,1)。
Vz∈X,∑(z(。)2~癌,且lkn∑(z“’)2~Nd—+十∞l—l
f=l
∈础的矿范数定义为:
d
Ilz忆一(墨(z“’)’)告
当户<1时,该范数又称为分数范数‘“]。定理1[151
定理6[2z]
Vz∈x川z忆二N(√d一丢,丢)≈N
z
任给是>o,如果睡誉襻一o,则姆P
、”一“枷E(|I
(佰,百I)。即当维数d趋向于无穷大时,lI
态分布。
IIz近似服从正
。7一h(塑巫性业车身咚岐业<。)一1。min(II1|p)
、
该定理表明,d维标准高斯空间中的绝大部分概率集中于一个超球壳上,即
z
(型必矫芈<£)_1.贝m]~lirain(
、
定理2[163假设样本数目理足够大,使得E(IIz雌)2∈
[,ra≤确in||Xi忪,。m≤酶ax||Xi吣]成立。如果扣lkn
||z||p)
z
此处型坚山{黑音艿野掣称为范数的相对差异,
RⅥ一誉揣称为相对方差。
o。
黜一
P
佰一£<ll
z
II。<瓶+e
例如:当d一1000,£一3.46时:P(28.16<l|zll<35.08)≥1—10“
I|;)2
3高维数据空间的几何性质
投影法和截面法是分析高维数据空间几何性质的基本工具。类比于平面几何和立体几何中的概念,我们可以定义如下的高维几何体,并推导出高维几何体的一些奇特性质,这些性质可以看作是“度量集中”现象的几何直观解释。3.1超立方体3.1.1相关定义
定义3中心在坐标原点、边长为2r的d维超立方体C4(r)为
∥(r)一{(zn’,…,z‘田)I—r≤z“’≤,-foralli}垒[一r,
该定理表明,随着数据空间维数的增加,样本点范数的相对差异和相对方差都趋于0。在高维数据空间中,某个样本点到其最近邻居点和最远邻居点之间的距离趋于相等,从而导致一些基于距离度量的机器学习算法性能降低。这种现象通常称为“度量集中”,最早由Milman在描述高维概率分布时引入[5I。随着维数的增长,欧氏空间中任意两点间距离度量的差异性变得越来越弱,从而导致数据趋向于均匀分布。
已有相关研究表明F17-20],高维空间中数据点之间的相似性度量对矿范数中P值的选取比较敏感。图1显示了IIz忆一1在二维情形下的图形,P值越小,其边界越靠近坐标轴,在机器学习算法中越容易导致稀疏解。
r]。
特别地,0维立方体就是一个点,1维立方体是一条线段,二维立方体是一个正方形。显然,超立方体Cd(,.)共有24个
顶点,2d个d一1维侧面,2‘鸬个d一是维的侧面(鸬表示d
中取出k个的排列数),且每个侧面可看作是超立方体。超立
方体的顶点为u一(±,.,…,士r),到坐标原点的距离为r仃。
图蓦堕兰囵
图l不I司扩范数下的单位圆
单位超立方体可以表示为∥(÷),其直径(超立方体上任意
两点之间距离的最大值)为√万。
定义4超立方体Cd(r)的赤道面为
Ho一{z:Ez‘i’一O}
定理3L20]
给定咒个d维样本点,其每个分量相互独立
则Hc一{z:∑z“’一c)就表示与H。平行的超平面,点z一(zn’,…,z“’)到Ho的垂直距离为
且来自于均匀分布,则存在常数C,使得
c・√赤≤恕E(警皆)≤c嘞_1)・
r弋一
dist(x,Ho)一去l∑z“’I
4d
1=1
√—2p+—1
这里dist‰和出s缔。分别表示"个样本点之间的最大扩距离
度量和最小矿距离度量。
此定理表明,由分数距离度量所计算的样本点之间的相对差异性更大。2.2高斯空间
定义2
d维标准高斯空间由各个分量相互独立且来源
定义5
d维超立方体C4(r)的体积为:
V(Cy(r))一(2r)×(2r)×…×(2r)一(2r)4
\—————————————、/’——————————一df岫
注意到,超立方体的体积随着维数呈指数增长。定义6体积之和,即
S(Cd(r))=(2d)×V(Cy~1(r))
d维超立方体C。(r)的表面积为其所有侧面的
于标准正态分布的d维随机向量构成,即
X一{(z‘”,z‘∞,…,z‘d’):z‘;’~N(O,1),i一1,…,d}
3.1.2重要性质
其概率密度函数为
如)一士(2n)2exp(一掣)
定理4
VxEx,E(||zI|;)一d・E((z“’)。)一d。
定理7恕cos‘1r新,el>一0,其中ei表示坐标轴上的
单位向量。
该定理说明,随着维数的增长,超立方体的对角线逐渐正交于所有的坐标轴。
・
213
・
定理8V。一(z(1),…,z(田)∈鼎,且z(i)2三,【,(一0.5,
0.5),则
E(disfl(x,/40))一百1
证明:根据定义4,可知
E哮I量∥’I)2=吉%r(量∥’)=i1蚤d%r(∥’)
=上di§=1f上12、一上12
该定理说明,单位超立方体内任一点到其赤道面H0的
平均平方距离为壶。
fo,
K专
定理9枷lh[11V(Cd(r))={1,r一号t—
●
【o。,r>丢
定理10
e∈(o,
4_.∞
1坠y(∥(专)一∥(专一专))一1,v
o
■
厶
1)。
该定理表明,单位超立方体的体积主要集中在其外壳上。
这也启发我们,原始高维数据的某个度量实际上分布在某个
维数较低的子空间,这也是降维算法实施的依据之一。
定理11
—e~,V£∈
厶厶o“
(0,d)。
定理12璺窭笺g詈寻=o,V
r∈(o,+。。)。
3.2超球体3.2.1相关定义
定义7圆心在坐标原点、半径为r的d维超球体定义
为
B。(7.):{(z<1),…,z(由)I∑d(z(t’)z≤户}
i=1
其体积‘233为
v(∥(r))一鱼鸳
dr(要)
r∞
1这里r(s)=}e-tt’1dt是Gamma函数,且r(寺)一J0
厶
压,r(1)=1,r(z+1)一zr(z)。
特别地,单位超球体的体积为:
寿一
d=2p
v(∥(1))一_
f
【
d=2p+1
显然,V(∥(r))=V(Bd(1))・一。于是,超立方体∥
(r)的外接球为Bd(r扭),内切球为Bd(r)。
定义8超球体∥(r)的表面称为球面,记作a(∥(r)),
即
d
a(Ba(r))一{(z(u,…,X‘d))I∑(z‘‘’)2=r2)
注意,a(Bd(r))可以看作是d维欧氏空间中的d一1维流形。从拓扑观点来看,d维球面可以表示为a(Ba+1(口))一
剐U{。o),其局部同构于d维欧氏空间R4。
定义9超球体Ba(r)的表面积定义为
・214・
S(B4(r))一S(∥(1))∥-1
等价地,d维单位超球体可以看作是对d一1维球壳的积分,
即
V(Bd(1))=I
S(∥(1))一-1dr
J0
于是
’
.s(∥(r))一芋(v(∥(力))一d・V(∥(1))・∥1
dr
定义10超球体的中心切片定义为
剧(r)={z:0
z
If≤r,一g◇n’≤e,s∈(o,r))
3.2.2重要性质
根据上面的定义,容易导出如下的相关定理。
定理13与d维超立方体的每个d一1维侧面相交的d维超球体不一定包含超立方体的中心。如图2所示。
夕/\\
、
●
起立方体.
中心
/
\
/
,
图2定理13的几何解释
考虑下面的反例。假设中心点在坐标原点的单位超立方体,当d=16时,假设超球体的球心在(O.2,…,0.2)处,该点
到坐标原点的欧氏距离为/16・0.22一o.8,此时定义该超球体的半径为0.7,则该超球体与单位超立方体的所有15个侧面相交。显然,超立方体的中心点并不包含在超球体中。
定理14
v(∥(1))一墅譬粤卫,s(B抖・(1))一2nV
(∥一1(1)),v(∥(1)):姿v(∥一2(1)),s(酽(1)):笔s
a
口一二
(Ba一2(1))。
该定理容易由定义7和定义9得出,反映了单位超球体
的体积与其表面积之间的递归关系。
定理15limV(∥(r))=O,limS(∥(r))一O。
定理1
6[24]!酬脚励:jo’≤专。~
l嗡r>去
上面两个定理表明,任给超立方体∥(r)(r>—柰=),随
着维数d的增加,其外接超球体的体积趋向于无穷大,而内切
超球体的体积趋向于0。
定理17恕嬲_o。
该定理表明,高维超球体的体积集中在球壳上。例如,当
d≥500时,至少99%的体积包含在厚度为1%的球壳上。
定理18恕弋面酊笋-e_三。
v(B。(r一{))
证明:根据定义7,可得
罂—氓萨矿一撄
,.V(∥(r一言”
,.
2(r--d)。寇州导)
dr(d)2一老
:1inl(1一Z6-5)4一e一手d—一
ra
定理19地潞黑_00
该定理表明,随着维数的增加,超立方体的体积主要集中于超立方体的边角上,即其内切超球体的体积所占比重越来越小。因此,在高维数据空间的结构分析中,其内部中心往往是“空”的,这种现象被称为“空空间”现象。
4.1
人工数据集上的距离度量选择
实验中,随机生成1000个d维样本点,每个维度分量相
互独立且服从[o,1]区间上的均匀分布。随着维数d的增加,
样本点的矿范数(实验中分别取p=O.5,1,1.5,2四种情形)的分布呈现出较大的差异,如图3所示,维数d越高,范数分布的集中效应越明显,且P越大,这种集中趋势越突出。另外随着维数d的增加,其均值以不同的方式增大,其中P一0.5时呈先慢后快增长趋势,p一1时呈线性增长趋势,p>l时呈先快后慢增长趋势(见图4(a));当p<2时,其方差随着维数增加而增加,p=2时,方差呈现减小趋势(见图4(b));而相对方差和相对差异随着维数增加而快速减zb(见图4(c)和(d))。
由图3和图4所示的实验结果可以看出,当采用分数范数(即p<l时)的距离度量方式时,样本间的“度量集中”现象比声>1时较弱。
p=0.5
p=l
I产15
定理20您潞端-1,地器湍一1。
该定理表明,高维超球体的体积、表面积主要集中于中心切片上。
3.3其他高维几何体
下面再介绍几类具有解析形式的体积计算公式的高维几何体。
3.3.1超长方体
d维的超长方体R4(Ⅱ)定义如下:
尺d(Ⅱ)={(z‘u,…,z‘由)I一乜“’≤≤z“’≤≤以“’,口“’∈R+}其体积为:
V(Ro)=24Ⅱn‘i’
萨2
3.3.2超平行几何体
超平行几何体是平行四边形和平行六面体概念在高维空间中的推广,可定义为:
‰,一坛淼筹宰}
超平行几何体∥(口)可以看作是由超长方体掣(n)经过
可逆线性变换得到的,因此
V(P(n))一Idet(A叫)l・V(副(口))
3.3.3超单纯形
d维超单纯形是三角形概念在高维的推广,可以定义为9一{z:O≤z‘1’≤z‘2’≤…≤z‘田≤1}
显然,超单纯形铲具有如下形式的d+1个顶点:
{(O,o,…,O),(o,1,o,…,o),(o,1,1,…,o),…,(1,1,…,1))
下面推导其体积计算公式。注意到在超立方体{z:o≤z“’≤1}内共有d!种不同的顶点坐标排列。下面考虑另一个超单纯形,其(f+1个顶点如下:
掰一{(O,o,…,O),(1,0,o,…,O),(O,1,o,…,O),…,(O,
o,…,o,1))
根据顶点xE∥和Y∈S}的关系:
d
l=l
d
l二Z
d
z‘1’一j,‘西,z‘2’一∑y‘订,.27‘3’=∑y‘n,…,.27‘由=∑Y‘i’l=d—l
可知此处的线性变换矩阵的行列式为1,即V(9)一V(研),因此超单纯形9的体积为
V(9)=击
4实验结果
根据以上对高维数据空间的奇特性质的综述可以看出,“度量集中”现象是高维数据分析的一大难点,传统的基于欧氏距离度量的算法不适合高维数据分析。维数约减是克服这一困难的常规方法,然而维数约减无可避免地会导致数据中蕴含的某些信息的损失,本文主要研究度量选择对机器学习算法性能的影响。下面通过实验来讨论高维数据空问中不同距离度量的分布,及其对经典的基于距离度量的机器学习算法(如KNN和Kmeans)的影响。
・
誊囫{1盟"霰5
02
噩0.070.06网
;№州
g
l|
215
・
£g
g{}j
E
均值,算法性能比较结果见表3和表4。
02
:035
n1
。0.05=
O
篓n
(C)范数的相对方差
表3扩范数度量下的KNN分类结果
oF2寄—‘
表4扩范数度量下的K—means聚类结果
(d)范数的相对差异
图4高维空间中样本点范数的均值(a)、方差(b)、相对方差(c)和
相对差异(d)
4.2
UCI数据集上的距离度量选择
为了验证不同范数的选择对机器学习算法性能的影响,
实验表明,分数范数度量可以显著提高经典的分类算法KNN和聚类算法K—means在高维数据集上的性能。4.3人脸数据集上的距离度量选择
人脸图像数据是典型的高维数据,在人脸识别实验中,首先将图像数据拉直变成向量形式,假设经过裁剪之后的人脸图像长为32个像素,宽为32个像素,则在算法处理中通常将其转换为1024(32×32)维的向量。实验中选取了Yale、Oli-vetti、UMIST和GeorgiaTeeh等人脸数据集(见表5),分别在不同的距离度量设置下,采用KNN算法(五取1)进行人脸识别,其中每个人脸随机抽取T张图片作为训练集,其余的作为测试集。每次实验重复进行50次,平均识别准确率见表6一表9,当p=0.5时,KNN算法取得最高的识别准确率。
表5人脸数据集描述
名称
维数
102425766441800
我们选用来自于真实世界的UCI测试数据集n,数据集相关描述如表1所列。对于原始数据集中属性有缺失的情形,实验中直接对其赋值一1。同时,实验中首先对每个维度上的数据按照下面的公式规范化为0到1之间:
bE(/)一min(z‘i’)‘m。。。‘‘。a。。。x。。。。。(’。。x。。。。(。。/)。。。。。)。。。。-。。’’’。。。m。。‘。。。i。。n。。。。(。。。x。。。。。(。。I。——)
表1数据集描述
样本数
165400575750
类别数
15402050
实验中,我们首先计算了各个数据集上不同范数度量下的相对差异。由表2的计算结果可知,p=O.5时,样本范数的相对差异最大,这也意味着在该范数度量下的机器学习算法的性能也应该是最好的。
表2
UCI数据集上的样本扩范数相对差异
Yalez)Olivettis)U ̄Ⅱgr4)
c,eorgi【aTech5)
表6扩范数度量下的KNN人脸识别结果(Yale)
表7扩范数度量下的KNN人脸识别结果(Olivetti)
在分类任务的实验中,我们采用基于不同的范数度量的KNN算法,实验中k取3,对样本集进行随机划分,50%作为训练集,50%作为测试集,其评价指标为误分率;在聚类任务的实验中,我们采用基于不同的范数度量的K-means算法,初始聚类中心随机选择,最大迭代次数为1000,其评价指标为RandIndex。每个数据集上的算法重复执行50次后取平
表8扩范数度量下的KNN人脸识别结果(UMIST)
1)http://archive.ics.uci.edu/ml/datasets.html
毡http:||恻.es.nyu.edu/~roweis/data.html
・216・
∞CVC.yale.edu/projects/yalefaees/yalefaces.html
4)http://images.ee.umist.ac.uk/danny/database.html5)http://www.anefian.corn/research/facereco.htm
表9扩范数度量下的KNN人脸识别结果(GeorgiaTech)
结束语本文对高维数据空间的统计性质和几何性质进行了系统的综述,这些性质都可以看作是“度量集中”现象的
具体表现。当样本的维数增大时,数据集呈现出“度量集中”现象,即不同样本之问的距离度量的相对差异在逐渐减小,这使得基于样本间距离度量的机器学习算法的性能大大降低。
因此,距离度量的选择对于机器学习算法至关重要,本文通过
大量实验讨论了不同距离度量的选择对经典的机器学习算法(如KNN和Kmenns)的影响,实验结果表明分数范数的距离度量可以显著提高算法性能。
参考文献
[1]Skillicom
D
RUnderstandingHigh-DimensionedSpaces[M1.
Springer-VerlagNewYorkIncorporated,2013
[2]Donoho
D
L
High-dimensionaldataanalysis:The
curses
and
blessingsofdimensionality[刀.AMSMathChallengesLecture,
2000:1-32
[3]BellmanRAdaptiveControlProcess:AGuideTour[M].Prin-
cetonUniversityPress,Princeton,NewJersey,1961
[4]FukunagaK
Introduction
to
StadsticalPatternRecognition(2nd
ed)[M].NewYork:Academic,1990,39-40(31—34);220-221
[5]Mil’manVD.NewproofofthetheoremofADvoretzkyon
in-
tersections
ofconvex
bodies[J].FunctionalAnalysisanditsAp
plications,1971,5(4):288-295
[6]WeberR,SchekH-J,BlottSAquantitativeanalysisandper-
formancestudyforsimilarity-smrdl
metlxMsin
hit出-dimmsicml
spaces[C]//Proceedingsof
the24rdInternationalConference
on
VeryLaI_geDataBases,set'.VLDB’98.SanFrancisco,CA,
USA:MorganKanfmarmPublishers
Inc,1998:194-205
[7]GaedeV,GEmtherQ
Multidimensional
ac1L'egs
methods[J].
ACMComputingSurveys(C:SUR),1998。30(2):170-231
[8]FrancoisD,WertzV,Verleysen腿Non-euclidean
metricsfor
similarity
searchinnoisy
datasets[C]//Proc.of琰iANN.2005
[9]Kouiroukidis
N,EvangelidisG.TheEffectsofDimensionality
Cursein
High
DimensionalkNNSearch[C]//Informaties
(1)CI),201115thPanhellenie
Conferenceoil.口EEE。2011:41-45
[i03ClarkeR,RessomHW,WangA。eta1.ThepropertiesoflIigh-
dimensionaldataspaces:implicationsforexploringgeneand
pro-
teinexpressiondata[J].NatureReviewsCancer,2008,8(1):37—
49
[11]Jimenez
L,LandgrebenSupervisedClassificationinHighDi—
mensional
Space:Geometrical,Statistical
and
Asymptoticsl
PropertiesofMultivariatedata[j].IEEETrsnsactions
on
Geo-
scienceandRemoteSensing,1999,37(6)
[12]Jimenez
L,LandgrebeD.Highdimensionalfeaturereductionvia
projectionpursuit[C]//GeoscienceandRemoteSensingSympo-
sium,1994.IGARSS’94.Surfaceand
Atmospheric
Remote
Sensing:Technologies,DataAnalysisandInterpretation.Inter-
national.IE匝,1994,2:1145—1147
[13]RuppM,SchneiderP,SchneiderG.Distancephenomena
in
high-
dimensionalchemicaldescriptorspaces:Consequences
forsimi—larity-based
approaches[J].Journalof
Computational
Chemis—
try,2009,30(14):2285—2296
[14]FrancoisD,WertzV,VerleysenM
The
concentrationoffrac-
tionaldistances[J].IEEETransactions
on
KnowledgeandData
Engineering,2007,19(7):873-886
[15]DurrantRJ,Kab6nAWhen
is‘nearest
neighbor’meaningful:
A
converse
theoremandimplications[J].Journal
ofComplexity,
2009,25(4):385-397
[16]Beyer
neighbor”m锄angfd?[M]//Datahase‰巧rICDT’99.
K,GoldsteinJ,RamakrishnanR,eta1.Whenis。nearest
Springer
BerlinHeidelberg,1999:217-235
[17]HinneburgA,Agga,walCC,KeimDAwhatisthene.arest
neighborin
high
dimensionalspaces?[M].Bibliothekder
UIliversit豆tKonstanz。2000
[18]FrancoisD,Werta
V,Verleysen
MNon-euclideen
metricsfor
similaritysearchinnoisydatasetsEC-]//Proc
ofESANN.2005
[19]Hsu
C
M,ChenMSOnthedesignandapplicabilityofdistance
functionsinhigh-dimensionaldata
spaee[J].IEEETransactions
on
KnowledgeandDataEngineering,2009,21(4):523-536
[20]A鼹啪l
CC,HinneburgA,Keim
D八On
the
surprising
be-
haviorofdistancemetricsinhighdimensionalspaces[C]//P挣
ceedingsofthe8thInternational
Conference
on
Database
Theo-
ry,Ser.ICDT’01.London,UKISpringer-Verlag,20011420-434
[21]CanalLAnormalapproximationforthechi-squaredistribution
[J].ComputationalStatistics&Data
Analysis,2005,48(4):
803—808
[223
KatafygiotisLS。ZuevKM
Geometricinsightintothechallen-
gesof
solving
high-dimensionalreliabilityproblemsEJ].Pmbabi—
listicEngineeringMechanics,2008,23(2):208-218
D3]Wang
liar卜zhong.Crl帕metricStructureofHigh-Dimensiona/Da-
taandDimensionalityReduction[C]//Higher
EducationPress
(China)andSpringer.Beijing,2011
[241HoperoftJ。KennanRComputerScienceTheoryfortheInfor-
mation
AgeEM].Spring,2012:7-27
・217・
高维数据空间的性质及度量选择
作者:
作者单位:刊名:英文刊名:年,卷(期):
何进荣, 丁立新, 胡庆辉, 李照奎, HE Jin-rong, DING Li-xin, HU Qing-hui, LI Zhao-kui武汉大学计算机学院软件工程国家重点实验室 武汉430072计算机科学
Computer Science2014,41(3)
本文链接:http://d.wanfangdata.com.cn/Periodical_jsjkx201403046.aspx