（计算机应用技术专业论文）天文光谱分类算法在分布式环境下的应用研究.pdf

i i l 东大学硕十学位论文 摘要 天体光谱蕴含着天体重要的物理信息，通过光谱的研究，人们可以测定天体 的成分，确定天体的表面温度，光度，直径，质量等信息。因此，光谱分析在天 体和物理学中占有重要地位。l a m o s t 望远镜建成以后，每个观测夜都将产生 上万条光谱。如何处理这些海量光谱从而及时获得所需的科学信息成为一项重要 的议题。 数据挖掘技术正在众多领域中得到广泛的应用，它是从大量的、不完全的、 有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但 又是潜在有用的信息和知识的过程。运用数据挖掘技术可以实现相关性预测，分 类，聚类，孤立点发现，时间序列分析等等功能，面对海量的光谱数据，数据挖 掘技术正好可以为解决光谱数据的分类，参数测量等工作提供很好的支持。 天文光谱数据具有海量及分布式存储等特点，其相关的处理需要分布式环境 及数据挖掘算法的支持。本文主要研究分布式环境下天文光谱数据挖掘的并行和 分布式挖掘算法。以分布式存储的光谱多属性数据集为基础，利用主从模式的并 行程序模式，对光谱进行快速并可扩展性的分布式并行处理，并减少冗余计算及 节点间的通信量，避免了不必要的网络负载和网络竞争的产生，解决并行分类算 法性能的负载均衡问题，以期提高天文光谱处理的效率。结果表明，不仅有利于 减少通信机进行i o 的开销，并能根据统计信息和网络状态、通信代价，考虑到 任务均衡，合理分配任务，有利于提高算法的并行度和执行效率。 本论文的主要工作包括： ( 1 ) 建立分布式运行环境，搭建基于m p i 的并行计算环境，进行分布式分 类挖掘算法的研究。( 2 ) 提出考虑负载平衡的分布式并行挖掘系统，提出在分类 算法任务分配时，根据网络负载和计算节点负载情况合理分配任务，达到并行挖 掘效率的最大化。( 3 ) 按照数据挖掘的一般流程，对晚型星和类星体两类星体的 的光谱数据进行特征提取，主要利用p c a 方法进行降维处理，以适应分类需要。 ( 4 ) 研究s p r i n t 算法，将s p r i n t 算法并行化实现，并对并行s p r i n t 算法 进行了改进，对降维后的光谱数据在分布式环境下进行分类处理。 关键词：分布式数据挖掘、并行决策树分类算法、负载均衡、天文光谱 【j 东大学硕十学1 7 = 论文 a b s t r a c t t h es p e c t r ao fc e l e s t i a lb o d i e sc o n t a i ni m p o r t a n tp h y s i c a li n f o r m a t i o no fc e l e s t i a l b o d i e s t h r o u g hr e s e a r c h e so ns p e c t r a , p e o p l ec a l lq u a l i t a t i v e l yo rq u a n t i t a t i v e l y m e a s u r et h ec h e m i c a lc o m p o n e n t so fc e l e s t i a lb o d i e s ，d i r e c t l yo ri n d i r e c t l yc o n f i r m s u r f a c et e m p e r a t u r e ，l u m i n o s i t y , d i a m e t e r , a n dm a s so fc e l e s t i a lb o d i e sa n dd o r e s e a r c ho nr a d i a lm o v e m e n ta n ds e l fr e v o l u t i o no fc e l e s t i a lb o d i e s t h u ss p e c t r a l a n a l y s i sp l a y sa l li m p o r t a n tr o l ei na s t r o p h y s i c s a f t e rt h ee x p e c t e dc o m p l e t i o no ft h e l a m o s t p r o j e c t ，l a r g ea m o u n to fs p e c t r ao fc e l e s t i a lb o d i e sw i l lb ec o l l e c t e di ne a c h o b s e r v a t i o nn i g h t h o wt od e a l 、航t l it h e s ev o l u m i n o u ss p e c t r aa n do b t a i nu s e f u l s c i e n t i f i ci n f o r m a t i o nb e c o m e sa l li m p o r t a n tr e s e a r c ht o p i c d a t am i n i n gt e c h n o l o g yh a sb e e nw i d e l ya p p l i e di nm a n yf i e l d s d a t am i n i n gi sa c o u r s eo fe x t r a c t i n gc r y p t i c ，u n k n o w nb u tp o t e n t i a lu s e f u li n f o r m a t i o na n dk n o w l e d g e t h a te m b e d d e di na b u n d a n t ，i n c o m p l e t e ，n o i s y , f u z z ya n dr a n d o md a t a b yd a t a m i n i n gt e c h n o l o g y , t h e f u n c t i o n so fc o r r e l a t i v ep r e d i c t i o n , c l a s s i f i c a t i o n , a n d c l u s t e r i n g ，i s o l a t e dp o 缸d i s c o v e r i n ga n dt i m e - s e r i e sa n a l y s i sc a l lc o m et r u e a t p r e s e n tm a n ym i n i n ga l g o r i t h m s 埘ml l i g h - d i m e n s i o n a ld a t ab e c o m er e s e a r c h h o t s p o t s t h es p e c t r ao fc e l e s t i a ld a t aa r ea l s oh i g h d i m e n s i o n a l t h u s ，d a t am i n i n g t e c h n o l o g yc a np r o v i d eg o o ds u p p o r tf o rt h ec l a s s i f i c a t i o no fs p e c t r a ld a t aa n d t h ea s t r o n o m ys p e c t r a ld a t ai sm a s s i v ea n ds t o r e di nd i s t r i b u t e dw a y , a n di tn e e d t ob em i n e di np a r a l l e la n dd i s t r i b u t e dw a yt om e e tt h ed e m a n do fi t sn e e d s w ed i v i d e t h es p e c t r u md a t ai n t op i e c e sa n dm i n ee a c hs e g m e n to fd a t ai np a r a l l e lo rd i s t r i b u t e d w a yw h i c hs t o r e di nd i s t r i b u t e dw a y i nt h ep r o c e s so fm i n i n g ，w eu s eu s e ra g e n tt o r e d u c et h eo v e r l a pc o m p u t i n g ，a n du s ed a t am i n i n ga g e n tt or e d u c et h et r a f f i cb e t w e e n t h ec o m p m i n gn o d e st oi m p r o v et h ep r o c e s se f f i c i e n c y t h em a i nj o b so ft h i st h e s i sa i ma tc l a s s i f i c a t i o no fc e l e s t i a lb o d i e sa n dm a i n p o i n t sa r es u m m a r i z e da sf o l l o w s ： ( 1 ) c r e a t ead i s t r i b u t e do p e r a t i n ge n v i r o n m e n t ，t h es t r u c t u r e sp a r a l l e lc o m p u t i n g e n v i r o n m e n tb a s e do nm p if o rt h ec o n d u c to fd i s t r i b u t e dc l a s s i f i c a t i o na l g o r i t h mf o r m i n i n gr e s e a r c h ( 2 ) p r o p o s ead i s t r i b u t e dp a r a l l e lm i n i n gs y s t e mc o n s i d e r i n gl o a d 3 山东大学硕卜学能论文 b a l a n c i n g ，t h ep r o p o s e dc l a s s i f i c a t i o na l g o r i t h mt a s ka l l o c a t i o n , i na c c o r d a n c ew i t h t h en e t w o r kl o a da n dl o a dc o n d i t i o n so f c o m p u t i n gn o d e s , t om a x i m i z et h ee f f i c i e n c y o fp a r a l l e le x c a v a t i o n ( 3 ) a c c o r dt ot h eg e n e r a lp r o c e s so fd a t am i n i n g ，u s ep c a d i m e m i o n a l i t yr e d u c t i o np r o c e s s i n gt od of e a t u r ee x t r a c t i o no fl a t e - t y p es t a r sa n d q u a s a r st w oq u a s a r ss p e c t r a ld a t at om e e tc l a s s i f i c a t i o nn e e d s ，( 4 ) d or e s e a r c ho f f s p r i n ta l g o r i t h m ，a n dp a r a l l e l a l g o r i t h m s t o i m p r o v es p r i n t , a f t e r t h e d r o p - d i m e n s i o n a ls p e c t r a ld a t ai nt h ed i s t r i b u t e de n v i r o n m e n tu n d e rt h ec l a s s i f i c a t i o n 。 k e yw o r d ：d i s t r i b u t e dd a t am i n i n g ，p a r a l l e ld e c i s i o nt r e ec l a s s i f i c a t i o n , l o a d b a l a n c e ，s p e c t r u m 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：蜘日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：兰盆墨塑导师签名：( 圣垒墨日期：竺2 兰：二 山东大学硕十学位论文 第1 章绪论 1 1 引言 l a m o s t 望远镜建成以后，每个观测夜都将产生上万条光谱。随着数据量 的增加，如何处理这些海量光谱从而及时获得所需的科学信息成为一项重要的议 题，数据挖掘处理海量数据的能力成了不可忽视的问题。分布式数据挖掘是解决 这个问题的有效途径。分布式数据挖掘是分布式计算与数据挖掘技术的有机结 合，是建立在分布式数据集的基础上，用于分布式环境下的数据发现技术【l 】。本 文对于分类算法在分布式环境下的并行化进行探讨，搭建了天文光谱了分布式计 算环境，提出了考虑负载平衡的挖掘系统，并且给出一个分布式分类算法的具体 实现，并对已处理好的光谱数据进行分类处理，验证了算法在天文光谱挖掘中的 适用性。 1 2l a m o s t 项目 1 2 1l a m o s t 简介 大天区面积多目标光纤光谱天文望远镜【2 1 ( l a r g es k ya r e am u l t i - o b j e c tf i b e r s p e c t r o s c o p i ct e l e s c o p e ，l a m o s t ) 于1 9 9 7 年正式立项，目前该项目正在建设中。 l a m o s t 是一台横卧于南北方向的中星仪式反射施密特望远镜，可观测天区的 赤纬从一1 0 度到+ 9 0 度。相应于5 度视场、直径为1 7 5 米的焦面上放置4 0 0 0 根 光纤。采用并行可控的光纤定位技术，可在较短的时间里将光纤按星表位置精确 定位，并提供了光纤位置微调的可能。是世界上光谱获取率最高的望远镜。 l a m o s t 项目完成后将有大量的数据产出，在观测期内将达到1 07 数量级的 光谱数据。这样一个庞大的天文数据，利用人工方法来处理光谱分类显然不能满 足实际的需求。目前，国际上常用的天文软件包有m i d a s ，f i g a r o ，i r a f 等， 它们都是通过人机交互的方式来完成光谱处理的。虽然利用人机交互的方式处理 光谱时可以融入天文学家的专家知识，并根据天文学家的经验做出判断和分析， 但面对像l a m o s t 这样大型的巡天计划的海量数据，如果还采用人工交互方式， 靠天文工作者逐条分析光谱，已经远远满足不了需求。 1 山东大学硕十号：何论文 曼曼皇皇曼篡燃曼! 曼曼! 曼嬲1 1 ； ； 。i 一 一。i i i ； 一 一i i h ! h 1 2 2l m s t 的意义和科学目标 王a m o s t 工程的实施具有重要科学意义，主要表现在如下三个方瑟： ( 1 ) l a v l o s t 在望远镜发展中具有重要的地位。l m , 4 0 s t 望远镜采用了 共行可控的光纾定位技术。由于它的4 米瑟径，在1 5 小时曝光时闻内以l 纳米 的光谱分辨率可以观测到2 0 5 等的暗弱天体的光谱；由于它相应于5 度视场的 1 7 5 米焦面上可以放置数千根光纤，连接到多台光谱仪上，同时获得4 0 0 0 个天 体的光谱，成为世界上光谱获取率最高的望远镜。 ( 2 ) 多墨标光纤望远镜是天文学发展的方向之一。“多目标光纾光谱观测 技术已经成为当今光学天文学重点发展的方向之一。 ( 3 ) l a m o s t 的数据量很大，可供大批天文学家进行课题研究。l a m o s t 望远镜在数年之内将能得到1 0 7 左右的星系光谱，1 0 7 数量级的恒星光谱，以及 约1 0 7 数量级的类星体光谱，这是一个菲常庞大的天文数据库。 l a m o s t 的三大核心课题是：星系红移巡天与宇宙大尺度结构，恒星物理 与银河系结构，多波段天体的光学研究。 ( 1 ) l a m o s t 对上午万个星系，类星体等河外天体光谱进行光谱巡天，将 在诸如星系，类星体和宇宙大尺度结构等河外天体物理和宇宙学问题的研究上做 出重大贡献。 ( 2 ) l a m o s t 在诸如恒星，星族和银河系结构，运动学及化学等河内天体 物理研究上做出重大贡献。 ( 3 ) 结合红外，射电，x 射线等巡天的大量天体的光谱观测将在各类天体 多波段交叉征认上做出重大贡献。 1 2 3la m o s t 光谱处理综述 整个天体光谱自动处理过程可以用图1 1 来表示f 引。这里主要讲述了光谱数 据的获取和预处理过程。首先介绍了获取一维光谱数据的步骤，然后介绍了光谱 数据的常用数据保存格式f i t s 以及光谱分类前的相应处理，包括连续谱归一化、 谱线提取和去噪等。 2 山东大学硕+ 学位论文 图卜1 天体光谱自动处理过程 进入l a m o s t 光学系统的光信号，通过c c d 数据采集系统，得到原始的 二维光谱数据，按照如下图像处理步骤得到一维光谱数据： 1 ) 去除宇宙线，对c c d 坏图像进行插值 2 ) 偏置( b i a s ) 和暗流( d a r k ) 改正 3 ) c c d 图像上光纤孔确认和追迹 4 ) 光谱仪杂散光改正 5 ) 平常校准 6 ) 从二维光谱中最佳地抽取一维谱 7 ) 波长定标及减天光 8 ) 天光改正 9 ) 流量定标 f i t s 是国际天文学会1 9 8 2 年确定的世界各天文台之间用于数据传输，交换 的统一标准格式1 4 。它所记录的数据对象主要是一维，二维乃至多维数据，尤其 在图像处理，储存及传输方面充当着极为重要的脚色。f i t s 文件由一系列定长 的逻辑单元组成，每个逻辑记录长度是2 8 8 0 字节( b y t e s ) 。从内容上来讲，它 由两部分组成：前一部分是a s c i i 码编译的标题记录，用来记录后面数据的文字 描述，参数设定，分析结果等。后一部分是观测数据，可以看作多维的点阵，每 一点的像元值都是定长的( 1 ，2 或4 字节) 二进制数，具体长度由b i t p i x 给出。 一般而言，数据维数在3 0 0 0 维以上。 在光谱处理前首先要进行数据格式的转换，即把f i t s 文件格式转换成后续 处理需要的各种文件格式，比如a s c i i 码格式等【5 1 。同时把原始的单个光谱数据 按组形成以数据矩阵存储的文件。 天体光谱的识别分类基于不同信息【6 】，有的基于整条光谱( 连续谱和谱线) ， 有的基于谱线信息，因此不同的光谱识别器需要进行不同的光谱处理。 3 山东大学硕十学何论文 曼皇曼曼曼鼍黑皇曼曼曼! 量邕鼍嬲曼曼曼曼曼曼璺憋懋曼曼曼曼! 曼曼黑皇皇曼曼曼! 曼烹燃鬯苎! 曼! 曼皇燃姥曼曼曼曼曼量懋嬲葛曼曼曼曼曼曼篡嬲皇皇曼曼曾曼曼懒 连续谱归化的目的是使得相同谱线的表现形式一致。其步骤包括：提取连 续谱，然后用原来的光谱去除连续谱，使连续谱归化。在连续谱提取中，用多 项式逼近连续潜是常用的方法之一：同时，还有许多剐的方法，如形态滤波器 7 1 ， 中值滤波器1 8 】，小波变换f 9 1 等。 谱线提取是连续谱归一化和去噪的副产品。这时的光谱又称为谱线光谱。 噪声对于弱源来说主要是信号噪声，当然还包括天光背景、探测器热噪声以 及未知源等影响，其主要表现形式是随机白噪声，也有波长不固定的干扰噪声。 较好的滤波方法有形态滤波器【1 0 1 ，中值滤波器1 1 1 】，小波变换f 1 2 1 等。 经过上述处理后，再利用数据挖掘技术进行光谱数据的特征提取和选择，从 两达到巨动识别，自动分类和自动测量的鼹的。 1 3 天体光谱分类 1 - 3 1 天体辐射与天体分类 天体光谱自动识别的研究离不开天文学知识，光谱对于天文学家而言，它们 最显著的特征是谱线。天体中的原予、分子等在不同能级之阌跃迁就会吸收或发 射谱线，不同的原子和分子有其特定的谱线。天体的辐射特性可以用不同波长处 强度的分布来攒述。连续辐射指的是不聚集在任何特定波长处的辐射。类星体连 续谱的种可能的解释是同步加速机制；而恒星的连续普是由恒星的有效温度、 表面重力加速度和化学丰度决定的，热星的连续谱的形状是耄中性氢原子的束缚 自由吸收决定的，冷星的连续谱取决于负氢离子的作用。原子在吸收或发出辐 射时，必吸收或辐射菜一特定波长的特定能量的光予，光子集中在某个特定波长 的辐射叫发射线；如果在某一特定波长处辐射少了，就是天体光谱里出现了吸收 线。不同类型的辐射来囊完全不露的天体。 1 3 2 天体光谱分类 宇宙中存在着各种各样的天体，天文上首先以银河系为界线将天体分为河内 源和河外源。其中河内源主要是诞星和星际介质( i s m ) ，而河外源主要是指各种 星系。下面首先介绍有关天体分类的几个重要概念。 4 i i i 东大学硕十学1 = 7 ：论文 正常天体主要包括正常恒星和正常星系；而发射线天体主要包括活动星系， 活动星系核。正常恒星的光谱是由连续光谱和其上所叠加的吸收线组成，分类序 列按有效温度从高到底排序，主要分为七个光谱型：o ，b ，a ，f ，g ，k ，m 。 星系是由几十亿至几千亿颗恒星和星系气体以及尘埃物质等组成。一般把强非热 辐射，喷发，爆发，特小体积里迸发出特大能量等特性成为活动性。活动星系主 要有星暴星系，活动星系核则包括类星体，l i n e r 星系，s e y f e r t 星系等。 l a m o s t 天体光谱分类可用图1 2 来表示。 图1 - 2 天体光谱的物理分类【1 0 1 1 4 研究现状和本文组织结构 国际上，当前关于光谱的自动识别、分类问题，天文学家做的比较多的是恒 星光谱的分类识别【1 3 1 引，目前国际上应用在恒星光谱分类中的方法主要有( 1 ) 有代表性的a u t o c l a s s 。这是一个基于贝叶斯理论的分类方法。它采用非监督学 习算法。( 2 ) k u r t z 博士论文【3 】，应用交叉相关和主分量分析方法，将m k 分类 方法应用到低分辨率光谱( 11 4n m ) 。在他的论文中，首先采用主分量分析法构 造模板，然后与样本进行交叉相关。他的实验中只包括了光谱范围b 0 到m 2 的 数据，而且对光度级的分类结果不好。( 3 ) g u l a t i 等人采用两层b p 网络用神 经网络方法作恒星光谱的分类工作【2 1 ，但由于自由变量太多，如何避免过度学 习是一个有待解决的问题，后来还用多层反馈网络( m b p n ) 将包含1 5 8 条恒星 5 山东_ 大学硕十学何论文 ! i | 一, i l l ，i l l l l l l i ! l l l l , l l i i i l l l l l !i l l , , , i , , ! , !i ! 光谱的数据集分成5 5 个类型，分类精度为2 个光谱子型，光度型的正确率为6 4 【1 9 1 。此辨，文献将多层感知神经网络和p c a 方法用于m k 的二元分类，还 研究了p c a 对于恒星光谱的压缩。 圜际上类星体研究方面，文献f 2 1 】将s d s s 中的1 6 ，7 0 7 个q s o 蓝移到静止波 段，用p c a 分析，得到了其前4 条特征光谱，并讨论了它们的天文物理意义； 指出q s o 的光谱分类可国蓠两条特征光谱来完成。文章还提出类星体的红移和 光度与特征光谱系数是相关的。 国内研究方面f 4 】，吴永东采用结合数学形态滤波器的证据累积方法，周虹 采用结合神经网络的一维h o u g h 方法，黄凌云采用结合p c a 的二维h o u g h 变换 方法和神经网络技术，酃晓波利用伪三焦法，赵梅芳稠角自适应基神经网络瞄l ， 对类星体的红移自动测量和分类问题进行了研究；薛剑桥采用自适应神经网络 ( s o f m ) 的方法和邱波采用粗集盘动提取规则的方法对恒星的光谱型自动分类 问题进行了研究，许鑫在【2 1 j 中提出了基于核技巧的光谱分类技术。李乡儒重点研 究了f i s h e r 线性判别分桥和相关内量机( 科m ) 有监督特堑提取方法及其在星系 光谱分类中的应用【2 2 l 。此外罗阿理采用小波技术对滤波和提取连续谱的问题进行 了研究1 2 】。这些都是对正在进行的自动识别和分类系统有重要的参考价值。 本文剩下内容由以下几章构成： 第二章：分布式数据挖掘技术。介缨了数据挖掘技术的概念和常用于天体分 类的技术方法，以及分布式数据挖掘的概念； 第三章：分布式并行挖掘系统调度策略设计。对天文光谱数据的分稚式特点 提出了可有效平衡负荷的调度策略。 第四章：分布式决策树分类算法及改进。对算法性麓进行了分折，并提出几 个改进的策略； 第五章：决策树分类实例； 第六章：总结以及以后的工作展望。 6 山东大学硕十学位论文 2 1 引言 第2 章分布式数据挖掘技术 在数据化、信息化的今天，数据挖掘应运而生并成为一种新型学科。数据挖 掘技术已经在许多领域得到了广泛的应用。其中，利用数据挖掘技术可以实现数 据的分类，聚类，关联规则发现，时间和空间序列分析，孤立点检测等目标和要 求。 因此，将光谱数据的高维性和数据挖掘技术结合起来开发相应的分类算法和 规则，就成为一项重要的研究科题。在天文上，就是从海量数据中发现稀有的 天体或现象，或者发现以前未知种类的天体或新天文现象。不管天体是已知的或 未知的，数据被划分成各种不同类型的天体时，将遇到自动分类或聚类分析的问 题。 本章首先介绍了高维数据挖掘的概念、挖掘过程步骤等，然后着重介绍了用 于数据分类的分类器的特性及相应构造方法。 2 2 数据挖掘技术 2 2 1 概念 数据挖掘( d a t am i n i n g ，d m ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程【。 确切地说，数据挖掘( d m ) ，又称数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) ，是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡 的及有潜在应用价值的信息或模式，它是数据库研究中的一个很有应用价值的新 领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。 数据挖掘其实是知识发现的核心部分，而知识发现是在积累了大量数据后，从中 识别出有效的、新颖的、潜在的、有用的及最终可以理解的知识，人们利用这些 知识改进工作，提高效率和效益。数据挖掘是信息发展到一定程度的必然产物， 7 山东大学硕十学位论文 ! i | i i , , ! , i l l l l l l1 1 1 | i l l l ! l 是利用积累数据的一个高级阶段。用数据库管理系统来存储数据，用机器学习的 方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知 识发现( k d d ) 的产生。数据挖掘使数据库技术进入了一个更高级的阶段，它 不仅能对过去的数据进行查询和遍历，并且能够找如过去数据之间的潜在联系， 从而促进信息的传递。 在数据挖掘技术的众多应用领域中，经常会碰到些对象，它们可能有几十、 几百或成千上万个属性。可以将这些对象表示成高维属性空间中的点或向量，这 样就把客观世界中的对象集用高维数据的集合来表示。对这种数据进行挖掘就是 高维数据挖掘f 驯。由于这些特点，方面随着维数的升高，索引结构的修剪效率 迅速下降，当维数增加到一定时候时，采用索萼| 结构还不如顺序扫描；另一方面， 在高维空间中由于查询点到其最近邻和最远邻在很多情况下几乎是等距离的，最 近邻的概念常常失去意义f 2 4 1 。 光谱数据的维数通常是比较高的，从几百到几予维。从天体光谱中抽取数据 点，这几千个数据点就撼述了一条光谱。将每一个数据点看络是一个维度，光谱 数据的自动分类必须要做的就是降维。 2 2 2 数据挖掘的步骤 数掘挖掘过程的步骤和内容如下嘲： 1 确定挖掘对象 清瞬地定义出问题，认清数据挖掘的霹的是数据挖掘的重要一步。挖掘的最 后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘 剡带有盲墨性，是不会成功的。 2 数据准备 ( 1 ) 数据的选择 搜索所有与挖掘对象有关的内部和外部数据信息，并从中选择一个数据集或 在多数据集的子集上聚焦，挑出适用于数据挖掘应用的数据。 ( 2 ) 数据的预处理 去除噪声或无关数据，去除空白数据域，考虑时间顺序和数据交化等。研究 数据的质量，为进一步的分析做准备，并确定将要进行的挖掘操作的类型。 3 山东大学硕十学何论文 曼曼曼曼鼍舅m mmmmm i 曼曼皇曼曼璺曼曼曼曼曼曼曼舅! 曼曼曼曼曼曼曼曼曼! 皇曼皇曼曼曼曼蔓曼曼曼舅曼曼鼍曼曼詈皇曼曼 ( 3 ) 数据的转换 找到数据的特征表示，用维变换或转换方法减少有效变量的数目或找到数据 的不变式。将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的。 建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对所得到的经过转换的数据进行挖掘。用k d d 过程中的准则，选择某个特 定数据挖掘算法( 如汇总、分类、回归、聚类等) 用于搜索数据中的模式。除了 完善从选择合适的挖掘算法外，其余一切工作都能自动地完成。然后搜索或产生 一个特定的感兴趣的模式或一个特定的数据集。 4 结果解释和评估 解释并评估结果。解释某个发现的模式，去掉多余的不切题意的模式，转换 某个有用的模式，以使用户明白。其使用的分析方法一般应由数据挖掘操作而定， 通常会用到可视化技术。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去，获得这些知识的 作用或证明这些知识。用预先、可信的知识检查和解决知识中可能的矛盾。 2 2 3 数据挖掘系统 典型的数据挖掘系统的体系构成如图2 1 。其中，数据库、数据仓库或者是 其他一些信息存储媒介为数据挖掘的工作对象；服务器主要是响应数据挖掘引擎 的请求，提取相应的数据；领域知识库主要用来指导挖掘的过程，以及用来评价 挖掘出来的候选模式；数据挖掘引擎是整个系统的核心部分，可以由以下模块组 成：分类模块、关联规则模块、聚类分析模块、时序模块和异常分析模块等；模式 评价模块主要是根据一定的度量标准来与数据挖掘模块交互，以使得数据挖掘 向着我们感兴趣的方向进行，往往越是高效的数据挖掘系统这种交互影响的程度 越高：图形用户界面主要是为方便用户与数据挖掘系统的交互：由用户提出挖掘任 务、指定重要的挖掘参数以及由当前返回的结果指导进行更进一步的挖掘工作。 9 l l j 东大学硕十学位论文 曼曼! 曼曼戮! l i i i i i l l r i _ i i i i h i i i i 曼i 曼皇曼! 曼嬲囊寰 图2 - 1 一般数攥挖撼系统 从上述关于数据挖掘系统的讨论来看，数据挖掘所有功能的完全实现决非一 件简单的事情，霾意市场上出现的很多数据挖掘系统并不是严格意义上的这 类系统。有的系统不能处理大数据量，只能称为一个机器学习系统、或者一个统 计分析王具、或个实验性系统原型等；同样，有的系统仅能执行一些数据或信 息检索任务，包括执行一些求和运算、或推导型查询问答等，也只能被称为信息 检索系统或者推导型数据库系统。 2 3 数据挖掘分类方法 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务分，可 分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依 赖关系或依赖模型发现、异常和趋势发现等等；根据挖掘对象分，有关系数据库、 面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质 数据库、遗产数据库以及环球网w e b ；根据挖掘方法分，可分为：机器学习方 法、统计方法、神经网络方法和数据库方法。机器学习中，可细分为：归纳学习 方法( 决策树、规剐归纳等) 、基于范倒学习、遗传算法等。统计方法中，可细分 为：回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、费歇尔判别、非参 数判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索性分析( 主分量分毒蓐法、相 关分析法等) 等。神经网络方法中，可细分为：前向神经网络( b p 算法等) 、自组 织神经网络( 自组织特征映射、竞争学习等) 瞄l 等。数据库方法主要是多维数据分 析或联机分析处理( o l a p ) 方法，另外还有面向属性的归纳方法。 通常天文学中使耀麴数据挖掇技术有： i o i l i 东大学硕七学位论文 ( 1 ) 监督的分类方法，如决策树或人工神经网络( 舢州) 。这种方法通常 用于区分恒星与星系【2 7 , 2 8 】，在多参数空间中寻找具有预测特性的已知类型天体也 可以用这种方法( 如寻找高红移类星体) 。 ( 2 ) 非监督的分类方法四 3 1 】，如e m ( e x p e c t a t i o nm a x i m i z a t i o n ) ， m c c v ( m o n t ec a r l oc r o s sv a l i d a t i o n ) 。这些方法己用于确定数字巡天得到的星团 数目，并将成为虚拟天文台分类工具的重要组成部分。 ( 3 ) 主分量分析方法( p c a ) 3 2 , 3 3 】，具有非监督性，对数据进行预处理， 去掉一些无关或不重要的参量，即降维。主要用于恒星、星系和类星体的光谱分 类，星系的形态分类。 ( 4 ) 其它方法，如最大似然法、非参数技术、信息瓶颈、小波、广义h o u g h 变换、贝叶斯方法、独立分量分析方法( i c a ) 、最近邻规则、最小距离方法等。 2 4 分类算法与分类器构造方法 2 4 1 分类算法 分类是数据挖掘中的一个重要课题，可用于预测和决策。分类算法亦是数据 挖掘算法中很重要的一种，主要分类算法有决策树( d e c i s i o nt r e e ) 算法。 分类问题可描述为：输入数据，或称训练集( t r a i n i n g s e t ) ，是一条条的数据库 记录( r e c o r d ) 组成的。每一条记录包含若干条属性( a t t r i b u t e ) ，组成一个特征向量， 训练集的每条记录还有一个特定的类标签( c l a s sl a b e l ) 与之对应，该类标签是系 统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量： ( v l ，v 2 ，v n ；) 。在这里v i 表示字段值，c 表示类别【l 2 5 。 分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每 一个类找到一种准确的描述或者模型。由此生成的类描述用来对未来的测试数据 进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这 些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一 个类有更好的理解。或者说我们获得了对这个类的知识。 【i i 东大学硕十学能论文 2 4 2 分类器 分类在数据挖掘中是一顼非鬻重要的任务，蠢前在商业上应用最多。分类的 目的是学会一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中 的数据顼映射到给定类剃中的某个。分类和回弱都可用于预测。预测的目的是 从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进 行预测。和回归方法不网的是，分类的输出是离散的类别值，而回归的输出则是 连续数值。 要构造分类器，需要有一个训练样本数据集俸为输入。训练集由一组数据库 记录或元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向 量，此外，调练样本还有一个类别标记。一个具体样本的形式可力：( v l ，v 2 ， v n ；c ) ；其中v i 表示字段值，c 表示类别。 不同的分类器有不同的特点。有三种分类器评价或比较尺度f l ：。( 1 ) 预测 准确度。( 2 ) 计算复杂度。( 3 ) 模型描述的简洁度。预测准确度是用得最多的 一种比较尺度，特别是对于预测型分类任务，目前公认的方法是l o 番分层交叉 验证法。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操 作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环 节。对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的 分类器构造法就更有用，而神经网络方法产生的结果就难以理解。 其中，训练集是构造分类器的基础，它是包含些属性数据集，包含类别属 性。类别属性值的类型一般是离散的，类别数目不宜过多，文中的类别主要用于 区分类星体与晚行星鼹类，以及些孤立点。类别属性值的数目越少，构造如来 的分类器的错误率一般会越低。 从训练集中自动地构造出分类器的算法叫生成器( i n d u c e r ) 。在生成分类器 后，首先评估该分类器的准确率。如果模型的准确率可以接受，就可以利用它来 对数据集中不包含类标签属性的记录进行分类。 另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有 的有缺值，有的分布稀疏，有的字段或属性闻相关性强，有的属性是离散的面有 的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数 据。 1 2 山东大学硕+ 学位论文 2 4 3 构造方法 分类在数据挖掘中是一项非常重要的任务，分类的目的是根据数据集的特点 构建一个分类器，该分类器能把数据库中的数据项映射到给定类别中的某一个， 从而可以用于预测。实现分类的方法有很多，分类模型的构造方法有神经网络方 法、统计学方法、机器学习方法、决策树方法【3 1 等。下面分别对决策树方法及统 计方法中的p c a 方法做了介绍。 2 4 3 1 p c a 方法 主分量分析方法( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 是一个简化某类特 殊数据的工具，是分析用较少数量的特征对样本进行描述以达到降低特征空间维 数的方法。设想我们有1 1 个物体，且每个物体有p 个参量。例如有n 个参加会议 的计算机专家，我们知道p 种情况：他们的身高、体重、发表的论文数、飞的路 程和他们的汽车耗油量。这p 个参数是怎样相关的呢。 处理这种问题的传统的方法是画出每两个参量图以寻找相关性。然而当参数 增加时，再这样做显然较复杂，我们很容易陷入参量网的困境中。每一个参数或 多或少地与其它参数的混合相关。人们大脑可以轻松自如地处理两三个参数。通 过分别画出不同参量对其他参量的图，我们可以了解5 7 个变量。若超出这个范 围，恐怕我们的大脑就要需要帮助了。 p c a 方法广泛应用于信号处理、统计学和神经网络计算，在文献中又称k l 变换( k a r h u n e n - l o e v et r a n s f o r m ) 或h o t e l l i n g 变换( h o t e l l i n gt r a n s f o r m ) ，属于多 变量分析方法的一种，正好适合处理这样的问题：当你知道许多事物的多种情况， 又想知道这些情况是否彼此相关。主分量分析方法可以找出彼此相关的参量，并 把相关的量组合成一个新量，这样大大减小了参量数，同时又不至于损失信息。 p c a 法中用到的数学方法是方差矩阵的特征值和特征向量分析。因此矩阵 的特征值对应的特征向量之问是独立的、相互垂直的，矩阵最大特征值对应的特 征向量就是矩阵的第一个主分量并以此类推，因此可以利用这些主分量对原数据 进行分析，从而降低原始数据的维数。其数学模型描述如下： 设样本资料阵为： 1 3 l i j 东大学硕十学位论文 皇曼! 曼曼燃蔓曼曼曼i i i i i i i i i i i i笪 i , i i i i i i i i i 一i i i i _ 麓 综合指标为， x = t j ，茗：，j 尹，_ 。x 硝l lg-x。l犁p e 2 1 ，- - - 9 )x = ( j l ，茗2 ，j 尹) =l( 2 ) ：一硝一犁j ( 2 - 2 ) 只= 口l j x i + 口删x 2 + + a x po = l ，删) ( 2 3 ) 并取 口l j2+口2=1(2-4) 要求( 1 曩，t 不相关。( 2 ) 曩是x t 戈，的线性函数中方差最大的，依 此类推。 主成分的见何意义： 设有n 个样晶，每个样品有两个观测变量五，x 2 ，二维平面的散点图。n 个 样本点，无论沿着五轴方向还是x