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

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

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

4、很多度量值為0的單元）,冰山立方體 (2),對于稀疏的數(shù)據(jù)立方體，我們往往通過指定一個最小支持度閾值（也稱冰山條件），來進行部分物化，這種部分物化的方體稱之為冰山方體。比如： 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),冰山方體的計算通過冰山條件（例：HAVING COUNT(*) = min_sup）來減輕計算數(shù)據(jù)立方體中不重要的聚集單元的

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

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

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

8、計算完全數(shù)據(jù)立方體 一種使用數(shù)組直接尋址的典型MOLAP方法 計算步驟 （1）將數(shù)組分成塊（chunk,一個可以裝入內(nèi)存的小子方） 塊還可以進一步被壓縮，以避免空數(shù)組單元導致的空間浪費（處理稀疏立方體） （2）通過訪問立方體單元，計算聚集。 可以優(yōu)化訪問單元組的次序，使得每個單元被訪問的次數(shù)最小化，從而減少內(nèi)存訪問和磁盤I/O的開銷。,完全立方體計算的多路數(shù)組聚集方法(2),一個包含A,B,C的3-D數(shù)組，假定維A,B,C的基數(shù)分別是40、400和4000,A(month) 40個值,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個值,B(city) 400個值,44,28,56,40,24,52,36,20,60,哪個是多路數(shù)組聚集的最佳遍歷次序？,將要物化的立方體： 基本方體ABC，已計算，對應于給定的3-D數(shù)組 2D方體AB，AC和BC 1D方體A,B,C 0D頂點方體，記作all,完全立方體計算的多路數(shù)組聚集方法(3),B(city) 400,通過掃描ABC的14塊，計算出塊b0c0，然后塊內(nèi)存可以分配給下一刻b1c0,如此繼續(xù)，可計算整個BC方體（一次只需一個BC塊在內(nèi)存）,完全立方體計算的多路數(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方體的計算，必須掃描64塊中的每一塊；計算其他塊亦然 多路數(shù)組聚集方法避免重復掃描：當一個3D塊在內(nèi)存時，向每一個平面同時聚集,思考：計算時需要多少內(nèi)存？,完全立方體計算的多路數(shù)組聚集方法(5),方法：各平面要按他們大小的升序排列進行排序和計算 詳見書P108例4-4 思想：將最小的平面放在內(nèi)存中，對最大的平面每次

11、只是取并計算一塊,完全立方體計算的多路數(shù)組聚集方法(6),根據(jù)1到64的掃描次序，在塊內(nèi)存中保存所有相關(guān)的2-D平面所需的最小存儲為： 40400（用于整個AB平面）401000（用于AC平面一行）1001000（用于BC平面一塊)156，000 這種方法的限制：只有在維數(shù)比較小的情況下，效果才比較理想(要計算的立方體隨維數(shù)指數(shù)增長) 如果維的數(shù)目比較多，可以考慮使用“自底向上的計算”或者時“冰山方體” 計算,數(shù)據(jù)立方體計算與數(shù)據(jù)泛化（2）,數(shù)據(jù)泛化,數(shù)據(jù)泛化 通過將相對層次較低的值（如屬性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ù)的特征化和比較描述，當所描述的概念所指的是對象類時，也稱為類描述 特征化：提供給定數(shù)據(jù)匯集的簡潔匯總 比較：提供兩個或多個數(shù)據(jù)集的比較描述,概念描述 VS. OLAP,相似處： 數(shù)據(jù)泛化 對數(shù)據(jù)的匯總在不同的抽象級別上進行呈現(xiàn) 區(qū)別： 復雜的數(shù)據(jù)類型和聚集 OLAP中維和度量的數(shù)據(jù)類型都非常有限（非數(shù)值型的

13、維和數(shù)值型的數(shù)據(jù)），表現(xiàn)為一種簡單的數(shù)據(jù)分析模型 概念描述可以處理復雜數(shù)據(jù)類型的屬性及其聚集 用戶控制與自動處理 OLAP是一個由用戶控制的過程 概念描述則表現(xiàn)為一個更加自動化的過程,數(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ù)中每個屬性的不同值的個數(shù)進行泛化，方法是屬性刪除或者是屬性泛化 通過合并相等的，泛化的廣義元組，并累計他們對應的計數(shù)值進行聚集操作 通過與用戶交互，將廣義關(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ī)則：對初始工作關(guān)系中具有大量不同值的屬性，符合以下情況，應使用屬性刪除： 在此屬性上沒有泛化操作符（比如該屬性沒有定義相關(guān)的概念分層） 該屬性的較高層概念用其他屬性表示 屬性泛化的使用規(guī)則：如果初始工作關(guān)系中的某個屬性具有大量不同值，且

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

17、集函數(shù)count與每個數(shù)據(jù)庫元組相關(guān)聯(lián)， 初始工作關(guān)系的每個元組的值初始化為1 通過屬性刪除和屬性泛化，初始工作關(guān)系中的元組可能被泛化，導致相等的元組分組 新的相等的元組分組的計數(shù)值設(shè)為初始工作關(guān)系中相應元組的計數(shù)和 e.g. 52個初始工作關(guān)系中的元組泛化為一個新的元組T，則T的計數(shù)設(shè)置為52 還可以應用其他聚集函數(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的分級作為概念分層,面向?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，收集每個屬性a的不同值 對每個屬性a，根據(jù)閾

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

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

21、比較，比如屬性泛化 屬性泛化必須在所有比較類上同步進行，將屬性泛化到同一抽象層后進行比較。 E.g. City VS country,類比較的過程,數(shù)據(jù)收集 通過查詢處理收集數(shù)據(jù)庫中相關(guān)的數(shù)據(jù)，并將其劃分為一個目標類和一個或多個對比類 維相關(guān)分析 如果存在較多的維，則應當對這些類進行維相關(guān)分析，僅選擇高度相關(guān)的維進行進一步分析。（可以使用基于熵的度量） 同步泛化 同步的在目標類和對比類上進行泛化，泛化到維閾值控制的層，得到主目標類 關(guān)系/方體 和 主對比類 關(guān)系/方體 導出比較的表示 用可視化技術(shù)表達類比較描述，通常會包含“對比”度量，反映目標類與對比類間的比較 (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）,進行類比較挖掘的輸入： 給定的屬性：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)系查詢，得到初始目標類工作關(guān)系和初始對比類工作關(guān)系 可以看成使構(gòu)造數(shù)據(jù)立方體的過程 引入一個新維

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