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

第13章

復(fù)雜數(shù)據(jù)的商務(wù)智能分析方法

Lecture13:Analyzing

Complex

DatainBI主要內(nèi)容13.1序列模式挖掘13.1.1序列模式的定義

13.1.2序列模式挖掘算法

13.2社會網(wǎng)絡(luò)分析13.2.1中心度分析13.2.2鏈接分析

13.3數(shù)據(jù)流數(shù)據(jù)挖掘13.4多關(guān)系數(shù)據(jù)挖掘13.1序列模式挖掘序列模式則是分析購物序列中物品之間的關(guān)聯(lián)。例如，“買了電腦后一段時間內(nèi)顧客會購買打印機”，這表達了先后兩次購買的物品之間的關(guān)聯(lián)。序列模式挖掘算法主要有：AprioriAll、AprioriSome、GSP、SPADE、LAPIN-SPAM、FreeSpan

和PrefixSpan

等。頻繁閉合序列發(fā)現(xiàn)算法CloSpan。13.1.1序列模式的定義

一個序列（Sequence）s是若干個項集的有序列表，表示為s=<s1s2…sn>，其中sj是一個項集。

sj

又稱為序列

的一個元素（Element），表示為(x1x2…xm)，其中xj是一個項。

當一個元素只包含一個項時，小括號可省略。一個序列中所包含的所有項的個數(shù)稱為序列的長度，含有k個項的序列稱為k-序列。對s中的每個元素按順序進行編號，元素的編號稱為元素號（ElementID，簡稱EID）。子序列超序列的定義已知序列

sa=<a1a2…an>，序列sb=<b1b2…bm>，m

n，若存在整數(shù)i1<i2<…<in

使得a1

bi1,a2

bi2,…,an

bin，則稱

sb包含sa，或

sa被

sb包含，記為

sa

sb

（若

sa≠

sb，記為

sa

sb），稱

sa為

sb的子序列，sb

稱為

sa的超序列。

例如，<a(ac)(ad)e>是一個6-序列。<a>、<ac>都是序列<a(ac)(ad)e>的子序列，但<a(cd)>不是。前綴序列、后綴序列已知序列

sa=<a1a2…an>，序列sb=<b1b2…bm>，n≤m

，sa稱為sb

的前綴序列（或簡稱前綴），當且僅當：1）sa的前n-1個元素分別與sa的前n-1個元素對應(yīng)相等，即對于任意

，都有

ai=bi；2）an

bn

；3）按字母順序，集合(bn?an)中的所有項都在an中的所有項之后。若sa是sb的前綴，則

β=<bn’bn+1…bm>稱為sb相對于前綴

sa的后綴序列（或簡稱后綴），其中

bn’=bn?an。例如，<a>、<aa>、<a(ac)>都是序列<a(ac)(ad)e>的前綴，<(ad)e>是序列<a(ac)(ad)e>相對于前綴<a(ac)>的后綴。

序列數(shù)據(jù)庫、頻繁序列一個序列數(shù)據(jù)庫SD由若干個序列構(gòu)成，每個序列有一個唯一的序列號SID（SequenceID）。給定序列數(shù)據(jù)庫SD，一個序列

α（又稱序列模式）的支持度，記為sup(α)，是指SD中所有包含α的序列的個數(shù)。若α的支持度不小于用戶指定的最小支持度，則稱α是一個頻繁序列。給定序列數(shù)據(jù)庫SD以及最小支持度minsup，序列模式挖掘問題就是要找到SD中的所有滿足最小支持度的頻繁序列。序列數(shù)據(jù)庫的舉例

SID序列1<a(bc)b(cd)>2<a(bcd)b>3<(cd)eac>SD由3個序列構(gòu)成，有a、b、c、d、e共5個項。第1個序列有4個元素，分別為(a)、(bc)、(b)和(dc)，EID分別為1至4。設(shè)最小支持度minsup=2。序列<a(bc)>出現(xiàn)在第1個和第2個序列中，則sup(<a(bc)>)=2，滿足minsup，所以該序列模式是頻繁的。但由于在第1個和第2個序列中，還包含序列模式<a(bc)b>，是<a(bc)>的超序列，且支持度也是2，因此序列模式<a(bc)>不是一個閉合序列。13.1.2序列模式挖掘算法SPADE由MohammedJ.Zaki于2001年提出。它利用了支持度的反單調(diào)特性，即一個頻繁序列模式的任意一個子序列也一定是頻繁的，或者反過來說，一個非頻繁序列模式的任意一個超序列一定是非頻繁的。SPADE算法將序列數(shù)據(jù)庫中的序列進行變換，改為用序列號和元素號來表示每個項，這種表達方式稱為縱向ID列表。對于表13.1中的序列數(shù)據(jù)庫，對應(yīng)的縱向ID列表如表13.4所示。第1步—構(gòu)造縱向ID列表a(SID,EID)b(SID,EID)c(SID,EID)d(SID,EID)e(SID,EID)1,12,13,3

1,21,32,22,3

1,21,42,23,13,41,42,23,1

3,2算法的第1步是將序列數(shù)據(jù)庫SD轉(zhuǎn)化為縱向ID列表，如下表所示。表中，每個項各對應(yīng)一個ID列表，ID列表中每一行的內(nèi)容為（SID,EID），SID是序列號，EID是元素號。

第2步—找所有的頻繁2-序列。把每個頻繁項的ID列表掃描進內(nèi)存，然后對其進行縱向到橫向的轉(zhuǎn)換（如表13.5所示），使得只有當兩個項擁有相同的SID時才會被配對組合。在此例中可以得到的候選2-序列包括：<ab>，<ac>，<ad>，<bb>，<bd>，<cb>，<cd>，<cc>，<ca>，<db>，<(bc)>，<(cd)>，<(bd)>。

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)第3步—分解把所有的頻繁2-序列，根據(jù)其長度為1的前綴序列，前綴序列相同的序列作為一類，這樣分解為不同的類。本例中是3類：前綴為<a>的一類包括<ab>，<ac>，<ad>。前綴為<b>的一類包括<bb>和<(bc)>。前綴為<c>的一類包括<cc>，<cb>和<(cd)>。第4步—序列的順序連接

對于每兩個擁有相同的長度為(k-1)的前綴的頻繁k-序列，進行順序連接。每次順序連接最多可產(chǎn)生三類(k+1)-序列以及這些序列的ID列表。序列<ab>和<ac>的順序連接產(chǎn)生三個候選的3-序列(如圖)：<abc>，<acb>，<a(bc)>，其中<abc>非頻繁。序列<ab>和<ab>的順序連接產(chǎn)生的是<abb>，其ID列表包括（1，3）和（2，3）。ab1,

21,

32,

22,

3a(bc)1,

22,

2ac1,

21,

42,

23,

4acb1,

32,

3abc1,

4SPADE

算法小結(jié)具有以下優(yōu)勢：第一，對ID列表進行順序連接比較簡單快捷，而且隨著頻繁序列的長度增長，ID列表的規(guī)模會減?。坏诙?，通過分解操作，產(chǎn)生候選序列這一代價較大的過程被限制在較小的子類中；第三，由于只有3次對數(shù)據(jù)庫的遍歷，輸入/輸出的代價較低。但，SPADE仍然需要產(chǎn)生相當數(shù)量的候選序列，尤其是當序列數(shù)據(jù)庫規(guī)模很大、序列模式可能很長的情況。13.2社會網(wǎng)絡(luò)分析人類社會中個人或組織之間存在各種各樣的社會關(guān)系，由個人或組織及其之間的關(guān)系構(gòu)成的網(wǎng)絡(luò)稱為社會網(wǎng)絡(luò)（socialnetwork）。社會網(wǎng)絡(luò)分析（socialnetworkanalysis）是對社會網(wǎng)絡(luò)的結(jié)構(gòu)和屬性進行分析，以發(fā)現(xiàn)其中的局部或全局特點，發(fā)現(xiàn)其中有影響力的個人或組織，發(fā)現(xiàn)網(wǎng)絡(luò)的動態(tài)變化規(guī)律等。社會網(wǎng)絡(luò)分析是一個多學科交叉研究領(lǐng)域，涉及社會學、計算機、心理學、經(jīng)濟、數(shù)學等多種學科。本節(jié)重點介紹中心度分析以及鏈接分析技術(shù)。13.2.1中心度分析

中心度分析可用于識別網(wǎng)絡(luò)中重要的個體或組織。社會網(wǎng)絡(luò)中心度度量有很多，典型的包括：度中心度（degreecentrality）度量；中間中心度(BetweennessCentrality)；接近中心度（ClosenessCentrality）；特征向量中心度(eigenvectorcentrality)…等。社會網(wǎng)絡(luò)通常利用圖G（V，E）表示，其中V是結(jié)點的集合，每個結(jié)點代表一個用戶，可以是個體或組織；E是邊的集合。社會網(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)}。vavbvevcvd度中心度根據(jù)結(jié)點的度來衡量結(jié)點的重要性。一個結(jié)點如果與很多其他結(jié)點有關(guān)系，某種程度上說明它重要。無向圖中一個結(jié)點k的度中心度，記為DC(k)，等于一個結(jié)點的度，即DC(k)=deg(k)；有向圖中一個結(jié)點k的度中心度，可以定義為入度中心度和出度中心度。圖13.2中，結(jié)點vb的入度中心度為1，出度中心度為3.中間中心度衡量一個用戶在一個網(wǎng)絡(luò)中對于最大化信息傳播的重要性。中間中心度高的用戶往往起到一個信息傳播橋梁的作用。一個結(jié)點k的中間中心度，記為BC(k)，計算公式如下：其中i和j是圖中不同于結(jié)點k的任意兩個結(jié)點；

(i,k,j)指的是從結(jié)點i到結(jié)點j的最短路徑中經(jīng)過結(jié)點k的路徑個數(shù)，而

(i,j)指的是從結(jié)點i到結(jié)點j的最短路徑的個數(shù)。接近中心度度量一個結(jié)點與圖中其他結(jié)點的聯(lián)系緊密程度，衡量的是信息從一個結(jié)點向其它節(jié)點的傳播速度。它是通過最短路徑的長度來衡量的，對于無向圖其計算公式如下：

(13-2)其中j是圖中不同于結(jié)點k的任結(jié)點，n=|V|，是圖中結(jié)點個數(shù)；d(k,j)指的是從結(jié)點k到結(jié)點j的最短路徑的長度（即路徑中邊的個數(shù)）。例如，從vb到vc的最短路徑是vbvc，長度為1.特征向量中心度特征向量中心度將一個結(jié)點的鄰居的重要性考慮在內(nèi)。它將圖的鄰接矩陣的最大特征根對應(yīng)的特征向量中的每個值作為對應(yīng)結(jié)點的重要性度量，即存在一個非零向量x使得：

Ax=λx

（13-3）

其中，A是圖G的鄰接矩陣，

是A的特征根。鄰接矩陣13.2.2鏈接分析

PageRank可以看作是特征向量中心度的一個變體，它由Google創(chuàng)始人sergeyBrin和LawrencePage提出，用于衡量web頁面的權(quán)威性。它基于以下3點假設(shè)：如果一個頁面被很多其他頁面所指向，則這個頁面可能是重要的。如果一個頁面被重要的頁面所指向，則這個頁面可能是重要的。一個頁面的重要性均分傳播到它指向的頁面中。PageRank計算（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)威度可以如下計算：PageRank計算（2）權(quán)威度的定義是遞歸的，因此可以進行迭代計算：初始情況下,每個結(jié)點的權(quán)威度為1/n,即R0(j)=1/n。相應(yīng)地，設(shè)R代表權(quán)威度列矢量，可以利用矩陣運算如下：

Ri=M

Ri-1示例圖G圖G的轉(zhuǎn)移矩陣MABCD13.3數(shù)據(jù)流數(shù)據(jù)挖掘?qū)嶋H應(yīng)用中，有些數(shù)據(jù)是實時、動態(tài)產(chǎn)生的，每個數(shù)據(jù)項到達的順序未知，長度可能是無限的。例如，提交給搜索引擎的查詢、股票交易、電信記錄、自動取款機交易記錄、零售商品交易記錄也屬于數(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)用于數(shù)據(jù)流挖掘。引入幾個符號定義設(shè)S表示輸入數(shù)據(jù)流：S=<e1,e2,e3…eN>。稱S為長度為N的數(shù)據(jù)流。設(shè)I表示數(shù)據(jù)流中不同數(shù)據(jù)項的集合，I={a1,a2,a3…an}，

即ei

I。設(shè)Fi表示集合I中項ai在S中的真實出現(xiàn)頻率，fi表示采用一定方法記錄的ai的近似頻率。從數(shù)據(jù)流S中挖掘頻繁項的任務(wù)為，設(shè)S的當前長度為N，給定相對頻率閾值φ∈(0,1)，要求輸出S中所有出現(xiàn)頻率不小于φN的數(shù)據(jù)項。流數(shù)據(jù)挖掘的近似模型給定相對頻率閾值φ∈(0,1)和錯誤率ε∈(0,φ)，在數(shù)據(jù)流S停止之前的任意時刻，輸出的數(shù)據(jù)項滿足如下兩個條件：(1)所有輸出數(shù)據(jù)項都要滿足Fi≤fi≤Fi+εN；(2)所有輸出數(shù)據(jù)項都要滿足Fi≥(φ-ε)N，并且所有Fi≥φN的數(shù)據(jù)項都被輸出。滿足這兩個條件的數(shù)據(jù)項稱為ε缺陷頻繁項。上述條件中，條件(1)保證了輸出數(shù)據(jù)項的估計頻率不會偏離真實頻率太多，而條件(2)保證了輸出數(shù)據(jù)項在允許的錯誤范圍內(nèi)都是頻繁的，并且真正頻繁的數(shù)據(jù)項不會被漏掉。SpaceSaving算法(1)由Agrawal和Abbadi提出；給定錯誤率ε∈(0,φ)，該算法設(shè)置m個計數(shù)器，且m=1/ε，每個計數(shù)器的內(nèi)容為(e,f,d)，其中e是數(shù)據(jù)項，f為e的近似頻率，d為近似頻率f與真實頻率F之間的最大差值，即誤差。SpaceSaving算法(2)對于數(shù)據(jù)流S中出現(xiàn)的每個元素e按照如下過程記錄每個數(shù)據(jù)項的出現(xiàn)頻率。如果當前計數(shù)器中存在e的計數(shù)器，將計數(shù)器的f值增1；如果當前計數(shù)器中不存在e的計數(shù)器，但是當前的計數(shù)器個數(shù)小于m，則新增計數(shù)器，令其取值為(e，1，0)；如果當前計數(shù)器中不存在e的計數(shù)器，且當前的計數(shù)器個數(shù)等于m，則找到f值最小的計數(shù)器，設(shè)該計數(shù)器記錄的信息為(em,fm,dm)將其改為記錄當前數(shù)據(jù)項e，令計數(shù)器其取值為(e,fm+1,fm)，其中fm和dm是這個計數(shù)器原來記錄的數(shù)據(jù)項的相應(yīng)的近似頻率和誤差。當用戶發(fā)出查詢滿足φ的頻繁的數(shù)據(jù)項時，輸出計數(shù)器記錄的滿足f>φN的所有數(shù)據(jù)項。示例（1）假設(shè)當前數(shù)據(jù)流S為S=<ABACBADBCB>，共有3個計數(shù)器，其監(jiān)控各個元素出現(xiàn)頻率的過程如下。前6個元素出現(xiàn)之后，計數(shù)器的內(nèi)容如下表所示。元素ABC近似頻率f321誤差d000表13.6數(shù)據(jù)流計數(shù)器示例（2）第7個元素D出現(xiàn)之后，選擇當前監(jiān)控元素C的計數(shù)器監(jiān)控D，修改其3部分內(nèi)容的取值，近似頻率增1，此時計數(shù)器的內(nèi)容如表13.7所示。第8個元素B出現(xiàn)之后，B正被監(jiān)控，只需將其近似頻率增1。元素ABD近似頻率f322誤差d001表13.7數(shù)據(jù)流計數(shù)器元素ABD近似頻率f332誤差d001表13.8數(shù)據(jù)流計數(shù)器示例（3）第9個元素C出現(xiàn)之后，從已有的計數(shù)器中找出一個來監(jiān)控它，選擇當前監(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ù)流計數(shù)器13.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)進行存儲和管理。商務(wù)智能的實際應(yīng)用中需要進行分析的數(shù)據(jù)通常是存儲在多個表中。這種存儲方式可以使得數(shù)據(jù)的冗余低，避免數(shù)據(jù)的不一致性。

一個多關(guān)系的金融數(shù)據(jù)庫數(shù)據(jù)庫中存放了賬戶信息（account表）、客戶信息（client表）、人口統(tǒng)計信息（district表）、關(guān)聯(lián)的信用卡信息（card表）、貸款信息（loan表）以及有關(guān)的交易信息（trans表和order表）。表disp表達了表account和表client之間的聯(lián)系。AnExample:LoanApplicationsApplyforloanApproveornot?AskthebackenddatabaseTheBackendDatabaseTargetrelation:Eachtuplehasaclasslabel,indicatingwhetheraloanispaidontime.district-idfrequencydateAccountaccount-idaccount-iddateamountdurationLoanloan-idpaymentaccount-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#crime96account-iddatetypeoperationTransactiontrans-idamountbalancesymbolHowtomakedecisionstoloanapplications?Rule-basedClassificationEverboughtahouseLiveinChicagoApprove!JustapplyforacreditcardReject…ApplicantApplicantRuleGenerationApplicant#1Applicant#2Applicant#3Applicant#4LoanIDAccountIDAmountDurationDecision1124100012Yes2124400012Yes31081000024No4451200036NoAccountIDFrequencyOpendateDistrictID128monthly02/27/9661820108weekly09/23/956182045monthly12/09/946180167weekly01/01/9561822LoanApplicationsAccountsOrdersDistrictsOtherrelationsSearchforgoodpredicatesacrossmultiplerelationsPreviousApproachesInductiveLogicProgramming(ILP)TobuildaruleRepeatedlyfindthebestpredicateToevaluateapredicateonrelationR,firstjointargetrelationwithRNotscalablebecauseHugesearchspace(numerouscandidatepredicates)NotefficienttoevaluateeachpredicateToevaluateapredicate Loan(L,+):-Loan(L,A,?,?,?,?),Account(A,?,‘monthly’,?)

firstjoinloanrelationwithaccountrelationCrossMineismorescalableandmorethanonehundredtimesfasterondatasetswithreasonablesizesCrossMine:AnEfficientandAccurateMulti-relationalClassifierTuple-IDpropagation:anefficientandflexiblemethodforvirtuallyjoiningrelationsConfinetherulesearchprocessinpromisingdirectionsLook-one-ahead:amorepowerfulsearchstrategyNegativetuplesampling:improveefficiencywhilemaintainingaccuracyTupleIDPropagationLoanIDAccountIDAmountDurationDecision1124100012Yes2124400012Yes31081000024No4451200036No0+,0–0+,1–0+,1–

2+,0–

Labels1,202/27/93monthly124Null01/01/97weekly67412/09/96monthly45309/23/97weekly108PropagatedIDOpendateFrequencyAccountIDApplicant#1Applicant#2Applicant#3Applicant#4PropagatetupleIDsoftargetrelationtonon-targetrelationsVirtuallyjoinrelationstoavoidthehighcostofphysicaljoinsPossiblepredicates:Frequency=‘monthly’:2+,1–Opendate<01/01/95:2+,0–TupleIDPropagation(cont.)EfficientOnlypropagatethetupleIDsTimeandspaceusageislowFlexibleCanpropagateIDsamongnon-targetrelationsManysetsofIDscanbekeptononerelation,whicharepropagatedfromdifferentjoinpathsTargetRelationR1R2R3OverallProcedureSequentialcoveringalgorithm

while(enoughtargettuplesleft) generatearule removepositivetargettuplessatisfyingthisruleExamplescoveredbyRule3ExamplescoveredbyRule2ExamplescoveredbyRule1PositiveexamplesRuleGenerationTogeneratearulewhile(true) findthebestpredicatep

iffoil-gain(p)>thresholdthenaddptocurrentrule

elsebreakPositiveexamplesNegativeexamplesA3=1A3=1&&A1=2A3=1&&A1=2&&A8=5EvaluatingPredicatesAllpredicatesinarelationcanbeevaluatedbasedonpropagatedIDsUsefoil-gaintoevaluatepredicatesSupposecurrentruleisr.Forapredicatep,

foil-gain(p)=CategoricalAttributesComputefoil-gaindirectlyNumericalAttributesDiscretizewitheverypossiblevalueRuleGenerationStartfromthetargetrelationOnlythetargetrelationisactiveRepeatSearchinallactiverelationsSearchinallrelationsjoinabletoactiverelationsAddthebestpredicatetothecurrentruleSettheinvolvedrelationtoactiveUntilThebestpredicatedoesnothaveenoughgainCurrentruleistoolongRuleGeneration:Exampledistrict-idfrequencydateAccountaccount-idaccount-iddateamountduration