第九章知識發現和數據挖掘數據庫中知識發現

史忠植中科院計算所2025/6/31高級人工智能史忠植知識發現關聯規則數據倉庫知識發現工具2025/6/32高級人工智能史忠植知識發現知識發現是指從數據集中抽取和精煉新的模式。范圍非常廣泛：經濟、工業、農業、軍事、社會數據的形態多樣化：數字、符號、圖形、圖像、聲音數據組織各不相同：結構化、半結構化和非結構發現的知識可以表示成各種形式 規則、科學規律、方程或概念網。2025/6/33高級人工智能史忠植數據庫知識發現

目前,關系型數據庫技術成熟、應用廣泛。因此,數據庫知識發現(KnowledgeDiscoveryinDatabasesKDD)的研究非?；钴S。

該術語于1989年出現，Fayyad定義為“KDD是從數據集中識別出有效的、新穎的、潛在有用的，以及最終可理解的模式的非平凡過程”

2025/6/34高級人工智能史忠植不同的術語名稱

知識發現是一門來自不同領域的研究者關注的交叉性學科，因此導致了很多不同的術語名稱。

知識發現:人工智能和機器學習界。數據挖掘(datamining): 統計界、數據分析、數據庫和管理信息系統界知識抽取(informationextraction)、信息發現(informationdiscovery)、智能數據分析(intelligentdataanalysis)、探索式數據分析(exploratorydataanalysis)信息收獲(informationharvesting)

數據考古(dataarcheology)2025/6/35高級人工智能史忠植2025/6/36高級人工智能史忠植知識發現的任務(1)數據總結：對數據進行總結與概括。傳統的最簡單的數據總結方法是計算出數據庫的各個字段上的求和值、平均值、方差值等統計值,或者用直方圖、餅狀圖等圖形方式表示。分類： 根據分類模型對數據集合分類。分類屬于有導師學習，一般需要有一個訓練樣本數據集作為輸入。聚類：

根據數據的不同特征，將其劃分為不同的類。無導師學習2025/6/37高級人工智能史忠植知識發現的任務(2)相關性分析：發現特征之間或數據之間的相互依賴關系 關聯規則偏差分析：

基本思想是尋找觀察結果與參照量之間的有意義的差別。通過發現異常,可以引起人們對特殊情況的加倍注意。建模： 構造描述一種活動或狀態的數學模型2025/6/38高級人工智能史忠植知識發現的方法(1)統計方法：

傳統方法： 回歸分析、判別分析、聚類分析、探索性分析模糊集(fuzzyset)Zadeh1965支持向量機(SupportVectorMachine)Vapnik90年代初粗糙集(RoughSet)Pawlak80年代初2025/6/39高級人工智能史忠植知識發現的方法(2)機器學習：

規則歸納：AQ算法決策樹：ID3、C4.5范例推理:CBR遺傳算法:GA貝葉斯信念網絡2025/6/310高級人工智能史忠植知識發現的方法(3)神經計算：

神經網絡是指一類新的計算模型，它是模仿人腦神經網絡的結構和某些工作機制而建立的一種計算模型。常用的模型：Hopfield網多層感知機自組織特征映射反傳網絡可視化： 2025/6/311高級人工智能史忠植KDD的技術難點動態變化的數據噪聲數據不完整冗余信息數據稀疏超大數據量2025/6/312高級人工智能史忠植關聯規則屬于知識發現任務中的相關性分析由于條形碼技術的發展,零售部門可以利用前端收款機收集存儲大量的售貨數據。因此,如果對這些歷史事務數據進行分析,則可對顧客的購買行為提供極有價值的信息。例如,可以幫助如何擺放貨架上的商品(如把顧客經常同時買的商品放在一起),幫助如何規劃市場(怎樣相互搭配進貨)。2025/6/313高級人工智能史忠植關聯規則的表示關聯規則的形式如“在購買面包顧客中,有70%的人同時也買了黃油”,可以表示成：面包→黃油。用于關聯規則發現的主要對象是事務型數據庫,其中針對的應用則是售貨數據,也稱貨籃數據。一個事務一般由如下幾個部分組成:事務處理時間,一組顧客購買的物品,有時也有顧客標識號(如信用卡號)。2025/6/314高級人工智能史忠植關聯規則的相關概念(1)設R={I1,I2……Im}是一組物品集，W是一組事務集。W中的每個事務T是一組物品，T

R。假設有一個物品集A，一個事務T，如果A

T，則稱事務T支持物品集A。關聯規則是如下形式的一種蘊含：A→B，其中A、B是兩組物品，A

I，B

I，且A∩B=

。2025/6/315高級人工智能史忠植關聯規則的相關概念(2)支持度物品集A的支持度：稱物品集A具有大小為s的支持度,如果D中有s%的事務支持物品集XP(A)1000個顧客購物，其中200個顧客購買了面包，支持度就是20％（200/1000）。

關聯規則A→B的支持度：關聯規則A→B在事務數據庫W中具有大小為s的支持度,如果物品集A∪B的支持度為s100個顧客購買了面包和黃油，則面包→黃油10％2025/6/316高級人工智能史忠植關聯規則的相關概念(3)可信度設W中支持物品集A的事務中，有c％的事務同時也支持物品集B，c％稱為關聯規則A→B的可信度。

P(B|A)1000個顧客購物，200個顧客購買了面包，其中140個買了黃油，則可信度是70％（140/200）。2025/6/317高級人工智能史忠植關聯規則的相關概念(4)最小支持度minsup用戶規定的關聯規則必須滿足的最小支持度。最小可信度minconf用戶規定的關聯規則必須滿足的最小可信度。大項集(大項集、大物品集largeitemset)支持度不小于最小支持度minsup的物品集2025/6/318高級人工智能史忠植關聯規則發現任務給定一個事務數據庫D，求出所有滿足最小支持度和最小可信度的關聯規則。該問題可以分解為兩個子問題：求出D中滿足最小支持度的所有大項集；利用大項集生成滿足最小可信度的所有關聯規則。對于每個大項集A，若B

A，B≠φ，且Confidence（B

(A

B)）

minconf，則構成關聯規則B

(A

B)2025/6/319高級人工智能史忠植關聯規則發現的基本思路

第2個子問題比較容易。目前大多數研究集中在第一個子問題上，即如何高效地求出大項集。

首先生成長度為1的大項集（即單個物品），記為L[1]；在L[k]的基礎上生成候選物品集C[k+1]，候選物品集必須保證包括所有的大項集。用事務數據庫D中的事務對C[k+1]進行支持度測試以生成長度為k+1的大項集L[k+1]，計算每個候選物品集的支持度，如果大于minsup，則加入到L[k+1]中。如果L[k+1]為空集，則結束，L[1]∪L[2]∪…即為結果；否則轉(2)，繼續。2025/6/320高級人工智能史忠植思路的正確性利用了大物品集向下封閉性，即大物品集X的任意子集一定是大物品集，反過來說，如果X有一子集不是大項集，則X肯定不是。是寬度優先算法2025/6/321高級人工智能史忠植經典的Apriori算法(1)L[1]={large1-itemsets};(2)for(k=2;L[k-1]不為空;k++)dobegin(3)C[k]=apriori-gen(L[k-1]);//新候選物品集(4)Foralltransactionst∈Ddobegin(5)C=subset(C[k],t);//t中的候選物品集(6)Forallcandidatesc∈Cdo(7)c.count++;(8)end;(9)L[k]={c∈C[k]|c.count>=minsup};(10)end;(11)Answer=L[1]∪L[2]∪…2025/6/322高級人工智能史忠植apriori-gen(L[k-1])分成兩步：join算法：從兩個L[k-1]物品集生成候選物品集C[k]insertintoC[k]selectp.item1,p.item2,...,p.item(k-1),q.item(k-1)fromL[k-1]p,L[k-1]qwherep.item1=q.item1,...,p.item(k-2)=q.item(k-2),p.item(k-1)<q.item(k-1)2025/6/323高級人工智能史忠植Prune算法：從C[k]中除去大小為k-1且不在L[k-1]中的子集(1)Forallitemsetsc∈C[k]do(2)Forall(k-1)-subsetssofcdo(3)if(s

L[k-1])(4)thendeletecfromC[k]2025/6/324高級人工智能史忠植舉例：L[3]為{{1,2,3},{1,2,4},{1,3,4},{1,3,5},{2,3,4}}經過join后，C[4]={{1,2,3,4},{1,3,4,5}}由于{1,3,4,5}有子集{1,4,5}不在L[3]中，所以經過prune后，得到L[4]={{1,2,3,4}}2025/6/325高級人工智能史忠植2025/6/326高級人工智能史忠植2025/6/327高級人工智能史忠植2025/6/328高級人工智能史忠植2025/6/329高級人工智能史忠植關聯規則發現注意的問題充分理解數據目標明確數據準備工作要做好選取適當的最小的支持度和可信度很好地理解關聯規則2025/6/330高級人工智能史忠植關聯規則發現使用步驟連接數據，做數據準備給定最小支持度和最小可信度，利用知識發現工具提供的算法發現關聯規則可視化顯示、理解、評估關聯規則2025/6/331高級人工智能史忠植關聯規則在保險業務中的應用最小支持度1%，最小可信度為50%2025/6/332高級人工智能史忠植2025/6/333高級人工智能史忠植2025/6/334高級人工智能史忠植2025/6/335高級人工智能史忠植數據倉庫在過去幾十年，數據庫技術，特別是OLTP（聯機事務處理），主要是為自動化生產、精簡工作任務和高速采集數據服務。它是事務驅動的、面向應用的。20世紀80年代，人們要利用現有的數據，進行分析和推理，從而為決策提供依據。這種需求既要求聯機服務，又涉及大量用于決策的數據。而傳統的數據庫系統已無法滿足這種需求：所需歷史數據量很大，而傳統數據庫一般只存儲短期數據。涉及許多部門的數據，而不同系統的數據難以集成。對大量數據的訪問性能明顯下降

2025/6/336高級人工智能史忠植數據倉庫的定義信息處理技術的發展趨勢是：從大量的事務型數據庫中抽取數據，并將其清理、轉換為新的存儲格。隨著此過程的發展和完善，這種九十年代初出現的支持決策的、特殊的數據存儲即被稱為數據倉庫（DataWarehouse）。Inmon將數據倉庫明確定義為：數據倉庫（DataWarehouse）是面向主題的，集成的，內容相對穩定的、不同時間的數據集合，用以支持經營管理中的決策制定過程。

2025/6/337高級人工智能史忠植數據倉庫的特征(1)

數據倉庫中的數據是面向主題的

與傳統數據庫面向應用相對應的。主題是一個在較高層次將數據歸類的標準，每一個主題基本對應一個宏觀的分析領域

數據倉庫中的數據是集成的

在數據進入數據倉庫之前，必然要經過加工與集成。要統一原始數據中的所有矛盾之處，還要進行數據綜合和計算2025/6/338高級人工智能史忠植數據倉庫的特征(2)

數據倉庫中的數據是穩定的數據倉庫的數據主要供決策分析之用，所涉及的操作主要是數據查詢，一般不進行修改操作

數據倉庫中的數據又是隨時間不斷變化的數據倉庫的數據不是實時更新的，但并不是永遠不變的，也要隨著時間的變化不斷地更新、增刪和重新綜合。更新周期 2025/6/339高級人工智能史忠植元數據元數據（Metadata）是關于數據的數據，它描述了數據的結構、內容、編碼、索引等內容。傳統數據庫中的數據字典是一種元數據，但在數據倉庫中，元數據的內容比數據庫中的數據字典更加豐富和復雜。設計一個描述能力強、內容完善的元數據，是有效管理數據倉庫的具有決定意義的重要前提2025/6/340高級人工智能史忠植元數據的重要性數據倉庫使用者往往將使用元數據作為分析的第一步。元數據如同數據指示圖，指出了數據倉庫內各種信息的位置和含義從操作型數據環境到數據倉庫的數據轉換是復雜的、多方面的，是數據倉庫建設的關鍵性步驟，元數據要包含對這種轉換的清晰描述，保證這種轉換是正確、適當和合理的，并且是靈活可變的元數據還管理粒度的劃分、索引的建立以及抽取更新的周期等，以便管理好數據倉庫中的大規模數據2025/6/341高級人工智能史忠植數據倉庫的相關概念事實表（Fact）：存儲用戶需要查詢分析的數據，事實表中一般包含多個維（Dimension）和度量（Measurement）。維：代表了用戶觀察數據的特定視角，如：時間維、地區維、產品維等。每一個維可劃分為不同的層次來取值，如時間維的值可按年份、季度、月份來劃分，描述了不同的查詢層次。度量：是數據的實際意義，描述數據“是什么”，即一個數值的測量指標，如：人數、單價、銷售量等。

2025/6/342高級人工智能史忠植數據倉庫的建模模型度量的實際數據存放在事實表中。維的詳細信息，如不同的層次劃分和相應數據等在維表中存儲，事實表中存放各個維的標識碼鍵。事實表和維表將通過這些鍵關聯起來，構成一種星型模型對于層次復雜的維,為避免冗余數據占用過大的存儲空間,可以使用多個表來描述,這種星型模式的擴展稱為雪花模型2025/6/343高級人工智能史忠植OLAP數據倉庫技術中，多維數據分析（MultidimensionalDataAnalysis）方法是一種重要的技術，也稱作聯機分析處理（On-LineAnalyticalProcessing，簡稱OLAP）或數據立方體（DataCube）方法，主要是指通過各種即席復雜查詢，對數據倉庫中存儲的數據進行各種統計分析的應用

數據倉庫是面向決策支持的，決策的前提是數據分析。在數據分析中經常要用到諸如求和、總計、平均、最大、最小等匯集操作，這類操作的計算量特別大。2025/6/344高級人工智能史忠植OLAP的類型ROLAP：數據保留在原有的關系型結構中，并且將聚合表也存儲在關系數據庫,在技術成熟及各方面的適應性上較之MOLAP占有一定的優勢，性能較差MOLAP:數據和聚合都存儲在多維結構中，效率較高，便于進行優化操作。維數多數據量大時，存儲是難點。HOALP:數據保留在原有的關系型結構中，聚合存儲在多維結構。結合ROLAP和MOLAP兩者的優點2025/6/345高級人工智能史忠植OLAP的分析操作OLAP的基本多維分析操作有鉆?。╮ollup和drilldown）、切片（slice）和切塊（dice）、以及旋轉（pivot)等。鉆取是改變維的層次，變換分析的粒度。它包括向上鉆取和向下鉆取。rollup是在某一維上將低層次的細節數據概括到高層次的匯總數據；而drilldown則相反，它從匯總數據深入到細節數據進行觀察切片和切塊是在一部分維上選定值后，關心度量數據在剩余維上的分布。如果剩余的維只有兩個，則是切片，否則是切塊旋轉是變換維的方向，即在表格中重新安排維的放置（例如行列互換2025/6/346高級人工智能史忠植數據倉庫和知識發現技術的結合(1)

知識發現成為數據倉庫中進行數據深層分析的一種必不可少的手段數據倉庫是面向決策分析的，數據倉庫從事務型數據抽取并集成得到的分析型數據后，需要各種決策分析工具對這些數據進行分析和挖掘，得到有用的決策信息。而知識發現技術具備從大量數據中發現有用信息的能力。2025/6/347高級人工智能史忠植數據倉庫和知識發現技術的結合(2)

數據倉庫為知識發現提供經過良好預處理的數據源

知識發現往往依賴于經過良好組織和預處理的數據源，數據的好壞直接影響知識發現的效果。數據倉庫具有從各種數據源中抽取數據，并對數據進行清洗、聚集和轉換等各種處理的能力2025/6/348高級人工智能史忠植一、數據挖掘概念----發展1989IJCAI會議：數據庫中的知識發現討論專題KnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,1991)1991-1994KDD討論專題AdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,1996)1995-1998KDD國際會議(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD,SIGKDD’1999-2002會議,以及SIGKDDExplorations數據挖掘方面更多的國際會議PAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.2025/6/349高級人工智能史忠植二、數據挖掘軟件的發展代特征數據挖掘算法集成分布計算模型數據模型第一代作為一個獨立的應用支持一個或者多個算法獨立的系統單個機器向量數據第二代和數據庫以及數據倉庫集成多個算法：能夠挖掘一次不能放進內存的數據數據管理系統，包括數據庫和數據倉庫同質、局部區域的計算機群集有些系統支持對象,文本和連續的媒體數據第三代和預言模型系統集成

多個算法數據管理和預言模型系統intranet/extranet網絡計算支持半結構化數據和web數據第四代和移動數據/各種計算設備的數據聯合

多個算法數據管理、預言模型、移動系統移動和各種計算設備普遍存在的計算模型RobertGrossman，NationalCenterforDataMiningUniversityofIllinoisatChicago的觀點2025/6/350高級人工智能史忠植二、數據挖掘軟件的發展第一代數據挖掘軟件2025/6/351高級人工智能史忠植二、數據挖掘軟件的發展第一代數據挖掘軟件CBA新加坡國立大學?；陉P聯規則的分類算法，能從關系數據或者交易數據中挖掘關聯規則，使用關聯規則進行分類和預測2025/6/352高級人工智能史忠植二、數據挖掘軟件的發展第二代數據挖掘軟件特點與數據庫管理系統（DBMS）集成

支持數據庫和數據倉庫，和它們具有高性能的接口，具有高的可擴展性