一种新的工作流频繁模式挖掘算法研究

第36卷　第9期2009年9月计算机科学Comp uter Science Vol.36No.9Sep 2009

到稿日期:2008210214　返修日期:2008212225 本文受国家自然科学基金(60673160)资助。

高　昂(1981-),男,博士研究生,主要研究方向为工作流挖掘、电子商务、Web 服务等,E 2mail :gaoang318@https://www.doczj.com/doc/8d15995335.html, ;杨　扬(1955-),男,教授,博士生导师,主要研究方向为电子商务、图像处理、网格计算等;王玥薇(1980-),女,硕士研究生,讲师,主要研究方向为电子商务、网格计算等。

一种新的工作流频繁模式挖掘算法研究

高　昂1　杨　扬1　王玥薇1,2

(北京科技大学信息工程学院　北京100083)1　(公安海警高等专科学校　宁波315801)2

　

摘　要　为了提高工作流模型挖掘技术的准确性,提出了一种新的工作流频繁模式挖掘算法。首先,阐述了工作流模型依赖矩阵的定义,并利用工作流日志建立了依赖矩阵。然后采用活动间的依赖关系作为频繁项集,设计了一种基于依赖矩阵的频繁项集自动生成算法。最后对频繁项集进行处理,得到最终的工作流频繁模式。该算法能够处理活动间交叠关系和具有串、并行关系的工作流模型,因此更具优越性。关键词　工作流模型,矩阵,频繁模式挖掘中图法分类号　TP391 文献标识码　A

N ew Algorithm R esearch for Mining Workflow Frequent P attern

GAO Ang 1　YAN G Yang 1　WAN G Yue 2wei 1,2

(College of Information Engineering ,University of Science and Technology Beijing ,Beijing 100083,China )1

(Public Security Marine Police Academy ,Ningbo 315801,China )2

　

Abstract To improve mining accuracy of workflow models ,a new algorithm for mining workflow f requent pattern was proposed.Firstly ,the Workflow Model depend Matrix (WM )was defined ,and set up WM by using workflow logs.Se 2condly ,using the depend relation of activities as f requent itemsets ,an alogrithm was designed to automatically generate frequent itemsets based on WM.Finally ,got the workflow f requent pattern by disposing frequent itemsets.The algo 2rithm has advantage in disposing the interleaving relations between activities and workflow models with the serial or parallel relations.

K eyw ords Workflow model ,Matrix ,Frequent pattern mining

1　引言

传统的工作流建模需要投入大量的时间,一般由商业顾问和管理者完成,他们对模型的理解往往会影响模型的质

量[1]。与之相比,工作流管理系统日志中包含丰富的信息(包括商业流程中各个活动的执行过程),可以利用这些更为客观的信息建立工作流模型。从工作流的生命周期(模型设计阶段、模型实现阶段、模型运行和模型维护阶段)来看,传统的建模方法主要集中于前两个阶段,而工作流挖掘技术主要针对运行与维护阶段,并将这两个阶段产生的信息反馈于设计和实现阶段,为模型再设计提供信息。工作流挖掘技术既可作为商业智能的一部分,也可为商业流程分析提供支持。

本文通过扩展经典的Apriori 算法[2]作为新的工作流模型频繁模式挖掘方法,挖掘模型中的频繁模式。工作流频繁模式是体现活动间逻辑关系强弱的重要工具,利用工作流模型频繁模式能够在流程发生变化时及时地发现现有的模型变化及趋势,并量化活动间逻辑关系的强弱。在商务智能领域,利用频繁模式可以实时监控工作流管理系统运行,在关键的决策点可以提供后续活动走势预测、商业决策和风险预测等方面支持。与其他工作流模式挖掘方法相比,本算法以活动

间依赖关系为频繁模式项集,解决了其他算法不能处理的活动间交叠关系,能够处理具有串、并行关系的工作流模型,更具优越性。

2　基本概念

活动是工作流模型的基本组成单元,V =(a 1,a 2,…,a n )表示日志中所有活动的集合。实例是四元组(I ns N O ,a i ,S T ,

E T )的集合,其中I ns N O 为实例编号,a i ∈V ,S T 和E T 分别

为活动a i 的开始事件发生时间和结束事件发生时间。S 0表示日志中所有实例的集合。实例I 的活动集为A S (I )={a i :

(I ns N O ,a i ,S T ,E T )∈I}。假设工作流模型中不存在循环,

则任何实例I 都不存在重复活动。

定义1　实例集合S 上,活动a j 局部依赖于活动a i ,记

为a i πs a j ΖΠ实例I ∈S ,如果有a i ∈A S (I ),a j ∈A S (I )且活动a i 的结束时间E T i 早于活动a j 的开始时间S T j 同时成立。

两个活动如果仅在一部分实例集上依赖并不能保证依赖关系的正确性,只有当它们在整个日志实例集上依赖时才能保证这个依赖关系是正确的。

定义2　活动a j 全局依赖于活动a i ,记为a i πa j Ζ对于实

?

132?

例集合S,有a iπs a j(其中S={I:a i∈A S(I),a j∈A S(I),I∈S0})。

由定义1易知,依赖具有传递性,即实例集合S中如果有a iπs a k且a kπs a j]a iπs a j。从依赖的传递性可以得知,在建立的工作流模型中并不需要表示所有活动间的依赖关系,因为一部分依赖关系可以通过其他活动间的依赖关系传递表达。由此,在全局依赖的基础上提出了直接依赖的定义。

定义3　活动a j直接依赖于活动a i,a iπd a jΖa iπa j,且对于ΠI∈S,??a k,使a iπa k和a kπa j同时成立(其中令S′= {I:a i∈A S(I),a j∈A S(I),I∈S0},S为S′中所有具有相同的实例活动集的实例的集合)。

从直接依赖的定义可知,直接依赖关系首先是全局依赖关系,这样保证了依赖关系的正确性。其次考察定义3中实例集S的范围。由于具有不同活动集的实例间可能蕴涵着逻辑或关系,S的范围为日志S0中所有包含活动a i和a j且具有相同实例活动集的实例集合。这个定义将S0中所有包含a i和a j的活动分为多个子集。后续的算法将利用这一点分别挖掘每个子集中a i和a j间的直接依赖关系并汇总,得到活动间的逻辑或关系。显然,当活动a iπd a j时,在扩展有向图中应该存在一条有向边,由活动a i指向a j。

定义4　模式G=(V,F)为某实例I j的子集,称实例I 支持一个有向图表示的工作流模式P。如果模式G中的依赖关系在实例I中是成立的,记为GΘI。

定义5　日志中所有实例集合S0,对于工作流模式G的支持度P=|{I:I∈S0,GΘI}|/|S0|×100%,其中|S0|表示日志中的实例数。同时可得,对于实例集S′,有向图所表示的工作流模式G′在实例集S′上是频繁的,如果实例集S′中有对模式G′的支持度s≥最小支持度阈值P s。

定义6　ΠI i,I j∈实例集S,满足A S(I i)=A S(I j),则实例集S对应的依赖矩阵定义为v阶布尔矩阵D=(d ij),v= |DS(I)|,|DS(I)|为集合DS(I)的元素个数。其中if活动a iπs a j,d ij=1;else if a jπs a i,d ij=-1;else d ij=0。

3　频繁模式挖掘算法基本思想

Agrawal等人最早提出了串行模式挖掘方法,该方法事先定义阈值,利用Apriori算法挖掘串行实例中不小于阈值的极大串行序列作为串行模式,并且对算法进行了优化[3,4]。Mannila等人利用窗口方法的最终目的是找到序列的集合,集合中的每个序列都被足够多的窗口所包含到[5]。但是文献[6,7]中的挖掘方法只将每个活动作为一个原子事件,没有考虑每个活动从开始事件到结束事件之间的时间间隔,所以只能处理串行的工作流模式序列。

本文主要通过扩展经典的Apriori算法挖掘工作流频繁模式。Apriori算法中,频繁项集仅是一个事务中项的集合,没有顺序关系。但在工作流频繁模式挖掘算法中,活动间有先后顺序,而且存在并行结构,所以采用活动间依赖关系作为频繁项集和候选项集的项,即每个实例表示为形如d ij=n(n =1,0,-1)的依赖矩阵元素集合,通过函数Com pM at ri x2 Patterns计算频繁项集,再通过函数Com p Patterns得到最终的工作流频繁模式集合。此外,Apriori算法中对频繁项没有要求。但在工作流模型中,依赖矩阵D i包含活动集合A S (D i)中任意活动间的依赖关系,其表示的模型才具有意义,所以在工作流模式挖掘中,要求项集频繁且完整。

4　频繁模式挖掘过程

本文提出的工作流频繁模型挖掘过程可以分为4个步骤。下面以某公司处理客户投诉的工作流模型为例,详细解释模型挖掘过程。图1是以有向图表示的某公司处理客户投诉的过程模型。其中,活动a1为投诉登记;活动a2为邮寄调查表;活动a3为投诉评估,在投诉评估后,可以选择处理投诉或跳过处理;活动a4为处理调查表;活动a5为处理投诉;活动a6为检查结果

;活动a7为归档。

图1　某公司处理客户投诉过程模型

当公司接到投诉并进行登记后,处理调查表和评估投诉两个活动在逻辑上具有并行关系,在评估完成之后,可以选择处理投诉或跳过处理。

4.1　数据预处理

对日志中每一个实例I,算法关心的是活动集A S(I)中的每个活动开始事件和结束事件发生的先后顺序,而并非开始事件和结束事件的具体发生时间,所以首先将日志数据进行初步整理,得到每个实例的活动的开始事件和结束事件的时间序列。如果A S(I i)=A S(I j),且实例I i和I j中各个活动的开始事件和结束事件有相同的时间序列,则称实例I i和I j 是重复的。工作流日志中存在大量的重复实例,在数据预处理中过滤掉重复的实例,可以大大地减少后续步骤中处理的数据量。

对日志S0,在去掉重复实例后得到工作流实例集S,将其分为多个子集S1,S2,…,S n,满足ΠS i中如果I i∈S i,则ΠI j∈S i,都有A S(I i)=A S(I j),且S=S1∪S2∪S3∪…∪S n。

对于图1所示的工作流模型,将日志经过上述预处理后得到实例集S如下,其中a s i和a e i分别表示活动开始事件和活动结束事件。

I1=(a s1,a e1,a s2,a s3,a e2,a s4,a e3,a s5,a e4,a e5,a s6,a e6,a s7,a e7),

I2=(a s1,a e1,a s2,a s3,a e3,a s5,a e2,a s4,a e5,a s6,a e4,a e6,a s7,a e7),

I3=(a s1,a e1,a s3,a s2,a e3,a s6,a e2,a s4,a e4,a e6,a s7,a e7),

I4=(a s1,a e1,a s2,a s3,a e3,a s6,a e6,a e2,a s4,a e4,a s7,a e7),

I5=(a s1,a e1,a s2,a s3,a e3,a s5,a e5,a s6,a e2,a s4,a e6,a e4,a s7,a e7)。

S1={I1,I2,I5},S2={I3,I4}。

4.2　计算依赖矩阵

经过数据预处理之后得到实例集S1,S2,…,S n,对每一个实例集S i按照依赖矩阵定义,分别得到对应的依赖矩阵。上述处理客户投诉过程模型中的实例集S1,S2按照定义6可得依赖矩阵D1和D2。算法中采用活动间的依赖关系作为实例项,则可得1项候选集合C1={d ij=1∪d ij=0∪d ij=-1, a i,a j∈V,且i

?

2

3

2

?

D1=a1

a2

a3

a4

a5

a6

a7

0111111

-1001001

-1000111

-1-100001

-10-10011

-10-10-101

-1-1-1-1-1-10

D2=a1

a2

a3

a4

a6

a7

011111

-100101

-100111

-1-1-1001

-10-1001

-1-1-1-1-10

依赖矩阵都是沿对角线对称,所以可以将依赖矩阵简化为上三角矩阵,在后续的步骤中降低算法的复杂度。

D1=a1

a2

a3

a4

a5

a6

a7

111111

01001

0111

001

11

1

D2=a1

a2

a3

a4

a6

a7

11111

0101

111

01

1

4.3　计算矩阵频繁项集

利用Com pM at ri x Patterns函数计算矩阵频繁项集。C k 代表k项候选频繁集;L k代表k代项频繁集。首先计算所有频繁项集,但是这些频繁项集并不一定完整。然后去掉其中不完全的矩阵频繁项集,得到最终的频繁集。

Com pM at ri x Patterns(全体实例集合S0,1项频繁集合L1,阈值P s)

{

Max K=1;

f or(k=2;L k≠ ;k++)

{

由k-1项频繁集L k-1生成k项候选集C k;

for(矩阵D1,D2,…,D n)

{

for(k项候选集C k中每项C n)

{if(矩阵D i中存在k个元素值=C n中元素)∥找出矩阵D i支持的项c;

C1=C1∪C n;C n.count++;

}

L k={d ij∈C1|C n.count/|S0|×100%>P s};

If(L k≠ )Max K++;

}

for(k=Max K;k>1;k--)

{

for(L k中每一项C n)

{

if(d ij(d ij∈C n)组成的矩阵为上三角完全矩阵)

delete L k-1,L k-2,…,L i中C n的子项;

else delete C n;

}

}

Retrun L1,L2,…,L Max k;

}

上述依赖矩阵经函数Com pM at ri x Patterns处理后得到矩阵频繁项集L2={(D1′,D2′)},其中

D1′=

a1

a2

a4

a7

111

11

1,D2′=

a1

a3

a5

a6

111

11

4.4　生成频繁模式

利用Com Patterns函数将生成的频繁矩阵元素项集L1, L2,…,L Max k中的项生成以有向图表示的频繁模式。对于频繁矩阵元素项集L k,其中每个项C n中的矩阵元素集合{d ij: d ij∈C n}可以组成一个上三角矩阵D n,即对应活动集合A S (C n)的依赖矩阵。Com Patterns把活动集A S(S i)分为4个集合:FormerSet,CurS et,N ex tS et,L ef tSet。

Com p Patterns(De pend M at ri x:D n)

{

FormerSet=NextSet=tem p= ,CurSet=(活动a j:a j∈A S(S i)且a j不依赖于其他任何活动),L ef tSet=A S(S i)-CurSet;

while L ef tS et≠ {

for(CurSet中的每一个活动a j){

CurrentA ct=a j,N ex tSet=(活动a u:a u∈L ef tSet,且a u不依赖于其他任何L ef tS et中的活动);

for(N ex tS et中的每一个活动a u){

for(L ef tSet中的每一个活动a v≠a u){

if(活动a v依赖于活动a j)矩阵D i中令元素d jv=0;

}

}

tem p=tem p∪N ex tSet;N ex tS et= ;

}

FormerS et=FormerS et∪CurS et;CurS et=tem p;

L ef tS et=L ef tSet-CurSet;

}

}

由函数Com Patterns处理频繁依赖矩阵D1′,D2′可得包含直接依赖关系的矩阵D3′,D4′,如下所示:

D3′=

a1

a2

a4

a7

1

1

1,D4′=

a1

a3

a5

a6

1

11

(下转第251页)

图5给出了并行复算加速比在故障率不同的情况下对容错并行算法性能的影响。容错并行算法的期望执行时间随着并行复算加速比的增大而减小,加速比和效率随之而增大。故障率较高时,增大并行复算的加速比可以有效提高容错并行算法的性能。然而,故障率较低时,并行复算的加速比对容错并行算法性能的影响也较小。

结束语　传统的并行算法性能度量用于评估无故障时并行程序的性能。本文建立了考虑系统故障情况下的性能模型来预测容错并行算法的完成时间,以此为基础评估了程序段的运行时间、数据保存开销、故障率以及并行复算加速比等系统参数对容错并行算法性能的影响。程序段的选择是个优化设计问题,存在最优程序段运行时间;数据保存开销对容错并行算法的影响较大,它比并行复算加速比对容错并行算法性能的影响更大,数据保存开销越低,容错并行算法的性能越好;故障率越低,系统发生故障的概率越低,容错并行算法的性能越好;并行复算加速比的增大可以提高容错并行算法的性能,尤其是对于故障率较高以及程序段运行时间较长的容错并行算法,增大并行复算加速比可以有效提高容错并行算法的性能。

参考文献

[1]

Grama A ,Gupta A ,Karypis G ,et al .Introduction to Parallel Computing ,Second Edition[M ].Addison Wesley ,J anuary 2003[2]

Yang Xuejun ,Du Yunfei ,Wang Panfeng ,et al.F TPA :Suppor 2ting Fault Tolerant Parallel Computing Through Parallel Re 2computing[J ].IEEE Transactions on Parallel and Distributed

Systems (Accepted )[3]Duda A .The Effect s of Checkpointing on Program Execution Time[J ].Information Processing Letters ,1983,16:2212229[4]

Y oung J W.A First Order Approximation to t he Optimal Checkpoint Interval[J ].Comm.ACM ,1974,17(9):5302531[5]

K im J unSeong ,Lilja D J .Characterization of Communication Patterns in Message 2Passing Parallel Scientific Application Pro 2grams[C ]∥Proceedings of t he Second International Workshop on Network 2based Parallel Computing :Communication ,Archi 2tecture ,and Applications.J anuary 1998:2022216[6]

Vetter J https://www.doczj.com/doc/8d15995335.html,munication Characteristics of Large 2scale Scien 2tific Applications for Contemporary Cluster Architectures[C]∥International Parallel and Distributed Processing Symposium.2002[7]

Zamani R ,Af sahi https://www.doczj.com/doc/8d15995335.html,munication Characteristics of Message 2Passing Scientific and Engineering Applications [C ]∥Procee 2dings of t he 17t h IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS ’2005).Phoe 2nix ,AZ ,USA ,November 2005:6442649[8]

Amdahl G M.Validity of t he single 2processor approach to achie 2ving large scale computing capabilities [J ].A FIPS Conference Proceedings ,1967,4(30):4832485[9]

Gustaf son J.Reevaluating Amdahl ’s Law[J ].Communication of ACM ,1988,31(5):5322533

(上接第233页)

经过Com Patterns 函数处理的矩阵D n 包含了日志中所

有的活动间直接依赖关系,可以直接通过D n 生成频繁模式,由有向图G =(V ,F )表示,其中V =A S (C n )代表有向图的节点集合(a 1,a 2,…,a n );F 是有向图的边集。对于矩阵D n 元素d ij =1,则工作流模型中存在一条从有向边a i 指向a j ;反之,d ij =-1存在一条从有向边a j 指向a i 。

最后根据直接依赖矩阵D 3′,D ′4得到最终的工作流频繁模式,如图2所示

。

图2　最终工作流频繁模式

结束语　工作流频繁模式包含了丰富的信息,可以为流

程动态变化问题的解决提供基础。同时,可以为工作流管理系统中重要的商业决策、风险预测等提供支持,也为工作流模型优化提供依据。利用日志信息挖掘工作流频繁模式,是近年来新出现的研究领域。本文提出的算法与其他工作流模式挖掘方法相比,能够处理具有串、并行关系的工作流模式,更具优越性,在工作流模型中,活动间除串、并行关系外还存在循环关系。本算法在处理活动间并行循环关系时存在不足,不能完全处理循环关系,这是今后工作的主要方向。

参考文献

[1]范玉顺.工作流管理技术基础[M ].北京:清华大学出版社,

2001:20235

[2]

Agrawal R ,Imielinski T ,Swami A.Mining association rules be 2tween set s of items in large databases [C ]∥Proceedings of t he ACM SIGMOD International Conference Management of Date.Washington ,1993:2072216

[3]Agrawal R ,Srikant R.Mining sequential patterns[C]∥Procee 2dings of International Conference on Data Engineering.Taipei ,Taiwan ,1995:1352139

[4]Srikant R .Agrawal R .Mining sequential patterns :generaliza 2tions and performance improvement s [C ]∥Proceedings of t he 5t h International Conference on Extending Database Technology

(EDB T ).Avignon ,France ,1996:1172133[5]

Mannila H ,Toivonen H ,Verkamo A I.Discovering frequent epi 2sodes in sequences[C ]∥Proceedings of t he First International Conference on Knowledge Discovery and Data Mining.Avignon ,France ,1995:1942204[6]

Sadiq W ,Orlowska M E.Analyzing Process Models Using Graph Reduction Techniques [J ].Information Systems ,2000,25(2):1172134[7]

Sadiq S ,Orlowska M .On correctness issues in conceptual mode 2ling of workflows[C]∥Proceedings of t he 5t h Euopean Confe 2rence on Information Systems.Cork ,Ireland ,1997:19221

频繁项集挖掘的Apriori改进算法研究

１０００－５８６２（２０１１）０５－０４９８－０５ 频繁项集挖掘的Ａｐｒｉｏｒｉ改进算法研究 栗晓聪滕少华 广东工业大学计算机学院，广东广州５１０００６ 摘要：针对Ａｐｒｉｏｒｉ算法的不足，提出了一种新的优化算法—ＩＡｐｒｉｏｒｉ．该算法应用散列技术优化产生频繁－２项集，优化连接操作减少连接判断的次数，通过对候选项集编码来减少扫描数据库的次数，优化逻辑“与”运算减少不必要的“与”操作次数，缩短生成频繁项集的时间．ＩＡｐｒｉｏｒｉ算法仅需３次扫描数据库．研究结果表明，该算法具有快速、直观、节省内存等优点． Ａｐｒｉｏｒｉ算法；频繁项集；候选项集；ＩＡｐｒｉｏｒｉ算法 ＴＰ３１１Ａ ２０１１－０７－１２ 广东省自然科学基金（０６０２１４８４，　９１５１００９００１０００００７）和广州市越秀区科技计划（２００７－ＧＸ－０２３）资助项目． 滕少华（１９６２－），男，江西南昌人，教授，博士，主要从事协同工作、网络安全和数据挖掘方面的研究．

第５期

２０１１年

第５期

＠＠［１］王琳，滕少华，伍乃骐，等．基于协议分析的散列模式入侵检 测方法［Ｊ］．计算机工程与设计，２００６，２７（１）：　５３－５５．＠＠［２］颜跃进，李舟军，陈火旺，等．基于ＦＰ－Ｔｒｅｅ有效挖掘最大频 繁项集［Ｊ］．软件学报，２００５，１６（２）：　２１５－２２２． ＠＠［３］郭宇红，童云海，唐世渭，等．基于ＦＰ－Ｔｒｅｅ的反向频繁项集 挖掘［Ｊ］．软件学报，２００８，１９（２）：　３３８－３５０． ＠＠［４］　Ｈａｎ　Ｊｉａｗｅｉ，　Ｐｅｉ　Ｊｉａｎ，　Ｙｉｎ　Ｙｉｗｅｎ，　ｅｔ　ａｌ．　Ｍｉｎｉｎｇ　ｆｒｅｑｕｅｎｔ　ｍａｔｔｅｒｎｓ ｗｉｔｈｏｕｔ　ｃａｎｄｉｄａｔｅ　ｇｅｎｅｒａｔｉｏｎ　［Ｊ］．　Ｄａｔａ　Ｍｉｎｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒ，　２００４，　８（１）：　５３－８７． ＠＠［５］Ｊｉａｗｅｉ　Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ　Ｋａｍｂｅｒ．数据挖掘概念与技术［Ｍ］．范 明，孟小峰，译．北京：机械工业出版社，２００７：１６７－１６１．＠＠［６］　Ｗｕ　Ｘｉｎｇｄｏｎｇ，　Ｖｉｐｉｎ　Ｋｕｍａｒ，　Ｒｏｓｓ　Ｑｕｉｎｌａｎ　Ｊ．　Ｔｏｐ　１０　ａｌｇｏｒｉｔｈｍｓ　 ｉｎ　ｄａｔａ　ｍｉｎｉｎｇ　［Ｊ］．　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，　２００８，１４（１）：　１－３７． ＠＠［７］陈耿，朱玉全，杨鹤标，等．关联规则挖掘中若干关键技术的 研究［Ｊ］．计算机研究与发展，２００５，４２（１０）：　１７８５－１７８９．＠＠［８］徐章艳，刘美玲，张师超，等．Ａｐｒｉｏｒｉ算法的三种优化方法［Ｊ］． 计算机工程与应用，２００４，４０（３６）：　１９０－１９３． ＠＠［９］傅慧，邹海．基于待与项集的频繁项集挖掘算法的研究［Ｊ］． 计算机工程与设计，２００９，３０（１）：　１２９－１３１． ＠＠［１０］徐健辉．生成频繁项集的逻辑“与”运算算法［Ｊ］．计算机应用， ２００４，２４（１１）：　８８－９０． ＠＠［１１］俞燕燕，李绍滋．基于散列的关联规则ＡｐｒｉｏｒｉＴｉｄ改进算法［Ｊ］． 计算机工程，２００８，３４（５）：　６０－６２． ＠＠［１２］柴华昕，王勇．Ａｐｒｉｏｒｉ挖掘频繁项集算法的改进［Ｊ］．计算机 工程与应用，２００７，４３（２４）：　１５８－１６１． Ｔｈｅ　Ｒｅｓｅａｒｃｈ　ｏｎ　Ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　Ａｐｒｉｏｒｉ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ Ｍｉｎｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｉｔｅｍｓｅｔｓ　 ＬＩ　Ｘｉａｏ－ｃｏｎｇＴＥＮＧ　Ｓｈａｏ－ｈｕａ

流数据频繁模式挖掘算法汇总

频繁模式挖掘 常用的概念： 事务数据库： 时间ID： 项集(item set)： 重要算法： 1、A priori 主要思想就是从大小1开始遍历可能频繁集k，当满足V所有集合子集都在之前计算过的频繁集k中，且出现次数满足频繁要求，则V为k+1频繁集这样做有如下好处：如果一个集合是频繁集，那么它的所有子集都是频繁集； 如果一个集合不是频繁集，那么它的所有超集都不会是频繁集 缺点就是要多次扫描事务数据库 2、F P-growth 可以用来识别包含某个元素的最大频繁集。 FP-growth算法通过构造FP-tree来实现，FP-tree由频繁项集表和前缀树构成。 FP-tree的构建需要扫描两遍数据库， （1）第一遍对所有元素技术并降序排序，然后将数据库中每个事务里的元素按照这个顺序重新排序

（2）按照项头表的顺序逐渐插入元素 ··· （3）FP-tree的挖掘 得到了FP树和项头表以及节点链表，我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。 （1）先从F挖掘 通过它，我们很容易得到F的频繁2项集为{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,F:2}，{A:2,E:2,F:2},...还有一些频繁三项集，就不写了。当然一直递归下去，最大的频繁项集为频繁5项集，为{A:2,C:2,E:2,B:2,F:2}

《大数据时代下的数据挖掘》试题和答案与解析

《海量数据挖掘技术及工程实践》题目 一、单选题（共80题） 1)( D )的目的缩小数据的取值范围，使其更适合于数据挖掘算法的需要，并且能够得到 和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 2)某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖 掘的哪类问题？(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 3)以下两种描述分别对应哪两种对分类算法的评价标准？ (A) (a)警察抓小偷，描述警察抓的人中有多少个是小偷的标准。 (b)描述有多少比例的小偷给警察抓了的标准。 A. Precision,Recall B. Recall,Precision A. Precision,ROC D. Recall,ROC 4)将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务？(C) A. 频繁模式挖掘 B. 分类和预测 C. 数据预处理 D. 数据流挖掘 5)当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数 据相分离？(B) A. 分类 B. 聚类 C. 关联分析 D. 隐马尔可夫链 6)建立一个模型，通过这个模型根据已知的变量值来预测其他某个变量值属于数据挖掘的 哪一类任务？(C) A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 7)下面哪种不属于数据预处理的方法？ (D) A.变量代换 B.离散化

C.聚集 D.估计遗漏值 8)假设12个销售价格记录组已经排序如下：5, 10, 11, 13, 15, 35, 50, 55, 72, 92, 204, 215 使用如下每种方法将它们划分成四个箱。等频（等深）划分时，15在第几个箱子内？ (B) A.第一个 B.第二个 C.第三个 D.第四个 9)下面哪个不属于数据的属性类型：(D) A.标称 B.序数 C.区间 D.相异 10)只有非零值才重要的二元属性被称作：( C ) A.计数属性 B.离散属性 C.非对称的二元属性 D.对称属性 11)以下哪种方法不属于特征选择的标准方法： (D) A.嵌入 B.过滤 C.包装 D.抽样 12)下面不属于创建新属性的相关方法的是： (B) A.特征提取 B.特征修改 C.映射数据到新的空间 D.特征构造 13)下面哪个属于映射数据到新的空间的方法？ (A) A.傅立叶变换 B.特征加权 C.渐进抽样 D.维归约 14)假设属性income的最大最小值分别是12000元和98000元。利用最大最小规范化的方 法将属性的值映射到0至1的范围内。对属性income的73600元将被转化为：(D) A.0.821 B.1.224 C.1.458 D.0.716 15)一所大学内的各年纪人数分别为：一年级200人，二年级160人，三年级130人，四年 级110人。则年级属性的众数是： (A) A.一年级 B.二年级 C.三年级 D.四年级

聚类、关联规则挖掘、图数据库

聚类 一、聚类的定义 聚类，属于一种非监督学习方法，它试图在无标签的数据集中发现其分布状况或模式。通常，我们认为同一聚类中的数据点比不同聚类的数据点具有更大的相似性。 二、传统的聚类算法的分类 1、基于划分的聚类算法 主要思想：基于划分的聚类算法通过构造一个迭代过程来优化目标函数，当优化到目标函数的最小值或极小值时，可以得到数据集的一些不相交的子集，通常认为此时得到的每个子集就是一个聚类。 典型方法： k-means算法 FCM算法。 2、层次聚类算法 主要思想：层次聚类方法使用一个距离矩阵作为输入，经过聚类后得到一个反映该数据集分布状况的聚类层次结构图。 层次聚类算法通常分为两种： 凝聚的层次聚类算法：它首先把每个数据点看作是一个聚类，然后以一种自底向上的方式通过不断地选择最近邻居聚类对的合并操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。 分类的层次聚类算法：它首先把所有的数据点看作是一个聚类，然后以一种以自顶向下的方式通过不断地选择最松散簇进行分裂操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。 典型方法： AGNES (AGglomerative NESting) BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) CURE (Clustering Using REpresentative) 3、基于密度的聚类算法 主要思想：基于密度的聚类算法试图通过稀疏区域来划分高密度区域以发现明显的聚类和孤立点，主要用于空间型数据的聚类。 典型方法： DBSCAN (Density-based Spatial Clustering of Application with Noise) OPTICS (Ordering Points to Identify the Clustering Structure) 4、基于网格的聚类算法 主要思想：基于网格的聚类算法是一种基于网格的具有多分辨率的聚类方法。它首先将数据集的分布空间划分为若干个规则网格(如超矩形单元)或灵活的网格(如任意形状的多

一种高效频繁子图挖掘算法.2007,18(10)_2469-2480

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/8d15995335.html, Journal of Software , Vol.18, No.10, October 2007, pp.2469?2480 https://www.doczj.com/doc/8d15995335.html, DOI: 10.1360/jos182469 Tel/Fax: +86-10-62562563 ? 2007 by Journal of Software . All rights reserved. 一种高效频繁子图挖掘算法 ? 李先通, 李建中+, 高 宏 (哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) An Efficient Frequent Subgraph Mining Algorithm LI Xian-Tong, LI Jiang-Zhong +, GAO Hong (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) + Corresponding author: Phn: +86-451-86415827, E-mail: lijzh@https://www.doczj.com/doc/8d15995335.html,, https://www.doczj.com/doc/8d15995335.html, Li XT, Li JZ, Gao H. An efficient frequent subgraph mining algorithm. Journal of Software , 2007,18(10): 2469?2480. https://www.doczj.com/doc/8d15995335.html,/1000-9825/18/2469.htm Abstract : With the successful development of frequent item set and frequent sequence mining, the technology of data mining is natural to extend its way to solve the problem of structural pattern mining —Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry, biology, computer networks, and World-Wide Web. In this paper we propose a new algorithm GraphGen for mining frequent subgraphs. GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm before, the complexity is O (n 3·2n ), n is the number of frequent edges in a graph dataset. The complexity of GraphGen is ???? ?????n n O n log 25.2, which is improved )log (n n O ? times than the best one. Experiment results prove this theoretical analysis. Key words : frequent pattern mining; subgraph isomorphism; subtree isomorphism; frequent subgraph; spanning tree 摘 要: 由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题——频繁子图挖掘.诸如化学、生物学、计算机网络和WWW 等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间 复杂性是O (n 3·2n ),其中,n 是图集中的频繁边数.提出的算法时间复杂性是???? ?????n n O n log 25.2,性能提高了)log (n n O ?倍. 实验结果也证实了这个理论结果. 关键词: 频繁模式挖掘;子图同构;子树同构;频繁子树;生成树 中图法分类号: TP311 文献标识码: A ? Supported by the National Natural Science Foundation of China under Grant No.60473075 (国家自然科学基金); the Key Program National Natural Science Foundation of China under Grant No.60533110 (国家自然基金重点项目); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University (NCET) under Grant No.NCET-05-0333 (国家教育部新世纪创新人才计划) Received 2006-09-08; Accepted 2006-11-14

一种基于频繁模式的时间序列分类框架

第32卷第2期电子与信息学报Vol.32No.2 2010年2月 Journal of Electronics & Information Technology Feb. 2010 一种基于频繁模式的时间序列分类框架 万里①③廖建新①②朱晓民①②倪萍①③ ①(北京邮电大学网络与交换技术国家重点实验室北京 100876) ②(东信北邮信息技术有限公司北京 100191) ③(卡耐基梅隆大学匹兹堡 15213) 摘要：如何提取和选择时间序列的特征是时间序列分类领域两个重要的问题。该文提出MNOE(Mining Non- Overlap Episode)算法计算时间序列中的非重叠频繁模式，并将其作为时间序列特征。基于这些非重叠频繁模式，该文提出EGMAMC(Episode Generated Mixed memory Aggregation Markov Chain)模型描述时间序列。根据似然比检验原理，从理论上推导出频繁模式在时间序列中出现的次数和EGMAMC模型是否能显著描述时间序列之间的关系；根据信息增益定义，选择能显著描述时间序列的频繁模式作为时间序列特征输入分类模型。在UCI (University of California Irvine)公共数据集和实际智能楼宇数据集上的实验表明，选择频繁模式作为特征进行分类的准确率、召回率和F-Measure均优于不选择频繁模式作为特征的分类结果。高效的计算和有效的选择非重叠频繁模式作为时间序列特征有助于提高时间序列分类模型的各项评价指标。 关键词：时间序列分类；频繁模式挖掘；智能楼宇 中图分类号：TP393 文献标识码：A 文章编号：1009-5896(2010)02-0261-06 DOI: 10.3724/SP.J.1146.2009.00135 A Frequent Pattern Based Time Series Classification Framework Wan Li①③Liao Jian-xin①②Zhu Xiao-min①②Ni Ping①③ ①(State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing 100876, China) ②(EBUPT Information Technology Co., Ltd, Beijing 100191, China) ③(Carnegie Mellon University, Pittsburgh, US 15213, USA) Abstract:How to extract and select features from time series are two important topics in time series classification. In this paper, a MNOE (Mining Non-Overlap Episode) algorithm is presented to find non-overlap frequent patterns in time series and these non-overlap frequent patterns are considered as features of the time series. Based on these non-overlap episodes, an EGMAMC (Episode Generated Mixed memory Aggregation Markov Chain) model is presented to describe time series. According to the principle of likelihood ratio test, the connection between the support of episode and whether EGMAMC could describe the time series significantly is induced. Based on the definition of information gain, significant frequent patterns are selected as the features of time series for classification. The experiments on UCI (University of California Irvine) datasets and smart building datasets demonstrate that the classification model trained with selecting significant frequent patterns as features outperforms the one trained without selecting them on precision, recall and F-Measure. The time series classification models can be improved by efficiently extracting and effectively selecting non-overlap frequent patterns as features of time series. Key words:Time series classification; Frequent pattern mining; Smart building 1引言 给定一个数据样本集合，每个数据样本包括： 2009-02-02收到，2009-09-03改回 国家杰出青年科学基金(60525110)，国家973 计划项目(2007CB307100，2007CB307103)和电子信息产业发展基金项目(基于3G的移动业务应用系统)资助课题 通信作者：万里 wanly@https://www.doczj.com/doc/8d15995335.html, 一个输入时间序列{()|{1,2,,}} i X t t T =∈ x"及其 离散的分类标签 s C，其中，()n t R ∈ x是一个n维向 量，称作t时刻发生的事件，{1,2,,} s C S ∈"。时间 序列分类的目标是预测新给出的时间序列 j X的类标签。时间序列分类技术在通信[1]、生物信息[2]、自动控制[3]等领域已有广泛应用，但通常情况下时间序列的长度不相等，即使所有待分类时间序列长度相

频繁子图模式挖掘

数据挖掘与商务智能读书报告Using Association Rules for Product Assortment

英文标题：gSpan: Graph-Based Substructure Pattern Mining 中文标题：频繁子图模式挖掘 文献来源：ICDM 2002 一、主要内容（2000～2500字）： （1）论文研究的问题概述 数据挖掘技术及其算法是目前国际上数据库和信息决策领域最前沿的研究方向之一,本文就数据挖掘中基于图结构的gSpan挖掘算法及其应用进行了研究。本文研究了频繁字图挖掘在图数据集的新方法，提出了一种新的算法gSpan，它在没有候选集的情况下发现了频繁子结构。gSpan在图中建立了一种新的字典序，和各图形映射到一个唯一的最小DFS代码作为它的规范的标签。基于这种字典顺序，gSpan采用深度优先的搜索策略高效的挖掘频繁连通子图。研究表明，gSpan大大优于以前的算法。 gSpan算法是图挖掘邻域的一个算法，而作为子图挖掘算法，又是其他图挖掘算法的基础，所以gSpan算法在图挖掘算法中还是非常重要的。gSpan算法在挖掘频繁子图的时候，用了和FP-grown中相似的原理，就是模式增长方法，也用到了最小支持度计数作为一个过滤条件。图算法在程序上比其他的算法更加的抽象，在实现时更加需要空间想象能力。 如果整个数据集图中可以容纳主存，gSpan可以直接应用，否则人们要首先执行基于图的数据投影仪，然后应用gSpan。gSpan是第一个在频繁子图挖掘中使用深度优先搜索的算法。本文介绍DFS字典序和最小DFS码这两种技术，它们形成一种新的规范的标识系统来支持DFS搜索。gSpan在一个步骤里结合了频繁子图的增长和检查，从而加速挖掘过程。 （2）论文研究的理论意义及其应用前景 频繁图挖掘是数据挖掘中一个非常广泛的应用。频繁图挖掘可以理解为从大量的图中挖掘出一些满足给定支持度的频繁图，同时算法需要保证这些频繁图不是重复的。gSpan是一个非常高效的算法，它利用dfs-code序列对搜索树进行编码，并且制定一系列比较规则，从而保证最后只得到序列“最小”的频繁图集合。 由于大部分图挖掘算法都需要利用频繁子图,频繁子图挖掘逐渐成为了数据挖掘领域中的热点研究内容。目前,很多高效的频繁子图挖掘算法已经被提出。其中,gSpan算法是目前公认的最好的频繁子图挖掘算法。然而,在化合物数据集上,还可以利用化合物的特殊结构进一步优化gSpan算法的性能。文献利用了化合物分子结构的对称性和原子类型分布的不均衡

频繁模式挖掘算法(Apriori)

实验一频繁模式挖掘算法（Apriori） 一、实验目的 1、理解频繁模式和关联规则 2、掌握频繁模式挖掘算法Apriori 3、为改进Apriori打下基础 二、实验内容 1、选定一个数据集（可以参考教学中使用的数据集） 2、选择合适的实现环境和工具实现算法，本次试验采用的是C++ 3、根据设置的最小支持度和置信度，给出数据集的频繁模式集 三、实验原理 该算法的基本思想是：Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1.然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此迭代，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。 Apriori性质：频繁项集的所有非空子集也必是频繁的。Apriori算法主要包括连接步和剪枝步两步组成。在连接步和剪枝步中采用Apriori性质可以提高算法的效率。 Apriori伪代码 算法：Apriori 输入：D - 事务数据库；min_sup - 最小支持度计数阈值 输出：L - D中的频繁项集 方法： L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集 For(k=2;Lk-1!=null;k++){ Ck=apriori_gen(Lk-1); // 产生候选，并剪枝 For each 事务t in D{ // 扫描D进行候选计数 Ct =subset(Ck,t); // 得到t的子集 For each 候选c 属于Ct c.count++; } Lk={c属于Ck | c.count>=min_sup} } Return L=所有的频繁集； Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets) For each项集l1属于Lk-1 For each项集l2属于Lk-1 If((l1[1]=l2[1])&&( l1[2]=l2[2])&&........ && (l1[k-2]=l2[k-2])&&(l1[k-1]

数据挖掘实验三应用 Apriori 算法挖掘频繁项集

实验三、应用 Apriori 算法挖掘频繁项集 学院计算机科学与软件学院 ?实验目的： （1）熟悉 VC++编程工具和 Apriori 频繁项集挖掘算法。 （2）根据管理层的需求，确定数据挖掘的任务，明确数据挖掘的功能，也 就是明确要挖掘什么。 （3）由确定的数据挖掘任务，从实验一处理后的结果中，采用切块或切片 等联机分析处理技术，选择出挖掘任务相关数据。 （4）用 VC++编程工具编写 Apriori 算法的程序，对任务相关数据运行 Apriori 算法，挖掘出所有的频繁项集。 1.写出实验报告。 ?实验原理： 1 、Apriori 算法 Apriori 使用一种称作逐层搜索的迭代方法，k 项集用于探索（k+1）项集。 首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项， 找出频繁 1 项集的集合。该集合记作 L 1 。然后，L 1 用于找频繁 2 项集的集合L 2 ，L 2 用于找 L 3 ，如此下去，直到不能再找到频繁 k 项集。找每个 L k 需要一次数据库全扫描。 2、提高频繁项集逐层产生的效率 Apriori 性质：频繁项集的所有非空子集也必须是频繁的。 三、实验内容： 1、实验内容 在给定的数据中提取统一购物篮购买的商品信息，由这些数据构成事务数据库 D，挖掘其中的频繁项集 L。 挖掘频繁项集的算法描述如下： Apriori 算法：使用逐层迭代找出频繁项集 输入：事务数据库 D；最小支持度阈值。 输出：D 中的频繁项集 L。 （1） L 1 = find_frequent_1-itemsets(D); // 挖掘频繁 1-项集，比较容易 （2） for (k=2;L k-1 ≠Φ ;k++) { （3） C k = apriori_gen(L k-1 ,min_sup); // 调用 apriori_gen 方法生成候选频繁 k-项集分为两步：合并、减枝 （4） for each transaction t ∈ D { // 扫描事务数据库 D （5） Ct = subset(C k ,t); （6） for each candidate c ∈ Ct （7） c.count++; // 统计候选频繁 k-项集的计数 （8） } （9） L k ={c ∈ Ck|c.count≥min_sup} // 满足最小支持度的 k-项集即为频 繁 k-项集

数据挖掘一些面试题总结

数据挖掘一些面试题总结（Data Mining） 摘录一段 企业面对海量数据应如何具体实施数据挖掘，使之转换成可行的结果/模型？ 首先进行数据的预处理，主要进行数据的清洗，数据清洗，处理空缺值，数据的集成，数据的变换和数据规约。 请列举您使用过的各种数据仓库工具软件（包括建模工具，ETL工具，前端展现工具，OLAP Server、数据库、数据挖掘工具）和熟悉程度。 ETL工具：Ascential DataStage ，IBM warehouse MANAGER、Informatica公司的PowerCenter、Cognos 公司的DecisionStream 市场上的主流数据仓库存储层软件有：SQL SERVER、SYBASE、ORACLE、DB2、TERADATA 请谈一下你对元数据管理在数据仓库中的运用的理解。 元数据能支持系统对数据的管理和维护，如关于数据项存储方法的元数据能支持系统以最有效的方式访问数据。具体来说,在数据仓库系统中，元数据机制主要支持以下五类系统管理功能： （１）描述哪些数据在数据仓库中； （２）定义要进入数据仓库中的数据和从数据仓库中产生的数据； （３）记录根据业务事件发生而随之进行的数据抽取工作时间安排； （４）记录并检测系统数据一致性的要求和执行情况； （５）衡量数据质量。 数据挖掘对聚类的数据要求是什么？ （1）可伸缩性 （2）处理不同类型属性的能力 （3）发现任意形状的聚类 （4）使输入参数的领域知识最小化 （5）处理噪声数据的能力 （6）对于输入顺序不敏感 （7）高维性 （8）基于约束的聚类 （9）可解释性和可利用性 简述Apriori算法的思想，谈谈该算法的应用领域并举例。 思想：其发现关联规则分两步，第一是通过迭代，检索出数据源中所有烦琐项集，即支持度不低于用户设定的阀值的项即集，第二是利用第一步中检索出的烦琐项集构造出满足用户最小信任度的规则，其中，第一步即挖掘出所有频繁项集是该算法的核心，也占整个算法工作量的大部分。 在商务、金融、保险等领域皆有应用。在建筑陶瓷行业中的交叉销售应用，主要采用了Apriori 算法 通过阅读该文挡，请同学们分析一下数据挖掘在电子商务领域的应用情况（请深入分析并给出实例，切忌泛泛而谈）？ 单选题 1. 某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖掘的哪类问题？(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理

频繁模式的挖掘

文献翻译 带约束条件的频繁模式的挖掘 摘要 众所周知，频繁模式的挖掘在数据挖掘中起到相当重要的作用。但是频繁模式的挖掘常常产生相当数量的模式和规则，这些不仅降低效率而且影响数据挖掘的效果。最近的一些工作更显示约束性的挖掘范例在频繁模式、关系、相互关联、连续的模式和其他有意义的挖掘中的作用。 最近，我们开发了一种增长型的模式挖掘方法来处理频繁的模式。这个方法不仅高效率，而且处理各种需求的时候效果很好。包括一些以前不能很好处理的为问题也能有效解决。在这篇论文中，我们将对模式增长型方法对频繁和连续的模式挖掘的要点进行概述。而且还将就一些复杂的具体问题进行探讨。 1、介绍 频繁模式的挖掘在数据挖掘项目中的作用不言而喻，比如寻找相联合性、相关性、因果关系、连续关系的模式、一段情节、多维的模式、最大的模式、时间分块性还有合并且合并模式。频繁模式的挖掘技术也可以用来解决其他问题，比如冰块算法、分类等等。这些广泛的应用就更显示出提高其效果和效率的重要性。 频繁模式的挖掘常常产生频繁模式和规则，这样会降低效率和效果，因为每次挖掘用户都需要进行繁琐的搜索。最近的工作突出了限制性搜索范例的重要性：用户可以通过丰富的语义形式来表示他挖掘进行的重点。另外也允许用户的继续开发和控制，可以由用户控制需要搜索的范围和模式，来取得进一步的效果提升。 以前关系频繁模式挖掘的大部分研究比如[2;9;16;18;21;22;29;30;32],采用类似Apriori的方法，基于反单调的Apriori属性[2]:如果长度为k的模式并不是频繁的，那么它的长度为k+1的父模式不会是频繁的。核心想法是从长度为k的模式中反复的产生长度为k+1的模式，然后检查他们在数据库中出现的频率。一个直观的类似Apriori的方法就是应用反单调的约束来削减候选项。但是很多常用的约束并不是反单调的，比如avg(X)>=X,需要X模式的平均值大于等于v。

频繁子图挖掘研究综述_鲁慧民

26卷　第3期2009年3月 微电子学与计算机 M IC ROELECTRONICS &COM PUTER Vol .26　No .3M arch 2009 收稿日期:2008-05-30 基金项目:国家“八六三”计划项目(2008AA 01Z 131) 频繁子图挖掘研究综述 鲁慧民,冯博琴,宋擒豹 (西安交通大学电子与信息工程学院,陕西西安710049) 摘　要:归纳了频繁子图挖掘方法的处理流程,分析评价了频繁子图挖掘的典型算法:广度优先搜索和深度优先搜索的频繁子图挖掘算法,概述了频繁子图挖掘研究的平台———图模型及其产生器,并对频繁子图挖掘方法未来研究方向进行了展望. 关键词:子图同构;频繁子图挖掘;图模型;图产生器 中图分类号:T P391 文献标识码:A 文章编号:1000-7180(2009)03-0156-06 Survey of Frequent Subgraph Mining Research LU Hui -min ,FENG Bo -qin ,SONG Qin -bao (School of Electronic and Information Engineering ,Xi ′an Jiaotong U niversity ,Xi ′an 710049,China ) A bstract :T he process of Frequent Subgr aph M ining is summarized in this paper .Broad First Search (BFS ),Depth First Search (DF S ),w hich are the typical mining algo rithms are analyzed and evaluated .T he g raph model and its generator ,w hich is the impo rtant research platform of frequent subg raph mining are introduced .O pen issues and fur ther research di -rections are also discussed . Key words :subg raph isomorphism ;frequent subg raph mining ;graph pa ttern ;g raph g enerator 1　引言 频繁子图挖掘与相对比较成熟的文本型频繁项 挖掘相比,图的数据量大,结构复杂,对原始的图数据进行频繁子图挖掘难度较大.同时通过边或节点添加生成的候选子图集中往往存在大量的冗余,子图同构的NP 问题等都增加了候选子图支持度计算的复杂性,因此一般的文本数据挖掘方法不再适用于频繁子图挖掘,必须结合图数据格式的特点寻求新的挖掘算法. Akihiro 等人在2002年首先将Aprio ri 算法思想应用到频繁子图挖掘中,此后各种基于Aprio ri 思想,采用递归的方法来发现频繁子图的挖掘算法相继出现,主要包括AGM 、AcGM 、FSG 等.后来韩家炜等人将FP -grow th 思想应用到频繁子图挖掘中,使图挖掘得到了迅速的发展,主要包括gSpan 、CloseGraph 和FFSM 等,它们主要通过逐渐扩展频 繁边得到频繁子图,但对边的扩展过程略有不同.此 外还出现了一些其它的频繁子图挖掘算法,例如Wang 等于2005年提出了一种基于索引的频繁子图挖掘算法GraphMiner [1];2007年Zhu 等提出一种基于用户约束条件的频繁子图挖掘算法gPrune [2] ,Karste 等提出了适用于动态图挖掘的 Dynamic G REW 算法[3] 等. 作为图挖掘研究的重点,频繁子图挖掘算法得到了广泛深入的研究,文中总结归纳了频繁子图挖掘的处理流程,对典型的频繁子图挖掘算法进行了分析评价,同时介绍了研究频繁子图挖掘的平台———图模型及其产生器,并展望了频繁子图挖掘的未来研究方向. 2　频繁子图挖掘的处理流程 频繁子图挖掘即从输入数据库中挖掘出所有的频繁子图.

数据挖掘试卷分析

一、简答题 1、什么是数据挖掘？数据挖掘有哪些挖掘任务？请进行简要的解释。 答：数据挖掘是一种技术，将传统的数据分析方法与处理大量数据的复杂算法相结合，从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和知识的过程。简而言之，数据挖掘是从大量数据中挖掘有趣模式和知识的过程。 数据挖掘的任务主要有分类分析、聚类分析、关联分析、序列分析及时间序列。另外，还有孤立点分析、依赖关系分析、概念描述、偏差检测等。 1、分类分析(Classification Analysis) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是有制导的学习，它利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预测，常应用于风险管理、广告投放等商业环境。 2、聚类分析(Clustering Analysis) 聚类又被称为分隔（segmentatio），聚类分析是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之间的相互关系。聚类分析是无制导的学习，聚类分析与分类分析不同，它不依赖于没有事先确定的类，也没有已具有类标识的训练集。好的聚类分析算法应该使得所得到的聚簇内的相似性很高，而不同的聚簇间的相似性很低。 3、关联分析 (Association Analysis) 关联规则挖掘是由Rakesh Apwal等人首先提出的。两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。最典型的应用是市场中购物篮分析。 4、序列分析及时间序列(Sequence Analysis and Time Sequence) 序列分析及时间序列是指通过序列信息或时间序列搜索出重复发生概率较高的模式。与回归一样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处的序列或时间的不同。 2、为什么要数据预处理？简要论述数据预处理步骤和每一步骤的任务 答：原始业务数据来自多个数据库或数据仓库，它们的结构和规则可能是不同的，这将导致原始数据非常的杂乱、不可用，即使在同一个数据库中，也可能存在重复的和不完整的数据信息，为了使这些数据能够符合数据挖掘的要求，提高效率和得到清晰的结果，必须进行数据的预处理。为数据挖掘算法提供完整、干净、准确、有针对性的数据，减少算法的计算量，提高挖掘效率和准确程度。 数据预处理步骤包含数据清理、数据集成、数据规约和数据变换。数据清理的任务是通过填充缺失值、光滑噪声并识别离群点、纠正数据中的不一致。将多个数据源中的数据结合起来存放在一个一致的数据存储中，有助于减少结果数据集的冗余和不一致，从而提高其后挖掘过程的准确性和速度。数据规约的任务是指在尽可能保持原始数据完整性的前提下，最大限度地精简数据量（缩小数据的取值范围）。这样，在归约后的数据集上挖掘将更有效，并产生相同(或几乎相同)的分析结果。数据变换的任务是对数据进行变换和统一，主要有规范化、离散化等策略，达到适用于挖掘的目的。 3、数据仓库相关？什么是OLAP？在数据仓库上经常进行哪些OLAP操作？请进行简要解释。 答： 建立数据仓库（特点见书P83）的目的有3个： 一是为了解决企业决策分析中的系统响应问题，数据仓库能提供比传统事务数据库更快的大规模决策

文本挖掘算法总结

文本数据挖掘算法应用小结 1、基于概率统计的贝叶斯分类 2、ID３决策树分类? 3、基于粗糙集理论Rough Sｅt的确定型知识挖掘? 4、基于k－mｅ 6、ＳＯＭ神经元网络聚类? 7、ans聚类?5、无限细分的模糊聚类Fuzｚy Clustｅｒing ? 基于Meａninｇ的文本相似度计算?8、文本模糊聚类计算?9、文本k－mｅａns聚类 13、ＰＣA主成分分析 12、序列模式发现? 10、文本分类?１1、关联模式发现? 1、基于概率统计的贝叶斯分类 算法概述:贝叶斯公式是由英国数学家（Thomas Bayｅｓ１70２-1763 ）创造，用来描述两个条件概率之间的关系，比如Ｐ(A｜B)为当“Ｂ”事件发生时“A”事件发生的概率，按照乘法法则: P(A∩Ｂ）=P(Ａ）*P(B|Ａ）＝P(B）*Ｐ（A|B），可导出 贝叶斯公式:P(A|B)=P(Ｂ｜A）＊P（Ａ)／P（B） 贝叶斯分类基本思想为：设决策变量为D,D１,Ｄ2,Di，…,Dk为n条记录组成的样本空间Ｓ的一个划分，将n条记录划分成ｋ个记录集合,如果以Ｐ(Di)表示事件Ｄｉ发生的概率,且P(Di）> ０( ｉ=1，2，…,k)。对于任一事件ｘ,Ｐ（x)>0，则有: 贝叶斯分类的基本原理，就是利用贝叶斯条件概率公式,将事件X视为多个条件属性Ｃｊ各种取值的组合，当x事件发生时决策属性Dｉ发生的条件概率。贝叶斯分类是一种概率型分类知识挖掘方法，不能百分之百地确定Ｘ事件发生时Di一定发生。 解决问题：预测所属分类的概率。通过已知n条样本集记录，计算各种条件属性组发生的概率，得出“贝叶斯分类”规则，给定一个未知“标签”记录，选择最大概率为其所属“分类”。 2、IＤ3 决策树分类 算法概述：ID3算法是J. Ross Quiｎlan在1９75提出的分类算法，当时还没有“数据挖掘”的概念。该算法以信息论为基础,以信息熵和信息增益度来确定分枝生成决策树D-Tree。ID ３算法以决策树D-Ｔree构建分类知识模型，D-Treｅ中最上面的节点为根节点Roｏt,每个分支是一个新的决策节点,或者是树的叶子。每个决策节点代表一个问题或决策,每一个叶子节点代表一种可能的分类结果，沿决策树在每个节点都会遇到一个测试，对每个节点上问题的不同取值导致不同的分支，最后会到达一个叶子节点为确定所属分类。