天体光谱数据挖掘技术.ppt

《天体光谱数据挖掘技术.ppt》由会员分享，可在线阅读，更多相关《天体光谱数据挖掘技术.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、天体光谱数据挖掘技术天体光谱数据挖掘技术太原科技大学计算机科学与技术学院张继福太原科技大学计算机科学与技术学院张继福太原科技大学计算机科学与技术学院张继福太原科技大学计算机科学与技术学院张继福 20082008年年1111月月一、概一、概 述述 1）数据挖掘数据挖掘数据挖掘数据挖掘 2 2）天体光谱数据挖掘）天体光谱数据挖掘）天体光谱数据挖掘）天体光谱数据挖掘 3 3）课题的研究意义）课题的研究意义）课题的研究意义）课题的研究意义二、主要研究工作二、主要研究工作 1 1）基于约束基于约束基于约束基于约束FPFP树的天体光谱数据相关性分析树的天体光谱数据相关性分析树的天体光谱数据相关性分析树的天

2、体光谱数据相关性分析 2 2）基于概念格的天体光谱离群数据挖掘基于概念格的天体光谱离群数据挖掘基于概念格的天体光谱离群数据挖掘基于概念格的天体光谱离群数据挖掘 数据挖掘数据挖掘 定义：数据挖掘就是从大量的、不完全的、有噪声的、模定义：数据挖掘就是从大量的、不完全的、有噪声的、模定义：数据挖掘就是从大量的、不完全的、有噪声的、模定义：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含的、未知的、潜在的有用糊的、随机的数据中，提取隐含的、未知的、潜在的有用糊的、随机的数据中，提取隐含的、未知的、潜在的有用糊的、随机的数据中，提取隐含的、未知的、潜在的有用信息和知识，为决策支持

3、服务。信息和知识，为决策支持服务。信息和知识，为决策支持服务。信息和知识，为决策支持服务。主要任务：关联规则、分类、聚类、离群数据等。主要任务：关联规则、分类、聚类、离群数据等。主要任务：关联规则、分类、聚类、离群数据等。主要任务：关联规则、分类、聚类、离群数据等。常用的方法有：关联规则、决策树、神经网络、遗传算法、常用的方法有：关联规则、决策树、神经网络、遗传算法、常用的方法有：关联规则、决策树、神经网络、遗传算法、常用的方法有：关联规则、决策树、神经网络、遗传算法、粗糙集、模糊集、概念格、统计分析等。粗糙集、模糊集、概念格、统计分析等。粗糙集、模糊集、概念格、统计分析等。粗糙集、模糊集、概

4、念格、统计分析等。天体光谱数据挖掘天体光谱数据挖掘 我国正在建造一台大天区面积多目标光纤光谱望远我国正在建造一台大天区面积多目标光纤光谱望远我国正在建造一台大天区面积多目标光纤光谱望远我国正在建造一台大天区面积多目标光纤光谱望远镜（镜（镜（镜（LAMOSTLAMOST），是国家重大科学工程项目，也是世界），是国家重大科学工程项目，也是世界），是国家重大科学工程项目，也是世界），是国家重大科学工程项目，也是世界上光谱获取率最高的望远镜。上光谱获取率最高的望远镜。上光谱获取率最高的望远镜。上光谱获取率最高的望远镜。预计预计预计预计LAMOSTLAMOST所观测到的光谱数据容量将有可能达所观测到的光

5、谱数据容量将有可能达所观测到的光谱数据容量将有可能达所观测到的光谱数据容量将有可能达到到到到4TB4TB。急需一种新的以计算机为主的数据分析技术急需一种新的以计算机为主的数据分析技术急需一种新的以计算机为主的数据分析技术急需一种新的以计算机为主的数据分析技术,分析分析分析分析和识别如此庞大的海量光谱数据。和识别如此庞大的海量光谱数据。和识别如此庞大的海量光谱数据。和识别如此庞大的海量光谱数据。天体光谱数据处理主要内容天体光谱数据处理主要内容天体光谱数据处理主要内容天体光谱数据处理主要内容:预处理预处理预处理预处理(去噪、归一化去噪、归一化去噪、归一化去噪、归一化等等等等)、分类与识别分类与识别

6、分类与识别分类与识别、测量（红移等参数）测量（红移等参数）测量（红移等参数）测量（红移等参数）等。等。等。等。一条一条Seyfert 2 光谱数据图光谱数据图(红移为红移为0)天体光谱是天体电磁辐射按照波长的有序排列，蕴含着天体的重要天体光谱是天体电磁辐射按照波长的有序排列，蕴含着天体的重要物理信息，例如：天体的化学成份、天体的表面温度、直径、质量、光物理信息，例如：天体的化学成份、天体的表面温度、直径、质量、光度以及天体的视向运动和自转度以及天体的视向运动和自转。天文学家和天体物理学家通过分析天体天文学家和天体物理学家通过分析天体光谱的信息，不仅可以研究宇宙中物质的分布特征，还可以研究天体的

7、光谱的信息，不仅可以研究宇宙中物质的分布特征，还可以研究天体的形成和随时间的演化等重大科学问题形成和随时间的演化等重大科学问题。主要的方法主要的方法主要的方法主要的方法 交叉相关分析与主成分分析（交叉相关分析与主成分分析（交叉相关分析与主成分分析（交叉相关分析与主成分分析（PCAPCA）、人工神经网络、）、人工神经网络、）、人工神经网络、）、人工神经网络、小波变换、贝叶斯统计、小波变换、贝叶斯统计、小波变换、贝叶斯统计、小波变换、贝叶斯统计、SVMSVM等。等。等。等。典型的成果典型的成果典型的成果典型的成果 1 1）AutoclassAutoclass，基于贝叶斯统计的一种光谱分类方，基于贝

8、叶斯统计的一种光谱分类方，基于贝叶斯统计的一种光谱分类方，基于贝叶斯统计的一种光谱分类方法，发现了一些以前未注意的光谱类型和谱线；法，发现了一些以前未注意的光谱类型和谱线；法，发现了一些以前未注意的光谱类型和谱线；法，发现了一些以前未注意的光谱类型和谱线；2 2）GulatiGulati等人采用两层等人采用两层等人采用两层等人采用两层BPBP神经网络方法，用于恒星神经网络方法，用于恒星神经网络方法，用于恒星神经网络方法，用于恒星光谱次型的分类；光谱次型的分类；光谱次型的分类；光谱次型的分类；3 3）EllisEllis等人采用交叉相关分析对光谱进行分类；等人采用交叉相关分析对光谱进行分类；等人

9、采用交叉相关分析对光谱进行分类；等人采用交叉相关分析对光谱进行分类；4 4）邱波等人采用基于粗糙集的方法，进行了恒星光）邱波等人采用基于粗糙集的方法，进行了恒星光）邱波等人采用基于粗糙集的方法，进行了恒星光）邱波等人采用基于粗糙集的方法，进行了恒星光谱的分类识别；谱的分类识别；谱的分类识别；谱的分类识别；5 5）覃冬梅等人采用基于主分量分析法的二维恒星特）覃冬梅等人采用基于主分量分析法的二维恒星特）覃冬梅等人采用基于主分量分析法的二维恒星特）覃冬梅等人采用基于主分量分析法的二维恒星特征空间的快速光谱识别方法；征空间的快速光谱识别方法；征空间的快速光谱识别方法；征空间的快速光谱识别方法；6 6）

10、刘中田等人提出基于小波特征的）刘中田等人提出基于小波特征的）刘中田等人提出基于小波特征的）刘中田等人提出基于小波特征的MM型星自动识别型星自动识别型星自动识别型星自动识别方法等。方法等。方法等。方法等。课题的研究意义课题的研究意义课题的研究意义课题的研究意义 由于天文界对宇宙的认识还比较有限，由于天文界对宇宙的认识还比较有限，由于天文界对宇宙的认识还比较有限，由于天文界对宇宙的认识还比较有限，LAMOSTLAMOST巡天巡天巡天巡天计划的一个重要任务是要发现一些新的、特殊类型的天体，计划的一个重要任务是要发现一些新的、特殊类型的天体，计划的一个重要任务是要发现一些新的、特殊类型的天体，计划的一

11、个重要任务是要发现一些新的、特殊类型的天体，因此，如何利用数据挖掘技术从海量天体光谱数据中发现因此，如何利用数据挖掘技术从海量天体光谱数据中发现因此，如何利用数据挖掘技术从海量天体光谱数据中发现因此，如何利用数据挖掘技术从海量天体光谱数据中发现未知的、特殊的天体及天体规律是数据挖掘值得研究和探未知的、特殊的天体及天体规律是数据挖掘值得研究和探未知的、特殊的天体及天体规律是数据挖掘值得研究和探未知的、特殊的天体及天体规律是数据挖掘值得研究和探索的新应用领域。索的新应用领域。索的新应用领域。索的新应用领域。面向特定任务的数据挖掘是当前数据挖掘领域发展的面向特定任务的数据挖掘是当前数据挖掘领域发展的

12、面向特定任务的数据挖掘是当前数据挖掘领域发展的面向特定任务的数据挖掘是当前数据挖掘领域发展的趋势之一。以趋势之一。以趋势之一。以趋势之一。以LAMOSTLAMOST项目为背景，对天体光谱数据挖掘项目为背景，对天体光谱数据挖掘项目为背景，对天体光谱数据挖掘项目为背景，对天体光谱数据挖掘技术进行了研究，其研究成果不仅具有重要的理论价值，技术进行了研究，其研究成果不仅具有重要的理论价值，技术进行了研究，其研究成果不仅具有重要的理论价值，技术进行了研究，其研究成果不仅具有重要的理论价值，而且可直接应用到而且可直接应用到而且可直接应用到而且可直接应用到LAMOSTLAMOST中，为国家重大科学工程提供中

13、，为国家重大科学工程提供中，为国家重大科学工程提供中，为国家重大科学工程提供技术支撑。技术支撑。技术支撑。技术支撑。退回引言引言引言引言关联规则描述了属性之间的关联程度，也就是说有效地描关联规则描述了属性之间的关联程度，也就是说有效地描关联规则描述了属性之间的关联程度，也就是说有效地描关联规则描述了属性之间的关联程度，也就是说有效地描述了数据集属性之间的相关性关系。述了数据集属性之间的相关性关系。述了数据集属性之间的相关性关系。述了数据集属性之间的相关性关系。利用关联规则来描述天体光谱数据特征与其物理化学性质利用关联规则来描述天体光谱数据特征与其物理化学性质利用关联规则来描述天体光谱数据特征与

14、其物理化学性质利用关联规则来描述天体光谱数据特征与其物理化学性质之间存在的、未知的相关性是可行性的，具有重要的应用之间存在的、未知的相关性是可行性的，具有重要的应用之间存在的、未知的相关性是可行性的，具有重要的应用之间存在的、未知的相关性是可行性的，具有重要的应用价值。价值。价值。价值。频繁模式集的生成频繁模式集的生成频繁模式集的生成频繁模式集的生成是提高关联规则挖掘效率的关键。是提高关联规则挖掘效率的关键。是提高关联规则挖掘效率的关键。是提高关联规则挖掘效率的关键。频繁模式生成主要有：频繁模式生成主要有：频繁模式生成主要有：频繁模式生成主要有：AprioriApriori和和和和FPFP两类

15、算法。两类算法。两类算法。两类算法。AprioriApriori算法算法算法算法 优点优点优点优点:思路比较清晰，以递归统计为基础，剪枝生成频繁思路比较清晰，以递归统计为基础，剪枝生成频繁思路比较清晰，以递归统计为基础，剪枝生成频繁思路比较清晰，以递归统计为基础，剪枝生成频繁集；集；集；集；缺点缺点缺点缺点:在生成频繁模式过程中，需要产生大量的候选项和在生成频繁模式过程中，需要产生大量的候选项和在生成频繁模式过程中，需要产生大量的候选项和在生成频繁模式过程中，需要产生大量的候选项和多次遍历数据库，多次遍历数据库，多次遍历数据库，多次遍历数据库，I/OI/O代价太高，难以适应海量高维数据。代价太

16、高，难以适应海量高维数据。代价太高，难以适应海量高维数据。代价太高，难以适应海量高维数据。FPFP算法算法算法算法 优点优点优点优点:(l)(l)通过对通过对通过对通过对FPFP树的递归访问，产生频繁模式集，仅需树的递归访问，产生频繁模式集，仅需树的递归访问，产生频繁模式集，仅需树的递归访问，产生频繁模式集，仅需要构造要构造要构造要构造FPFP树和条件树和条件树和条件树和条件FPFP树，不需要产生候选项集；树，不需要产生候选项集；树，不需要产生候选项集；树，不需要产生候选项集；(2)(2)对事务数据库仅需两次遍历，第对事务数据库仅需两次遍历，第对事务数据库仅需两次遍历，第对事务数据库仅需两次遍

17、历，第l l次遍历产生频繁次遍历产生频繁次遍历产生频繁次遍历产生频繁l-l-项集，第项集，第项集，第项集，第2 2次遍历用于构造次遍历用于构造次遍历用于构造次遍历用于构造FPFP树，从而降低了访问数据树，从而降低了访问数据树，从而降低了访问数据树，从而降低了访问数据库的次数。库的次数。库的次数。库的次数。缺点缺点缺点缺点:FP:FP树需要占用大量内存。树需要占用大量内存。树需要占用大量内存。树需要占用大量内存。约束约束约束约束FPFP树及其构造树及其构造树及其构造树及其构造 一阶谓词逻辑与背景知识一阶谓词逻辑与背景知识一阶谓词逻辑与背景知识一阶谓词逻辑与背景知识 数据挖掘是从宏观角度利用积累的

18、巨量数据进行知识数据挖掘是从宏观角度利用积累的巨量数据进行知识数据挖掘是从宏观角度利用积累的巨量数据进行知识数据挖掘是从宏观角度利用积累的巨量数据进行知识抽象的高级阶段，是一项高级的智能活动，因此数据挖掘抽象的高级阶段，是一项高级的智能活动，因此数据挖掘抽象的高级阶段，是一项高级的智能活动，因此数据挖掘抽象的高级阶段，是一项高级的智能活动，因此数据挖掘过程离不开背景知识的支持。过程离不开背景知识的支持。过程离不开背景知识的支持。过程离不开背景知识的支持。关联规则挖掘过程也离不开背景知识的支持。关联规则挖掘过程也离不开背景知识的支持。关联规则挖掘过程也离不开背景知识的支持。关联规则挖掘过程也离不

19、开背景知识的支持。面向关联规则挖掘的背景知识实际上是描述数据集中面向关联规则挖掘的背景知识实际上是描述数据集中面向关联规则挖掘的背景知识实际上是描述数据集中面向关联规则挖掘的背景知识实际上是描述数据集中的对象与属性之间、属性与属性之间的约束关系，因此采的对象与属性之间、属性与属性之间的约束关系，因此采的对象与属性之间、属性与属性之间的约束关系，因此采的对象与属性之间、属性与属性之间的约束关系，因此采用一阶谓词逻辑描述关联规则挖掘中的背景知识是可行的。用一阶谓词逻辑描述关联规则挖掘中的背景知识是可行的。用一阶谓词逻辑描述关联规则挖掘中的背景知识是可行的。用一阶谓词逻辑描述关联规则挖掘中的背景知识

20、是可行的。定义定义定义定义3-1 3-1 设设设设r r 是交易数据库中的关系表名个体变量，是交易数据库中的关系表名个体变量，是交易数据库中的关系表名个体变量，是交易数据库中的关系表名个体变量，f f 是是是是表示关系表到属性的映射的函词，表示关系表到属性的映射的函词，表示关系表到属性的映射的函词，表示关系表到属性的映射的函词，k k 是支持度是支持度是支持度是支持度（0k10k1），则背景知识），则背景知识），则背景知识），则背景知识G G可由如下谓词公式，通过逻辑可由如下谓词公式，通过逻辑可由如下谓词公式，通过逻辑可由如下谓词公式，通过逻辑运算符组成合适公式。运算符组成合适公式。运算符组成

21、合适公式。运算符组成合适公式。(1)Interesting(1)Interesting(f(rf(r)(2)(2)support(f(r),ksupport(f(r),k)Interesting(Interesting(f(rf(r)(3)(3)Interested(f(rInterested(f(r)Interesting(Interesting(f(rf(r)(4)(4)P(f(rP(f(r)Q(f(rQ(f(r)Interesting(Interesting(f(rf(r)定义定义定义定义3-3 3-3 设设设设D D为交易数据库，为交易数据库，为交易数据库，为交易数据库，minmin为

22、最小支持度，为最小支持度，为最小支持度，为最小支持度，G G为背为背为背为背景知识，如果景知识，如果景知识，如果景知识，如果L L是一频繁模式，且是一频繁模式，且是一频繁模式，且是一频繁模式，且G G（L L）=True=True，则称，则称，则称，则称L L为约束频繁模式。为约束频繁模式。为约束频繁模式。为约束频繁模式。CFP-treeCFP-tree及构造及构造及构造及构造 定义定义定义定义3-4 3-4 设设设设G G为背景知识，对于任意频繁模式树为背景知识，对于任意频繁模式树为背景知识，对于任意频繁模式树为背景知识，对于任意频繁模式树FP-treeFP-tree，如果从根节点到叶子节点

23、的路径中，所描述的任一频繁，如果从根节点到叶子节点的路径中，所描述的任一频繁，如果从根节点到叶子节点的路径中，所描述的任一频繁，如果从根节点到叶子节点的路径中，所描述的任一频繁模式模式模式模式P P，使得，使得，使得，使得G G（P P）=True=True，则称，则称，则称，则称FP-TreeFP-Tree为约束频繁模为约束频繁模为约束频繁模为约束频繁模式树式树式树式树CFP-treeCFP-tree。构造思想与方法构造思想与方法构造思想与方法构造思想与方法:只有数据库中的事务只有数据库中的事务只有数据库中的事务只有数据库中的事务T T满足满足满足满足G G所构造出的所构造出的所构造出的所构

24、造出的FP-TreeFP-Tree，才能包含用户感兴趣的约束频繁模式，可采用两次扫描数才能包含用户感兴趣的约束频繁模式，可采用两次扫描数才能包含用户感兴趣的约束频繁模式，可采用两次扫描数才能包含用户感兴趣的约束频繁模式，可采用两次扫描数据库来完成据库来完成据库来完成据库来完成CFP-treeCFP-tree的构造的构造的构造的构造 。定理定理定理定理2-1 2-1 设设设设D D为一个交易数据库、为一个交易数据库、为一个交易数据库、为一个交易数据库、minmin为最小支持度、为最小支持度、为最小支持度、为最小支持度、G G为背景知识，所构造出的约束为背景知识，所构造出的约束为背景知识，所构造出

25、的约束为背景知识，所构造出的约束FPFP树为树为树为树为CFP-treeCFP-tree，则从，则从，则从，则从CFP-treeCFP-tree提取出的任意频繁模式提取出的任意频繁模式提取出的任意频繁模式提取出的任意频繁模式P P，一定是满足，一定是满足，一定是满足，一定是满足G G（P P）=true=true（即约束频繁模式）。（即约束频繁模式）。（即约束频繁模式）。（即约束频繁模式）。定理定理定理定理2-2 2-2 设设设设D D为一个交易数据库、为一个交易数据库、为一个交易数据库、为一个交易数据库、minmin为最小支持度、为最小支持度、为最小支持度、为最小支持度、G G为背景知识，所

26、构造出的约束为背景知识，所构造出的约束为背景知识，所构造出的约束为背景知识，所构造出的约束FPFP树为树为树为树为CFP-treeCFP-tree，P P为任为任为任为任意频繁模式，若意频繁模式，若意频繁模式，若意频繁模式，若G G（P P）=true=true（即约束频繁模式），则（即约束频繁模式），则（即约束频繁模式），则（即约束频繁模式），则P P一定是一定是一定是一定是CFP-treeCFP-tree中的频繁模式。中的频繁模式。中的频繁模式。中的频繁模式。定理定理定理定理2-3 CFP-tree2-3 CFP-tree是是是是FP-treeFP-tree的子集。的子集。的子集。的子集。

27、定理定理定理定理2-4 2-4 设设设设D D为一个交易数据库、为一个交易数据库、为一个交易数据库、为一个交易数据库、G1G1，G2G2为背景知识，为背景知识，为背景知识，为背景知识，且且且且G1G2G1G2、T1T1，T2T2分别是基于分别是基于分别是基于分别是基于G1G1，G2G2构造的构造的构造的构造的CFP-treeCFP-tree，则，则，则，则T1T2T1T2。（约束的单调性）。（约束的单调性）。（约束的单调性）。（约束的单调性）推论推论推论推论3-1 3-1 设设设设D D为一个交易数据库、为一个交易数据库、为一个交易数据库、为一个交易数据库、G1G1，G2G2为背景知识，为背景

28、知识，为背景知识，为背景知识，T1T1，T2T2分别是基于分别是基于分别是基于分别是基于G1G1，G2G2构造的构造的构造的构造的CFP-treeCFP-tree，当，当，当，当G1=G2G1=G2时时时时T1=T2T1=T2。(约束的唯一性约束的唯一性约束的唯一性约束的唯一性)推论推论推论推论3-2 3-2 设设设设D D为一个交易数据库、为一个交易数据库、为一个交易数据库、为一个交易数据库、G1G1为背景知识，为背景知识，为背景知识，为背景知识，T TCFPCFP是是是是基于基于基于基于G1G1构造的构造的构造的构造的CFP-treeCFP-tree，T TFPFP是数据库是数据库是数据库

29、是数据库D D的的的的FP-treeFP-tree，当，当，当，当G1=G1=时时时时T TCFPCFP=T=TFPFP。定理定理定理定理3-5 3-5 设设设设D D为一个交易数据库、为一个交易数据库、为一个交易数据库、为一个交易数据库、minmin为一个最小支持为一个最小支持为一个最小支持为一个最小支持度、度、度、度、G G为背景知识，构造出的约束为背景知识，构造出的约束为背景知识，构造出的约束为背景知识，构造出的约束FPFP树为树为树为树为CFP-treeCFP-tree，由，由，由，由G G将交易数据库分为两部分，即：将交易数据库分为两部分，即：将交易数据库分为两部分，即：将交易数据库

30、分为两部分，即：D=D1D=D1D2,D2,其中：其中：其中：其中：T TD1D1，那么，那么，那么，那么G G（T T）=True=True，T TD2D2，G G（T T）=False=False，如果对于如果对于如果对于如果对于D1D1，采用传统，采用传统，采用传统，采用传统FP-treeFP-tree构造方构造方构造方构造方法的法的法的法的FPFP树为树为树为树为FP-Tree1FP-Tree1，则，则，则，则CFP-treeCFP-tree与与与与FP-Tree1FP-Tree1是同一是同一是同一是同一棵树。棵树。棵树。棵树。约束约束约束约束FPFP树的构造算法树的构造算法树的构造算

31、法树的构造算法 算法描述及分析（见算法描述及分析（见算法描述及分析（见算法描述及分析（见P23-24P23-24）实验分析实验分析实验分析实验分析 硬件：硬件：硬件：硬件：PentiumIV-2.0G CPU PentiumIV-2.0G CPU，512M 512M 内存；内存；内存；内存；软件：软件：软件：软件：Windows XP Windows XP 操作系统，操作系统，操作系统，操作系统，DBMS DBMS 为为为为ORACLE9iORACLE9i，VC+VC+为编程语言；为编程语言；为编程语言；为编程语言；数据预处理：数据预处理：数据预处理：数据预处理：(8400(8400 条条条条

32、SDSSSDSS恒星光谱数据恒星光谱数据恒星光谱数据恒星光谱数据)1 1）选定间隔为）选定间隔为）选定间隔为）选定间隔为20 20 的的的的200200个波长，离散化为十三种个波长，离散化为十三种个波长，离散化为十三种个波长，离散化为十三种值；值；值；值；2 2）温度等间隔离散化为三种值，七类恒星温度离散）温度等间隔离散化为三种值，七类恒星温度离散）温度等间隔离散化为三种值，七类恒星温度离散）温度等间隔离散化为三种值，七类恒星温度离散化为二十一种值；化为二十一种值；化为二十一种值；化为二十一种值；3 3）光度、化学分度、微湍流等间隔离散化为三种值。）光度、化学分度、微湍流等间隔离散化为三种值。

33、）光度、化学分度、微湍流等间隔离散化为三种值。）光度、化学分度、微湍流等间隔离散化为三种值。表表表表3-2 3-2 约束约束约束约束FPFP树构造效率比较树构造效率比较树构造效率比较树构造效率比较1 1（|DB|=6000|DB|=6000，单位：秒），单位：秒），单位：秒），单位：秒）最小支持度（min）约束条件5%3%2%1%无约束（FP算法）384503640819光度_1化学丰度_2191253298385光度_1162217241320光度_1化学丰度_2130168197259表表表表3-3 3-3 约束约束约束约束FPFP树构造效率比较树构造效率比较树构造效率比较树构造效率比较2

34、 2（min=3%min=3%，单位：秒），单位：秒），单位：秒），单位：秒）数据集|DB|约束条件2000400060008400无约束（FP算法）104302503797光度_1化学丰度_252154253360光度_142120217299光度_1化学丰度_236103168244表3-4 约束频繁模式（|DB|=8400，min=1%，单位：个）约束条件无约束光度_1化学丰度_2光度_1光度_1化学丰度_2频繁模式个数5732710408221基于基于CFP树的天体光谱数据相关性分析系统树的天体光谱数据相关性分析系统 天体光谱数据预处理天体光谱数据预处理天体光谱数据预处理天体光谱数据预

35、处理 归一化归一化归一化归一化 离散化（表离散化（表离散化（表离散化（表3-5 3-5 恒星光谱数据离散化参数恒星光谱数据离散化参数恒星光谱数据离散化参数恒星光谱数据离散化参数）天体光谱知识表示天体光谱知识表示天体光谱知识表示天体光谱知识表示 给定一个天体光谱数据库给定一个天体光谱数据库给定一个天体光谱数据库给定一个天体光谱数据库DB=I1,I2,DB=I1,I2,Im,Im为为为为DBDB中中中中mm条光谱数据的集合，条光谱数据的集合，条光谱数据的集合，条光谱数据的集合，DBDB中每一条光谱中每一条光谱中每一条光谱中每一条光谱IiIi就是就是就是就是I I中的一组中的一组中的一组中的一组项目

36、子集，即项目子集，即项目子集，即项目子集，即IiIi I I，其中：，其中：，其中：，其中：I=A1,A2,An,S1,S2,I=A1,A2,An,S1,S2,SmSm ，AiAi为第为第为第为第i i波长处的离散化特征属性，波长处的离散化特征属性，波长处的离散化特征属性，波长处的离散化特征属性，SjSj第第第第j j个物理化学个物理化学个物理化学个物理化学性质的离散化属性。性质的离散化属性。性质的离散化属性。性质的离散化属性。定义定义定义定义3-5 3-5 设设设设r r 是天体光谱数据库中的关系表名个体变量，是天体光谱数据库中的关系表名个体变量，是天体光谱数据库中的关系表名个体变量，是天体

37、光谱数据库中的关系表名个体变量，f f 是表示关系表到属性的映射的函词，是表示关系表到属性的映射的函词，是表示关系表到属性的映射的函词，是表示关系表到属性的映射的函词，min min 是最小支持度是最小支持度是最小支持度是最小支持度（00 min1min1），则天体光谱知识），则天体光谱知识），则天体光谱知识），则天体光谱知识G G可由如下谓词公式，可由如下谓词公式，可由如下谓词公式，可由如下谓词公式，通过逻辑运算符组成合适公式。通过逻辑运算符组成合适公式。通过逻辑运算符组成合适公式。通过逻辑运算符组成合适公式。(1)Interesting(1)Interesting(f(rf(r)(2)(2

38、)support(f(rsupport(f(r),),min)min)Interesting(Interesting(f(rf(r)(3)(3)Interested(f(rInterested(f(r)Interesting(Interesting(f(rf(r)对于任意天体光谱知识对于任意天体光谱知识对于任意天体光谱知识对于任意天体光谱知识G G，G G是由定义是由定义是由定义是由定义3-53-5中的三类谓中的三类谓中的三类谓中的三类谓词公式，通过逻辑运算符组成的合适公式，由文献词公式，通过逻辑运算符组成的合适公式，由文献词公式，通过逻辑运算符组成的合适公式，由文献词公式，通过逻辑运算符组成

39、的合适公式，由文献5656可可可可知，知，知，知，G G可化简为合取范式，并用子句集可化简为合取范式，并用子句集可化简为合取范式，并用子句集可化简为合取范式，并用子句集S S来表示。来表示。来表示。来表示。定理定理定理定理3-6 3-6 设设设设S S是表示天体光谱知识是表示天体光谱知识是表示天体光谱知识是表示天体光谱知识G G的子句集，任一子句的子句集，任一子句的子句集，任一子句的子句集，任一子句s sS S是由谓词是由谓词是由谓词是由谓词Interesting(Interesting(f(rf(r)、support(f(rsupport(f(r),),min)min)、Interested

40、(f(rInterested(f(r)所表达的若干有限文字析取式，所表达的若干有限文字析取式，所表达的若干有限文字析取式，所表达的若干有限文字析取式，且下列公式成立。且下列公式成立。且下列公式成立。且下列公式成立。Interesting(f1(r1)Interesting(f1(r1)support(f2(r1),support(f2(r1),min)min)Interested(f3(r1)Interested(f3(r1)InterestingInteresting（f1(r1)f1(r1)f2(r1)f2(r1)f3(r1)f3(r1)）定理定理定理定理3-7 3-7 设设设设S S是表

41、示天体光谱知识是表示天体光谱知识是表示天体光谱知识是表示天体光谱知识G G的子句集，任一子句的子句集，任一子句的子句集，任一子句的子句集，任一子句s sS S是感兴趣的天体光谱模式。是感兴趣的天体光谱模式。是感兴趣的天体光谱模式。是感兴趣的天体光谱模式。推论推论推论推论3-1 3-1 设设设设G G为天体光谱知识，则为天体光谱知识，则为天体光谱知识，则为天体光谱知识，则G G描述了一组感性趣的天描述了一组感性趣的天描述了一组感性趣的天描述了一组感性趣的天体光谱模式，即天体光谱模式集。体光谱模式，即天体光谱模式集。体光谱模式，即天体光谱模式集。体光谱模式，即天体光谱模式集。天体光谱数据的频繁模式

42、提取与关联规则挖掘天体光谱数据的频繁模式提取与关联规则挖掘天体光谱数据的频繁模式提取与关联规则挖掘天体光谱数据的频繁模式提取与关联规则挖掘 CFPCFP树的遍历：树的遍历：树的遍历：树的遍历：创建一个项头表，使得每个项通过一个节点链指向它创建一个项头表，使得每个项通过一个节点链指向它创建一个项头表，使得每个项通过一个节点链指向它创建一个项头表，使得每个项通过一个节点链指向它在树中的位置。提取过程从在树中的位置。提取过程从在树中的位置。提取过程从在树中的位置。提取过程从1 1频繁模式开始，构造它的条频繁模式开始，构造它的条频繁模式开始，构造它的条频繁模式开始，构造它的条件模式基；件模式基；件模式

43、基；件模式基；然后构造它的条件然后构造它的条件然后构造它的条件然后构造它的条件CFPCFP树，并递归地在该树上树，并递归地在该树上树，并递归地在该树上树，并递归地在该树上进行提取。进行提取。进行提取。进行提取。关联规则生成：关联规则生成：关联规则生成：关联规则生成：对于任一频繁模式对于任一频繁模式对于任一频繁模式对于任一频繁模式P P L L，其中：，其中：，其中：，其中：P=P1P=P1 P2P2，P1P1是是是是天体光谱数据特征的非空子模式，天体光谱数据特征的非空子模式，天体光谱数据特征的非空子模式，天体光谱数据特征的非空子模式，P2P2是物理化学性质的是物理化学性质的是物理化学性质的是物

44、理化学性质的非空子模式，如果非空子模式，如果非空子模式，如果非空子模式，如果 (P1(P1 P2/DB)/P2/DB)/(P1/DB)P1/DB)minmin，则生成一条关联规则，则生成一条关联规则，则生成一条关联规则，则生成一条关联规则“P1P1 P2”P2”。体系结构与功能体系结构与功能体系结构与功能体系结构与功能 主 程 序数据预处理背景知识获取CFP树构造频繁模式提取关联规则挖掘预处理参数输入挖掘结果输出用户接口 规则提取FP树的构造 频繁模式挖掘归一化恒星光谱库恒星光谱数据离散化运行结果及分析运行结果及分析运行结果及分析运行结果及分析 退回引言引言引言引言 离群数据识别的主要方法：离

45、群数据识别的主要方法：离群数据识别的主要方法：离群数据识别的主要方法：距离的方法、统计的方法、局部密度的方法和基于偏距离的方法、统计的方法、局部密度的方法和基于偏距离的方法、统计的方法、局部密度的方法和基于偏距离的方法、统计的方法、局部密度的方法和基于偏离模型的方法等。离模型的方法等。离模型的方法等。离模型的方法等。大多数的方法是从全局的观点看待离群数据，很难发大多数的方法是从全局的观点看待离群数据，很难发大多数的方法是从全局的观点看待离群数据，很难发大多数的方法是从全局的观点看待离群数据，很难发现低维子空间中的偏移数据，而且很难应用于高维数据。现低维子空间中的偏移数据，而且很难应用于高维数据

46、。现低维子空间中的偏移数据，而且很难应用于高维数据。现低维子空间中的偏移数据，而且很难应用于高维数据。C C C.AgarwalC.Agarwal等人在等人在等人在等人在20052005年提出了一种基于子空间的年提出了一种基于子空间的年提出了一种基于子空间的年提出了一种基于子空间的高维离群数据识别算法，该算法采用遗传算法搜索离群数据。高维离群数据识别算法，该算法采用遗传算法搜索离群数据。高维离群数据识别算法，该算法采用遗传算法搜索离群数据。高维离群数据识别算法，该算法采用遗传算法搜索离群数据。C C C.Agarwal,PC.Agarwal,P S.YuS.Yu.An effective an

47、d efficient algorithm.An effective and efficient algorithm for high-dimensional outlier detectionfor high-dimensional outlier detection，The International The International Journal on Very Large Data BasesJournal on Very Large Data Bases，2005,14(2)2005,14(2)：211 221211 221 存在问题：存在问题：存在问题：存在问题：仅利用稀疏度系

48、数，在子空间中来考察数据的行为，仅利用稀疏度系数，在子空间中来考察数据的行为，仅利用稀疏度系数，在子空间中来考察数据的行为，仅利用稀疏度系数，在子空间中来考察数据的行为，无法避免由于正常数据的稀疏，导致在子空间中也是稀疏的无法避免由于正常数据的稀疏，导致在子空间中也是稀疏的无法避免由于正常数据的稀疏，导致在子空间中也是稀疏的无法避免由于正常数据的稀疏，导致在子空间中也是稀疏的不足，因此识别结果不是准确的；不足，因此识别结果不是准确的；不足，因此识别结果不是准确的；不足，因此识别结果不是准确的；不能确保能发现稀疏度系数最小的子空间，进而发现不能确保能发现稀疏度系数最小的子空间，进而发现不能确保能

49、发现稀疏度系数最小的子空间，进而发现不能确保能发现稀疏度系数最小的子空间，进而发现的离群数据也不够准确，该文献中的实验也验证了这一点；的离群数据也不够准确，该文献中的实验也验证了这一点；的离群数据也不够准确，该文献中的实验也验证了这一点；的离群数据也不够准确，该文献中的实验也验证了这一点；不能确保发现所有满足条件的离群数据，识别结果的不能确保发现所有满足条件的离群数据，识别结果的不能确保发现所有满足条件的离群数据，识别结果的不能确保发现所有满足条件的离群数据，识别结果的完备性得不到保证。完备性得不到保证。完备性得不到保证。完备性得不到保证。概念格概念格概念格概念格,由由由由WilleWille

50、 R R 提出提出提出提出,是一种支持数据分析和知是一种支持数据分析和知是一种支持数据分析和知是一种支持数据分析和知识发现的一种有效工具。识发现的一种有效工具。识发现的一种有效工具。识发现的一种有效工具。每个节点是一个形式概念每个节点是一个形式概念每个节点是一个形式概念每个节点是一个形式概念,由由由由外延外延外延外延和和和和内涵内涵内涵内涵两部分组成。两部分组成。两部分组成。两部分组成。通过通过通过通过HasseHasse 图生动和简洁地体现了这些概念之间的图生动和简洁地体现了这些概念之间的图生动和简洁地体现了这些概念之间的图生动和简洁地体现了这些概念之间的泛化泛化泛化泛化和和和和特化特化特化