《數(shù)據(jù)倉庫和數(shù)據(jù)挖掘》復習大綱

數(shù)據(jù)挖掘復習第頁《數(shù)據(jù)倉庫和數(shù)據(jù)挖掘》復習大綱一、共三道大題：填空題（每空1分，共20分），簡答題（8道小題，每題5分，共40分），計算、分析與證明題（四道題，共40分）二、復習范圍：填空題與簡答題：數(shù)據(jù)挖掘（DataMining）：從海量數(shù)據(jù)中提取有興趣的模式（Pattern）或知識（knowledge）。數(shù)據(jù)倉庫是面向主題的、集成的、時變的、非易失的數(shù)據(jù)集合，它用來支持管理部門的決策過程。名詞解釋OLTP:On-LineTransactionProcessing聯(lián)機事務處理。其基本特征是顧客的原始數(shù)據(jù)可以立即傳送到計算中心進行處理，并在很短的時間內(nèi)給出處理結果。對響應時間要求比較高。傳統(tǒng)關系數(shù)據(jù)庫的主要任務日常操作:購買,存貨,財務等.OLAP:On-LineAnalyticalProcessing聯(lián)機分析處理。OLTP是傳統(tǒng)的關系型數(shù)據(jù)庫的主要應用，主要是基本的、日常的事務處理，例如銀行交易。OLAP是數(shù)據(jù)倉庫系統(tǒng)的主要應用，支持復雜的分析操作，側(cè)重決策支持，并且提供直觀易懂的查詢結果。數(shù)據(jù)倉庫的主要任務數(shù)據(jù)分析與決策支持KDD：KnowledgeDiscoveryinData數(shù)據(jù)中的知識發(fā)現(xiàn)。定義：從數(shù)據(jù)集中別出有效的、新穎的、潛在有用的，以及最終可理解的模式的非平凡過程。知識發(fā)現(xiàn)將信息變?yōu)橹R。BI：BusinessIntelligence商業(yè)智能。BI是一套完整的解決方案，用來將企業(yè)中現(xiàn)有的數(shù)據(jù)進行有效的整合，快速準確的提供報表并提出決策依據(jù)，幫助企業(yè)做出明智的業(yè)務經(jīng)營決策。數(shù)據(jù)挖掘是BI的核心。ETL:Extraction-Transformation-Loading數(shù)據(jù)提取、轉(zhuǎn)換和加載。ETL負責將分散的、異構數(shù)據(jù)源中的數(shù)據(jù)如關系數(shù)據(jù)、平面數(shù)據(jù)文件等抽取到臨時中間層后進行清洗、轉(zhuǎn)換、集成，最后加載到數(shù)據(jù)倉庫或數(shù)據(jù)集市中，成為聯(lián)機分析處理、數(shù)據(jù)挖掘的基礎。2.1數(shù)據(jù)倉庫的特征：數(shù)據(jù)倉庫是面向主題的是匯總的是集成的非易失的(是不可更新的)時變的(是隨時間變化而變化的)大容量非規(guī)范化元數(shù)據(jù)數(shù)據(jù)源2.2數(shù)據(jù)倉庫的特點有：效率足夠高（2）數(shù)據(jù)質(zhì)量（3）擴展性（4）面向主題2.3數(shù)據(jù)倉庫的模型：（1）企業(yè)倉庫（Enterprisewarehouse）：搜集了關于主題的所有信息，跨越整個組織。（2）數(shù)據(jù)集市（DataMart）：包含企業(yè)范圍數(shù)據(jù)的一個子集，對于特定的用戶是有用的，其范圍限于選定的主題。（3）虛擬倉庫（Virtualwarehouse）：操作數(shù)據(jù)庫上視圖的一組集合。為了有效處理查詢，只有一些可能的匯總視圖被物化。虛擬倉庫易于建立，但是需要操作數(shù)據(jù)庫服務器具有剩余能力。常用多維數(shù)據(jù)結構建模（數(shù)據(jù)立方體）。數(shù)據(jù)立方體的每個維對應于模式中的一個或一組屬性，每個單元存放某種聚集度量值。數(shù)據(jù)立方體提供數(shù)據(jù)的多維視圖，并允許預計算和快速訪問匯總數(shù)據(jù)。2.4數(shù)據(jù)倉庫的多層結構：通常，數(shù)據(jù)倉庫采用三層結構：（1）底層是數(shù)據(jù)倉庫服務器，它幾乎總是一個關系數(shù)據(jù)庫系統(tǒng)?！叭绾斡稍搶犹崛?shù)據(jù)，創(chuàng)建數(shù)據(jù)倉庫？”使用稱作網(wǎng)間連接程序的應用程序，由操作數(shù)據(jù)庫和外部數(shù)據(jù)源（如，由外部咨詢者提供的顧客側(cè)面信息）提取數(shù)據(jù)。網(wǎng)間連接程序由下面的DBMS支持，允許客戶程序產(chǎn)生SQL代碼，在服務器上執(zhí)行。網(wǎng)間連接程序的例子包括ODBC（開放數(shù)據(jù)庫連接）和微軟的OLE-DB（數(shù)據(jù)庫開放鏈接和嵌入），JDBC（Java數(shù)據(jù)庫連接）。（2）中間層是OLAP服務器，其典型的實現(xiàn)或者是（1）關系OLAP（ROLAP）模型，即擴充的關系DBMS，它將多維數(shù)據(jù)上的操作映射為標準的關系操作；或者是（2）多維OLAP（MOLAP）模型，即特殊的服務器，它直接實現(xiàn)多維數(shù)據(jù)和操作。（3）頂層是客戶，它包括查詢和報告工具、分析工具、和/或數(shù)據(jù)挖掘工具（例如，趨勢分析、預測等）。數(shù)據(jù)倉庫的視圖（1）自頂向下視圖：可以選擇數(shù)據(jù)倉庫所需要的相關信息。這些信息能夠滿足當前和未來商務的需求。（2）數(shù)據(jù)源視圖：解釋操作數(shù)據(jù)庫系統(tǒng)收集、存儲和管理的信息。這些信息可能以不同的詳細程度和精度建檔，存放在由個別數(shù)據(jù)源表到集成的數(shù)據(jù)源表中。通常，數(shù)據(jù)源用傳統(tǒng)的數(shù)據(jù)建模技術，如ER模型或者CASE工具建模。（3）數(shù)據(jù)倉庫視圖：包括事實表和維表。提供存放在數(shù)據(jù)倉庫內(nèi)部的信息。包括預計算的總和與計數(shù)，以及提供歷史別進的關于源、原始日期和時間等信息。（4）商務視圖：是從最終用戶的角度透視數(shù)據(jù)倉庫中的數(shù)據(jù)。數(shù)據(jù)立方體的有效計算：部分物化：部分方體物化，只預計算更“有用”的部分方體完全物化：表示數(shù)據(jù)立方體的所有方體都預計算不物化：多路數(shù)組聚集（Multiwayarrayaggregation）：完全立方體計算的方法度量的分類：(1)分布式的（distributive）:一個聚集函數(shù)是分布的，如果它能以以下分布式進行計算:如果將函數(shù)用于n個聚集值得到的結果，與將函數(shù)用于所有數(shù)據(jù)得到的結果一樣，則該函數(shù)可以用分布式計算。如,count(),sum(),min(),max().(2)代數(shù)的（algebraic）:一個函數(shù)是代數(shù)的，如果它能夠由一個具有M個參數(shù)的代數(shù)函數(shù)計算（其中M是一個有界整數(shù)），而每個參數(shù)都可以用一個分布聚集函數(shù)得到。如,avg(),standard_deviation().整體的（holistic）:如果描述它的子聚集所需的存儲沒有一個常數(shù)界，即不存在一個具有M個參數(shù)的代數(shù)函數(shù)進行這一計算（其中M是常數(shù)）。如,median()（中位數(shù)）,mode()（出現(xiàn)次數(shù)最多的數(shù)，眾數(shù)）等。對于發(fā)現(xiàn)的模式有：4.1興趣度度量一個模式是有趣的，如果它是：易理解的,在一定程度上對新數(shù)據(jù)或測試數(shù)據(jù)是有效的,可能有用的,新穎的,或者驗證了用戶正在確證的某一個假設4.2主觀與客觀興趣度度量客觀的:基于統(tǒng)計或模式的結構,如支持度,可信度等.主觀的:基于用戶的觀點,如期望之中的，新穎的，等等.聚類分析常用的數(shù)據(jù)結構數(shù)據(jù)矩陣（2模）區(qū)分矩陣（1模）兩種學習模型（1）有監(jiān)督學習模型：提供了每個訓練元組的類標號，稱作監(jiān)督學習，即分類器的學習在被告知每個訓練元組屬于哪個類的監(jiān)督下進行。（2）無監(jiān)督學習（聚類）模型：每個訓練元組的類標號都是未知的，并且要學習的類的個數(shù)或集合也可能事先不知道。為什么需要數(shù)據(jù)預處理及其主要內(nèi)容現(xiàn)實世界的數(shù)據(jù)一般都是臟的、不完整的、含噪音的和不一致的，數(shù)據(jù)預處理技術可以改進數(shù)據(jù)的質(zhì)量，從而有助于提高其后的挖掘過程的精度和性能。由于高質(zhì)量的決策必須依賴于高質(zhì)量的數(shù)據(jù)，因此數(shù)據(jù)預處理是只是發(fā)現(xiàn)過程中重要的步驟。檢測數(shù)據(jù)異常、盡早地調(diào)整數(shù)據(jù)并規(guī)約待分析的數(shù)據(jù)，將在決策過程中得到高回報。不完整的:缺少屬性值,感興趣的屬性缺少屬性值,或僅包含聚集數(shù)據(jù)含噪聲的:包含錯誤或存在孤立點不一致的:在名稱或代碼之間存在著差異（2）數(shù)據(jù)預處理的主要任務：數(shù)據(jù)清洗（Datacleaning）填充遺失的數(shù)據(jù),平滑噪聲數(shù)據(jù),辨識或刪除孤立點,解決不一致性問題數(shù)據(jù)集成（Dataintegration）對多個數(shù)據(jù)庫，數(shù)據(jù)立方或文件進行集成數(shù)據(jù)變換（Datatransformation）規(guī)范化與聚集（Normalizationandaggregation）數(shù)據(jù)約簡（Datareduction）得到數(shù)據(jù)集的壓縮表示，它小的多，但能夠產(chǎn)生同樣的（或幾乎同樣的）分析結果數(shù)據(jù)離散化（Datadiscretization）特別對數(shù)字值而言非常重要挖掘的知識類型描述性的：刻畫目標數(shù)據(jù)中數(shù)據(jù)的一般性質(zhì)。預測性的：在當前數(shù)據(jù)上進行歸納，以便做出預測。1、概念/類描述：特征化和區(qū)分2、挖掘頻繁模式、關聯(lián)和相關3、分類和預測4、聚類分析5、離群點分析6、演變分析常見的OLAP操作上卷Rollup(上鉆drill-up):通過一個維的概念分層向上攀升或通過維規(guī)約，在數(shù)據(jù)立方體上進行聚集。下鉆Drilldown(rolldown):上卷的逆操作，它由不太詳細的數(shù)據(jù)得到更詳細的數(shù)據(jù)?？梢酝ㄟ^沿維的概念分層向下或引入新的維實現(xiàn)。切片Slice與切塊dice投影與選擇。轉(zhuǎn)軸Pivot(rotate)是一種目視操作，它轉(zhuǎn)動數(shù)據(jù)的視角，提供數(shù)據(jù)的替代表示其它操作：鉆過drillacross：執(zhí)行涉及多個事實表的查詢。鉆透drillthrough：使用SQL的機制，鉆到數(shù)據(jù)立方的底層，到后端關系表。關聯(lián)規(guī)則的確定性度量與實用性度量支持度和置信度是關聯(lián)規(guī)則的確定性度量與實用性度量。（1）支持度：事務包含XUY的概率，即support=P(XUY)支持度計算：Support(XY)=P(XUY)={XUY}的支持度計數(shù)（模式或項集在DB中出現(xiàn)的頻率）/事務表中總的事務數(shù)（2）置信度：事務同時包含X與Y的條件概率：confidence=P(Y|X)置信度計算：Confidence(XY)=P(Y|X)=P(XUY)/P(X)=｛XUY｝支持度計數(shù)/X支持度計數(shù)數(shù)據(jù)立方的兩種表。維度表事實表數(shù)據(jù)挖掘在互聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)的應用；商務智能搜索引擎知識發(fā)現(xiàn)過程的主要步驟知識發(fā)現(xiàn)的主要過程：創(chuàng)建目標數(shù)據(jù)集：數(shù)據(jù)選擇數(shù)據(jù)預處理：數(shù)據(jù)清洗、數(shù)據(jù)約簡與數(shù)據(jù)變換構建數(shù)據(jù)倉庫（可選）數(shù)據(jù)挖掘模式評價與知識表示知識的使用OLTP與OLAP的主要區(qū)別聯(lián)機事務處理OLTP(on-linetransactionprocessing)；聯(lián)機分析處理OLAP(on-lineanalyticalprocessing)OLTP和OLAP的區(qū)別：（1）用戶和系統(tǒng)的面向性:OLTP面向顧客，而OLAP面向市場；（2）數(shù)據(jù)內(nèi)容：OLTP系統(tǒng)管理當前數(shù)據(jù)，而OLAP管理歷史的數(shù)據(jù)；（3）數(shù)據(jù)庫設計：OLTP系統(tǒng)采用實體-聯(lián)系（ER)模型和面向應用的數(shù)據(jù)庫設計，而OLAP系統(tǒng)通常采用星形和雪花模型；（4）視圖：OLTP系統(tǒng)主要關注一個企業(yè)或部門內(nèi)部的當前數(shù)據(jù)，而OLAP系統(tǒng)主要關注匯總的統(tǒng)一的數(shù)據(jù)；（5）訪問模式：OLTP訪問主要有短的原子事務組成，而OLAP系統(tǒng)的訪問大部分是只讀操作，盡管許多可能是復雜的查詢。為什么需要構建單獨隔離的數(shù)據(jù)倉庫（1）使得操作數(shù)據(jù)庫與數(shù)據(jù)倉庫都獲得高性能：DBMS—OLTP:訪問方法,索引,并發(fā)控制,數(shù)據(jù)恢復。Warehouse—OLAP:復雜OLAP查詢,多維視圖,整理。（2）對數(shù)據(jù)與功能的要求不同:丟失的數(shù)據(jù):決策支持需要歷史數(shù)據(jù)，而傳統(tǒng)數(shù)據(jù)庫并不一定維護歷史數(shù)據(jù)。數(shù)據(jù)整理:決策支持需要對異構數(shù)據(jù)源進行數(shù)據(jù)整理。數(shù)據(jù)質(zhì)量:不同的數(shù)據(jù)源常常具有不一致的數(shù)據(jù)表示，編碼結構與格式。數(shù)據(jù)預處理（缺失數(shù)據(jù)）方法：（1）忽略元組:除非元組有多個屬性缺少值，否則該方法不是很有效（2）人工填充：費時費力（3）自動填充：使用一個全局常量填充:如,“unknown”,會誤認為是一個新的、有意義的類?!該屬性的平均值使用與給定元組屬同一類的所有樣本的該屬性的平均值使用最可能的值:使用基于推導的方法，如Bayesian公式或決策樹數(shù)據(jù)倉庫的設計模式建模數(shù)據(jù)倉庫:維&度量星型模式（Starschema）:一個事實表以及一組與事實表連結的維表。每維只用一個表表示，而每個表包含一組屬性。雪花模式（Snowflakeschema）:雪花模式是星型模式的變種，其中某些維表是規(guī)范化的。（normalized），因而把數(shù)據(jù)進一步分解到附加的表中。事實星座（Factconstellations）:多個事實表分享共同的維表，這種模式可以看作星型模式的集合，因此稱為星系模式（galaxyschema）或事實星座。三種度量函數(shù)的定義（1）離散度量函數(shù)：如果x=y，則d(x,y)=0，否則d(x,y)=1（2）歐幾里得度量函數(shù)（3）曼哈頓度量函數(shù)：曼哈頓距離=準確率度量函數(shù)：Accuracy=sensitivity*pos/(pos+neg)+specificity*(neg/(neg+pos))預測其誤差度量分箱平滑19.1噪聲:是一個策略變量中的隨即錯誤或偏差平滑（Smoothing）:去除噪聲數(shù)據(jù)分箱平滑：對數(shù)據(jù)進行排序，然后把它們劃分到箱，然后通過箱平均值，箱中值或者箱邊界值進行平滑。分箱的方法主要有：①等深分箱法②等寬分箱法數(shù)據(jù)平滑的方法主要有：平均值法、邊界值法和中值法19.2簡單的平滑方法:分箱（1）等寬(距離)劃分:根據(jù)屬性值的范圍劃分成N等寬的區(qū)間如果A和B屬性值的最大與最小值，則區(qū)間寬度為:W=(B–A)/N.很直接，但孤立點將會對此方法有很大的影響（2）等深(頻率)劃分:劃分成N個區(qū)間，每個區(qū)間含有大約相等地樣本數(shù)具有較好的數(shù)據(jù)擴展性分箱方法示例*價格排序:4,8,9,11,15,21,21,22,24,25,26,28,29,30,40*劃分成箱(等深):-Bin1:4,8,9,11,15-Bin2:21,21,22,24,25-Bin3:26,28,29,30,40*用箱平均值平滑數(shù)據(jù):-Bin1:9.4,9.4,9.4,9.4,9.4-Bin2:22.6,22.6,22.6,22.6,22.6-Bin3:30.6,30.6,30.6,30.6,30.6*用箱中值平滑數(shù)據(jù):-Bin1:9,9,9,9,9-Bin2:22,22,22,22,22-Bin3:29,29,29,29,29無監(jiān)督離散化（如分箱）、有監(jiān)督離散法（基于熵）（1）離散化：把連續(xù)型屬性的取值范圍劃分為區(qū)間，通過離散化減少數(shù)據(jù)集大小，為了進一步分析做好準備（2）數(shù)值數(shù)據(jù)的離散化——分箱；直方圖分析：常用的規(guī)約技術，把數(shù)據(jù)劃分成若干個桶，并存儲每個桶的平均值或和，常用于定量問題?！垲惙治觯喊褦?shù)據(jù)集合劃分成類，然后僅僅存儲這些類的表示?？梢孕纬蓪哟尉垲惤Y構，并用多維索引樹結構存儲。有多種聚類的定義以及聚類算法?！陟氐碾x散化：給定一個樣本集合S，如果用邊界值T把S畫風成2個區(qū)間S1和S2，則劃分后的熵為：I(S,T)=(|S1|/|S|)*Ent(S1)+(|S2|/|S|)*Ent(S2)選擇某一邊界T的準則是：它使其后劃分得到的信息增益最大。停止條件是：Ent(S)–I(S,T)>threshold該方法可以約簡數(shù)據(jù)集并提高分類精度。評估分類器準確率的方法使用靈敏性和特效行度量。靈敏度稱為真正（識別）率，特效行是真負率（正確識別的負元組百分比）靈敏性sensitivity=t_pos/pos特效行specificity=t_neg/negprecision=t_pos/(t_pos+f_pos)其中t_pos是正確的cancer元組數(shù)量，pos為總的cancer元組數(shù)量Accuracy=sensitivity*pos/(pos+neg)+specificity*(neg/(neg+pos))方法：（1）保持方法和隨機子抽樣：保持（holdout）方式是我們目前位置討論準確率時暗指的方法。給定數(shù)據(jù)隨機劃分成兩個獨立的集合。訓練集和檢驗集。通常，三分之二的數(shù)據(jù)分配到訓練集，其余三分之一分配到檢驗集。使用訓練集導出模型，其準確率用檢驗集估計。估計是悲觀的，因為只有一部分初始數(shù)據(jù)用于導出模型。隨機子抽樣：是保持方法的一種變形，它將保持方法重復k次，總準確率估計取每次迭代準確率的平均值。（2）交叉確認：在k折交叉確認，初始數(shù)據(jù)隨機劃分成k個互不相交的子集或折D1，D2，……Dk，每個折的大小大致相等。訓練和檢驗進行k次。在第i次迭代，劃分Di用作檢驗集，其余劃分一起用來訓練模型。對于分類，準確率估計是k次迭代正確分類的總數(shù)除以初始數(shù)據(jù)中的元組總數(shù)。留一：是k折交叉確認的特殊情況，其中k設置為初始元組數(shù)。也就是說，每次只給檢驗集留出一個樣本。在分層交叉確認中，折被分層，使得每個折中元組的類分布與在初始數(shù)據(jù)中的大致相同。（3）自助法：自助法從給定訓練元組中有放回均勻抽樣。每當選中一個元組，它等可能地被再次選中并添加到訓練集中。基于規(guī)則的分類器規(guī)則：前件，后件，覆蓋基于規(guī)則的分類若干問題：學習到的規(guī)則能夠覆蓋整個示例空間嗎？－缺省規(guī)則如何學到最優(yōu)規(guī)則？－NP－h(huán)ard問題不同類型屬性之間的相似性計算（realvalue、binary、nominal、orderedset）（1）區(qū)間值變量：S=平均絕對偏差M=平均值相似性計算z=(x–m)/s（2）二元變量：（3）標稱型變量：M:匹配數(shù)目p：全部變量數(shù)目D(i,j)=(p-m)/p（4）序數(shù)型變量：把每個變量的范圍映射到[0,1]例如：一共7個變量，小學文憑這個變量數(shù)為1則：z=(1–1)/(7–1)Z=(r–1)/(M–1)（5）向量對象間的余弦相似性：常見的聚類優(yōu)化目標（最小化聚類間相似性、最大化聚類內(nèi)相似性等）及k-center、k-c