天體光譜數(shù)據(jù)挖掘技術(shù)

1、天體光譜數(shù)據(jù)挖掘技術(shù),太原科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院張繼福 2008年11月,一、概 述 1）數(shù)據(jù)挖掘 2）天體光譜數(shù)據(jù)挖掘 3）課題的研究意義二、主要研究工作 1）基于約束FP樹的天體光譜數(shù)據(jù)相關(guān)性分析 2）基于概念格的天體光譜離群數(shù)據(jù)挖掘,數(shù)據(jù)挖掘,定義：數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含的、未知的、潛在的有用信息

2、和知識，為決策支持服務(wù)。 主要任務(wù)：關(guān)聯(lián)規(guī)則、分類、聚類、離群數(shù)據(jù)等。 常用的方法有：關(guān)聯(lián)規(guī)則、決策樹、神經(jīng)網(wǎng)絡(luò)、遺傳算法、粗糙集、模糊集、概念格、統(tǒng)計分析等。,天體光譜數(shù)據(jù)挖掘,我國正在建造一臺大天區(qū)面積多目標(biāo)光纖光譜望遠(yuǎn)鏡（LAMOST），是國家重大科學(xué)工程項目，也是世界上光譜獲取率最高的望遠(yuǎn)鏡。 預(yù)計LAMOST所觀測到的光譜數(shù)據(jù)容量將有可能達(dá)到4TB。

3、 急需一種新的以計算機(jī)為主的數(shù)據(jù)分析技術(shù), 分析和識別如此龐大的海量光譜數(shù)據(jù)。 天體光譜數(shù)據(jù)處理主要內(nèi)容:預(yù)處理(去噪、歸一化等)、分類與識別、測量（紅移等參數(shù)）等。,一條Seyfert 2 光譜數(shù)據(jù)圖(紅移為0) 天體光譜是天體電磁輻射按照波長的有序排列，蘊含著天體的重要物理信息，例如：天體的化學(xué)成份、天體的表面溫度、直徑、質(zhì)量、光度以及天體的視向運動和自轉(zhuǎn)。天文學(xué)家和天體物理學(xué)家

4、通過分析天體光譜的信息，不僅可以研究宇宙中物質(zhì)的分布特征，還可以研究天體的形成和隨時間的演化等重大科學(xué)問題。,主要的方法 交叉相關(guān)分析與主成分分析（PCA）、人工神經(jīng)網(wǎng)絡(luò)、小波變換、貝葉斯統(tǒng)計、SVM等。 典型的成果 1） Autoclass，基于貝葉斯統(tǒng)計的一種光譜分類方法，發(fā)現(xiàn)了一些以前未注意的光譜類型和譜線； 2） Gulati等人采

5、用兩層BP神經(jīng)網(wǎng)絡(luò)方法，用于恒星光譜次型的分類； 3）Ellis等人采用交叉相關(guān)分析對光譜進(jìn)行分類； 4）邱波等人采用基于粗糙集的方法，進(jìn)行了恒星光譜的分類識別； 5）覃冬梅等人采用基于主分量分析法的二維恒星特征空間的快速光譜識別方法； 6）劉中田等人提出基于小波特征的M型星自動識別方法等。,課題的研究意義 由于天文界對宇宙的認(rèn)識還比較有限，

6、LAMOST巡天計劃的一個重要任務(wù)是要發(fā)現(xiàn)一些新的、特殊類型的天體，因此，如何利用數(shù)據(jù)挖掘技術(shù)從海量天體光譜數(shù)據(jù)中發(fā)現(xiàn)未知的、特殊的天體及天體規(guī)律是數(shù)據(jù)挖掘值得研究和探索的新應(yīng)用領(lǐng)域。 面向特定任務(wù)的數(shù)據(jù)挖掘是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域發(fā)展的趨勢之一。以LAMOST項目為背景，對天體光譜數(shù)據(jù)挖掘技術(shù)進(jìn)行了研究，其研究成果不僅具有重要的理論價值，而且可直接應(yīng)用到LAMOST中，為國家重大科學(xué)工程提供技術(shù)支撐

7、。,退回,引言,關(guān)聯(lián)規(guī)則描述了屬性之間的關(guān)聯(lián)程度，也就是說有效地描述了數(shù)據(jù)集屬性之間的相關(guān)性關(guān)系。利用關(guān)聯(lián)規(guī)則來描述天體光譜數(shù)據(jù)特征與其物理化學(xué)性質(zhì)之間存在的、未知的相關(guān)性是可行性的，具有重要的應(yīng)用價值。頻繁模式集的生成是提高關(guān)聯(lián)規(guī)則挖掘效率的關(guān)鍵。,頻繁模式生成主要有：Apriori和FP兩類算法。Apriori算法 優(yōu)點: 思路比較清晰，以遞歸統(tǒng)計為基礎(chǔ)，剪枝生成頻繁集； 缺點: 在生成頻繁模式過程

8、中，需要產(chǎn)生大量的候選項和多次遍歷數(shù)據(jù)庫，I/O代價太高，難以適應(yīng)海量高維數(shù)據(jù)。FP算法 優(yōu)點: (l) 通過對FP樹的遞歸訪問，產(chǎn)生頻繁模式集，僅需要構(gòu)造FP樹和條件FP樹，不需要產(chǎn)生候選項集； (2) 對事務(wù)數(shù)據(jù)庫僅需兩次遍歷，第l次遍歷產(chǎn)生頻繁l-項集，第2次遍歷用于構(gòu)造FP樹，從而降低了訪問數(shù)據(jù)庫的次數(shù)。 缺點: FP樹需要占用大量內(nèi)存。,約束FP樹及其構(gòu)造,一階

9、謂詞邏輯與背景知識 數(shù)據(jù)挖掘是從宏觀角度利用積累的巨量數(shù)據(jù)進(jìn)行知識抽象的高級階段，是一項高級的智能活動，因此數(shù)據(jù)挖掘過程離不開背景知識的支持。 關(guān)聯(lián)規(guī)則挖掘過程也離不開背景知識的支持。 面向關(guān)聯(lián)規(guī)則挖掘的背景知識實際上是描述數(shù)據(jù)集中的對象與屬性之間、屬性與屬性之間的約束關(guān)系，因此采用一階謂詞邏輯描述關(guān)聯(lián)規(guī)則挖掘中的背景知識是可行的。,定義3-1 設(shè)r 是交易數(shù)據(jù)庫中的

10、關(guān)系表名個體變量，f 是表示關(guān)系表到屬性的映射的函詞，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(

11、f(r)) ® Interesting (f(r)) 定義3-3 設(shè)D為交易數(shù)據(jù)庫，?min為最小支持度，G為背景知識，如果L是一頻繁模式，且G（L）=True，則稱L為約束頻繁模式。,CFP-tree及構(gòu)造 定義3-4 設(shè)G為背景知識，對于任意頻繁模式樹FP-tree，如果從根節(jié)點到葉子節(jié)點的路徑中，所描述的任一頻繁模式P，使得G（P）=True，則稱FP-Tree為約束頻繁模式樹CFP-tree。

12、 構(gòu)造思想與方法: 只有數(shù)據(jù)庫中的事務(wù)T滿足G所構(gòu)造出的FP-Tree，才能包含用戶感興趣的約束頻繁模式，可采用兩次掃描數(shù)據(jù)庫來完成CFP-tree的構(gòu)造 。,定理2-1 設(shè)D為一個交易數(shù)據(jù)庫、?min為最小支持度、G為背景知識，所構(gòu)造出的約束FP樹為CFP-tree，則從CFP-tree提取出的任意頻繁模式P，一定是滿足G（P）=true（即約束頻繁模式）。 定理2-2 設(shè)D為一個交易數(shù)

13、據(jù)庫、?min為最小支持度、G為背景知識，所構(gòu)造出的約束FP樹為CFP-tree，P為任意頻繁模式，若G（P）= true（即約束頻繁模式），則P一定是CFP-tree中的頻繁模式。,定理2-3 CFP-tree是FP-tree的子集。 定理2-4 設(shè)D為一個交易數(shù)據(jù)庫、G1，G2為背景知識，且G1G2、T1，T2分別是基于G1，G2構(gòu)造的CFP-tree，則T1T2。（約束的單調(diào)性） 推論3-1 設(shè)D為

14、一個交易數(shù)據(jù)庫、G1，G2為背景知識，T1，T2分別是基于G1，G2構(gòu)造的CFP-tree，當(dāng)G1=G2時T1=T2。(約束的唯一性),推論3-2 設(shè)D為一個交易數(shù)據(jù)庫、G1為背景知識，TCFP是基于G1構(gòu)造的CFP-tree，TFP是數(shù)據(jù)庫D的FP-tree，當(dāng)G1=ф時TCFP=TFP。 定理3-5 設(shè)D為一個交易數(shù)據(jù)庫、?min為一個最小支持度、G為背景知識，構(gòu)造出的約束FP樹為CFP-tree，由G將交易數(shù)據(jù)庫分為

15、兩部分，即：D=D1∪D2,其中：?T∈D1，那么G（T）=True， ?T∈D2，G（T）=False， 如果對于D1，采用傳統(tǒng)FP-tree構(gòu)造方法的FP樹為FP-Tree1，則CFP-tree與FP-Tree1是同一棵樹。,約束FP樹的構(gòu)造算法 算法描述及分析（見P23-24） 實驗分析 硬件：PentiumIV-2.0G CPU ，512M 內(nèi)存； 軟件：Wi

16、ndows XP 操作系統(tǒng)，DBMS 為ORACLE9i，VC++為編程語言； 數(shù)據(jù)預(yù)處理：(8400 條SDSS恒星光譜數(shù)據(jù)) 1）選定間隔為20 Å的200個波長，離散化為十三種值； 2）溫度等間隔離散化為三種值，七類恒星溫度離散化為二十一種值； 3）光度、化學(xué)分度、微湍流等間隔離散化為三種值。,表3-2 約束FP樹構(gòu)造效率比較1（|DB

17、|=6000，單位：秒）,,表3-3 約束FP樹構(gòu)造效率比較2（?min =3%，單位：秒）,,表3-4 約束頻繁模式（|DB|=8400，?min =1%，單位：個）,基于CFP樹的天體光譜數(shù)據(jù)相關(guān)性分析系統(tǒng),天體光譜數(shù)據(jù)預(yù)處理 歸一化 離散化（表3-5 　恒星光譜數(shù)據(jù)離散化參數(shù)）天體光譜知識表示 給定一個天體光譜數(shù)據(jù)庫DB={I1,I2,?,Im}為DB中m條光譜數(shù)據(jù)的集合，DB中每

18、一條光譜Ii就是I中的一組項目子集，即Ii? I，其中： I = { A1,A2,…,An ,S1,S2 ,…,Sm }， Ai為第i波長處的離散化特征屬性，Sj第j個物理化學(xué)性質(zhì)的離散化屬性。,定義3-5 設(shè)r 是天體光譜數(shù)據(jù)庫中的關(guān)系表名個體變量，f 是表示關(guān)系表到屬性的映射的函詞，?min 是最小支持度（0≤?min≤1），則天體光譜知識G可由如下謂詞公式，通過邏輯運算符組成合適公

19、式。 (1) Interesting (f(r)) (2) support(f(r), ?min) ® Interesting (f(r)) (3) Interested(f(r)) ® Interesting (f(r)) 對于任意天體光譜知識G，G是由定義3-5中的三類謂詞公式，通過邏輯運算符組成的合適公式，由文

20、獻(xiàn)[56]可知，G可化簡為合取范式，并用子句集S來表示。,定理3-6 設(shè)S是表示天體光譜知識G的子句集，任一子句s∈S是由謂詞Interesting (f(r)) 、support(f(r), ?min) 、Interested(f(r))所表達(dá)的若干有限文字析取式，且下列公式成立。 Interesting (f1(r1)) ?support(f2(r1), ?min) ?Interested(f3(r1)) ?Int

21、eresting（f1(r1) ?f2(r1) ? f3(r1)） 定理3-7 設(shè)S是表示天體光譜知識G的子句集，任一子句s∈S是感興趣的天體光譜模式。 推論3-1 設(shè)G為天體光譜知識，則G描述了一組感性趣的天體光譜模式，即天體光譜模式集。,天體光譜數(shù)據(jù)的頻繁模式提取與關(guān)聯(lián)規(guī)則挖掘 CFP樹的遍歷： 創(chuàng)建一個項頭表，使得每個項通過一個節(jié)點鏈指向它在樹中的位置。提取過程從1頻繁模式開始，構(gòu)

22、造它的條件模式基； 然后構(gòu)造它的條件CFP樹，并遞歸地在該樹上進(jìn)行提取。 關(guān)聯(lián)規(guī)則生成： 對于任一頻繁模式P?L，其中：P=P1?P2，P1是天體光譜數(shù)據(jù)特征的非空子模式，P2是物理化學(xué)性質(zhì)的非空子模式，如果?( P1?P2/DB)/ ?( P1/DB)≥?min，則生成一條關(guān)聯(lián)規(guī)則“P1? P2”。,,體系結(jié)構(gòu)與功能,,運行結(jié)果及分析,退回,引言,離群數(shù)據(jù)識別的主要方法： 距離的方

23、法、統(tǒng)計的方法、局部密度的方法和基于偏離模型的方法等。 大多數(shù)的方法是從全局的觀點看待離群數(shù)據(jù)，很難發(fā)現(xiàn)低維子空間中的偏移數(shù)據(jù)，而且很難應(yīng)用于高維數(shù)據(jù)。,C C.Agarwal等人在2005年提出了一種基于子空間的高維離群數(shù)據(jù)識別算法，該算法采用遺傳算法搜索離群數(shù)據(jù)。 C C.Agarwal,P S.Yu. An effective

24、 and efficient algorithm for high-dimensional outlier detection，The International Journal on Very Large Data Bases，2005, 14 ( 2)：211 – 221 存在問題： ①僅利用稀疏度系數(shù)，在子空間中來考察數(shù)據(jù)的行為，無法避免由于正常數(shù)據(jù)的稀疏，導(dǎo)致在子空間中也是稀疏的不

25、足，因此識別結(jié)果不是準(zhǔn)確的； ②不能確保能發(fā)現(xiàn)稀疏度系數(shù)最小的子空間，進(jìn)而發(fā)現(xiàn)的離群數(shù)據(jù)也不夠準(zhǔn)確，該文獻(xiàn)中的實驗也驗證了這一點； ③不能確保發(fā)現(xiàn)所有滿足條件的離群數(shù)據(jù)，識別結(jié)果的完備性得不到保證。,概念格, 由Wille R 提出, 是一種支持?jǐn)?shù)據(jù)分析和知識發(fā)現(xiàn)的一種有效工具。 每個節(jié)點是一個形式概念, 由外延和內(nèi)涵兩部分組成。 通過Hasse 圖

26、生動和簡潔地體現(xiàn)了這些概念之間的泛化和特化關(guān)系。 具有知識表示的完備性、直觀性和簡潔性等特點。 將概念格中每個概念內(nèi)涵看作子空間，內(nèi)涵看作子空間所包含的對象，從而用概念格結(jié)點，描述子空間中的離群數(shù)據(jù)，是可行的。,基于概念格的低維子空間離群數(shù)據(jù),在稀疏子空間中，稀疏度系數(shù)僅反映了子空間中包含的數(shù)據(jù)對象個數(shù)遠(yuǎn)小于期望值，但數(shù)據(jù)對象個數(shù)遠(yuǎn)小于期望值，可能是數(shù)據(jù)對象在更低維子空間上的過度稀疏造成的，

27、稀疏度系數(shù)并不能正確反映稀疏子空間上的數(shù)據(jù)偏離程度。因此僅采用S(D)來判斷稀疏子空間的方法，不能保證結(jié)果的準(zhǔn)確性。 數(shù)學(xué)期望表示了子空間中對象的平均個數(shù)，引入一個用戶設(shè)置的系數(shù)，采用它們的乘積來度量子空間的稠密程度。,定義4-1 對于一個任意的數(shù)據(jù)集，其屬性集為M，對象集為G，且每維均離散化為?個區(qū)間，DENSE為用戶設(shè)置的稠密度系數(shù)， ?由約簡屬性集P(P?M)構(gòu)成的約簡子空間D，且其包含的對象集為A(A?

28、G),若|A|?DENSE*|G|*(1/?)|D|，則稱D為稠密子空間。 定義4-2 對于一個任意的數(shù)據(jù)集，其屬性集為M，對象集為G，?由約簡屬性集P(P?M)構(gòu)成的稀疏子空間D，且其包含的對象集為A(A?G)，若?由約簡屬性集P1(P1?P)構(gòu)成的約簡子空間D1，均為稠密子空間，則稱D為離群子空間，A中的數(shù)據(jù)對象為離群數(shù)據(jù)。,定義4-3 設(shè)K=(G,M,I)為任意形式背景，?h=(A，B)?L(G,M,I)，如果屬性集

29、合B1滿足下述兩個條件，則它被稱為h的一個內(nèi)涵縮減。 B1?= B? = A B2? ? B1? = A (for any B2 ? B1) 定義4-4 設(shè)K=(G,M,I)為任意形式背景，?h=(A，B)?L(G,M,I)，h的內(nèi)涵縮減集為RED={Bi| Bi為h的內(nèi)涵縮減}，若? Bi?RED，滿足由屬性集Bi構(gòu)成的子空間S為稀疏子空間，則稱h為稀疏概念，若?由約

30、簡屬性集P(P?Bi)構(gòu)成的約簡子空間S1為稠密子空間，則稱概念h為離群概念，A中包含的數(shù)據(jù)對象為離群數(shù)據(jù)。,定理4-1 對于一個任意的數(shù)據(jù)集，其屬性集為M，對象集為G，K=(G,M,I)為其對應(yīng)的形式背景，?由約簡屬性集P（P? M）構(gòu)成的約簡子空間D，及包含在D中的對象集O（即O= P?），則?h=(A，B)?L(G,M,I)，及h的內(nèi)涵縮減集RED={Bi| Bi為h的內(nèi)涵縮減}，使得P?RED，O= A成立。

31、 定理4-2 對于一個任意的數(shù)據(jù)集，其屬性集為M，對象集為G，K=(G,M,I)為其對應(yīng)的形式背景，?由約簡屬性集P(P?M)構(gòu)成的離群子空間D，及其包含的離群數(shù)據(jù)集O(O ? G)，則在概念格L(G,M,I)中，必?一個離群概念h=(A,B)?L(G,M,I)，及h的內(nèi)涵縮減集RED={Bi|Bi為h的內(nèi)涵縮減},使得P?RED，A=O成立。,定理4-3 設(shè)K=(G,M,I)為任意形式背景，?h=(A,B)?L(G,M,I)，

32、P為h的一個內(nèi)涵縮減，則? 約簡屬性集P1 (P1?P)，必? h1=(A1, B1) ?L(G,M,I)，使得P1為h1的內(nèi)涵縮減，且B1?B。 定理4-4 設(shè)K=(G,M,I)為任意形式背景，?h=(A,B)?L(G,M,I)，若P1為h的一個內(nèi)涵縮減，且若由P1構(gòu)成的子空間D1為稀疏子空間，則當(dāng)稠密度系數(shù)DENSE=0時，A中包含的數(shù)據(jù)對象是離群數(shù)據(jù)。,基于概念格的低維子空間離群數(shù)據(jù)挖掘算法,算法描述CLOM 算法分

33、析 實驗分析 硬件：PentiumIV-2.0G CPU ，512M 內(nèi)存， 軟件：Windows XP 操作系統(tǒng)，DBMS 為ORACLE9i，VC++為編程語言 形式背景：（SDSS恒星光譜數(shù)據(jù)） 1)選定間隔為20的200個波長， 作為屬性集； 2)依據(jù)每一波長處的流量、峰寬和形狀，將其離散化為十三種數(shù)值之一，并作為該波

34、長處取值。,表2-2 不同對象的建格與挖掘時間比較(TS=-1，DENSE=1.2),表2-3 不同TS值的挖掘時間和離群數(shù)據(jù)數(shù) (DENSE=1.2，記錄數(shù)8315),表2-4 不同DENSE值的挖掘時間和離群數(shù)據(jù)(TS=-1.7，記錄數(shù)8315),基于概念格的天體光譜離群數(shù)據(jù)挖掘系統(tǒng),天體光譜數(shù)據(jù)與形式背景 在流量離散化處理中，不僅要描述天體光譜波長處的流量強度和峰寬，同時還應(yīng)描述波的形狀，即：吸收線

35、還是發(fā)射線，故對于光譜不僅需考慮波長處的強度和峰寬兩個因素，而且還需要考慮波的形狀。 可以利用三個特征變量I、J、W來描述光譜在某一波長處的特征，I表示光譜波的強度，J表示光譜波峰的寬度，W表示光譜波的形狀。從而將天體光譜數(shù)據(jù)中各個波長處的數(shù)據(jù)，轉(zhuǎn)變?yōu)橐蕴卣髯兞縄、J和W表示的特征數(shù)據(jù)。如果某一條光譜圖中包含著的波長為A=[Ai]，i=1，2，3，…n ，其中Ai表示i個波長處的光譜特征，n表示共有n個波長，那么A

36、i可表示為Ai={Ii，Ji，Wi} 。,表4-3 光譜數(shù)據(jù)離散化,光譜數(shù)據(jù)按照上述方法及表4-3離散化后，形成了天體光譜數(shù)據(jù)的形式背景，從而適應(yīng)于天體光譜數(shù)據(jù)概念格的構(gòu)造。,功能與體系結(jié)構(gòu),,開發(fā)環(huán)境與工具 采用VC++和Oracle9i作為開發(fā)工具，在PentiumIV-3.0G CPU，512M內(nèi)存，Windows XP操作系統(tǒng)上，實現(xiàn)了天體光譜數(shù)據(jù)離群挖掘系統(tǒng)。 關(guān)鍵模塊的實現(xiàn)技術(shù)

37、 一、基于鏈表結(jié)構(gòu)的概念格格構(gòu)造 二、STL和ADO技術(shù),運行結(jié)果及分析 將以文本存儲的歸一化后的光譜數(shù)據(jù)導(dǎo)入到oracle數(shù)據(jù)庫中。數(shù)據(jù)包括光譜數(shù)據(jù)的fit文件名、sn_g信噪比、紅移值、44根特征線的高度及等值寬度，每條光譜數(shù)據(jù)一共是91維，圖4-6為導(dǎo)入的5412條高紅移類星體的運行界面。,數(shù)據(jù)離散化,概念格,離群數(shù)據(jù),小結(jié),提出了一種基于約束FP樹的天體光譜數(shù)據(jù)相關(guān)性分析技術(shù)。

38、 首先采用一階謂詞邏輯作為背景知識表示技術(shù)，提出了一種新的FP樹，約束FP樹或CFP樹，并給出了其構(gòu)造算法CFP-Construct，從而降低了FP樹構(gòu)造的復(fù)雜性，提高了關(guān)聯(lián)規(guī)則挖掘結(jié)果的針對性。其次，采用基于約束FP樹的關(guān)聯(lián)規(guī)則挖掘方法作為天體光譜數(shù)據(jù)相關(guān)性分析手段，提出了一種新的基于約束FP樹的天體光譜數(shù)據(jù)相關(guān)性分析。最后，采用VC ++ 和Oracle9i 作為開發(fā)工具，設(shè)計并實現(xiàn)了天體光譜數(shù)據(jù)相關(guān)性分析原

39、型系統(tǒng)，實驗結(jié)果分析表明，該相關(guān)性分析方法是可行的和有價值的。 提出了一種基于概念格的天體光譜離群數(shù)據(jù)挖掘技術(shù)。 首先，通過定義和分析了度量低維子空間離群數(shù)據(jù)的稀疏度系數(shù)和稠密度系數(shù)，將概念格中每個概念內(nèi)涵看作子空間，提出了一種基于概念格的低維子空間離群數(shù)據(jù)挖掘算法CLOM。其次，將概念節(jié)點的內(nèi)涵縮減看作天體光譜特征子空間，，提出了一種基于CLOM算法天體光譜離群數(shù)據(jù)識別方法。最后，采用VC ++ 和Oracl