（计算机应用技术专业论文）基于对称性检测的数据分析方法研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：i 垦翌日期；理! 型缈尹 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名；碰塑导师签名：叠塾日期：2 竺三盟 复旦大学硕士学位论文 摘要 在当今这样一个信息爆炸的时代，有效的数据分析方法起着至关重要的作 用。数据分析的目标是揭示蕴藏在数据中的规律或者知识，因此它几乎可以应用 在人类生活的各个领域，从传统统计学领域的数据分析，到今天新兴的数据挖掘 领域，数据分析的研究一直都受到广大学者们的关注。目前，学者们根据不同的 原则已经提出了很多有效的数据分析方法，但对称性检测在数据分析中的应用并 没有得到应有的重视。 本文主要探讨如何将对称性检测整合到已有的数据分析方法中以提高其性 能。首先，对于聚类分析，我们提出了一种新的基于镜像对称的层次聚类算法 s y m h c ，思路是利用数据集本身的镜像对称性信息导出合适的相似度度量，以更 好地反映数据集的对称特征( 如果存在) ，从而增强聚类的效果；在利用对称性对 数据样本局部分布的均匀程度进行度量的基础上，我们提出了基于局部分布的离 群点的概念，并相应地给出了两种检测算法l d b o d l d b o d + ；最后，我们尝试通 过数据分布中的骨架点对原来的数据集进行聚类分析，从而提出了一种新的聚类 算法s p b c ，在提取骨架点的过程中，为了确定当前样本集的“形状”，我们又从 局部对称性的角度提出了一种新的边界点检测算法s b b p d 。 本文通过一系列的实验将所提出的算法和原有的各种算法进行了比较，从而 评估了本文提出的算法的有效性，并且尝试将其应用于实际问题的解决，如网络 入侵检测，基因芯片数据的聚类分析。 关键词：对称性、聚类分析、离群点检测、网络入侵检测、骨架点 中图法分类号：t p 3 0 1 1 复旦大学硕士学位论文 a b s t r a c t t o d a y , w ea r el i v i n gi naw o r l df u o fi n f o r m a t i o n 。w h e r et h ee f f e c t i v ed a t a a n a l y s i sa p p r o a c h e sp l a ya ni n d i s p e n s a b l ea n dc r u c i a lr o l e t h ea i mo fd a t a a n a l y s i sl i e si nr e v e a l i n gt h ek n o w l e d g eh i d d e ni nt h ed a t as e t h e n c e ，d a t a a n a l y s i sc a nb ea p p l i e di n t oa l m o s te v e r yf i e l do fh u m a nb e i n g s f r o mt h e c l a s s i c a ld a t aa n a l y s i si ns t a t i s t i c sf i e l dt oc u r r e n tn e wd a t am i n i n gf i e l d ，d a t a a n a l y s i sh a sb e e nd r a w i n ga r e n t i o no fr e s e a r c h e mf r o md i f f e r e n tc o m m u n w e s s of a r , m a n ye f f e c t i v ed a t aa n a l y s i st e c h n i q u e sh a v eb e e nd e v e l o p e db a s e d o nd i f f e r e n tp r i n c i p l e s h o w e v e r t h ea p p l i c a t i o no fs y m m e t r yd e t e c t i o ni nd a t a a n a l y s i sh a sn o td r a w nt h e a r e n t i o nt h a ti ts h o u l dd r a w i nt h i sp a p e nw em a i n l yd i s c u s sh o wt oi n c o r p o r a t es y m m e t r yd e t e c t i o ni n t o o r i g i n a ld a t aa n a l y s i sa p p r o a c h e ss oa st oi m p r o v et h e i rp e r f o r m a n c e f i r s t ，w e p r o p o s e dan o v e lh i e r a r c h i c a lc l u s t e d n ga l g o r i t h mb a s e do nr e f l e c t i o n a l s y m m e t r y , s y m h c ，o fw h i c hb a s i ci d e ai st oi n d u c ea na p p r o p r i a t es i m i l a r i t y m e a s u r e m e n ts oa st oc h a r a c t e r i z et h es y m m e t r i cf e a t u r e ( i fp r e s e n t ) b e r e r a n d i m p r o v e t h e c l u t e r i n ge f f e c t ；o n t h eb a s i so f m e a s u r i n g t h e h o m o g e n e o u s n e s so ft h el o c a ld i s t n b u t i o no fad a t as a m p l ew i t hs y m m e t r y , w e f u r t h e rp r o p o s e dl o c a ld i s t r i b u t i o nb a s e do u t i i e r s 。a c c o r d i n g l y , w ed e v e l o p e d t w od e t e c t i o na l g o r i t h m s ：l d b o da n dl d b o d + ；f i n a l l y , w e 埘e dt op e r f o r m c l u s t e r i n ga n a l y s i so v e rt h eo r i g i n a ld a t as e tt h r o u g ht h es k e l e t o np o i n t si nt h e d a t as e t ；h e n c e ，w ed e v e l o p e dan e w c l u s t e r i n ga l g o r i t h ms p b c d u r i n gt h e p r o c e s so fs k e l e t o np o i n te x t r a c t i o n ，w ea l s op r o p o s e dan e wb o r d e rp o i n t d e t e c t i o na l g o r i t h ms b b p df r o mt h ev i e w p o i n to fl o c a ls y m m e t r ys oa st o d e t e r m i n et h e 。s h a p e ”o fc u r r e n td a t as e t i nt h i sp a p e r ，w ec o n d u c t e ds e v e r a le x p e r i m e n t so v e rt h es y n t h e t i ca n d r e a l - w o r l dd a t as e t st oe v a l u a t et h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m s t h r o u g hc o m p a r i s o nw i t hp r e v i o u sa l g o r i t h m s m e a n w h i l e w e 仃i e dt oa p p l y t h e mi n t os o m ep r a c t i c a lp r o b l e m sl i k en e t w o r ki n v i s o nd e t e c t i o n 。m i c r o a r r a y d a t aa n a l y s i s k e y w o r d s ：s y m m e t 蟛, c l u s t e r i n ga n a l y s i s , o u t l i e rd e t e c t i o n , n e t w o r ki n v a s i o n d e t e c t i o n ，s k e l e t o np o i n t s u b j e c tc l a s s i f i c a t i o n ：t p 3 0 1 1 - 2 - 复旦大学硕士学位论文 1 引言 1 引言 1 1 研究背景、目的和意义 2 0 世纪是科学技术迅速发展韵世纪，物理和化学的发展使我们可以清楚地 认识物质的组成，从分子、原子、电子等各个层次上深入地了解微观世界；而天 文技术、空问技术的发展则使得我们可以了解地球以外的客观世界；以电子信息 技术为龙头的工业技术的飞速发展，使得我们可以不断地改造世界，甚至为人类 更加舒适地生活创造新的世界。 信息技术尤其是计算机科学技术的发展，使我们可获得的数据信息呈级数增 长。可以毫不夸张地说，我们正生活在一个信息数据爆炸的时代，各种数据信息 的种类之多，数量之大远非我们可以想象。以人类基因组计划c 踟棚孵厅6 n o m e p r o j e c t , h g p ) 为例，它是美国在1 9 9 0 年提出实施的项伟大的科学计划，主要 任务是测定人类碱基序列，其数据量将达到3 0 亿个碱基对。 最近，由e m c 公司赞助i i ) c ( 美国国际数据公司) 进行的一项题为数字宇宙 膨胀：到2 0 1 0 年全球信息增长预测的研究1 1 】中指出，2 0 0 6 年全球产生的数字 化信息总量达1 5 1 0 亿吉比特，其中原刨信息为4 0 0 亿吉比特，而到2 0 1 0 年，全 球产生的数字化信息总量有望达到9 8 8 0 亿吉比特，在短短的四年间就将翻六倍。 1 6 1 0 亿吉比特具体意味着多少呢? 如果我们要将所有这些信息用打印纸打印出 来，则所用的纸张可以覆盖地球表面四次之多。下面图1 1 ( a ) ( b ) 分别给出2 0 0 2 到2 0 1 0 年每年电子邮件和数字图像的数据量统计( 预测) 1 1 1 。 ( a )( b ) 图1 12 0 0 2 - - 2 0 1 0 年每年电子邮件和数字图像的数据量统计( 预测) 数据的丰富导致了对强有力的数据分析方法的需求，大量的数据被描述为 复旦大学硕士学位论文1 引言 。数据丰富。但信息贫乏”。没有强有力的数据分析方法，理解快速增长的海量 数据已经超出了人的能力。正因为如此，数据分析获得了多个领域研究学者们的 重视，而且已经积累了大量实用有效的数据分析方法。 很多数据分析方法都来自于统计学领域，以多元统计分析为例，它主要是用 来研究客观事物中多个变量( 或多个因素) 之间相互依赖的统计规律性，是数理统 计学中的一个重要分支。目前，学者们已经提出了很多有效的分析方法，比如； 多重回归分析、判别分析、聚类分析、主成分分析、对应分析、因子分析、典型 相关分析等。 近些年发展起来的机器学习( m a c h i n ek 锄i g ) 可以说是数据分析研究的一 个新兴领域，它旨在研究计算机怎么模拟或实现人类的学习行为，以获取新的知 识和技能，重新组织已有的知识结构傻之不断改善自身的性能，它属于入工智能 研究的范畴，是使计算机具有智能的根本途径，同时也为数据分析方法的研究注 入了新的活力。 为了更好地处理和理解快速增长的海量数据，学者们于2 0 世纪8 0 年代末期 创立了一个新的研究领域，数据挖掘( d a t am i n i n 0 ，或称数据挖掘和知识发现 ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y , d m k d ) 。这是在数据库技术，机器学习、 人工智能、统计分析等基础上发展起来的一个交叉性的学科，也可以说它是以往 数据分析研究领域的一个集成。自从数据挖掘和知识发现的概念于1 9 8 9 年8 月 首次出现在第1 1 届国际联合人工智能学术会议以来，数据挖掘和知识发现领域 的研究和应用均得到了长足的发展，形成了一些行之有效的理论和方法，并逐渐 成为数据分析研究领域的研究热点。 粗略地讲，数据挖掘是研究从大量的、有噪声的、随机的数据中抽取挖掘出 未知的、有价值的模式或规律等知识的复杂过程【2 】。丽数据挖掘的过程可大致分 为：问题定义、数据收集和预处理、数据挖掘算法的执行以及结果的解释和评估， 如图i 2 所示。 图1 2 数据挖掘的过程描述 数据挖掘是为了在大量的数据中发现有用的令人感兴趣的信息，因此发现何 种知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中，数 复旦大学硕士学位论文1 引言 据挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据 挖掘的要求；另一方面通过对各种学习算法的对比而确定可用的学习算法。 数据准备又可分为三个子步骤：数据选取、数据预处理和数据转换。数据选 取的目的是确定发现任务的操作对象，是根据用户的需要从原始数据中抽取的一 组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。 数据转换的主要目的是消减数据维数，即从初始特征中找出真正有用的特征，以 减少数据挖掘时要考虑的特征或变量个数。 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的，如分 类、聚类、关联规则发现或序列模式发现等，再决定使用什么样的算法。选择实 现算法有两个考虑因素：一是不同数据有不同特点，需要用与之相关的算法来挖 掘；二是用户或实际运行系统的要求。 数据挖掘阶段发现出来的模式，经过评估，可能存在冗余或无关的模式，这 时需要将其剔除；也有可能模式不能满足用户要求，这是则需要整个发现过程回 退到前一阶段，如重新选取数据、采用新的数据变换方法等。此外，知识发现最 终是面向人类用户的，因此要对发现的模式进行可视化，或者将结果转换为用户 易懂的表示方式。 前面提到，数据挖掘的目标在于发现隐藏在大量数据中的有用的知识，这个 目标也正是数据分析的目的所在。数据的量往往比较大，变化也比较快，而知识 却比较精炼，相对也比较稳定。但同时我们也应该注意到这一目标所应面对的困 难和挑战。 在所有的困难中，最大的困难在于如何定义和表示知识。虽然人脑在存储信 息，提取知识方面有着无与伦比的潜力，但目前我们对于这种机制仍然所知不多， 更别说有效地将其应用于实际的数据分析了。要想达到预期的目标，我们必将还 有很长的一段路要走。 数据分析的意义是不言而喻的，凡是需要对数据进行处理的领域都会用到这 样或那样的数据分析方法。特别是在今天这样一个信息爆炸的时代，数据分析更 是显得不可缺少。下面我们特别分析几个应用领域，以说明数据分析可能的应用： 在过去的几十年里，生物医学研究有了迅猛的发展。从新药物的开发和 癌症治疗的突破，到通过大规模序列模式和基因功能的发现进行人类基因 的识别与研究，这些研究大量都集中在d n a 数据的分析上，有效的数据分 析方法将为d n a 数据分析提供有力的工具 复旦大学硕士学位论文1 引言 大部分银行和金融机构都提供丰富多样的储蓄服务，信用服务和投资服 务，这必将产生海量的数据，因此也对数据分析方法提出了更高的要求 零售业也是数据分析的主要应用领域，这是因为零售业积累了大量的销 售数据，顾客购买历史记录，货物进出，消费与服务记录等等，其数据量 还在不断地迅速膨胀。有效的数据分析方法可有助于识别顾客的购买行 为，发现顾客购买模式和趋势，改进服务质量，取碍更好的顾客保持力和 满意程度 电信业已经迅速地从单纯地提供市话和长话服务演变为提供综合电信服 务，如语音、传真、寻呼、移动电话、图像、电子邮件，以及其它数据通 信服务。利用数据分析技术来帮助其理解商业行为，确定电信模式，捕捉 盗用行为，更好地利用资源和提高服务质量是非常有必要的 1 2 本文主要贡献 本文主要研究对称性在数据分析中的应用，旨在从一个新的角度去分析数 据。改进已有的算法，具体而言： 我们提出了一种新的层次聚类算法s y m h c ( s y m m e t r yb a s e dh i e r a r c h i c a l c l u s t e r i n g ) 。在该算法中。我们首先度量给定数据集的镜像对称性并检测 相应的对称超平面，如果镜像对称性比较显著的话，我们就根据获得的对 称信息导出相应的“接近度”度量矩阵并用传统的c o m p l e t e - l i n k 层次 聚类算法进行聚类，否则裁采甩通常的欧氏“接近度”度量矩阵进行聚类 从局部分布的角度出发，我们提出了新的离群点检测算法 l d b o d l d b o d + ( l o c a ld i s t r i b u t i o nb a s e do u t l i e rd e t e c t o r ) 。不同于最近 比较流行的l o f 离群点检测算法( 从局部密度的角度进行检测) ，我们用局 部分布来刻画离群点的特征，而局部分布主要是通过如下三个量进行量 化；局部平均距离，局部密度和局部分布均匀度，其中局部分布均匀度的 度量可以转化为局部对称性的度量 基于数据集的骨架点，我们又提出一种新的聚类分析算法s p b c ( s k e l e t o n p o i n t b a s e d c l u s t e r i n g ) 。在该算法中，我们通过当前样本集的。形状”来 决定所需要的骨架点，为了较为准确地判断当前样本集的“形状”，我们 从局部对称性的角度出发，提出了基于对称性的边界点检测算法 s b b p d ( s y m m e t r yb a s e db o r d e rp o i n td e t e c t i o n ) 复旦大学硕士学位论文1 引言 1 。3 本文结构 本文第二章首先讨论对称性的基本概念，然后提炼出关于对称性的两个基本 侗题：对称性的检铡和度量，并在此基础上对前入的一些相关研究进行介绍。 本文第三章提出了一种新的层次聚类算法s y n t i c 。我们首先对方法的动机进 行讨论，然后详细的阐述了算法的两个关键闳题；翅何检铡给定数据集的镜像对 称性以及如何根据获得的对称信息导出合适的“接近度”度量，最后对相关的工 作进行了综述，并且利用三个具有镜像对称性的人造数据集和三个从u c i d s 获得 的实际数据集对s y m b c 算法的有效性进行了评估。 本文第四章从局部分布的角度出发，提出两个新的离群点检测算法 l d b o d l d b o d + 。我们首先对方法的动机进行描述，然后给出局部平均距离，局部 密度和局部分布均匀程度三个量用以量化描述数据点的局部分布，在此基础上， 给出两种不同类型的检测算法，并用一些医学相关的实际数据集对l d b o d l d b o d + 的有效性进行检测。此外，我们也讨论了l d b o d l d b o d f 在网络入侵检测问题 中的应用。 本文第五章提出了一种新的聚类分析算法s p b c 。我们首先对方法的动机进 行描述，然后从局部对称性的角度提出了边界点检测算法s b b p d ，并在此基础上 提出了相应的骨架点提取算法积聚类算法。我们利用u c i 的一些实际数据集对该 算法的有效性进行检测，同时也将其应用于基因芯片数据的聚类分析。 最后，本文第六章总结了全文，讨论了本文研究存在的问题。并对未来可能 的研究方向进行了展望。 复旦大学硕士学位论文 2 对称性检测及度量 2 对称性检测及度量 对称性在我们的周围随处可见，扶自然界的植物，动物，以及星球，银洞系， 到很多人造的物体，都呈现出不同程度的对称性。对于我们人类而言，能够准确 检测和度量对称性是一种非常重要的能力 下面我们首先讨论对称性的定义，在此基础上，提炼出关于对称性的两个关 键问题，最后对前人的相关工作进行综述。 2 1 对称性定义 粗略地讲，对称性是指某种变换下的不变性，例如，将一个正方形绕其某条 对角线旋转1 8 0 度，则旋转后的图形和原来的图形重合。在数学上，我们通常用 对称变换来刻画物体的对称性。所谓对称变换是指这样一种交换：将该交换应用 于某个系统，所得结果和原来的系统是相同的。 数学上可以证明，对于一个对称系统，其所有对称变换可以构成一个群，通 常我们称这个群为对称群【3 1 。下面以 3 中的一个例子来说明对称性的概念。 图2 1 用以说明对称性概念的矩形示意 如图2 1 所示，该矩形具有三种对称性：关于轴a 镜像对称，关于轴b 镜像 对称，以及关于点c 中心对称。为了描述该矩形的对称性，我们定义如下四个对 称变换： 绕轴a 旋转1 8 0 度：1 - - 4 ，2 - - 3 ，3 2 ，4 一l ，记为口 绕轴b 旋转1 8 0 度：1 - - 2 ，2 - - 1 ，3 4 ，4 3 ，记为口 关于c 反射：l 一3 ，2 - - 4 ，3 - - 1 ，4 2 ，记为， 不变变换：l 一1 。2 2 ，3 3 ，4 4 ，记为e 复合运算0 表定义如下： 复旦大学硕士学位论文2 对称性检测及度量 oe口 芦y ee口 夕r dae y 声r e a ry 口 e 由运算表可知：合成运算0 是封闭的，e 是它的单位元，每个元素以其自身 为逆元，由复合映射的性质知。又是可结合的，所以，该矩形的所有对称变换关 于其合成运算。构成一个群，就是我们前面提到的对称群。 前面对称性的定义仅适用于具有精确对称性的系统，因为它要求变换后的结 果和原来系统完全相同。然而，在现实世界中，精确对称是非常少见的，尤其是 对于数字信息，由于量化和表示的误差，结果很可能只能保持近似对称。因此， 在本文后面的研究中，我们都是考虑近似对称经，这里近似对称性是指系统在对 称变化下所得的结果“几乎”和原来的系统重合。显然，这里的关键是如何对“几 乎”的含义进行量化。 最容易理解和识别的对称性是几何对称，图2 2 示意了如下类型的几何对 称： 线性( 一维) 几何对称：平移对称，点镜像对称 平面( 二维) 几何对称：线镜像对称，滑动对称( 平移对称和镜像对称的组 合) ，旋转对称 空问( 三维) 几何对称：面镜像对称，扭对称( 平移对称和旋转对称的组合) 除了几何对称以外。还有缀多其它类型的非凡何对称，比如：时褐对称，即 系统在时间反演下是保持不变的，或颜色对称，即系统在颜色空间变换下保持不 变。 在本文的研究中，我们主要考虑双边对称性。如果存在某个超平面使得系统 在关于该超平面的镜像变换下保持不变，我们就说该系统是双边对称的。因此， 常见的关于点，线，面的镜像对称都属于双边对称的范畴。 2 2 对称性的检测和度量 尽管有多种不同类型的对称，但目前大多数的研究都是考虑双边对称性和旋 转对称性。如果不考虑所有的底层技巧的话。所有的研究可以大致分为两个方面； 复旦大学硕士学位论文 2 对称性检测及度量 对称性的检测和对称性的度量。其中，对称性检测旨在发现一个系统的对称性而 不必量化其对称的程度，而对称性度量的目标是量化对称的程度，这种量化可以 是局部的也可以是全局的，局部度量是对数据集中的每个点的对称性进行度量， 可以用来度量纹理或者定位具有高对称性的点，全局度量是考察整个数据集的对 称性，可以直接用来分类或比较数据集。 图2 2 各类几何对称示意图 在本文的研究中，我们需要将这两个不同的问题结合起来考虑，首先考虑如 何衡量给定数据集相对于某个超平面的对称程度，然后根据这种度量决定数据集 的对称超平面，即给定数据集关于该超平面的对称程度最高，具体细节可以参考 本文第三章的处理。 2 3 相关工作综述 对称性及其应用的研究是一个非常活跃的研究领域，目前无论是在理论还是 在实际应用方面，都取得了大量的成果。 关于对称性最早的研究始于心理学家，他们渴望理解人类是如何感知对称性 的a 这些研究结果揭示了人类对对称性的感知和对称性的数学概念并没有直接的 复旦大学硕士学位论文 2 对称性检测及度量 联系。 z u s n e l 4 】使用“s y m m e t r o g r a p h ”( 如图2 3 所示) 来度量二维多边形的旋转对 称性，这种度量通过量化该多边形在慢慢旋转过程中和它自己的重叠程度来进 行。经过反复实验，z u s n e 得出的结论是人们对对称性并没有一个很好的概念。 根据s a n t i n i 和j a i n 的理论阁，“在一些情况下，学者们选取一些合适的特征将 一幅图像表示为向量空间中的一个点，通常这需要作出一些重要的但又无法确保 正确的假设，例如他们通常假设向量空间的距离度量是采用欧氏度量”。如果人 类对于对称性的感知像对颜色的感知一样是非线性的，则可以从一定程度上解释 z u s n e 的结论，即人们所感知到的对称性同数学上计算出来的对称性是有所不同 的。 图2 3z u s n e 实验中“s y m e t r o g r a p h ”示意 f a u b e r t l 6 】的实验证明，相比于其它情况，人类更容易检测垂直方向的镜像 对称性。图2 4 给出了一个这样的例子。z u s n e 和f a u b e r t 的工作在一定程度上 表明人类感知到的对称性同数学上定义的对称性并没有太多的相关性。因为一个 给定点集可以任意旋转而不改变数学计算的结果，但旋转却明显地影响到了人类 对对称性的感知。因此下面综述的工作可能并不能精确地建模人类对于对称性的 感知，它们只是基于对称性的数学描述。 一些研究学者们认为对称性是视觉感知的一个重要组成部分。v e t t e r ， p o g g i o 和b u l t h o f l 做了相关的心理实验，在实验中，实验对象被要求识别对 称的和不对称的三维物体，最后他们得出的结论是人类更容易识别对称的物体。 复旦大学硕士学位论文2 对称性检测及度量 l a b o n t e 掣刀模拟人类的感知对由点和线段构成的图像的全局双边对称性 进行检测。在他们的方法中，首先将图像数据按照它们的接近度，相似度和方向 进行聚类，然后通过比较每对聚类的对称轴确定全局对称性。他们宣称他们的模 型和人类对于对称性的感知是一致的，并且认为聚类过程要先于对称性的感知。 o - ， o - 。 - 吧 ， 。i - 。 图2 4f a u b e r t 实验示意 除了心理学家对于对称性的研究以外，其它各个领域也都对对称性或其应用 从不同的角度进行了研究，但其中大多数方法都是针对数字图像而提出的。 m a r o l a g j 提出一种方法可以用来检测仅包含一个物体的数字图像的所有近 似镜像对称轴。在该方法中，他们用极坐标表示数字图像，其中以原图像的质心 作为坐标原点，然后图像的对称性通过一个“对称系数”的量来度量，其范围是 从0 ( 没有对称性) 到1 ( 精确对称) ；随后，p r i d m o r e l 9 1 提出一个类似的方法，但 其方法主要是基于霍夫变换( h o u g ht r a m f o n m ) ；i m i y a 等1 1 川也是在霍夫空间中检 测多边形的旋转对称性。 有些学者提出利用图像的频谱来简化对称性检测的问题，这是因为空间对称 特征在频域中可以被转化为更加简单的模式。比如，带状图像对应于频域中的一 条线，而空间中相互交织的模式也对应于频域中的交叉，如图2 5 所示。 频域方法在描述图像纹理方面也是非常有用的，通常粗糙的纹理对应于图像 的低频部分，而精细纹理对应于图像的高频部分。由于频域方法要求连续的数据， 因此它们只适用于一维信号，二维图像等的处理，而不能应用于稀疏的数据点集。 y o d o g a w a “】对二维单一模式图像的对称性提出一种度量，称为 “s y m m e t r o p y ”，这个量是将该图像垂直，水平，中心方向的对称度量累加而得 到的，这里的对称度量是通过图像的w a l s h 能量谱来定义的，该方法的缺点是其 对于图像的旋转，平移和收缩等不能保持不变性。 一 ， - - “ 。龙ki-k一甏 一 一 复旦大学硕士学位论文2 对称性检测及度量 b i g u n 1 2 i 提出用共轭调和函数对来表示坐标变换，从而定义灰度图像中的局 部旋转对称性。在该方法中，对称性是在f o u r i e r 域中建模的，但实际检测是通 过空间域的卷积来实现的，因此对于图像的每个邻域，卷积的结果是一个复数， 其中复数的模用来表示相应的对称程度。 跏b u r 等【”】使用局部g a b o r 能量谱的复数矩来度量二维灰度图像的局部对 称性。最近，k o v e s i i t 4 提出一种新的频域方法来度量二维图像的局部对称性， 在该方法中，他们根据一维信号中相位谱的一致性计算一个维度无关的对称量， 通过在多个方向进行类似的计算并加以组合，数字图像中的每个象素都被赋予一 个对称程度值。 图2 5 具有对称性的数字图像的频域对应表示 z a b r o d s k y 等【1 习【1 6 j 提出很多概念和方法用于二维数据点集和数字图像的对 称性检测。与以往方法不同的是，他们将对称性看成一种连续的特征，而不是以 往的有或无的特征。具体地，他们定义对称变换( s y m m e t r yt r a n s f o r m ) 如下：使 某个形状变为对称的，对每个顶点所需要的最小平移和旋转量，相应地，对称距 复旦大学硕士学位论文2 对称性检测及度量 离( s y m m e t r yd i s t a n c e ) 定义为所需要的最少努力将一个几乎对称的形状转为精 确对称的形状。实际地，对称距离可以定义为所有顶点移动距离的平方平均值。 与此同时，他们也提出一个多分辨率方法来降低概率分布函数中局部最小值的影 响，这个方法的基本思路是先在较低的分辨率上生成近似的对称变换，然后再在 较高的分辨率下“精化”前面褥到的近似对拣交换。 由于z a b r o d s k y 等的方法是计算最可能的对称镜像，因此他们不需要事先对 要处理的物体的形状做任何假设，这点带来的好处是可以用来恢复一些被遮挡的 近似对称的形状。 z a b r o d s k y 等宣称他们的方法可以很容易被扩展到高维的情况，并且将二维 数字图像假想为三维物体以检测他们方法对三维数据的有效性但这里存在的问 题是二维数字图像并非真正的三维物体，它只是三维物体从一个视点观察的结 果。尽管在理论上，他们的方法可以适用于高维的情况，但方法本身的复杂性妨 碍了它在实际中的推广和应用。 r e i s f e l d 和他的同事们旧也在二维数字图像的对称性检测方面作出了重要 的贡献，并且用对称性来理解数字图像的内容比如，他们使用一般化的对称算 子( g e n e r a l i z e ds y m m e t r yo p e r a t o r ) 来度量二维灰度图像纹理，同时该算子也可以 直接用来检测数字图像的对称性，图2 6 给出一个效果示意。 图2 6 一般化的对称算子对数字图像对称性检测示意 在上面提到的检测算法中，几乎所有的算法只能应用于二维数字图像，或者 说很难推广到三维甚至更高维的情形，因此，学者们也针对三维或者更高维的情 复旦大学硕士学位论文 2 对称性检测及度量 况提出了一些算法。 m a r g o l i n 等1 1 8 1 对点集定义了一个对称度量，该度量的范围是从0 到1 ，其 中，0 表示没有对称性，而l 表示精确对称，他们的思路是先计算该点集多面体 凸包的体积v ，然后将该点集作对称变换获得其镜像点集，并计算原来点集和镜 像点集的总体积v ，最后以体积比v v 作为该点集的对称度量。该方法的缺陷在 于它仅适用于凸点集的情况。对于二维的情况，他们提出使用周长来代替体积。 但由于要计算点集的凸包，该方法的计算量还是比较大的。 c o l l i o t 等【刎也提出一个类似的对称度量，不同的是，他们是通过度量原数 据点集和其镜像点集之间的距离来度量给定点集的对称性，该方法不受数据维数 限制，可以非常容易地推广到高维的情形，而且它的复杂度也不是很高。在本文 后面的研究中，我们也是采用类似的思路来检测数据集的对称性，具体细节可参 考后面3 2 部分。 s u n 等【1 9 1 提出利用扩展高斯图像( e x t e n d e dg a u s s i a ni m a g e ) 来检测三维物体 的镜像对称和旋转对称平面。物体的扩展高斯图像是定义在单位球表面的一个连 续函数，该方法首先使用原始图像和其扩展高斯图像计算一个三维方向直方图 ( 3 do r i e n t a t i o nh i s t o g r a m ) ，然后对这个直方图进行分析以确定原来图像的对称 平面，但该方法只能检测到最主要的对称性，而不能检测到所有的对称性。该方 法将三维物体看成是二维物体，因为它只考虑了物体的表面，而且没有量化物体 对称的程度，属于对称性检测的范畴。另外，该方法的计算复杂度也比较高。 总而言之，作为一个非常活跃并且非常有用的研究领域，关于对称性的研究 势必会继续受到广大学者们的关注。我们认为未来关于对称性的研究，可能主要 会集中于三个方向： 继续从心理学的角度理解人类对于对称性的感知，真正搞清楚对称性在 人类感知中所起的作用 继续研究针对于二维图像的高效的，健壮的对称性检测算法，因为当今 世界的数字信息中，非常大的一部分是数字图像信息，数字图像的处理 和以往相比，将具有更多更广的应用前景；另外，由于人类世界到处都 可以看到对称的现象，因此对称性也必然会体现在数字图像中，从对称 性的角度来研究和理解图像是一个很好的思路 对三维或者更高维的情形，探讨有效的对称性检测算法，虽然一般的数 据集并不如二维数字图像广泛，但随着信息技术的发展，这样的数据也 会越来越多，但目前这方面的研究还不是很多 复旦大学硕士学位论文 2 对称性检测及度量 2 4 本章小结 本章首先就对称性的概念进行描述，在此基础上，我们提炼出关于对称性研 究的两个关键问题：对称性检测和对称性度量，其中前者是旨在发现对称性而不 去量化，后者在一定程度上恰好相反。 然后我们就前人的相关工作进行综述，首先，我们回顾了心理学家对于对称 性所作的研究，发现数学上定义的对称性和人类所感知的对称性并没有直接的联 系；其次，我们主要总结了学者们就二维数字图像所提出的对称性检测方法，其 中有直接在空间域上执行的方法，也有基于频域的方法；最后，我们主要是就三 维和高维的情形，综述了学者们提出的一些方法。 复旦大学硕士学位论文 3 基于近似镜像对称的层次聚类 3 基于近似镜像对称的层次聚类 本章我们从镜像对称的角度提出了一种新的聚类算法s y m h c ( s y m m e t r y b a s e d h i e r a r c h i c a lc l u s t e r i n g ) ，该算法旨在解决预先设定相似度度量所存在的问 题。接下来，我们首先描述该算法的动机，然后叙述两个关键问题的解决：如何 检测给定数据集的近似镜像对称性，以及如何利用已经获得的对称信息导出适合 给定数据集的相似度度量，最后对前人相关的工作进行综述，并给出实验结果。 3 1 动机 聚类分析是探索发现给定数据集底层结构的基本工具之一，已经被广泛应用 于很多个领域。事实上，聚类( 或者说分类) 是人类所具备的最基本的能力之一， 并且在人类发展的漫长历史中扮演着不可缺少的重要角色i 矧。 正如许多研究学者们指出的那样，聚类分析旨在将一组对象划分成若干个均 匀的子类，并且使得同一个子类中的对象彼此间非常相似，而不同子类中的对象 彼此不相似，也就是人们常说的“物以类聚，人以群分”。通常，聚类分析可以 被分为两个不同的类别：有监督聚类分析( s u p e r v i s e dc l u s t e r i n ga n a l y s i s ) 和无监 督聚类分析( u n s u p e r v i s e dc l u s t e r i n ga n a l y s i s ) ，其中前者是对有类别标记的数据 样本进行分析处理，而后者是对无类别标记的数据样本进行分析。最近，介于有 监督聚类分析和无监督聚类分析之间的半监督聚类分析( s e m i s u p e r v i s e d c l u s t e r i n ga n a l y s i s ) 也获得了学者们的关注1 2 5 1 。 粗略地讲，已存的聚类算法可以分为两大类：层次聚类分析和划分聚类分析， 这里分类的标准是基于聚类算法所产生的结果的特征瞄l 。具体地，层次聚类对 数据对象进行一系列的聚类或者划分，无论是聚合型聚类( 开始将每个数据对象 认为是一个聚类，然后不断聚类直到所有数据对象都被划到一个大的聚类中) 还 是分割型聚类( 开始时将所有数据对象看成是一个聚类，然后不断进行划分直到 每个数据对象都单独成为一个聚类) ，其结果都是一个层次结构，相对的，划分 型聚类算法只是将给定对象分成预先给定的若干个聚类，而不涉及到层次结构。 无论是层次聚类还是划分型聚类，它们都要依赖于个相似度( 或不相似度) 度量的定义。这种度量实质上是确立了一个将样本分入哪一类的规则。很多聚类 算法采用的都是预先确定的相似度度量，这往往需要作出很多假设，比如数据样 本的分布，聚类结果的形状等等。像传统的k m e a n s 算法就假定聚类结果是超球 复旦大学硕士学位论文3 基于近似镜像对称的层次聚类 或超椭圆，从而采用欧氏距离作为不相似度的度量。尽管这些算法大多数情况下 表现良好，但对于少数不服从假设分布的数据集，它们就很难准确地刻画数据对 象间本来的相似度。解决该问题的一个方案是从数据集中自动“学习”需要的相 似度度量，而不是预先确定这种度量。 通常，为了从数据集中“学习”合适的相似度度量，我们往往需要一些背景 知识或者关于给定数据集的先验知识。在已有的一些方法中，这些知识是以部分 已经标记的样本或者某些样本对间的相似度限制的形式来提供的1 2 2 1 1 ：2 3 l 。 尽管对于半监督聚类分析，自动学习合适的相似度度量已经取得了较多的成 果，但其对于严格的无监督聚类分析仍然充满了挑战。一个非常新颖有趣的尝试 是基于对称性来定义相似度度量，比如，在 2 4 中，s u n 等从点对称( 或称中心 对称) 的角度提出一个新颖的距离度量，其中是以聚类的中心作为中心对称的参 考点。 基于同样的考虑，本章尝试利用给定数据集的近似镜像对称性来导出合适的 相似度度量，目标是使得这种度量能够更好地反映数据集的对称特征。尽管本章 的思路和 2 4 有所相似，但本章提出方法的具体实现还是有着很大的不同，具体 表现在如下几个方面：首先，我们并没有强制给定数据集一定要具有对称性，我 们会将对称性的检测作为一个预处理阶段，如果数据集确实具备对称性，我们就 根据获得的信息调节数据对象的相似度度量，否则就按照通常的方式进行聚类。 其次，在本章中我们考虑的是镜像对称，在自然界中，镜像对称要比中心对称更 为常见。再次，我们仅是利用获得的对称信息来导出合适的相似度度量。 由以上分析，我们可以发现本章的两个关键问题在于：如何检测给定的数据 集是否具有镜像对称性，如果数据集确实是对称的，如何根据获得的对称信息修 改相似度度量，使其能更好地反映数据集的对称特征。 3 - 2 近似镜像对称性的检测 如前所述，对称性通常用对称变换来描述，其中对称变换是指这样一种变换， 将该变换应用于一个系统，所得的结果与原系统是完全相同的，关于对称性的更 多细节可参考第2 章。 在我们能将对称信息应用于聚类分析前，我们必须解决如下的问题：我们应 当如何有效地检测并度量给定系统的对称性。如果我们仅将对称性作为一个二元 特征( 即一个系统不是对称的，就是非对称的) ，或者只考虑精确对称，则这个问 题就容易得多。然而，由于数字化或量化的误差，即使是精确对称的物体也可能 复旦大学硕士学位论文 3 基于近似镜像对称的层次聚类 失去其精确对称性。如果将对称性作为一个近似的特征【捌考虑，我们便可以更 精确她描述非精确的对称性。如前所述，如果一个系统相对于某种变换是近似不 变的，我们就说该系统关于这种变换是近似对称的，这里的难点就在于如何量化 “几乎不变”。现在，前面的闯题可以重新表述为：如何有效检测和度量一个给 定系统的近似对称性。在接下来的讨论中，我们仅考虑7 维数据点集的