提出了一种基于概念格的天体光谱离群数据挖掘技术首先

天体光谱数据挖掘技术太原科技大学计算机科学与技术学院张继福2008年11月一、概述1）数据挖掘2）天体光谱数据挖掘3）课题的研究意义二、主要研究工作1）基于约束FP树的天体光谱数据相关性分析2）基于概念格的天体光谱离群数据挖掘数据挖掘定义：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含的、未知的、潜在的有用信息和知识，为决策支持服务。主要任务：关联规则、分类、聚类、离群数据等。常用的方法有：关联规则、决策树、神经网络、遗传算法、粗糙集、模糊集、概念格、统计分析等。天体光谱数据挖掘我国正在建造一台大天区面积多目标光纤光谱望远镜（LAMOST），是国家重大科学工程项目，也是世界上光谱获取率最高的望远镜。预计LAMOST所观测到的光谱数据容量将有可能达到4TB。急需一种新的以计算机为主的数据分析技术,分析和识别如此庞大的海量光谱数据。天体光谱数据处理主要内容:预处理(去噪、归一化等)、分类与识别、测量（红移等参数）等。一条Seyfert2光谱数据图(红移为0)天体光谱是天体电磁辐射按照波长的有序排列，蕴含着天体的重要物理信息，例如：天体的化学成份、天体的表面温度、直径、质量、光度以及天体的视向运动和自转。天文学家和天体物理学家通过分析天体光谱的信息，不仅可以研究宇宙中物质的分布特征，还可以研究天体的形成和随时间的演化等重大科学问题。主要的方法交叉相关分析与主成分分析（PCA）、人工神经网络、小波变换、贝叶斯统计、SVM等。典型的成果1）Autoclass，基于贝叶斯统计的一种光谱分类方法，发现了一些以前未注意的光谱类型和谱线；2）Gulati等人采用两层BP神经网络方法，用于恒星光谱次型的分类；3）Ellis等人采用交叉相关分析对光谱进行分类；4）邱波等人采用基于粗糙集的方法，进行了恒星光谱的分类识别；5）覃冬梅等人采用基于主分量分析法的二维恒星特征空间的快速光谱识别方法；6）刘中田等人提出基于小波特征的M型星自动识别方法等。课题的研究意义由于天文界对宇宙的认识还比较有限，LAMOST巡天计划的一个重要任务是要发现一些新的、特殊类型的天体，因此，如何利用数据挖掘技术从海量天体光谱数据中发现未知的、特殊的天体及天体规律是数据挖掘值得研究和探索的新应用领域。面向特定任务的数据挖掘是当前数据挖掘领域发展的趋势之一。以LAMOST项目为背景，对天体光谱数据挖掘技术进行了研究，其研究成果不仅具有重要的理论价值，而且可直接应用到LAMOST中，为国家重大科学工程提供技术支撑。退回引言•关联规则描述了属性之间的关联程度，也就是说有效地描述了数据集属性之间的相关性关系。•利用关联规则来描述天体光谱数据特征与其物理化学性质之间存在的、未知的相关性是可行性的，具有重要的应用价值。•频繁模式集的生成是提高关联规则挖掘效率的关键。•频繁模式生成主要有：Apriori和FP两类算法。•Apriori算法优点:思路比较清晰，以递归统计为基础，剪枝生成频繁集；缺点:在生成频繁模式过程中，需要产生大量的候选项和多次遍历数据库，I/O代价太高，难以适应海量高维数据。•FP算法优点:(l)通过对FP树的递归访问，产生频繁模式集，仅需要构造FP树和条件FP树，不需要产生候选项集；(2)对事务数据库仅需两次遍历，第l次遍历产生频繁l-项集，第2次遍历用于构造FP树，从而降低了访问数据库的次数。缺点:FP树需要占用大量内存。约束FP树及其构造•一阶谓词逻辑与背景知识数据挖掘是从宏观角度利用积累的巨量数据进行知识抽象的高级阶段，是一项高级的智能活动，因此数据挖掘过程离不开背景知识的支持。关联规则挖掘过程也离不开背景知识的支持。面向关联规则挖掘的背景知识实际上是描述数据集中的对象与属性之间、属性与属性之间的约束关系，因此采用一阶谓词逻辑描述关联规则挖掘中的背景知识是可行的。定义3-1设r是交易数据库中的关系表名个体变量，f是表示关系表到属性的映射的函词，k是支持度（0≤k≤1），则背景知识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为约束频繁模式。•CFP-tree及构造定义3-4设G为背景知识，对于任意频繁模式树FP-tree，如果从根节点到叶子节点的路径中，所描述的任一频繁模式P，使得G（P）=True，则称FP-Tree为约束频繁模式树CFP-tree。构造思想与方法:只有数据库中的事务T满足G所构造出的FP-Tree，才能包含用户感兴趣的约束频繁模式，可采用两次扫描数据库来完成CFP-tree的构造。定理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中的频繁模式。定理2-3CFP-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。(约束的唯一性)推论3-2设D为一个交易数据库、G1为背景知识，TCFP是基于G1构造的CFP-tree，TFP是数据库D的FP-tree，当G1=ф时TCFP=TFP。定理3-5设D为一个交易数据库、min为一个最小支持度、G为背景知识，构造出的约束FP树为CFP-tree，由G将交易数据库分为两部分，即：D=D1∪D2,其中：T∈D1，那么G（T）=True，T∈D2，G（T）=False，如果对于D1，采用传统FP-tree构造方法的FP树为FP-Tree1，则CFP-tree与FP-Tree1是同一棵树。•约束FP树的构造算法算法描述及分析（见P23-24）实验分析硬件：PentiumIV-2.0GCPU，512M内存；软件：WindowsXP操作系统，DBMS为ORACLE9i，VC++为编程语言；数据预处理：(8400条SDSS恒星光谱数据)1）选定间隔为20Å的200个波长，离散化为十三种值；2）温度等间隔离散化为三种值，七类恒星温度离散化为二十一种值；3）光度、化学分度、微湍流等间隔离散化为三种值。表3-2约束FP树构造效率比较1（|DB|=6000，单位：秒）最小支持度（min）约束条件5%3%2%1%无约束（FP算法）384503640819光度_1∨化学丰度_2191253298385光度_1162217241320光度_1∧化学丰度_2130168197259表3-3约束FP树构造效率比较2（min=3%，单位：秒）数据集|DB|约束条件2000400060008400无约束（FP算法）104302503797光度_1∨化学丰度_252154253360光度_142120217299光度_1∧化学丰度_236103168244表3-4约束频繁模式（|DB|=8400，min=1%，单位：个）约束条件无约束光度_1∨化学丰度_2光度_1光度_1∧化学丰度_2频繁模式个数5732710408221基于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个物理化学性质的离散化属性。定义3-5设r是天体光谱数据库中的关系表名个体变量，f是表示关系表到属性的映射的函词，min是最小支持度（0≤min≤1），则天体光谱知识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来表示。定理3-6设S是表示天体光谱知识G的子句集，任一子句s∈S是由谓词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的子句集，任一子句s∈S是感兴趣的天体光谱模式。推论3-1设G为天体光谱知识，则G描述了一组感性趣的天体光谱模式，即天体光谱模式集。•天体光谱数据的频繁模式提取与关联规则挖掘CFP树的遍历：创建一个项头表，使得每个项通过一个节点链指向它在树中的位置。提取过程从1频繁模式开始，构造它的条件模式基；然后构造它的条件CFP树，并递归地在该树上进行提取。关联规则生成：对于任一频繁模式PL，其中：P=P1P2，P1是天体光谱数据特征的非空子模式，P2是物理化学性质的非空子模式，如果(P1P2/DB)/(P1/DB)≥min，则生成一条关联规则“P1P2”。•体系结构与功能主程序数据预处理背景知识获取CFP树构造频繁模式提取关联规则挖掘预处理参数输入挖掘结果输出用户接口规则提取FP树的构造频繁模式挖掘归一化恒星光谱库恒星光谱数据离散化•运行结果及分析退回引言离群数据识别的主要方法：距离的方法、统计的方法、局部密度的方法和基于偏离模型的方法等。大多数的方法是从全局的观点看待离群数据，很难发现低维子空间中的偏移数据，而且很难应用于高维数据。CC.Agarwal等人在2005年提出了一种基于子空间的高维离群数据识别算法，该算法采用遗传算法搜索离群数据。CC.Agarwal,PS.Yu.Aneffectiveandefficientalgorithmforhigh-dimensionaloutlierdetection，TheInternationalJournalonVeryLargeDataBases，2005,14(2)：211–221存在问题：①仅利用稀疏度系数，在子空间中来考察数据的行为，无法避免由于正常数据的稀疏，导致在子空间中也是稀疏的不足，因此识别结果不是准确的；②不能确保能发现稀疏度系数最小的子空间，进而发现的离群数据也不够准确，该文献中的实验也验证了这一点；③不能确保发现所有满足条件的离群数据，识别结果的完备性得不到保证。概念格,由WilleR提出,是一种支持数据分析和知识发现的一种有效工具。每个节点是一个形式概念,由外延和内涵两部分组成。通过Hasse图生动和简洁地体现了这些概念之间的泛化和特化关系。具有知识表示的完备性、直观性和简洁性等特点。将概念格中每个概念内涵看作子空间，内涵看作子空间所包含的对象，从而用概念格结点，描述子空间中的离群数据，是可行的。基于概念格的低维子空间离群数据在稀疏子空间中，稀疏度系数仅反映了子空间中包含的数据对象个数远小于期望值，但数据对象个数