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