DATABASESYSTEMCONCEPTS第13章數據倉庫與數據挖掘113.2數據倉庫1992年william

H.Inmon

在《BuildingtheDataWarehouse》一書中首先系統的闡述了關于數據倉庫的思想、理論，從此數據倉庫的研究和應用得到了廣泛的關注，Inmon被人們尊稱為“數據倉庫之父”。2一、數據倉庫綜述數據倉庫中數據組織的基本原則是面向主題性表示，DW中的所有數據都是圍繞著某一主題組織、展開的。例如，在企業銷售管理中的管理人員，所關心的是本企業什么時候，哪些產品銷售量大，利潤高？那些客戶采購的產品數量多？競爭對手的那些產品對本企業產品構成威脅？根據這些管理決策的分析對象，就可以抽取出“產品”、“客戶”、“時間”等主題。3數據倉庫綜述數據倉庫的數據仍具有集合性，意味著必須以某種數據集合的形式存儲起來。目前DW所采用的數據集合方式主要是：1.關系模式，以關系數據庫方式存儲

2.多維模式，以多維數據庫方式存儲

3.混合模式，兩者相結合的方式存儲數據倉庫工具集主要由一些分析工具組成，主要包括檢索查詢工具，多維數據的OLAP分析工具、統計分析及數據挖掘工具

4數據倉庫綜述元數據:倉庫結構描述,模式,視圖,維,導出數據的定義;匯總算法,數據庫到數據倉庫的映射,系統數據,元數據作目錄用,保存在當前磁盤上,倉庫中元數據作為數據的數據，可對數據倉庫中的各種數據進行詳細的描述與說明，說明每個數據的上下文關系，使每個數據具有符合現實的真實含義，使最終用戶了解這些數據之間的關系。

5二、OLAP綜述數據庫是長期儲存在計算機存貯介質上，有一定組織形式、可共享的數據集合。數據倉庫是一個面向主題的、集成的、非易失的且隨時間變化的數據集合，用來支持管理人員的決策。數據庫的主要任務是OLTP（聯機事務處理）

6

OLAP綜述數據倉庫的主要任務是OLAP（聯機分析處理）

OLTP面向客戶、辦事員、操作員的事務和查詢處理OLAP面向經理、主管、分析人員的數據分析OLTP處理的數據是基本表中的元組數據OLAP處理的數據是不同粒度的匯總數據7

OLAP綜述OLTP采用E-R模型和面向應用的數據庫設計

OLAP采用星型或雪花模型和面向主題的多維數據立方體設計OLTP主要功能是DBMSOLAP主要功能是檢索查詢工具，多維數據分析工具、統計分析及數據挖掘工具8三、多維數據模型數據倉庫和OLAP基于多維數據模型---數據立方體

三季度一季度二季度寧波四季度杭州濟南萊蕪計算機電話電視音響6058258729709多維數據模型數據立方體允許以多維對數據建模和觀察，由維表和事實表組成例：商品銷售立方體維表：時間維表、商品維表、商店維表、

地區維表事實表：各維表的碼和度量（銷售金額、銷售量）10多維數據模型多維數據模型分為星型模型和雪花模型

時間鍵天星期幾月季年時間鍵商品鍵商店鍵地區鍵銷售金額銷售量商店鍵商店名商店類型地區鍵街道城市省國家商品鍵商品名商標類別供應商類型商店維時間維銷售事實表地區維商品維11多維數據模型

時間鍵天星期幾月季年時間鍵商品鍵商店鍵地區鍵銷售金額銷售量商店鍵商店名商店類型地區鍵街道城市鍵商品鍵商品名商標類別供應鍵商店維時間維銷售事實表地區維商品維城市鍵城市省國家供應鍵供應商類型12多維數據模型常用的多維數據模型，見曹譯本產品缺陷與質量分析商標管理---促銷分析咨詢服務---費用分析咨詢服務---使用分析金融---帳目分析金融---信貸分析13多維數據模型保健—服務使用人力資源—雇員停工期和調動人力資源---工資津貼分析生產---循環時間生產---庫存事務處理分析生產---勞動時間分析生產---定期發貨分析14多維數據模型生產---產品成本分析生產---供應能力分析產品管理---市場分析銷售---顧客人口統計分析銷售---商品供應線管理分析銷售---銷售分析銷售---軟件產品銷售分析15多維數據模型銷售---電信產品銷售分析服務中心---尋呼分析16

13.3數據挖掘數據挖掘的定義數據挖掘就是應用一系列技術從大型數據庫或數據倉庫中提取人們感興趣的信息和知識，這些知識或信息是隱含的，事先未知而潛在有用的，提取的知識表示為概念、規則、規律、模式等形式。數據挖掘是一類深層次的數據分析。

17一、數據挖掘方法數據挖掘的方法和技術信息論方法：ID3方法------決策樹分類集合論方法：粗糙集方法----用于分類模糊論方法----用于聚類人工神經網絡方法：用于分類、聚類、特征挖掘、預測遺傳算法：用于分類18數據挖掘統計分析方法：相關分析.回歸分析.差異分析.因子分析.聚類分析.判別分析文本挖掘：文本分類、文本聚類、Web挖掘可視化技術：可視化數據分析技術拓寬了傳統的圖表功能，使用戶對數據的剖析更清楚。19二、數據挖掘—分類分類的概念已知訓練集中的對象屬于某個類的情況下，把給定的數據分到一定的類中。分類的兩步過程：首先，在已知訓練數據集上，根據屬性特征，為每一種類別找到一個合理的描述或模型，即分類規則，形成分類器。其次根據規則對新數據進行分類。

20數據挖掘—分類分類的主要算法（1）決策樹算法（2）貝葉斯分類算法（3）神經網絡分類算法（4）遺傳算法（5）粗糙集分類算法21數據挖掘—分類分類方法的評估標準（1）準確率表示分類模型正確的預測新的或先前未見過的數據的類標號的能力。（2）速度表示產生和使用模型的計算花費，即時間復雜性。（3）健壯性22數據挖掘—分類表示對于給定的帶噪聲的數據和具有空缺值的數據，模型正確預測的能力。（4）可伸縮性表示對于給定的不同大小數據集，有效的構造模型的能力（5）可解釋性反映學習模型提供的理解和洞察的層次。23

三、決策樹分類器決策樹分類器決策樹是一種用于產生分類規則的樹結構樹中的內節點表示在一個屬性上的測試每個樹葉代表類或類分布樹中的每個分枝代表一個測試輸出，即一條規則。樣本的屬性為結點，信息量最大的為根結點

屬性的值為分支24數據挖掘----分類決策樹算法：ID3、CART、QUEST、C4.5ID3算法基本思想是貪心算法，采用自上而下的分而治之的方法構造決策樹。首先檢測訓練數據集的所有屬性，選擇信息增益最大的屬性A建立決策樹根節點，由該屬性特征的不同取值建立分枝25數據挖掘----分類對各分枝的實例子集遞歸，用該方法建立樹的節點和分枝，直到某一子集中的數據都屬于同一類別，或者沒有特征可以再用于對數據進行分割。

26數據挖掘----分類例：氣候訓練集

NO.屬性類別天氣氣溫濕度風1晴熱高無風N2晴熱高有風N3多云熱高無風P4雨適中高無風P5雨冷正常無風P6雨冷正常有風N7多云冷正常有風P27數據挖掘----分類

8晴適中高無風N9晴冷正常無風P10雨適中正常無風P11晴適中正常有風P12多云適中高有風P13多云熱正常無風P14雨適中高有風N28數據挖掘----分類結果：決策樹----分類器

晴天氣濕度P風NPNP雨多云高正常有風無風29數據挖掘----分類屬性信息增益（互信息）計算：

I（U，V）=H（U）-H（U/V）

=類別熵–條件熵其中，U為類別集合，{N，P}V為屬性的值集合類別熵（先驗熵）的計算：H（U）=∑P(ui

)log2(1/P(ui

))=-∑P(ui

)log2(P(ui

))30數據挖掘----分類P(ui

)=屬于ui

類的樣本數/全體樣本數條件熵（后驗熵）的計算：H（U/V）=∑P(vj

)∑P(ui︱vj

)log2(1/P(ui

︱vj

)))P(vj

)=屬性取值為vj

的樣本數/全體樣本數如屬性為天氣，v1為晴，v2為多云，v3為雨31數據挖掘----分類P(ui︱vj

)=屬性取值為vj

的樣本中屬于ui類的樣本/屬性取值為vj

的樣本數實例類別熵計算：u1=P

，P(u1

)=9/14u2=N

，P(u2)=5/14H（U）=-∑P(ui

)log2(P(ui

))=（9/14）log2(14/9)+（5/14）/

log2(14/5)=0.9432數據挖掘----分類類別熵計算：屬性為天氣，v1為晴，v2為多云，v3為雨P(v1)=5/14,14行中5行為晴P(v2)=4/14,P(v3)=5/14，u1為P,P(u1/

v1)=2/5，5行晴中P類2u2為N,P(u2/

v1)=3/5，5行晴中N類3同理33數據挖掘----分類P(u1/

v2)=4/4P(u2/

v2)=0/4P(u1/

v3)=2/5P(u1/

v3)=3/5

H（U/V）=（5/14）[（2/5）log2(5/2)+（3/5）log2(5/3)]+（4/14）[（4/4）log2(4/4)+0]+（5/14）

[

（2/5）log2(5/2)+（3/5）log2(5/3)]=0.69434數據挖掘----分類天氣屬性的信息增益（互信息）I（天氣）=0.94-0.694=0.246同理可求：I（氣溫）=0.029I（濕度）=0.151I（風）=0.048選取信息增益最大的屬性，天氣，為根結點35數據挖掘----分類在14個樣本中，按根結點的三個值建分支，對應三個序號的子集：F1={1，2，8，9，11}F2={3，7，12，13}F3={4，5，6，10，14}其中F2中樣本全屬P類，分支標記為P類F1，F2中繼續遞歸建子樹，注意求子樹的信息增益仍用全部屬性（4個）

36數據挖掘----分類F1中，天氣屬性的值全部取“晴”，余下的三個屬性中，濕度的信息增益最大，再按其值分支。F1中，天氣屬性的值全部取“晴”，余下的三個屬性中，風的信息增益最大，再按其值分支。最后得出決策樹。37數據挖掘----分類決策樹算法的基本策略：樹以代表訓練樣本的單個結點開始（根）（所有的數據都在根結點）如果樣本都在同一類。則該結點成為樹葉，并用該類標記；否則，算法使用信息增益的基于熵的度量作為啟發信息，選擇能夠最好的將樣本分類的屬性，該屬性成為該結點的“測試”或“判定”屬性；

38數據挖掘----分類對于測試屬性的每個已知的值，創建一個分枝，并據此劃分樣本；算法使用同樣的過程，遞歸的形成每個劃分上的樣本決策樹，一旦一個屬性出現在一個結點上，就不必考慮該結點的任何后代；遞規劃分停止的條件給定結點的所有樣本屬于同一類；39數據挖掘----分類

沒有剩余屬性可以用來進一步劃分樣本，在此情況下，使用多數表決。這設計獎給定的節點轉換成樹葉，并用Samples的多數所在的類標記它。分枝test_attribute=ai

沒有樣本，這時，以Samples中的多數創建一個樹葉。

40數據挖掘----分類算法描述算法：Generate-decision_tree由給定的訓練數據集產生一棵決策樹。輸入：訓練樣本Samples,由離散值屬性表示；候選屬性的集合attribute_list輸出：一棵決策樹方法：創建結點N41數據挖掘----分類2）ifSamples都在同一類Cthen3）返回N作為葉結點,以類C標記;4）ifattribute_list為空then5）返回N作為葉結點，標記為Samples最普通的類；//使用多數表決。6）選擇attribute_list中具有最高信息增益的屬性test_attribute;7）標記結點N為test_attribute;

42數據挖掘----分類8）foreachtest_attribute中已知值ai//劃分Sample;9）由結點N長出一個條件為test_attribute=ai的分枝；10）設Si是Sample中test_attribute=ai

的樣本集合//一個劃分11）ifSi為空then43數據挖掘----分類12）加上一個樹葉，標記為Samples中最普通的類；13）else加上一個由Generate_decision_tree(Si,,attribute_list_返回的結點

44數據挖掘----分類由決策樹提取分類規則從根結點到葉的每條路經創建一條規則葉結點包含類預測，形成規則后件每條路經上除葉結點外的每個結點屬性對構成規則前件的合取項規則用IF_THEN形式表達45數據挖掘----分類例：IF天氣=“多云”THEN類別=”P”IF天氣=“晴”and濕度=“高”THEN類別=”N”IF天氣=“晴”and濕度=“正常”THEN類別=”P”IF天氣=“雨”and風=“有風”THEN類別=”N”IF天氣=“雨”and風=“無風”THEN類別=”P”46數據挖掘----分類決策樹的優點：可以生成可理解的規則計算量相對來說不是很大，速度較快可以處理連續和種類屬性決策樹可以清晰的顯示那些屬性比較重要。

決策樹的缺點：

對連續性的屬性比較難預測對有時間順序的數據，需要預處理47四、粗糙集分類粗糙集方法是用上、下近似集來處理不確定性問題基本思想：把對象（元組）的屬性分為條件屬性和決策屬性，按各屬性相同劃分成等價類條件屬性和決策屬性之間有三種關系：下近似：決策屬性包含條件屬性上近似：決策屬性和條件屬性之交非空無關：48數據挖掘----分類粗糙集分類

基于訓練集數據的等價類,等價類中的樣本描述同一類數據有些類不能被屬性區分,粗糙集用集合近似“粗略”地定義這些類C類的下近似集中樣本,全部屬于C類C類的上近似集中樣本,部分屬于C類49數據挖掘----分類粗糙集方法是用上、下近似集來處理不確定性問題基本思想：把對象（元組）的屬性分為條件屬性和決策屬性(類)，按各屬性相同劃分成等價類條件屬性和決策屬性之間有三種關系：下近似：決策屬性包含條件屬性上近似：決策屬性和條件屬性之交非空無關：50數據挖掘----分類然后對下近似建立確定性規則，對上近似建立不確定性規則，無關情況下不存在規則。

|----------------------|

|||

|

C的下近似|||

------

|------------C的上近似

51數據挖掘----分類引例：

流感數據表條件屬性C決策屬性DU頭疼（a）肌肉痛（b）體溫（c）流感（d）e1是（1）是（1）正常（0）否（0）e2是（1）是（1）高（1）是（1）e3是（1）是（1）很高（2）是（1）e4否（0）是（1）正常（0）否（0）e5否（0）否（0）高（1）否（0）e6否（0）是（1）很高（2）是（1）e7是（1）否（0）高（1）是（1）52數據挖掘----分類定義

粗糙集系統S=（U，A，V，F）U：對象（元組）集合，U={e1,e2,…,en}

例如U={e1,e2,…,e7}A：屬性集合，分成不相交的條件屬性集C和決策屬性集D

例如C={頭疼，肌肉痛，體溫

}，D={流感

}V:屬性值的集合，值域，例如V體溫

={正常，高，很高}53數據挖掘----分類

F：值影射函數，U×A→V，f(ei,a)∈Va

例如f(e2,頭疼)=“是”等價集（不分明集）的定義：給定屬性A，

a∈A,ei∈U，ej∈U有f(ei,a)=f(ej,a),（兩行A屬性值相等），則ei

與ej

關于A等價。等價的對象（元組）形成等價集，關于A的所有等價集形成U上的一個劃分54數據挖掘----分類

例如條件屬性集C(頭疼，肌肉痛，體溫)的等價集為：E1={e1},E2={e2},E3={e3},E4={e4},E5={e5},E6={e6},E7={e7};(七行皆不相等）劃分E={E1，E2，E3，E4，E5，E6，E7}例如決策屬性集D(流感)的等價集為：Y1={e1,e4，e5}

,Y2={e2,e3，e6，e7

}

劃分Y={Y1，Y2};(相等的行成一集）55數據挖掘----分類等價集的下近似集設U關于A的劃分E，關于A’的劃分YYj（Yj

∈Y）是A’的一個等價集，Yj關于A的下近似集定義：

AYj=∪

{Ei∣Ei∈E且Ei

Yj}

含義：E中被Yj包含的各等價集的并集例如決策屬性D的等價集分別是：Y1={e1,e4，e5}，Y2={e2,e3，e6，e7

}56數據挖掘----分類關于條件屬性C的下近似集分別是：

CY1={E1}∪{E4}∪{

E5}={e1,e4,e5}

CY2={E2}∪{E3}∪{

E6}∪{E7}

={e2,e3,e6,e7}

Yj（Yj

∈Y）是A’的一個等價集，Yj關于A的上近似集定義：

AYj=∪

{Ei∣Ei∈E且Ei∩

Yj

≠Φ}57數據挖掘----分類含義：E中各等價集與Yj的交集非空的并集例如決策屬性D的等價集分別是：E={{e1},{e2},{e3},{e4},{e5},{e6},{e7}}Y1={e1,e4，e5}，Y2={e2,e3，e6，e7

}CY1={E1}∪{E4}∪{

E5}={e1,e4,e5}

CY2={E2}∪{E3}∪{

E6}∪{E7}

={e2,e3,e6,e7}

58數據挖掘----分類

AYj–

AYj

（上近似集與下近似集差集）稱為邊界線區域確定度：αA（Yj

）=(∣U∣-∣AYj–

AYj∣)/∣U∣其中：∣U∣，∣AYj–

AYj∣分別表示元素個數，如∣U∣=7，∣AY1–

AY2∣=0例如αC（Y1）=1，αC（Y2）=1含義：αA（Yj

）反映U中對象根據A中屬性就可以確定其屬于Yj的比例。59數據挖掘----分類若αA（Yj

）=1，U中每個對象都可以根據A中屬性確定其是否屬于Yj若0<αA（Yj

）<1，U中部分對象可以根據A中屬性確定其是否屬于Yj若αA（Yj

）=0，U中每個對象都不能根據A中屬性確定其是否屬于YjαA（Yj

）是根據A確定對象屬于Yj的可信度60數據挖掘----分類

最小屬性集去掉多余的屬性后的屬性集屬性集C與屬性集D之間的依賴程度：

γ（C，D）=︱POS（C，D）︱/︱

U︱其中：POS（C，D）=∪{C

Yj

︱j=1,2,…}

例如：POS（C，D）=CY1∪CY2={e1,e2，e3，e4,e5，e6，e7}

︱POS（C，D）︱=7，︱

U︱=7γ（C，D）=161數據挖掘----分類γ反映條件屬性C能區分決策屬性等價集的能力γ（C，D）∈[0，1]若γ（C，D）=0，根據條件屬性C的值無法將任何對象準確分類；若γ（C，D）=1，根據條件屬性C的值可以將任何對象準確分類；62數據挖掘----分類屬性的重要度

C為條件屬性集，D為決策屬性集,a∈C,a關于D的重要度：

SGF（C-{

a}，D）=γ（C，D）-γ（C-{a}，D）含義：C去掉a后導致對象不能被準確分類的比例63數據挖掘----分類

SGF（C-{

a}，D）

∈[0，1]若SGF（C-{

a}，D）=0，可以從根據條件屬性C中去掉a

；若SGF（C-{

a}，D）

≠0，不可以從根據條件屬性C中去掉a；

P（PC）是C的最小屬性集，當且僅當γ（P，D）=γ（C，D）含義：P與C具有同樣的決策能力64數據挖掘----分類

例如C={a,b,c},D=xusrzyv

a的重要度計算：條件屬性集C’={b,c}C’=等價集為E1={e1,e4},E2={e2},E3={e3,e6},E4={e5,e7}D的等價集為Y1={e1,e4，e5},Y2={e2,e3，e6，e7}C’Y1={E1}={e1,e4},C’Y2={E2，E3}={e2,e3，e6}65數據挖掘----分類

POS（C-{a}，D）=C’Y1∪C’Y2={e1,e2，e3，e4，e6}

︱POS（C-{a}，D）︱=5，︱

U︱=7γ（C-{a}，D）=5/7

SGF（C-{a}，

D）=

γ（C，D）-γ（C-{a}，D）=1-5/7≠0結論：屬性a不可去掉66數據挖掘----分類同理可以求屬性b的重要度：

SGF（C-{b}，

D）=

γ（C，D）-γ（C-{b}，D）=1-1=0結論：屬性b可去掉簡化原流感數據表，去掉屬性‘肌肉痛’，合并相同的元組67數據挖掘----分類

流感數據表條件屬性C決策屬性DU頭疼（a）體溫（c）流感（d）e1是（1）正常（0）否（0）e2是（1）高（1）是（1）e3是（1）很高（2）是（1）e4否（0）正常（0）否（0）e5否（0）高（1）否（0）e6否（0）很高（2）是（1）68數據挖掘----分類條件屬性集C(頭痛，體溫)的等價集為：E1={e1},E2={e2},E3={e3},E4={e4},E5={e5},E6={e6},劃分E={E1，E2，E3，E4，E5，E6},

決策屬性集D(流感)的等價集為：Y1={e1,e4，e5}

,Y2={e2,e3，e6

}劃分Y={Y1，Y2}69數據挖掘----分類獲取規則條件屬性集C的劃分E={E1，E2，…,Ei,…},

決策屬性集D的劃分Y={Y1，Y2,…,Yj,…}1)如果Ei

∩

Yj

≠Φ，則有規則：

rij

=Des(Ei)→Des(Yj)

當Ei

∩

Yj=Ei時，rij

確定，可信度cf=1

70數據挖掘----分類當Ei

∩

Yj

≠

Ei時，rij不確定，可信度cf=︱Ei

∩

Yj︱/︱Ei︱

2）如果Ei

∩

Yj=Φ，Ei與Yj不能建立規則。例如：E1∩Y1=

E1，E4∩Y1=

E4，E5∩Y1=

E5，有規則：r11=Des(E1)→Des(Y1)，即頭痛=是∧體溫=正常→流感=否，cf=171數據挖掘----分類

r41=Des(E4)→Des(Y1)，即頭痛=否∧體溫=正常→流感=否，cf=1r51=Des(E5)→Des(Y1)，即頭痛=否∧體溫=高→流感=否，cf=1例如：E2∩Y2=

E2，E3∩Y2=

E3，E6∩Y2=

E6，有規則：r22=Des(E2)→Des(Y2)，即頭痛=是∧體溫=高→流感=是，cf=172數據挖掘----分類r32=Des(E3)→Des(Y2)，即頭痛=是∧體溫=很高→流感=是，cf=1

r62=Des(E2)→Des(Y2)，即頭痛=否∧體溫=很高→流感=是，cf=1合并：r11與

r41得：（頭痛=是∨頭痛=否）∧體溫=正常→流感=否，cf=1，等價體溫=正常→流感=否，cf=173數據挖掘----分類合并：r32與

r62得：（頭痛=是∨頭痛=否）∧體溫=很好→流感=是，cf=1，等價體溫=很好→流感=是，cf=1最后的規則：1）體溫=正常→流感=否2）頭痛=否∧體溫=高→流感=否74數據挖掘----分類3）體溫=很高→流感=是4）頭痛=是∧體溫=高→流感=是75五、樸素貝葉斯分類統計學分類方法,給定樣本,求屬于每個類的概率,按最大值分配樣本到該類樸素:假定一個屬性值對給定類的影響獨立于其他屬性的值.貝葉斯定理:設X是未知類的樣本,H是X屬于C的一個假定,X的分類問題變為求P(H︱X),即給定X,H成立的概率76數據挖掘----分類P(H︱X)稱為條件X下H的后驗概率:

P(H︱X)=

P(X︱H)P(H)/P(X)其中:P(X︱H)稱為條件H下X的后驗概率;P(H)是H的先驗概率,獨立于X;P(X)是X的先驗概率;例如:樣本的類是各種水果,X表示是紅色和圓的樣本,H假定X是蘋果類,P(H︱X)表示:當X是紅色和圓的樣本時,X屬蘋果類的確信度.77數據挖掘----分類P(H)表示任意給定的樣本是蘋果的概率;P(X︱H)表示已知樣本是蘋果,

X是紅色和圓的樣本概率;P(X)表示樣本集中任取一個樣本是紅色和圓的樣本概率;樸素貝葉斯分類算法:每個樣本表示為n維向量:X={x1,x2,…,xn},屬性A1,A2,…An的值設定m個類C1,C2,…Cm,對未知類的樣本X,78數據挖掘----分類當且僅當P(Ci︱X)>P(Cj︱X),(1≤j≤m,i≠j),將X分配給類Ci,即P(Ci︱X)>是最大的,按貝葉斯公式

P(Ci︱X)=

P(X︱Ci)P(Ci)/P(X)其中:P(X)對每個類是常數,只需求

P(X︱Ci)P(Ci)

P(Ci)=Ci中的訓練樣本數/訓練樣本總數如果P(Ci)未知,假定P(C1)=P(C2)=…=P(Cm)79數據挖掘----分類

按屬性值相互條件獨立的樸素假定

P(X︱Ci)=∏nk=1

P(Xk︱Ci)其中:P(Xk︱Ci)=類Ci中具有Xk值的樣本數/類Ci中樣本數結論:實驗研究表明,與所有分類算法相比,貝葉斯分類具有最小的出錯率,可以與之媲美,經常被用作其他分類算法的理論判定80數據挖掘----分類例:購買電子產品顧客數據訓練樣本集序號年齡收入學生信用類：買計算機1<=30高否一般否2<=30高否優秀否331..40高否一般是4>40中否一般是5>40低是一般是6>40低是優秀否731..40低是優秀是8<=30中否一般否9<=30低是一般是10>40中是一般是11<=30中是優秀是1231..40中否優秀是1331..40高是一般是14>40中否優秀否81數據挖掘----分類

例:對未知類樣本的分類

X=(年齡=“<=30”,收入=“中”,學生=“是”,信用=“一般”)P(C1)=P(買計算機=“是”)=9/14=0.643P(C2)=P(買計算機=“否”)=5/14=0.357為計算P(X︱Ci),i=1,2,先求:P(年齡=“<=30”︱買計算機=“是”)=2/9=0.222P(年齡=“<=30”︱買計算機=“否”)=3/5=0.60082數據挖掘----分類P(收入=“中”︱買計算機=“是”)=4/9=0.444P(收入=“中”︱買計算機=“否”)=2/5=0.400P(學生=“是”︱買計算機=“是”)=6/9=0.667P(學生=“是”︱買計算機=“否”)=1/5=0.200P(信用=“一般”︱買計算機=“是”)=6/9=0.667P(年齡=“一般”︱買計算機=“否”)=2/5=0.400得:P(X︱Ci),i=1,2P(X︱C1)=P(X︱買計算機=“是”)

=0.222*0.444*0.667*0.667=0.04483數據挖掘----分類P(X︱C1)=P(X︱買計算機=“否”)

=0.600*0.400*0.200*0.400

=0.019得

P(X︱Ci)P(Ci),i=1,2

P(X︱C1)P(C1)=P(X︱買計算機=“是”)P(買計算機=“是”)=0.044*0.643=0.028P(X︱C2)P(C2)=P(X︱買計算機=“否”)P(買計算機=“否”)=0.019*0.357=0.007結果:將X分配到C1類,即買計算機=“是”84數據挖掘----分類P(收入=“中”︱買計算機=“是”)=4/9=0.444P(收入=“中”︱買計算機=“否”)=2/5=0.400P(學生=“是”︱買計算機=“是”)=6/9=0.667P(學生=“是”︱買計算機=“否”)=1/5=0.200P(信用=“一般”︱買計算機=“是”)=6/9=0.667P(年齡=“一般”︱買計算機=“否”)=2/5=0.400得:P(X︱買計算機=“是”)=0.222*0.444*0.667*0.667=0.04485六、人工神經網絡分類人工神經網絡方法仿真生物神經網絡，本質上是一個分散型或矩陣結構。通過對訓練數據的輸入逐步修正網絡連接的權值,形成一個分類器。人工神經網絡方法主要有：前饋網絡：含感知機.反向傳輸模型.函數式網絡。反饋式網絡：用于聯想記憶和優化計算。86數據挖掘----分類

基本概念

x1

x2

xi輸入層

wij

Ok

wjk

Oj隱藏層輸出層87數據挖掘----分類

多層前饋神經網絡每個圓圈為一個神經元輸入層:訓練樣本X={x1,x2,…,xi}輸入,該層每個神經元為X的一個屬性值輸入隱藏層(Oj):類神經元的第二,第三層,…,前一層的輸入加權作為本層的輸入,本層的輸出加權為下層的輸入.第二層前連輸入層,最后一層后連輸出層.隱藏層的數量任意,只一層,稱為兩層神經網絡,有兩層為三層神經網絡.實踐中通常用一層.88數據挖掘----分類輸出層(Ok):

輸出給定樣本的類預測輸入層單元的值規范化:訓練樣本的屬性值是連續的,規范化為0.0—1.0之間,是離散的,規范化為0或1.輸出層單元的值規范化:輸出為兩個類,用一個輸出單元,1代表一個類,0代表一個類;輸出為多個類,每個類用一個輸出單元后向傳播算法使用多層前饋神經網絡,最流行89數據挖掘----分類

基本思想:

1)前向傳播輸入:前一層的輸出乘以權加偏置得本層的單元值,依次傳播到輸出層2)后向傳播誤差:從輸出層開始計算本層的誤差,更新到本層的權和偏置,依次傳播到第一個隱藏層3)迭代對訓練樣本集的每個樣本重復1),2),直到滿足要求90數據挖掘----分類隱藏層或輸出層單元j的凈輸入:

Ij=∑iwij

Oi+θj

其中:wij是上一層的單元i到本層單元j的權Oi是上一層的單元i到本層單元j的輸出,θj是本層單元j的偏置隱藏層或輸出層單元j的輸出:

Oi=1/(1+e-Ij)91數據挖掘----分類輸出層單元j的誤差:

Errj=Oj(1-Oj)(Tj-Oj)Tj是給定樣本的已知類標號隱藏層單元j的誤差:

Errj=Oj(1-Oj)∑k

Errk

Oi92數據挖掘----分類權更新:

△Wij=(p)Errj

Oi

Wij=Wij+△WijP是學習率,0-1間的常數,太小,學習慢;太大,擺動.取迭代次數的倒數.

偏置的更新:93數據挖掘----分類

△θj

=(p)Errj

θj

=θj

+△θj

初值選取:權和偏置初始值為-1到1間的隨機數終止條件:輸入一個樣本,進行一次前向傳播輸入和后向傳播誤差.94數據挖掘----分類輸入一遍訓練集的每個樣本為一個周期,反復周期迭代,如果滿足以下條件之一,訓練結束.1)前一周期的△Wij都很小2)前一周期的未正確分類率小于給出閾值3)迭代超出預先指定的周期數實驗表明,權收斂需數十萬個周期95數據挖掘----分類例:后向傳播算法學習的樣本計算,X={1,0,1},X類標號Tj=1,學習率p=0.9123456x2x1x3w14w24w15w35w34w46w25w5696數據挖掘----分類

初始輸入、權值、偏置x1x2x3θ4θ5θ6101-0.40.20.1W14W15W24W25W34W35W46W560.2-0.30.40.1-0.50.2-0.3-0.297數據挖掘----分類

凈輸入、輸出的計算單元j凈輸入Ij輸出Oj=1/(1+e-Ij)40.2+0-0.5-0.4=-0.70.3325-0.3+0+0.2+0.2=0.10.5256(-0.3)(0.332)-(0.2)(0.525+0.1=-0.1050.47498數據挖掘----分類

單元誤差計算單元jErrj6(0.474)(1-0.474)（1-0.474）=0.13115(0.525)(1-0.525)（0.1311）(-0.2)=-0.00654(0.332)(1-0.332)（0.1311）(-0.3)=-0.008799數據挖掘----分類

權、偏差的更新權、偏差新值W46-0.3+(0.9)(0.1311)(0.332)=-0.261W56-0.2+(0.9)(0.1311)(0.525)=-0.138W140.2+(0.9)(-0.0087)(1)=0.192W15-0.3+(0.9)(-0.0065)(1)=-0.306W240.4+(0.9)(-0.0087)(0)=0.4W250.1+(0.9)(-0.0065)(0)=0.1W34-0.5+(0.9)(-0.0087)(1)=-0.508W350.2+(0.9)(-0.0065)(1)=0.194θ60.1+(0.9)(0.1311)=0.218θ50.2+(0.9)(-0.0065)=0.194θ4-0.4+(0.9)(-0.0087)=-0.408100七、遺傳算法分類遺傳算法模仿人工選擇培育良種的思路，從一個初始規則集合開始，迭代的通過交換對象成員（雜交、基因突變）產生群體，（繁殖），評估并擇優復制（物競天澤、適者生存、不適應者淘汰）優勝劣汰逐代積累計算，最終得到最有的知識集。遺傳算法三個基本算子：101數據挖掘----分類

繁殖：從一個舊種群選擇出生命力強的個體產生新種群的過程。交叉：選擇兩個不同個體的部分進行交換，形成新個體。變異：對某些個體的某些基因進行變異。

這種遺傳算法能夠產生一群優良后代，這些后代力求滿足適應性、，經過若干代的遺傳，將得到滿足要求的后代，即問題的解。102八、聚類聚類的概念是在要劃分的類未知的情況下，將數據對象分成不同的類，無指導學習。聚類的作用：例：商務上，根據購買模式，發現不同的客戶群；地球觀測中，發現不同的地區；城市數據中，按類型、價值和位置，對房屋進行分組103數據挖掘---聚類聚類中的數據表示對象---屬性矩陣：N×P矩陣

N行：對象個數，P列：屬性個數其中x(i,j)是對象i的屬性j的值相似度矩陣：N×N矩陣

，其d(i,j)是對象i與對象j之間的相似度相似度計算

104數據挖掘---聚類歐幾里得距離

d(i,j)=sqt(∣xi1-xj1∣2+∣xi2-xj2∣2+…+∣xip-xjp∣2)曼哈坦距離d(i,j)=∣xi1-xj1∣

+∣xi2-xj2∣

+…+∣xip-xjp∣105數據挖掘---聚類明考斯基距離d(i,j)=(∣xi1-xj1∣q+∣xi2-xj2∣q+…+∣xip-xjp∣q)1/q

加權的歐幾里得距離

d(i,j)=sqt(w1∣xi1-xj1∣2+w2∣xi2-xj2∣2+…+wp∣xip-xjp∣2)106數據挖掘---聚類

主要聚類方法

1.劃分方法1)初始：確定k個劃分，k個類2)每個類至少一個對象，每個對象只屬于一個類3）按距離，把對象劃分到不同類中典型的方法是k-平均算法、k-中心點算法107九、k-平均算法聚類k-平均算法算法：k-平均輸入：類數目k和包含n個對象的數據庫輸出：k個類方法：1）任選k個對象作為初始類中心2）repeat108數據挖掘---聚類3)計算類中對象的平均值，將每個對象重新賦給最類似的類4）更新類的平均值，5）until不再發生變化說明：初始隨機選擇k個對象，代表類的平均值（類中心），其余對象計算與每個類中心的距離，劃分到最近距離的類中，重新計算類中心，重復。例：109數據挖掘---聚類

●●●●●●●●●●●●●●●●●●●●●110數據挖掘---聚類

●●●●●●★●●★●●●●●●●●●●●★●●111數據挖掘---聚類

●●●●●●★●●★●●●●●●●●●●★●●●112十、k-中心點算法聚類

k-中心點算法算法：k-中心點輸入：類數目k和包含n個對象的數據庫輸出：k個類方法：1）任選k個對象作為初始類中心點2）repeat113數據挖掘---聚類3)將每個對象指派給離中心點最近的類4）隨機選擇非中心點h,計算h替換中心點i的總代價RChi,如果RChi

<0,用h替換中心點，然后對非中心點對象按與新的中心點的距離，指派類5）until不再發生變化114數據挖掘---聚類說明：RChi=∑ki=1∑p∈Ci(︱p-mi’︱2-︱p-mi︱2其中：RChi為h替換中心點i的總代價，p是給定對象，mi是類Ci的中心點，mi’是類Ci用h替換中心點i的后的中心點。基本思想是設置初始中心點后，反復用非中心點對象替換中心點，以改進聚類質量。因為k-平均對孤立點是敏感的115數據挖掘---聚類2.層次方法將聚類對象組成一棵聚類樹，頂端包含所有對象的類，底端是一個個單個對象的類，中間是其相鄰下層類合并的類。分為：凝聚層次聚類：從葉子到根，葉子是一個對象一個類，根是所有對象的類。分裂層次聚類：從根到葉子116數據挖掘---聚類例：五個對象a,b,c,d,e，按歐氏距離計算adeabdecdeabcdebc117數據挖掘---聚類3.其它聚類基于密度的聚類：基于網格的聚類基于模型的聚類

118十一、關聯規則挖掘關聯規則的基本概念數據關聯是數據庫中存在的一類重要的可被發現的知識，若兩個或多個變量間存在著某種規律性，就稱為關聯。關聯分析的目的就是找出數據庫中隱藏的關聯網。關聯分析發現關聯規則，這些規則展示屬性值頻繁地在給定數據集中一起出現的條件。119數據挖掘---關聯規則例：關聯規則：age（x，“20-29”）∧income(x,”2000-3000”)→buys(x,”CD-Player”)[支持度=2%,置信度=60%]表示所研究的顧客2%（支持度）在20—29歲，月薪載2000—3000元，購買CD機的可能性有60%。

例：

啤酒→尿布，是從大型超市的購物籃當中分析出的關聯規則。

120數據挖掘---關聯規則關聯規則的作用例如，買牛奶的顧客有80%也同時買面包，經常一塊購買的商品可以放近一些，以便進一步刺激這些商品一起銷售，例如，如果顧客購買計算機又傾向于同時購買財務軟件，將硬件和軟件放在商店的兩端，可能誘發購買這些商品的顧客一路挑選其他商品。

121數據挖掘---關聯規則基本定義

項集：項的集合稱為項集（itemset）。設I={I?,I2,..,In}是一個項集，其中Ii(I=1,2,3,…,n)可以是購物籃中的物品，也可以是保險公司的顧客。

K項集---包含K個項的項集被成為K項集，表示項集中項的數目。

122數據挖掘---關聯規則事務：事務是項的集合，設有事務T，則T

I。對應每個事務有唯一的標識，如事務號記為ID。設X是I中項的集合，如果X

T，則稱事務T包含X。事務集：事務的集合稱為事務集。設某事務集為D，則D={T1，T2，…,Tn},D={Ti|Ti∈D,i=1,2,…,n}.

123數據挖掘---關聯規則例：超市事務數據庫，9個事務，事務的項按字典順序存放。

TID項ID的列表T1T2T3T4T5T6T7T8T9牛奶，面包，雞蛋面包，

啤酒面包，

咖啡牛奶，面包，啤酒牛奶，咖啡面包，咖啡牛奶，咖啡牛奶，面包，咖啡,雞蛋牛奶，面包，咖啡124數據挖掘---關聯規則關聯規則關聯規則是如下形式的邏輯蘊涵：A

B，其中A，B是項集，A∈I，B∈I，A∩B=Ф。一般用兩個數據描述關聯規則的屬性。設A，B是項集，對于事務集D，A∈D，B∈D，A∩B=Ф，（1）可信度（置信度）：“值得信賴性”。125數據挖掘---關聯規則可信度定義為：可信度（A

B）=包含A和B的元組數/包含A的元組數可信度表達的就是在出現項集A的事務集D中，項集B也同時出現的概率。例如：購買牛奶的顧客中有80%也同時購買了面包，即關聯規則（牛奶）面包）的可信度為80%。126數據挖掘---關聯規則支持度（Support）支持度（A

B）=包含A和B的元組數/元組總數。支持度描述了A和B這兩個項集在所有事務中同時出現的概率。例如在一個商場中，某天共有1000筆業務，其中有100筆業務同時買了牛奶和面包，則其牛奶

面包關聯規則的支持度為10%。127數據挖掘---關聯規則給定一個事務集D，挖掘關聯規則問題就是產生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關聯規則。關聯規則的種類：關聯規則可以分為布爾型和數值型。布爾型考慮的是項集的存在與否，而數值型則是量化的關聯。例如：性別=“女”

職業=“秘書”布爾型性別=“女”

avg（收入）=2300數值型128數據挖掘---關聯規則關聯規則可分為單維的和多維的。單維只涉及到數據的一個維例如：啤酒

尿布單維的關聯規則多維處理的數據會涉及到多個維。例如：性別=“女”

職業=“秘書”多維的關聯規則129數據挖掘---關聯規則關聯規則挖掘的經典算法。Apriori算法(1993年，Agrawal提出)基本概念頻繁項集——所有支持度大于最小支持度的項集稱為頻繁項集，或簡稱項集。強關聯規則——同時滿足最小支持度閾值和最小可信度閾值的規則稱為強規則。找出所有的頻繁項集由頻繁項集產生強關聯規則130數據挖掘---關聯規則Apriori算法（找頻繁項集算法）算法Apriori使用根據候選生成的逐層迭代找出頻繁項集。輸入：事務數據庫D；最小支持度閾值min_sup。輸出：D中的頻繁項集L方法：

131數據挖掘---關聯規則首先產生頻繁1-項集L1，然后是頻繁2-項集L2，…Lr，直到某個r使得Lr為空，這時算法停止。在第k次循環中，L?-1進行自身連接，通過Apriori的性質進行剪枝，產生候選K項集Ck，再對Ck中的每個元素按支持度選取，產生頻繁項集L?。Apriori的性質：頻繁項集的所有非空子集都必須也是頻繁的，132數據挖掘---關聯規則1）L?-?自身連接的規則：設l1和l2是L?-?中的任兩子集，記號li[j]表示li子集中的第j項。如果l?[1]=l2[1]∧……∧l?[k-2]=l2[k-2]∧l1[k-1]<l2[k-1],則做l?∞l2,加入到L?-?自身連接的結果中。注意：連接條件是兩個項的前k-2項相同133數據挖掘---關聯規則2)剪枝步按照Apriori的性質：頻繁項集的所有非空子集都必須也是頻繁的檢查連接產生每個元素，若元素中有子集不在L?-?中，把元素刪除。連接之后的結果Ck是L?的超集，它的成員可能是不頻繁的，掃描數據庫確定Ck中每個候選的計數，按支持度確定L?。134數據挖掘---關聯規則程序：L1={1-itemsets}For(k=2;L?-?≠

;k++)dobeginCk=Apriori-gen(L?-1)//新的候選項集Foralltransactiont∈DdobeginCt=subset(Ck,t);//變量t中所包含的候選集

forallcandidatesc∈CtdoC.count++;end

135數據挖掘---關聯規則

L?={C∈Ck|C.count≥min_sup}endAnswer=üL?Procedureapriori-gen(L?-?:frequent(k-1)-itemsets;min_sup:minimumsupportthreshold)foreachitemsetL1∈L?-?foreachitemsetL2∈L?-?136數據挖掘---關聯規則ifL?[1]=L2[1]∧L?[2]=L2[2]∧……∧L?[k-2]=L2[k-2]∧L1[k-1]<L2[k-1]then{C=L1∞L2//joinstep;generatecandidatesifhas_infrequent_subset(C,L?-?)thendeleteC;//Prunestep;elseaddCtoCk;}returnCk137數據挖掘---關聯規則Procedurehas_infrequent_subset(C:candidateK-itemset;L?-?:frequent(k-1)–itemsets)foreach(K-1)-subsetSofCifS

L?-?thenreturntruereturnfalse.138數據挖掘---關聯規則例：事務數據庫D，9個事務，事務的項按字典順序存放。設最小支持度閾值為2

TID項ID的列表T1T2T3T4T5T6T7T8T9I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3139數據挖掘---關聯規則掃描D，對每個項的出現次數記數，求候選1-項集C1。項集支持度計算{I1}{I2}{I3}{I4}{I5}67622140數據挖掘---關聯規則對C1，按最小支持度閾值為2， 求出支持度大于2的項，為L1項集支持度計算{I1}{I2}{I3}{I4}{I5}67622141數據挖掘---關聯規則由L1∞L1自身連接，產生候選2-項集C2項集支持度計算{I1，I2}{I1，I3}{I1，I4}{I1，I5}{I2，I3}{I2，I4}{I2，I5}{I3，I4}{I3，I5}{I4，I5}4412422010142數據挖掘---關聯規則按最小支持度閾值為2，由C2產生L2項集支持度計算{I1，I2}{I1，I3}{I1，I5}{I2，I3}{I2，I4}{I2，I5}

442422

143數據挖掘---關聯規則由L2∞L2自身連接，前K-2項相等（K=3），最后一項不等，得連接結果：

{{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}}∞{{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}}={{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}}144數據挖掘---關聯規則按照頻繁集的子集必須是頻繁的，以L2={{I1，I2}，{I1，I3}，{I1，I5}，{I2，I3}，{I2，I4}，{I2，I5}}為準，剪枝，得C3項集支持度計算{I1，I2，I3}{I1，I3，I5}22145數據挖掘---關聯規則按最小支持度閾值為2，由C3產生L3項集支持度計算{I1，I2，I3}{I1，I3，I5}22146數據挖掘---關聯規則由L3∞L3自身連接，前K-2項相等（K=4），最后一項不等，得連接結果：{{I1，I2，I3}，{I1，I2，I5}}∞{{I1，I2，I3}，{I1，I2，I5}}={{I1，I2，I3，I5}}按照頻繁集的子集必須是頻繁的，子集{I2，I3，I5}

L3,故剪去{I1，I2，I3，I5}故C4=

，L4=

，算法終止。147數據挖掘---關聯規則關聯規則的產生方法對于每個頻繁項集L，產生L的所有非空子集；對每個非空子集S，如果support_count(L)/support_count(S)≥minconf,則輸出關聯規則“S

(L-S)”說明：1）關聯規則“S

(L-S)”的可信度計算：148數據挖掘---關聯規則按可信度公式可信度（A

B）=包含A和B的元組數/包含A的元組數則可信度（S

(L-S)）=包含S和L-S的元組數/包含S的元組數=包含L的元組數/包含S的元組數=support_count(L)/support_count(S)2）minconf是最小可信度閾值，由領域專家或用戶設定

149數據挖掘---關聯規則例：頻繁項集L={I1，I2，I5}，求L產生的關聯規則。求L的非空子集S分別是：{I1,I2},{I1,I5},{I2,I5},{I1},{I2},{I5}

支持數：422672

L的支持數=2，關聯規則如下：1)I1∧I2

I5Confidence=2/4=50%2)I1∧I5

I2Confidence=2/2=100%

150數據挖掘---關聯規則3)I2∧I5

I1Confidence=2/2=100%4)I1

I2∧I5Confidence=2/6=33%5)I2

I1∧I5Confidence=2/7=29%6)I5

I1∧I2Confidence=2/2=100%若最小可信度閾值minconf為70%，則輸出的關聯規則為2),3),6)

151十二、FP-tree的關聯規則挖掘算法基于FP-tree的關聯規則挖掘算法Apriori算法的缺點可能產生大量的候選集。例如，如果有一萬個頻繁1項集，則Apriori算需要產生10M個候選2項集，并累計和檢查它們的頻繁性；為發現長度為100的頻繁模式，它必須產生多達10３０個候選。需要重復的掃描數據庫，候選集檢查是一個很大的集合。152數據挖掘---關聯規則FP-tree頻繁