數(shù)據(jù)挖掘05數(shù)據(jù)立方體.ppt

1、數(shù)據(jù)立方體計(jì)算與數(shù)據(jù)泛化,數(shù)據(jù)泛化,數(shù)據(jù)泛化 數(shù)據(jù)庫中的數(shù)據(jù)和對(duì)象通常包含原始概念層的細(xì)節(jié)信息，數(shù)據(jù)泛化就是將數(shù)據(jù)庫中的跟任務(wù)相關(guān)的大型數(shù)據(jù)集從相對(duì)較低的概念層抽象到較高的概念層的過程。 主要方法： 數(shù)據(jù)立方體（OLAP使用的方法） 面向?qū)傩缘臍w納方法,1,2,3,4,5,概念層,(Month, city, customer_group),(Month, *, *),兩種不同類別的數(shù)據(jù)挖掘,從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描述性挖掘和預(yù)測(cè)性挖掘 描述性挖掘：以簡(jiǎn)潔概要的方式描述數(shù)據(jù)，并提供數(shù)據(jù)的有趣的一般性質(zhì)。 E.g. 數(shù)據(jù)泛化就是一種描述性數(shù)據(jù)挖掘 預(yù)測(cè)性數(shù)據(jù)挖掘：通過分析數(shù)據(jù)建立一個(gè)

2、或一組模型，并試圖預(yù)測(cè)新數(shù)據(jù)集的行為。 E.g 分類、回歸分析等,數(shù)據(jù)立方體的物化,數(shù)據(jù)立方體有利于多維數(shù)據(jù)的聯(lián)機(jī)分析處理 數(shù)據(jù)立方體使得從不同的角度對(duì)數(shù)據(jù)進(jìn)行觀察成為可能 方體計(jì)算（物化）的挑戰(zhàn)：海量數(shù)據(jù)，有限的內(nèi)存和時(shí)間 海量數(shù)據(jù)運(yùn)算對(duì)大量計(jì)算時(shí)間和存儲(chǔ)空間的要求,數(shù)據(jù)立方體-基本概念(1),數(shù)據(jù)立方體可以被看成是一個(gè)方體的格，每個(gè)方體用一個(gè)group-by表示 最底層的方體ABC是基本方體，包含所有3個(gè)維 最頂端的方體（頂點(diǎn)）只包含一個(gè)單元的值，泛化程度最高 上卷和下鉆操作與數(shù)據(jù)立方體的對(duì)應(yīng),P102 圖4-1,數(shù)據(jù)立方體-基本概念(2),基本方體的單元是基本單元，非基本方體的單元是聚集

3、單元 聚集單元在一個(gè)或多個(gè)維聚集，每個(gè)聚集維用*表示 E.g. (city, *, year, measure) m維方體：(a1,a2,.,an)中有m個(gè)不是* 祖先和子孫單元 i-D單元a=(a1,a2,.,an, measuresa)是j-D單元b=(b1,b2,.,bn, measureb)的祖先，當(dāng)且僅當(dāng) (1)ij，并且 (2)對(duì)于1m n，只要am *就有am=bm,冰山立方體 (1),為了確保快速的聯(lián)機(jī)分析，有時(shí)希望預(yù)計(jì)算整個(gè)立方體（所有方體的所有單元） n維數(shù)據(jù)立方體包含2n個(gè)方體 如果考慮概念分層 部分物化是存儲(chǔ)空間和響應(yīng)時(shí)間的折中方案 事實(shí)上，很多高維方體都是稀疏的（包含

4、很多度量值為0的單元）,冰山立方體 (2),對(duì)于稀疏的數(shù)據(jù)立方體，我們往往通過指定一個(gè)最小支持度閾值（也稱冰山條件），來進(jìn)行部分物化，這種部分物化的方體稱之為冰山方體。比如： COMPUTE CUBE Sales_Iceberg AS SELECT month, city, cust_grp, COUNT(*) FROM Sales_Info CUBE BY month, city, cust_grp HAVING COUNT(*) = min_sup,閉立方體 (1),冰山方體的計(jì)算通過冰山條件（例：HAVING COUNT(*) = min_sup）來減輕計(jì)算數(shù)據(jù)立方體中不重要的聚集單元的

5、負(fù)擔(dān)，然而仍有大量不感興趣的單元需要計(jì)算 比如：最小支持度為10，假定100維的數(shù)據(jù)立方體有兩個(gè)基本方體：(a1,a2,a3,a100):10, (a1,a2,b3,b100):10，假設(shè)冰山條件為最小支持度10 則需計(jì)算和存儲(chǔ)的單元仍是海量：2101-6個(gè) 如：(a1,a2,a3,a99,*):10, (a1,*,a3,a100):10,閉立方體 (2),閉單元 一個(gè)單元c是閉單元，如果單元c不存在一個(gè)跟c有著相同度量值的后代d 例如：上述例子中，任何一個(gè)(a1,a2,a3,*,*,*):10,都和他的后代有相同度量值 閉立方體：一個(gè)僅有閉單元組成的數(shù)據(jù)立方體 例如：,(a1,a2,*,*,

6、*):20,(a1,a2,a3, a100):10,(a1,a2,b3, b100):10,立方體外殼,部分物化的另外一種策略：僅預(yù)計(jì)算涉及少數(shù)維的方體（比如3到5維），這些立方體形成對(duì)應(yīng)數(shù)據(jù)立方體的外殼 利用外殼對(duì)其他的維組合查詢進(jìn)行快速計(jì)算 仍將導(dǎo)致大量方體（n很大時(shí)），類似的我們可以利用方體的興趣度，選擇只預(yù)計(jì)算立方體外殼的部分,立方體計(jì)算的一般策略 (1),一般，有兩種基本結(jié)構(gòu)用于存儲(chǔ)方體 關(guān)系OLAP（ROLAP） 底層使用關(guān)系模型存儲(chǔ)數(shù)據(jù) 多維OLAP（MOLAP） 底層使用多維數(shù)組存儲(chǔ)數(shù)據(jù) 無論使用哪種存儲(chǔ)方法，都可以使用以下立方體計(jì)算的一般優(yōu)化技術(shù) 優(yōu)化技術(shù)1：排序、散列和分組

7、 將排序、散列(hashing)和分組操作應(yīng)用于維的屬性，以便對(duì)相關(guān)元組重新排序和聚類,立方體計(jì)算的一般策略 (2),優(yōu)化技術(shù)2：同時(shí)聚集和緩存中間結(jié)果 由先前計(jì)算的較低層聚集來計(jì)算較高層聚集，而非從基本方體開始計(jì)算，減少I/O 優(yōu)化方法3：當(dāng)存在多個(gè)子女時(shí)，由最小的子女聚集 例如，計(jì)算Cbranch，可以利用C(branch, year)或者C(branch, item)，顯然利用前者更有效 優(yōu)化技術(shù)4：可以使用Apriori剪枝方法有效的計(jì)算冰山方體 如果給定的單元不能滿足最小支持度，則該單元的后代也都不滿足最小支持度,完全立方體計(jì)算的多路數(shù)組聚集方法(1),使用多維數(shù)組作為基本數(shù)據(jù)結(jié)構(gòu)，

8、計(jì)算完全數(shù)據(jù)立方體 一種使用數(shù)組直接尋址的典型MOLAP方法 計(jì)算步驟 （1）將數(shù)組分成塊（chunk,一個(gè)可以裝入內(nèi)存的小子方） 塊還可以進(jìn)一步被壓縮，以避免空數(shù)組單元導(dǎo)致的空間浪費(fèi)（處理稀疏立方體） （2）通過訪問立方體單元，計(jì)算聚集。 可以優(yōu)化訪問單元組的次序，使得每個(gè)單元被訪問的次數(shù)最小化，從而減少內(nèi)存訪問和磁盤I/O的開銷。,完全立方體計(jì)算的多路數(shù)組聚集方法(2),一個(gè)包含A,B,C的3-D數(shù)組，假定維A,B,C的基數(shù)分別是40、400和4000,A(month) 40個(gè)值,B,29,30,31,32,1,2,3,4,5,9,13,14,15,16,64,63,62,61,48,47

9、,46,45,a1,a0,c3,c2,c1,c 0,b3,b2,b1,b0,a2,a3,C(item) 4000個(gè)值,B(city) 400個(gè)值,44,28,56,40,24,52,36,20,60,哪個(gè)是多路數(shù)組聚集的最佳遍歷次序？,將要物化的立方體： 基本方體ABC，已計(jì)算，對(duì)應(yīng)于給定的3-D數(shù)組 2D方體AB，AC和BC 1D方體A,B,C 0D頂點(diǎn)方體，記作all,完全立方體計(jì)算的多路數(shù)組聚集方法(3),B(city) 400,通過掃描ABC的14塊，計(jì)算出塊b0c0，然后塊內(nèi)存可以分配給下一刻b1c0,如此繼續(xù)，可計(jì)算整個(gè)BC方體（一次只需一個(gè)BC塊在內(nèi)存）,完全立方體計(jì)算的多路數(shù)組

10、聚集方法(4),A,B,29,30,31,32,1,2,3,4,5,9,13,14,15,16,64,63,62,61,48,47,46,45,a1,a0,c3,c2,c1,c 0,b3,b2,b1,b0,a2,a3,C,44,28,56,40,24,52,36,20,60,B,BC方體的計(jì)算，必須掃描64塊中的每一塊；計(jì)算其他塊亦然 多路數(shù)組聚集方法避免重復(fù)掃描：當(dāng)一個(gè)3D塊在內(nèi)存時(shí)，向每一個(gè)平面同時(shí)聚集,思考：計(jì)算時(shí)需要多少內(nèi)存？,完全立方體計(jì)算的多路數(shù)組聚集方法(5),方法：各平面要按他們大小的升序排列進(jìn)行排序和計(jì)算 詳見書P108例4-4 思想：將最小的平面放在內(nèi)存中，對(duì)最大的平面每次

11、只是取并計(jì)算一塊,完全立方體計(jì)算的多路數(shù)組聚集方法(6),根據(jù)1到64的掃描次序，在塊內(nèi)存中保存所有相關(guān)的2-D平面所需的最小存儲(chǔ)為： 40400（用于整個(gè)AB平面）401000（用于AC平面一行）1001000（用于BC平面一塊)156，000 這種方法的限制：只有在維數(shù)比較小的情況下，效果才比較理想(要計(jì)算的立方體隨維數(shù)指數(shù)增長(zhǎng)) 如果維的數(shù)目比較多，可以考慮使用“自底向上的計(jì)算”或者時(shí)“冰山方體” 計(jì)算,數(shù)據(jù)立方體計(jì)算與數(shù)據(jù)泛化（2）,數(shù)據(jù)泛化,數(shù)據(jù)泛化 通過將相對(duì)層次較低的值（如屬性age的數(shù)值）用較高層次的概念（如青年、中年、老年）置換來匯總數(shù)據(jù) 主要方法： 數(shù)據(jù)立方體（OLAP使用

12、的方法） 面向?qū)傩缘臍w納方法,1,2,3,4,5,概念層,(17,18,19,34,35,36,56,57,),(青年,中年,老年),什么是概念描述？,概念描述是一種數(shù)據(jù)泛化的形式。 概念通常指數(shù)據(jù)的匯集 如frequent buyers，graduate students 概念描述產(chǎn)生數(shù)據(jù)的特征化和比較描述，當(dāng)所描述的概念所指的是對(duì)象類時(shí)，也稱為類描述 特征化：提供給定數(shù)據(jù)匯集的簡(jiǎn)潔匯總 比較：提供兩個(gè)或多個(gè)數(shù)據(jù)集的比較描述,概念描述 VS. OLAP,相似處： 數(shù)據(jù)泛化 對(duì)數(shù)據(jù)的匯總在不同的抽象級(jí)別上進(jìn)行呈現(xiàn) 區(qū)別： 復(fù)雜的數(shù)據(jù)類型和聚集 OLAP中維和度量的數(shù)據(jù)類型都非常有限（非數(shù)值型的

13、維和數(shù)值型的數(shù)據(jù)），表現(xiàn)為一種簡(jiǎn)單的數(shù)據(jù)分析模型 概念描述可以處理復(fù)雜數(shù)據(jù)類型的屬性及其聚集 用戶控制與自動(dòng)處理 OLAP是一個(gè)由用戶控制的過程 概念描述則表現(xiàn)為一個(gè)更加自動(dòng)化的過程,數(shù)據(jù)特征化的面向?qū)傩缘臍w納,一種面向關(guān)系數(shù)據(jù)查詢的、基于匯總的在線數(shù)據(jù)分析技術(shù)。 受數(shù)據(jù)類型和度量類型的約束比較少 面向?qū)傩詺w納的基本思想： 使用關(guān)系數(shù)據(jù)庫查詢收集任務(wù)相關(guān)的數(shù)據(jù) 通過考察任務(wù)相關(guān)數(shù)據(jù)中每個(gè)屬性的不同值的個(gè)數(shù)進(jìn)行泛化，方法是屬性刪除或者是屬性泛化 通過合并相等的，泛化的廣義元組，并累計(jì)他們對(duì)應(yīng)的計(jì)數(shù)值進(jìn)行聚集操作 通過與用戶交互，將廣義關(guān)系以圖表或規(guī)則等形式，提交給用戶,數(shù)據(jù)聚焦 （1）,目的是獲

14、得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，在DMQL中他們由in relevance to子句表示。 示例： DMQL: 描述Big-University數(shù)據(jù)庫中研究生的一般特征 use Big_University_DB mine characteristics as “Science_Students” in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpa from student where status in “graduate”,數(shù)據(jù)聚焦 （2）,上述DMQL查詢轉(zhuǎn)換為如下S

15、QL查詢，收集任務(wù)相關(guān)數(shù)據(jù)集 Select name, gender, major, birth_place, birth_date, residence, phone#, gpa from student where status in Msc, M.A., MBA, PhD 初始工作關(guān)系,數(shù)據(jù)泛化,數(shù)據(jù)泛化的兩種常用方法：屬性刪除和屬性泛化 屬性刪除的適用規(guī)則：對(duì)初始工作關(guān)系中具有大量不同值的屬性，符合以下情況，應(yīng)使用屬性刪除： 在此屬性上沒有泛化操作符（比如該屬性沒有定義相關(guān)的概念分層） 該屬性的較高層概念用其他屬性表示 屬性泛化的使用規(guī)則：如果初始工作關(guān)系中的某個(gè)屬性具有大量不同值，且

16、該屬性上存在泛化操作符，則使用該泛化操作符對(duì)該屬性進(jìn)行數(shù)據(jù)泛化操作,屬性泛化控制,確定什么是“具有大量的不同值”，控制將屬性泛化到多高的抽象層。 屬性泛化控制的兩種常用方法： 屬性泛化閾值控制 對(duì)所有屬性設(shè)置一個(gè)泛化閾值或者是對(duì)每個(gè)屬性都設(shè)置一個(gè)閾值（一般為2到8） 泛化關(guān)系閾值控制 為泛化關(guān)系設(shè)置一個(gè)閾值，確定泛化關(guān)系中，不同元組的個(gè)數(shù)的最大值。（通常為10到30，允許在實(shí)際應(yīng)用中進(jìn)行調(diào)整） 兩種技術(shù)的順序使用：使用屬性泛化閾值控制來泛化每個(gè)屬性，然后使用關(guān)系閾值控制進(jìn)一步壓縮泛化的關(guān)系,歸納過程中的聚集值計(jì)算,在歸納過程中，需要在不同的抽象層得到數(shù)據(jù)的量化信息或統(tǒng)計(jì)信息 聚集值計(jì)算過程 聚

17、集函數(shù)count與每個(gè)數(shù)據(jù)庫元組相關(guān)聯(lián)， 初始工作關(guān)系的每個(gè)元組的值初始化為1 通過屬性刪除和屬性泛化，初始工作關(guān)系中的元組可能被泛化，導(dǎo)致相等的元組分組 新的相等的元組分組的計(jì)數(shù)值設(shè)為初始工作關(guān)系中相應(yīng)元組的計(jì)數(shù)和 e.g. 52個(gè)初始工作關(guān)系中的元組泛化為一個(gè)新的元組T，則T的計(jì)數(shù)設(shè)置為52 還可以應(yīng)用其他聚集函數(shù)，包括sum，avg等,面向?qū)傩缘臍w納示例,挖掘BigUniversity數(shù)據(jù)庫中研究生的一般特征 name：刪除屬性（大量不同值，無泛化操作符） gender：保留該屬性，不泛化 major：根據(jù)概念分層向上攀升文，理，工 birth_place：根據(jù)概念分層location向

18、上攀升 birth_date：泛化為age，再泛化為age_range residence：根據(jù)概念分層location向上攀升 phone#：刪除屬性 gpa：根據(jù)GPA的分級(jí)作為概念分層,面向?qū)傩缘臍w納示例,主泛化關(guān)系,初始工作關(guān)系,面向?qū)傩缘臍w納算法,輸入 1. DB; 2. 數(shù)據(jù)挖掘查詢DMQuery; 3. 屬性列表; 4. 屬性的概念分層; 5. 屬性的泛化閾值； 輸出 主泛化關(guān)系P 算法描述： W get_task_relevant_data(DMQuery, DB) prepare_for_generalization(W) 掃描W，收集每個(gè)屬性a的不同值 對(duì)每個(gè)屬性a，根據(jù)閾

19、值確定是否刪除，如果不刪除，則計(jì)算其最小期望層次L，并確定映射對(duì)(v,v) P generalization(W) 通過使用v代替W中每個(gè)v，累計(jì)計(jì)數(shù)并計(jì)算所有聚集值，導(dǎo)出P 每個(gè)泛化元組的插入或累積計(jì)數(shù) 用數(shù)組表示P,導(dǎo)出泛化的表示 (1),泛化關(guān)系 一部分或者所有屬性得到泛化的關(guān)系，包含計(jì)數(shù)或其他度量值的聚集 交叉表 二維交叉表使用每行顯示一個(gè)屬性，使用每列顯示另外一個(gè)屬性將結(jié)果集映射到表中 可視化工具： 條形圖、餅圖、曲線和數(shù)據(jù)立方體瀏覽工具（用單元的大小代表計(jì)數(shù)，用單元亮度代表另外的度量）,P133-134,導(dǎo)出泛化的表示 (2),量化規(guī)則 使用t_weight表示主泛化關(guān)系中每個(gè)元組

20、的典型性 量化特征規(guī)則 將泛化的結(jié)果映射到相應(yīng)的量化特征規(guī)則中，比如：,量化特征規(guī)則中每個(gè)析取代表一個(gè)條件，一般，這些條件的析取形成目標(biāo)類的必要條件，因?yàn)樵摋l件是根據(jù)目標(biāo)類的所有情況導(dǎo)出的。也就是說，目標(biāo)類的所有元組必須滿足該條件。然而，該規(guī)則可能不是目標(biāo)類的充分條件，因?yàn)闈M足同一條件的元組可能屬于其他類。,E.g.,挖掘類比較：區(qū)分不同的類,類比較挖掘的目標(biāo)是得到將目標(biāo)類與對(duì)比類相區(qū)分的描述。 目標(biāo)類和對(duì)比類間必須具有可比性，即兩者間要有相似的屬性或維。 本科生 VS. 研究生；student VS. address 很多應(yīng)用于類特征化的技巧（處理單個(gè)類的多層數(shù)據(jù)的匯總和特征化）可以應(yīng)用于類

21、比較，比如屬性泛化 屬性泛化必須在所有比較類上同步進(jìn)行，將屬性泛化到同一抽象層后進(jìn)行比較。 E.g. City VS country,類比較的過程,數(shù)據(jù)收集 通過查詢處理收集數(shù)據(jù)庫中相關(guān)的數(shù)據(jù)，并將其劃分為一個(gè)目標(biāo)類和一個(gè)或多個(gè)對(duì)比類 維相關(guān)分析 如果存在較多的維，則應(yīng)當(dāng)對(duì)這些類進(jìn)行維相關(guān)分析，僅選擇高度相關(guān)的維進(jìn)行進(jìn)一步分析。（可以使用基于熵的度量） 同步泛化 同步的在目標(biāo)類和對(duì)比類上進(jìn)行泛化，泛化到維閾值控制的層，得到主目標(biāo)類 關(guān)系/方體 和 主對(duì)比類 關(guān)系/方體 導(dǎo)出比較的表示 用可視化技術(shù)表達(dá)類比較描述，通常會(huì)包含“對(duì)比”度量，反映目標(biāo)類與對(duì)比類間的比較 (e.g count%),類比

22、較挖掘示例（1）,任務(wù) 挖掘描述BigUniversity本科生和研究生的類比較 任務(wù)的DMQL描述,use Big_University_DB mine comparison as “grad_vs_undergrad_students” in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpa for “graduate_students” where status in “graduate” versus “undergraduate_students” where statu

23、s in “undergraduate” analyze count% from student,類比較挖掘示例（2）,進(jìn)行類比較挖掘的輸入： 給定的屬性：name, gender, major, birth_place, birth_date, residence, phone# and gpa 在屬性ai上定義的概念分層 Gen(ai) 在屬性ai上定義的屬性分析閾值 Ui 在屬性ai上定義的屬性泛化閾值Ti 屬性相關(guān)性閾值R,類比較挖掘示例（3）,任務(wù)的處理過程 數(shù)據(jù)收集 DMQL查詢轉(zhuǎn)化為關(guān)系查詢，得到初始目標(biāo)類工作關(guān)系和初始對(duì)比類工作關(guān)系 可以看成使構(gòu)造數(shù)據(jù)立方體的過程 引入一個(gè)新維

24、status來標(biāo)志目標(biāo)類和對(duì)比類（graduate, undergraduate） 其他屬性形成剩余的維 在兩個(gè)數(shù)據(jù)類上進(jìn)行維相關(guān)分析 刪除不相關(guān)或者使弱相關(guān)的維：name, gender, major, phone#,P137,類比較挖掘示例（4）,同步泛化 在目標(biāo)類和對(duì)比類上同步的進(jìn)行泛化，將相關(guān)的維泛化到由維閾值控制的層，形成主目標(biāo)類 關(guān)系/方體 和主對(duì)比類 關(guān)系/方體 導(dǎo)出比較的表示 用表、圖或規(guī)則等形式表達(dá)類比較描述的挖掘結(jié)果 用戶應(yīng)該能夠在主目標(biāo)類 關(guān)系/方體 和主對(duì)比類 關(guān)系/方體進(jìn)行進(jìn)一步的OLAP操作,類比較挖掘示例（5）,目標(biāo)類的主泛化關(guān)系: 研究生,對(duì)比類的主泛化關(guān)系: 本科生,類比較描述的量化判別規(guī)則表示（1）,類比較描述中的目標(biāo)類和對(duì)比類的區(qū)分特性也