（计算机应用技术专业论文）高维数据挖掘在天体粗分类中的应用.pdf

山东大学硕士学位论文 摘要 天体光谱蕴含着天体重要的物理信息，通过光谱的研究，人们可以定性或定 量地测定天体的化学成分，直接或者间接地确定天体的表面温度，光度，直径， 质量，研究天体的视向运动和自转。因此，光谱分析在天体和物理学中占有重要 地位。l a m o s t 望远镜建成以后，每个观测夜都将产生上万条光谱。如何处理这 些海量光谱从而及时获得所需的科学信息成为一项重要的议题。 数据挖掘技术正在众多领域中得到广泛的应用，它是从大量的、不完全的、 有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但 又是潜在有用的信息和知识的过程。运用数据挖掘技术可以实现相关性预测，分 类，聚类，孤立点发现，时间序列分析等等功能，许多针对高维数据的挖掘算法 也正成为研究的热点，光谱数据本身就是高维的，因此，面对海量的光谱数据， 数据挖掘技术正好可以为解决光谱数据的分类，参数测量等工作提供很好的支 持。 按照l a m o s t 的科学目标，光谱数据的分类可以分为粗分类和细分类两大部 分。其中粗分类是指首先将天体光谱分成正常天体和发射线天体，然后将正常天 体分成正常星系和恒星，发射线天体分成星暴星系和活动星系核。 本论文的主要工作针对天体粗分类展开，主要工作包括： 1 ) 研究了覆盖算法，总结该算法的特点并提出相应的改进。覆盖算法主要由 下述两步构成：首先将分类问题转换成一个集覆盖问题，然后通过求解最小支撑 覆盖集来完成分类。其中，论文中讨论的是基于类间最大距离算法。该算法是一 种构造性算法，不涉及任何迭代计算，算法时间性能只取决于覆盖点的个数。论 文指出根据覆盖算法的原理，随着覆盖半径的增大，将增加支撑覆盖集的支撑覆 盖点个数；而当覆盖半径逐渐减小时，支撑覆盖集的支撑覆盖点个数将递增。覆 盖半径的选择应根据实际情况灵活设置，多次试验取得最优值，从而使算法在精 确度和速度上都取得较好实际效果。其次提出计算样本点之间的距离时应该采用 对各特征向量加权的方法计算，这样进一步提高分类的准确性。 2 ) 按照数据挖掘的一般流程，对晚型星和类星体两类星体的分类构建了挖掘 模型，采用图示的方式，抓取两类不同星体的特征，用规则对两类星体较好的进 i i i 东大学硕十学位论文 行了分类。分类算法简洁迅速。在系统实现过程中，开发平台采用了微软新推 的n e t 架构，开发语言是面向n e t 的开发语言c 扰系统主要包含预处理、谱线 图示，分类训练几个模块。 关键词：天体光谱，粗分类，覆盖算法，高维数据 i i 山东大学硕士学位论文 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 nq 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 , m a s so fc e l e s t i a lb o d i e sa n dd or e s e a r c ho n r 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 la n a l y s i sp l a y s a ni 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 el 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 e c 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 lw i t ht 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 n u 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 ni 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 e p 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 i n td 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 t ，m a n ym i n i n ga l g o r i t h m sw i t hh 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 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 p a r a m e t e rm e a s u r e m e n t a c c o r d i n gt ot h eo b j e c to fl a m o s t t h ec l a s s i f i c a t i o no fs p e c t r ad a t ac a l lb e d i v i d e di n t ot w o p a r t s ：r o u g hc l a s s i f i c a t i o na n dc a r e f u lc l a s s i f i c a t i o n t h ef i r s ts t e po f r o u g hc l a s s i f i c a t i o ni st od i v i d es p e c t r ao fc e l e s t i a lb o d i e si n t on o r m a lo b j e c t sa n d e m i s s i o n l i n eo b j e c t s a n dt h e nn o r m a lo b j e c t sa r ed i v i d e di n t on o r m a lg a l a x i e sa n d s t a r s ，w h i l ee m i s s i o n l i n eo b j e c t sa r ed i v i d e di n t os t a r b u r s tg a l a x i e sa n da c t i v e g a l a c t i cn u c l e i t h em a i nj o b so ft h i st h e s i sa i ma tr o u g hc 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 d m a i np o i n t sa r es u m m a r i z e da sf o l l o w s ： 1 ) a f t e rd o i n gr e s e a r c ho nc o v e r i n ga l g o r i t h m ，s u m m a r i z et h ec h a r a c t e r so ft h e a l g o r i t h ma n dp u tu pc o r r e s p o n d i n gi m p r o v e m e n t s t h em e t h o di sc o m p o s e do ft h ef o l l o w i n gt w os t e p s ：t h ec l a s s i f i c a t i o np r o b l e mi s f i r s tc o n v e r t e di n t oas e tc o v e t i n gp r o b l e m ，a n dt h e nt h ec l a s s i f i c a t i o ni sc a r r i e do u tb y i i i 山东大学硕士学位论文 s o l v i n gt h es u p p o r tc o v e r i n gs e t s t h ea l g o r i t h md i s c u s s e di nt h i st h e s i si sb a s e do n t h em a x i m a ld i s t a n c eb e t w e e nc l u s t e r s i nt h ec o v e t i n ga l g o r i t h m ，i t e r a t i v ec a l c u l a t i o n i sn o tr e q u i r e ds i n c ei ti sas t r u c t u r a la l g o r i t h m ，a n dt h ed i s c r i m i n a n tf u n c t i o nd e p e n d s o n l yo nt h es u p p o r tp o i n t so ft h ec o v e r i n gs e t s t h et h e s i sp o i n t so u tt h a ta c c o r d i n gt ot h et h e o r yo fc o v e t i n ga l g o r i t h m s ，t h e n u m b e ro fc o v e r i n gd a t ap o i n t sw i l li n c r e a s ew i t ht h ed e c r e a s eo fc o v e r i n gr a d i u sa n d t h en u m b e ro fc o v e d n gd a t ap o i n t sw i l ld e c r e a s ew i t ht h ei n c r e a s eo fc o v e r i n gr a d i u s t h ec o v e r i n gr a d i u ss h o u l db es e tf l e x i b l ea n do b t a i nt h eo p t i m i z e dv a l u ev i ar e p e a t e d e x p e r i m e n t s t h u st h ea l g o r i t h mc a ng e te x c e l l e n tr e s u l t sb o t ho np r e c i s i o na n d p r o c e s s i n gs p e e d t h et h e s i sa l s op o i n t so u tt h a tt h er e s u l t sw i l lb eb e t t e ri ft h e d i s t a n c eb e t w e e nd i f f e r e n td a t ap o i n t si sc a l c u l a t e du s i n gw e i g h t e de i g e n v e c t o r 2 ) b a s e do nt h ec h a r a c t e r i s t i co fh i g h d i m e n s i o n a ld a t aa n dt h eg e n e r a lf l o wo f d a t am i n i n g , t h es t u d yb u i l tas t e l l a rs p e c t r ac l a s s i f i c a t i o nm o d e li nh i g h d i m e n s i o n a l d a t am i n i n ga n da n a l y z e dt h es p e c t r af e a t u r e so fq u a s a ra n dl a t e t y p es t a rw i t ht h e m o d e l t h e s et w oc a t e g o r i e so fs t a r - s p e c t r u ma r ec l a s s i f i e di na p p r o a c ho fs t a t i s t i c m e t h o d t h ep r o p o s e dm e t h o di ss h o w nb ye x t e n s i v ee x p e r i m e n t st ob ep r o m p ta n d h i g he f f i c i e n c y i nt h ec o u p eo fs y s t e md e v e l o p m e n t d e v e l o pf l a ti n t r o d u c e s n e t s t r u c t u r e a n dd e s i g nl a n g u a g ei sc 撑t h es y s t e mm a i nc o n t a i n ss u c hm o d u l e s ： p r e p r o c e s s i n g , l i n ep r e s e n t a t i o na n dc l a s s i f i c a t i o nt r a i n i n ge t c k e yw o r d s ：d a t am i n i n g ；h i g h d i m e n s i o n a l ；c l a s s i f i c a t i o n ；s p e c t r u m 东大学硕+ 学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：姻：至：纽日期：! 盟：兰! 研 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授扭：l 东大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：幽：鱼型 导师签名：么墨丝墨日期： l l j 东大学硕士学位论文 1 1 引言 第1 章绪论 几千年来，人类对天体和宇宙的研究一直没有停止，其研究水准显示着个 国家和民族在科技发展前沿中的位置，并对一个民族的宇宙观、自然观有着深刻 的影响。对天体的光谱分析技术的使用和发展，促进了现代天体物理学和其他自 然学科的巨大进步。 天体光谱是天体电磁辐射按照波长的有序排列，蕴含着天体重要的物理信 息。天文学家通过分析天体光谱信息，不仅可以研究宇宙中物质的分布特征，还 可以研究天体的形成和随时间演化等一系列科学重大问题。 天体光谱信号的物理分类是研究光谱的重要一环。面对浩瀚的宇宙，将数以 亿计的天体进行恰当分类是进行深入研究工作的前提。天体的分类有不同的标 准，这里论文中的分类指的是光谱物理分类。 其中，本文的天体光谱粗分类主要是指：首先将天体光谱分成正常天体和发 射线天体，然后将正常天体分成正常星系和恒星，发射线天体分成星暴星系和活 动星系核。 正在建造的国家重大工程l a m o s t 项目望远镜( 大天区面积多目标光 纤光谱望远镜) 将产生大量的光谱数据。面对这些海量数据的归类，人工手动 处理已远远满足不了需求，开发光谱的自动处理、测量和分类算法和系统就 摆到了我们面前。本论文研究正是在l a m o s t 的项目背景下展开。 1 2i 。a m o s t 项目 1 2 1l a m o s t 简介 大天区面积多目标光纤光谱天文望远镜( l a r g es k ya r e am u l t i o b j e c t f i b e rs 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 度n + 9 0 度。相应于5 度视场、直径为1 7 5 米的焦面上放 置4 0 0 0 根光纤。采用并行可控的光纤定位技术，可在较短的时间里将光纤按星 表位置精确定位，并提供了光纤位置微调的可能。这将在光纤定位技术上突破目 前世界上同时定位6 4 0 根光纤的技术。通过这样的构思和设计，解决了大视场 的施密特望远镜透射改正板很难做大，大口径反射望远镜视场较小的问题，使 l a m o s t 成为大口径兼大视场光学望远镜的世界之最。由于它的4 米口径，在1 5 小时曝光时间内以1 纳米的光谱分辨率可以观测到2 0 5 等的暗弱天体的光谱； 由于它相应于5 度视场的1 7 5 米焦面上可以放置数千根光纤，连接到多台光谱 仪上，同时获得4 0 0 0 个天体的光谱，成为世界上光谱获取率最高的望远镜。 l a m o s t 项目完成后将有大量的数据产出，在观测期内将达到1 0 “7 数量级 的光谱数据。这样一个庞大的天文数据，利用人工方法来处理光谱分类显然不能 满足实际的需求。目前，国际上常用的天文软件包有m i d a s ，f i g a r o ，i r a f 等， 它们都是通过人机交互的方式来完成光谱处理的。虽然利用人机交互的方式处理 j 光谱时可以融入天文学家的专家知识，并根据天文学家的经验做出判断和分析， 但面对像l a m o s t 这样大型的巡天计划的海量数据，如果还采用人工交互方式， 靠天文工作者逐条分析光谱，已经远远满足不了需求。 1 2 2l a m o s t 的意义和科学目标 l a m o s t 工程的实施具有重要科学意义，主要表现在如下三个方面： 1 ) l a m o s t 在望远镜发展中具有重要的地位。l a m o s t 望远镜采用了并行可控的 光纤定位技术。由于它的4 米口径，在1 5 小时曝光时间内以1 纳米的光谱 分辨率可以观测到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 数量级的恒星光谱，以及约加6 数 量级的类星体光谱，这是个非常庞大的天文数据库。 2 山东大学硕士学位论文 l a m o s t 的三大核心课题是：星系红移巡天与宇宙大尺度结构，恒星物理与 银河系结构，多波段天体的光学研究。 1 ) l a m o s t 对上千万个星系，类星体等河外天体光谱进行光谱巡天，将在诸 如星系，类星体和宇宙大尺度结构等河外天体物理和宇宙学问题的研究 上做出重大贡献。 2 ) l a m o s t 在诸如恒星，星族和银河系结构，运动学及化学等河内天体物理 研究上做出重大贡献。 3 ) 结合红外，射电，x 射线等巡天的大量天体的光谱观测将在各类天体多 波段交叉征认上做出重大贡献。 1 2 3l a m o s t 光谱处理综述 整个天体光谱自动处理过程可以用图卜l 来表示 1 ) 。这里主要讲述了光谱 数据的获取和预处理过程。首先介绍了获取一维光谱数据的步骤，然后介绍了光 谱数据的常用数据保存格式f i t s 以及光谱分类前的相应处理，包括连续谱归一 化、谱线提取和去噪等。 巨习刮至二斗r - - 一 i 自动识别i l i 自动测量i 图1 - 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 ) 从二维光谱中最佳地抽取一维谱 3 l i j 东大学硕士学位论文 7 ) 波长定标及减天光 8 ) 天光改j 下 9 ) 流量定标 f i t s 是国际天文学会1 9 8 2 年确定的世界各天文台之间用于数据传输，交换 的统一标准格式。它所记录的数据对象主要是一维，二维乃至多维数据，尤其在 图像处理，储存及传输方面充当着极为重要的脚色。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 千维以上。 在光谱处理前首先要进行数据格式的转换，即把f i t s 文件格式转换成后续 处理需要的各种文件格式，比如a s c i i 码格式等 1 3 。同时把原始的单个光谱数 据按组形成以数据矩阵存储的文件。 天体光谱的识别分类基于不同信息 8 ，有的基于整条光谱( 连续谱和谱线) ， 有的基于谱线信息，因此不同的光谱识别器需要进行不同的光谱处理。 连续谱归一化的目的是使得相同谱线的表现形式一致。其步骤包括：提取连 续谱，然后用原来的光谱去除连续谱，使连续谱归化。在连续谱提取中，用多 项式逼近连续谱是常用的方法之一；同时，还有许多别的方法，如形态滤波器 1 4 ，中值滤波器 1 3 ，小波变换 4 等。 谱线提取是连续谱归一化和去噪的副产品。这时的光谱又称为谱线光谱。 噪声对于弱源来说主要是信号噪声，当然还包括天光背景、探测热器噪声以 及未知源等影响，其主要表现形式是随机白噪声，也有波长不固定的干扰噪声。 较好的滤波方法有形态滤波器 1 6 ，中值滤波器 1 3 ，高斯滤波器 1 5 ，小波变 换 4 等。 经过上述处理后，再利用数据挖掘技术进行光谱数据的特征提取和选择，从 而达到自动识别，自动分类和自动测量的目的。 4 i j i 东大学硕十学位论文 1 3 天体粗分类 天体的分类与天体辐射有着直接的关系。天体的分类也可以大致分为两个阶 段：天体粗分类和天体的细分类。 1 3 1 天体辐射与天体分类 天体光谱自动识别的研究离不开天文学知识，光谱对于天文学家而言，它们 最显著的特征是谱线。天体中的原子、分子等在不同能级之问跃迁就会吸收或发 射谱线，不同的原子和分子有其特定的谱线。天体的辐射特性可以用不同波长处 强度的分布来描述。连续辐射指的是不聚集在任何特定波长处的辐射。类星体连 续谱的一种可能的解释是同步加速机制；而恒星的连续谱是由恒星的有效温度、 表面重力加速度和化学丰度决定的，热星连续谱的形状是由中性氢原子的束缚一 自由吸收决定的，冷星的连续谱取决于负氢离子的作用。原子在吸收或发出辐射 时，只吸收或辐射某一特定波长的特定能量的光子，光子集中在某个特定波长的 辐射叫发射线；如果在某一特定波长处辐射少了，就是天体光谱里出现了吸收线。 不同类型的辐射来自完全不同的天体。 1 3 2 天体光谱分类 宇宙中存在着各种各样的天体，天文上首先以银河系为界线将天体分为河内 源和河外源。其中河内源主要是恒星和星际介质( i s m ) ，而河外源主要是指各种 星系。下面首先介绍有关天体分类的几个重要概念。 正常天体主要包括正常恒星和正常星系；而发射线天体主要包括活动星系， 活动星系核。正常恒星的光谱是由连续光谱和其上所叠加的吸收线组成，分类序 列按有效温度从高到底排序，主要分为七个光谱型：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 来表示。 【j j 东大学硕士学位论文 图1 - 2 天体光谱的物理分类【6 】 本文的天体光谱粗分类主要是指：首先将天体光谱分成正常天体( n g s ) 和发 射线天体( a g s ) ，这属于测量红移的前奏。然后将正常天体分成正常星系和恒星， 发射线天体分成星暴星系和活动星系核。其分类过程可以用图卜3 来表示 1 。 图1 - 3 粗分类器设计 1 4 研究现状和本文组织结构 现在全球已有近二十台4 米级望远镜和十多台8 米级望远镜，天体光谱高分 辨率观测的能力有了很大提高。但是对于在大天区范围内获得大规模的光谱，仅 6 l i i 东大学硕士学位论文 靠增加望远镜数量不能真正解决问题。解决光谱测量的低效率，首先需要能够同 时测量多个天文目标光谱的技术。“多目标光纤光谱仪技术”为大规模天文测量 创造了技术条件。 国际上，当前关于光谱的自动识别、分类问题，天文学家做的比较多的是恒 星光谱的分类识别 1 2 ，2 2 2 7 ，目前国际上应用在恒星光谱分类中的方法主要 有1 ) 有代表性的a u t o c l a s s 。这是一个基于贝叶斯理论的分类方法。它采用非监 督学习算法。2 ) k u r t z 博士论文 1 ，应用交叉相关和主分量分析方法，将m k 分类方法应用到低分辨率光谱( 1 1 4r i m ) 。在他的论文中，首先采用主分量分析法 构造模板，然后与样本进行交叉相关。他的实验中只包括了光谱范围b o 到m 2 的 数据，而且对光度级的分类结果不好。3 ) g u l a t i 等人采用两层b p 网络用神经网 络方法作恒星光谱的分类工作 4 ，但由于自由变量太多，如何避免过度学习是 一个有待解决的问题，后来还用多层反馈网络( m b p n ) 将包含1 5 8 条恒星光谱的 数据集分成5 5 个类型，分类精度为2 个光谱子型，光度型的正确率为6 4 2 8 。 此外，文献 2 9 将多层感知神经网络和p c a 方法用于m k 的二元分类，还研究了 p c a 对于恒星光谱的压缩。 国际上类星体研究方面，文献 3 0 将s d s s 中的1 6 ，7 0 7 个q s o 蓝移到静止波 段，用p c a 分析，得到了其前4 条特征光谱，并讨论了它们的天文物理意义；指 出q s o 的光谱分类可由前两条特征光谱来完成。文章还提出类星体的红移和光度 与特征光谱系数是相关的。文献 3 1 直接从谱线出发，找到了基于线强比的判据， 对于星暴星系和窄线的a g n 进行分类。 国内研究方面 8 ，吴永东采用结合数学形态滤波器的证据累积方法，周虹 采用结合神经网络的一维h o u g h 方法，黄凌云采用结合p c a 的二维h o u g h 变换方 法和神经网络技术，邱晓波利用伪三角法，赵梅芳利用自适应基神经网络 2 0 ， 对类星体的红移自动测量和分类问题进行了研究；薛剑桥采用自适应神经网络 ( s o f m ) 的方法和邱波采用粗集自动提取规财的方法对恒星的光谱型自动分类问 题进行了研究，许鑫在 2 1 1 中提出了基于核技巧的光谱分类技术。李乡儒重点研 究了f i s h e r 线性判别分析和相关向量机( r v m ) 有监督特征提取方法及其 在星系光谱分类中的应用 2 2 。此外罗阿理采用小波技术对滤波和提取连续 谱的问题进行了研究 4 。这些都是对正在进行的自动识别和分类系统有重要的 7 l l i 东大学硕七学位论文 参考价值。 本文剩下内容由以下几章构成： 第二章：高维数据挖掘技术。介绍了数据挖掘技术的概念和常用于天体分类 的技术方法； 第三章：分类判别的覆盖算法分析及其改进。对覆盖算法性能进行了分析， 并提出几个改进的地方； 第四章：一个类星体和晚型星分类的实例： 第五章：总结。 i i j 东大学硕士学位论文 第二章高维数据挖掘技术 2 1 引言 在数据化、信息化的今天，数据挖掘应运而生并成为一种新型学科。数据挖 掘技术已经在许多领域得到了广泛的应用。其中，利用数据挖掘技术可以实现数 据的分类，聚类，关联规则发现，时间和空间序列分析，孤立点检测等目标和要 求。 因此，将光谱数据的高维性和数据挖掘技术结合起来开发相应的分类算法和 规则，就成为一项重要的研究科题。在天文上，就是从海量数据中发现稀有的天 体或现象，或者发现以前未知种类的天体或新天文现象。不管天体是已知的或未 知的，数据被划分成各种不同类型的天体时，将遇到自动分类或聚类分析的问题。 本章首先介绍了高维数据挖掘的概念、挖掘过程步骤等，然后着重介绍了用 于数据分类的分类器的特性及相应构造方法。 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 y i nd a t a b a s e ，k d d ) ，是指从大型数据库或数据仓库中提取隐含的、未知的、非 平凡的及有潜在应用价值的信息或模式，它是数据库研究中的一个很有应用价值 的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技 术。数据挖掘其实是知识发现的核心部分，而知识发现是在积累了大量数据后， 从中识别出有效的、新颖的、潜在的、有用的及最终可以理解的知识，人们利用 这些知识改进工作，提高效率和效益。数据挖掘是信息发展到一定程度的必然产 物，是利用积累数据的一个高级阶段。用数据库管理系统来存储数据，用机器学 9 山东大学硕士学位论文 习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中 的知识发现( k d d ) 的产生。数据挖掘使数据库技术进入了一个更高级的阶段， 它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联 系，从而促进信息的传递。 在数据挖掘技术的众多应用领域中，经常会碰到一些对象，它们可能有几十， 几百或成千上万个属性。可以将这些对象表示成高维属性空间中的点或向量，这 样就把客观世界中的对象集用高维数据的集合来表示。对这种数据进行挖掘就是 高维数据挖掘 2 。在高维空间中，数据点是非常稀疏的，在空区域中点的密度 可能会很高，这称之为高维数据的稀疏性和空空间现象 2 。由于这些特点，一 方面随着维数的升高，索引结构的修剪效率迅速下降，当维数增加到一定时候时， 采用索引结构还不如顺序扫描 1 0 ；另一方面，在高维空间中由于查询点到其最 近邻和最远邻在很多情况下几乎是等距离的，最近邻的概念常常失去意义 1 1 。 具体在天文上来说，光谱数据的维数通常是比较高的，从几百到几千维。从 天体光谱中抽取数据点，这几千个数据点就描述了一条光谱。将每一个数据点看 作是一个维度，光谱的数据自动分类就成为高维数据挖掘问题【1 7 】。 2 2 2 数据挖掘的步骤 数据挖掘过程的步骤和大体内容如下 5 ： ( 1 ) 确定挖掘对象 清晰地定义出问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最 后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘 则带有盲目性，是不会成功的。 ( 2 ) 数据准备 数据的选择 搜索所有与挖掘对象有关的内部和外部数据信息，并从中选择一个数据集或 在多数据集的子集上聚焦，挑出适用于数据挖掘应用的数据。 数据的预处理 去除噪声或无关数据，去除空白数据域，考虑时问顺序和数据变化等。研究 数据的质量，为进一步的分析做准备，并确定将要进行的挖掘操作的类型。 1 0 l i f 东大学硕士学位论文 数据的转换 找到数据的特征表示，用维变换或转换方法减少有效变量的数目或找到数据 的不变式。将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的。 建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 ( 3 ) 数据挖掘 对所得到的经过转换的数据进行挖掘。用k d d 过程中的准则，选择某个特 定数据挖掘算法( 如汇总、分类、回归、聚类等) 用于搜索数据中的模式。除了 完善从选择合适的挖掘算法外，其余一切工作都能自动地完成。然后搜索或产生 一个特定的感兴趣的模式或一个特定的数据集。 ( 4 ) 结果解释和评估 解释并评估结果。解释某个发现的模式，去掉多余的不切题意的模式，转换 某个有用的模式，以使用户明白。其使用的分析方法一般应由数据挖掘操作而定， 通常会用到可视化技术。 ( 5 ) 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去，获得这些知识的 作用或证明这些知识。用预先、可信的知识检查和解决知识中可能的矛盾。 2 2 3 数据挖掘的种类方法 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务分，可 分为分类或预测模型发现、数据总结、聚类? 关联规则发现、序列模式发现、依 赖关系或依赖模型发现、异常和趋势发现等等；根据挖掘对象分，有关系数据库、 面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质 数据库、遗产数据库以及环球网w e b ；根据挖掘方法分，可分为：机器学习方法、 统计方法、神经网络方法和数据库方法。机器学习中，可细分为：归纳学习方法 ( 决策树、规贝0 归纳等) 、基于范例学习、遗传算法等。统计方法中，可细分为： 回归分析( 多元回归、白回归等) 、判别分析( 贝叶斯判别、费歇尔判别、非参数 判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索性分析( 主分量分析法、相关 分析法等) 等。神经网络方法中，可细分为：前向神经网络( b p 算法等) 、自组织 神经网络( 自组织特征映射、竞争学习等) 等。数据库方法主要是多维数据分析或 山东大学硕十学位论文 联机分析处理( o l a p ) 方法，另外还有面向属性的归纳方法。 通常天文学中使用的数据挖掘技术有： 监督的分类方法，如人工神经网络( a n n ) 或决策树。这种方法通常用于 区分恒星与星系 3 0 一3 2 ，在多参数空间中寻找具有预测特性的已知类型天体也 可以用这种方法( 如寻找高红移类星体) 。 非监督的分类方法 3 4 3 7 ，如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 ) 。这些方法已用于确定数字巡天得到的星 团数目，并将成为虚拟天文台分类工具的重要组成部分。 主分量分析方法( p c a ) 3 8 4 0 ，具有非监督性，对数据进行预处理， 去掉一些无关或不重要的参量，即降维。主要用于恒星、星系和类星体的光谱分 类，星系的形态分类。 其它方法，如最大似然法、非参数技术、信息瓶颈、小波、广义h o t i g l l 变换、贝叶斯方法、独立分量分析方法( i c a ) 、最近邻规则、最小距离方法等。 2 3 分类与分类器构造方法 2 3 1 分类器 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的 目的是学会一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中 的数据项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是 从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据 进行预测。和回归方法不同的是，分类的输出是离散的类别值，而回归的输出则 是连续数值。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由组数据库 记录或元组构成，每个元组是个由有关字段( 又称属性或特征) 值组成的特征向 量，此外，训练样本还有一个类别标记。一个具体样本的形式可为：( v l ，v 2 ， v n ：c ) ：其中v i 表示字段值，c 表示类别。 不同的分类器有不同的特点。有三种分类器评价或比较尺度 7 ：l 预测准确 度：2 计算复杂度：3 模型描述的简洁度。预测准确度是用得最多的一种比较尺度， 1 i i 东大学硕士学位论文 特别是对于预测型分类任务，目前公认的方法是1 0 番分层交叉验证法。计算复 杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是臣量的 数据库，因此空间和时问的复杂度问题将是非常重要的一个环节。对于描述型的 分类任务，模型描述越简洁越受欢迎：例如，采用规则表示的分类器构造法就更 有用，而神经网络方法产生的结果就难以理解。 另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有 的有缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有 的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数 据。 2 3 2 构造方法 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。下面 几小节分别对统计方法中的p c a 方法、c l i q u e 算法和支撑向量机技术，以及 神经网络方法做了介绍。 2 3 2 1p 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 ) 是一个简化某类 特殊数据的工具，是分析用较少数量的特征对样本进行描述以达到降低特征空问 维数的方法。设想我们有n 个物体，且每个物体有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