天体光谱数据挖掘技术

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,天体光谱数据挖掘技术,2008年11月,1,一、概 述,1）,数据挖掘,2）天体光谱数据挖掘,3）课题的研究意义,二、主要研究工作,1）,基于约束FP树的天体光谱数据相关性分析,2）,基于概念格的天体光谱离群数据挖掘,2,数据挖掘,定义：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含的、未知的、潜在的有用信息和知识，为决策支持服务。,主要任务：关联规则、分类、聚类、离群数据等。,常用的方法有：关联规则、决策树、神经网络、遗传算法、粗糙集、模糊集、概念格、统计分析等。,3,天体光谱数据挖掘,我国正在建造一台大天区面积多目标光纤光谱望远镜（LAMOST），是国家重大科学工程项目，也是世界上光谱获取率最高的望远镜。,预计LAMOST所观测到的光谱数据容量将有可能达到4TB,。,急需一种新的以计算机为主的数据分析技术, 分析和识别如此庞大的海量光谱数据。,天体光谱数据处理主要内容:,预处理(去噪、归一化等),、,分类与识别,、,测量（红移等参数）,等。,4,一条Seyfert 2 光谱数据图(红移为0),天体光谱是天体电磁辐射按照波长的有序排列，蕴含着天体的重要物理信息，例如：天体的化学成份、天体的表面温度、直径、质量、光度以及天体的视向运动和自转。天文学家和天体物理学家通过分析天体光谱的信息，不仅可以研究宇宙中物质的分布特征，还可以研究天体的形成和随时间的演化等重大科学问题。,5,主要的方法,交叉相关分析与主成分分析（PCA）、人工神经网络、小波变换、贝叶斯统计、SVM等。,典型的成果,1） Autoclass，基于贝叶斯统计的一种光谱分类方法，发现了一些以前未注意的光谱类型和谱线；,2） Gulati等人采用两层BP神经网络方法，用于恒星光谱次型的分类；,3）Ellis等人采用交叉相关分析对光谱进行分类；,4）邱波等人采用基于粗糙集的方法，进行了恒星光谱的分类识别；,5）覃冬梅等人采用基于主分量分析法的二维恒星特征空间的快速光谱识别方法；,6）刘中田等人提出基于小波特征的M型星自动识别方法等。,6,课题的研究意义,由于天文界对宇宙的认识还比较有限，LAMOST巡天计划的一个重要任务是要发现一些新的、特殊类型的天体，因此，如何利用数据挖掘技术从海量天体光谱数据中发现未知的、特殊的天体及天体规律是数据挖掘值得研究和探索的新应用领域。,面向特定任务的数据挖掘是当前数据挖掘领域发展的趋势之一。以LAMOST项目为背景，对天体光谱数据挖掘技术进行了研究，其研究成果不仅具有重要的理论价值，而且可直接应用到LAMOST中，为国家重大科学工程提供技术支撑。,退回,7,引言,关联规则描述了属性之间的关联程度，也就是说有效地描述了数据集属性之间的相关性关系。,利用关联规则来描述天体光谱数据特征与其物理化学性质之间存在的、未知的相关性是可行性的，具有重要的应用价值。,频繁模式集的生成,是提高关联规则挖掘效率的关键。,8,频繁模式生成主要有：Apriori和FP两类算法。,Apriori算法,优点: 思路比较清晰，以递归统计为基础，剪枝生成频繁集；,缺点: 在生成频繁模式过程中，需要产生大量的候选项和多次遍历数据库，I/O代价太高，难以适应海量高维数据。,FP算法,优点:,(l) 通过对FP树的递归访问，产生频繁模式集，仅需要构造FP树和条件FP树，不需要产生候选项集；,(2) 对事务数据库仅需两次遍历，第l次遍历产生频繁l-项集，第2次遍历用于构造FP树，从而降低了访问数据库的次数。,缺点: FP树需要占用大量内存。,9,约束FP树及其构造,一阶谓词逻辑与背景知识,数据挖掘是从宏观角度利用积累的巨量数据进行知识抽象的高级阶段，是一项高级的智能活动，因此数据挖掘过程离不开背景知识的支持。,关联规则挖掘过程也离不开背景知识的支持。,面向关联规则挖掘的背景知识实际上是描述数据集中的对象与属性之间、属性与属性之间的约束关系，因此采用一阶谓词逻辑描述关联规则挖掘中的背景知识是可行的。,10,定义3-1 设r 是交易数据库中的关系表名个体变量，f 是表示关系表到属性的映射的函词，k 是支持度（0k1），则背景知识G可由如下谓词公式，通过逻辑运算符组成合适公式。,(1) Interesting (f(r),(2) support(f(r),k),Interesting (f(r),(3) Interested(f(r),Interesting (f(r),(4) P(f(r) Q(f(r),Interesting (f(r),定义3-3 设D为交易数据库，,min为最小支持度，G为背景知识，如果L是一频繁模式，且G（L）=True，则称L为约束频繁模式。,11,CFP-tree及构造,定义3-4 设G为背景知识，对于任意频繁模式树FP-tree，如果从根节点到叶子节点的路径中，所描述的任一频繁模式P，使得G（P）=True，则称FP-Tree为约束频繁模式树CFP-tree。,构造思想与方法:,只有数据库中的事务T满足G所构造出的FP-Tree，才能包含用户感兴趣的约束频繁模式，可采用两次扫描数据库来完成CFP-tree的构造 。,12,定理2-1 设D为一个交易数据库、,min为最小支持度、G为背景知识，所构造出的约束FP树为CFP-tree，则从CFP-tree提取出的任意频繁模式P，一定是满足G（P）=true（即约束频繁模式）。,定理2-2 设D为一个交易数据库、,min为最小支持度、G为背景知识，所构造出的约束FP树为CFP-tree，P为任意频繁模式，若G（P）= true（即约束频繁模式），则P一定是CFP-tree中的频繁模式。,13,定理2-3 CFP-tree是FP-tree的子集。,定理2-4 设D为一个交易数据库、G1，G2为背景知识，且G1G2、T1，T2分别是基于G1，G2构造的CFP-tree，则T1T2。（约束的单调性）,推论3-1 设D为一个交易数据库、G1，G2为背景知识，T1，T2分别是基于G1，G2构造的CFP-tree，当G1=G2时T1=T2。(约束的唯一性),14,推论3-2 设D为一个交易数据库、G1为背景知识，T,CFP,是基于G1构造的CFP-tree，T,FP,是数据库D的FP-tree，当G1=时T,CFP,=T,FP,。,定理3-5 设D为一个交易数据库、,min为一个最小支持度、G为背景知识，构造出的约束FP树为CFP-tree，由G将交易数据库分为两部分，即：D=D1D2,其中：,TD1，那么G（T）=True，,TD2，G（T）=False， 如果对于D1，采用传统FP-tree构造方法的FP树为FP-Tree1，则CFP-tree与FP-Tree1是同一棵树。,15,约束FP树的构造算法,算法描述及分析（见P23-24）,实验分析,硬件：PentiumIV-2.0G CPU ，512M 内存；,软件：Windows XP 操作系统，DBMS 为ORACLE9i，VC+为编程语言；,数据预处理：(8400 条SDSS恒星光谱数据),1）选定间隔为20 的200个波长，离散化为十三种值；,2）温度等间隔离散化为三种值，七类恒星温度离散化为二十一种值；,3）光度、化学分度、微湍流等间隔离散化为三种值。,16,表3-2 约束FP树构造效率比较1（|DB|=6000，单位：秒）,最小支持度（,min,）,约束条件,5%,3%,2%,1%,无约束（FP算法）,384,503,640,819,光度_1化学丰度_2,191,253,298,385,光度_1,162,217,241,320,光度_1化学丰度_2,130,168,197,259,17,表3-3 约束FP树构造效率比较2（,min =3%，单位：秒）,数据集|DB|,约束条件,2000,4000,6000,8400,无约束（FP算法）,104,302,503,797,光度_1化学丰度_2,52,154,253,360,光度_1,42,120,217,299,光度_1化学丰度_2,36,103,168,244,18,表3-4 约束频繁模式（|DB|=8400，,min =1%，单位：个）,约束条件,无约束,光度_1化学丰度_2,光度_1,光度_1化学丰度_2,频繁模式个数,5732,710,408,221,19,基于CFP树的天体光谱数据相关性分析系统,天体光谱数据预处理,归一化,离散化（表3-5 恒星光谱数据离散化参数,）,天体光谱知识表示,给定一个天体光谱数据库DB=I1,I2,Im为DB中m条光谱数据的集合，DB中每一条光谱Ii就是I中的一组项目子集，即Ii,I，其中：,I = A1,A2,An ,S1,S2 ,Sm ，,Ai为第i波长处的离散化特征属性，Sj第j个物理化学性质的离散化属性。,20,定义3-5 设r 是天体光谱数据库中的关系表名个体变量，f 是表示关系表到属性的映射的函词，,min 是最小支持度（0,min1），则天体光谱知识G可由如下谓词公式，通过逻辑运算符组成合适公式。,(1) Interesting (f(r),(2) support(f(r),min),Interesting (f(r),(3) Interested(f(r),Interesting (f(r),对于任意天体光谱知识G，G是由定义3-5中的三类谓词公式，通过逻辑运算符组成的合适公式，由文献56可知，G可化简为合取范式，并用子句集S来表示。,21,定理3-6 设S是表示天体光谱知识G的子句集，任一子句sS是由谓词Interesting (f(r) 、support(f(r),min) 、Interested(f(r)所表达的若干有限文字析取式，且下列公式成立。,Interesting (f1(r1),support(f2(r1),min),Interested(f3(r1),Interesting（f1(r1),f2(r1),f3(r1)）,定理3-7 设S是表示天体光谱知识G的子句集，任一子句sS是感兴趣的天体光谱模式。,推论3-1 设G为天体光谱知识，则G描述了一组感性趣的天体光谱模式，即天体光谱模式集。,22,天体光谱数据的频繁模式提取与关联规则挖掘,CFP树的遍历：,创建一个项头表，使得每个项通过一个节点链指向它在树中的位置。提取过程从1频繁模式开始，构造它的条件模式基； 然后构造它的条件CFP树，并递归地在该树上进行提取。,关联规则生成：,对于任一频繁模式P,L，其中：P=P1,P2，P1是天体光谱数据特征的非空子模式，P2是物理化学性质的非空子模式，如果,( P1,P2/DB)/,( P1/DB),min，则生成一条关联规则“P1,P2”。,23,体系结构与功能,主 程 序,数据预处理,背景知识获取,CFP树构造,频繁模式提取,关联规则挖掘,24,预处理参数输入,挖掘结果输出,用户接口,规则提取,FP树的构造,频繁模式挖掘,归一化,恒星光谱库,恒星光谱数据,离散化,25,运行结果及分析,26,27,退回,28,引言,离群数据识别的主要方法：,距离的方法、统计的方法、局部密度的方法和基于偏离模型的方法等。,大多数的方法是从全局的观点看待离群数据，很难发现低维子空间中的偏移数据，而且很难应用于高维数据。,29,C C.Agarwal等人在2005年提出了一种基于子空间的高维离群数据识别算法，该算法采用遗传算法搜索离群数据。,C C.Agarwal,P S.Yu. An effective and efficient algorithm for high-dimensional outlier detection，The International Journal on Very Large Data Bases，2005, 14 ( 2)：211 221,存在问题：,仅利用稀疏度系数，在子空间中来考察数据的行为，无法避免由于正常数据的稀疏，导致在子空间中也是稀疏的不足，因此识别结果不是准确的；,不能确保能发现稀疏度系数最小的子空间，进而发现的离群数据也不够准确，该文献中的实验也验证了这一点；,不能确保发现所有满足条件的离群数据，识别结果的完备性得不到保证。,30,概念格, 由Wille R 提出, 是一种支持数据分析和知识发现的一种有效工具。,每个节点是一个形式概念, 由,外延,和,内涵,两部分组成。,通过Hasse 图生动和简洁地体现了这些概念之间的,泛化,和,特化,关系。,具有知识表示的,完备性,、,直观性,和,简洁性,等特点。,将概念格中每个概念内涵看作子空间，内涵看作子空间所包含的对象，从而用概念格结点，描述子空间中的离群数据，是可行的。,31,基于概念格的低维子空间离群数据,在稀疏子空间中，稀疏度系数仅反映了子空间中包含的数据对象个数远小于期望值，但数据对象个数远小于期望值，可能是数据对象在更低维子空间上的过度稀疏造成的，稀疏度系数并不能正确反映稀疏子空间上的数据偏离程度。因此仅采用S(D)来判断稀疏子空间的方法，不能保证结果的准确性。,数学期望表示了子空间中对象的平均个数，引入一个用户设置的系数，采用它们的乘积来度量子空间的稠密程度。,32,定义4-1 对于一个任意的数据集，其属性集为M，对象集为G，且每维均离散化为,个区间，DENSE为用户设置的稠密度系数，,由约简属性集P(P,M)构成的约简子空间D，且其包含的对象集为A(A,G),若|A|,DENSE*|G|*(1/,),|D|,，则称D为稠密子空间。,定义4-2 对于一个任意的数据集，其属性集为M，对象集为G，,由约简属性集P(P,M)构成的稀疏子空间D，且其包含的对象集为A(A,G)，若,由约简属性集P1(P1,P)构成的约简子空间D1，均为稠密子空间，则称D为离群子空间，A中的数据对象为离群数据。,33,定义4-3 设K=(G,M,I)为任意形式背景，,h=(A，B),L(G,M,I)，如果属性集合B1满足下述两个条件，则它被称为h的一个内涵缩减。,B1,= B,= A,B2,B1,= A (for any B2,B1),定义4-4 设K=(G,M,I)为任意形式背景，,h=(A，B),L(G,M,I)，h的内涵缩减集为RED=Bi| Bi为h的内涵缩减，若,Bi,RED，满足由属性集Bi构成的子空间S为稀疏子空间，则称h为稀疏概念，若,由约简属性集P(P,Bi)构成的约简子空间S1为稠密子空间，则称概念h为离群概念，A中包含的数据对象为离群数据。,34,定理4-1 对于一个任意的数据集，其属性集为M，对象集为G，K=(G,M,I)为其对应的形式背景，,由约简属性集P（P,M）构成的约简子空间D，及包含在D中的对象集O（即O= P,），则,h=(A，B),L(G,M,I)，及h的内涵缩减集RED=Bi| Bi为h的内涵缩减，使得P,RED，O= A成立。,定理4-2 对于一个任意的数据集，其属性集为M，对象集为G，K=(G,M,I)为其对应的形式背景，,由约简属性集P(P,M)构成的离群子空间D，及其包含的离群数据集O(O,G)，则在概念格L(G,M,I)中，必,一个离群概念h=(A,B),L(G,M,I)，及h的内涵缩减集RED=Bi|Bi为h的内涵缩减,使得P,RED，A=O成立。,35,定理4-3 设K=(G,M,I)为任意形式背景，,h=(A,B),L(G,M,I)，P为h的一个内涵缩减，则,约简属性集P1 (P1,P)，必,h1=(A1, B1),L(G,M,I)，使得P1为h1的内涵缩减，且B1,B。,定理4-4 设K=(G,M,I)为任意形式背景，,h=(A,B),L(G,M,I)，若P1为h的一个内涵缩减，且若由P1构成的子空间D1为稀疏子空间，则当稠密度系数DENSE=0时，A中包含的数据对象是离群数据。,36,基于概念格的低维子空间离群数据挖掘算法,算法描述CLOM,算法分析,实验分析,硬件：PentiumIV-2.0G CPU ，512M 内存，,软件：Windows XP 操作系统，DBMS 为ORACLE9i，VC+为编程语言,形式背景：（SDSS恒星光谱数据）,1)选定间隔为20的200个波长， 作为属性集；,2)依据每一波长处的流量、峰宽和形状，将其离散化为十三种数值之一，并作为该波长处取值。,37,表2-2 不同对象的建格与挖掘时间比较(TS=-1，DENSE=1.2),记录条数,建格时间,离群挖掘时间,离群数据数,5000,657s,174s,9,5500,822s,213s,7,6000,861s,234s,6,7000,1184s,435s,19,8315,1887s,595s,19,38,表2-3 不同TS值的挖掘时间和离群数据数 (DENSE=1.2，记录数8315),TS值,离群挖掘时间,离群数据数,-0.3,872s,60,-0.8,750s,31,-1.2,591s,19,-1.7,356s,6,39,表2-4 不同DENSE值的挖掘时间和离群数据(TS=-1.7，记录数8315),DENSE值,离群挖掘时间,离群数据数,0.6,394s,44,0.8,376s,23,1,366s,12,1.2,356s,6,1.4,354s,4,40,基于概念格的天体光谱离群数据挖掘系统,天体光谱数据与形式背景,在流量离散化处理中，不仅要描述天体光谱波长处的流量,强度,和,峰宽,，同时还应描述波的,形状,，即：吸收线还是发射线，故对于光谱不仅需考虑波长处的强度和峰宽两个因素，而且还需要考虑波的形状。,可以利用三个特征变量I、J、W来描述光谱在某一波长处的特征，I表示光谱波的强度，J表示光谱波峰的宽度，W表示光谱波的形状。从而将天体光谱数据中各个波长处的数据，转变为以特征变量I、J和W表示的特征数据。如果某一条光谱图中包含着的波长为A=Ai，i=1，2，3，n ，其中Ai表示i个波长处的光谱特征，n表示共有n个波长，那么Ai可表示为Ai=Ii，Ji，Wi 。,41,表4-3 光谱数据离散化,光谱数据按照上述方法及表4-3离散化后，形成了天体光谱数据的形式背景，从而适应于天体光谱数据概念格的构造。,42,功能与体系结构,光谱数据离群挖掘系统,数据预处理,构造概念格,离群数据挖掘,数据导入,光谱数据离散化,一般概念格构造,查看概念格文件,43,离散表,天体,光谱归一库,用户接口,概念格构造,离群数据挖掘,构造参数输入,挖掘结果输出,数据处理,概念格数据文本,44,开发环境与工具,采用VC+和Oracle9i作为开发工具，在PentiumIV-3.0G CPU，512M内存，Windows XP操作系统上，实现了天体光谱数据离群挖掘系统。,关键模块的实现技术,一、基于链表结构的概念格格构造,二、STL和ADO技术,45,运行结果及分析,将以文本存储的归一化后的光谱数据导入到oracle数据库中。数据包括光谱数据的fit文件名、sn_g信噪比、红移值、44根特征线的高度及等值宽度，每条光谱数据一共是91维，图4-6为导入的5412条高红移类星体的运行界面。,46,47,数据离散化,48,概念格,49,离群数据,50,小结,提出了一种基于约束FP树的天体光谱数据相关性分析技术。,首先采用一阶谓词逻辑作为背景知识表示技术，提出了一种新的FP树，约束FP树或CFP树，并给出了其构造算法CFP-Construct，从而降低了FP树构造的复杂性，提高了关联规则挖掘结果的针对性。其次，采用基于约束FP树的关联规则挖掘方法作为天体光谱数据相关性分析手段，提出了一种新的基于约束FP树的天体光谱数据相关性分析。最后，采用VC + 和Oracle9i 作为开发工具，设计并实现了天体光谱数据相关性分析原型系统，实验结果分析表明，该相关性分析方法是可行的和有价值的。,提出了一种基于概念格的天体光谱离群数据挖掘技术。,首先，通过定义和分析了度量低维子空间离群数据的稀疏度系数和稠密度系数，将概念格中每个概念内涵看作子空间，提出了一种基于概念格的低维子空间离群数据挖掘算法CLOM。其次，将概念节点的内涵缩减看作天体光谱特征子空间，提出了一种基于CLOM算法天体光谱离群数据识别方法。最后，采用VC + 和Oracle9i 作为开发工具，设计并实现了基于概念格的天体光谱离群数据挖掘原型系统，实验和系统运行结果分析表明，利用该方法挖掘出的天体光谱离群数据是准确的、完备的和有效的。,51,欢迎各位专家、学者多提宝贵意见！,谢谢大家！,52,