高维数据空间的性质及度量选择

第４１卷第３期２０１４年３月

计算机科学

Ｃｏｍｐｕｔｅｒ

Ｓｃｉｅｎｃｅ

Ｖ０１．４１Ｎｏ．３

Ｍａｒ

２０１４

高维数据空间的性质及度量选择

何进荣丁立新胡庆辉李照奎

（武汉大学计算机学院软件工程国家重点实验室

武汉４３００７２）

摘要高维数据分析是机器学习和数据挖掘研究中的主要内容，降维算法通过寻找数据表示的最优子空间来约减

维数，在降低计算代价的同时，也提高了后续分类或者聚类算法的性能，从而成为高维数据分析的有效手段。然而，目前缺乏高维数据分析的理论指导。对高维数据空间的统计和几何性质进行了综述，从不同的角度给出了高维数据空

间中“度量集中”现象的直观解释，并讨论了通过度量选择的方式来提高经典的基于距离度量的机器学习算法在分析

高维数据时的性能。实验表明，分数距离度量方式可以显著提高Ｋ近邻和Ｋ１Ｔｌｅａｒｌｓ算法的性能。关键词

高维数据，维数灾难，度量集中

文献标识码Ａ

中图法分类号ＴＰｌ８１

Ｐ】叫ｐｅｎｉ箦ｏｆＨｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌＤａｔａＳｐａｃｅａｎｄＭｅｔｒｉｃＣｈｏｉｃｅ

ＨＥＪｉｍｍｎｇ

ＤＩＮＧＬｉ－ｘｉｎ

ＨＵＱｉｎｇ－ｈｕｉ

ＬＩＺｈａｏ－ｋｕｉ

（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ。ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００７２，ＣＫｍ）

Ａｌ葛ｔｒａｅｔ

ｓｐａｃｅ

Ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａａｎａｌｙｓｉｓｉｓｔｈｅ

ｃｏｒｅ

ｔａｓｋｏｆｍａｃｈｉｎｅｌｅａｒｎｉｎｇａｎｄｄａｔａｍｉｎｉｎｇ．Ｂｙｆｉｎｄｉｎｇｏｐｔｉｍａｌｓｕｂ—

ｃａｉｌｔ

ｆｏｒｄａｔａｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ｄｉｍｅｎｓｉｏｎａｌｉｔｙｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｓ

ｏｒ

ｒｅｄｕｃｅｃｏｍｐｕｔａｔｉｏｎａｌ

ｃｏｓｔ

ａｎｄｉｍｐｒｏｖｅｔｈｅｐｅｒ－

ｆｏｒｍａｎｃｅｏｆｓｕｂｓｅｑｕｅｎｔｃｌａｓｓｉｆｉｃａｔｉｏｎ

ａｎａｌｙｓｉｓ．Ｈｏｗｅｖｅｒ．ｔｈｅｒｅｉｓｖｅｒｙｌｉｔｔｌｅ

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

ｆｏｒｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｉｓ

ｏｉｌ

ｇｕｉｄａｎｃｅｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａ．ＴｌｌｉＳ

ｇａｖｅ

ｐａｐｅｒ

ｒｅｖｉｅｗｅｄ

ｏｎ“ｃｏｎ－

ｓｏｍｅｓｔａｔｉｓｔｉｃａｌａｎｄｇｅｏｍｅｔｒｉｃａｌｐｒｏｐｅｒｔｉｅｓｏｆｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａｓｐａｃｅ．ａｎｄ

ｃｅｎｔｒａｔｉｏｎｏｆｍｅａｓｕｒｅ”ｐｈｅｎｏｍｅｎｏｎｆｒｏｍｄｉｆｆｅｒｅｎｔｐｅｒｓｐｅｃｔｉｖｅｓ．Ｉｎｏｒｄｅｒｔｏｌｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍｓｂａｓｅｄ

ｏｎ

ｓｏｍｅｉｎｔｕｉｔｉｖｅｅｘｐｌａｎａｔｉｏｎｓ

ｉｍｐｍｖｅｐｅｒｆｏｒｍａｎｃｅｓｏｆｃｌａｓｓｉｃａｌｍａｃｈｉｎｅ

ｏｎ

ｄｉｓｔａｎｃｅｍｅｔｒｉｃ，ｔｈｉｓｐａｐｅｒ

ｄｉｓｃｕｓｓｅｄｔｈｅｅｆｆｅｃｔｓｏｆｍｅｔｒｉｃｃｈｏｉｃｅ

ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａ

ａｎａｌｙｓｉｓ．Ｅｍｐｉｒｉｃａｌ

ｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｆｒａｃｔｉｏｎａｌｄｉｓｔａｎｃｅｍｅｔｒｉｃｃａｎ

ｉｍｐｒｏｖｅｐｅｒｆｏｒｍａｎｃｅｓ

ｏｆＫＮｅａｒｅｓｔＮｅｉｇｈｂｏｒａｎｄ

Ｋｎｌｅａｎｓｓｉｇｎｉｆｉｃａｎｔｌｙ．

Ｋｅｙｗｏｔｄｓ

Ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａ，Ｃｕｒｓｅｏｆｄｉｍｅｎｓｉｏｎａｌｉｔｙ，Ｃｏｎｃｅｎｔｒａｔｉｏｎｏｆｍｅａｓｕｒｅ

１

引言

随着大数据时代的来临，高维数据分析已经成为应用驱

了研究，并讨论了降维算法在高维数据分类中的必要性。文献［１３３在化学信息学中分析分子之间的相似性度量时，讨论

高维分子描述空间的一些现象，比如空空问现象、距离度量集中现象等等。

动的热点研究问题Ｉｔ，２］。机器学习算法在直接处理高维数据

时，无可避免会遇到“维数灾难”问题［３］，即要达到同样的精

然而，国内外研究文献中关于高维数据空间的性质方面的专题研究非常少见，从而导致对高维数据的理论分析和算法设计缺乏指导。基于此，本文从几何和统计的角度，总结归

纳了高维数据空间的性质，当数据空间的样本维数无限增长

度，学习模型所需要的样本数随着样本维数的增加呈指数增

长，在算法应用研究中表现为“小样本”问题［４］，在数学分析上则表现为“度量集中”现象［５］。

由于在计算机处理中，数据通常是作为向量进行运算，因

此高维数据空间本质上就是向量空间。目前关于高维数据空间性质的讨论，主要集中于数据库技术中相似性检索方法的研究睁９｜，当数据库中每条记录的属性较多时，欧氏度量下的

时，本文从各个侧面给出了“度量集中”现象的直观解释。最后通过实验分析，讨论了不同的距离度量对机器学习算法性

能的影响。

２高维数据空间的统计性质

大数定律和集中不等式是分析高维数据空间统计性质的

基本工具。下面给出分析高维数据空间统计性质的相关定义和结论。

最近邻就失去意义。文献Ｅｔ０３在分析基因和蛋白质表达数据

时，以此为例解释了高维数据数据空间中的一些性质。文献

［１１，１２］以超光谱数据分析为例，对高维数据空间的特性进行

到稿日期：２０１３－０５—１９返惨日期：２０１３－０９－１６

本文受中央高校基本科研业务费专项资金（２０１２２１１０２０２０９），广东省省部产学研结合专项

（２０１１８０９０４００４７７），珠海市产学研合作专项资金（２０１１Ａ０５０１０１００５，２０１２Ｄ０５０１９９００１６），珠海市重点实验室科技攻关项目（２０１２Ｄ０５０１９９００２６）资助。何进荣（１９８４－－），男，博士生，主要研究方向为特征提取、高维数据分析，Ｅ－ｍａｉｌ：｝Ｉｅｊｉｎｒｏｎｇ＠１ｗｈＩＬｅｄｕ．ｃｒｌ！丁立新（１９６７一），男，教授，博士生导师，主要研究方向为智能信息处理、云计算；胡庆辉（１９７６一），男，博士生，主要研究方向为机器学习；李照蠢（１９７６一），男，博士生，主要研究方向为机器学习。・２１２・

２．１高维数据空间中的度量

定义１

ｄ维向量空间中的某点ｚ一（ｚ‘１’，ｚＱ’，…，ｚ∽）

定理５Ｅ２１３

（Ｏ，１）。

Ｖｚ∈Ｘ，∑（ｚ（。）２～癌，且ｌｋｎ∑（ｚ“’）２～Ｎｄ—＋十∞ｌ—ｌ

ｆ＝ｌ

∈础的矿范数定义为：

ｄ

Ｉｌｚ忆一（墨（ｚ“’）’）告

当户＜１时，该范数又称为分数范数‘“］。定理１［１５１

定理６［２ｚ］

Ｖｚ∈ｘ川ｚ忆二Ｎ（√ｄ一丢，丢）≈Ｎ

ｚ

任给是＞ｏ，如果睡誉襻一ｏ，则姆Ｐ

、”一“枷Ｅ（｜Ｉ

（佰，百Ｉ）。即当维数ｄ趋向于无穷大时，ｌＩ

态分布。

ＩＩｚ近似服从正

。７一ｈ（塑巫性业车身咚岐业＜。）一１。ｍｉｎ（ＩＩ１｜ｐ）

、

该定理表明，ｄ维标准高斯空间中的绝大部分概率集中于一个超球壳上，即

ｚ

（型必矫芈＜￡）＿１．贝ｍ］～ｌｉｒａｉｎ（

、

定理２［１６３假设样本数目理足够大，使得Ｅ（ＩＩｚ雌）２∈

［，ｒａ≤确ｉｎ｜｜Ｘｉ忪，。ｍ≤酶ａｘ｜｜Ｘｉ吣］成立。如果扣ｌｋｎ

｜｜ｚ｜｜ｐ）

ｚ

此处型坚山｛黑音艿野掣称为范数的相对差异，

ＲⅥ一誉揣称为相对方差。

ｏ。

黜一

Ｐ

佰一￡＜ｌｌ

ｚ

ＩＩ。＜瓶＋ｅ

例如：当ｄ一１０００，￡一３．４６时：Ｐ（２８．１６＜ｌ｜ｚｌｌ＜３５．０８）≥１—１０“

Ｉ｜；）２

３高维数据空间的几何性质

投影法和截面法是分析高维数据空间几何性质的基本工具。类比于平面几何和立体几何中的概念，我们可以定义如下的高维几何体，并推导出高维几何体的一些奇特性质，这些性质可以看作是“度量集中”现象的几何直观解释。３．１超立方体３．１．１相关定义

定义３中心在坐标原点、边长为２ｒ的ｄ维超立方体Ｃ４（ｒ）为

∥（ｒ）一｛（ｚｎ’，…，ｚ‘田）Ｉ—ｒ≤ｚ“’≤，－ｆｏｒａｌｌｉ｝垒［一ｒ，

该定理表明，随着数据空间维数的增加，样本点范数的相对差异和相对方差都趋于０。在高维数据空间中，某个样本点到其最近邻居点和最远邻居点之间的距离趋于相等，从而导致一些基于距离度量的机器学习算法性能降低。这种现象通常称为“度量集中”，最早由Ｍｉｌｍａｎ在描述高维概率分布时引入［５Ｉ。随着维数的增长，欧氏空间中任意两点间距离度量的差异性变得越来越弱，从而导致数据趋向于均匀分布。

已有相关研究表明Ｆ１７－２０］，高维空间中数据点之间的相似性度量对矿范数中Ｐ值的选取比较敏感。图１显示了ＩＩｚ忆一１在二维情形下的图形，Ｐ值越小，其边界越靠近坐标轴，在机器学习算法中越容易导致稀疏解。

ｒ］。

特别地，０维立方体就是一个点，１维立方体是一条线段，二维立方体是一个正方形。显然，超立方体Ｃｄ（，．）共有２４个

顶点，２ｄ个ｄ一１维侧面，２‘鸬个ｄ一是维的侧面（鸬表示ｄ

中取出ｋ个的排列数），且每个侧面可看作是超立方体。超立

方体的顶点为ｕ一（±，．，…，士ｒ），到坐标原点的距离为ｒ仃。

图蓦堕兰囵

图ｌ不Ｉ司扩范数下的单位圆

单位超立方体可以表示为∥（÷），其直径（超立方体上任意

两点之间距离的最大值）为√万。

定义４超立方体Ｃｄ（ｒ）的赤道面为

Ｈｏ一｛ｚ：Ｅｚ‘ｉ’一Ｏ｝

定理３Ｌ２０］

给定咒个ｄ维样本点，其每个分量相互独立

则Ｈｃ一｛ｚ：∑ｚ“’一ｃ）就表示与Ｈ。平行的超平面，点ｚ一（ｚｎ’，…，ｚ“’）到Ｈｏ的垂直距离为

且来自于均匀分布，则存在常数Ｃ，使得

ｃ・√赤≤恕Ｅ（警皆）≤ｃ嘞＿１）・

ｒ弋一

ｄｉｓｔ（ｘ，Ｈｏ）一去ｌ∑ｚ“’Ｉ

４ｄ

１＝１

√—２ｐ＋—１

这里ｄｉｓｔ‰和出ｓ缔。分别表示＂个样本点之间的最大扩距离

度量和最小矿距离度量。

此定理表明，由分数距离度量所计算的样本点之间的相对差异性更大。２．２高斯空间

定义２

ｄ维标准高斯空间由各个分量相互独立且来源

定义５

ｄ维超立方体Ｃ４（ｒ）的体积为：

Ｖ（Ｃｙ（ｒ））一（２ｒ）×（２ｒ）×…×（２ｒ）一（２ｒ）４

＼—————————————、／’——————————一ｄｆ岫

注意到，超立方体的体积随着维数呈指数增长。定义６体积之和，即

Ｓ（Ｃｄ（ｒ））＝（２ｄ）×Ｖ（Ｃｙ～１（ｒ））

ｄ维超立方体Ｃ。（ｒ）的表面积为其所有侧面的

于标准正态分布的ｄ维随机向量构成，即

Ｘ一｛（ｚ‘”，ｚ‘∞，…，ｚ‘ｄ’）：ｚ‘；’～Ｎ（Ｏ，１），ｉ一１，…，ｄ｝

３．１．２重要性质

其概率密度函数为

如）一士（２ｎ）２ｅｘｐ（一掣）

定理４

ＶｘＥｘ，Ｅ（｜｜ｚＩ｜；）一ｄ・Ｅ（（ｚ“’）。）一ｄ。

定理７恕ｃｏｓ‘１ｒ新，ｅｌ＞一０，其中ｅｉ表示坐标轴上的

单位向量。

该定理说明，随着维数的增长，超立方体的对角线逐渐正交于所有的坐标轴。

・

２１３

・

定理８Ｖ。一（ｚ（１），…，ｚ（田）∈鼎，且ｚ（ｉ）２三，【，（一０．５，

０．５），则

Ｅ（ｄｉｓｆｌ（ｘ，／４０））一百１

证明：根据定义４，可知

Ｅ哮Ｉ量∥’Ｉ）２＝吉％ｒ（量∥’）＝ｉ１蚤ｄ％ｒ（∥’）

＝上ｄｉ§＝１ｆ上１２、一上１２

该定理说明，单位超立方体内任一点到其赤道面Ｈ０的

平均平方距离为壶。

ｆｏ，

Ｋ专

定理９枷ｌｈ［１１Ｖ（Ｃｄ（ｒ））＝｛１，ｒ一号ｔ—

●

【ｏ。，ｒ＞丢

定理１０

ｅ∈（ｏ，

４＿．∞

１坠ｙ（∥（专）一∥（专一专））一１，ｖ

ｏ

■

厶

１）。

该定理表明，单位超立方体的体积主要集中在其外壳上。

这也启发我们，原始高维数据的某个度量实际上分布在某个

维数较低的子空间，这也是降维算法实施的依据之一。

定理１１

—ｅ～，Ｖ￡∈

厶厶ｏ“

（０，ｄ）。

定理１２璺窭笺ｇ詈寻＝ｏ，Ｖ

ｒ∈（ｏ，＋。。）。

３．２超球体３．２．１相关定义

定义７圆心在坐标原点、半径为ｒ的ｄ维超球体定义

为

Ｂ。（７．）：｛（ｚ＜１），…，ｚ（由）Ｉ∑ｄ（ｚ（ｔ’）ｚ≤户｝

ｉ＝１

其体积‘２３３为

ｖ（∥（ｒ））一鱼鸳

ｄｒ（要）

ｒ∞

１这里ｒ（ｓ）＝｝ｅ－ｔｔ’１ｄｔ是Ｇａｍｍａ函数，且ｒ（寺）一Ｊ０

厶

压，ｒ（１）＝１，ｒ（ｚ＋１）一ｚｒ（ｚ）。

特别地，单位超球体的体积为：

寿一

ｄ＝２ｐ

ｖ（∥（１））一＿

ｆ

【

ｄ＝２ｐ＋１

显然，Ｖ（∥（ｒ））＝Ｖ（Ｂｄ（１））・一。于是，超立方体∥

（ｒ）的外接球为Ｂｄ（ｒ扭），内切球为Ｂｄ（ｒ）。

定义８超球体∥（ｒ）的表面称为球面，记作ａ（∥（ｒ）），

即

ｄ

ａ（Ｂａ（ｒ））一｛（ｚ（ｕ，…，Ｘ‘ｄ））Ｉ∑（ｚ‘‘’）２＝ｒ２）

注意，ａ（Ｂｄ（ｒ））可以看作是ｄ维欧氏空间中的ｄ一１维流形。从拓扑观点来看，ｄ维球面可以表示为ａ（Ｂａ＋１（口））一

剐Ｕ｛。ｏ），其局部同构于ｄ维欧氏空间Ｒ４。

定义９超球体Ｂａ（ｒ）的表面积定义为

・２１４・

Ｓ（Ｂ４（ｒ））一Ｓ（∥（１））∥－１

等价地，ｄ维单位超球体可以看作是对ｄ一１维球壳的积分，

即

Ｖ（Ｂｄ（１））＝Ｉ

Ｓ（∥（１））一－１ｄｒ

Ｊ０

于是

’

．ｓ（∥（ｒ））一芋（ｖ（∥（力））一ｄ・Ｖ（∥（１））・∥１

ｄｒ

定义１０超球体的中心切片定义为

剧（ｒ）＝｛ｚ：０

ｚ

Ｉｆ≤ｒ，一ｇ◇ｎ’≤ｅ，ｓ∈（ｏ，ｒ））

３．２．２重要性质

根据上面的定义，容易导出如下的相关定理。

定理１３与ｄ维超立方体的每个ｄ一１维侧面相交的ｄ维超球体不一定包含超立方体的中心。如图２所示。

夕／＼＼

、

●

起立方体．

中心

／

＼

／

，

图２定理１３的几何解释

考虑下面的反例。假设中心点在坐标原点的单位超立方体，当ｄ＝１６时，假设超球体的球心在（Ｏ．２，…，０．２）处，该点

到坐标原点的欧氏距离为／１６・０．２２一ｏ．８，此时定义该超球体的半径为０．７，则该超球体与单位超立方体的所有１５个侧面相交。显然，超立方体的中心点并不包含在超球体中。

定理１４

ｖ（∥（１））一墅譬粤卫，ｓ（Ｂ抖・（１））一２ｎＶ

（∥一１（１）），ｖ（∥（１））：姿ｖ（∥一２（１）），ｓ（酽（１））：笔ｓ

ａ

口一二

（Ｂａ一２（１））。

该定理容易由定义７和定义９得出，反映了单位超球体

的体积与其表面积之间的递归关系。

定理１５ｌｉｍＶ（∥（ｒ））＝Ｏ，ｌｉｍＳ（∥（ｒ））一Ｏ。

定理１

６［２４］！酬脚励：ｊｏ’≤专。～

ｌ嗡ｒ＞去

上面两个定理表明，任给超立方体∥（ｒ）（ｒ＞—柰＝），随

着维数ｄ的增加，其外接超球体的体积趋向于无穷大，而内切

超球体的体积趋向于０。

定理１７恕嬲＿ｏ。

该定理表明，高维超球体的体积集中在球壳上。例如，当

ｄ≥５００时，至少９９％的体积包含在厚度为１％的球壳上。

定理１８恕弋面酊笋－ｅ＿三。

ｖ（Ｂ。（ｒ一｛））

证明：根据定义７，可得

罂—氓萨矿一撄

，．Ｖ（∥（ｒ一言”

，．

２（ｒ－－ｄ）。寇州导）

ｄｒ（ｄ）２一老

：１ｉｎｌ（１一Ｚ６－５）４一ｅ一手ｄ—一

ｒａ

定理１９地潞黑＿００

该定理表明，随着维数的增加，超立方体的体积主要集中于超立方体的边角上，即其内切超球体的体积所占比重越来越小。因此，在高维数据空间的结构分析中，其内部中心往往是“空”的，这种现象被称为“空空间”现象。

４．１

人工数据集上的距离度量选择

实验中，随机生成１０００个ｄ维样本点，每个维度分量相

互独立且服从［ｏ，１］区间上的均匀分布。随着维数ｄ的增加，

样本点的矿范数（实验中分别取ｐ＝Ｏ．５，１，１．５，２四种情形）的分布呈现出较大的差异，如图３所示，维数ｄ越高，范数分布的集中效应越明显，且Ｐ越大，这种集中趋势越突出。另外随着维数ｄ的增加，其均值以不同的方式增大，其中Ｐ一０．５时呈先慢后快增长趋势，ｐ一１时呈线性增长趋势，ｐ＞ｌ时呈先快后慢增长趋势（见图４（ａ））；当ｐ＜２时，其方差随着维数增加而增加，ｐ＝２时，方差呈现减小趋势（见图４（ｂ））；而相对方差和相对差异随着维数增加而快速减ｚｂ（见图４（ｃ）和（ｄ））。

由图３和图４所示的实验结果可以看出，当采用分数范数（即ｐ＜ｌ时）的距离度量方式时，样本间的“度量集中”现象比声＞１时较弱。

ｐ＝０．５

ｐ＝ｌ

Ｉ产１５

定理２０您潞端－１，地器湍一１。

该定理表明，高维超球体的体积、表面积主要集中于中心切片上。

３．３其他高维几何体

下面再介绍几类具有解析形式的体积计算公式的高维几何体。

３．３．１超长方体

ｄ维的超长方体Ｒ４（Ⅱ）定义如下：

尺ｄ（Ⅱ）＝｛（ｚ‘ｕ，…，ｚ‘由）Ｉ一乜“’≤≤ｚ“’≤≤以“’，口“’∈Ｒ＋｝其体积为：

Ｖ（Ｒｏ）＝２４Ⅱｎ‘ｉ’

萨２

３．３．２超平行几何体

超平行几何体是平行四边形和平行六面体概念在高维空间中的推广，可定义为：

‰，一坛淼筹宰｝

超平行几何体∥（口）可以看作是由超长方体掣（ｎ）经过

可逆线性变换得到的，因此

Ｖ（Ｐ（ｎ））一Ｉｄｅｔ（Ａ叫）ｌ・Ｖ（副（口））

３．３．３超单纯形

ｄ维超单纯形是三角形概念在高维的推广，可以定义为９一｛ｚ：Ｏ≤ｚ‘１’≤ｚ‘２’≤…≤ｚ‘田≤１｝

显然，超单纯形铲具有如下形式的ｄ＋１个顶点：

｛（Ｏ，ｏ，…，Ｏ），（ｏ，１，ｏ，…，ｏ），（ｏ，１，１，…，ｏ），…，（１，１，…，１））

下面推导其体积计算公式。注意到在超立方体｛ｚ：ｏ≤ｚ“’≤１｝内共有ｄ！种不同的顶点坐标排列。下面考虑另一个超单纯形，其（ｆ＋１个顶点如下：

掰一｛（Ｏ，ｏ，…，Ｏ），（１，０，ｏ，…，Ｏ），（Ｏ，１，ｏ，…，Ｏ），…，（Ｏ，

ｏ，…，ｏ，１））

根据顶点ｘＥ∥和Ｙ∈Ｓ｝的关系：

ｄ

ｌ＝ｌ

ｄ

ｌ二Ｚ

ｄ

ｚ‘１’一ｊ，‘西，ｚ‘２’一∑ｙ‘订，．２７‘３’＝∑ｙ‘ｎ，…，．２７‘由＝∑Ｙ‘ｉ’ｌ＝ｄ—ｌ

可知此处的线性变换矩阵的行列式为１，即Ｖ（９）一Ｖ（研），因此超单纯形９的体积为

Ｖ（９）＝击

４实验结果

根据以上对高维数据空间的奇特性质的综述可以看出，“度量集中”现象是高维数据分析的一大难点，传统的基于欧氏距离度量的算法不适合高维数据分析。维数约减是克服这一困难的常规方法，然而维数约减无可避免地会导致数据中蕴含的某些信息的损失，本文主要研究度量选择对机器学习算法性能的影响。下面通过实验来讨论高维数据空问中不同距离度量的分布，及其对经典的基于距离度量的机器学习算法（如ＫＮＮ和Ｋｍｅａｎｓ）的影响。

・

誊囫｛１盟＂霰５

０２

噩０．０７０．０６网

；№州

ｇ

ｌ｜

２１５

・

￡ｇ

ｇ｛｝ｊ

Ｅ

均值，算法性能比较结果见表３和表４。

０２

：０３５

ｎ１

。０．０５＝

Ｏ

篓ｎ

（Ｃ）范数的相对方差

表３扩范数度量下的ＫＮＮ分类结果

ｏＦ２寄—‘

表４扩范数度量下的Ｋ—ｍｅａｎｓ聚类结果

（ｄ）范数的相对差异

图４高维空间中样本点范数的均值（ａ）、方差（ｂ）、相对方差（ｃ）和

相对差异（ｄ）

４．２

ＵＣＩ数据集上的距离度量选择

为了验证不同范数的选择对机器学习算法性能的影响，

实验表明，分数范数度量可以显著提高经典的分类算法ＫＮＮ和聚类算法Ｋ—ｍｅａｎｓ在高维数据集上的性能。４．３人脸数据集上的距离度量选择

人脸图像数据是典型的高维数据，在人脸识别实验中，首先将图像数据拉直变成向量形式，假设经过裁剪之后的人脸图像长为３２个像素，宽为３２个像素，则在算法处理中通常将其转换为１０２４（３２×３２）维的向量。实验中选取了Ｙａｌｅ、Ｏｌｉ－ｖｅｔｔｉ、ＵＭＩＳＴ和ＧｅｏｒｇｉａＴｅｅｈ等人脸数据集（见表５），分别在不同的距离度量设置下，采用ＫＮＮ算法（五取１）进行人脸识别，其中每个人脸随机抽取Ｔ张图片作为训练集，其余的作为测试集。每次实验重复进行５０次，平均识别准确率见表６一表９，当ｐ＝０．５时，ＫＮＮ算法取得最高的识别准确率。

表５人脸数据集描述

名称

维数

１０２４２５７６６４４１８００

我们选用来自于真实世界的ＵＣＩ测试数据集ｎ，数据集相关描述如表１所列。对于原始数据集中属性有缺失的情形，实验中直接对其赋值一１。同时，实验中首先对每个维度上的数据按照下面的公式规范化为０到１之间：

ｂＥ（／）一ｍｉｎ（ｚ‘ｉ’）‘ｍ。。。‘‘。ａ。。。ｘ。。。。。（’。。ｘ。。。。（。。／）。。。。。）。。。。－。。’’’。。。ｍ。。‘。。。ｉ。。ｎ。。。。（。。。ｘ。。。。。（。。Ｉ。——）

表１数据集描述

样本数

１６５４００５７５７５０

类别数

１５４０２０５０

实验中，我们首先计算了各个数据集上不同范数度量下的相对差异。由表２的计算结果可知，ｐ＝Ｏ．５时，样本范数的相对差异最大，这也意味着在该范数度量下的机器学习算法的性能也应该是最好的。

表２

ＵＣＩ数据集上的样本扩范数相对差异

Ｙａｌｅｚ）Ｏｌｉｖｅｔｔｉｓ）Ｕ￣Ⅱｇｒ４）

ｃ，ｅｏｒｇｉ【ａＴｅｃｈ５）

表６扩范数度量下的ＫＮＮ人脸识别结果（Ｙａｌｅ）

表７扩范数度量下的ＫＮＮ人脸识别结果（Ｏｌｉｖｅｔｔｉ）

在分类任务的实验中，我们采用基于不同的范数度量的ＫＮＮ算法，实验中ｋ取３，对样本集进行随机划分，５０％作为训练集，５０％作为测试集，其评价指标为误分率；在聚类任务的实验中，我们采用基于不同的范数度量的Ｋ－ｍｅａｎｓ算法，初始聚类中心随机选择，最大迭代次数为１０００，其评价指标为ＲａｎｄＩｎｄｅｘ。每个数据集上的算法重复执行５０次后取平

表８扩范数度量下的ＫＮＮ人脸识别结果（ＵＭＩＳＴ）

１）ｈｔｔｐ：／／ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ／ｍｌ／ｄａｔａｓｅｔｓ．ｈｔｍｌ

毡ｈｔｔｐ：｜｜恻．ｅｓ．ｎｙｕ．ｅｄｕ／～ｒｏｗｅｉｓ／ｄａｔａ．ｈｔｍｌ

・２１６・

∞ＣＶＣ．ｙａｌｅ．ｅｄｕ／ｐｒｏｊｅｃｔｓ／ｙａｌｅｆａｅｅｓ／ｙａｌｅｆａｃｅｓ．ｈｔｍｌ

４）ｈｔｔｐ：／／ｉｍａｇｅｓ．ｅｅ．ｕｍｉｓｔ．ａｃ．ｕｋ／ｄａｎｎｙ／ｄａｔａｂａｓｅ．ｈｔｍｌ５）ｈｔｔｐ：／／ｗｗｗ．ａｎｅｆｉａｎ．ｃｏｒｎ／ｒｅｓｅａｒｃｈ／ｆａｃｅｒｅｃｏ．ｈｔｍ

表９扩范数度量下的ＫＮＮ人脸识别结果（ＧｅｏｒｇｉａＴｅｃｈ）

结束语本文对高维数据空间的统计性质和几何性质进行了系统的综述，这些性质都可以看作是“度量集中”现象的

具体表现。当样本的维数增大时，数据集呈现出“度量集中”现象，即不同样本之问的距离度量的相对差异在逐渐减小，这使得基于样本间距离度量的机器学习算法的性能大大降低。

因此，距离度量的选择对于机器学习算法至关重要，本文通过

大量实验讨论了不同距离度量的选择对经典的机器学习算法（如ＫＮＮ和Ｋｍｅｎｎｓ）的影响，实验结果表明分数范数的距离度量可以显著提高算法性能。

参考文献

［１］Ｓｋｉｌｌｉｃｏｍ

Ｄ

ＲＵｎｄｅｒｓｔａｎｄｉｎｇＨｉｇｈ－ＤｉｍｅｎｓｉｏｎｅｄＳｐａｃｅｓ［Ｍ１．

Ｓｐｒｉｎｇｅｒ－ＶｅｒｌａｇＮｅｗＹｏｒｋＩｎｃｏｒｐｏｒａｔｅｄ，２０１３

［２］Ｄｏｎｏｈｏ

Ｄ

Ｌ

Ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａａｎａｌｙｓｉｓ：Ｔｈｅ

ｃｕｒｓｅｓ

ａｎｄ

ｂｌｅｓｓｉｎｇｓｏｆｄｉｍｅｎｓｉｏｎａｌｉｔｙ［刀．ＡＭＳＭａｔｈＣｈａｌｌｅｎｇｅｓＬｅｃｔｕｒｅ，

２０００：１－３２

［３］ＢｅｌｌｍａｎＲＡｄａｐｔｉｖｅＣｏｎｔｒｏｌＰｒｏｃｅｓｓ：ＡＧｕｉｄｅＴｏｕｒ［Ｍ］．Ｐｒｉｎ－

ｃｅｔｏｎＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，Ｐｒｉｎｃｅｔｏｎ，ＮｅｗＪｅｒｓｅｙ，１９６１

［４］ＦｕｋｕｎａｇａＫ

Ｉｎｔｒｏｄｕｃｔｉｏｎ

ｔｏ

ＳｔａｄｓｔｉｃａｌＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ（２ｎｄ

ｅｄ）［Ｍ］．ＮｅｗＹｏｒｋ：Ａｃａｄｅｍｉｃ，１９９０，３９－４０（３１—３４）；２２０－２２１

［５］Ｍｉｌ’ｍａｎＶＤ．ＮｅｗｐｒｏｏｆｏｆｔｈｅｔｈｅｏｒｅｍｏｆＡＤｖｏｒｅｔｚｋｙｏｎ

ｉｎ－

ｔｅｒｓｅｃｔｉｏｎｓ

ｏｆｃｏｎｖｅｘ

ｂｏｄｉｅｓ［Ｊ］．ＦｕｎｃｔｉｏｎａｌＡｎａｌｙｓｉｓａｎｄｉｔｓＡｐ

ｐｌｉｃａｔｉｏｎｓ，１９７１，５（４）：２８８－２９５

［６］ＷｅｂｅｒＲ，ＳｃｈｅｋＨ－Ｊ，ＢｌｏｔｔＳＡｑｕａｎｔｉｔａｔｉｖｅａｎａｌｙｓｉｓａｎｄｐｅｒ－

ｆｏｒｍａｎｃｅｓｔｕｄｙｆｏｒｓｉｍｉｌａｒｉｔｙ－ｓｍｒｄｌ

ｍｅｔｌｘＭｓｉｎ

ｈｉｔ出－ｄｉｍｍｓｉｃｍｌ

ｓｐａｃｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ

ｔｈｅ２４ｒｄＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ｏｎ

ＶｅｒｙＬａＩ＿ｇｅＤａｔａＢａｓｅｓ，ｓｅｔ＇．ＶＬＤＢ’９８．ＳａｎＦｒａｎｃｉｓｃｏ，ＣＡ，

ＵＳＡ：ＭｏｒｇａｎＫａｎｆｍａｒｍＰｕｂｌｉｓｈｅｒｓ

Ｉｎｃ，１９９８：１９４－２０５

［７］ＧａｅｄｅＶ，ＧＥｍｔｈｅｒＱ

Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ

ａｃ１Ｌ＇ｅｇｓ

ｍｅｔｈｏｄｓ［Ｊ］．

ＡＣＭＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙｓ（Ｃ：ＳＵＲ），１９９８。３０（２）：１７０－２３１

［８］ＦｒａｎｃｏｉｓＤ，ＷｅｒｔｚＶ，Ｖｅｒｌｅｙｓｅｎ腿Ｎｏｎ－ｅｕｃｌｉｄｅａｎ

ｍｅｔｒｉｃｓｆｏｒ

ｓｉｍｉｌａｒｉｔｙ

ｓｅａｒｃｈｉｎｎｏｉｓｙ

ｄａｔａｓｅｔｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ琰ｉＡＮＮ．２００５

［９］Ｋｏｕｉｒｏｕｋｉｄｉｓ

Ｎ，ＥｖａｎｇｅｌｉｄｉｓＧ．ＴｈｅＥｆｆｅｃｔｓｏｆＤｉｍｅｎｓｉｏｎａｌｉｔｙ

Ｃｕｒｓｅｉｎ

Ｈｉｇｈ

ＤｉｍｅｎｓｉｏｎａｌｋＮＮＳｅａｒｃｈ［Ｃ］／／Ｉｎｆｏｒｍａｔｉｅｓ

（１）ＣＩ），２０１１１５ｔｈＰａｎｈｅｌｌｅｎｉｅ

Ｃｏｎｆｅｒｅｎｃｅｏｉｌ．口ＥＥＥ。２０１１：４１－４５

［ｉ０３ＣｌａｒｋｅＲ，ＲｅｓｓｏｍＨＷ，ＷａｎｇＡ。ｅｔａ１．ＴｈｅｐｒｏｐｅｒｔｉｅｓｏｆｌＩｉｇｈ－

ｄｉｍｅｎｓｉｏｎａｌｄａｔａｓｐａｃｅｓ：ｉｍｐｌｉｃａｔｉｏｎｓｆｏｒｅｘｐｌｏｒｉｎｇｇｅｎｅａｎｄ

ｐｒｏ－

ｔｅｉｎｅｘｐｒｅｓｓｉｏｎｄａｔａ［Ｊ］．ＮａｔｕｒｅＲｅｖｉｅｗｓＣａｎｃｅｒ，２００８，８（１）：３７—

４９

［１１］Ｊｉｍｅｎｅｚ

Ｌ，ＬａｎｄｇｒｅｂｅｎＳｕｐｅｒｖｉｓｅｄＣｌａｓｓｉｆｉｃａｔｉｏｎｉｎＨｉｇｈＤｉ—

ｍｅｎｓｉｏｎａｌ

Ｓｐａｃｅ：Ｇｅｏｍｅｔｒｉｃａｌ，Ｓｔａｔｉｓｔｉｃａｌ

ａｎｄ

Ａｓｙｍｐｔｏｔｉｃｓｌ

ＰｒｏｐｅｒｔｉｅｓｏｆＭｕｌｔｉｖａｒｉａｔｅｄａｔａ［ｊ］．ＩＥＥＥＴｒｓｎｓａｃｔｉｏｎｓ

ｏｎ

Ｇｅｏ－

ｓｃｉｅｎｃｅａｎｄＲｅｍｏｔｅＳｅｎｓｉｎｇ，１９９９，３７（６）

［１２］Ｊｉｍｅｎｅｚ

Ｌ，ＬａｎｄｇｒｅｂｅＤ．Ｈｉｇｈｄｉｍｅｎｓｉｏｎａｌｆｅａｔｕｒｅｒｅｄｕｃｔｉｏｎｖｉａ

ｐｒｏｊｅｃｔｉｏｎｐｕｒｓｕｉｔ［Ｃ］／／ＧｅｏｓｃｉｅｎｃｅａｎｄＲｅｍｏｔｅＳｅｎｓｉｎｇＳｙｍｐｏ－

ｓｉｕｍ，１９９４．ＩＧＡＲＳＳ’９４．Ｓｕｒｆａｃｅａｎｄ

Ａｔｍｏｓｐｈｅｒｉｃ

Ｒｅｍｏｔｅ

Ｓｅｎｓｉｎｇ：Ｔｅｃｈｎｏｌｏｇｉｅｓ，ＤａｔａＡｎａｌｙｓｉｓａｎｄＩｎｔｅｒｐｒｅｔａｔｉｏｎ．Ｉｎｔｅｒ－

ｎａｔｉｏｎａｌ．ＩＥ匝，１９９４，２：１１４５—１１４７

［１３］ＲｕｐｐＭ，ＳｃｈｎｅｉｄｅｒＰ，ＳｃｈｎｅｉｄｅｒＧ．Ｄｉｓｔａｎｃｅｐｈｅｎｏｍｅｎａ

ｉｎ

ｈｉｇｈ－

ｄｉｍｅｎｓｉｏｎａｌｃｈｅｍｉｃａｌｄｅｓｃｒｉｐｔｏｒｓｐａｃｅｓ：Ｃｏｎｓｅｑｕｅｎｃｅｓ

ｆｏｒｓｉｍｉ—ｌａｒｉｔｙ－ｂａｓｅｄ

ａｐｐｒｏａｃｈｅｓ［Ｊ］．Ｊｏｕｒｎａｌｏｆ

Ｃｏｍｐｕｔａｔｉｏｎａｌ

Ｃｈｅｍｉｓ—

ｔｒｙ，２００９，３０（１４）：２２８５—２２９６

［１４］ＦｒａｎｃｏｉｓＤ，ＷｅｒｔｚＶ，ＶｅｒｌｅｙｓｅｎＭ

Ｔｈｅ

ｃｏｎｃｅｎｔｒａｔｉｏｎｏｆｆｒａｃ－

ｔｉｏｎａｌｄｉｓｔａｎｃｅｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ

ｏｎ

ＫｎｏｗｌｅｄｇｅａｎｄＤａｔａ

Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，１９（７）：８７３－８８６

［１５］ＤｕｒｒａｎｔＲＪ，Ｋａｂ６ｎＡＷｈｅｎ

ｉｓ‘ｎｅａｒｅｓｔ

ｎｅｉｇｈｂｏｒ’ｍｅａｎｉｎｇｆｕｌ：

Ａ

ｃｏｎｖｅｒｓｅ

ｔｈｅｏｒｅｍａｎｄｉｍｐｌｉｃａｔｉｏｎｓ［Ｊ］．Ｊｏｕｒｎａｌ

ｏｆＣｏｍｐｌｅｘｉｔｙ，

２００９，２５（４）：３８５－３９７

［１６］Ｂｅｙｅｒ

ｎｅｉｇｈｂｏｒ”ｍ锄ａｎｇｆｄ？［Ｍ］／／Ｄａｔａｈａｓｅ‰巧ｒＩＣＤＴ’９９．

Ｋ，ＧｏｌｄｓｔｅｉｎＪ，ＲａｍａｋｒｉｓｈｎａｎＲ，ｅｔａ１．Ｗｈｅｎｉｓ。ｎｅａｒｅｓｔ

Ｓｐｒｉｎｇｅｒ

ＢｅｒｌｉｎＨｅｉｄｅｌｂｅｒｇ，１９９９：２１７－２３５

［１７］ＨｉｎｎｅｂｕｒｇＡ，Ａｇｇａ，ｗａｌＣＣ，ＫｅｉｍＤＡｗｈａｔｉｓｔｈｅｎｅ．ａｒｅｓｔ

ｎｅｉｇｈｂｏｒｉｎ

ｈｉｇｈ

ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅｓ？［Ｍ］．Ｂｉｂｌｉｏｔｈｅｋｄｅｒ

ＵＩｌｉｖｅｒｓｉｔ豆ｔＫｏｎｓｔａｎｚ。２０００

［１８］ＦｒａｎｃｏｉｓＤ，Ｗｅｒｔａ

Ｖ，Ｖｅｒｌｅｙｓｅｎ

ＭＮｏｎ－ｅｕｃｌｉｄｅｅｎ

ｍｅｔｒｉｃｓｆｏｒ

ｓｉｍｉｌａｒｉｔｙｓｅａｒｃｈｉｎｎｏｉｓｙｄａｔａｓｅｔｓＥＣ－］／／Ｐｒｏｃ

ｏｆＥＳＡＮＮ．２００５

［１９］Ｈｓｕ

Ｃ

Ｍ，ＣｈｅｎＭＳＯｎｔｈｅｄｅｓｉｇｎａｎｄａｐｐｌｉｃａｂｉｌｉｔｙｏｆｄｉｓｔａｎｃｅ

ｆｕｎｃｔｉｏｎｓｉｎｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｄａｔａ

ｓｐａｅｅ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ

ｏｎ

ＫｎｏｗｌｅｄｇｅａｎｄＤａｔａＥｎｇｉｎｅｅｒｉｎｇ，２００９，２１（４）：５２３－５３６

［２０］Ａ鼹啪ｌ

ＣＣ，ＨｉｎｎｅｂｕｒｇＡ，Ｋｅｉｍ

Ｄ八Ｏｎ

ｔｈｅ

ｓｕｒｐｒｉｓｉｎｇ

ｂｅ－

ｈａｖｉｏｒｏｆｄｉｓｔａｎｃｅｍｅｔｒｉｃｓｉｎｈｉｇｈｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅｓ［Ｃ］／／Ｐ挣

ｃｅｅｄｉｎｇｓｏｆｔｈｅ８ｔｈＩｎｔｅｒｎａｔｉｏｎａｌ

Ｃｏｎｆｅｒｅｎｃｅ

ｏｎ

Ｄａｔａｂａｓｅ

Ｔｈｅｏ－

ｒｙ，Ｓｅｒ．ＩＣＤＴ’０１．Ｌｏｎｄｏｎ，ＵＫＩＳｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００１１４２０－４３４

［２１］ＣａｎａｌＬＡｎｏｒｍａｌａｐｐｒｏｘｉｍａｔｉｏｎｆｏｒｔｈｅｃｈｉ－ｓｑｕａｒｅｄｉｓｔｒｉｂｕｔｉｏｎ

［Ｊ］．ＣｏｍｐｕｔａｔｉｏｎａｌＳｔａｔｉｓｔｉｃｓ＆Ｄａｔａ

Ａｎａｌｙｓｉｓ，２００５，４８（４）：

８０３—８０８

［２２３

ＫａｔａｆｙｇｉｏｔｉｓＬＳ。ＺｕｅｖＫＭ

Ｇｅｏｍｅｔｒｉｃｉｎｓｉｇｈｔｉｎｔｏｔｈｅｃｈａｌｌｅｎ－

ｇｅｓｏｆ

ｓｏｌｖｉｎｇ

ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｒｅｌｉａｂｉｌｉｔｙｐｒｏｂｌｅｍｓＥＪ］．Ｐｍｂａｂｉ—

ｌｉｓｔｉｃＥｎｇｉｎｅｅｒｉｎｇＭｅｃｈａｎｉｃｓ，２００８，２３（２）：２０８－２１８

Ｄ３］Ｗａｎｇ

ｌｉａｒ卜ｚｈｏｎｇ．Ｃｒｌ帕ｍｅｔｒｉｃＳｔｒｕｃｔｕｒｅｏｆＨｉｇｈ－Ｄｉｍｅｎｓｉｏｎａ／Ｄａ－

ｔａａｎｄＤｉｍｅｎｓｉｏｎａｌｉｔｙＲｅｄｕｃｔｉｏｎ［Ｃ］／／Ｈｉｇｈｅｒ

ＥｄｕｃａｔｉｏｎＰｒｅｓｓ

（Ｃｈｉｎａ）ａｎｄＳｐｒｉｎｇｅｒ．Ｂｅｉｊｉｎｇ，２０１１

［２４１ＨｏｐｅｒｏｆｔＪ。ＫｅｎｎａｎＲＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅＴｈｅｏｒｙｆｏｒｔｈｅＩｎｆｏｒ－

ｍａｔｉｏｎ

ＡｇｅＥＭ］．Ｓｐｒｉｎｇ，２０１２：７－２７

・２１７・

高维数据空间的性质及度量选择

作者：

作者单位：刊名：英文刊名：年，卷(期)：

何进荣， 丁立新， 胡庆辉， 李照奎， 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