（计算机软件与理论专业论文）固有维数估计的研究与应用.pdf

中文摘要 随着信息技术的不断发展，高维数据越来越多。这些高维数据在提供更加详 细信息的同时，数据维数的大幅度提高也给数据处理工作带来了前所未有的困 难，不同研究者分别从各自的研究领域提出了多种维数约减算法。但是它们都有 一个共同的前提：只有数据集的固有维数( i n t r i n s i cd i m e n s i o n ) 被正确估计，才 能获得理想的降维效果。针对于此，固有维数估计( i n t r i n s i cd i m e n s i o ne s t i m a t i o n ) 研究成为了流形学习领域的重要研究方向。基于高维数据集的固有维数估计，可 以帮助人们更好地认识数据集的固有结构，发掘数据集潜在的信息，对于数据的 降维及其它的后续处理具有重要的意义。 本文在全面分析现有线性维数约减算法和非线性维数约减算法的基础上，重 点研究了固有维数估计算法，并就b a l 矗z sk d g l 的p d e ( p a c k i n gd i m e n s i o n e s t i m a t i o n ) 算法存在的问题进行了改进，提出了一种i p d e ( i m p r o v e m e n to n p a c k i n gd i m c n s i o ne s t i m a t i o n ) 算法。为了更好地验证i p d e 算法的优劣性，本文 对其进行了详细的算法实现。实验表明，i p d e 算法能够很好地解决p d e 算法存在 无用开销的问题，在运行效率上要优于p d e 算法，同时，在对不同类型的数据集 进行固有维数估计时，同样具有稳定性。实验最后将固有维数估计算法与维数约 减算法及模式识别技术结合起来，通过手写体字符识别实验进一步验证了i p d e 算法在实践中的稳定性以及实用价值。 关键词：流形学习，固有维数估计，维数约减，i p d e 算法 a b s t r a c t m o r ea n dm o i eh i g hd i m e n s i o n a ld a t ai so b t a i n e dw i t ht h ed e v e l o p m e n to fi n f o r m a t i o n t e c h n o l o g i e s h i g hd i m e n s i o n a ld a t ac a np r o v i d em o r ei n f o r m a t i o n ；h o w e v e r , h o wt og a i nt h e m o r ei m p o r t a n ti n f o r m a t i o nf r o m8 0m u c hd a t ai sb e c o m i n gad i f f i c u l tp r o b l e m a f t e rm a n yy e a r s o fr e s e a r c h , s o m ed i m e n s i o n a lr e d u c t i o nm e t h o d sw e r ep r o p o s e d , s u c ha sp c a ，l l ea n d l a p l a c i a ne i g e n m a p s ，e t c t h r o u g ht h e s em e t h o d s ，t h eh i g hd i m e n s i o n a ld a t ac a nb ee m b e d d e di n al o w e rs p a c e 。b u tan e wp r o b l e mh a sa r i s e n h o wm a n yi st h ed i m e n s i o no f e m b e d d i n gs p a c e ? s o ， i n t r i n s i cd i m e n s i o n a le s t i m a t i o ni sc o n c e r n e d i tc a l lh e l pt od i s c o v e rt h ei n t r i n s i cd i m e n s i o no f d a t as e t , a n dp l a y sag u i d i n gr o l ei nd i m e n s i o n a lr e d u c t i o n t h i sp a p e rf o c u s e so nt h e s t u d y i n go ft h e i n t r i n s i cd i m e n s i o n a le s t i m a t i o no fh i g h d i m e n s i o n a ld a t a a r e ra na n a l y s i st ot h ep r o b l e m so fp d e ( p a c k i n gd i m e n s i o ne s t i m a t i o n ) a l g o r i t h mp r o v i d e db yb a l 矗z s 聪g l ，a nt p d e ( i m p r o v e m e n t0 1 1p a c k i n gd i m e n s i o ne s t i m a t i o n ) a l g o r i t h ma n di t si m p l e m e n t a t i o ni sp r e s e n t e d t h ee x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mh a sa h i g h e rr u n n i n ge f f i c i e n c ya n ds t a b i l i t yt h a nt h ep d ea l g o r i t h m 。t h e n , b yc o m b i n i n g t h ei n t r i n s i c d i m e n s i o n a le s t i m a t i o na l g o r i t h m , d i m e n s i o nr e d u c t i o na l g o r i t h ma n dp a t t e r nr e c o g n i t i o n t e c h n o l o g y , t h es t a b i l i t ya n dv a l i d i t yo f t h ei p d ea l g o r i t h mi sf m t h e rp r o v e di nt h ee x p e r i n l e n to f h a n d w r i t i n gc h a r a c t e rr e c o g n i t i o n k e yw o r d s ：m a n i f o l dl e a r n i n g ，i n w i n s i cd i m e n s i o ne s t i m a t i o n ，d i m e n s i o nr e d u c t i o n , i p d e a l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：栖 l 欺 签字日期：1 年月2 日 学位论文版权使用授权书 本学位论文作者完全了解墨叠盘堂有关保留、使用学位论文的规定。 特授权丞鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 栖；上敏 2 月2 日 工 新躲几平腾 签字日期： 。一7 年2 月z 日 第一章绪论 1 1 研究背景和目的 第一章绪论 随着信息科学技术的不断发展，人们越来越多的接触到大量的高维数据。高 维数据在提供更加丰富、细致的信息的同时，数据维数的大幅度提高又会给数据 处理工作带来前所未有的困难。以c m u 数据库中的t u r n t n gc u p l 虱像数据集为例， 该数据集所包含图像的分辨率是6 4 * 6 4 ，即该数据集的维数为4 0 9 6 维，如图1 1 所示。 图1 1m m i n gc u p 数据集 如果直接对此数据集进行操作，其难度可想而知。不过，现实世界中多数复 杂的商维数据集完全可以由几个独立的变量表示。同样以该数据集为例该数据 集中的图像是对杯子进行水平旋转采集而成，也就是说，每幅图像部可以用角度 变量来表示，这将大大简化对该数据集的处理，同时，存储空间以及计算开销也 会大大减少。 为了发现这些独立的变量，流形学习( m a n i f o l dl e a r n i n g ) 作为机器学习的 一个分支受到了广泛的关注。目前，该领域研究主要分为两个方面，一方面是数 据集的固有维数估计另一个方面是探讨如何既能晟大保持数据集的原始信息， 又能简化数据集的复杂度。当前该领域的研究多侧重于第二个方面，即数据集的 维数约减。不同研究者分别从各自的研究领域提出了多种维数约减算法譬如主 成分分析( p r l n c i p a l c o m p o n e n t a r i a h s i s ，p c a ) “1 ，局部线性嵌入 0 ；求出这k 个特征根所对应 的k 个特征向量，并将其单位化，得到4 ，4 ：，4 。；得出 y 1 = 口：x ，j ，2 = 口；x ，y t = 口：x 。 经过上述讨论，可以总结出主成分分析算法的一些基本性质【2 】： ( 1 ) 各个主成分之间互不相关；若原变量服从正态，则各主成分之间互相 独立； ( 2 ) 各个主成分的作用大小是：y ，2y 2 乃； 五 ( 3 ) 前k 个主成分的累计贡献率是丝_ 1 0 0 ，在应用时，累计贡献率 m 为7 0 - 8 0 或以上即可。 主成分分析算法常被用来寻找判断某种事物或者现象的综合指标，并给综合 指标所蕴藏的信息以恰当的解释，以便更深刻地揭示事物固有的规律。它执行简 单，对于线性结构的数据集能够得到很好的降维结果。但是该方法是从全局的角 度考虑问题，没有考虑数据集的局部信息，在对非线性结构数据集进行处理时， 不可避免的丢失一些重要信息，很难达到理想的降维效果。 6 第二章流形学习概述 2 经典多维尺度算法 经典多维尺度算法( c l a s s i cm u l t i d i m e n s i o n a ls c a l i n g ，c m d s ) f 1 9 】，是一种 传统的寻求保持数据点之间差异性( 相似性) 的降维方法，最早由t o r g e r s o n 在 1 9 5 2 年提出的。其基本思想是：原数据集合中相近的点在嵌入空间中仍然很近， 远离的点仍然远离。c m d s 可保持数据点之间差异的特性，使其可广泛应用于人 工智能、经济学等研究领域。 c m d s 与p c a 相似，只是输入的矩阵有所不同：p c a 计算的是协方差矩阵； c m d s 输入的是点到点的距离所构成的矩阵。二者的输入矩阵都是对称的，半正 定的。 2 2 2 非线性维数约减算法 1 局部线性嵌入算法 局部线性嵌入( l o c a l l yl i n e a re m b e d d i n g ，简称l l e ) 2 0 】，是s a u l 和r o w e i s 在2 0 0 0 年提出的一种无监督的非线性学习理论。其基本思想是假设数据所在流 形是局部线性的，可以利用邻近点构建局部几何，然后寻找能够在平移、旋转、 伸缩变换下保持局部几何结构的局部线性映射，从而达到数据维数约减的目的。 该算法的提出使得人们更加关心局部信息，通过局部信息的探讨来进一步得到更 多的流形信息。 该算法认为在局部空间中，数据点的结构是线性的，每个数据点都可由它的 邻点线性重构。 假设个d 维输入数据 x ，x ， 据 j ，l ，y ) ，y ，霖。，d d 。 l l e 算法如下【2 1 也】： ， x i 专皿dj 通过u 正算法，得到输出数 输入参数：数据集x ，d n 矩阵，矩阵的每一列代表一个d 维数据点；邻 点数露；嵌入维数d ； 输出：y ，d n 矩阵，d d ； ( 1 ) 为数据集x 中的每个点寻找邻域点； ( 2 ) 构建重构权重矩阵缈； ( 3 ) 通过权重矩阵形计算嵌入坐标l ，。 l i 正算法中邻域点数的确定上有两种方法，一种是计算两点的欧氏距离，寻 找露个最近的点：另一种方法是指定球域占，球域中所包含的数据点就是邻域点。 l l e 算法计算邻域点的过程相当耗时，最坏精况下其复杂度为o ( d n 2 ) ，其 中d 为高维空间维数，为样本点数。 2 拉普拉斯特征映射算法 第二章流形学习概述 拉普拉斯特征映射( l a p l a c i a ne i g e n m a p s ) 【2 3 1 ，最优保持了原空间中数据点 的局部分布情况，其基本思想是：将微分流形、谱图论的知识应用于降维之中， 在高维空间中离得很近的点投影到低维空间中的象也应该离得很近。 假设将n 个点 x ，x ，映射到一维空间r 中，其中x ，er d ，映射后的 坐标是 y l ，y ) ，其中y ，r 。，d “d 。 获得好的映射的关键是使以下目标函数最小化： ( j ，嘞) 2 ， 公式( 2 - i ) 分析：而，- 之间联系紧密，权重相应也会很大，如果映射到新的空间 后，新坐标y l ，y j 未保持而，- 的紧密关系，则作为一个惩罚系数，会使得 目标函数很大。所以最小化公式( 2 1 ) 保证了原空间分布的最优映射。 以上目标函数为了计算简便，可以写成 昙b 嘞) 2 = 昙位+ 巧一2 舅乃) ；i 1 厶乃2 + i 1 厶趵2 一e y , y ，w q，埘埘 = j 1 以2 岛+ j 1 莩巧一否舅乃 = 露眈一咒乃 = l ，r 助 ( 令巩= ) ， ( 令= d - w ) 其中上常被称为l a p l a c i a n 矩阵。 r 因此，最后目标函数演化成j ，r 缈，问题归结为m i n y r 缈。为了防止所有数 据点映射到同一点，加入限制条件j ，r d l = 0 。该问题中y 的值可以通过求解广 义特征值问题跏= 2 d y 得出，其证明过程可以参见文献幽j 。 将上述映射问题一般化，映射空间扩大到m 维空间，】，= y ，y ：，y 。 ， 其中y 为l m 阵，它的第f 行代表第f 个点的嵌入坐标。则目标函数为 妒一y 国0 2 = 以r 三y ) 嵇 公式( 2 2 ) 第二章流形学习概述 其中j ，伪= b 。o ) ，。( f ) 】。 问题归结为m i t t 仃p r 三y ) ，同样，为了防止映射到肼一1 维空间中，需要设 置限制条件y r d y = i 。以上问题的解也是通过求解广义特征值问题毋= 2 1 ) y 得 出。 l a p l a e i a ne i g e n m a p s 算法如下： 输入参数：d 维空间中的个点 x ，x ) 所构成的高维流形，邻域选择参 数：占或者k ；嵌入维数d ； 输出：d 维空间上的个点 m ，y ) ； 算法描述如下： ( 1 ) 构造邻域图。如果点i 和点，是邻域点则将两点连接，目前有两种方法 来寻找一个点的邻域点。 6 - - 邻域法：占是一个正实数，如果两点间的距离小于占，则认为这两点为邻 域点。这种方法的优点在于它是基于几何观点，并且得到的邻接矩阵是对称的； 缺点是占的大小不容易确定。 k 一近邻法：求出该点与其余点的距离，取前k 个距离最小的点，则这个点就 是k 近邻点。这种方法参数选取简单，所以我们通常采用这种方法来获取邻域点。 ( 2 ) 构造权值矩阵。同样有两种方法构造权值矩阵形。 h e a t - k e r n e l 法：该方法是受到h e a t - k e r n e l 理论的启发而得出的，如果点f 和 点j f 是邻域点，则两点间的权值为： i 多 u = e x p ( - 毕， s i m p l ew e i g h t 法：如果点i 和点，是邻域点则睨设为1 ，否则设为0 。 ( 3 ) 计算d 维嵌入。第二步求得的权值矩阵是一个d x d 维的矩阵，对 该矩阵求特征值并把求得的特征值升序排列，然后求出这些特征值对应的特征向 量，取这些特征向量的前d 个分量作为嵌入低维空间上的映射。 3 等距映射算法 等距映射算法( i s o m e t r i cm a p p i n g ，i s o m a p ) 【2 5 】，由t e n e n b a u m 等人提出，其 基本思想是首先计算流形上的测地线距离，然后应用c m d s 算法，发现嵌入在高 维空间的低维坐标，这样i s o m a p 就通过数据间的测地线距离，保留了数据固有的 几何分布结构。其基本出发点与c m d s 方法一致，二者的差异是在于“距离”的 计算上。c m d s 通常采用两点间的“欧氏距离”，而i s o m a p 贝l j 采用“测地距离”。 i s o m a p 算法【2 6 j 如下： 9 第二章流形学习概述 输入参数：d 维空间中的数据集x ，d n 矩阵；邻域半径占；嵌入维数d ； 输出：d 维嵌入空间l ，； ( 1 ) 构造邻域图：根据输入空间x 中每两个样本点间的欧氏距离来确定流 形m 上点之间的邻域关系，与当前样本点的距离小于固定邻域半径占的所有点都 被认为是样本点的邻域点。这些样本点之间的邻域关系通过一个有权图g 来表 示，其中邻域点之间的权重为点距离d y ( i ，歹) ； ( 2 ) 估计点之间的测地线距离：将流形m 上点之间的测地线距离用图g 上 的最短路径距离作为近似估计。若初始时f 和歹之间有一条边，则 d g ( f ，j ) = d x ( f ，j ) ；否则d g ( 厶j ) = 0 0 。对所有的k = 1 , 2 ，n ，依次更新d g ( f ，j ) 的值：d o ( f ，j ) = m i n d g ( 毛，) ，d g ( f ，五) + d g ( 置，j f ) ，这样得到的矩阵 d a ( f ，j f ) = g ( z ，j f ) ) 表示了图g 中所有点对之间的最短距离； ( 3 ) 构造d 维低维嵌入：将c m d s 算法应用于最短距离矩阵 d a ( f ，j ) = d a ( f ，j ) ，构造d 维欧氏空间嵌入】，这个嵌入空间能够最大限度地 保持流形的固有几何特征。令名。是矩阵f ( d g ) 的第p 个特征值( 特征值已按降序 排列) ，是第p 个特征向量的第害个分量，则d 维嵌入向量y ，的第p 个分量等 于厄。 i s o m a p 算法的总体复杂度近似为o ( n 2 ) 。 i s o m a p 算法有效的两个前提是：高维数据所在的低维流形与欧氏空间的一个 子集是整体等距的；与数据所在的流形等距的欧氏空间的子集是一个凸集。 2 2 3 算法小结 p c a 和c m d s 作为两种典型的线性维数约减算法，有着严格数学推导基础， 在工程和科学计算中有广泛的应用，但是这两种线性降维约减算法主要适用于具 有线性结构的数据集，对于非线性结构的数据集则难以达到理想的降维效果。 u 擅把高维空间中的流形看成局部线性结构，其低维嵌入就是将“流形片” 按照流形之间的相邻关系重新连接起来，因此l l e 屏蔽了全局信息的影响，把全 局计算转换为局部计算；l a p l a c i a ne i g e n m a p s 算法通过在低维空间中保持在高 维空间原本邻近的样本点之间的相互位置关系来求出低维嵌入，一定程度上最优 保持了原空间中数据点的局部分布情况；i s o m a p 算法是一种全局性算法，充分考 虑了所有样本点之间的相互作用信息，在认知上强调整体性，因而对于无噪声数 据的嵌入效果优于其他非线性流形学习算法，但是该算法仅适用于学习内部平坦 的低维流形，不适合学习具有较大的内在曲率的流形【2 6 。u 正、l a p l a c i a n e i g e n m a p s 和i s o m a p 算法，主要适用于非线性结构的数据集。此类算法更符合人 类的认知特点，因此更易于被人们理解和接受。 1 0 第二章流形学习概述 从算法过程上看，大多数维数约减算法都要求显式地设置数据集嵌入的维 数，因此合适地估计数据集的固有维数对于数据集的处理有着重要意义。 2 3 固有维数估计方法 固有维数，i n t r i n s i cd i m e n s i o n ，也被称为“本征维数【2 7 1 ，其概念主要是相 对于高维数据来说。假设某数据集是维数据集，但是它的每一条记录均可由m ( m ) 个变量来表示，那么一般认为该数据集的固有维数为m 维。例如，第 一章中的t u r n i n gc u p s 像数据集，虽然处于4 0 9 6 维空间中，但是它的固有维数是 一维的。目前，固有维数估计方法主要有两种 2 8 - 3 0 ：一种是特征值方法，另一 种是几何方法。 2 3 1 特征值方法 特征值方法，也称为映射方法，该方法主要基于主成分分析理论，即将原始 变量进行线性组合，生成若干综合变量。这些综合变量之间不相关，并且尽可能 多地表示原始变量包含的信息。实践中，通常用方差来表示包含原始信息的多少， 方差越大，包含的信息越多。对这些综合变量的方差排序，并确定一个阈值，大 于该阈值的方差的个数即为所求固有维数。 固有维数的计算步骤是： ( 1 ) 计算数据集所对应协方差矩阵的特征值； ( 2 ) 设定一个阈值； ( 3 ) 将特征值与阈值进行比较，大于阈值的特征值的个数即为该数据集的 固有维数。 该类维数估计方法计算简单，但是也有如下缺点：首先，需要确定合适的阂 值，如果阈值选取不合适，会直接影响到维数估计的准确性；其次，这类估计方 法适用于线性结构数据集，对于非线性结构的数据集进行维数估计时，估计的效 果不理想，因为主成分分析方法是从全局看待问题，因此基于它所计算的固有维 数只能代表全局的固有维数，局部的信息没有考虑进去；最后，也是一个非常重 要的前提是数据集的协方差矩阵必须是满秩或者非奇异，可以求特征值时，才能 使用这种维数估计方法。 针对于数据集非线性结构的情况，b r u k e 和s o r m m e r 提出了一个解决方法【3 0 】： 首先对数据集进行聚类，然后为各个聚类的中心数据点构建一个最优拓扑保持映 射，然后在各个聚类上实施维数估计计算。 这种改进的维数估计方法能够很好地在非线性数据集上计算，但是仍然需要 第二章流形学习概述 设置阈值，并且还需要设置聚类的数目。 2 3 2 几何方法 几何方法基于数据集的几何结构，从数据集的几何结构中获得维数信息。该 类方法主要计算的是分形维数，不同的维数定义指导着不同的计算方法。 h a u s d o f f f 维数是分形维数理论中最基本的定义，其概念最早是德国波恩大学 数学家f d i xh a u s d o r t f 提出，之后由a b r a ms a m o i l o v i t e hb e s i c o v i t c h 对其进行了 扩展，因此也被称为h a u s d o r f f - b e s i e o v i t e h 维数。 其数学定义【3 l 】如下： 定义2 _ 4 ：若嚏甩维欧氏空间f 的任意非空子集，u 的直径定义为 l u i = s 1 l p l x y i ：x ，y e u 即u 内任意两点距离的最大值( 式中的s u p 是上确界的缩写) 。 若p 0 为可数( 或有限) 个直径不超过万的集构成的覆盖f 的集类，即且 fc uu , ，对每个i ，o o ， 定义。 日；( f ) = i n f i v ，i ： 玑) 为，的一个万一覆盖 i f f i l 其中万是一个定值。于是考虑不超过万的f 的覆盖，并试图使这些直径的s 次幂 的和达到最小。 当万一o 时，下确界日；趋于一个极限记为： h s ( f ) = 1 i m 日；( ，) b - - h o 对风中任何子集f ，这个极限都存在。z 被称为，的5 维h a u s d o r f f 钡l j 度。 定义2 6 ：对任意一个集合f ，当s 从0 逐渐增大时，存在s 的临界值，使得胁 由。o 突然变为0 ( 见图2 1 ) ，则称这个临界值为集合f 的h a u s d o r f f 维数，常用 d h 或d h ( f ) 表示，即： 1 2 第二章流形学习概述 r s i ) l l 当s - - - d h 时，有o 层 ( 8 - - i x ，一j 力 关联维数便于从实验中直接测定，因此应用很广。在数据分布均匀的情况下， 能够很好地估计数据集的维数，但是在数据分布不均匀，或者噪声点较多的情况 下，d 晰会大大低于数据集的固有维数。因此，关联维数受数据分布和噪声点的 影响很大。 第二章流形学习概述 信息维数将概率引入到分形维数中。 定义2 8 ：信息维数( i n f o r m a t i o nd i m e n s i o n ) 1 3 3 】 = 觋善掣 其中只( 占) 表示各个子集被访问的概率，毋( g ) = 1 ，如果该子集包含元素多， 面 那么它相应的只p ) 就会大，因此信息维数也会受到数据分布状况的影响。在等 概率的情况下，信息维数等于h a u s d o r f f 维数。不过，由于概率的引入，使得计 算变得极为复杂，因此信息维数在实际中应用并不多。 容量维数是利用相同大小的小球或者立方体覆盖集合而定义的维数，最早由 数学家科尔莫可诺夫提出，其定义与h a u s d o r f f 维数相似，以包覆作为基础。 假设边长为1 的正方形，当边长变为原来的1 2 时，原正方形中包含4 个小 正方形，且4 = 2 2 ；边长为l 的正方体，当边长变为原来的1 2 时，原正方体中 包含8 个小正方体，且8 = 2 3 ；从这里可以发现，表达式4 = 2 2 和8 = 2 3 中2 上面的 幂，恰好是相应的正方形和正方体的维数。如果上面的关系写成通式，则有： n = k d 其中，k 为边长缩小的倍数，为边长缩小k 倍后新形体的个数，则d 便是形体 所具有的维数，容量维数的定义由此可得。 定义2 - 9 ：容量维数( c a p a c i t yd i m e n s i o n ) 【3 3 】 假设集合s ，若用直径为8 的标准体去覆盖s ，所需标准体的最小数量为n ( ) ， 则s 的容量维数定义如下： = 二脚- 4 u 訾f 一。 其中覆盖几何对象s 的标准体，视几何对象的不同可选择小球、单位立方体或小 区间等。 和关联维数、信息维数相比，容量维数不依赖数据在流形上的分布，能够很 好地避免受数据分布和噪声的影响，但是在实际中，容量维数用得并不多，主要 是因为它的计算开销太大。针对于此，本文将在下章介绍一种基于容量维数的包 维数。 1 4 第三章包维数算法改进及实现 3 1 理论依据 第三章包维数算法改进及实现 b a l t z sk 6 9 1 ) 白t 克服传统的容量维数计算开销大的缺点，通过使用包数重新 定义了容量维数，定义如下： - - 1 蜘警s _ u “7 6 0 其中m ( 0 为包数。 对于有限的数据样本，s 的零极限是不能实现的，因此，可以通过计算l o g 埘甜 得出与l o g 的关系曲线，然后利用曲线的线性部分的斜率来进行维数估计。定 义 2 8 1 如下： ( 诵) - 笔掣 3 2 算法描述及改进 任何一个智能过程，在计算机科学领域中都必须转化为机器可执行的算法。 因此，研究机器学习的算法是必不可少的。一个机器学习的问题通常可以归结为 搜索问题，而机器学习算法的本质就是寻找一个最优解，也就是说是一种优化算 法。从图论的角度来看，数据集对应一个邻接图，数据集中的元素对应于图中的 顶点，如果两个顶点互为邻点，则中间存在一条边。对应于包数的计算可以归结 为从数据集所对应的邻接图中寻找最大独立集的问题，独立集中的任意两点之间 都不存在边。这是一个经典的n p h a r d l 商 题f 3 4 】，目前还不存在有效算法对其进行 精确求解，因此只能寻求包数m ( e ) 的一个近似值。b a l 缸sk 6 9 l 提出的p d e ( p a c k i n gd i m e n s i o ne s t i m a t i o n ) 算法使用贪婪算法来计算包数m ( ) 的近似值。 算法流程如下： 输入参数：数据集s ，l ，2 ； 输出：估计的容量维数d 嗽k ； ( 1 ) 随机排列数据点在集合s 中的位置； 第三章包维数算法改进及实现 f o rk = lt 02d 0 集合c 置空； f o r i - 1t o n d o f o r j = lt ol c ld o i f d ( s i 】，c d ) s i 【 t h e n j - - n + 1 ；) f o r j i f j s a m p l e ：s e m p k 锄u m o f p a i a ：i n t o 奄呐n 刖i ：d o u b l , , 1 如l m o ：d o u b l e 一 嘎帅9 a n ：d o u b l d 孰a r j a h c e ：d o u b l e ， 岛枷mb 1 5 im h i a b g r a m ：d o uh e d 磷a n c o 日0 ，a m p u le d i s t a n c e 邮 o r d 蚰如n 嘲d 图3 一il c a m i a g m e a s t a i n g d i m e n s i o n 包类图 1 e x p e r i m e n t 类 ( 1 ) e x p e r i m e n t 类提供了对外的访问接1 2 1m a i n 方法，用户可以通过一个测 试类对e x p e r i m e n t m a i n ( s t r i n g a r g s ) 进行调用，完成用户所提供数据文件的 维数估计； ( 2 ) r e a d s a m p l e 方法用来实现数据文件的载入和封装，本代码框架要求数 据文件的格式为：每一个数据点为一行，点坐标以空格相隔开。当调用 r e a d s a m p l e 方法时，程序将根据用户提供的数据文件路径进行访问，并将读入 第三章包维数算法改进及实现 的数据进行对象化封装； ( 3 ) g c t s a m p l e 方法用来返回数据文件的封装对象，如前面所述，r e a d s a m p l e 方法完成数据的载入，但最终需要通过g e t s a m p l e 方法来进行返回； ( 4 ) o n e e x p e r i m e n t 负责处理流程的组装，包括对数据文件的对象化载入、 数据点欧氏距离的计算以及维数估计等方法的调用和组装； ( 5 ) h a n d l e s a r g u m e n t 方法处理用户调用m a i n 函数时提供的参数，本次实 验中需要用户提供的参数主要有三个，分别是：数据文件路径、b u c k e t 数和输出 目录，用户可以选择这三个参数中的任意几个进行输入调用，h a a d l e s a r g u m e n t 将对用户输入的参数进行预处理，其中b u c k e t 数可以用来控制算法的比较距离。 2 d i s t a n c e s 类 用来完成点集的欧氏距离的计算和相关的辅助功能。 ( 1 ) 在构造函数d i s t a n c e s 中，通过输入参数即点集对象，完成了对点集中 任意两点的欧氏距离的计算和封装，同时根据构造函数调用的不同，我们还会选 择性的对距离完成排序等操作； ( 2 ) c o m p u t e d i s t a n c e s 方法用来完成欧氏距离的计算； ( 3 ) o r d e r d i s t a n c e s 方法用来完成对距离的排序，通过调用m y m a t h 类中的 索引建立方法进行实现。 3 p a c k i n g d i m e n s i o n s i m p l e 类 用来实现包维数估计的相关逻辑，我们在此类中完成了对p d e 和i p d e 算法 核心的实现，其中包括四个方法： ( 1 ) p a c k i n g d i m e n s i o n s i m p l e 方法是构造方法，用来初始化程序运行时所需 变量，包括：从输入参数中得到的数据集对象、距离对象和其他在类调用过程中 用到的辅助属性； ( 2 ) p a c k i n g n u m b e r e s t i m a t e 方法用来计算数据集的包数，根据指定的距离 变量来进行点集距离的处理，最终完成基于给定参考距离的数据集包数计算； ( 3 ) p a c k i n g n u m b e r e s t i m a t e s 方法用来计算数据集的包数的l o g 值，对应于 定义中的l o g m ( ) ； ( 4 ) d i m e n s i o n e s t i m a t e w i t h c o n f i d e n c e 方法实现了按照包维数定义计算出结 果并将其输出到屏幕，同时为了方便用户查看和跟踪运行结果，该方法会将结果 保存在指定的文件中。 i p d e 算法的改进部分主要体现在p a c k i n g n u m b e r e s t i m a t e 方法中。 包l i n e a r a l g e b r a 顾名思义，是一些代数的对象封装，其类图如图3 - 2 所示。 1 9 第三章包维数算法改进及实现 o f v 8 k t o r iv e k t o r o b j e c t l 一目 s a m p l e 易p o 仉t s ：v e c t o r s a m p i 印 ，l n i t i a ii ze s a m pl e p a r a m e t e r s 0 4 b c i o n e 0 s ha 0o w c i o n e 0 4 b g e tp o i n t a t0 4 l f i n d p o i n t0 4 - g e t s 注e o a d d 0 鲥ld p o i n t 0 4 - l n s er tp oi n t 铷 4 b d ei e te p o i n t a t0 4 l d el e te p o i n t s 0 4 1 , u pd a t e p oi n t a t 0 s a m o i e l o a d a b i e 4 - l o a d 0 4 - a d d p o i n t 0 1 s a m p l e 类 该类实现了对数据集的封装以及对数据集进行操作的方法集合，s a m p l e 类使 用i a v a u t i l v e c t o r 来实现对数据集的维护，每一个数据点就是v e c t o r 中的一个元 素，同时类中包含了一些针对于数据集的专有方法，下面将对方法进行简要介绍： ( 1 ) i n i t i a l i z e s a m p l e p a r a m e t e r s 方法通过输入参数实现点集对象的初始化； ( 2 ) c l o n e 方法用来实现s a m p l e 对象的深克隆； ( 3 ) s h a l l o w c l o n e 方法为s a m p l e 对象的浅克隆方法； ( 4 ) g e t p o i n t a t 方法通过输入索引值得到点集对象中对应于索引值的数据点 对象； ( 5 ) f i n d p o i n t 方法通过输入的数据点对象返回其在点集对象中的索引值； ( 6 ) g e t s i z e 方法用来返回数据点的数量； 第三章包维数算法改进及实现 ( 7 ) a d d 方法将一个输入的数据点集对象添加到当前点集对象中，相当于 批处理操作；a d d p o i n t 方法是每次调用只添加一个数据点对象到当前的点集对象 中； ( 8 ) i n s e r t p o i n t a t 方法将输入的数据点插入到指定的索引位置； ( 9 ) d e l e t e p o i n t a t 方法将指定索引位置的数据点进行删除，而d e l e t e p o i n t s 则是通过一个标志数组将标志为t r u e 的对应的数据点进行删除； ( 1 0 ) u p d a t e p o i n t a t 方法是更新指定索引位置的数据点的属性。 2 s a m p l c l o a d a b l e 类 s a m p l e l o a d a b l e 类继承于s a m p l e ，它实现了从文件中载入数据集的方法l o a d 方法，同时重载了a d d p o 血方法以实现从输入流中读取数据，并将其组装为一 个数据点对象添加到数据点集中。 3 s a m p l e d d 类 s a m p l e d d 类继承于s a m p l e l o a d a b l e 类，它实现了一个默认克隆方法 d e f a u l t c l o n e ，用来初始化一个s a m p l e d d 对象，并且重载方法a d d p o i n t 使得类 可以从文本中读取一个数据点并进行添加。 4 v e k t o r 接口 v e k t o r 具体实现由v e k t o r o b j e e t 和v e k t o r d d 完成，它主要完成数据点对象 的定义和数据点相关操作的方法集合的定义。c l o n e 方法用来完成对v e k t o r 的克 隆；u p d a t e 方法用来完成数据点v e k t o r 属性的更新；d i m e n s i o n 方法用来返回数 据点对象的维数：g c t c o o r d