第1章數據挖掘及其算法概覽

數據挖掘的目標是支持利用數據進行合理的決策。數據挖掘可以與數據倉庫結合起來幫助實現某些類型的決策。數據庫知識發現基本概念數據挖掘目標數據挖掘產生的背景數據庫知識發現基本概念第1章數據挖掘及其算法概覽VolumeVelocityVariety海量高速多格式多格式海量數據包括多種多樣不同格式的數據。從簡單的電子郵件、數據日志、信用卡記錄到儀器收集的科學研究數據、醫療數據以及豐富的媒體數據（圖像、音、視頻等）等。半結構和非結構化數據所占的比重日益增加，目前這些不同格式的數據需要采用不同的處理方法。這對傳統上以結構化數據為主的數據管理技術帶來了新的挑戰。

淘寶數據內容：日志型數據、文本數據、關系型數據；涉及的維度多（100個不同行業的商品維度、五級商品類目體系、80000多個品牌）第1章數據挖掘及其算法概覽數據庫知識發現基本概念數據挖掘產生的背景需要一種新的數據集成邏輯組織模型來描述多格式數據共存的數據管理應用環境。針對目前數據管理方法存在的問題，2005年MichaelJ.Franklin和

AlonHalevy提出了數據空間作為一種新的數據管理方法來解決目前數據管理領域面臨的困難。數據空間的目標是為分布異構、多格式的數據源提供一個統一的、便捷的和高效的方法來管理屬于主體的所有數據，而不僅僅是某個片段。數據空間概念提出以來，研究者圍繞數據空間的組織模型、系統原理、存儲索引、搜索查詢進行了理論上、應用上的研究，取得了一定的成果，但由于發展時間較短，數據空間研究和應用仍處于起步階段。多格式第1章數據挖掘及其算法概覽數據庫知識發現基本概念數據挖掘產生的背景第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程數據源數據源。。數據目標數據預處理后的數據信息知識數據準備數據挖掘結果表達及解釋數據集成數據選擇預處理數據挖掘表達及解釋第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程-數據準備數據準備：數據選取、數據預處理和數據轉換。數據選取的目標是確定發現任務的操作對象，即目標數據，它是根據用戶需求從原始數據庫中抽取的一組數據；

數據預處理一般包括消除噪聲、推導計算缺值數據、消除重復記錄、完成數據類型轉換（如將連續值數據轉換為離散值數據）；

數據轉換的主要目標是消減數據維數或降維。即從初始特征中找出真正有用的特征并減少數據挖掘時要考慮的特征或者變量的個數。第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程-數據準備數據選取

數據挖掘通常不需要所有的數據。有些數據對象和數據屬性對建立模型獲得模式是沒有影響的，這些數據的加入會大大影響挖掘效率，甚至可能導致數據挖掘結果的偏差。對數據庫表的選擇，有兩種方式，縱向選擇-列屬性選擇；橫向選擇-元組或記錄選擇。數據選擇是對發現任務和數據本身的內容的理解的基礎上。尋找依賴于發現目標的表達數據的有用特征，以減少數據規模，從而在盡可能保持數據原貌的前提下最大限度地精簡數據量。通過數據選取使數據的規律性和潛在特征更加明顯。數據選取在實際應用中非常重要，但DM領域對其也就并不深入，往往認為數據挖掘時，數據已經準備好了。第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程-數據準備數據預處理

也稱數據清理或者數據清洗。在數據中消除錯誤和不一致，并解決對象識別問題的過程。主要包括空值處理、噪聲數據處理、及不一致數據處理等。也就是說通過數據預處理去除噪聲或無關數據，并處理數據中缺失的數據項或域。例如，關于“高薪”、“低收入”等概念在不同的數據集合中有不同的定義，需要進行統一。需要對數據值進行標準化，例如，人員出身地在不同的集合中表示不同，例如一個集合中為哈市，一個集合中為哈爾濱市。解決異名同義問題，以及同名異義等問題。數據清理是一個困難、繁瑣的問題。DM領域對此研究并不多，在數據集成領域研究比較豐富。第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程-數據準備數據集成

數據挖掘需要對數據進行集成。將多個數據源中的數據合并存放在統一的數據存儲中。數據集成主要涉及三個方面的問題：模式集成：從多個異構的數據庫、文件、遺留系統中提取并集成數據，解決語義二義性，統一不同的數據格式，消除冗余，重復等問題。模式集成涉及實體識別。目前該領域研究比較熱，但問題多難以形成統一的解決方法。目前研究包括元數據、元知識（Metadata,Metaknowledge）及本體（Ontology）等方法。數據值沖突檢測及處理：表示、比例、單位、編碼等不同的解決方法。例如，貨幣單位等冗余：如同一屬性多次出現等(結果綜合，EntityResolution)。在數據倉庫和數據挖掘領域，也許不需要規范化（去規范化）。第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程-數據挖掘數據挖掘：確定目標和任務。如數據總結、分類、聚類、關聯規則發現或者序列模式發現等。確定任務后，考慮采用何種算法。同樣的任務可以采用不同的算法來實現。選擇算法的考慮因素包括：不同的數據有不同的特點，因此需要采用與之相關的算法來處理；用戶或實際運行系統的要求，有的用戶可能希望獲得描述性、易于理解的描述性知識，有的用戶可能希望獲得預測準確度高的預測型知識。數據挖掘僅僅是整個過程的一個部分，數據挖掘質量的好壞有兩個影響因素。采用的數據挖掘技術的有效性；用于挖掘數據的質量和數量。數據挖掘過程是一個非平凡的過程，需要不斷反饋。可視化在數據挖掘中扮演重要的角色。第1章數據挖掘及其算法概覽數據庫知識發現基本概念知識發現的過程-結果表達于解釋結果解釋和評價：數據挖掘階段發現的模式，經過用戶或機器的評價，可能存在冗余或無關的模式，需要將其剔除。模式也可能不滿足用戶的要求，需要重新進行KDD過程。數據庫知識發現基本概念第1章數據挖掘及其算法概覽Web數據挖掘WEB數據挖掘內容挖掘結構挖掘使用挖掘分類聚類檢索隱鏈接分析層次鏈接分析個性化協同過濾從網頁內容中抽取有用的信息和知識從表征WEB結構的超鏈接中尋找有用的知識從記錄每位用戶點擊情況的使用日志中挖掘用戶的訪問模式數據庫知識發現基本概念第1章數據挖掘及其算法概覽Web數據挖掘WEB挖掘過程和數據挖掘過程十分相似，區別通常只是數據收集。在傳統的數據挖掘中，數據經常是收集并存儲在數據倉庫中，對Web挖掘來說，數據收集是一項艱巨的任務。尤其是在進行WEB內容挖掘和結構挖掘方面，需要爬取大量的網頁。第1章數據挖掘及其算法概覽數據挖掘算法概覽

多數情況下，數據挖掘算法可以從五個方面進行考慮。也就是任務、模型、評分函數、搜索方法和數據管理技術。或者稱它們是算法組件。關于算法組件例如關聯規則的典型數據挖掘算法組件：

1任務：描述變量之間的關聯關系；

2結構：用概率表示的“關聯規則”模式；

3評分函數：可信度與支持度的閾值；

4搜索方式：系統搜索，帶剪枝的廣度優先；

5數據管理技術：多重線性掃描。第1章數據挖掘及其算法概覽典型數據挖掘算法數據挖掘領域典型算法*ID3,C4.5（決策樹）*Thek-meansalgorithm（聚類）Supportvectormachines（支持向量機）*TheApriorialgorithm（關聯規則）TheEMalgorithm（迭代優化算法）*PageRank（網頁等級/重要性算法）*AdaBoost（迭代分類算法）*kNN:k-nearestneighborclassification（基于事例的學習）NaiveBayes（貝葉斯學習）CART（增量學習算法）第2章數據倉庫數據倉庫基本概念主要通過以下五點區分開來。

用戶和系統的面向性OLTP是面向顧客的,用于事務和查詢處理;OLAP是面向市場的,用于數據分析

數據內容

OLTP系統管理當前數據;OLAP系統管理大量歷史數據,提供匯總和聚集機制.

數據庫設計

OLTP采用實體-聯系ER模型和面向應用的數據庫設計;

OLAP采用星型或雪花模型和面向主題的數據庫設計.

視圖

OLTP主要關注一個企業或部門內部的當前數據,不涉及歷史數據或不同組織的數據;OLAP則相反.

訪問模式

OLTP系統的訪問主要由短的原子事務組成.這種系統需要并行和恢復機制;

OLAP系統的訪問大部分是只讀操作OLTP（on-linetransactionprocessing）與OLAP（On-LineAnalyticalProcessing）區別第2章數據倉庫數據倉庫基本概念數據倉庫定義及特征

數據倉庫理論的創始人W.H.Inmon在其《BuildingtheDataWarehouse》一書中，給出了數據倉庫的四個基本特征：

面向主題，數據是集成的，數據是不可更新的，數據是隨時間不斷變化。企業級主題區域級原子數據集成倉庫格式直接訪問數據集市格式直接訪問企業信息化工廠√第3范式否物理維度*是維度數據倉庫√維度是*邏輯*維度是獨立型數據集市×N/AN/A物理維度*是數據倉庫體系結構第2章數據倉庫數據倉庫體系結構的爭論三種體系結構的特征比較數據倉庫體系結構第2章數據倉庫數據倉庫體系結構的爭論三種體系結構比較體系結構提倡者其他稱謂描述維度設計的角色企業信息化工廠BillInmon原子數據倉庫企業數據倉庫企業數據倉庫是原子數據的一種集成倉庫不能被直接訪問數據集市為部門使用/分析而重新組織數據維度設計只應用于數據集市維度數據倉庫RalphKimball企業數據倉庫總線體系結構結構化數據集市虛擬數據集市維度數據倉庫是原子數據的一種集成倉庫可以被訪問包含在維度數據倉庫的主題區域，有時稱為數據集市數據集市不要求是獨立的數據庫所有數據按維度組織獨立型數據集市無倡導者但很常見數據集市豎井式煙筒型孤島型主題區域的實現不需要企業環境可以使用維度設計Inmon的企業信息化工廠和Kimball的維度數據倉庫都關注企業級應用。他們的目的是支持跨企業或組織機構的分析型需求。這種方法允許在一個主題區域內處理需求，就像跨主題區域處理問題一樣。關注企業級應用需要采用一種工程化的方法來處理來自不同組織的數據需求。數據倉庫不能僅憑傾聽幾次需求就能設計出來。設計團隊必須研究、分析公共數據元素的不同特征，這些特征由于用戶不同而有所差別。比如，用戶或產品可能在制造、銷售或審計中彼此關聯。對于相同的數據元素，在不同的系統中會采用不同的處理方法，數據倉庫設計必須以一種統一的視圖來適應所有不同的觀點。相比之下，獨立型數據集市在關注企業級應用方面顯示出了不足。其開發只考慮了來自一個小組或部門的需求。由于這種關注的片面性，其開發不會受制于對跨企業公共數據元素的探討；而僅僅關注特定主題區域的特定系統。由于這兩種企業體系結構有相同的范圍，因此產生了一個相同的體系結構特點：它們都有一個獨立的原子數據的集成倉庫。在企業信息化工廠中，這一倉庫被稱為企業數據倉庫。在維度數據倉庫中，該倉庫被稱為維度數據倉庫。這種集中存儲的集成特性與關注企業級應用是一致的。它匯集了公共實體的多種優勢，比如顧客或產品。同樣，關注原子化也滿足了企業目標。無須按照特定分組或主題區域的需求來收集細節數據。取而代之的是，盡可能有效地收集細節數據以滿足所有的分析型需求。數據倉庫體系結構第2章數據倉庫數據倉庫體系結構的爭論三種體系結構比較參考StarSchema完全參考手冊—數據倉庫維度設計權威指南清華大學出版社

對于Inmon體系結構來說，數據集市是為部門使用而建立的一組表格，并且是物理分離的。可以聚集細節數據以適應部門或小組的特殊需要。在這方面，它與獨立型數據集市有一些相似之處；然而，企業信息化工廠中的數據集市在企業倉庫中獲取數據，因此內容與企業信息視圖保持一致。而這是獨立型數據集市無法保證的。對于Kimball體系結構來說，不要求數據集市與物理數據分開存儲。相反，它可以是一種邏輯構件——數據倉庫表的子集。單獨的數據集市報表可以隨時構建。構建完畢后即可從集成倉庫中得到報表。數據集市與企業信息視圖保持一致，要么是由于它們將這種視圖具體化，要么是由于它們從數據集市中獲取數據。

數據倉庫體系結構第2章數據倉庫數據倉庫體系結構的爭論三種體系結構比較第2章數據倉庫數據倉庫體系結構DW中還有一類重要的數據：元數據（metedata）。元數據是“關于數據的數據”（RDBMS中的數據字典就是一種元數據）。數據倉庫中的元數據描述了數據的結構、內容、索引、碼、數據轉換規則、粒度定義等。關于元數據

在數據倉庫系統中，元數據可以幫助數據倉庫管理員和數據倉庫的開發人員非常方便地找到他們所關心的數據。在數據倉庫系統中，元數據機制主要支持以下五類系統治理功能：

1描述哪些數據在數據倉庫中；

2定義要進入數據倉庫中的數據和從數據倉庫中產生的數據；

3記錄根據業務事件發生而隨之進行的數據抽取工作時間安排；

4記錄并檢測系統數據一致性的要求和執行情況；

5衡量數據質量。第2章數據倉庫數據倉庫體系結構元數據作用及功能第2章數據倉庫數據倉庫元數據管理元數據分類技術元數據業務元數據

技術元數據是存儲關于數據倉庫系統技術細節的數據，是用于開發和治理數據倉庫使用的數據。描述和設計如何訪問和處理數據，包括查詢、匯總、遞交等。它主要包括以下信息：

1數據倉庫結構的描述，包括倉庫模式、視圖、維、層次結構和導出數據的定義，以及數據集市的位置和內容；

2業務系統、數據倉庫和數據集市的體系結構和模式；

3匯總用的算法，包括度量和維定義算法，數據粒度、主題領域、聚集、匯總、預定義的查詢與報告；

4由操作環境到數據倉庫環境的映射，包括源數據和它們的內容、數據分割、數據提取、清理、轉換規則和數據刷新規則、安全（用戶授權和存取控制）。第2章數據倉庫技術元數據數據倉庫元數據管理技術元數據示例：用戶報表和查詢訪問模式、頻率和執行時間；審計控制和負載平衡信息；數據的技術結構；提供給DSS的記錄系統；源數據字段標識；從操作型記錄系統到DSS的映射與轉換；編碼/引用表轉換；物理和邏輯數據模型；

DSS表名、鍵和索引；域值；DSS表結構和屬性；數據模型和DSS之間的關系；操作型系統的表結構和屬性；抽取歷史；

DSS表訪問模式；DSS歸檔；工作相關性；程序名和描述；版本維護；安全性；清洗規則等。第2章數據倉庫數據倉庫元數據管理

業務元數據從業務角度描述了數據倉庫中的數據，它提供了介于使用者和實際系統之間的語義層，使得不懂計算機技術的業務人員也能夠“讀懂”數據倉庫中的數據。業務元數據為DSS分析人員提供了訪問DSS底層的數據倉庫和數據集市中信息的線路圖。第2章數據倉庫業務元數據數據倉庫元數據管理

業務元數據主要包括以下信息：使用者的業務術語所表達的數據模型、對象名和屬性名；訪問數據的原則和數據的來源；系統所提供的分析方法以及公式和報表的信息；具體包括以下信息：

1企業概念模型：這是業務元數據所應提供的重要的信息，它表示企業數據模型的高層信息、整個企業的業務概念和相互關系。以這個企業模型為基礎，不懂數據庫技術和SQL語句的業務人員對數據倉庫中的數據也能做到心中有數。

2多維數據模型：這是企業概念模型的重要組成部分，它告訴業務分析人員在數據集市當中有哪些維、維的類別、數據立方體以及數據集市中的聚合規則。這里的數據立方體表示某主題領域業務事實表和維表的多維組織形式。

3業務概念模型和物理數據之間的依靠：以上提到的業務元數據只是表示出了數據的業務視圖，這些業務視圖與實際的數據倉庫或數據庫、多維數據庫中的表、字段、維、層次等之間的對應關系也應該在元數據知識庫中有所體現。第2章數據倉庫業務元數據數據倉庫元數據管理業務數據示例：業務分析員了解的數據結構（與技術用戶比較，產品體系對于業務用戶的意義有所不同）；

DSS中信息的常見訪問例程；主題領域（例如產品、客戶、銷售等）；表名的業務定義；屬性名和業務術語的定義；數據質量的統計信息；

DSS字段映射、轉換和概要；下鉆、上鉆、鉆過和鉆透的規則；域值；數據負責人；數據位置；

DSS刷新日期等。第2章數據倉庫業務元數據數據倉庫元數據管理元數據源元數據存儲元數據用戶ETL工具/處理過程數據建模工具業務人員/文檔生產系統應用數據質量工具其他元數據源報表和OLAP工具版本控制/權限管理數據倉庫元數據技術元數據業務元數據操作元數據業務用戶管理員開發人員第2章數據倉庫關于元數據數據倉庫元數據管理第2章數據倉庫數據倉庫元數據管理元數據主要工具常見的元數據位置元數據類型常見工具ETL數據轉換規則ArdentDatastage程序任務間的相關性SagentSolutionDSS負載平衡統計及加載統計InformaticPowermartSASInstitute數據譜系（DataLineage）數據建模工具邏輯和物理數據模型OracleDesigner2000技術實體和屬性定義PlatnumErwin域值Silverrun報表工具用戶訪問模式Brio報表執行時間CognosBusinessObjects業務實體、屬性、標準定義InformaticAdvantage數據質量工具數據質量統計i.dCentric審核控制TrilliumVality生產商應用程序邏輯和物理數據模型PeopleSoft數據字典SAPSiebolSystems數據倉庫的數據模式第2章數據倉庫星型模式(StarSchema)事實表(facttable)，存放基本數據，相關主題的數據主體（BCNF）維(dimension)，影響、分析主體數據的因素量(measure)，事實表中的數據屬性維表(dimensiontable)，表示維的各種表維是量的取值條件，維用外鍵表示以事實表為中心，加上若干維表，組成星型數據模式例：產品-商店-銷售額CustSalesLocationSalesProdSalesTimeSalesSalestimeid<pk,fk>productid<pk,fk>locationid<pk,fk>customerid<pk,fk>salesrevenueunitssoldProductproductid<pk>makemodelTimetimeid<pk>dateyearquartermonthweekLocationlocationid<pk>regiondistrictstoreCustomercustomerid<pk>categorygroupSalesfactSalesmeasuresTimedimensionAttributesofthe

timedimension數據倉庫的數據模式第2章數據倉庫星型模式

位于星形中心的實體是指標實體，是用戶最關心的基本實體和查詢活動的中心，為數據倉庫的查詢活動提供定量數據。每個指標實體代表一系列相關事實，完成一項指定的功能。位于星形圖星角上的實體是維度實體，其作用是限制用戶的查詢結果，將數據過濾使得從指標實體查詢返回較少的行，從而縮小訪問范圍。每個維表有自己的屬性，維表和事實表通過關鍵字相關聯。星形模式雖然是一個關系模型，但是它不是一個規范化的模型。在星形模式中，維度表被故意地非規范化了，這是星形模式與OLTP系統中的關系模式的基本區別。使用星形模式主要原因:提高查詢的效率。采用星形模式設計的數據倉庫的優點是由于數據的組織已經過預處理，主要數據都在龐大的事實表中,所以只要掃描事實表就可以進行查詢，而不必把多個龐大的表聯接起來，查詢訪問效率較高。同時由于維表一般都很小,甚至可以放在高速緩存中,與事實表作連接時其速度較快;便于用戶理解。對于非計算機專業的用戶而言，星形模式比較直觀，通過分析星形模式，很容易組合出各種查詢。數據倉庫的數據模式第2章數據倉庫星型模式數據倉庫的數據模式第2章數據倉庫雪花模式(SnowflakeSchema)維一般是由若干層次組成把維按其層次結構表示成若干個表規范化、節省存儲空間但需多做連接操作定單號銷售員號客戶號產品號日期標識地區名稱數量總價定單號定貨日期客戶號客戶名稱客戶地址銷售員號姓名城市產品號產品名稱單價日期標識日月年地區名稱省事實表雪花模式產品號公司代碼公司代碼公司名稱地址雪花模式(SnowflakeSchema)數據倉庫的數據模式第2章數據倉庫

雪花模式是對星形模式維表的進一步層次化，將某些維表擴展成事實表，這樣既可以應付不同級別用戶的查詢，又可以將源數據通過層次間的聯系向上綜合，最大限度地減少數據存儲量，因而提高了查詢功能。數據倉庫的數據模式第2章數據倉庫星模式與雪花模式的區別數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表維度提供了環境信息，如果沒有環境信息，報表將顯得毫無意義。成功的維度設計要點在于適當地使用鍵，維度列集合包含豐富的細節信息，摒棄節省存儲空間的主張。

星型模式中，每個維度表都分配有一個代理鍵。這個鍵并不是從操作型系統中獲得的。代理鍵僅僅是為數據倉庫和數據集市創建的。代理鍵通常表現為整數，在星型模式加載時的獲取、轉換、加載(ETL)過程中產生并被管理。鍵值不包含內在的含義，因此對數據倉庫使用者來說并無特殊的意義。維度表的每一行都包含一個唯一的代理鍵與之對應。與代理鍵不同，多數維度表中都包含一個或多個自然鍵。自然鍵通常來源于源系統。它們不能唯一地區分數據倉庫中的行，但能夠區分來自源系統中對應的實體。數據倉庫的數據模式第2章數據倉庫維度表與事實表SurrogateKeyNaturalKeySKU產品統一編號的簡稱，在大型企業中每種產品均對應有唯一的SKU號維度表數據倉庫的數據模式第2章數據倉庫維度表與事實表SurrogateKey的作用

（1）維度表的每一行都包含一個唯一的代理鍵與之對應。起到了類似數據庫表中主鍵的作用。（2）將代理鍵作為唯一標識符的使用方法允許數據倉庫對源系統發生的變化做出響應，這種方式適應了分析型系統的需求。由于維度表不依賴于自然鍵來區分行的唯一性，因此維度表能夠維護歷史信息，即使源系統不能也無所謂。維度表假設訂單輸入系統包含一個customer_id為404777的記錄，該記錄包含客戶的地址信息。在客戶地址發生改變時，由于源系統重寫了客戶地址，因此無法跟蹤地址變遷的歷史信息。如果在維度表中使用同樣的customer_id作為區分行的唯一標識符，那么在維度表中僅能存儲一條customer_id為404777的記錄，因此采用該方式的維度表也不能跟蹤客戶地址變遷的歷史信息。通過使用代理鍵，我們就可以在系統中為customer_id為404777的客戶保存兩條甚至多條記錄，因此可以維護客戶地址變遷的歷史信息。這一歷史信息可能是有用的。數據倉庫的數據模式第2章數據倉庫維度表與事實表SurrogateKey的作用維度表數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表維度為事實提供了環境。沒有環境，事實就無法理解。例如類似“訂單為40000美元”這樣的說明沒有什么意義。它表達的是沒有任何實際意義的事實(訂單總額)。該訂單是有關一個產品還是多個產品的？是一天的訂單情況還是一年的訂單情況？為正確理解“40000美元”的含義，顯然需要更多的信息。“2009年1月有關電子產品的訂單為40000美元”，通過增加維度環境——電子產品類、一個月、某年，使得事實具有實際意義。維度以及維度值在多個方面增強了事實的含義：用于過濾查詢或報表。

用于控制聚集事實的范圍。

用于確定信息的順序或排序。

與事實一起構成提供報表的環境。

用于定義主從結構、分組、分類匯總、匯總等。通過這些應用，維度揭示了事實的價值。在查詢中可以使用維度的不同組合方式回答各種問題。維度涉及的屬性越廣，對事實表開展分析工作的方式就越多。數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表的作用在操作型系統中，經常采用的方法是將數據元素盡可能分解為構成其內容的多個組件。采用這種方法，可以將不同的組件按照需要加以合并。例如，客戶姓名可以分解并以first_name、middle_initial、last_name的方式存儲。在需要時可以將這些屬性加以組合形成全名。

這些組件具備分析的價值，當然應該包含在維度設計中。與操作型模式不同，維度模式還應該包含這些組件的各種組合。例如，如果在報表中存在大量的按照全名或last_middle_first格式分類信息的情況，那么應該將這些組合獨立地以列的方式體現在維度表中。如下圖數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表的應用數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表的應用客戶維度展示了如何將客戶姓名的三個組成部分，例如

JohnP.Smith，構建為客戶維度表中的5個屬性。由于每一個屬性在維度設計時都可以獲取，因此可以很容易地使用它們來組織數據、排序報表、設置數據順序等。另外，由于它們在查詢中是不可計算的，因此對數據庫管理員來說，可以為這些列增加索引以改善查詢性能數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表—緩慢變化維-變化類型1

Type1Change

當一個維度值的源發生變化，并且不需要在星型模式中保留變化歷史時，通常采用類型1來響應變化情況。僅僅使用變化的值重寫維度即可。該技術通常應用于源數據元素是為了更正錯誤而發生更改的情況。通過重寫星型模式中對應的維度值，變化類型1刪除了數據元素的歷史信息。星型模式不會保留該列曾經包含不同值的線索。一般來說，該方法可以達到預期的效果，但也可能會導致混亂。如果存在與變化前關聯的事實，就說明歷史環境發生了改變。數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表—緩慢變化維

Type1Change數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表—緩慢變化維Type2Change多數操作型系統的變化采用變化類型2處理。變化類型2保存了變化的歷史事實。描述變化前的事件的事實與過去的值關聯，描述變化后的事件的事實將與新值關聯。當源系統發生變化時，可以采用的第2種方法是在維度表中插入新的行。先前存在的記錄不會發生任何改變。變化類型2將保存與以往值關聯的事實環境，并允許新的事實與新值關聯。數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表—緩慢變化維Type2Change客戶SueJohnson地址改變的問題提供了應用變化類型2的實例。隨著時間的推移，客戶Sue由先前居住在亞利桑那州，改變為目前居住在加利福尼亞州。她居住在亞利桑那州時提交過一些訂單，居住在加利福尼亞州時提交了另外一些訂單。若采用變化類型1處理客戶Sue地址變化的情況，會產生一些負面效果，即重新聲明了Sue地址變化前提交訂單的環境。這些訂單將與她目前居住的加利福尼亞州關聯，即使這些訂單是Sue在亞利桑那州提交的。數據倉庫的數據模式第2章數據倉庫維度表與事實表維度表—緩慢變化維小結（1）數據倉庫針對數據源發生的變化而進行響應，這樣的過程稱

為緩慢變化維（2）緩慢變化類型1在響應數據源變化時，重寫維度屬性。維度表

不能反映歷史情況。已經存在事實的歷史環境被改變了。（3）數據值發生改變時，緩慢變化類型2創建了一個新版本的維度

行。盡管不能與時間關聯，但維度表維護了版本歷史，歷史

事實的環境得到保存。數據倉庫的數據模式第2章數據倉庫維度表與事實表事實表事實表是度量業務過程的引擎。事實表存儲用來描述過程的詳細度量。事實采用外鍵為每個度量提供維度環境。作為過程度量的核心，事實表應包含與其描述的過程有關的所有事實，當然也包含從其他方面獲得的一些事實。

事實以特定的細節層次存儲，但可以通過上卷產生各種級別的維度。

由于事實具有可加性，因此這樣的聚集是可能的。某些度量不具備可加性，但通常可以分解成具有可加性的組件數據倉庫的數據模式第2章數據倉庫維度表與事實表事實表該星型模式的事實表包含下列事實：quantity_ordered(訂貨數量)

order_dollars(訂單總額)

cost_dollars(開銷總額)

margin_dollars(利潤總額)利潤總額可以通過從訂單總額減去開銷總額獲得當然放不放在事實表中與應用和設計者的風格有關。1.切片和切塊(SliceandDice)在多維數據結構中,按二維進行切片,按三維進行切塊,可得到所需要的數據。如在“城市、產品、時間”三維立方體中進行切塊和切片,可得到各城市、各產品的銷售情況。2.鉆取(Drill)

鉆取包含向下鉆取(Drill-down)和向上鉆取(Drill-up)/上卷(Roll-up)操作，鉆取的深度與維所劃分的層次相對應。

3.旋轉(Rotate)/轉軸(Pivot)通過旋轉可以得到不同視角的數據。第2章數據倉庫多維分析第2章數據倉庫多維分析OLAP的分析方法(一)切片(slicing)、切塊(dicing)按時間維向上鉆取60按時間維向下鉆取OLAP的分析方法(二)鉆取(drill-down)第2章數據倉庫多維分析OLAP的分析方法(三)旋轉第2章數據倉庫多維分析第2章數據倉庫多維分析多維分析方法總結切片是在一部分維上選定值后，關心數據在剩余維上的數據度量。鉆取是改變維的層次，變換分析的粒度；Rollup是在某一維上將低層次的細節數據概括到高層次的匯總數據；Drilldown則相反，它從匯總數據深入到細節數據進行觀察。旋轉式改變維的方向，即在表格中重新安排維的位置（如行列互換）。第2章數據倉庫高性能物理數據倉庫設計非規格化數據非規格化數據倉庫的兩個主要優勢：1能夠提高多個數量級的查詢響應時間；因為大型的，長時間的表格掃描或復雜的連接可以被簡單地查找預先計算出來的結果所取代；2將使系統資源被更加有效地利用；能夠大量減少為獲得某個特定查詢的結果而需要處理的工作量。非規格化數據倉庫一般方法：預聚集、列復制、預連接第2章數據倉庫高性能物理數據倉庫設計非規格化數據非規格化數據的三種技巧1預聚集將一個聚集函數（例如求和求平均）的結果存儲以被后用的方法稱為預聚集；該方法在數據庫中也經常使用，因為這些聚集函數的計算往往需要掃描大量的記錄，將他們計算一次后就存儲在數據庫中以便后續使用是非常實際的方法。例如在稅務系統中經常將每月稅收總計和平均存儲在特定的表中。在數據倉庫中，一般將詳細數據進行匯總。第2章數據倉庫高性能物理數據倉庫設計非規格化數據非規格化數據的三種技巧2列復制當用戶經常進行連接操作時，為了較少連接的代價，將經常連接的兩個或者多個表合并。第2章數據倉庫高性能物理數據倉庫設計非規格化數據非規格化數據的三種技巧3預連接是列復制的極端情況。列復制只是將某個表的一列或者幾列復制到一個表中。預連接時將某個表中的所有列復制到一個表中。就是說用指定的連接鍵來連接兩個（多個）表格，并將連接結果存儲在一個表中。表掃描的代價顯然要比表連接的代價小。第2章數據倉庫高性能物理數據倉庫設計非規格化數據非規格化數據的三種技巧非規格化的代價：增加了磁盤容量；非規格化本身需要大量的計算和合并代價；增加了數據倉庫的刷新代價。對于那些查詢需要非規格化需要在實際應用用加以驗證和改進，也就是說與應用環境有關。第2章數據倉庫高性能物理數據倉庫設計類型劃分無共享型共享內存型共享磁盤型共享內存共享磁盤磁盤磁盤磁盤內存內存內存CPUCPUCPU磁盤磁盤磁盤內存內存內存網絡網絡網絡CPUCPUCPUCPUCPUCPUSN：SharedNothingSM：SharedMemorySD：SharedDiskSM：處理器之間的通信通過共享內存，數據處理算法比較簡單。最大的問題是難以擴展SD：消除了SM的問題，將所有處理器連接到磁盤上，磁盤成為可擴展性的障礙。SN：消除了SM、SD存在的問題，可擴展性最好，網絡成為主要瓶頸。瓶頸SM內存SD磁盤SN網絡類型第2章數據倉庫高性能物理數據倉庫設計并行數據處理第4章關聯規則關聯規則挖掘簡介

關聯規則（AssociationRule）是數據中所蘊含的一類重要規律，對關聯規則進行挖掘是數據挖掘中的一項根本性任務，甚至可以說是數據庫和數據挖掘領域中所發明的并被廣泛研究的最為重要的模型。第4章關聯規則關聯規則挖掘簡介

關聯規則（AssociationRule）反映一個事物與其他事物之間的相互依存性和關聯性。是對一個事物和其它事物的相互依存和關聯關系的描述。若兩個或多個變量的取值存在某種規律，稱為關聯。關聯規則是尋找在同一個事件中出現的不同項的相關性。如果兩個或者多個事物之間存在一定的關聯關系，那么，其中一個事物就能夠通過其他事物預測到。

關聯規則是數據挖掘中用于表示局部模式的最流行方法之一。關聯分析的目的是挖掘隱藏在數據間的相互關系，自動探測以前未發現的蘊藏著的模式模式是一種局部概念，它反映的是數據某一方面的信息。而模型則是對數據的全面描述。第4章關聯規則關聯規則挖掘簡介

典型的關聯規則發現問題是對超市中的貨籃數據（MarketBasket）進行分析。通過發現顧客放入貨籃中的不同商品之間的關系來分析顧客的購買習慣。（關聯規則應用最適合的應用案例）貨籃數據的特點：數據量巨大，數據稀疏。(行為百萬級，列至少是千級別的，行表示一次購買事件，列表示商店的商品)

對一個描述超市的數據集合來說，模式可能是“十分之一”的顧客購買了酒和牛奶。第4章關聯規則關聯規則挖掘簡介Basket-idA1A2A3A4A5….….T110000T211110T310101T400100T501110T611100T710110T801101T910010T1001101…….

購物籃數據中，行表示顧客購買行為，列表示商店的商品。若顧客購買了某種商品，則表中表示為1，反之為0第4章關聯規則關聯規則挖掘簡介關聯規則

關聯規則是對數據庫中某些特定事件一起發生的概率的簡單陳述；首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD會議上提出；在事務、關系數據庫中的項集和對象中發現頻繁模式、關聯規則、相關性或者因果結構。頻繁模式是指數據庫中頻繁出現的項集。SIGMOD：SpecialInterestGrouponManagementofData第4章關聯規則關聯規則挖掘簡介研究關聯規則的目標：發現數據中的規律超市中的什么產品經常會被一起購買；-啤酒與尿布在購買了PC機后，顧客下一步一般購買什么產品；如何自動對WEB文檔分類；用戶上了CCTV網站后，一般將會去那些其他網站；用戶購買了“XXX”書后，一般還會購買什么書;某一類納稅人在當月未納稅，則其下個月也不納稅的可能性第4章關聯規則關聯規則挖掘簡介關聯規則特別適用于稀疏的數據集合。如購物籃等。為簡單起見，設所有變量都是二值的，則關聯規則具有以下的形式：如果A=1，且B=1,則C=1的概率為p。其中，A、B、C是二值變量。且

p=p(C=1|A=1,B=1)，

即給定A=1，B=1時C=1的條件概率。P有時被稱為規則的精度或可信度。p(C=1，A=1，B=1)稱為支持度。尋找規則結構的典型目標就是尋找滿足以下約束的所有規則：可信度p大于某個閾值pa，支持度大于某個閾值ps。例如尋找支持度大于0.05,可信度大于0.8的所有規則。第4章關聯規則關聯規則挖掘簡介關于規則(Rule)表示

規則是人工智能領域研究的知識表示方法中最古老，最經典的一種表示方法。應用非常廣泛。具有易于解釋的優點。規則是由左側的命題（前提或者條件）和右側的結論組成。規則的含義是如果左側為真，則右側也為真。規則的左側一般可以是合取式（conjunction）。規則具有固有的離散性，也就是說，規則左右側均為布爾陳述。因此規則特別適合于離散型和范疇型變量建模。概率（Probabilistic）規則將此定義修改為：如果左側為真，則右側為真的概率是p。概率p實際上就是給定左側后，右側為真的條件概率。第4章關聯規則關聯規則挖掘簡介如何從數據中發現模式？

若給定了表示模式的某種方式及這種表示方式下的所有可能模式。最原始的方法就是依次試驗每種模式，并觀察它是否在數據中發生。若模式的數量較小，此方法是可以接受的。但一般都不行，例如前述超市的例子。假定有5000種商品（以0,1表示是否購買）則可能的模式個數是25000個。（實際上是25000-1）若各個模式之間毫無關系。只好采用原始的方式。實際上，模式都存在大量的結構，可以使用這些模式結構引導搜索。通常各個模式之間都存在泛化關系。第4章關聯規則關聯規則挖掘簡介關于泛化如果只要模式α出現在數據中，模式β也一定出現在數據中，則稱模式β就是模式α的泛化。例如模式“至少有10%的顧客購買了香煙”是模式“至少有10%的顧客購買了香煙和啤酒”的泛化。使用模式中的泛化關系可以得到一種簡單的算法來尋找出現在數據中的所有特定類型的模式。第4章關聯規則關聯規則挖掘簡介關于頻繁項集對于從變量A1,….,Ap觀察到的0,1集合關聯規則的形式如下：

((Ai1=1)∧(Ai2=1)∧…..∧(Aik=1))=〉Aik+1=1

可以簡化為

(Ai1

∧Ai2

∧…..∧Aik=1)

像(Ai1=1)∧(Ai2=1)∧…..∧(Aik=1)這樣的模式被稱為項集（itemset）第4章關聯規則關聯規則挖掘簡介關于屬性值-屬性值離散化若數據集的屬性都是布爾值，則此數據集中挖掘的關聯規則都是布爾關聯規則。其它屬性可以進行轉換。可以將非布爾值數據轉換為布爾數據值。TIDAgeSalary1353200243460035637004242100………第4章關聯規則關聯規則挖掘簡介關于屬性值-屬性值離散化

上圖中，挖掘某一個具體的年齡和一個具體的收入間的關聯關系，由于屬性取值的多樣性，通常很難滿足最小支持度和最小可信度閾值指標。并且一般來說，發現類似Age(41)=>Salary(4320)之類的表達顯然沒有多大意義。更多的情況是希望發現年齡段與收入范圍間的關系。因此，可以將數量屬性值劃分為若干區間，按照區間的劃分將一個數量屬性分解為若干個布爾屬性。例如將年齡按照[20，30），[30，40），…

收入按區間[2000，3000），[3000，4000），…..進行劃分。第4章關聯規則IBM公司Almaden研究中心的R.Agrawal首先提出關聯規則模型，并給出求解算法AIS。隨后又出現了SETM和Apriori等算法。其中，Apriori是關聯規則模型中的經典算法。

給定一組事務；產生所有的關聯規則；滿足最小支持度和最小可信度。關聯規則的基本模型及算法

設I={i1,i2,…,im}為所有項目的集合，D為事務數據庫，事務T是一個項目子集（TI）。每一個事務具有唯一的事務標識TID。設A是一個由項目構成的集合，稱為項集。事務T包含項集A，當且僅當AT。如果項集A中包含k個項目，則稱其為k項集。項集A在事務數據庫D中出現的次數占D中總事務的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。第4章關聯規則關聯規則的基本模型及算法第4章關聯規則關聯規則的基本模型及算法

關聯規則是形如XY的邏輯蘊含式，其中XI，YI，且XY=。如果事務數據庫D中有s%的事務包含XY，則稱關聯規則XY的支持度為s%，實際上，支持度是一個概率值。若項集X的支持度記為support(X)，規則的信任度為

support(XY)／support(X)。這是一個條件概率P(Y|X)。也就是：support(XY)=P(XY)confidence(XY)=P(Y|X)第4章關聯規則關聯規則的基本模型及算法關聯規則的挖掘一般分為兩個步驟。（1）找出所有支持度大于等于最小支持度閾值的頻繁項集。（2）由頻繁項集生成滿足可信度閾值的關聯規則。第一步工作相當費時，第二步相對容易得多。所以關聯規則算法的性能主要由第一步決定。第4章關聯規則關聯規則的基本模型及算法Basket-idA1A2A3A4A5….….T110000T211110T310101T400100T501110T611100T710110T801101T910010T1001101…….第4章關聯規則關聯規則的基本模型及算法關聯規則的典型數據挖掘算法組件：

1任務：描述變量之間的關聯關系；

2結構：用概率表示的“關聯規則”模式；

3評分函數：可信度與支持度的閾值；

4搜索方式：系統搜索，帶剪枝的廣度優先；

5數據管理技術：多重線性掃描。第4章關聯規則關聯規則的基本模型及算法關于評分函數關聯規則的評分函數是簡單的二擇一函數。有兩個閾值：可信度Pa，支持度Ps。

Ps是規則支持度的下限。當我們想要至少覆蓋10%時，Ps=.1Pa是規則可信度的下限。當我們想要精度不低于90%，Pa=.9

若一個模式滿足上述兩個條件，則得分為1，否則為0。因此，算法的目標就是尋找得分為1的規則。

所有關聯規則的數量非常巨大，前面提到5000種商品共有25000種模式。但可用評分函數的優勢，可以將平均運行時間將到一個可以接受的范圍。第4章關聯規則關聯規則的基本模型及算法關于評分函數注意若P(A=1)≤Ps，且P(B=1)≤Ps中任何一個成立。則

P(A=1,B=1)≤Ps。

因此，可以首先找概率大于Ps的所有單個事件（線性掃描一次）。若事件（或一組事件）大于Ps，則稱其為頻繁項集（頻繁1項集）。然后，對這些頻繁事件所有可能對作為容量為2的候選頻繁集合。

第4章關聯規則關聯規則的基本模型及算法關于評分函數：更一般的情況下。當從容量為K-1的頻繁項集生成容量為K的頻繁項集時，可以剪除任何容量為K的集合。只要它包含的K-1項的子集，且該子集在K-1級是不頻繁的。例如，若有容量為2的頻繁項集（A=1，B=1）及（B=1,C=1）。將其組合為容量為3的頻繁項集（A=1，B=1，C=1）若存在（A=1，B=1）是不頻繁的，則（A=1，B=1，C=1）是不頻繁的，因此可以將其剪除。第4章關聯規則關聯規則的基本模型及算法關于評分函數注意這種剪除可在不直接搜索數據的情況下進行，因此提高了計算速度。確定了修剪后的容量為K的頻繁項集后，對數據庫再執行一次線性掃描以確定那些集合是頻繁的。然后將確定后的容量為K的頻繁項集進行組合，以生成所有可能的含有K+1個事件的頻繁集合，然后再修剪，再掃描一次數據，直到無法產生新的頻繁集。第4章關聯規則關聯規則的基本模型及算法頻繁項集的挖掘問題可以用圖形形式表示。所有項集能構成的組合用圖所示的集合枚舉樹（Set-enumerationTree）表示。集合枚舉樹是一顆排序樹。樹中每個節點表示一種項集組合。樹根是空集。以下依次為1項集，2項集，3項集，….頻繁項集的數據挖掘問題實際上是從集合枚舉樹中找一條分割線使分割線上的項集是頻繁的，分割線下的項集是非頻繁的。為找出此分割線，需要以一定的策略遍歷該樹。第4章關聯規則關聯規則的基本模型及算法{}abcdeabacadaebcbdbecdcedeabcabdabeacdaceadebcdbcebdecdeabcdabceabdeacdebcdeabcde第4章關聯規則關聯規則的基本模型及算法支持度和可信度

查找所有的規則X&YZ具有最小支持度和可信度支持度,

s,一次交易中包含{X、Y、Z}的可能性可信度,

c,

包含{X、Y}的交易中也包含Z的條件概率設最小支持度為50%,最小可信度為50%,則可得到AC(50%,66.6%)CA(50%,100%)買尿布的客戶二者都買的客戶買啤酒的客戶第4章關聯規則關聯規則的基本模型及算法Letmin_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,F第4章關聯規則關聯規則的基本模型及算法ForruleA

C:support=support({A}{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%第4章關聯規則關聯規則的基本模型及算法Apriori算法Apriori算法是一種經典的生成布爾型關聯規則的頻繁項集挖掘算法.算法名字是緣于算法使用了頻繁項集的性質這一先驗知識.思想:Apriori使用了一種稱作level-wise搜索的迭代方法,其中k-項集被用作尋找(k+1)-項集. 首先,找出頻繁1-項集,以L1表示.L1用來尋找L2,即頻繁2-項集的集合.L2用來尋找L3,以此類推,直至沒有新的頻繁k-項集被發現.每個Lk都要求對數據庫作一次完全掃描..第4章關聯規則關聯規則的基本模型及算法Apriori算法頻繁項集

為了避免計算所有項集的支持度（實際上頻繁項集只占很少一部分），Apriori算法引入潛在頻繁項集的概念。若潛在頻繁k項集的集合記為Ck，頻繁k項集的集合記為Lk，m個項目構成的k項集的集合為，則三者之間滿足關系LkCk

。構成潛在頻繁項集所遵循的原則是“頻繁項集的子集必為頻繁項集”。第4章關聯規則關聯規則的基本模型及算法Apriori算法關聯規則的性質性質1：頻繁項集的子集必為頻繁項集。

性質2：非頻繁項集的超集一定是非頻繁的。

Apriori算法運用性質1，通過已知的頻繁項集構成長度更大的項集，并將其稱為潛在頻繁項集。潛在頻繁k項集的集合Ck是指由有可能成為頻繁k項集的項集組成的集合。以后只需計算潛在頻繁項集的支持度，而不必計算所有不同項集的支持度，因此在一定程度上減少了計算量。

第4章關聯規則關聯規則的基本模型及算法Apriori算法關聯規則的性質Apriori算法是反單調的即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。第4章關聯規則關聯規則的基本模型及算法{}abcdeabacadaebcbdbecdcedeabcabdabeacdaceadebcdbcebdecdeabcdabceabdeacdebcdeabcde若{c,d,e}是頻繁的，則其子集{c,d}、{c,e}、{d,e}{c}、t9sydie、{e}一定是頻繁的反之，如果一個集合是非頻繁的，則其超集必然也是非頻繁的第4章關聯規則關聯規則的基本模型及算法為什么需要支持度和可信度？支持度是一種重要的度量，因為支持度低的規則可能只是偶然出現。從商務角度看，低支持度的規則多半也是不令人感興趣的，因為對顧客很少同時購買的商品進行促銷沒有意義。另一方面，可信度度量通過規則進行推理的可靠性。對于給定的規則X-〉Y，可信度越高，Y在包含X的事務中出現的可能性就越大。可信度也提供了Y在給定X下的條件概率的估計回顧Apriori算法L1C2L2C3L3候選鍵產生1、連接步2、剪枝步2項集建立3項集建立頻繁項集產生計算步驟問題：處理龐大的候選集合問題：重復掃描數據表檢查候選模式第4章關聯規則關聯規則的基本模型及算法第4章關聯規則關聯規則的基本模型及算法Apriori算法的核心:用頻繁的(k–1)-項集生成候選的頻繁k-項集用數據庫掃描和模式匹配計算候選集的支持度Apriori的瓶頸:候選集生成巨大的候選集:掃描數據庫次數：如果最長的模式是n的話，則需要n

次數據庫掃描Apriori算法的瓶頸Apriore算法小結，兩個問題：

1、復雜的候選建立過程消耗了大量的時間、空間和內容；

2、對數據庫的多遍掃描；第4章關聯規則關聯規則研究趨勢Apriori算法的幾個注意點：Apriori算法理論上是指數級別的算法。設I中項目的數目為m，則整個

項集集合空間的規模將達到O（2m）。然而，該算法充分利用了數據的

稀疏性和較高的最小支持度值來保證算法的可行性和高效性。在購物

籃數據分析中，數據的稀疏性（Sparseness）表現在“盡管商場會出售

數量巨大的各種商品，但每位顧客一次僅會購買很少的一部分。”由于該算法不需要將數據集一次性裝入內存中，所以它可以應用于規模

巨大的數據集合上。算法僅需要對數據集合掃描K次，其中K是最大項

集的大小。在實際應用中，K往往很小。一旦給定了一個事務集T，一個最小支持度值和一個最小置信度值，則T

中頻繁項目集集合就被唯一確定了。任何算法都應該找出同一個頻繁項

目集，這一特性在其他很多算法中都不成立。比如分類和聚類。第4章關聯規則關聯規則研究趨勢目前主要的研究集中在改進關聯規則算法的效率：1）減少對數據庫掃描的遍數；2）抽樣指導方法；3）并行化4）對結構模型增加額外的約束第4章關聯規則關聯規則研究趨勢減少對數據庫掃描的遍數FP樹是繼Apriori之后關聯規則挖掘的一個里程碑。頻繁項集的建立僅經過兩遍數據庫掃描，并且不產生候選建立過程。FP樹是一種擴展的前綴樹結構，存儲關鍵的和頻繁模式的數量。節點中的樹僅僅包含頻繁1項集。FP樹的優點表現在三個方面：

FP樹是一種對原始數據庫數據的壓縮表達，僅有頻繁項可以加入到樹中；其他不相關的數據被剪枝；該算法僅僅掃描數據庫兩遍。

FP樹采用分治方法減少了后續的條件FP樹的數量。第4章關聯規則關聯規則研究趨勢抽樣指導方法抽樣方法一般包括兩個步驟：1、獲取數據庫的抽樣并獲得抽樣的關聯規則；2、將上述結果在數據庫中驗證。Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FTransaction-idItemsbought10A,B,C11C,E,G……20A,C30A,D40B,E,F…..….規則集Validation第4章關聯規則關聯規則研究趨勢并行化

利用并行系統可以利用其高速和高存儲特點。FDM算法是Apriori算法的并行化實現（采用SN結構）。從研究上看，在此方面可以有所作為。第4章關聯規則關聯規則研究趨勢關聯規則挖掘的約束

多數發現頻繁模式的數據挖掘技術針對數據集合。一般，其目標是發現頻繁出現在數據集中（超過用戶定義的域值）的所有模式。但用戶往往想要通過增加額外的約束限制被發現的模式，例如對模式結構的約束。數據挖掘系統應該運用這些約束加速數據挖掘的過程。應用到約束驅動的模式發現主要分以下幾類：

1、后處理技術。在挖掘過程完成后，將不滿足用戶約束要求的模式過濾掉；

2、模式過濾技術。將約束集成到數據挖掘過程中，只建立滿足用戶約束的模式；

3、數據集合過濾。將不滿足用戶約束的數據集合過濾掉。

第4章關聯規則FP-TREE用Frequent-Patterntree(FP-tree)結構壓縮數據庫,-高度濃縮，同時對頻繁集的挖掘又完備的-避免代價較高的數據庫掃描開發一種高效的基于FP-tree的頻繁集挖掘算法-采用分而治之的方法學：分解數據挖掘任務為小任務-避免生成關聯規則:只使用部分數據庫!關聯規則研究趨勢第4章關聯規則FP-TREEFP樹是一種輸入數據的壓縮表示，它通過逐個讀入事務，并把每個事務映射到FP樹種的一條路徑來構造。由于不同的事務可能有若干個相同的項，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用FP樹結構獲得的壓縮效果越好。關聯規則研究趨勢第4章關聯規則關聯規則研究趨勢利用FP-TREE方法實現頻繁項集挖掘（示例）TIDITEMSBought100a,b,c,d,e,f,g,h200