1、Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 1Introduction to商务智能方法与应用第13章 复杂数据的商务智能分析方法 Lecture 13: Analyzing Complex Data in BIPrinciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 2主要内容 13.1 序列模式挖掘- 13.1.1 序列模式的定义 - 13.1.2 序列模式挖掘算法 13.2 社会网络分析- 13.
2、2.1 中心度分析- 13.2.2 链接分析 13.3 数据流数据挖掘 13.4 多关系数据挖掘Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 313.1 序列模式挖掘 序列模式则是分析购物序列中物品之间的关联。- 例如，“买了电脑后一段时间内顾客会购买打印机”，这表达了先后两次购买的物品之间的关联。 序列模式挖掘算法主要有：AprioriAll、AprioriSome、GSP、SPADE、LAPIN-SPAM、FreeSpan 和PrefixSpan 等。 频繁闭合序列发现算法CloSpan。
3、Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 413.1.1 序列模式的定义 一个序列（Sequence）s是若干个项集的有序列表，表示为s= ，其中sj是一个项集。 sj 又称为序列 的一个元素（Element），表示为(x1x2xm) ，其中xj是一个项。 当一个元素只包含一个项时，小括号可省略。一个序列中所包含的所有项的个数称为序列的长度，含有k个项的序列称为k-序列。 对s中的每个元素按顺序进行编号，元素的编号称为元素号（Element ID，简称EID）。Principles and
4、 Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 5子序列超序列的定义 已知序列 sa=，序列sb=，mn，若存在整数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：复杂数据的商务智能分析
5、方法 6前缀序列、后缀序列 已知序列 sa=，序列sb=，nm ，sa称为 sb 的前缀序列（或简称前缀），当且仅当：1）sa的前n-1个元素分别与sa的前n-1个元素对应相等，即对于任意 ，都有 ai=bi；2）an bn ；3）按字母顺序，集合(bnan) 中的所有项都在 an中的所有项之后。若 sa是 sb的前缀，则 =称为 sb相对于前缀 sa的后缀序列（或简称后缀），其中 bn=bnan。 例如，、都是序列的前缀， 是序列相对于前缀的后缀。 Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方
6、法 7序列数据库、频繁序列 一个序列数据库SD由若干个序列构成，每个序列有一个唯一的序列号SID（Sequence ID）。 给定序列数据库SD，一个序列 （又称序列模式）的支持度，记为sup() ，是指SD中所有包含的序列的个数。若的支持度不小于用户指定的最小支持度，则称是一个频繁序列。 给定序列数据库SD以及最小支持度minsup，序列模式挖掘问题就是要找到SD中的所有满足最小支持度的频繁序列。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 8序列数据库的举例 SID序列序列123 SD由3
7、个序列构成，有a、b、c、d、e共5个项。第1个序列有4个元素，分别为(a)、(bc)、(b)和(dc)，EID分别为1至4。设最小支持度minsup = 2。 序列出现在第1个和第2个序列中，则sup() = 2，满足minsup，所以该序列模式是频繁的。但由于在第1个和第2个序列中，还包含序列模式，是的超序列，且支持度也是2，因此序列模式不是一个闭合序列。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 913.1.2 序列模式挖掘算法SPADE 由Mohammed J. Zaki于2001年
8、提出。 它利用了支持度的反单调特性，即一个频繁序列模式的任意一个子序列也一定是频繁的，或者反过来说，一个非频繁序列模式的任意一个超序列一定是非频繁的。SPADE算法将序列数据库中的序列进行变换，改为用序列号和元素号来表示每个项，这种表达方式称为纵向ID列表。对于表13.1中的序列数据库，对应的纵向ID列表如表13.4所示。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 10第1步构造纵向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步是将序列数据库SD转化为纵向ID列表，如下表所示。 表中，每个项各对应一个ID列表，ID列表中每一行的内容为（SID, EID），SID是序列号，EID是元素号。 Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 11第2步找所有的频繁2-序列。 把每个频繁项的ID列表扫描进内存，然后对其进行纵向到横向的转换（如表13.5所示），使得只有当两个项拥有相同的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：复杂数据的商务智能分析方法 12第3步分解 把所有的频繁2-序列，根据其长度为1的前缀序列，前缀序列相同的序列作为一类，这样分解为不同的类。 本例中是3类：- 前缀为的一类包括，。-
11、 前缀为的一类包括和。 - 前缀为的一类包括，和。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 13第4步序列的顺序连接 对于每两个拥有相同的长度为(k-1)的前缀的频繁k-序列，进行顺序连接。每次顺序连接最多可产生三类(k+1)-序列以及这些序列的ID列表。 序列和的顺序连接产生三个候选的3-序列(如图)： ，其中非频繁。 序列和的顺序连接产生的是，其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：复杂数据的商务智能分析方法 14SPADE 算法小结 具有以下优势：- 第一，对ID列表进行顺序连接比较简单快捷，而且随着频繁序列的长度增长，ID列表的规模会减小；- 第二，通过分解操作，产生候选序列这一代价较大的过程被限制在较小的子类中；- 第三，由于只有3次对数据库的遍历，输入/输出的代价较低。 但，SPADE仍然需要产生相当数量的候选序列，尤其是当序列数据库规模很大、序列模式可能很长的情况。Principles and Application
13、s of Business IntelligenceChap 13：复杂数据的商务智能分析方法 1513.2 社会网络分析 人类社会中个人或组织之间存在各种各样的社会关系，由个人或组织及其之间的关系构成的网络称为社会网络（social network）。 社会网络分析（social network analysis）是对社会网络的结构和属性进行分析，以发现其中的局部或全局特点，发现其中有影响力的个人或组织，发现网络的动态变化规律等。 社会网络分析是一个多学科交叉研究领域，涉及社会学、计算机、心理学、经济、数学等多种学科。 本节重点介绍中心度分析以及链接分析技术。Principles and A
14、pplications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 1613.2.1 中心度分析 中心度分析可用于识别网络中重要的个体或组织。 社会网络中心度度量有很多，典型的包括：- 度中心度（degree centrality）度量；- 中间中心度(Betweenness Centrality)；- 接近中心度（Closeness Centrality）；- 特征向量中心度(eigenvector centrality)- 等。 社会网络通常利用图G（V，E）表示，其中V是结点的集合，每个结点代表一个用户，可以是个体或组织；E是边的集合。Pr
15、inciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 17社会网络有向图示例 图中结点代表用户，边代表用户之间的关注关系，其中：- 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：复杂数据的商务智能分析方法 18度中心度 根据结点的度来衡量结点的重要性。 一个结点
16、如果与很多其他结点有关系，某种程度上说明它重要。- 无向图中一个结点k的度中心度，记为DC(k)，等于一个结点的度，即DC(k)=deg(k)；- 有向图中一个结点k的度中心度，可以定义为入度中心度和出度中心度。 图13.2中，结点vb的入度中心度为1，出度中心度为3.Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 19中间中心度 衡量一个用户在一个网络中对于最大化信息传播的重要性。 中间中心度高的用户往往起到一个信息传播桥梁的作用。一个结点k的中间中心度，记为BC(k)，计算公式如下： 其中i
17、和j是图中不同于结点k的任意两个结点；(i, k, j)指的是从结点i到结点j的最短路径中经过结点k的路径个数，而(i, j)指的是从结点i到结点j的最短路径的个数。BC k( )= i,k,j() i,j()jViV,ijkPrinciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 20接近中心度 度量一个结点与图中其他结点的联系紧密程度，衡量的是信息从一个结点向其它节点的传播速度。它是通过最短路径的长度来衡量的，对于无向图其计算公式如下： (13-2) 其中j是图中不同于结点k的任结点，n=|V|，是图
18、中结点个数；d(k, j)指的是从结点k到结点j的最短路径的长度（即路径中边的个数）。例如，从vb到vc的最短路径是vbvc，长度为1.CC k( )=n-1d k,j()jV,jkPrinciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 21特征向量中心度 特征向量中心度将一个结点的邻居的重要性考虑在内。它将图的邻接矩阵的最大特征根对应的特征向量中的每个值作为对应结点的重要性度量，即存在一个非零向量x使得： Ax=x （13-3） 其中，A是图G的邻接矩阵，是A的特征根。va vb vc vd veva
19、vbvcvdve0101000111000000000000100邻接矩阵Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 2213.2.2 链接分析 PageRank可以看作是特征向量中心度的一个变体，它由Google 创始人sergey Brin 和Lawrence Page提出，用于衡量web 页面的权威性。它基于以下3点假设：- 如果一个页面被很多其他页面所指向，则这个页面可能是重要的。- 如果一个页面被重要的页面所指向，则这个页面可能是重要的。- 一个页面的重要性均分传播到它指向的页面中
20、。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 23PageRank计算（1） 给定图G(V, E)，|V|=n，设M是该图转移矩阵T的转置矩阵，Mkj，即M中第k行第j列的元素，其取值分为两种情况：- 若结点j和k之间存在j指向k的边，则Mkj=1/|O(j)|, 其中|O(j)|代表结点j的出度。- 若两个结点之间不存在这种边，则Mkj=0。R(j)代表结点j的权威度。 根据这3个假设，任一个点的权威度可以如下计算：R(j)=R(k)|O(k)|kI(j)Principles and Ap
21、plications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 24PageRank计算（2） 权威度的定义是递归的，因此可以进行迭代计算：初始情况下,每个结点的权威度为1/n,即R0(j)=1/n。 相应地，设R代表权威度列矢量，可以利用矩阵运算如下： Ri = M Ri-1Ri(j)=Ri-1(k)|O(k)|kI(j)Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 25示例 图G 图G的转移矩阵MABCD A B C DM=ABCD 000
22、120001211000000Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 2613.3 数据流数据挖掘 实际应用中，有些数据是实时、动态产生的，每个数据项到达的顺序未知，长度可能是无限的。例如，提交给搜索引擎的查询、股票交易、电信记录、自动取款机交易记录、零售商品交易记录也属于数据流。 由于速度快，数量大，现有存储设备通常无法保存数据流的所有历史信息，如果要实时发现隐藏在数据流中的某些知识，需要设计高效的挖掘算法，以便对数据流读取一次或几次就发现所需要的知识。 传统数据挖掘技术很难直接应用于
23、数据流挖掘。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 27引入几个符号定义 设S表示输入数据流：S=。称S为长度为N的数据流。设I表示数据流中不同数据项的集合，I=a1, a2, a3 an， 即eiI。 设Fi表示集合I中项ai在S中的真实出现频率，fi表示采用一定方法记录的ai的近似频率。 从数据流S中挖掘频繁项的任务为，设S的当前长度为N，给定相对频率阈值(0,1)，要求输出S中所有出现频率不小于N的数据项。Principles and Applications of Busines
24、s IntelligenceChap 13：复杂数据的商务智能分析方法 28流数据挖掘的近似模型 给定相对频率阈值(0,1)和错误率(0,)，在数据流S停止之前的任意时刻，输出的数据项满足如下两个条件：(1) 所有输出数据项都要满足FifiFi+N；(2) 所有输出数据项都要满足Fi(-)N，并且所有FiN的数据项都被输出。 满足这两个条件的数据项称为缺陷频繁项。 上述条件中，条件(1)保证了输出数据项的估计频率不会偏离真实频率太多，而条件(2)保证了输出数据项在允许的错误范围内都是频繁的，并且真正频繁的数据项不会被漏掉。Principles and Applications of Busin
25、ess IntelligenceChap 13：复杂数据的商务智能分析方法 29Space Saving算法(1) 由Agrawal和Abbadi提出； 给定错误率(0,)，该算法设置m个计数器，且m=1/，每个计数器的内容为(e, f, d)，其中e是数据项，f为e的近似频率，d为近似频率f与真实频率F之间的最大差值，即误差。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 30Space Saving算法(2) 对于数据流S中出现的每个元素e按照如下过程记录每个数据项的出现频率。- 如果当前计
26、数器中存在e的计数器，将计数器的f值增1；- 如果当前计数器中不存在e的计数器，但是当前的计数器个数小于m，则新增计数器，令其取值为(e，1，0)；- 如果当前计数器中不存在e的计数器，且当前的计数器个数等于m，则找到f值最小的计数器，设该计数器记录的信息为(em, fm, dm)将其改为记录当前数据项e，令计数器其取值为(e, fm+1, fm)，其中fm和dm是这个计数器原来记录的数据项的相应的近似频率和误差。 当用户发出查询满足的频繁的数据项时，输出计数器记录的满足f N的所有数据项。Principles and Applications of Business Intelligence
27、Chap 13：复杂数据的商务智能分析方法 31示例（1） 假设当前数据流S为S=，共有3个计数器，其监控各个元素出现频率的过程如下。 前6个元素出现之后，计数器的内容如下表所示。元素元素ABC近似频率f321误差d000表13.6 数据流计数器Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 32示例（2） 第7个元素D出现之后，选择当前监控元素C的计数器监控D，修改其3部分内容的取值，近似频率增1，此时计数器的内容如表13.7所示。 第8个元素B出现之后，B正被监控，只需将其近似频率增1。元素
28、元素ABD近似频率f322误差d001表13.7 数据流计数器元素元素ABD近似频率f332误差d001表13.8 数据流计数器Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 33示例（3） 第9个元素C出现之后，从已有的计数器中找出一个来监控它，选择当前监控元素D的计数器，修改其3部分内容的取值后如下表所示。 第8个元素B出现之后，B正被监控，只需将其近似频率增1。 元素元素ABC近似频率f333误差d002表13.9 数据流计数器元素元素BAC近似频率f433误差d002表13.10 数据流
29、计数器Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 3413.4 多关系数据挖掘 企业运营过程中收集、积累的数据绝大多数存储在信息系统的数据库中。 最常用的数据库是关系数据库，由多个关系构成。每个关系对应一个表。 数据仓库中的数据也多数是由关系数据库管理系统进行存储和管理。 商务智能的实际应用中需要进行分析的数据通常是存储在多个表中。这种存储方式可以使得数据的冗余低，避免数据的不一致性。 Principles and Applications of Business IntelligenceC
30、hap 13：复杂数据的商务智能分析方法 35一个多关系的金融数据库 数据库中存放了账户信息（account表）、客户信息（client表）、人口统计信息（district表）、关联的信用卡信息（card表）、贷款信息（loan表）以及有关的交易信息（trans表和order表）。表disp表达了表account和表client之间的联系。Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 36An Example: Loan ApplicationsApply for loanApprove or
31、 not?Ask the backend databasePrinciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 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：复杂数据的商务智能分析方法 38Rule-based ClassificationEver bought a houseLive in ChicagoApprove!Just apply for a credit cardReject Applica
34、ntApplicantPrinciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 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：复杂数据的商务智能分析方法 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：复杂数据的商务智能分析方法 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：复杂数据的商务智能分析方法 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：复杂数据的商务智能分析方法 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：复杂数据的商务智能分析方法 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 B
44、usiness IntelligenceChap 13：复杂数据的商务智能分析方法 48Rule Generation: Exampledistrict-idfrequencydateAccountaccount-idaccount-iddateamountdurationLoanloan-idpaymentaccount-idbank-toaccount-toamountOrderorder-idtypedisp-idtypeissue-dateCardcard-idaccount-idclient-idDispositiondisp-idbirth-dategenderdistrict-i
45、dClientclient-iddist-nameregion#people#lt-500Districtdistrict-id#lt-2000#lt-10000#gt-10000#cityratio-urbanavg-salaryunemploy95unemploy96den-enter#crime95#crime96account-iddatetypeoperationTransactiontrans-idamountbalancesymbolTarget relationFirst predicateSecond predicateRange of Search Principles a
46、nd Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 49Look-one-ahead in Rule Generation Two types of relations: Entity and Relationship Often cannot find useful predicates on relations of relationshipTarget RelationnSolution of CrossMine:nWhen propagating IDs to a relation of relationship,
47、 propagate one more step to next relation of entity.No good predicatePrinciples and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 50Negative Tuple Sampling A rule covers some positive examples Positive examples are removed after covered After generating many rules, there are much less p
48、ositive examples than negative ones+Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 51Negative Tuple Sampling (cont.) When there are much more negative examples than positive ones- Cannot build good rules (low support)- Still time consuming (large number of negative examples) Make sampling on negative examples- Improve efficiency without affecting rule quality+Principles and Applications of Business IntelligenceChap 13：复杂数据的商务智能分析方法 52
