（应用数学专业论文）基于深度函数的曲线拟合方法研究.pdf

中文摘要 为了将一维数据的排序问题推广n - 维数据，引入了深度函数的概念，它已 经很成功地运用于鲁棒估计、测试理论和图像显示。深度曲线就是所有具有相同 深度值的点形成区域的边界，所有的深度曲线形成了一个嵌套式的多边形集合， 而最深的深度曲线的中心被称为中值。由于目前现有的计算深度曲线和中值的算 法运行都很缓慢，这就限制了深度曲线的应用。本文利用直线排列中的拓扑扫描 的方法提出了一种新的算法，可以在时间复杂性和空间复杂性为0 f ”2 ) 的情况 下，计算出所有的二维深度曲线，一旦计算出深度曲线，任意点的深度值就可以 在时间复杂性为0 ( 1 0 9 2 刀) 的情况下计算出来，这就很好地解决了深度曲线计算 速度慢的问题，使深度函数在实际应用中更加方便。本文给出了构造半空间深度 曲线的算例，验证了该算法的有效性和正确性。文章最后还举例说明了深度曲线 的应用。 关键词：深度函数，t u k e y 深度，深度曲线，对偶变换 a b s t r a c t t h ec o n c 印to fl o c a t i o nd e p t hw a si n t r o d u c e da saw a yt oe x t e n dt h et m i v a r i a t e n o t i o no fr a n k i n gt oab i v a r i a t ec o n f i g u r a t i o no fd a t ap o i n t s i th a su s e ds u c c e s s f u l l y f o rr o b u s te s t i m a t i o n ，h y p o t h e s i st e s t i n g ，a n dg r a p h i c a ld i s p l a yt h e d e p t hc o n t o t i i i s t h eb o u n d a r i e so f r e g i o n so fa l lp o i n t sw i t he q u a ld e p t h ，a l lc o n t o u r sf o r mac o l l e c t i o n o fn e s t e dp o l y g o n s ，a n dt h ec e n t e ro ft h ed e e p e s tc o n t o u ri sc a l l e dt h et u k e ym e d i a n t h eo n l ya v a i l a b l ei m p l e m e n t e da l g o r i t h m sf o r 也ed e p t hc o n t o u r sa n dt h et u k e y m e d i a na r es l o w , w h i c hl i m i t st h e i ru s e f u l n e s s i nt h i sp a p e rw ed e s c r i b ea l la l g o r i t h m w h i c hc o m p u t e sa l lb i v a r i a t ed e p t hc o n t o u r si nd ( 刀2 ) t i m ea n ds p a c e ，u s i n g t o p o l o g i c a ls w e e po ft h ed u a la r r a n g e m e n to fl i n e s ，o n c et h e s ec o n t o u r sa r ek n o w n ， t h el o c a t i o nd e p t ho fa n yp o i n tc a l lb ec o m p u t e di n o ( 1 0 9 2 疗l t i m e s ot h i sa l g o r i t h m s o l v e dt h ep r o b l e mo fc o m p u t i n gs p e e d , a n dm a k et h ed e p t hf u n c t i o nu s e dm o r e c o n v e n i e n t l yi np r a c t i c e s o m en u m e r i c a le x a m p l e sa r eg i v e nh e r et os h o wt h e a l g o r i t h m sv a l i d i t ya n de f f e c t i v i 够a tt h ee n do ft h i sp a p e r , w ei l l u s t r a t et h e a p p l i c a t i o no fd e p t hc o n t o u r s k e y w o r d s ：d e p t hf u n c t i o n s ，t u k e yd e p t h ，d e p t hc o n t o u r s ，d u a l i t yt r a n s f o r m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤壅盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：杪牟建f 目 签字日期： 易7 年厂月g 日 学位论文版权使用授权书 本学位论文作者完全了解基盗盘堂有关保留、使用学位论文的规定。 特授权墨鎏盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：谓建阂 签字日期：易叻一) 年厂月矽日 聊躲汐亍钐云 签字日期：z 口口7 年石月矿日 第一章绪论 第一章绪论 本章首先对深度函数产生的背景做一下简单的分析，进而概述深度函数的应 用，并扼要介绍了本文的主要工作。 1 1 背景分析 深度函数的概念与统计学中的数据分析有着密切的联系，它最早来源于一组 一维数据的次序统计量的推广。在一维的情况下，如果有一组数据 s = 五，k ) ，其中置r ，i = l ，2 ， ，则可以很容易地计算出这组数据s 的 中位数，首先我们将s 中的元素重新排序，排序后为j = 。】，。矗，其中 簟。i 。】，若记s 的中位数为m ，则 m = 耳川 l 丁j 1f ， 、 虱铂+ 1 爿j n = 2 m + 1 n 2 2 m m z ， 长期以来人们一直在高维数据处理和分析中寻找“次序统计量”，却没有得 到很满意的结果，由于缺少自然而有效的高维数据排序方法，因而像一维问题中 “中位数的概念很难推广到高维问题中，深度函数则提供了高维数据排序的一 种工具，其主要思想是提供一种从高维数据中心( 最深点) 向外的排序方法，深 度函数的定义就是对于给定的集合s = 五，五，以 墨r d ，对于r 4 中任意一点 工，根据z 靠近s 中心的程度来赋予一个数值，这个数值就叫做该点的深度，那 么我们就可以根据深度值来对高维数据进行排序。这样在有了高维数据的排序方 法之后，就可以获得数据的一些内在性质：最大值和最小值，相关性，变化范围， 以及集合外部的点对数据的影响等等。人们一直对排序问题很感兴趣，在很多情 况下极值能够反映出最好的是什么，最坏的是什么，像在气象学中要用到最低温 度和最高的洪水级别；在工业可靠性分析中要知道部件的最短寿命；以及在奥林 匹克运动中的最高与最低跳水纪录。另外，数据排序之后可以清晰地反映出数据 的变化范围，最大的深度值可以作为对一组数据集合的中心的一个粗略估计，正 第一章绪论 因为如此，深度函数已经在高维数据分析，统计判决等方面带有了一定的应用， 并在工业、工程、生物医学等诸多领域也得到很好的应用。 1 2 深度函数及其算法综述 近年来，随着对高维数据的排序方法的不断研究，虽然已经获得了不少的方 法，但是这些方法并不能令人们完全满意，因为人们只能从这些排序方法中获得 部分有用的信息，而基于深度函数的高维数据的排序方法具有很好的统计学的性 质，这就使得深度函数得到了一定发展。 t u k e y t 3 】首次提出了关于高维空间中点集的半空问深度函数，半空间深度函 数也叫t u l ( e y 深度函数，它是根据划分半空间的方法来确定每一个点的深度值， 也就是说该点的深度值为所有边界线经过该点的闭的半空间中含样本点的个数 的最小值。半空间深度函数有者很好的统计学性质，是目前研究最深入的一种深 度函数。 l i u t l 0 】提出了单纯形深度函数，它是基于d 维空间中单纯形来度量每一个点 的深度值，我们知道一维单纯形为线段，二维单纯形为三角形，三维单纯形为四 面体，对于d 维空间中的一点用包含该点的所有单纯形个数与所有单纯形的个数 的比值来表示该点的深度值。对于二维空间来说，有疗个点组成的集合就可以形 ， 、 成i 1 个单纯形，而对于高维空间来说这个值就会更大，所以单纯形深度函数的 l 3 计算是相当麻烦的，目前对其研究主要是集中在二维实数空间中，对于高维空间 来说还有很多的工作需要做。 r o u s s e e u w 和h u b e r t 5 】提出了回归深度函数，它来源于统计学中的鲁棒回归 分析的研究，因此在二维实数空问中回归深度函数就是反映刀个点和一条直线的 关系的，它对每一条直线赋一个回归深度值，回归深度值最大的直线可以作为统 计学中的一个回归估计，回归深度同样适合高维空间，这就是用来反映n 个点和 一个超平面的关系，同样对应着高维的回归估计。通过对偶变换，r o u s s e e u w 和 h u b e r t t 6 】又提出了超平面深度函数，对于二维实数空间来说，就是将回归深度里 的点和直线分别对偶成直线和点，这就使超平面深度函数与半空问深度函数联系 起来了，也可以说超平面深度函数是半空间深度函数的一个推广。 z u o 1 6 】提出了投影深度函数，投影深度函数和半空间深度函数一样有着很好 的统计学性质，这使得投影深度函数也有着十分广泛的应用，在这方面，z u o 和 第章绪论 s e t t l i n g 1 7 】有着比较深入的研究。 虽然目前已经有多种深度函数，但是能运用到实际中的却不是很多，这里面 一个重要的原因就是缺少准确而且有效的算法。目前，仅有的一些深度曲线的算 法还主要集中在二维和三维中，而对于高维空问的算法更是十分缺乏的。其中研 究比较深入的就是半空间深度函数，对于二维实数空间来说，目前主要的半空间 深度曲线的算法有： 1 9 8 7 年，c o l e ，s h a r i r 并t y a p 1 8 1 ，最早提出了求t u k e y 深度的最大值算法的复杂 度为o ( n l 0 9 5r t l 。 1 9 9 1 年，m a t o u e k 【2 1 】利用二级参数查找的方法来确定最大t u k e y 深度是不是 大于等于给定的值k ，其复杂度为o ( nl 0 9 4 刀) ，这样m a t o u e k 的算法就可以根据 所有深度值大于等于k 的点构成的区域，得到整个深度值为k 的等深度值曲线， 然后再利用二分查找的方法就可以找到最大t u k e y 深度值，其复杂度为 o ( n l 0 9 5 聍1 。 一1 9 9 6 年，r u t s 和r o u s s e e u w t l 3 】提出了i s o d e p t h 算法，计算第k 条t u k e y 深度 曲线的复杂度为d ( 刀2l o g n ) ，计算出所有的t u k e y 深度曲线的复杂度为 o ( n 3 l o g 咒1 。 1 9 9 8 年，r o u s s e e u w 和r u t s 1 2 】提出t h a l f m e d 算法，该算法计算最大t u k e y 深度值和所有的t u k e y 深度曲线的复杂度为o ( 甩2l 0 9 2 甩) 。 2 0 0 2 年，k m i l l e r 和p r o u s s e e u w 1 4 】提出了基于拓扑扫描的算法，该算法可 以在时间复杂性和空间复杂性都在o ( n 2 1 的情况下，计算出所有的二维t u k e y 深 度曲线。 在三维实数空间中，c o l e t l 5 】提出了求t u k e y 深度的最大值算法的复杂度为 o ( n 2l 0 9 7 以) ，随后c o l e 叉修正了该算法，使其复杂度为o ( n 2l 0 9 4 刀) 。 目前，关于单纯形深度函数的算法，仅有求最大单纯形深度值的算法，还没 有找到计算单纯形深度曲线的算法，在r 2 中计算任意一点z 关于集合s 的单纯 形深度的复杂度为d ( 力l o g n ) ，计算所有样本点的单纯形深度的复杂度为 d f ”：1 【6 3 1 ，而计算最大单纯形深度的复杂度却需要d ( 行4 ) 8 1 。 至于回归深度函数，最实用的就是计算最大回归深度值，在二维实数空间中 p j r o u s s e e u w 和m h u b e r t t 5 j 提出了求最大回归深度值的算法，其复杂度为 o ( n 3 ) 。 而超平面深度是由回归深度经过对偶变换得到的，由对偶变换的性质可知， 超平面深度和回归深度是一致的，二者知道其中一个就可以得到另一个。 第一章绪论 1 3 本文主要工作 本文的主要工作是提出一种基于深度函数的平面二维数据的深度曲线的算 法，由于高维数据分析的需要，我们提出了深度函数的概念，有了深度函数就为 我们绘制深度曲线带来了极大的方便，但是由于缺少有效的计算工具，使得深度 曲线的计算遇到了很大的麻烦，目前对深度曲线的研究主要是集中在二维空间 中，所以本文利用了计算几何中凸包的增量算法、直线排列中的拓扑扫描算法、 以及对偶变换的方法，很好地解决了一种二维深度曲线的计算问题，为深度曲线 在实际中的应用带来了极大的方便。 本文通过不同样本点集的算例验证了上述算法的有效性和正确性。算例说明 了本文的算法不仅对小规模的样本点集适合，对于大规模的样本点集同样是适合 的。文章最后，通过实例说明了深度曲线的一个具体应用，从中可以看出深度函 数在应用领域有着十分广阔的前景。 第二章深度函数的基本理论 2 1 算法的复杂性 第二章深度函数的基本理论 算法的复杂性包括算法的时间复杂性和算法的空问复杂性。为了说明复杂性 的概念，先介绍问题规模的概念。 定义2 1 用一个与问题相关的整数量来估计问题计算量的大小，该整数量表 示输入数据量的尺度，称为问题的规模。 例如，行列式的规模可以用其阶数刀来表示，图问题的规模可以用其边数或 顶点数来表示，等等。 定义2 2 利用某算法处理一个问题规模为门的输入所需要的时间，称为该算 法的时间复杂性。 显然，它是以的函数，记为丁( 疗) 。 类似地可以定义算法的空间复杂性s ( 栉) 。下面主要讨论算法的时间复杂性。 如果对某一正常数c ，一个算法在时间c n 2 内能处理规模为刀的输入，则称此 算法的时间复杂性为0 ( 玎2 ) ，读作“”2 阶。 定义2 3 一般地，算法的时间复杂性有如下定义： ( i ) 如果存在正常数c 和绝，使得当刀耽时有丁( 栉) 矿( 聍) ，则称厂( 玎) 是 丁( ，z ) 的一个上界，记作丁( 胛) = d ( 厂( 刀) ) 。 ( i i ) 如果存在正常数c ，使得对无穷多个疗，关系式丁( 疗) ( ，? ) 成立，则称 厂( 刀) 是丁( 胛) 的一个下界，记作r ( 玎) = q ( 厂( ，z ) ) 。 ( i i i ) 如果丁( 力) = d ( 厂( 刀) ) 和丁( ”) = q ( ( 聍) ) 同时成立，则称r ( 以) 和厂( 玎) 是 同阶的，记作r ( 刀) = 秒( 厂( 行) ) 。 2 2 凸包及其算法 凸包是计算几何中最普遍、最基本的一种结构，不仅它自身有许多特性，而 且它还是构造其他几何形体的有效工具。在应用中，许多实际问题可以归结为凸 包问题。本节主要介绍凸包的基本概念，及计算二维凸包的算法。 第二章深度函数的基本理论 2 2 i 凸包的基本概念 设s 是平面( e 2 ) 中的点集，用c h ( s ) 表示点集s 的凸包，b c h ( s ) 表示s 的凸包边界。 定义2 4 设s 是平面上的非空点集，p l , p ：是s 中任意两点，如果v te o ，1 ， 点 p = t p l + ( 1 一f ) p 2 s ， 则称s 是凸集。这就是说，如果s 中任意两点所连线段全部位于s 之中，那么s 是凸的。 如果给定e 2 中k 个不同的点p l ，p ：，p k ，则点集 r 七、 p = ip ：p = t l p t + t 2 p 2 + t k p t ，t i = 1 ；f f o ，i = l ，2 ，k l i = l j 是由p l ，1 7 2 ，p t 生成的凸集，且p 是p 。，p 2 ，p 。的一个凸组合。因此，一条线段 是由其端点的凸组合组成，一个三角形则是由它的三个角( 点) 的所有凸组合组 成，而三维中的四面体是由它的四个角( 点) 的所有凸组合组成。 点集s 的凸包就是- s 中的若干个点的所有凸组合的集合。对于d 维中的点集 s ，c h ( s 1 是s 的d + l ( 或者更少) 个点的所有凸组合的集合，因此二维点集 的凸包至多是其3 个点所有凸组合的集合。每个凸组合的集合确定一个三角形， 这样，平面点集s 的凸包是由s 中的点确定的所有三角形的并。 2 2 2 凸包的算法及算例 定义2 5 如图2 1 所示，从点集s 的最左端顶点出发，沿着凸包顺时针行进 到最右端顶点的那段折线，称为点集s 的上凸包。换言之，组成上凸包的，就是 从上方界定凸包的那些边。 类似地，可以定义下凸包。 上凸包下凸包 图2 1 平面点集的上凸包和下凸包 第二章深度函数的基本理论 下面的算法2 1 给出了递增式算法的伪代码，这段代码既计算上凸包，也计 算下凸包，在完成后一项工作时，只需将各点自右向左排列，后继的计算与上凸 包的算法都是相仿的。 算法2 1 a l g o r i t h mc o n v e x h u l l ( p ) i n p u t 平面点集 o u t p u t 由c h ( p ) 的所有的顶点沿顺时针方向组成的一个列表 ( 1 ) 根据x 坐标，对所有点进行排序，得到序列a ，p ：，n ( 2 ) 在三。p 中加入a 和岛( 在届前) ( 3 ) f o ri 6 - - 3t o n ( 4 ) d o 在。p p 。，中加入只 ( 5 ) w h i l e ( 三。，咿中至少还有三个点，而且最末尾的三个点所构成的不 是一个右拐) ( 6 ) d o 将倒数第二个项点从三。，矽中删除 ( 7 ) 在三，d 。中加入见和p 川( p 。在前) ( 8 ) f o rf 卜刀一2d o w n t o1 ( 9 ) d o 在l 如。，中加入只 ( 1 0 ) w h i l e ( l f d 。中至少还有三个点，而且最末尾的三个点所构成的不 是一个右拐) ( 1 1 )d o 将倒数第二个顶点从，o w 。中删除 ( 1 2 ) 将第一个和最后一个点从上，d 。仃中删除( 以免在上凸包与下凸包连接之后， 出现重复顶点) ( 1 3 ) 将三如。连接到三唧。，后面( 将由此得到的列表记为l ) ( 14 ) r e t u r n ( l ) 从上面的算法可以看出，对于给定包含胛个点的任意一个平面点集，构造其 上凸包和下凸包的复杂度为o ( 1 0 9 n 1 ，这是因为仅上述算法的第一步对各点按字 典排序的复杂度为o ( 1 0 9 n 1 ，其余各步循环的次数的都是线性的，循环的次数加 起来不会超过玎，所以，从第二步到结束的复杂度不会超过o ( n ) ，整个算法的 复杂度取决于第一步，即o ( 1 0 9 n 1 。 下面给出根据上述递增式算法得到的计算平面点集的上凸包和下凸包的算 例： 第二章深度函数的基本理论 例2 1 如图2 2 所示，图形的上半部分是由2 0 个点组成的平面点集的上凸 包，即上图中虚线部分；图形的下半部分是由2 0 个点组成的平面点集的下凸包， 即下图中虚线部分。 2 3 对偶变换 图2 2 由2 0 个点组成的平面点集的上凸包和下凸包 平面上的任何一点，都拥有两个参数，x 坐标和y 坐标，平面上任何一条( 非 垂直的) 直线，也有两个参数，斜率以及与y 坐标轴的交点，因此，可以通过某 种一一对应的方式，将一组点映射为一组直线，反之亦然。如果做的巧妙的话， 甚至可以将原先点集所具有的某些性质，转换为直线集所具有的某些性质。如图 2 3 所示，原先共线的三个点，将映射为共点的三条直线。有多种不同的映射方 式，都能做到这一点，称为对偶变换( d u a l i t yt r a n s f o r m ) 。 某个对象经过对偶变换后得到的映射，称为该对象的对偶( d u a l ) 。有一种 简单的对偶变换定义如下，任意给定平面上的一个点尸= ( 口，b ) ，p 的对偶，记作 r ( e ) ，定义为直线r ( e ) ：y = 似+ b ；而非垂直直线，：y = c x + d 的对偶r ( 1 ) ，定义 为点r ( 1 ) ：( 一c ，d ) ，从图2 3 中可以看出对偶变换的过程：原平面中的点彳= ( 1 ，2 ) ， 经过对偶变换后成为直线t ( a 1 ：y = 工+ 2 ，而原平面中的直线m ：y = 一2 x + 2 ，经 第二章深度函数的基本理论 过对偶变换后成为点r ( 聊) - - ( 2 ，2 ) 。 啊种- 劈k 叭钐 歹 彩 一 图2 - 3 对偶变换的一个例子 我们说，对偶变换将对象从原平面( p r i m a lp l a n e ) 映射到对偶平面( d u a l p l a n e ) ，原来在原平面中具有的某些性质，在对偶平面中依然成立： 对偶变换丁具有下述基本性质： ( 1 ) t 是其自身的逆，即丁( 丁( 石) ) = 工，其中x 是一个点或是一条直线。 ( 2 ) r 是平面上所有非垂直直线与所有的点之间的一一对应关系。 ( 3 ) 点p 位于直线，上，当且仅当点r ( 1 ) 位于直线r ( e ) 上。 ( 4 ) 直线厶和直线厶交与点p ，当且仅当直线丁( 尸) 通过两点丁( ，1 ) 和丁( 乞) 。 ( 5 ) 如果点p 位于，的上( 下) 方，当且仅当直线r ( e ) 位于点r ( 1 ) 的上( 下) 方。 从图2 3 中可以看出这些性质：在原平面中，点a ，b ，c ，d 都落在直线，上； 而在对偶平面中，直线r ( 彳) ，丁( b ) ，丁( c ) ，r ( d ) 都经过点r ( 1 ) ，在原平面中，点 彳，b ，c ，d 都在直线历上方；而在对偶平面中，直线r ( 4 ) ，丁( b ) ，r ( c ) ，丁( d ) 都在 点r ( m 1 的上方。 2 4 直线的排列 如图2 - 4 所示，设l 为由平面上 条直线组成的集合，由集合l 可以导出平 面的一个子区域划分，这个子区域划分由顶点、边和面组成。其中有些边和面是 无界的。这种子区域划分，通常被称为“由l 导出的排列( a r r a n g e m e n t ) ”，记作 a ( l 1 。如果其中任何三条直线都不共点，而且任何两条直线都不平行，我们称 第二章深度函数的基本理论 之为“简单排列”。 图2 _ 4 直线的排列 所谓一个排列的复杂度，就是其中所有的顶点、边和面的总数，在一个点集 上定义的一个问题，经过对偶变换之后，往往可以转化为另一个关于排列的问题。 之所以这样做，是因为较之点集的结构，直线的排列的结构更加直观易见。例如， 在原平面上经过两点的一条直线，在对偶排列中将会变成一个项点，这样，这一 特性就会变得更加清楚明确。排列的附加结构并不是没有代价的。事实上，构造 一个完整的组合的复杂度是很高的。 定理2 1 设l 为由平面上胛条直线组成的任一集合，而a ( l ) 为由l 导出的 排列，则 ( i ) a ( 上) 中的顶点不超过玎( 刀一1 ) 2 ； ( i i ) a ( 1 中的边不超过栉2 条； 上述命题中的等号成立，当且仅当a ( l 1 是简单的。 证明：a ( l ) 中的每一个点，都必然是l 中某( 至少) 两条直线的交点。因 此，其总数至多为刀f 刀一1 ) 2 。要出现这样多个顶点，当且仅当每一对直线都能 贡献一个交点，而且不同的直线对所能贡献的交点互不相同。也就是说，a ( l ) 是 简单排列。 在任何一条直线上，边的条数要比顶点的个数正好多一，顶点的数目至多为 刀一1 ，故任何一条直线所贡献的边不会超过刀条。所有直线累计起来，边的总数 至多为刀2 。要出现这样多条边，当且仅当直线的排列是简单的。 2 5 小结 本章对深度函数及深度曲线算法的基本理论进行了研究，深度曲线是所有深 第一章深度函数的基本理论 度值相同的点形成的区域的边界，所有的深度曲线形成了一个嵌套式的多边形集 合，而常用的深度曲线一般都是凸的，这就需要用到计算几何中最基本的一种结 构凸包。对偶变换将点与直线( 超平面) 连接了起来，使得处理深度函数中 点的问题可以转化为直线( 超平面) 的问题，为深度函数的研究提供了一个有力 的工具。 第三章深度函数的研究 第三章深度函数的研究 给定集合s = 五，以lsr d ，对于r d 中任意一点z ，根据x 靠近s 中心的 程度赋予该点一个数值，这个数值就叫做该点的深度，深度函数厂是定义在s 上 的一个泛函，即厂：s r ，其中s r 4 。 由于在概率统计中的集合s 往往分为连续和有限样本的两种情况，所以我们 就根据给定集合s 的不同，来定义有限样本集合下的深度函数和连续样本集合下 的深度函数，本文主要是讨论在有限样本集合下的深度函数。 3 1 有限样本的深度函数的定义 设f 为r 4 中的任一个概率分布，c = 五，五鼍) 为，中的拧个随机样本， 对于r d 中任意一点x 关于集合c 的深度d ( x ，e ) 为x 靠近集合e 中心的程度。 常见的深度测量有：半空间深度、单纯形深度、回归深度、厶深度。深度函 数作为一个数据分析工具，有着十分重要的意义。但是对于高维数据集合，还是 缺乏有效的计算工具。因此，目前对深度函数的研究主要还集中在二维空间中。 3 2 深度函数的构造 由于统计学中的需要，我们定义深度函数时要使它满足某种性质，以便于我 们分析数据。 性质3 1 ：仿射不变性：任意一点z 的深度值，应不依赖于坐标系，尤其是 不依赖于坐标系刻度的变化而变化。 性质3 2 ：在中心达到最大。 由于一个分布，只能定义唯一的中心口( 例如关于某种对称的对称点可以作 为一个分布的中心) ，所以深度函数应该在中心达到最大值，也就是说： o ( 0 ；f ) = s u p d ( x ，f ) 【7 】o 工e 一 性质3 3 ：相对最深点的单调。 对某一个分布，当任意点x ，沿着任意一条穿过中心的固定射线远离最深 点汐( 也就是深度函数取得最大值的点) 时，z 的深度值应该单调递减。即： 第三章深度函数的研究 d ( x ；f ) d ( 秒+ 口( x 一秒) ；，) 刀，其中口【o ，1 】。 z u i oa n ds e r f l i n g t 】证明了如果某一深度函数满足这种单调性，连续情况下的 深度曲线将是相连的，另外他们还做出了在一些限制条件下离散样本的深度曲线 也是相连的。 性质3 4 ：在无穷远处趋于零。 任意一点工趋于无穷远处时，其深度值应该趋于零，即当_ 时， d ( x ；f ) 寸0 ，这里的是欧几里得范数，是任意一个分布。 满足这个性质是为了保证每个深度函数都是有界的。 3 3 几种不同的深度函数的例子 3 3 1 半空间深度( h a l f - s p a c ed e p t h ) 定义3 1 给定集合s = x i 9 o ，以 r d ，对于r d 中任意一点z 关于集合s 的 半空间深度( 也叫t u k e y 深度) 为所有边界线经过x 的闭的半空问中含s 中的点 的个数的最小值。 若记某一点x 关于集合s 的半空间深度为h d ( s ，x ) ，则肋( s ，x ) 2 卿h n s l ， 其中h 为经过x 的某一个半空间，i h n s i 表示闭的半空间h 所含s 中点的个数。 当d = 2 时，s 为二维点集，图3 - 1 给出了关于平面中1 0 个点组成的集合的 半平面深度计算，由下图可以看出，点0 的半空间深度为l ，这是因为边界线过 点9 的所有半平面中含样本点数最少的为1 ，即h d ( s ，9 1 - 1 ，由定义, - i p g 看出这 里的点臼属于样本集合，也可以不属于样本集合，也就说半空间深度函数可以求 出空间中任一点的半空间深度值，这也是半空间深度函数优越于其他深度函数的 一个地方。 第三章深度函数的研究 图3 1 点秒的半空间深度为1 由半空间深度函数的定义可知其取值范围为l r i d ( s ，x ) 【- 兰j ，其中l 詈j 表示小于等于兰的最小正整数。 z 半空问深度函数是1 9 7 4 年由呦【4 】引入的，它满足3 2 节所提到的所有性 质，在r 2 中，如果s 中的点，没有三点共线的情况，计算r 2 中的每一个点的半 空间深度需要时间复杂性为o ( n l o g n l ，关于集合s 的最大深度值，也n t t t u k e y 中值：最多可以达到l 詈l 。 3 3 2 单纯形深度( s i m p l i c i a ld e p t h ) 定义3 2 ，如果f 维的仿射空间不超过计1 个点，对任意的i 都成立，称一 个有限点集是仿射无关的。一个缸单纯形是斛1 个仿射无关点集的凸包，记为 盯= c o n v s 。仃的维数为d i m o = k 。在r j 中，仿射无关的最大点的数目为丹l ， 且有维数为1 ，, - - - , d 的单纯形。( 1 ) 单纯形为空集。 我们知道一维单纯形为线段，二维单纯形为三角形，三维单纯形为四面体。 定义3 3 给定集合s = 五9 o,o 9 以 r d ，对于r d 中的任意一点工关于集合 s 的单纯形深度( s d ) 为点x 被s 中的点形成的d 维单纯形所包含的概率，即 s d ( s ，x ) = b ( 工剐五局+ ，】) ， ，、一1 2 【d ：1j 小剐五】) v x r d 其中s 【五，局+ i 】表示由s 中的点墨，髟+ 。所形成的d 维单纯形，j 为一个计 第三章深度函数的研究 数函数，即若a 发生，则i ( a ) = 1 ；否则，( a ) = 0 。 单纯形深度是1 9 9 0 年被l i u 1 0 】作为一种深度函数而引入的，它仅满足性质 l ：仿射不变性，和性质4 ：在无穷远处趋于零，在某些离散样本的情况下不一 定满足性质2 ：在中心达到最大和性质3 ：相对最深点的单调性。最近，b u i t l l 9 】 对上面单纯形深度的定义进行了修改，修改后的定义对有些特殊的情况很适合。 定义3 4 给定集合s = 五9o 9 以 r d ，对于r d 中任意一点z 关于集合s 的单纯形深度( s d ) 为 ( 跏) = 圭( d ：1 ) ( 小s 阻，胪( x i n t ( s 【和一扎。】) ) ) 简记为( s ，x ) = 夕( s ，石) + 去仃( s ，x ) ，其中p ( s ，z ) 表示x 在其内部的单纯 形个数，仃( j s r ，x ) 表示x 在其边界的单纯形个数。 在r d 中，单纯形深度的的变化范围为o d ：l 】+ 。( ) 口o 】之问。在r 2 中计算任意一点x 关于集合s 的单纯形深度的复杂度为o ( n l o g n ) ，计算所有样 本点的单纯形深度的复杂度为d ( ”2 1 【9 1 ，而计算最大单纯形深度的复杂度却需要 o ( n 4 ) 隅】。 3 3 3 回归深度( r e g r e s s i o nd e p t h ) 通过统计学中鲁棒回归的研究，1 9 9 9 年r o u s s e e u w 和h u b e r t 提出了计算回 归深度的问题，回归深度是处理r d 中刀个点和超平面的关系，为了介绍回归深 度的概念，我们主要讨论d = 2 的情况，也就是平面中点集 乙= ( 葺，咒) ；f = 1 ，2 ，玎 和一条直线y = 儡x + 岛的协调关系， 记( 秒) = = 弗- o , , - g ，0 = ( 岛，岛) 表示一条直线y = o , x + g ， 定义3 5 一条直线0 = ( 鼠，岛) 被称为关于z 。不协调的( n o n f i t ) ，当且仅当存 在一个实数= ，使得对所有的i ，满足巧( 口) 0 = 1 而 v ，或者是 ( 口) v ，其中1 为计数函数，即若a 发生，( 彳) = 1 ；否则，( a ) = 0 。 定义3 6 给定集合s = 五，以 r 2 ，对于r 2 中任意一条直线矽关于集 合s 的回归深度( i ) 为使0 成为一个不协调的( n o n f i t ) 所需移去s 中最少的 点数。 图3 2 关于8 个点组成的集合的回归深度的计算，通过计算可得：直线，的 回归深度为0 ，直线m 的回归深度为4 。 第三章深度函数的研究 一，； 曼，7 ， 一 i ，。；r j “ j i 卫昏 - 图3 - 2 计算回归深度的例子 回归深度可用来衡量任意一超平面与r d 中的点集协调的好坏程度，我们知 道最大回归深度值就对应着超平面与点集协调最好的情况，因此最大回归深度值 被用来描述鲁棒回归估计，所以我们主要计算问题就是计算最大回归深度问题， 在二维中计算最大深回归线需要的时间复杂度为d ( 玎l o g ，1 ) 2 2 1 。 3 3 4 超平面深度( h y p e r p l a n ed e p t h ) 超平面深度是回归深度的对偶问题，也就是说将回归深度中的点和线经过对 偶变换就得到了超平面深度，下面给出超平面深度的定义： 定义3 7 设由刀个超平面组成的集合s = 1 1 2 】，吃 r d ，对于r d 中任意 一点工关于集合s 的超平面深度为万( 工) = 谚( 工) = ，m 山i n ( 、，- ( z ，z ，) ) ，这里的，( 石，z ，) 表 示s 中所有与射线 x + t u ，t 0 l 相交的超平面的个数，甜为r d 中任意一个方向。 可见，超平面深度是处理以个超平面与一个点的关系。当d = 2 时，也就是 在二维空间中，超平面深度就是处理刀条直线与一个点的关系，正好是回归深度 的对偶问题。同时可以看出，超平面深度与半空间深度的在一定程度上是一致 的，例如当d = 2 时，假设半空间深度是基于玎个点组成的样本点集，连接任意 ，”、， 、 两点组成一条直线，则有l = ：l 条直线，我们就可以作为基于这i = ：i 条直线的超平 l 么， l z 面深度，通过计算可以发现，对平面中任意一点用超平面深度和半空间深度计算 的深度值是一致的。 r o u s s e e u w 阎和h u b e r t 提出了计算d 维空问中的最大超平面深度值的复杂度 为o ( 拧2 扣1l o g 疗1 ，当d - - 2 时，他们先构造了一个计算最大超平面深度值的复杂 度为o ( n 31 的算法，随后他们又构造了一个计算最大超平面深度值的复杂度仅为 o ( n l 0 9 2 刀11 3 5 1 1 拘算法。 第三章深度函数的研究 3 3 5l l 深度( l 1d e p t h ) 定义3 8 给定集合s = 五，以) 取d ，对于r d 中任意一点x 关于集合s 的l - 深度为l 、d ( s ，x ) = 1 一f ( x ) 0 ，其中小) 5 晶， 一 7 7 ，q ( z ) p 工= 上奇仍是分配给每个点置的权，如果所粤的五各不相同，则仍 = l ；1 1 1 i 是欧几里得空间的距离。 l t 深度的取值范围为( 0 , i ) ，由于它计算起来非常简单，而且能够用于任何维 数据，所以它对应用于高维数据是很有吸引力，不过目前这方面的研究还不是很 多。 3 4 小结 本章研究了基于离散集合深度函数，并阐述了深度函数的构造问题，使得在 实际中可以根据需要来构造不同的深度函数。目前常用的深度函数有半空间深 度，单纯形深度，回归深度，厶深度。虽然目前这些深度函数研究的比较彻底些， 但仍然还有许多问题需要解决的，这也在一定程度上限制了深度函数的应用，所 以随着深度函数的研究的不断深入，会为其应用带来广阔的前景。 第四章深度曲线及其算法研究 第四章深度曲线及其算法研究 通过前三章的介绍，对深度函数有了一定的了解，因此本章就是要根据不同 的深度函数的定义来绘制深度曲线。深度曲线提供了一种高维数据可视化的有力 工具，并且可以计算一些数据集合的统计学特征，但是，令人遗憾的是目前深度 曲线的算法仅有二维和三维的，对于高维数据的深度曲线还没有很好的算法，所 以只有加强对其算法的研究，才能使深度曲线得到实际的应用。因此，本章主要 是介绍t u k e y 深度曲线的一种最优化算法，可以在时间复杂性和空间复杂性都在 o n 21 ) 的情况下，计算出所有的二维t u k e y 深度曲线。 4 1 深度曲线的定义 深度曲线，一种嵌套式的曲线，包括深度增长的区域，为数据集合的可视化 和比较提供了有力的工具。由于在统计学领域，对有限样本的深度曲线有着不同 的定义，因此也就可以构造不同的曲线，这里主要介绍两种不同的深度曲线。 4 1 1 基于等级关系的深度曲线 1 9 9 9 年，l 缸瞄】提出了基于等级关系的深度曲线，首先，对于给定集合 s = 五，以) ，令d ( x ) 表示任意一点石关于集合s 的深度， 。】，。】 表示 根据深度值大小排序后的集合，如果我们需要构造包含口刀( 其中0 口s 1 ) 个 样本点的等级深度曲线，就做集合 x 【。】，x f 卜。 1 的凸包，其中口，2 表示大 于等于口，z 的最小正整数。例如，一条包括r o 7 5 n 7 个样本点等级深度曲线为做 点集 x 【。】，”，。1 1 的凸包。 如图4 一l 所示，9 个样本点根据它们半空间深度的大小，标记相应的指数，l 对应深度值最大的点，9 对应深度值最小的点，图中有3 条等级深度曲线，分别 包括了3 个、6 个、9 个样本点。即：点l 、2 、3 组成的凸包，点l 、2 、3 、4 、 5 、6 细成的凸包，点1 、2 、3 、4 、5 、6 、7 、8 、9 组成的凸包。 第四章深度曲线及其算法研究 95 8 图4 _ l 基于9 个点的等级关系深度曲线 4 1 2 基于覆盖关系的深度曲线 基于覆盖关系深度曲线最早是由t u k e y 【2 4 - 2 刀提出来的，并用于描述二维的半 空间深度曲线。 首先，对于给定集合s = 五，以) ，令d ( s ，工) 表示任意一点x 关于集合s 的深度，则第k 条覆盖关系深度曲线为集合 x ：d ( s ，x ) 七，x r d 的边界。 如图4 2 所示，由九个样本点生成的四条基于覆盖关系的深度曲线，即图中 加粗的3 个多边形和最里面的一个点，其中最外边的一个凸多边形表示深度值为 l 的区域的边界。 图4 2 基于9 个点的覆盖关系深度曲线 4 2t u k e y 深度曲线算法研究进展 下面我们主要讨论d = 2 时，t u k e y 深度曲线的算法研究情况。 第四章深度曲线及其算法研究 c o l e ，s h a r i r 和y a p t l 8 】，最早提出了求t u k e y 深度的最大值算法的复杂度为 o ( n l 0 9 5 ”) 。 m a t o u e k 2 1 1 利用二级参数查找的方法来确定最大t u k e y 深度是不是大于等于 给定的值k ，其复杂度为o ( n l 0 9 4 以1 ，这样m a m u 吞, e k 的算法就可以根据所有深度 值大于等于k 的点构成的区域，得到整个深度值为k 的等深度值曲线，然后再利 用二分查找的方法就可以找到最大t u k e y 深度值，其复杂度为o ( n l 0 9 5 聍) 。 r u t s 和r o u s s e e u w 提出了一个n t t l s o d e p t h t ”均算法，计算第k 条深度曲线 的复杂度为d ( 胛2l o g n l ，计算出所有的深度曲线的复杂度为d ( 3l o g n ) 。 r o u s s e e u w 和r u t s 提出了一个1 1 4 h a l f m e d 1 2 】的算法，该算法计算最大深度 值和所有的深度曲线的复杂度为o ( 力21 0 9 2 刀) 。 4 3 求t u k e y 深度曲线的算法 4 3 1 基本原理 定义4 1 平面直线排列l 的上( 下) 包络为l 最上( 下) 的无