【正文】 ne: 問(wèn)題的引入,找一個(gè)便宜并且離海灘近的旅館 系統(tǒng)無(wú)法決定哪些是最好的，但它會(huì)提供所有的備選(interesting)旅館，也即它們不會(huì)在兩個(gè)維上都比其他任何旅館差，稱(chēng)其為Skyline,Skyline: 問(wèn)題的引入,稱(chēng)點(diǎn)x統(tǒng)治(dominate)點(diǎn)y，如果x在所有維上都不比y差，并且至少在一個(gè)維上好過(guò)y 旅館 (price=50, distance=0.8)統(tǒng)治 (price=100,distance=1.0),Skyline：更高、更靠近河流的建筑,東食西宿：更英俊、更有錢(qián),Skyline的性質(zhì),一個(gè)集合M，一個(gè)單調(diào)計(jì)分函數(shù)R,如果p?M使得R最大，那么p一定在M的Skyline中 不管你如何偏好旅館的價(jià)格和距離，你最中意的旅館總是在Skyline中 對(duì)Skyline中的任意一點(diǎn)p，總存在一個(gè)單調(diào)計(jì)分函數(shù)，p使得它最大，也即Skyline不會(huì)包含不是任何人偏好的旅館 統(tǒng)治滿足傳遞性，也即如果p統(tǒng)治q，q統(tǒng)治r，則p統(tǒng)治r,帶Skyline的SQL擴(kuò)展,SELECT…FROM…WHERE GROUP BY…HAVING… SKYLINE OF [ DISTINCT ] d1 [ MIN | MAX | DIFF ], … , dn [ MIN | MAX | DIFF ] TOP … ORDER BY…,SKYLINE OF d1 MIN ,d2 MAX ,d3 DIFF p(p1,p2,p3)統(tǒng)治q(q1,q2,q3)，如果 p1≤q1, p2≥q2, p3=q3,帶Skyline的SQL示例,用嵌套子查詢(xún)實(shí)現(xiàn)Skyline,Skyline的大小,聯(lián)機(jī)分析處理（OLAP）,存在著大量的分析型應(yīng)用 ——要求對(duì)大量的數(shù)據(jù)從各個(gè)角度進(jìn)行綜合分析（多維分析） 典型分析應(yīng)用： 對(duì)一些統(tǒng)計(jì)指標(biāo) （銷(xiāo)售金額） 從不同角度（維） （時(shí)間、地區(qū)、商品類(lèi)型） 從不同級(jí)別（層次）（地區(qū)：縣、地市、省、大區(qū)） 今年銷(xiāo)售量下降的因素（時(shí)間、地區(qū)、商品、銷(xiāo)售部門(mén)） 某種商品今年的銷(xiāo)售情況與以往相比，有怎樣的變化？每年的第一季度商品銷(xiāo)售在各類(lèi)商品上的分布情況怎樣？,多維數(shù)據(jù)模型,關(guān)系表與多維Cube,多維數(shù)據(jù)模型的基本組成：維+度量,多維數(shù)據(jù)模型,變量（指標(biāo)） 數(shù)據(jù)的實(shí)際意義，一般是一個(gè)數(shù)值度量指標(biāo) 例如：銷(xiāo)售量、銷(xiāo)售額，…… 而具體數(shù)據(jù)（如“10000”）是變量的一個(gè)值 維 觀察數(shù)據(jù)的特定角度 例如：時(shí)間、地區(qū)，…… 維的層次 特定角度的不同細(xì)節(jié)程度 例如：時(shí)間維：日、周、月、季、年 地理維：城市、地區(qū)、國(guó)家,多維分析的基本分析動(dòng)作,切片（Slice） 從多維數(shù)組選定一個(gè)二維子集，切出一個(gè)“平面” 切塊（Dice） 從多維數(shù)組選定一個(gè)三維子集，切出一個(gè)“立方體” 旋轉(zhuǎn) 改變一個(gè)報(bào)告（或頁(yè)面）顯示的維方向,關(guān)系的交叉表表示,關(guān)系表,關(guān)系的交叉表表示,交叉表,用SQL生成交叉表,SELECT Model, Year, Color, SUM(Sales) FROM Sales WHERE Model = 39。ALL Years39。) END FROM my_cube GROUP BY model, theyear, color WITH ROLLUP,OLAP Server的分類(lèi)：數(shù)據(jù)存儲(chǔ)方式,Relational OLAP (ROLAP) 利用關(guān)系數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)和管理基本數(shù)據(jù)和聚合數(shù)據(jù)，并利用一些中間件來(lái)支持缺失數(shù)據(jù)的處理 具有良好的可擴(kuò)展性 Multidimensional OLAP (MOLAP) 利用多維數(shù)據(jù)庫(kù)來(lái)存放和管理基本數(shù)據(jù)和聚合數(shù)據(jù) ，其中需要對(duì)稀疏矩陣處理技術(shù) 對(duì)預(yù)綜合的數(shù)據(jù)進(jìn)行快速索引 Hybrid OLAP (HOLAP) 利用關(guān)系數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)和管理基本數(shù)據(jù)，利用多維數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)和管理聚合數(shù)據(jù),多維數(shù)據(jù)庫(kù)存儲(chǔ),由許多（經(jīng)壓縮的）類(lèi)似于數(shù)組的對(duì)象構(gòu)成 每個(gè)對(duì)象由聚集成組的單元塊組成 每個(gè)單元塊按類(lèi)似于多維數(shù)組的結(jié)構(gòu)存儲(chǔ) 通過(guò)直接偏移計(jì)算進(jìn)行存取 每個(gè)對(duì)象帶有（壓縮的）索引和指針結(jié)構(gòu) 分析時(shí)常需維間的組合 需“旋轉(zhuǎn)”（數(shù)據(jù)立方體）及“切片” 高效的稀疏數(shù)據(jù)處理能力，略過(guò)缺失和重復(fù)數(shù)據(jù) 許多維間的組合沒(méi)有值：6月份冰鞋銷(xiāo)售量 許多值重復(fù)存儲(chǔ)：今年醬油的價(jià)格,用關(guān)系結(jié)構(gòu)表示多維數(shù)據(jù),關(guān)系數(shù)據(jù)庫(kù)使用廣泛，相當(dāng)成熟 用兩類(lèi)表來(lái)表示多維結(jié)構(gòu): 事實(shí)表，維表 事實(shí)(fact)表：用來(lái)存儲(chǔ)變量值和各維的碼值 維表：用來(lái)存儲(chǔ)維的描述信息(元數(shù)據(jù))，包括層次和類(lèi)等 事實(shí)表描述了主題的數(shù)據(jù)，維表是從不同的角度描述了對(duì)主題的分析尺度 維表就象星星的角一樣，分布在事實(shí)表的外圍，描述了業(yè)務(wù)的各個(gè)維,星型模式（Star Schema）,雪片模式(Snow Flake Schema),雪片模式,一個(gè)廣為流傳的數(shù)據(jù)挖掘例子,美國(guó)加州某個(gè)超市連鎖店通過(guò)數(shù)據(jù)挖掘從記錄著每天銷(xiāo)售和顧客基本情況的數(shù)據(jù)庫(kù)中發(fā)現(xiàn): 在下班后前來(lái)購(gòu)買(mǎi)嬰兒尿布的顧客多數(shù)是男性，他們往往也同時(shí)購(gòu)買(mǎi)啤酒。設(shè)sij是子集sj中類(lèi)Ci的樣本數(shù)，則根據(jù)由A劃分成子集的熵或期望信息是： 其中pij= sij / sj 選擇A作為分裂屬性獲得的信息增益為： Gain(A)=I(s1,…, sm) E(A),決策樹(shù)分類(lèi)舉例：訓(xùn)練數(shù)據(jù)集,決策樹(shù)分類(lèi)舉例：計(jì)算屬性的熵,類(lèi)標(biāo)號(hào)屬性 buys_computer，有兩個(gè)不同值{yes,no}， 有兩個(gè)類(lèi)，類(lèi)yes有9個(gè)樣本，類(lèi)no有5個(gè)樣本 計(jì)算屬性的熵 age = “40”: s13=3, s23=2, I(s13, s23)=0.971,決策樹(shù)分類(lèi)舉例：計(jì)算屬性的熵,Gain(age)=I(s1, s2) E(age)=0.246 Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048 因此選擇age作為分裂屬性,決策樹(shù)分類(lèi)舉例：分枝,age?,overcast,=30,40,3040,決策樹(shù)分類(lèi)舉例：最終結(jié)果,由決策樹(shù)產(chǎn)生規(guī)則,IF age = “40” AND credit_rating = “excellent” THEN buys_computer = “no” IF age = “40” AND credit_rating = “fair” THEN buys_computer = “yes”,聚類(lèi)分析（Clustering）,含義 聚類(lèi)是把一組對(duì)象按照相似性歸成若干類(lèi)別，即“物以類(lèi)聚”。例如，信譽(yù)良好的持卡人的特征為： 收入在25000以上 年齡在4555之間 居住在XYZ地區(qū) 對(duì)同類(lèi)記錄特征的描述（規(guī)則或模型）可用來(lái)分類(lèi)新記錄,分類(lèi)分析舉例,顧客購(gòu)物分類(lèi) 顧客屬性：姓名、年齡、收入、職業(yè)、信譽(yù)度 為每個(gè)顧客賦予一個(gè)標(biāo)記，即是否購(gòu)買(mǎi)計(jì)算機(jī) 按該標(biāo)記將顧客分類(lèi)，建立分類(lèi)模型 新來(lái)一個(gè)顧客，按分類(lèi)模型識(shí)別該顧客是否屬于購(gòu)買(mǎi)計(jì)算機(jī)類(lèi) 若顧客屬于購(gòu)買(mǎi)計(jì)算機(jī)的類(lèi)別，則將有關(guān)新的計(jì)算機(jī)的促銷(xiāo)材料分發(fā)給他,利用決策樹(shù)進(jìn)行數(shù)據(jù)分類(lèi),決策樹(shù) 一個(gè)類(lèi)似與流程圖的樹(shù)結(jié)構(gòu) 內(nèi)部接點(diǎn)表示一個(gè)與屬性值相關(guān)的判斷 邊表示判斷的結(jié)果 每個(gè)葉節(jié)點(diǎn)是一個(gè)類(lèi)別的標(biāo)識(shí),利用決策樹(shù)進(jìn)行數(shù)據(jù)分類(lèi)：ID3,利用決策樹(shù)進(jìn)行數(shù)據(jù)分類(lèi)：ID3,隨機(jī)判定分類(lèi)器 雞蛋好壞的概率分別為6/10, 4/10 熵為(6/10*log(6/10)+4/10*log(4/10)),選擇用手搖晃判定的分類(lèi)器 不搖晃時(shí)雞蛋好壞的概率分別為6/8, 2/8 搖晃時(shí)雞蛋好壞的概率分別為0/2, 2/2 熵為((6/8*log(6/8)+2/8*log(2/8))*8/10+ (0/2*log(0/2)+2/2*log(2/2))*2/10),選擇鹽水判定的分類(lèi)器 沉下時(shí)雞蛋好壞的概率分別為6/6, 0/6 浮起時(shí)雞蛋好壞的概率分別為0/4, 4/4 熵為0,利用決策樹(shù)進(jìn)行數(shù)據(jù)分類(lèi)：ID3,算法：Generate_decision_tree 輸入:訓(xùn)練樣本samples；候選屬性集合attribute_list