1、天體光譜數據挖掘技術太原科技大學計算機科學與技術學院張繼福 2008年11月一、概 述 1）數據挖掘 2）天體光譜數據挖掘 3）課題的研究意義二、主要研究工作 1）基于約束FP樹的天體光譜數據相關性分析 2）基于概念格的天體光譜離群數據挖掘 數據挖掘 定義：數據挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含的、未知的、潛在的有用信息和知識，為決策支持服務。 主要任務：關聯規則、分類、聚類、離群數據等。 常用的方法有：關聯規則、決策樹、神經網絡、遺傳算法、粗糙集、模糊集、概念格、統計分析等。天體光譜數據挖掘 我國正在建造一臺大天區面積多目標光纖光譜望遠鏡（LAMOST），是

2、國家重大科學工程項目，也是世界上光譜獲取率最高的望遠鏡。 預計LAMOST所觀測到的光譜數據容量將有可能達到4TB。 急需一種新的以計算機為主的數據分析技術, 分析和識別如此龐大的海量光譜數據。 天體光譜數據處理主要內容:預處理(去噪、歸一化等)、分類與識別、測量（紅移等參數）等。 一條Seyfert 2 光譜數據圖(紅移為0) 天體光譜是天體電磁輻射按照波長的有序排列，蘊含著天體的重要物理信息，例如：天體的化學成份、天體的表面溫度、直徑、質量、光度以及天體的視向運動和自轉。天文學家和天體物理學家通過分析天體光譜的信息，不僅可以研究宇宙中物質的分布特征，還可以研究天體的形成和隨時間的演化等重大

3、科學問題。主要的方法 交叉相關分析與主成分分析（PCA）、人工神經網絡、小波變換、貝葉斯統計、SVM等。 典型的成果 1） Autoclass，基于貝葉斯統計的一種光譜分類方法，發現了一些以前未注意的光譜類型和譜線； 2） Gulati等人采用兩層BP神經網絡方法，用于恒星光譜次型的分類； 3）Ellis等人采用交叉相關分析對光譜進行分類； 4）邱波等人采用基于粗糙集的方法，進行了恒星光譜的分類識別； 5）覃冬梅等人采用基于主分量分析法的二維恒星特征空間的快速光譜識別方法； 6）劉中田等人提出基于小波特征的M型星自動識別方法等。 課題的研究意義 由于天文界對宇宙的認識還比較有限，LAMOST巡

4、天計劃的一個重要任務是要發現一些新的、特殊類型的天體，因此，如何利用數據挖掘技術從海量天體光譜數據中發現未知的、特殊的天體及天體規律是數據挖掘值得研究和探索的新應用領域。 面向特定任務的數據挖掘是當前數據挖掘領域發展的趨勢之一。以LAMOST項目為背景，對天體光譜數據挖掘技術進行了研究，其研究成果不僅具有重要的理論價值，而且可直接應用到LAMOST中，為國家重大科學工程提供技術支撐。 退回引言關聯規則描述了屬性之間的關聯程度，也就是說有效地描述了數據集屬性之間的相關性關系。利用關聯規則來描述天體光譜數據特征與其物理化學性質之間存在的、未知的相關性是可行性的，具有重要的應用價值。頻繁模式集的生成

5、是提高關聯規則挖掘效率的關鍵。頻繁模式生成主要有：Apriori和FP兩類算法。Apriori算法 優點: 思路比較清晰，以遞歸統計為基礎，剪枝生成頻繁集； 缺點: 在生成頻繁模式過程中，需要產生大量的候選項和多次遍歷數據庫，I/O代價太高，難以適應海量高維數據。FP算法 優點: (l) 通過對FP樹的遞歸訪問，產生頻繁模式集，僅需要構造FP樹和條件FP樹，不需要產生候選項集； (2) 對事務數據庫僅需兩次遍歷，第l次遍歷產生頻繁l-項集，第2次遍歷用于構造FP樹，從而降低了訪問數據庫的次數。 缺點: FP樹需要占用大量內存。約束FP樹及其構造 一階謂詞邏輯與背景知識 數據挖掘是從宏觀角度利用

6、積累的巨量數據進行知識抽象的高級階段，是一項高級的智能活動，因此數據挖掘過程離不開背景知識的支持。 關聯規則挖掘過程也離不開背景知識的支持。 面向關聯規則挖掘的背景知識實際上是描述數據集中的對象與屬性之間、屬性與屬性之間的約束關系，因此采用一階謂詞邏輯描述關聯規則挖掘中的背景知識是可行的。 定義3-1 設r 是交易數據庫中的關系表名個體變量，f 是表示關系表到屬性的映射的函詞，k 是支持度（0k1），則背景知識G可由如下謂詞公式，通過邏輯運算符組成合適公式。 (1) Interesting (f(r) (2) support(f(r),k) Interesting (f(r) (3) Inte

7、rested(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，才能包含用戶感興趣的約束頻繁模式，可采用兩次掃描

8、數據庫來完成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-3 CFP-tree是FP-tree的子集。 定理2-4 設D為一個交易數據庫、G1，G2為背景知識，且G1G2、T1，T2分別是基于G1，

9、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=D1D2,其中：TD1，那么G（T）=True， TD2，G（T）=False， 如果

10、對于D1，采用傳統FP-tree構造方法的FP樹為FP-Tree1，則CFP-tree與FP-Tree1是同一棵樹。約束FP樹的構造算法 算法描述及分析（見P23-24） 實驗分析 硬件：PentiumIV-2.0G CPU ，512M 內存； 軟件：Windows XP 操作系統，DBMS 為ORACLE9i，VC+為編程語言； 數據預處理：(8400 條SDSS恒星光譜數據) 1）選定間隔為20 的200個波長，離散化為十三種值； 2）溫度等間隔離散化為三種值，七類恒星溫度離散化為二十一種值； 3）光度、化學分度、微湍流等間隔離散化為三種值。 表3-2 約束FP樹構造效率比較1（|DB|=

11、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化

12、學豐度_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 是最小支持度（0min1），則天體

13、光譜知識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的子句集，任一子句sS是由謂詞Interesting (f(r) 、support(f(r), min) 、Interested(f(r)所表達的若干有限文字

14、析取式，且下列公式成立。 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描述了一組感性趣的天體光譜模式，即天體光譜模式集。 天體光譜數據的頻繁模式提取與關聯規則挖掘 CFP樹的遍歷： 創建一個項頭表，使得每個項通過一個節點鏈指向它在樹中的位置。提取過程從1頻繁模式開始，構造它的條件模式基； 然后構造它的條件CFP樹，并遞歸地在該樹上進行提

15、取。 關聯規則生成： 對于任一頻繁模式PL，其中：P=P1P2，P1是天體光譜數據特征的非空子模式，P2是物理化學性質的非空子模式，如果( P1P2/DB)/ ( P1/DB)min，則生成一條關聯規則“P1 P2”。 體系結構與功能 主 程 序數據預處理背景知識獲取CFP樹構造頻繁模式提取關聯規則挖掘預處理參數輸入挖掘結果輸出用戶接口 規則提取FP樹的構造 頻繁模式挖掘歸一化恒星光譜庫恒星光譜數據離散化運行結果及分析 退回引言 離群數據識別的主要方法： 距離的方法、統計的方法、局部密度的方法和基于偏離模型的方法等。 大多數的方法是從全局的觀點看待離群數據，很難發現低維子空間中的偏移數據，而且

16、很難應用于高維數據。 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 存在問題： 僅利用稀疏度系數，在子空間中來考察數據的行為，無法避免由于正常數據的稀疏，導致在子空間中也是稀疏的不足，因此識別

17、結果不是準確的； 不能確保能發現稀疏度系數最小的子空間，進而發現的離群數據也不夠準確，該文獻中的實驗也驗證了這一點； 不能確保發現所有滿足條件的離群數據，識別結果的完備性得不到保證。 概念格, 由Wille R 提出, 是一種支持數據分析和知識發現的一種有效工具。 每個節點是一個形式概念, 由外延和內涵兩部分組成。 通過Hasse 圖生動和簡潔地體現了這些概念之間的泛化和特化關系。 具有知識表示的完備性、直觀性和簡潔性等特點。 將概念格中每個概念內涵看作子空間，內涵看作子空間所包含的對象，從而用概念格結點，描述子空間中的離群數據，是可行的。基于概念格的低維子空間離群數據 在稀疏子空間中，稀疏度

18、系數僅反映了子空間中包含的數據對象個數遠小于期望值，但數據對象個數遠小于期望值，可能是數據對象在更低維子空間上的過度稀疏造成的，稀疏度系數并不能正確反映稀疏子空間上的數據偏離程度。因此僅采用S(D)來判斷稀疏子空間的方法，不能保證結果的準確性。 數學期望表示了子空間中對象的平均個數，引入一個用戶設置的系數，采用它們的乘積來度量子空間的稠密程度。 定義4-1 對于一個任意的數據集，其屬性集為M，對象集為G，且每維均離散化為個區間，DENSE為用戶設置的稠密度系數， 由約簡屬性集P(PM)構成的約簡子空間D，且其包含的對象集為A(AG),若|A|DENSE*|G|*(1/)|D|，則稱D為稠密子空

19、間。 定義4-2 對于一個任意的數據集，其屬性集為M，對象集為G，由約簡屬性集P(PM)構成的稀疏子空間D，且其包含的對象集為A(AG)，若由約簡屬性集P1(P1P)構成的約簡子空間D1，均為稠密子空間，則稱D為離群子空間，A中的數據對象為離群數據。 定義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的內涵縮減，

20、若 BiRED，滿足由屬性集Bi構成的子空間S為稀疏子空間，則稱h為稀疏概念，若由約簡屬性集P(PBi)構成的約簡子空間S1為稠密子空間，則稱概念h為離群概念，A中包含的數據對象為離群數據。 定理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的內涵縮減，使得PRED，O= A成立。 定理4-2 對于一個任意的數據集，其屬性集為M，對象集為G，K=(G,M,I)為其對應的形式背景，由約簡屬性集P

21、(PM)構成的離群子空間D，及其包含的離群數據集O(O G)，則在概念格L(G,M,I)中，必一個離群概念h=(A,B)L(G,M,I)，及h的內涵縮減集RED=Bi|Bi為h的內涵縮減,使得PRED，A=O成立。 定理4-3 設K=(G,M,I)為任意形式背景，h=(A,B)L(G,M,I)，P為h的一個內涵縮減，則 約簡屬性集P1 (P1P)，必 h1=(A1, B1) L(G,M,I)，使得P1為h1的內涵縮減，且B1B。 定理4-4 設K=(G,M,I)為任意形式背景，h=(A,B)L(G,M,I)，若P1為h的一個內涵縮減，且若由P1構成的子空間D1為稀疏子空間，則當稠密度系數DEN

22、SE=0時，A中包含的數據對象是離群數據。 基于概念格的低維子空間離群數據挖掘算法 算法描述CLOM 算法分析 實驗分析 硬件：PentiumIV-2.0G CPU ，512M 內存， 軟件：Windows XP 操作系統，DBMS 為ORACLE9i，VC+為編程語言 形式背景：（SDSS恒星光譜數據） 1)選定間隔為20的200個波長， 作為屬性集； 2)依據每一波長處的流量、峰寬和形狀，將其離散化為十三種數值之一，并作為該波長處取值。 表2-2 不同對象的建格與挖掘時間比較(TS=-1，DENSE=1.2) 記錄條數建格時間離群挖掘時間離群數據數5000657s174s95500822s

23、213s76000861s234s670001184s435s1983151887s595s19表2-3 不同TS值的挖掘時間和離群數據數 (DENSE=1.2，記錄數8315) TS值離群挖掘時間離群數據數-0.3 872s60-0.8 750s31-1.2 591s19-1.7 356s6表2-4 不同DENSE值的挖掘時間和離群數據(TS=-1.7，記錄數8315) DENSE值離群挖掘時間離群數據數0.6 394s440.8 376s231 366s121.2 356s61.4 354s4基于概念格的天體光譜離群數據挖掘系統 天體光譜數據與形式背景 在流量離散化處理中，不僅要描述天體光

24、譜波長處的流量強度和峰寬，同時還應描述波的形狀，即：吸收線還是發射線，故對于光譜不僅需考慮波長處的強度和峰寬兩個因素，而且還需要考慮波的形狀。 可以利用三個特征變量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 。 表4-3 光譜數據離散化 光譜數據按照上述方法及表4-3離散化后，形成了天體光譜數據的形式背景，從而適應于天體光譜數據概念格的構造。 離散化值強度寬度類型離散化值強度寬度類型1弱窄吸收線7一般寬發射線2弱窄發射線8強寬發射線3一般窄發射線9一般窄吸收線4強窄發射線A一般寬吸收線5弱寬吸收線B強窄吸收線6弱寬發射線C強寬吸收線0無無無功能與體系結構 光譜數據離群挖掘系統數據預處理構造概念格離群數據挖掘數據導入光譜數據離散化一般概念格構造查看概念格文件離散表天體光譜歸一庫用戶接口概念格構造離群數據挖掘構造參數輸入