數(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納方法12345概念層(Month,city,customer_group)(Month,*,*)第1頁/共47頁數(shù)據(jù)泛化數(shù)據(jù)泛化12345概念層(Month,city,1兩種不同類別的數(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ù)集的行為。E.g分類、回歸分析等第2頁/共47頁兩種不同類別的數(shù)據(jù)挖掘從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描2數(shù)據(jù)立方體的物化數(shù)據(jù)立方體有利于多維數(shù)據(jù)的聯(lián)機分析處理數(shù)據(jù)立方體使得從不同的角度對數(shù)據(jù)進行觀察成為可能方體計算（物化）的挑戰(zhàn)：海量數(shù)據(jù)，有限的內(nèi)存和時間海量數(shù)據(jù)運算對大量計算時間和存儲空間的要求第3頁/共47頁數(shù)據(jù)立方體的物化數(shù)據(jù)立方體有利于多維數(shù)據(jù)的聯(lián)機分析處理第3頁3數(shù)據(jù)立方體---基本概念(1)數(shù)據(jù)立方體可以被看成是一個方體的格，每個方體用一個group-by表示最底層的方體ABC是基本方體，包含所有3個維最頂端的方體（頂點）只包含一個單元的值，泛化程度最高上卷和下鉆操作與數(shù)據(jù)立方體的對應(yīng)BA()CABACBCABCP102圖4-1第4頁/共47頁數(shù)據(jù)立方體---基本概念(1)數(shù)據(jù)立方體可以被看成是一個方體4數(shù)據(jù)立方體---基本概念(2)基本方體的單元是基本單元，非基本方體的單元是聚集單元聚集單元在一個或多個維聚集，每個聚集維用"*"表示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<j，并且(2)對于1≤m≤n，只要am≠"*"就有am=bm第5頁/共47頁數(shù)據(jù)立方體---基本概念(2)基本方體的單元是基本單元，非基5冰山立方體(1)為了確保快速的聯(lián)機分析，有時希望預(yù)計算整個立方體（所有方體的所有單元）n維數(shù)據(jù)立方體包含2n個方體如果考慮概念分層部分物化是存儲空間和響應(yīng)時間的折中方案事實上，很多高維方體都是稀疏的（包含很多度量值為0的單元）第6頁/共47頁冰山立方體(1)為了確?？焖俚穆?lián)機分析，有時希望預(yù)計算整個6冰山立方體(2)對于稀疏的數(shù)據(jù)立方體，我們往往通過指定一個最小支持度閾值（也稱冰山條件），來進行部分物化，這種部分物化的方體稱之為冰山方體。比如：COMPUTECUBESales_IcebergASSELECTmonth,city,cust_grp,COUNT(*)FROMSales_InfoCUBEBYmonth,city,cust_grpHAVINGCOUNT(*)>=min_sup第7頁/共47頁冰山立方體(2)對于稀疏的數(shù)據(jù)立方體，我們往往通過指定一個7閉立方體(1)冰山方體的計算通過冰山條件（例：HAVINGCOUNT(*)>=min_sup）來減輕計算數(shù)據(jù)立方體中不重要的聚集單元的負擔(dān)，然而仍有大量不感興趣的單元需要計算比如：最小支持度為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第8頁/共47頁閉立方體(1)冰山方體的計算通過冰山條件（例：HAVING8閉立方體(2)閉單元一個單元c是閉單元，如果單元c不存在一個跟c有著相同度量值的后代d例如：上述例子中，任何一個(a1,a2,a3,*,*,…,*):10,都和他的后代有相同度量值閉立方體：一個僅有閉單元組成的數(shù)據(jù)立方體例如：(a1,a2,*,*,…,*):20(a1,a2,a3,…,a100):10(a1,a2,b3,…,b100):10第9頁/共47頁閉立方體(2)閉單元(a1,a2,*,*,…,*):20(9立方體外殼部分物化的另外一種策略：僅預(yù)計算涉及少數(shù)維的方體（比如3到5維），這些立方體形成對應(yīng)數(shù)據(jù)立方體的外殼利用外殼對其他的維組合查詢進行快速計算仍將導(dǎo)致大量方體（n很大時），類似的我們可以利用方體的興趣度，選擇只預(yù)計算立方體外殼的部分第10頁/共47頁立方體外殼部分物化的另外一種策略：僅預(yù)計算涉及少數(shù)維的方體（10立方體計算的一般策略(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)和分組操作應(yīng)用于維的屬性，以便對相關(guān)元組重新排序和聚類第11頁/共47頁立方體計算的一般策略(1)一般，有兩種基本結(jié)構(gòu)用于存儲方體11立方體計算的一般策略(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頁/共47頁立方體計算的一般策略(2)優(yōu)化技術(shù)2：同時聚集和緩存中間結(jié)12完全立方體計算的多路數(shù)組聚集方法(1)使用多維數(shù)組作為基本數(shù)據(jù)結(jié)構(gòu)，計算完全數(shù)據(jù)立方體一種使用數(shù)組直接尋址的典型MOLAP方法計算步驟（1）將數(shù)組分成塊（chunk,一個可以裝入內(nèi)存的小子方）塊還可以進一步被壓縮，以避免空數(shù)組單元導(dǎo)致的空間浪費（處理稀疏立方體）（2）通過訪問立方體單元，計算聚集?？梢詢?yōu)化訪問單元組的次序，使得每個單元被訪問的次數(shù)最小化，從而減少內(nèi)存訪問和磁盤I/O的開銷。第13頁/共47頁完全立方體計算的多路數(shù)組聚集方法(1)使用多維數(shù)組作為基本數(shù)13完全立方體計算的多路數(shù)組聚集方法(2)一個包含A,B,C的3-D數(shù)組，假定維A,B,C的基數(shù)分別是40、400和4000A(month)40個值B29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C(item)4000個值B(city)400個值442856402452362060哪個是多路數(shù)組聚集的最佳遍歷次序？將要物化的立方體：基本方體ABC，已計算，對應(yīng)于給定的3-D數(shù)組2D方體AB，AC和BC1D方體A,B,C0D頂點方體，記作all第14頁/共47頁完全立方體計算的多路數(shù)組聚集方法(2)一個包含A,B,C的314完全立方體計算的多路數(shù)組聚集方法(3)A(month)40B29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C(item)4000442856402452362060B(city)400通過掃描ABC的1～4塊，計算出塊b0c0，然后塊內(nèi)存可以分配給下一刻b1c0,如此繼續(xù)，可計算整個BC方體（一次只需一個BC塊在內(nèi)存）第15頁/共47頁完全立方體計算的多路數(shù)組聚集方法(3)A(month)B2915完全立方體計算的多路數(shù)組聚集方法(4)AB29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C442856402452362060BBC方體的計算，必須掃描64塊中的每一塊；計算其他塊亦然多路數(shù)組聚集方法避免重復(fù)掃描：當(dāng)一個3D塊在內(nèi)存時，向每一個平面同時聚集思考：計算時需要多少內(nèi)存？第16頁/共47頁完全立方體計算的多路數(shù)組聚集方法(4)AB29303132116完全立方體計算的多路數(shù)組聚集方法(5)方法：各平面要按他們大小的升序排列進行排序和計算詳見書P108例4-4思想：將最小的平面放在內(nèi)存中，對最大的平面每次只是取并計算一塊第17頁/共47頁完全立方體計算的多路數(shù)組聚集方法(5)方法：各平面要按他們大17完全立方體計算的多路數(shù)組聚集方法(6)根據(jù)1到64的掃描次序，在塊內(nèi)存中保存所有相關(guān)的2-D平面所需的最小存儲為：40×400（用于整個AB平面）＋40×1000（用于AC平面一行）＋100×1000（用于BC平面一塊)＝156，000這種方法的限制：只有在維數(shù)比較小的情況下，效果才比較理想(要計算的立方體隨維數(shù)指數(shù)增長)如果維的數(shù)目比較多，可以考慮使用“自底向上的計算”或者時“冰山方體”計算第18頁/共47頁完全立方體計算的多路數(shù)組聚集方法(6)根據(jù)1到64的掃描次序18數(shù)據(jù)立方體計算與數(shù)據(jù)泛化（2）第19頁/共47頁數(shù)據(jù)立方體計算與數(shù)據(jù)泛化（2）第19頁/共47頁19數(shù)據(jù)泛化數(shù)據(jù)泛化通過將相對層次較低的值（如屬性age的數(shù)值）用較高層次的概念（如青年、中年、老年）置換來匯總數(shù)據(jù)主要方法：數(shù)據(jù)立方體（OLAP使用的方法）面向?qū)傩缘臍w納方法12345概念層(17,18,19,…,34,35,36,…,56,57,…)(青年,中年,老年)第20頁/共47頁數(shù)據(jù)泛化數(shù)據(jù)泛化12345概念層(17,18,19,…,3420什么是概念描述？概念描述是一種數(shù)據(jù)泛化的形式。概念通常指數(shù)據(jù)的匯集如frequentbuyers，graduatestudents概念描述產(chǎn)生數(shù)據(jù)的特征化和比較描述，當(dāng)所描述的概念所指的是對象類時，也稱為類描述特征化：提供給定數(shù)據(jù)匯集的簡潔匯總比較：提供兩個或多個數(shù)據(jù)集的比較描述第21頁/共47頁什么是概念描述？概念描述是一種數(shù)據(jù)泛化的形式。第21頁/共421概念描述VS.OLAP相似處：數(shù)據(jù)泛化對數(shù)據(jù)的匯總在不同的抽象級別上進行呈現(xiàn)區(qū)別：復(fù)雜的數(shù)據(jù)類型和聚集OLAP中維和度量的數(shù)據(jù)類型都非常有限（非數(shù)值型的維和數(shù)值型的數(shù)據(jù)），表現(xiàn)為一種簡單的數(shù)據(jù)分析模型概念描述可以處理復(fù)雜數(shù)據(jù)類型的屬性及其聚集用戶控制與自動處理OLAP是一個由用戶控制的過程概念描述則表現(xiàn)為一個更加自動化的過程第22頁/共47頁概念描述VS.OLAP相似處：第22頁/共47頁22數(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ù)進行泛化，方法是屬性刪除或者是屬性泛化通過合并相等的，泛化的廣義元組，并累計他們對應(yīng)的計數(shù)值進行聚集操作通過與用戶交互，將廣義關(guān)系以圖表或規(guī)則等形式，提交給用戶第23頁/共47頁數(shù)據(jù)特征化的面向?qū)傩缘臍w納一種面向關(guān)系數(shù)據(jù)查詢的、基于匯總的23數(shù)據(jù)聚焦（1）目的是獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，在DMQL中他們由inrelevanceto子句表示。示例：DMQL:描述Big-University數(shù)據(jù)庫中研究生的一般特征 useBig_University_DBminecharacteristicsas“Science_Students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin“graduate”第24頁/共47頁數(shù)據(jù)聚焦（1）目的是獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，24數(shù)據(jù)聚焦（2）上述DMQL查詢轉(zhuǎn)換為如下SQL查詢，收集任務(wù)相關(guān)數(shù)據(jù)集Selectname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin{"Msc","M.A.","MBA","PhD"}初始工作關(guān)系第25頁/共47頁數(shù)據(jù)聚焦（2）上述DMQL查詢轉(zhuǎn)換為如下SQL查詢，收集任25數(shù)據(jù)泛化數(shù)據(jù)泛化的兩種常用方法：屬性刪除和屬性泛化屬性刪除的適用規(guī)則：對初始工作關(guān)系中具有大量不同值的屬性，符合以下情況，應(yīng)使用屬性刪除：在此屬性上沒有泛化操作符（比如該屬性沒有定義相關(guān)的概念分層）該屬性的較高層概念用其他屬性表示屬性泛化的使用規(guī)則：如果初始工作關(guān)系中的某個屬性具有大量不同值，且該屬性上存在泛化操作符，則使用該泛化操作符對該屬性進行數(shù)據(jù)泛化操作第26頁/共47頁數(shù)據(jù)泛化數(shù)據(jù)泛化的兩種常用方法：屬性刪除和屬性泛化第26頁/26屬性泛化控制確定什么是“具有大量的不同值”，控制將屬性泛化到多高的抽象層。屬性泛化控制的兩種常用方法：屬性泛化閾值控制對所有屬性設(shè)置一個泛化閾值或者是對每個屬性都設(shè)置一個閾值（一般為2到8）泛化關(guān)系閾值控制為泛化關(guān)系設(shè)置一個閾值，確定泛化關(guān)系中，不同元組的個數(shù)的最大值。（通常為10到30，允許在實際應(yīng)用中進行調(diào)整）兩種技術(shù)的順序使用：使用屬性泛化閾值控制來泛化每個屬性，然后使用關(guān)系閾值控制進一步壓縮泛化的關(guān)系第27頁/共47頁屬性泛化控制確定什么是“具有大量的不同值”，控制將屬性泛化到27歸納過程中的聚集值計算在歸納過程中，需要在不同的抽象層得到數(shù)據(jù)的量化信息或統(tǒng)計信息聚集值計算過程聚集函數(shù)count與每個數(shù)據(jù)庫元組相關(guān)聯(lián)，初始工作關(guān)系的每個元組的值初始化為1通過屬性刪除和屬性泛化，初始工作關(guān)系中的元組可能被泛化，導(dǎo)致相等的元組分組新的"相等的元組分組"的計數(shù)值設(shè)為初始工作關(guān)系中相應(yīng)元組的計數(shù)和e.g.52個初始工作關(guān)系中的元組泛化為一個新的元組T，則T的計數(shù)設(shè)置為52還可以應(yīng)用其他聚集函數(shù)，包括sum，avg等第28頁/共47頁歸納過程中的聚集值計算在歸納過程中，需要在不同的抽象層得到數(shù)28面向?qū)傩缘臍w納——示例挖掘BigUniversity數(shù)據(jù)庫中研究生的一般特征name：刪除屬性（大量不同值，無泛化操作符）gender：保留該屬性，不泛化major：根據(jù)概念分層向上攀升{文，理，工…}birth_place：根據(jù)概念分層location向上攀升birth_date：泛化為age，再泛化為age_rangeresidence：根據(jù)概念分層location向上攀升phone#：刪除屬性gpa：根據(jù)GPA的分級作為概念分層第29頁/共47頁面向?qū)傩缘臍w納——示例挖掘BigUniversity數(shù)據(jù)庫中29面向?qū)傩缘臍w納——示例主泛化關(guān)系初始工作關(guān)系第30頁/共47頁面向?qū)傩缘臍w納——示例主泛化關(guān)系初始工作關(guān)系第30頁/共4730面向?qū)傩缘臍w納算法輸入1.DB;2.數(shù)據(jù)挖掘查詢DMQuery;3.屬性列表;4.屬性的概念分層;5.屬性的泛化閾值；輸出主泛化關(guān)系P算法描述：Wget_task_relevant_data(DMQuery,DB)prepare_for_generalization(W)掃描W，收集每個屬性a的不同值對每個屬性a，根據(jù)閾值確定是否刪除，如果不刪除，則計算其最小期望層次L，并確定映射對(v,v`)Pgeneralization(W)通過使用v`代替W中每個v，累計計數(shù)并計算所有聚集值，導(dǎo)出P每個泛化元組的插入或累積計數(shù)用數(shù)組表示P第31頁/共47頁面向?qū)傩缘臍w納算法輸入第31頁/共47頁31導(dǎo)出泛化的表示(1)泛化關(guān)系一部分或者所有屬性得到泛化的關(guān)系，包含計數(shù)或其他度量值的聚集交叉表二維交叉表使用每行顯示一個屬性，使用每列顯示另外一個屬性將結(jié)果集映射到表中可視化工具：條形圖、餅圖、曲線和數(shù)據(jù)立方體瀏覽工具（用單元的大小代表計數(shù)，用單元亮度代表另外的度量）P133-134第32頁/共47頁導(dǎo)出泛化的表示(1)泛化關(guān)系P133-134第32頁/共432導(dǎo)出泛化的表示(2)量化規(guī)則使用t_weight表示主泛化關(guān)系中每個元組的典型性量化特征規(guī)則將泛化的結(jié)果映射到相應(yīng)的量化特征規(guī)則中，比如：量化特征規(guī)則中每個析取代表一個條件，一般，這些條件的析取形成目標(biāo)類的必要條件，因為該條件是根據(jù)目標(biāo)類的所有情況導(dǎo)出的。也就是說，目標(biāo)類的所有元組必須滿足該條件。然而，該規(guī)則可能不是目標(biāo)類的充分條件，因為滿足同一條件的元組可能屬于其他類。E.g.第33頁/共47頁導(dǎo)出泛化的表示(2)量化規(guī)則量化特征規(guī)則中每個析取代表一個33挖掘類比較：區(qū)分不同的類類比較挖掘的目標(biāo)是得到將目標(biāo)類與對比類相區(qū)分的描述。目標(biāo)類和對比類間必須具有可比性，即兩者間要有相似的屬性或維。本科生VS.研究生；studentVS.address很多應(yīng)用于類特征化的技巧（處理單個類的多層數(shù)據(jù)的匯總和特征化）可以應(yīng)用于類比較，比如屬性泛化屬性泛化必須在所有比較類上同步進行，將屬性泛化到同一抽象層后進行比較。E.g.CityVScountry第34頁/共47頁挖掘類比較：區(qū)分不同的類類比較挖掘的目標(biāo)是得到將目標(biāo)類與對比34類比較的過程數(shù)據(jù)收集通過查詢處理收集數(shù)據(jù)庫中相關(guān)的數(shù)據(jù)，并將其劃分為一個目標(biāo)類和一個或多個對比類維相關(guān)分析如果存在較多的維，則應(yīng)當(dāng)對這些類進行維相關(guān)分析，僅選擇高度相關(guān)的維進行進一步分析。（可以使用基于熵的度量）同步泛化同步的在目標(biāo)類和對比類上進行泛化，泛化到維閾值控制的層，得到主目標(biāo)類關(guān)系/方體和主對比類關(guān)系/方體導(dǎo)出比較的表示用可視化技術(shù)表達類比較描述，通常會包含“對比”度量，反映目標(biāo)類與對比類間的比較(e.gcount%)第35頁/共47頁類比較的過程數(shù)據(jù)收集第35頁/共47頁35類比較挖掘——示例（1）任務(wù)挖掘描述BigUniversity本科生和研究生的類比較任務(wù)的DMQL描述useBig_University_DBminecomparisonas“grad_vs_undergrad_students”inrelevanceto

name,gender,major,birth_place,birth_date,residence,phone#,gpafor“graduate_students”wherestatusin“graduate”versus“undergraduate_students”wherestatusin“undergraduate”analyzecount%fromstudent第36頁/共47頁類比較挖掘——示例（1）任務(wù)useBig_Universi36類比較挖掘——示例（2）進行類比較挖掘的輸入：給定的屬性：name,gender,major,birth_place,birth_date,residence,phone#andgpa在屬性ai上定義的概念分層Gen(ai)在屬性ai上定義的屬性分析閾值Ui在屬性ai上定義的屬性泛化閾值Ti屬性相關(guān)性閾值R第37頁/共47頁類比較挖掘——示例（2）進行類比較挖掘的輸入：第37頁/共437類比較挖掘——示例（3）任務(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ù)類上進行維相關(guān)分析刪除不相關(guān)或者使弱相關(guān)的維：name,gender,major,phone#P137第38頁/共47頁類比較挖掘——示例（3）任務(wù)的處理過程P137第38頁/共438類比較挖掘——示例（4）同步泛化在目標(biāo)類和對比類上同步的進行泛化，將相關(guān)的維泛化到由維閾值控制的層，形成主目標(biāo)類關(guān)系/方體和主對比類關(guān)系/方體導(dǎo)出比較的表示用表、圖或規(guī)則等形式表達類比較描述的挖掘結(jié)果用戶應(yīng)該能夠在主目標(biāo)類關(guān)系/方體和主對比類關(guān)系/方體進行進一步的OLAP操作第39頁/共47頁類比較挖掘——示例（4）同步泛化第39頁/共47頁39類比較挖掘——示例（5）目標(biāo)類的主泛化關(guān)系:研究生對比類的主泛化關(guān)系:本科生第40頁/共47頁類比較挖掘——示例（5）目標(biāo)類的主泛化關(guān)系:研究生對比類的40類比較描述的量化判別規(guī)則表示（1）類比較描述中的目標(biāo)類和對比類的區(qū)分特性也可以用量化規(guī)則來表示，即量化判別規(guī)則量化判別規(guī)則使用d-weight作為興趣度度量（qa－概化元組Cj－目標(biāo)類qa的d-weight是初始目標(biāo)類工作關(guān)系中被qa覆蓋的元組數(shù)與初始目標(biāo)類和對比類工作關(guān)系中被qa覆蓋的總元組數(shù)的比第41頁/共47頁類比較描述的量化判別規(guī)則表示（1）類比較描述中的目標(biāo)類和對比41類比較描述的量化判別規(guī)則表示（2）目標(biāo)類中較高的d-weight表明概化元組所代表的概念主要來自于目標(biāo)類較低的d-weight值則表明該概念主要來自于對比類對給定的status=“Graduate”,Birth_coutry=“Canada”,Age_range=“25-30”,Gpa=“Good”

概化元組，其d-weight=90/(90+210)=30%(什么意思？)第42頁/共47頁類比較描述的量化判別規(guī)則表示（2）目標(biāo)類中較高的d-weig42類比較描述的量化判別規(guī)則表示（3）使用類比較描述的量化判別規(guī)則表示可以更好的描述上述的情況，其形式為：比如，剛才的挖掘結(jié)果可以使用量化判別規(guī)則表達如下：請注意該區(qū)分規(guī)則表達的是充分條件，即X滿足條件，則X為研究生的概率為30%(特征化量化規(guī)則表達的是什么條件？)第43頁/共47頁類比較描述的量化判別規(guī)則表示（3）使用類比較描述的量化判別規(guī)43類描述：特征化和比較的表示類特征化和類比較是形成類描述的兩個方面，我們可以通過綜合類特征化規(guī)則和類區(qū)分規(guī)則來形成類描述規(guī)則。量化特征化規(guī)則必要條件量化判別規(guī)則充分條件量化描述規(guī)則充要條件第44頁/共47頁類描述：特征化和比較的表示類特征化和類比較是形成類描述的兩個44量化描述規(guī)則——示例(1)一個給定類的概化元組的t-weight表明給定類中該元組的典型性（e.g.歐洲的銷售(類)中，電視機(元組)占多少百分比?）一個元組的d-weight表明，給定類的元組和對比類的元組相比，有多大區(qū)別（e.g.歐洲(類)的電視機(元組)銷售和北美的電視機銷售比如何？）第45頁/共47頁量化描述規(guī)則——示例(1)一個給定類的概化元組的t-wei45量化描述規(guī)則——示例(2)對于上述交叉表，可以直接用量化描述規(guī)則來表示表明對99年AllElectronics公司的TV和計算機銷售，如果一商品在歐洲售出，則其為TV的概率為25％…該公司40％的TV在歐洲售出…第46頁/共47頁量化描述規(guī)則——示例(2)對于上述交叉表，可以直接用量化描46感謝觀看！第47頁/共47頁感謝觀看！第47頁/共47頁47數(shù)據(jù)泛化數(shù)據(jù)泛化數(shù)據(jù)庫中的數(shù)據(jù)和對象通常包含原始概念層的細節(jié)信息，數(shù)據(jù)泛化就是將數(shù)據(jù)庫中的跟任務(wù)相關(guān)的大型數(shù)據(jù)集從相對較低的概念層抽象到較高的概念層的過程。主要方法：數(shù)據(jù)立方體（OLAP使用的方法）面向?qū)傩缘臍w納方法12345概念層(Month,city,customer_group)(Month,*,*)第1頁/共47頁數(shù)據(jù)泛化數(shù)據(jù)泛化12345概念層(Month,city,48兩種不同類別的數(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ù)集的行為。E.g分類、回歸分析等第2頁/共47頁兩種不同類別的數(shù)據(jù)挖掘從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描49數(shù)據(jù)立方體的物化數(shù)據(jù)立方體有利于多維數(shù)據(jù)的聯(lián)機分析處理數(shù)據(jù)立方體使得從不同的角度對數(shù)據(jù)進行觀察成為可能方體計算（物化）的挑戰(zhàn)：海量數(shù)據(jù)，有限的內(nèi)存和時間海量數(shù)據(jù)運算對大量計算時間和存儲空間的要求第3頁/共47頁數(shù)據(jù)立方體的物化數(shù)據(jù)立方體有利于多維數(shù)據(jù)的聯(lián)機分析處理第3頁50數(shù)據(jù)立方體---基本概念(1)數(shù)據(jù)立方體可以被看成是一個方體的格，每個方體用一個group-by表示最底層的方體ABC是基本方體，包含所有3個維最頂端的方體（頂點）只包含一個單元的值，泛化程度最高上卷和下鉆操作與數(shù)據(jù)立方體的對應(yīng)BA()CABACBCABCP102圖4-1第4頁/共47頁數(shù)據(jù)立方體---基本概念(1)數(shù)據(jù)立方體可以被看成是一個方體51數(shù)據(jù)立方體---基本概念(2)基本方體的單元是基本單元，非基本方體的單元是聚集單元聚集單元在一個或多個維聚集，每個聚集維用"*"表示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<j，并且(2)對于1≤m≤n，只要am≠"*"就有am=bm第5頁/共47頁數(shù)據(jù)立方體---基本概念(2)基本方體的單元是基本單元，非基52冰山立方體(1)為了確?？焖俚穆?lián)機分析，有時希望預(yù)計算整個立方體（所有方體的所有單元）n維數(shù)據(jù)立方體包含2n個方體如果考慮概念分層部分物化是存儲空間和響應(yīng)時間的折中方案事實上，很多高維方體都是稀疏的（包含很多度量值為0的單元）第6頁/共47頁冰山立方體(1)為了確?？焖俚穆?lián)機分析，有時希望預(yù)計算整個53冰山立方體(2)對于稀疏的數(shù)據(jù)立方體，我們往往通過指定一個最小支持度閾值（也稱冰山條件），來進行部分物化，這種部分物化的方體稱之為冰山方體。比如：COMPUTECUBESales_IcebergASSELECTmonth,city,cust_grp,COUNT(*)FROMSales_InfoCUBEBYmonth,city,cust_grpHAVINGCOUNT(*)>=min_sup第7頁/共47頁冰山立方體(2)對于稀疏的數(shù)據(jù)立方體，我們往往通過指定一個54閉立方體(1)冰山方體的計算通過冰山條件（例：HAVINGCOUNT(*)>=min_sup）來減輕計算數(shù)據(jù)立方體中不重要的聚集單元的負擔(dān)，然而仍有大量不感興趣的單元需要計算比如：最小支持度為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第8頁/共47頁閉立方體(1)冰山方體的計算通過冰山條件（例：HAVING55閉立方體(2)閉單元一個單元c是閉單元，如果單元c不存在一個跟c有著相同度量值的后代d例如：上述例子中，任何一個(a1,a2,a3,*,*,…,*):10,都和他的后代有相同度量值閉立方體：一個僅有閉單元組成的數(shù)據(jù)立方體例如：(a1,a2,*,*,…,*):20(a1,a2,a3,…,a100):10(a1,a2,b3,…,b100):10第9頁/共47頁閉立方體(2)閉單元(a1,a2,*,*,…,*):20(56立方體外殼部分物化的另外一種策略：僅預(yù)計算涉及少數(shù)維的方體（比如3到5維），這些立方體形成對應(yīng)數(shù)據(jù)立方體的外殼利用外殼對其他的維組合查詢進行快速計算仍將導(dǎo)致大量方體（n很大時），類似的我們可以利用方體的興趣度，選擇只預(yù)計算立方體外殼的部分第10頁/共47頁立方體外殼部分物化的另外一種策略：僅預(yù)計算涉及少數(shù)維的方體（57立方體計算的一般策略(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)和分組操作應(yīng)用于維的屬性，以便對相關(guān)元組重新排序和聚類第11頁/共47頁立方體計算的一般策略(1)一般，有兩種基本結(jié)構(gòu)用于存儲方體58立方體計算的一般策略(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頁/共47頁立方體計算的一般策略(2)優(yōu)化技術(shù)2：同時聚集和緩存中間結(jié)59完全立方體計算的多路數(shù)組聚集方法(1)使用多維數(shù)組作為基本數(shù)據(jù)結(jié)構(gòu)，計算完全數(shù)據(jù)立方體一種使用數(shù)組直接尋址的典型MOLAP方法計算步驟（1）將數(shù)組分成塊（chunk,一個可以裝入內(nèi)存的小子方）塊還可以進一步被壓縮，以避免空數(shù)組單元導(dǎo)致的空間浪費（處理稀疏立方體）（2）通過訪問立方體單元，計算聚集?？梢詢?yōu)化訪問單元組的次序，使得每個單元被訪問的次數(shù)最小化，從而減少內(nèi)存訪問和磁盤I/O的開銷。第13頁/共47頁完全立方體計算的多路數(shù)組聚集方法(1)使用多維數(shù)組作為基本數(shù)60完全立方體計算的多路數(shù)組聚集方法(2)一個包含A,B,C的3-D數(shù)組，假定維A,B,C的基數(shù)分別是40、400和4000A(month)40個值B29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C(item)4000個值B(city)400個值442856402452362060哪個是多路數(shù)組聚集的最佳遍歷次序？將要物化的立方體：基本方體ABC，已計算，對應(yīng)于給定的3-D數(shù)組2D方體AB，AC和BC1D方體A,B,C0D頂點方體，記作all第14頁/共47頁完全立方體計算的多路數(shù)組聚集方法(2)一個包含A,B,C的361完全立方體計算的多路數(shù)組聚集方法(3)A(month)40B29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C(item)4000442856402452362060B(city)400通過掃描ABC的1～4塊，計算出塊b0c0，然后塊內(nèi)存可以分配給下一刻b1c0,如此繼續(xù)，可計算整個BC方體（一次只需一個BC塊在內(nèi)存）第15頁/共47頁完全立方體計算的多路數(shù)組聚集方法(3)A(month)B2962完全立方體計算的多路數(shù)組聚集方法(4)AB29303132123459131415166463626148474645a1a0c3c2c1c0b3b2b1b0a2a3C442856402452362060BBC方體的計算，必須掃描64塊中的每一塊；計算其他塊亦然多路數(shù)組聚集方法避免重復(fù)掃描：當(dāng)一個3D塊在內(nèi)存時，向每一個平面同時聚集思考：計算時需要多少內(nèi)存？第16頁/共47頁完全立方體計算的多路數(shù)組聚集方法(4)AB29303132163完全立方體計算的多路數(shù)組聚集方法(5)方法：各平面要按他們大小的升序排列進行排序和計算詳見書P108例4-4思想：將最小的平面放在內(nèi)存中，對最大的平面每次只是取并計算一塊第17頁/共47頁完全立方體計算的多路數(shù)組聚集方法(5)方法：各平面要按他們大64完全立方體計算的多路數(shù)組聚集方法(6)根據(jù)1到64的掃描次序，在塊內(nèi)存中保存所有相關(guān)的2-D平面所需的最小存儲為：40×400（用于整個AB平面）＋40×1000（用于AC平面一行）＋100×1000（用于BC平面一塊)＝156，000這種方法的限制：只有在維數(shù)比較小的情況下，效果才比較理想(要計算的立方體隨維數(shù)指數(shù)增長)如果維的數(shù)目比較多，可以考慮使用“自底向上的計算”或者時“冰山方體”計算第18頁/共47頁完全立方體計算的多路數(shù)組聚集方法(6)根據(jù)1到64的掃描次序65數(shù)據(jù)立方體計算與數(shù)據(jù)泛化（2）第19頁/共47頁數(shù)據(jù)立方體計算與數(shù)據(jù)泛化（2）第19頁/共47頁66數(shù)據(jù)泛化數(shù)據(jù)泛化通過將相對層次較低的值（如屬性age的數(shù)值）用較高層次的概念（如青年、中年、老年）置換來匯總數(shù)據(jù)主要方法：數(shù)據(jù)立方體（OLAP使用的方法）面向?qū)傩缘臍w納方法12345概念層(17,18,19,…,34,35,36,…,56,57,…)(青年,中年,老年)第20頁/共47頁數(shù)據(jù)泛化數(shù)據(jù)泛化12345概念層(17,18,19,…,3467什么是概念描述？概念描述是一種數(shù)據(jù)泛化的形式。概念通常指數(shù)據(jù)的匯集如frequentbuyers，graduatestudents概念描述產(chǎn)生數(shù)據(jù)的特征化和比較描述，當(dāng)所描述的概念所指的是對象類時，也稱為類描述特征化：提供給定數(shù)據(jù)匯集的簡潔匯總比較：提供兩個或多個數(shù)據(jù)集的比較描述第21頁/共47頁什么是概念描述？概念描述是一種數(shù)據(jù)泛化的形式。第21頁/共468概念描述VS.OLAP相似處：數(shù)據(jù)泛化對數(shù)據(jù)的匯總在不同的抽象級別上進行呈現(xiàn)區(qū)別：復(fù)雜的數(shù)據(jù)類型和聚集OLAP中維和度量的數(shù)據(jù)類型都非常有限（非數(shù)值型的維和數(shù)值型的數(shù)據(jù)），表現(xiàn)為一種簡單的數(shù)據(jù)分析模型概念描述可以處理復(fù)雜數(shù)據(jù)類型的屬性及其聚集用戶控制與自動處理OLAP是一個由用戶控制的過程概念描述則表現(xiàn)為一個更加自動化的過程第22頁/共47頁概念描述VS.OLAP相似處：第22頁/共47頁69數(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ù)進行泛化，方法是屬性刪除或者是屬性泛化通過合并相等的，泛化的廣義元組，并累計他們對應(yīng)的計數(shù)值進行聚集操作通過與用戶交互，將廣義關(guān)系以圖表或規(guī)則等形式，提交給用戶第23頁/共47頁數(shù)據(jù)特征化的面向?qū)傩缘臍w納一種面向關(guān)系數(shù)據(jù)查詢的、基于匯總的70數(shù)據(jù)聚焦（1）目的是獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，在DMQL中他們由inrelevanceto子句表示。示例：DMQL:描述Big-University數(shù)據(jù)庫中研究生的一般特征 useBig_University_DBminecharacteristicsas“Science_Students”inrelevancetoname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin“graduate”第24頁/共47頁數(shù)據(jù)聚焦（1）目的是獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，71數(shù)據(jù)聚焦（2）上述DMQL查詢轉(zhuǎn)換為如下SQL查詢，收集任務(wù)相關(guān)數(shù)據(jù)集Selectname,gender,major,birth_place,birth_date,residence,phone#,gpafromstudentwherestatusin{"Msc","M.A.","MBA","PhD"}初始工作關(guān)系第25頁/共47頁數(shù)據(jù)聚焦（2）上述DMQL查詢轉(zhuǎn)換為如下SQL查詢，收集任72數(shù)據(jù)泛化數(shù)據(jù)泛化的兩種常用方法：屬性刪除和屬性泛化屬性刪除的適用規(guī)則：對初始工作關(guān)系中具有大量不同值的屬性，符合以下情況，應(yīng)使用屬性刪除：在此屬性上沒有泛化操作符（比如該屬性沒有定義相關(guān)的概念分層）該屬性的較高層概念用其他屬性表示屬性泛化的使用規(guī)則：如果初始工作關(guān)系中的某個屬性具有大量不同值，且該屬性上存在泛化操作符，則使用該泛化操作符對該屬性進行數(shù)據(jù)泛化操作第26頁/共47頁數(shù)據(jù)泛化數(shù)據(jù)泛化的兩種常用方法：屬性刪除和屬性泛化第26頁/73屬性泛化控制確定什么是“具有大量的不同值”，控制將屬性泛化到多高的抽象層。屬性泛化控制的兩種常用方法：屬性泛化閾值控制對所有屬性設(shè)置一個泛化閾值或者是對每個屬性都設(shè)置一個閾值（一般為2到8）泛化關(guān)系閾值控制為泛化關(guān)系設(shè)置一個閾值，確定泛化關(guān)系中，不同元組的個數(shù)的最大值。（通常為10到30，允許在實際應(yīng)用中進行調(diào)整）兩種技術(shù)的順序使用：使用屬性泛化閾值控制來泛化每個屬性，然后使用關(guān)系閾值控制進一步壓縮泛化的關(guān)系第27頁/共47頁屬性泛化控制確定什么是“具有大量的不同值”，控制將屬性泛化到74歸納過程中的聚集值計算在歸納過程中，需要在不同的抽象層得到數(shù)據(jù)的量化信息或統(tǒng)計信息聚集值計算過程聚集函數(shù)count與每個數(shù)據(jù)庫元組相關(guān)聯(lián)，初始工作關(guān)系的每個元組的值初始化為1通過屬性刪除和屬性泛化，初始工作關(guān)系中的元組可能被泛化，導(dǎo)致相等的元組分組新的"相等的元組分組"的計數(shù)值設(shè)為初始工作關(guān)系中相應(yīng)元組的計數(shù)和e.g.52個初始工作關(guān)系中的元組泛化為一個新的元組T，則T的計數(shù)設(shè)置為52還可以應(yīng)用其他聚集函數(shù)，包括sum，avg等第28頁/共47頁歸納過程中的聚集值計算在歸納過程中，需要在不同的抽象層得到數(shù)75面向?qū)傩缘臍w納——示例挖掘BigUniversity數(shù)據(jù)庫中研究生的一般特征name：刪除屬性（大量不同值，無泛化操作符）gender：保留該屬性，不泛化major：根據(jù)概念分層向上攀升{文，理，工…}birth_place：根據(jù)概念分層location向上攀升birth_date：泛化為age，再泛化為age_rangeresidence：根據(jù)概念分層location向上攀升phone#：刪除屬性gpa：根據(jù)GPA的分級作為概念分層第29頁/共47頁面向?qū)傩缘臍w納——示例挖掘BigUniversity數(shù)據(jù)庫中76面向?qū)傩缘臍w納——示例主泛化關(guān)系初始工作關(guān)系第30頁/共47頁面向?qū)傩缘臍w納——示例主泛化關(guān)系初始工作關(guān)系第30頁/共4777面向?qū)傩缘臍w納算法輸入1.DB;2.數(shù)據(jù)挖掘查詢DMQuery;3.屬性列表;4.屬性的概念分層;5.屬性的泛化閾值；輸出主泛化關(guān)系P算法描述：Wget_task_relevant_data(DMQuery,DB)prepare_for_generalization(W)掃描W，收集每個屬性a的不同值對每個屬性a，根據(jù)閾值確定是否刪除，如果不刪除，則計算其最小期望層次L，并確定映射對(v,v`)Pgeneralization(W)通過使用v`代替W中每個v，累計計數(shù)并計算所有聚集值，導(dǎo)出P每個泛化元組的插入或累積計數(shù)用數(shù)組表示P第31頁/共47頁面向?qū)傩缘臍w納算法輸入第31頁/共47頁78導(dǎo)出泛化的表示(1)泛化關(guān)系一部分或者所有屬性得到泛化的關(guān)系，包含計數(shù)或其他度量值的聚集交叉表二維交叉表使用每行顯示一個屬性，使用每列顯示另外一個屬性將結(jié)果集映射到表中可視化工具：條形圖、餅圖、曲線和數(shù)據(jù)立方體瀏覽工具（用單元的大小代表計數(shù)，用單元亮度代表另外的度量）P133-134第32頁/共47頁導(dǎo)出泛化的表示(1)泛化關(guān)系P133-134第32頁/共479導(dǎo)出泛化的表示(2)量化規(guī)則使用t_weight表示主泛化關(guān)系中每個元組的典型性量化特征規(guī)則將泛化的結(jié)果映射到相應(yīng)的量化特征規(guī)則中，比如：量化特征規(guī)則中每個析取代表一個條件，一般，這些條件的析取形成目標(biāo)類的必要條件，因為該條件是根據(jù)目標(biāo)類的所有情況導(dǎo)出的。也就是說，目標(biāo)類的所有元組必須滿足該條件。然而，該規(guī)則可能不是目標(biāo)類的充分條件，因為滿足同一條件的元組可能屬于其他類。E.g.第33頁/共47頁導(dǎo)出泛化的表示(2)量化規(guī)則量化特征規(guī)則中每個析取代表一個80挖掘類比較：區(qū)分不同的類類比較挖掘的目標(biāo)是得到將目標(biāo)類與對比類相區(qū)分的描述。目標(biāo)類和對比類間必須具有可比性，即兩者間要有相似的屬性或維。本科生VS.研究生；studentVS.address很多應(yīng)用于類特征化的技巧（處理單個類的多層數(shù)據(jù)的匯總和特征化）可以應(yīng)用于類比較，比如屬性泛化屬性泛化必須在所有比較類上同步進行，將屬性泛化到同一抽象層后進行比較。E.g.CityVScountry第34頁/共47頁挖掘類比較：區(qū)分不同的類類比較挖掘的目標(biāo)是得到將目標(biāo)類與對比81類比較的過程數(shù)據(jù)收集通過查詢處理收集數(shù)據(jù)庫中相關(guān)的數(shù)據(jù)，并將其劃分為一個目標(biāo)類和一個或多個對比類維相關(guān)分析如果存在較多的維，則應(yīng)當(dāng)對這些類進行維相關(guān)分析，僅選擇高度相關(guān)的維進行進一步分析。（可以使用基于熵的度量）同步泛化同步的在目標(biāo)類和對比類上進行泛化，泛化到維閾值控制的層，得到主目標(biāo)類關(guān)系/方體和主對比類關(guān)系/方體導(dǎo)出比較的表示用可視化技術(shù)表達類比較描述，通常會包含“對比”度量，反映目標(biāo)類與對比類間的比較(e.gcount%)第35頁/共47頁類比較的過程數(shù)據(jù)收集第35頁/共47頁82類比較挖掘——示例（1）任務(wù)挖掘描述BigUniversity本科生和研究生的類比較任務(wù)的DMQL描述useBig_University_DBminecomparisonas“grad_vs_undergrad_students”inrelevanceto

name,gender,major,birth_place,birth_date,residence,phone#,gpafor“graduate_students”wherestatusin“gra