商務(wù)智能課件：第13章 復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法

1、Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 1Introduction to商務(wù)智能方法與應(yīng)用第13章 復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 Lecture 13: Analyzing Complex Data in BIPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 2主要內(nèi)容 13.1 序列模式挖掘- 13.1.1 序列模式的定義 - 13.1.2 序列模式挖掘算法 13.2 社會網(wǎng)絡(luò)分析- 13.

2、2.1 中心度分析- 13.2.2 鏈接分析 13.3 數(shù)據(jù)流數(shù)據(jù)挖掘 13.4 多關(guān)系數(shù)據(jù)挖掘Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 313.1 序列模式挖掘 序列模式則是分析購物序列中物品之間的關(guān)聯(lián)。- 例如，“買了電腦后一段時間內(nèi)顧客會購買打印機”，這表達(dá)了先后兩次購買的物品之間的關(guān)聯(lián)。 序列模式挖掘算法主要有：AprioriAll、AprioriSome、GSP、SPADE、LAPIN-SPAM、FreeSpan 和PrefixSpan 等。 頻繁閉合序列發(fā)現(xiàn)算法CloSpan。

3、Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 413.1.1 序列模式的定義 一個序列（Sequence）s是若干個項集的有序列表，表示為s= ，其中sj是一個項集。 sj 又稱為序列 的一個元素（Element），表示為(x1x2xm) ，其中xj是一個項。 當(dāng)一個元素只包含一個項時，小括號可省略。一個序列中所包含的所有項的個數(shù)稱為序列的長度，含有k個項的序列稱為k-序列。 對s中的每個元素按順序進(jìn)行編號，元素的編號稱為元素號（Element ID，簡稱EID）。Principles and

4、 Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 5子序列超序列的定義 已知序列 sa=，序列sb=，mn，若存在整數(shù)i1i2in 使得 a1bi1, a2 bi2, , an bin，則稱 sb包含sa，或 sa被 sb包含，記為 sa sb （若 sa sb，記為 sa sb），稱 sa為 sb的子序列，sb 稱為 sa的超序列。 例如，是一個6-序列。、都是序列的子序列，但不是。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析

5、方法 6前綴序列、后綴序列 已知序列 sa=，序列sb=，nm ，sa稱為 sb 的前綴序列（或簡稱前綴），當(dāng)且僅當(dāng)：1）sa的前n-1個元素分別與sa的前n-1個元素對應(yīng)相等，即對于任意 ，都有 ai=bi；2）an bn ；3）按字母順序，集合(bnan) 中的所有項都在 an中的所有項之后。若 sa是 sb的前綴，則 =稱為 sb相對于前綴 sa的后綴序列（或簡稱后綴），其中 bn=bnan。 例如，、都是序列的前綴， 是序列相對于前綴的后綴。 Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方

6、法 7序列數(shù)據(jù)庫、頻繁序列 一個序列數(shù)據(jù)庫SD由若干個序列構(gòu)成，每個序列有一個唯一的序列號SID（Sequence ID）。 給定序列數(shù)據(jù)庫SD，一個序列 （又稱序列模式）的支持度，記為sup() ，是指SD中所有包含的序列的個數(shù)。若的支持度不小于用戶指定的最小支持度，則稱是一個頻繁序列。 給定序列數(shù)據(jù)庫SD以及最小支持度minsup，序列模式挖掘問題就是要找到SD中的所有滿足最小支持度的頻繁序列。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 8序列數(shù)據(jù)庫的舉例 SID序列序列123 SD由3

7、個序列構(gòu)成，有a、b、c、d、e共5個項。第1個序列有4個元素，分別為(a)、(bc)、(b)和(dc)，EID分別為1至4。設(shè)最小支持度minsup = 2。 序列出現(xiàn)在第1個和第2個序列中，則sup() = 2，滿足minsup，所以該序列模式是頻繁的。但由于在第1個和第2個序列中，還包含序列模式，是的超序列，且支持度也是2，因此序列模式不是一個閉合序列。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 913.1.2 序列模式挖掘算法SPADE 由Mohammed J. Zaki于2001年

8、提出。 它利用了支持度的反單調(diào)特性，即一個頻繁序列模式的任意一個子序列也一定是頻繁的，或者反過來說，一個非頻繁序列模式的任意一個超序列一定是非頻繁的。SPADE算法將序列數(shù)據(jù)庫中的序列進(jìn)行變換，改為用序列號和元素號來表示每個項，這種表達(dá)方式稱為縱向ID列表。對于表13.1中的序列數(shù)據(jù)庫，對應(yīng)的縱向ID列表如表13.4所示。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 10第1步構(gòu)造縱向ID列表a(SID,EID)b(SID,EID)c(SID,EID)d(SID,EID)e(SID,EID)1

9、, 12, 13, 31, 21, 32, 22, 31, 21, 42, 23, 13, 41, 42, 23, 13, 2 算法的第1步是將序列數(shù)據(jù)庫SD轉(zhuǎn)化為縱向ID列表，如下表所示。 表中，每個項各對應(yīng)一個ID列表，ID列表中每一行的內(nèi)容為（SID, EID），SID是序列號，EID是元素號。 Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 11第2步找所有的頻繁2-序列。 把每個頻繁項的ID列表掃描進(jìn)內(nèi)存，然后對其進(jìn)行縱向到橫向的轉(zhuǎn)換（如表13.5所示），使得只有當(dāng)兩個項擁有相同的SI

10、D時才會被配對組合。 在此例中可以得到的候選2-序列包括：，。 SID(項，項，EID)1(a, 1) (b, 2) (b, 3) (c, 2) (c, 4) (d, 4)2(a, 1) (b, 2) (b, 3) (c, 2) (d, 2)3(a, 3) (c, 1) (c, 4) (d, 1)Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 12第3步分解 把所有的頻繁2-序列，根據(jù)其長度為1的前綴序列，前綴序列相同的序列作為一類，這樣分解為不同的類。 本例中是3類：- 前綴為的一類包括，。-

11、 前綴為的一類包括和。 - 前綴為的一類包括，和。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 13第4步序列的順序連接 對于每兩個擁有相同的長度為(k-1)的前綴的頻繁k-序列，進(jìn)行順序連接。每次順序連接最多可產(chǎn)生三類(k+1)-序列以及這些序列的ID列表。 序列和的順序連接產(chǎn)生三個候選的3-序列(如圖)： ，其中非頻繁。 序列和的順序連接產(chǎn)生的是，其ID列表包括（1，3）和（2，3）。ab1, 21, 32, 22, 3a(bc)1, 22, 2ac1, 21, 42, 23, 4acb1

12、, 32, 3abc1, 4Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 14SPADE 算法小結(jié) 具有以下優(yōu)勢：- 第一，對ID列表進(jìn)行順序連接比較簡單快捷，而且隨著頻繁序列的長度增長，ID列表的規(guī)模會減?。? 第二，通過分解操作，產(chǎn)生候選序列這一代價較大的過程被限制在較小的子類中；- 第三，由于只有3次對數(shù)據(jù)庫的遍歷，輸入/輸出的代價較低。 但，SPADE仍然需要產(chǎn)生相當(dāng)數(shù)量的候選序列，尤其是當(dāng)序列數(shù)據(jù)庫規(guī)模很大、序列模式可能很長的情況。Principles and Application

13、s of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 1513.2 社會網(wǎng)絡(luò)分析 人類社會中個人或組織之間存在各種各樣的社會關(guān)系，由個人或組織及其之間的關(guān)系構(gòu)成的網(wǎng)絡(luò)稱為社會網(wǎng)絡(luò)（social network）。 社會網(wǎng)絡(luò)分析（social network analysis）是對社會網(wǎng)絡(luò)的結(jié)構(gòu)和屬性進(jìn)行分析，以發(fā)現(xiàn)其中的局部或全局特點，發(fā)現(xiàn)其中有影響力的個人或組織，發(fā)現(xiàn)網(wǎng)絡(luò)的動態(tài)變化規(guī)律等。 社會網(wǎng)絡(luò)分析是一個多學(xué)科交叉研究領(lǐng)域，涉及社會學(xué)、計算機、心理學(xué)、經(jīng)濟、數(shù)學(xué)等多種學(xué)科。 本節(jié)重點介紹中心度分析以及鏈接分析技術(shù)。Principles and A

14、pplications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 1613.2.1 中心度分析 中心度分析可用于識別網(wǎng)絡(luò)中重要的個體或組織。 社會網(wǎng)絡(luò)中心度度量有很多，典型的包括：- 度中心度（degree centrality）度量；- 中間中心度(Betweenness Centrality)；- 接近中心度（Closeness Centrality）；- 特征向量中心度(eigenvector centrality)- 等。 社會網(wǎng)絡(luò)通常利用圖G（V，E）表示，其中V是結(jié)點的集合，每個結(jié)點代表一個用戶，可以是個體或組織；E是邊的集合。Pr

15、inciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 17社會網(wǎng)絡(luò)有向圖示例 圖中結(jié)點代表用戶，邊代表用戶之間的關(guān)注關(guān)系，其中：- V= va，vb，vc，vd，ve， - E=(va, vb)，(va, vd)，(vb, vc)，(vb, vd)，(vb, ve)，(ve, vc)。vavbvevcvdPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 18度中心度 根據(jù)結(jié)點的度來衡量結(jié)點的重要性。 一個結(jié)點

16、如果與很多其他結(jié)點有關(guān)系，某種程度上說明它重要。- 無向圖中一個結(jié)點k的度中心度，記為DC(k)，等于一個結(jié)點的度，即DC(k)=deg(k)；- 有向圖中一個結(jié)點k的度中心度，可以定義為入度中心度和出度中心度。 圖13.2中，結(jié)點vb的入度中心度為1，出度中心度為3.Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 19中間中心度 衡量一個用戶在一個網(wǎng)絡(luò)中對于最大化信息傳播的重要性。 中間中心度高的用戶往往起到一個信息傳播橋梁的作用。一個結(jié)點k的中間中心度，記為BC(k)，計算公式如下： 其中i

17、和j是圖中不同于結(jié)點k的任意兩個結(jié)點；(i, k, j)指的是從結(jié)點i到結(jié)點j的最短路徑中經(jīng)過結(jié)點k的路徑個數(shù)，而(i, j)指的是從結(jié)點i到結(jié)點j的最短路徑的個數(shù)。BC k( )= i,k,j() i,j()jViV,ijkPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 20接近中心度 度量一個結(jié)點與圖中其他結(jié)點的聯(lián)系緊密程度，衡量的是信息從一個結(jié)點向其它節(jié)點的傳播速度。它是通過最短路徑的長度來衡量的，對于無向圖其計算公式如下： (13-2) 其中j是圖中不同于結(jié)點k的任結(jié)點，n=|V|，是圖

18、中結(jié)點個數(shù)；d(k, j)指的是從結(jié)點k到結(jié)點j的最短路徑的長度（即路徑中邊的個數(shù)）。例如，從vb到vc的最短路徑是vbvc，長度為1.CC k( )=n-1d k,j()jV,jkPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 21特征向量中心度 特征向量中心度將一個結(jié)點的鄰居的重要性考慮在內(nèi)。它將圖的鄰接矩陣的最大特征根對應(yīng)的特征向量中的每個值作為對應(yīng)結(jié)點的重要性度量，即存在一個非零向量x使得： Ax=x （13-3） 其中，A是圖G的鄰接矩陣，是A的特征根。va vb vc vd veva

19、vbvcvdve0101000111000000000000100鄰接矩陣Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 2213.2.2 鏈接分析 PageRank可以看作是特征向量中心度的一個變體，它由Google 創(chuàng)始人sergey Brin 和Lawrence Page提出，用于衡量web 頁面的權(quán)威性。它基于以下3點假設(shè)：- 如果一個頁面被很多其他頁面所指向，則這個頁面可能是重要的。- 如果一個頁面被重要的頁面所指向，則這個頁面可能是重要的。- 一個頁面的重要性均分傳播到它指向的頁面中

20、。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 23PageRank計算（1） 給定圖G(V, E)，|V|=n，設(shè)M是該圖轉(zhuǎn)移矩陣T的轉(zhuǎn)置矩陣，Mkj，即M中第k行第j列的元素，其取值分為兩種情況：- 若結(jié)點j和k之間存在j指向k的邊，則Mkj=1/|O(j)|, 其中|O(j)|代表結(jié)點j的出度。- 若兩個結(jié)點之間不存在這種邊，則Mkj=0。R(j)代表結(jié)點j的權(quán)威度。 根據(jù)這3個假設(shè)，任一個點的權(quán)威度可以如下計算：R(j)=R(k)|O(k)|kI(j)Principles and Ap

21、plications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 24PageRank計算（2） 權(quán)威度的定義是遞歸的，因此可以進(jìn)行迭代計算：初始情況下,每個結(jié)點的權(quán)威度為1/n,即R0(j)=1/n。 相應(yīng)地，設(shè)R代表權(quán)威度列矢量，可以利用矩陣運算如下： Ri = M Ri-1Ri(j)=Ri-1(k)|O(k)|kI(j)Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 25示例 圖G 圖G的轉(zhuǎn)移矩陣MABCD A B C DM=ABCD 000

22、120001211000000Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 2613.3 數(shù)據(jù)流數(shù)據(jù)挖掘 實際應(yīng)用中，有些數(shù)據(jù)是實時、動態(tài)產(chǎn)生的，每個數(shù)據(jù)項到達(dá)的順序未知，長度可能是無限的。例如，提交給搜索引擎的查詢、股票交易、電信記錄、自動取款機交易記錄、零售商品交易記錄也屬于數(shù)據(jù)流。 由于速度快，數(shù)量大，現(xiàn)有存儲設(shè)備通常無法保存數(shù)據(jù)流的所有歷史信息，如果要實時發(fā)現(xiàn)隱藏在數(shù)據(jù)流中的某些知識，需要設(shè)計高效的挖掘算法，以便對數(shù)據(jù)流讀取一次或幾次就發(fā)現(xiàn)所需要的知識。 傳統(tǒng)數(shù)據(jù)挖掘技術(shù)很難直接應(yīng)用于

23、數(shù)據(jù)流挖掘。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 27引入幾個符號定義 設(shè)S表示輸入數(shù)據(jù)流：S=。稱S為長度為N的數(shù)據(jù)流。設(shè)I表示數(shù)據(jù)流中不同數(shù)據(jù)項的集合，I=a1, a2, a3 an， 即eiI。 設(shè)Fi表示集合I中項ai在S中的真實出現(xiàn)頻率，fi表示采用一定方法記錄的ai的近似頻率。 從數(shù)據(jù)流S中挖掘頻繁項的任務(wù)為，設(shè)S的當(dāng)前長度為N，給定相對頻率閾值(0,1)，要求輸出S中所有出現(xiàn)頻率不小于N的數(shù)據(jù)項。Principles and Applications of Busines

24、s IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 28流數(shù)據(jù)挖掘的近似模型 給定相對頻率閾值(0,1)和錯誤率(0,)，在數(shù)據(jù)流S停止之前的任意時刻，輸出的數(shù)據(jù)項滿足如下兩個條件：(1) 所有輸出數(shù)據(jù)項都要滿足FifiFi+N；(2) 所有輸出數(shù)據(jù)項都要滿足Fi(-)N，并且所有FiN的數(shù)據(jù)項都被輸出。 滿足這兩個條件的數(shù)據(jù)項稱為缺陷頻繁項。 上述條件中，條件(1)保證了輸出數(shù)據(jù)項的估計頻率不會偏離真實頻率太多，而條件(2)保證了輸出數(shù)據(jù)項在允許的錯誤范圍內(nèi)都是頻繁的，并且真正頻繁的數(shù)據(jù)項不會被漏掉。Principles and Applications of Busin

25、ess IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 29Space Saving算法(1) 由Agrawal和Abbadi提出； 給定錯誤率(0,)，該算法設(shè)置m個計數(shù)器，且m=1/，每個計數(shù)器的內(nèi)容為(e, f, d)，其中e是數(shù)據(jù)項，f為e的近似頻率，d為近似頻率f與真實頻率F之間的最大差值，即誤差。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 30Space Saving算法(2) 對于數(shù)據(jù)流S中出現(xiàn)的每個元素e按照如下過程記錄每個數(shù)據(jù)項的出現(xiàn)頻率。- 如果當(dāng)前計

26、數(shù)器中存在e的計數(shù)器，將計數(shù)器的f值增1；- 如果當(dāng)前計數(shù)器中不存在e的計數(shù)器，但是當(dāng)前的計數(shù)器個數(shù)小于m，則新增計數(shù)器，令其取值為(e，1，0)；- 如果當(dāng)前計數(shù)器中不存在e的計數(shù)器，且當(dāng)前的計數(shù)器個數(shù)等于m，則找到f值最小的計數(shù)器，設(shè)該計數(shù)器記錄的信息為(em, fm, dm)將其改為記錄當(dāng)前數(shù)據(jù)項e，令計數(shù)器其取值為(e, fm+1, fm)，其中fm和dm是這個計數(shù)器原來記錄的數(shù)據(jù)項的相應(yīng)的近似頻率和誤差。 當(dāng)用戶發(fā)出查詢滿足的頻繁的數(shù)據(jù)項時，輸出計數(shù)器記錄的滿足f N的所有數(shù)據(jù)項。Principles and Applications of Business Intelligence

27、Chap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 31示例（1） 假設(shè)當(dāng)前數(shù)據(jù)流S為S=，共有3個計數(shù)器，其監(jiān)控各個元素出現(xiàn)頻率的過程如下。 前6個元素出現(xiàn)之后，計數(shù)器的內(nèi)容如下表所示。元素元素ABC近似頻率f321誤差d000表13.6 數(shù)據(jù)流計數(shù)器Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 32示例（2） 第7個元素D出現(xiàn)之后，選擇當(dāng)前監(jiān)控元素C的計數(shù)器監(jiān)控D，修改其3部分內(nèi)容的取值，近似頻率增1，此時計數(shù)器的內(nèi)容如表13.7所示。 第8個元素B出現(xiàn)之后，B正被監(jiān)控，只需將其近似頻率增1。元素

28、元素ABD近似頻率f322誤差d001表13.7 數(shù)據(jù)流計數(shù)器元素元素ABD近似頻率f332誤差d001表13.8 數(shù)據(jù)流計數(shù)器Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 33示例（3） 第9個元素C出現(xiàn)之后，從已有的計數(shù)器中找出一個來監(jiān)控它，選擇當(dāng)前監(jiān)控元素D的計數(shù)器，修改其3部分內(nèi)容的取值后如下表所示。 第8個元素B出現(xiàn)之后，B正被監(jiān)控，只需將其近似頻率增1。 元素元素ABC近似頻率f333誤差d002表13.9 數(shù)據(jù)流計數(shù)器元素元素BAC近似頻率f433誤差d002表13.10 數(shù)據(jù)流

29、計數(shù)器Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 3413.4 多關(guān)系數(shù)據(jù)挖掘 企業(yè)運營過程中收集、積累的數(shù)據(jù)絕大多數(shù)存儲在信息系統(tǒng)的數(shù)據(jù)庫中。 最常用的數(shù)據(jù)庫是關(guān)系數(shù)據(jù)庫，由多個關(guān)系構(gòu)成。每個關(guān)系對應(yīng)一個表。 數(shù)據(jù)倉庫中的數(shù)據(jù)也多數(shù)是由關(guān)系數(shù)據(jù)庫管理系統(tǒng)進(jìn)行存儲和管理。 商務(wù)智能的實際應(yīng)用中需要進(jìn)行分析的數(shù)據(jù)通常是存儲在多個表中。這種存儲方式可以使得數(shù)據(jù)的冗余低，避免數(shù)據(jù)的不一致性。 Principles and Applications of Business IntelligenceC

30、hap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 35一個多關(guān)系的金融數(shù)據(jù)庫 數(shù)據(jù)庫中存放了賬戶信息（account表）、客戶信息（client表）、人口統(tǒng)計信息（district表）、關(guān)聯(lián)的信用卡信息（card表）、貸款信息（loan表）以及有關(guān)的交易信息（trans表和order表）。表disp表達(dá)了表account和表client之間的聯(lián)系。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 36An Example: Loan ApplicationsApply for loanApprove or

31、 not?Ask the backend databasePrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 37The Backend DatabaseTarget relation: Each tuple has a class label, indicating whether a loan is paid on time.district-idfrequencydateAccountaccount-idaccount-iddateamountdurationLoanloan-idpaymen

32、taccount-idbank-toaccount-toamountOrderorder-idtypedisp-idtypeissue-dateCardcard-idaccount-idclient-idDispositiondisp-idbirth-dategenderdistrict-idClientclient-iddist-nameregion#people#lt-500Districtdistrict-id#lt-2000#lt-10000#gt-10000#cityratio-urbanavg-salaryunemploy95unemploy96den-enter#crime95#

33、crime96account-iddatetypeoperationTransactiontrans-idamountbalancesymbolHow to make decisions to loan applications?Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 38Rule-based ClassificationEver bought a houseLive in ChicagoApprove!Just apply for a credit cardReject Applica

34、ntApplicantPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 39Rule GenerationApplicant #1Applicant #2Applicant #3Applicant #4Loan IDAccount IDAmountDurationDecision1124100012Yes2124400012Yes31081000024No4451200036NoAccount IDFrequencyOpen dateDistrict ID128monthly02/27/96618

35、20108weekly09/23/956182045monthly12/09/946180167weekly01/01/9561822Loan ApplicationsAccountsOrdersDistrictsOther relationsnSearch for good predicates across multiple relationsPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 40Previous Approaches Inductive Logic Programming (

36、ILP)- To build a ruleRepeatedly find the best predicateTo evaluate a predicate on relation R, first join target relation with R- Not scalable becauseHuge search space (numerous candidate predicates)Not efficient to evaluate each predicate To evaluate a predicate Loan(L, +) :- Loan (L, A,?,?,?,?), Ac

37、count(A,?, monthly,?) first join loan relation with account relationCrossMine is more scalable and more than one hundred times faster on datasets with reasonable sizesPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 41CrossMine: An Efficient and Accurate Multi-relational Cla

38、ssifier Tuple-ID propagation: an efficient and flexible method for virtually joining relations Confine the rule search process in promising directions Look-one-ahead: a more powerful search strategy Negative tuple sampling: improve efficiency while maintaining accuracyPrinciples and Applications of

39、Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 42Tuple ID PropagationLoan IDAccount IDAmountDurationDecision1124100012Yes2124400012Yes31081000024No4451200036No0+, 00+, 10+, 1 2+, 0 Labels1, 202/27/93monthly124Null01/01/97weekly67412/09/96monthly45309/23/97weekly108Propagated IDOpen dateFrequencyAccount

40、IDApplicant #1Applicant #2Applicant #3Applicant #4nPropagate tuple IDs of target relation to non-target relationsnVirtually join relations to avoid the high cost of physical joinsPossible predicates:Frequency=monthly: 2 +, 1 Open date threshold then add p to current ruleelse breakPositiveexamplesNeg

41、ativeexamplesA3=1A3=1&A1=2A3=1&A1=2&A8=5Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 46Evaluating Predicates All predicates in a relation can be evaluated based on propagated IDs Use foil-gain to evaluate predicates- Suppose current rule is r. For a predicate p, foil-gai

42、n(p) = Categorical Attributes- Compute foil-gain directly Numerical Attributes- Discretize with every possible value()( )( )( )()()()-prNprPprPrNrPrPprPloglogPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 47Rule Generation Start from the target relation- Only the target re

43、lation is active Repeat- Search in all active relations- Search in all relations joinable to active relations- Add the best predicate to the current rule- Set the involved relation to active Until- The best predicate does not have enough gain- Current rule is too longPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 48Rule Generation: Exampledistrict-idfrequencydateAccountaccount-idaccount-iddateamountdurationLoanloan-idpaymentaccount-idbank-toaccount-toamountOrderorder-idtypedisp