第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 社會(huì)網(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 序列模式挖掘 序列模式則是分析購(gòu)物序列中物品之間的關(guān)聯(lián)。- 例如，“買了電腦后一段時(shí)間內(nèi)顧客會(huì)購(gòu)買打印機(jī)”，這表達(dá)了先后兩次購(gòu)買的物品之間的關(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 序列模式的定義 一個(gè)序列（Sequence）s是若干個(gè)項(xiàng)集的有序列表，表示為s= ，其中sj是一個(gè)項(xiàng)集。 sj 又稱為序列 的一個(gè)元素（Element），表示為(x1x2xm) ，其中xj是一個(gè)項(xiàng)。 當(dāng)一個(gè)元素只包含一個(gè)項(xiàng)時(shí)，小括號(hào)可省略。一個(gè)序列中所包含的所有項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度，含有k個(gè)項(xiàng)的序列稱為k-序列。 對(duì)s中的每個(gè)元素按順序進(jìn)行編號(hào)，元素的編號(hào)稱為元素號(hào)（Element ID，簡(jiǎn)稱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的超序列。 例如，是一個(gè)6-序列。、都是序列的子序列，但不是。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析

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

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

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

8、提出。 它利用了支持度的反單調(diào)特性，即一個(gè)頻繁序列模式的任意一個(gè)子序列也一定是頻繁的，或者反過來說，一個(gè)非頻繁序列模式的任意一個(gè)超序列一定是非頻繁的。SPADE算法將序列數(shù)據(jù)庫(kù)中的序列進(jìn)行變換，改為用序列號(hào)和元素號(hào)來表示每個(gè)項(xiàng)，這種表達(dá)方式稱為縱向ID列表。對(duì)于表13.1中的序列數(shù)據(jù)庫(kù)，對(duì)應(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ù)庫(kù)SD轉(zhuǎn)化為縱向ID列表，如下表所示。 表中，每個(gè)項(xiàng)各對(duì)應(yīng)一個(gè)ID列表，ID列表中每一行的內(nèi)容為（SID, EID），SID是序列號(hào)，EID是元素號(hào)。 Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 11第2步找所有的頻繁2-序列。 把每個(gè)頻繁項(xiàng)的ID列表掃描進(jìn)內(nèi)存，然后對(duì)其進(jìn)行縱向到橫向的轉(zhuǎn)換（如表13.5所示），使得只有當(dāng)兩個(gè)項(xiàng)擁有相同的SI

10、D時(shí)才會(huì)被配對(duì)組合。 在此例中可以得到的候選2-序列包括：，。 SID(項(xiàng)，項(xiàng)，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ù)其長(zhǎng)度為1的前綴序列，前綴序列相同的序列作為一類，這樣分解為不同的類。 本例中是3類：- 前綴為的一類包括，。-

11、 前綴為的一類包括和。 - 前綴為的一類包括，和。Principles and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 13第4步序列的順序連接 對(duì)于每?jī)蓚€(gè)擁有相同的長(zhǎng)度為(k-1)的前綴的頻繁k-序列，進(jìn)行順序連接。每次順序連接最多可產(chǎn)生三類(k+1)-序列以及這些序列的ID列表。 序列和的順序連接產(chǎn)生三個(gè)候選的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)勢(shì)：- 第一，對(duì)ID列表進(jìn)行順序連接比較簡(jiǎn)單快捷，而且隨著頻繁序列的長(zhǎng)度增長(zhǎng)，ID列表的規(guī)模會(huì)減?。? 第二，通過分解操作，產(chǎn)生候選序列這一代價(jià)較大的過程被限制在較小的子類中；- 第三，由于只有3次對(duì)數(shù)據(jù)庫(kù)的遍歷，輸入/輸出的代價(jià)較低。 但，SPADE仍然需要產(chǎn)生相當(dāng)數(shù)量的候選序列，尤其是當(dāng)序列數(shù)據(jù)庫(kù)規(guī)模很大、序列模式可能很長(zhǎng)的情況。Principles and Application

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

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

15、inciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 17社會(huì)網(wǎng)絡(luò)有向圖示例 圖中結(jié)點(diǎn)代表用戶，邊代表用戶之間的關(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é)點(diǎn)的度來衡量結(jié)點(diǎn)的重要性。 一個(gè)結(jié)點(diǎn)

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

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

18、中結(jié)點(diǎn)個(gè)數(shù)；d(k, j)指的是從結(jié)點(diǎn)k到結(jié)點(diǎn)j的最短路徑的長(zhǎng)度（即路徑中邊的個(gè)數(shù)）。例如，從vb到vc的最短路徑是vbvc，長(zhǎng)度為1.CC k( )=n-1d k,j()jV,jkPrinciples and Applications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 21特征向量中心度 特征向量中心度將一個(gè)結(jié)點(diǎn)的鄰居的重要性考慮在內(nèi)。它將圖的鄰接矩陣的最大特征根對(duì)應(yīng)的特征向量中的每個(gè)值作為對(duì)應(yīng)結(jié)點(diǎn)的重要性度量，即存在一個(gè)非零向量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可以看作是特征向量中心度的一個(gè)變體，它由Google 創(chuàng)始人sergey Brin 和Lawrence Page提出，用于衡量web 頁面的權(quán)威性。它基于以下3點(diǎn)假設(shè)：- 如果一個(gè)頁面被很多其他頁面所指向，則這個(gè)頁面可能是重要的。- 如果一個(gè)頁面被重要的頁面所指向，則這個(gè)頁面可能是重要的。- 一個(gè)頁面的重要性均分傳播到它指向的頁面中

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

21、plications of Business IntelligenceChap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 24PageRank計(jì)算（2） 權(quán)威度的定義是遞歸的，因此可以進(jìn)行迭代計(jì)算：初始情況下,每個(gè)結(jié)點(diǎn)的權(quán)威度為1/n,即R0(j)=1/n。 相應(yīng)地，設(shè)R代表權(quán)威度列矢量，可以利用矩陣運(yù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ù)挖掘 實(shí)際應(yīng)用中，有些數(shù)據(jù)是實(shí)時(shí)、動(dòng)態(tài)產(chǎn)生的，每個(gè)數(shù)據(jù)項(xiàng)到達(dá)的順序未知，長(zhǎng)度可能是無限的。例如，提交給搜索引擎的查詢、股票交易、電信記錄、自動(dòng)取款機(jī)交易記錄、零售商品交易記錄也屬于數(shù)據(jù)流。 由于速度快，數(shù)量大，現(xiàn)有存儲(chǔ)設(shè)備通常無法保存數(shù)據(jù)流的所有歷史信息，如果要實(shí)時(shí)發(fā)現(xiàn)隱藏在數(shù)據(jù)流中的某些知識(shí)，需要設(shè)計(jì)高效的挖掘算法，以便對(duì)數(shù)據(jù)流讀取一次或幾次就發(fā)現(xiàn)所需要的知識(shí)。 傳統(tǒng)數(shù)據(jù)挖掘技術(shù)很難直接應(yīng)用于

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

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

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

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

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

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

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

30、hap 13：復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法 35一個(gè)多關(guān)系的金融數(shù)據(jù)庫(kù) 數(shù)據(jù)庫(kù)中存放了賬戶信息（account表）、客戶信息（client表）、人口統(tǒng)計(jì)信息（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

42、 p, foil-gain(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 t

43、he target relation 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-idtypedis