數(shù)據(jù)挖掘概念與技術(shù)原書數(shù)據(jù)立方體計算與數(shù)據(jù)泛化體PPT課件

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

2、集的行為。 E.g 分類、回歸分析等第2頁/共45頁數(shù)據(jù)立方體的物化 數(shù)據(jù)立方體有利于多維數(shù)據(jù)的聯(lián)機(jī)分析處理 數(shù)據(jù)立方體使得從不同的角度對數(shù)據(jù)進(jìn)行觀察成為可能 方體計算（物化）的挑戰(zhàn)：海量數(shù)據(jù)，有限的內(nèi)存和時間 海量數(shù)據(jù)運算對大量計算時間和存儲空間的要求第3頁/共45頁數(shù)據(jù)立方體-基本概念(1) 數(shù)據(jù)立方體可以被看成是一個方體的格，每個方體用一個group-by表示 最底層的方體ABC是基本方體，包含所有3個維 最頂端的方體（頂點）只包含一個單元的值，泛化程度最高 上卷和下鉆操作與數(shù)據(jù)立方體的對應(yīng)BA()CABACBCABC第4頁/共45頁數(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)的祖先，當(dāng)且僅當(dāng) (1)i= min_sup第7頁/共45頁閉立方體 (1) 冰山方體的計算通過冰山條件（例：HAVING COUNT(*) = min_sup）來減輕計算數(shù)據(jù)立方體中不重要的聚集單元的負(fù)擔(dān)，然而仍有大量不感興趣的單元需要計算 比如：最小支持度為10，假定100

4、維的數(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第8頁/共45頁閉立方體 (2) 閉單元 一個單元c是閉單元，如果單元c不存在一個跟c有著相同度量值的后代d 例如：上述例子中，任何一個(a1,a2,a3,*,*,*):10,都和他的后代有相同度量值 閉立方體：一個僅有閉單元組成的數(shù)據(jù)立方體 例如：(a1,a2,*,*,*):20(a1,a2,a3, a100):10(a1,a2,b

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

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

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

8、2b1b0a2a3C(item) 4000個值B(city) 400個值442856402452362060哪個是多路數(shù)組聚集的最佳遍歷次序？將要物化的立方體：基本方體ABC，已計算，對應(yīng)于給定的3-D數(shù)組2D方體AB，AC和BC1D方體A,B,C0D頂點方體，記作all第14頁/共45頁完全立方體計算的多路數(shù)組聚集方法(3)A(month)40B29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C(item)4000442856402452362060B(city)400通過掃描ABC的14塊，計算出塊b0c0，然后

9、塊內(nèi)存可以分配給下一刻b1c0,如此繼續(xù)，可計算整個BC方體（一次只需一個BC塊在內(nèi)存）第15頁/共45頁完全立方體計算的多路數(shù)組聚集方法(4)AB29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C442856402452362060BBC方體的計算，必須掃描64塊中的每一塊；計算其他塊亦然多路數(shù)組聚集方法避免重復(fù)掃描：當(dāng)一個3D塊在內(nèi)存時，向每一個平面同時聚集第16頁/共45頁完全立方體計算的多路數(shù)組聚集方法(5) 方法：各平面要按他們大小的升序排列進(jìn)行排序和計算 詳見書P108例4-4 思想：將最小的平面放在內(nèi)存

10、中，對最大的平面每次只是取并計算一塊第17頁/共45頁完全立方體計算的多路數(shù)組聚集方法(6) 根據(jù)1到64的掃描次序，在塊內(nèi)存中保存所有相關(guān)的2-D平面所需的最小存儲為： 40400（用于整個AB平面）401000（用于AC平面一行）1001000（用于BC平面一塊)156，000 這種方法的限制：只有在維數(shù)比較小的情況下，效果才比較理想(要計算的立方體隨維數(shù)指數(shù)增長) 如果維的數(shù)目比較多，可以考慮使用“自底向上的計算”或者時“冰山方體” 計算第18頁/共45頁 概念描述是一種數(shù)據(jù)泛化的形式。 概念通常指數(shù)據(jù)的匯集 如frequent buyers，graduate students 概念描述

11、產(chǎn)生數(shù)據(jù)的特征化和比較描述，當(dāng)所描述的概念所指的是對象類時，也稱為類描述 特征化：提供給定數(shù)據(jù)匯集的簡潔匯總 比較：提供兩個或多個數(shù)據(jù)集的比較描述什么是概念描述？第19頁/共45頁 相似處： 數(shù)據(jù)泛化 對數(shù)據(jù)的匯總在不同的抽象級別上進(jìn)行呈現(xiàn) 區(qū)別： 復(fù)雜的數(shù)據(jù)類型和聚集 OLAP中維和度量的數(shù)據(jù)類型都非常有限（非數(shù)值型的維和數(shù)值型的數(shù)據(jù)），表現(xiàn)為一種簡單的數(shù)據(jù)分析模型 概念描述可以處理復(fù)雜數(shù)據(jù)類型的屬性及其聚集 用戶控制與自動處理 OLAP是一個由用戶控制的過程 概念描述則表現(xiàn)為一個更加自動化的過程概念描述 VS. OLAP第20頁/共45頁 一種面向關(guān)系數(shù)據(jù)查詢的、基于匯總的在線數(shù)據(jù)分析技術(shù)

12、。 受數(shù)據(jù)類型和度量類型的約束比較少 面向?qū)傩詺w納的基本思想： 使用關(guān)系數(shù)據(jù)庫查詢收集任務(wù)相關(guān)的數(shù)據(jù) 通過考察任務(wù)相關(guān)數(shù)據(jù)中每個屬性的不同值的個數(shù)進(jìn)行泛化，方法是屬性刪除或者是屬性泛化 通過合并相等的，泛化的廣義元組，并累計他們對應(yīng)的計數(shù)值進(jìn)行聚集操作 通過與用戶交互，將廣義關(guān)系以圖表或規(guī)則等形式，提交給用戶數(shù)據(jù)特征化的面向?qū)傩缘臍w納第21頁/共45頁 目的是獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，在DMQL中他們由in relevance to子句表示。 示例： DMQL: 描述Big-University數(shù)據(jù)庫中研究生的一般特征use Big_University_DBmine charac

13、teristics as “Science_Students”in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpafrom studentwhere status in “graduate”數(shù)據(jù)聚焦 （1）第22頁/共45頁 上述DMQL查詢轉(zhuǎn)換為如下SQL查詢，收集任務(wù)相關(guān)數(shù)據(jù)集Select name, gender, major, birth_place, birth_date, residence, phone#, gpafrom studentwhere status i

14、n Msc, M.A., MBA, PhD 初始工作關(guān)系數(shù)據(jù)聚焦 （2）第23頁/共45頁 數(shù)據(jù)泛化的兩種常用方法：屬性刪除和屬性泛化 屬性刪除的適用規(guī)則：對初始工作關(guān)系中具有大量不同值的屬性，符合以下情況，應(yīng)使用屬性刪除： 在此屬性上沒有泛化操作符（比如該屬性沒有定義相關(guān)的概念分層） 該屬性的較高層概念用其他屬性表示 屬性泛化的使用規(guī)則：如果初始工作關(guān)系中的某個屬性具有大量不同值，且該屬性上存在泛化操作符，則使用該泛化操作符對該屬性進(jìn)行數(shù)據(jù)泛化操作數(shù)據(jù)泛化第24頁/共45頁 確定什么是“具有大量的不同值”，控制將屬性泛化到多高的抽象層。 屬性泛化控制的兩種常用方法： 屬性泛化閾值控制 對所有

15、屬性設(shè)置一個泛化閾值或者是對每個屬性都設(shè)置一個閾值（一般為2到8） 泛化關(guān)系閾值控制 為泛化關(guān)系設(shè)置一個閾值，確定泛化關(guān)系中，不同元組的個數(shù)的最大值。（通常為10到30，允許在實際應(yīng)用中進(jìn)行調(diào)整） 兩種技術(shù)的順序使用：使用屬性泛化閾值控制來泛化每個屬性，然后使用關(guān)系閾值控制進(jìn)一步壓縮泛化的關(guān)系屬性泛化控制第25頁/共45頁 在歸納過程中，需要在不同的抽象層得到數(shù)據(jù)的量化信息或統(tǒng)計信息 聚集值計算過程 聚集函數(shù)count與每個數(shù)據(jù)庫元組相關(guān)聯(lián)， 初始工作關(guān)系的每個元組的值初始化為1 通過屬性刪除和屬性泛化，初始工作關(guān)系中的元組可能被泛化，導(dǎo)致相等的元組分組 新的相等的元組分組的計數(shù)值設(shè)為初始工作

16、關(guān)系中相應(yīng)元組的計數(shù)和 e.g. 52個初始工作關(guān)系中的元組泛化為一個新的元組T，則T的計數(shù)設(shè)置為52 還可以應(yīng)用其他聚集函數(shù)，包括sum，avg等歸納過程中的聚集值計算第26頁/共45頁 挖掘BigUniversity數(shù)據(jù)庫中研究生的一般特征 name：刪除屬性（大量不同值，無泛化操作符） gender：保留該屬性，不泛化 major：根據(jù)概念分層向上攀升文，理，工 birth_place：根據(jù)概念分層location向上攀升 birth_date：泛化為age，再泛化為age_range residence：根據(jù)概念分層location向上攀升 phone#：刪除屬性 gpa：根據(jù)GPA的

17、分級作為概念分層面向?qū)傩缘臍w納示例第27頁/共45頁面向?qū)傩缘臍w納示例主泛化關(guān)系初始工作關(guān)系第28頁/共45頁輸入1. DB; 2. 數(shù)據(jù)挖掘查詢DMQuery; 3. 屬性列表; 4. 屬性的概念分層; 5. 屬性的泛化閾值；輸出主泛化關(guān)系P算法描述：1. W get_task_relevant_data(DMQuery, DB)2. prepare_for_generalization(W)1.掃描W，收集每個屬性a的不同值2.對每個屬性a，根據(jù)閾值確定是否刪除，如果不刪除，則計算其最小期望層次L，并確定映射對(v,v)3. P generalization(W)q通過使用v代替W中每個v

18、，累計計數(shù)并計算所有聚集值，導(dǎo)出P1.每個泛化元組的插入或累積計數(shù)2.用數(shù)組表示P面向?qū)傩缘臍w納算法第29頁/共45頁 泛化關(guān)系 一部分或者所有屬性得到泛化的關(guān)系，包含計數(shù)或其他度量值的聚集 交叉表 二維交叉表使用每行顯示一個屬性，使用每列顯示另外一個屬性將結(jié)果集映射到表中 可視化工具： 條形圖、餅圖、曲線和數(shù)據(jù)立方體瀏覽工具（用單元的大小代表計數(shù)，用單元亮度代表另外的度量）導(dǎo)出泛化的表示 (1)第30頁/共45頁 量化規(guī)則 使用t_weight表示主泛化關(guān)系中每個元組的典型性 量化特征規(guī)則 將泛化的結(jié)果映射到相應(yīng)的量化特征規(guī)則中，比如：導(dǎo)出泛化的表示 (2)niiaqcountqcountw

19、eightt1)(/ )(_: )(.: )()(_arg ,mmllwtXconditionwtXconditionXclassettX%45: ) )( %30: ) )(%25: ) )( )( ,tAmericanNorthXlocationtEuropeXlocationtAsiaXlocationcomputerXitemX量化特征規(guī)則中每個析取代表一個條件，一般，這些條件的析取形成目標(biāo)類的必要條件，因為該條件是根據(jù)目標(biāo)類的所有情況導(dǎo)出的。也就是說，目標(biāo)類的所有元組必須滿足該條件。然而，該規(guī)則可能不是目標(biāo)類的充分條件，因為滿足同一條件的元組可能屬于其他類。E.g.第31頁/共45頁

20、 類比較挖掘的目標(biāo)是得到將目標(biāo)類與對比類相區(qū)分的描述。 目標(biāo)類和對比類間必須具有可比性，即兩者間要有相似的屬性或維。 本科生 VS. 研究生；student VS. address 很多應(yīng)用于類特征化的技巧（處理單個類的多層數(shù)據(jù)的匯總和特征化）可以應(yīng)用于類比較，比如屬性泛化 屬性泛化必須在所有比較類上同步進(jìn)行，將屬性泛化到同一抽象層后進(jìn)行比較。 E.g. City VS country挖掘類比較：區(qū)分不同的類第32頁/共45頁 數(shù)據(jù)收集 通過查詢處理收集數(shù)據(jù)庫中相關(guān)的數(shù)據(jù)，并將其劃分為一個目標(biāo)類和一個或多個對比類 維相關(guān)分析 如果存在較多的維，則應(yīng)當(dāng)對這些類進(jìn)行維相關(guān)分析，僅選擇高度相關(guān)的維進(jìn)

21、行進(jìn)一步分析。（可以使用基于熵的度量） 同步泛化 同步的在目標(biāo)類和對比類上進(jìn)行泛化，泛化到維閾值控制的層，得到主目標(biāo)類 關(guān)系/方體 和 主對比類 關(guān)系/方體 導(dǎo)出比較的表示 用可視化技術(shù)表達(dá)類比較描述，通常會包含“對比”度量，反映目標(biāo)類與對比類間的比較 (e.g count%)類比較的過程第33頁/共45頁 任務(wù) 挖掘描述BigUniversity本科生和研究生的類比較 任務(wù)的DMQL描述類比較挖掘示例（1）use Big_University_DBmine comparison as “grad_vs_undergrad_students”in relevance to name, gend

22、er, major, birth_place, birth_date, residence, phone#, gpafor “graduate_students”where status in “graduate”versus “undergraduate_students”where status in “undergraduate”analyze count%from student第34頁/共45頁 進(jìn)行類比較挖掘的輸入： 給定的屬性：name, gender, major, birth_place, birth_date, residence, phone# and gpa 在屬性ai

23、上定義的概念分層 Gen(ai) 在屬性ai上定義的屬性分析閾值 Ui 在屬性ai上定義的屬性泛化閾值Ti 屬性相關(guān)性閾值R類比較挖掘示例（2）第35頁/共45頁 任務(wù)的處理過程 數(shù)據(jù)收集 DMQL查詢轉(zhuǎn)化為關(guān)系查詢，得到初始目標(biāo)類工作關(guān)系和初始對比類工作關(guān)系 可以看成使構(gòu)造數(shù)據(jù)立方體的過程 引入一個新維status來標(biāo)志目標(biāo)類和對比類（graduate, undergraduate） 其他屬性形成剩余的維 在兩個數(shù)據(jù)類上進(jìn)行維相關(guān)分析 刪除不相關(guān)或者使弱相關(guān)的維：name, gender, major, phone#類比較挖掘示例（3）第36頁/共45頁 同步泛化 在目標(biāo)類和對比類上同步的進(jìn)

24、行泛化，將相關(guān)的維泛化到由維閾值控制的層，形成主目標(biāo)類 關(guān)系/方體 和主對比類 關(guān)系/方體 導(dǎo)出比較的表示 用表、圖或規(guī)則等形式表達(dá)類比較描述的挖掘結(jié)果 用戶應(yīng)該能夠在主目標(biāo)類 關(guān)系/方體 和主對比類 關(guān)系/方體進(jìn)行進(jìn)一步的OLAP操作類比較挖掘示例（4）第37頁/共45頁類比較挖掘示例（5）目標(biāo)類的主泛化關(guān)系: 研究生對比類的主泛化關(guān)系: 本科生第38頁/共45頁類比較描述的量化判別規(guī)則表示（1） 類比較描述中的目標(biāo)類和對比類的區(qū)分特性也可以用量化規(guī)則來表示，即量化判別規(guī)則 量化判別規(guī)則使用d-weight作為興趣度度量 （qa概化元組 Cj目標(biāo)類qa的d-weight是初始目標(biāo)類工作關(guān)系中

25、被qa覆蓋的元組數(shù) 與 初始目標(biāo)類和對比類工作關(guān)系中被qa覆蓋的總元組數(shù)的比miiaja)Ccount(q)Ccount(qweightd1第39頁/共45頁 目標(biāo)類中較高的d-weight表明概化元組所代表的概念主要來自于目標(biāo)類 較低的d-weight值則表明該概念主要來自于對比類類比較描述的量化判別規(guī)則表示（2）StatusBirth_countryAge_rangeGpaCountGraduateCanada25-30Good90UndergraduateCanada25-30Good210對給定的status=“Graduate”, Birth_coutry=“Canada”, Age_range=“25-30”, Gpa=“Good” 概化元組，其d-weight=90/(90+210)=30% (什么意思？)第40頁/共45頁類比較描述的量化判別規(guī)則表示（3） 使用類比較描述的量化判別規(guī)則表示可以更好的描述上述的情況，其形式為： 比如，剛才的挖掘結(jié)果可以使用量化判別規(guī)則表達(dá)如下： 請注意該區(qū)分規(guī)則表達(dá)的是充分條件，即X滿足條件，則X為研究生的概率為30% (特征化量化規(guī)則表達(dá)的是什么條件？) : )()(_arg ,weightddXconditionXclassettX%30:)(3025)(_)(_)(_,dgoodXgpaXrangeageCanad