aai09知識發(fā)現(xiàn)和數(shù)據(jù)挖掘2高級人工智能史忠植

第九章知識發(fā)現(xiàn)和數(shù)據(jù)挖掘數(shù)據(jù)庫中知識發(fā)現(xiàn)

史忠植中科院計算所2025/6/31高級人工智能史忠植知識發(fā)現(xiàn)關聯(lián)規(guī)則數(shù)據(jù)倉庫知識發(fā)現(xiàn)工具2025/6/32高級人工智能史忠植知識發(fā)現(xiàn)知識發(fā)現(xiàn)是指從數(shù)據(jù)集中抽取和精煉新的模式。范圍非常廣泛：經(jīng)濟、工業(yè)、農(nóng)業(yè)、軍事、社會數(shù)據(jù)的形態(tài)多樣化：數(shù)字、符號、圖形、圖像、聲音數(shù)據(jù)組織各不相同：結(jié)構(gòu)化、半結(jié)構(gòu)化和非結(jié)構(gòu)發(fā)現(xiàn)的知識可以表示成各種形式 規(guī)則、科學規(guī)律、方程或概念網(wǎng)。2025/6/33高級人工智能史忠植數(shù)據(jù)庫知識發(fā)現(xiàn)

目前,關系型數(shù)據(jù)庫技術(shù)成熟、應用廣泛。因此,數(shù)據(jù)庫知識發(fā)現(xiàn)(KnowledgeDiscoveryinDatabasesKDD)的研究非常活躍。

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

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

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

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

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

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

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

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

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

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

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

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

I，B

I，且A∩B=

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

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

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

A，B≠φ，且Confidence（B

(A

B)）

minconf，則構(gòu)成關聯(lián)規(guī)則B

(A

B)2025/6/319高級人工智能史忠植關聯(lián)規(guī)則發(fā)現(xiàn)的基本思路

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

首先生成長度為1的大項集（即單個物品），記為L[1]；在L[k]的基礎上生成候選物品集C[k+1]，候選物品集必須保證包括所有的大項集。用事務數(shù)據(jù)庫D中的事務對C[k+1]進行支持度測試以生成長度為k+1的大項集L[k+1]，計算每個候選物品集的支持度，如果大于minsup，則加入到L[k+1]中。如果L[k+1]為空集，則結(jié)束，L[1]∪L[2]∪…即為結(jié)果；否則轉(zhuǎn)(2)，繼續(xù)。2025/6/320高級人工智能史忠植思路的正確性利用了大物品集向下封閉性，即大物品集X的任意子集一定是大物品集，反過來說，如果X有一子集不是大項集，則X肯定不是。是寬度優(yōu)先算法2025/6/321高級人工智能史忠植經(jīng)典的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}}經(jīng)過join后，C[4]={{1,2,3,4},{1,3,4,5}}由于{1,3,4,5}有子集{1,4,5}不在L[3]中，所以經(jīng)過prune后，得到L[4]={{1,2,3,4}}2025/6/325高級人工智能史忠植2025/6/326高級人工智能史忠植2025/6/327高級人工智能史忠植2025/6/328高級人工智能史忠植2025/6/329高級人工智能史忠植關聯(lián)規(guī)則發(fā)現(xiàn)注意的問題充分理解數(shù)據(jù)目標明確數(shù)據(jù)準備工作要做好選取適當?shù)淖钚〉闹С侄群涂尚哦群芎玫乩斫怅P聯(lián)規(guī)則2025/6/330高級人工智能史忠植關聯(lián)規(guī)則發(fā)現(xiàn)使用步驟連接數(shù)據(jù)，做數(shù)據(jù)準備給定最小支持度和最小可信度，利用知識發(fā)現(xiàn)工具提供的算法發(fā)現(xiàn)關聯(lián)規(guī)則可視化顯示、理解、評估關聯(lián)規(guī)則2025/6/331高級人工智能史忠植關聯(lián)規(guī)則在保險業(yè)務中的應用最小支持度1%，最小可信度為50%2025/6/332高級人工智能史忠植2025/6/333高級人工智能史忠植2025/6/334高級人工智能史忠植2025/6/335高級人工智能史忠植數(shù)據(jù)倉庫在過去幾十年，數(shù)據(jù)庫技術(shù)，特別是OLTP（聯(lián)機事務處理），主要是為自動化生產(chǎn)、精簡工作任務和高速采集數(shù)據(jù)服務。它是事務驅(qū)動的、面向應用的。20世紀80年代，人們要利用現(xiàn)有的數(shù)據(jù)，進行分析和推理，從而為決策提供依據(jù)。這種需求既要求聯(lián)機服務，又涉及大量用于決策的數(shù)據(jù)。而傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)已無法滿足這種需求：所需歷史數(shù)據(jù)量很大，而傳統(tǒng)數(shù)據(jù)庫一般只存儲短期數(shù)據(jù)。涉及許多部門的數(shù)據(jù)，而不同系統(tǒng)的數(shù)據(jù)難以集成。對大量數(shù)據(jù)的訪問性能明顯下降

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

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

數(shù)據(jù)倉庫中的數(shù)據(jù)是面向主題的

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

數(shù)據(jù)倉庫中的數(shù)據(jù)是集成的

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

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

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

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

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

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

數(shù)據(jù)倉庫為知識發(fā)現(xiàn)提供經(jīng)過良好預處理的數(shù)據(jù)源

知識發(fā)現(xiàn)往往依賴于經(jīng)過良好組織和預處理的數(shù)據(jù)源，數(shù)據(jù)的好壞直接影響知識發(fā)現(xiàn)的效果。數(shù)據(jù)倉庫具有從各種數(shù)據(jù)源中抽取數(shù)據(jù)，并對數(shù)據(jù)進行清洗、聚集和轉(zhuǎn)換等各種處理的能力2025/6/348高級人工智能史忠植一、數(shù)據(jù)挖掘概念----發(fā)展1989IJCAI會議：數(shù)據(jù)庫中的知識發(fā)現(xiàn)討論專題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數(shù)據(jù)挖掘方面更多的國際會議PAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.2025/6/349高級人工智能史忠植二、數(shù)據(jù)挖掘軟件的發(fā)展代特征數(shù)據(jù)挖掘算法集成分布計算模型數(shù)據(jù)模型第一代作為一個獨立的應用支持一個或者多個算法獨立的系統(tǒng)單個機器向量數(shù)據(jù)第二代和數(shù)據(jù)庫以及數(shù)據(jù)倉庫集成多個算法：能夠挖掘一次不能放進內(nèi)存的數(shù)據(jù)數(shù)據(jù)管理系統(tǒng)，包括數(shù)據(jù)庫和數(shù)據(jù)倉庫同質(zhì)、局部區(qū)域的計算機群集有些系統(tǒng)支持對象,文本和連續(xù)的媒體數(shù)據(jù)第三代和預言模型系統(tǒng)集成

多個算法數(shù)據(jù)管理和預言模型系統(tǒng)intranet/extranet網(wǎng)絡計算支持半結(jié)構(gòu)化數(shù)據(jù)和web數(shù)據(jù)第四代和移動數(shù)據(jù)/各種計算設備的數(shù)據(jù)聯(lián)合

多個算法數(shù)據(jù)管理、預言模型、移動系統(tǒng)移動和各種計算設備普遍存在的計算模型RobertGrossman，NationalCenterforDataMiningUniversityofIllinoisatChicago的觀點2025/6/350高級人工智能史忠植二、數(shù)據(jù)挖掘軟件的發(fā)展第一代數(shù)據(jù)挖掘軟件2025/6/351高級人工智能史忠植二、數(shù)據(jù)挖掘軟件的發(fā)展第一代數(shù)據(jù)挖掘軟件CBA新加坡國立大學。基于關聯(lián)規(guī)則的分類算法，能從關系數(shù)據(jù)或者交易數(shù)據(jù)中挖掘關聯(lián)規(guī)則，使用關聯(lián)規(guī)則進行分類和預測2025/6/352高級人工智能史忠植二、數(shù)據(jù)挖掘軟件的發(fā)展第二代數(shù)據(jù)挖掘軟件特點與數(shù)據(jù)庫管理系統(tǒng)（DBMS）集成

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