工作流挖掘算法（共7篇）
工作流挖掘算法 篇1
在竞争日益激烈今天, 提高企业工作效率, 优化企业工作流程无疑是至关重要的, 而工作流管理系统正是基于这种形势应运而生的。针对现有企业工作流管理系统的不足, 为了提高工作流对动态不确定因素的适应能力, 引入了工作流频繁模式。对频繁模式给出了明确的定义, 并在Apriori算法基础上提出了一种工作流频繁模式挖掘算法。该频繁模式以工作流管理系统日志为基础, 可以量化活动间逻辑关系的强弱, 在关键活动处提供工作流后续走势预测以及商业决策和风险预测等方面支持。
1 基本思想
本文主要通过扩展经典的Apriori算法挖掘工作流频繁模式。Apriori算法中频繁项集仅是一个事务中项的集合, 没有顺序关系, 但在工作流频繁模式挖掘算法中活动间有先后顺序, 而且还存在并行结构, 所以采用活动间依赖关系作为频繁项集和候选项集的项, 即每个实例表示为形如dij=n (n=1, 0, -1) 的依赖矩阵元素集合, 通过函数Comp Matrix Patterns计算频繁项集, 再通过函数Comp Patterns得到最终的工作流频繁模式集合。此外, Apriori算法中对频繁项没有要求, 但在工作流模型中, 依赖矩阵Di包含活动集合AS (Di) 中任意活动间的依赖关系, 其表示的模型才具有意义, 所以工作流模式挖掘中, 要求项集频繁且完整。
2 形式化描述
定义1模式G= (V, F) 为某实例Ij的子集, 称实例I支持一个有向图表示的工作流模式P, 如果模式G中的依赖关系在实例I中是成立的, 记为
定义2日志中所有实例集合S0, 对于工作流模式G的支持度 其中|S0|表示日志中实例数。同时可得, 对于实例集S', 有向图所表示的工作流模式G'在实例集S'上是频繁的, 如果实例集S'中有对模式G'的支持度s叟最小支持度阈值P。
同时, 扩展了定义4中依赖矩阵的定义, 通过定义7, 实例所对应的扩展依赖矩阵是沿对角线对称, 所以很容易将矩阵转化为上三角矩阵, 降低算法的复杂度。
定义3坌Ii, Ij∈实例集S, 满足AS (Ii) =AS (Ij) , 则实例集S对应的依赖矩阵定义为v阶布尔矩阵D= (dij) , v=|DS (I) |, 为集合DS (I) 的元素个数。其中if活动
3 频繁模式挖掘过程
3.1 数据预处理
于MWMA工作流模型挖掘算法一致, MWPMA的输入日志也需要经过数据准备阶段, 包括数据选择, 数据转换与数据清洗。按照前一章的数据预处理办法, 首先把日志数据初步整理得到每个实例的活动的开始事件和结束事件的时间序列。并将日志S0划分为多个子集S1, S2, …, Sn, 满足∀Si, ∀Ii, Ij∈Si, 都有Ii与Ij重复, 每个集合Sj中选取一个实例Ijk作为代表。这样可以提高后续算法的效率。对各个子集S1, S2, …, Sn, 计算依赖矩阵D1, D2, …, Dn。算法中采用活动间的依赖关系作为实例项, 则可得1项候选集合C1={dij=1∪dij=0∪dij=-1:ak, aj∈V, 且i
3.2 计算矩阵频繁项集
利用Comp Matrix Patterns函数计算矩阵频繁项集。Ck代表k项候选频繁集;Lk代表k代项频繁集, 首先计算所有频繁项集, 但是这些频繁项集并不一定完整, 然后去掉其中不完全的矩阵频繁项集得到最终的频繁集。
3.3 生成频繁模式
下面再利用Comp Patterns函数将生成的频繁矩阵元素项集L1, L2, …, LMax K中的项生成以有向图表示的频繁模式。对于频繁矩阵元素项集Lk, 其中每个项cn中的矩阵元素集合{dij:dij∈cn}可以组成一个上三角矩阵Dn, 即对应活动集合AS (cn) 的依赖矩阵。Comp Patterns把活动集AS (Dn) 分为四个集合:Former Set, Cur Set, Next Set, Left Set。
经过Comp Dir Depend函数处理的矩阵Dn包含了日志中所有的活动间直接依赖关系, 可以直接通过Dn生成频繁模式, 由有向图G= (V, F) 表示, 其中V=AS (cn) 代表有向图的节点集合 (a1, …, akn) ;F是有向图的边集。对于矩阵Dn元素dij=1, 则工作流模型中存在一条从有向边ai指向aj;反之dij=1则存在一条从有向边由aj指向ai。
3.4 挖掘过程示例
下面以某公司处理客户投诉过程模型为例讲述模式挖掘过程, 设支持度为0.5。
将日志经过上述预处理之后得到实例集S如下, 其中ais, aie:分别表示活动的开始事件和活动结束事件,
由定义7可得上述实例所对应的扩展依赖矩阵简化为上三角矩阵如下:
经函数Comp Matrix Patterns处理后得到矩阵频繁项集L6={ (D1', D2') }其中
再由函数Comp Dir Depend处理频繁依赖矩阵D1', D2'可得包含直接依赖关系的矩阵D3', D4'如下:
最后根据直接依赖矩阵D3', D4'得到最终的工作流频繁模式:
4 结论
工作流频繁模式包含了丰富的信息, 可以为流程动态变化因素提供解决的基础, 同时可以为工作流管理系统中重要的商业决策、风险预测等提供支持, 也为工作流模型优化提供依据。本文扩展经典的Apriori算法作为新的工作流模型频繁模式挖掘方法, 与其他工作流模式挖掘方法相比, 本算法更具优越性, 能够处理具有串、并行关系的工作流模式。在工作流模型中, 活动间除串、并行关系外还存在循环关系, 本算法在处理活动间并行循环关系时存在不足, 不能完全处理循环关系。
摘要：针对企业工作效率日益提高的需求, 根据现有企业工作流管理系统的不足, 对Apriori算法进行优化, 提出MWPMA工作流频繁模式挖掘算法。
关键词：MWPMA,工作流频繁模式,挖掘算法
参考文献
[1]W.M.P.van der Aalst, A.J.M.M.Weijters, Process Mining-a re-search agenda, Computers in Industry[J].2004, 53 (3) :231-244.
[2]W.M.P.van der Aalst, B.F.van Dongen, J.Herbst, L.Maruster, G.Schimm, A.J.M.M.Weijters, Workflow mining-A survey of issues and approaches[J].Data&knowledge Engineering, 2003, 47 (2) :237-267.
[3]范玉顺.工作流管理技术基础———实现企业业务过程重组、过程管理与过程:自动化的核心技术[M].北京:清华大学出版社施普林格出版社, 2001.
数据挖掘技术与关联规则挖掘算法 篇2
1 数据挖掘技术介绍
1.1 数据挖掘技术的概念
数据挖掘技术是一门包容性以及开放性较强的跨领域数据信息揭示学科, 这项技术能从大量含有噪声, 且模糊不确定的实际业务数据中进行计算, 在这些数据中对当前尚未发现, 或者没有被明确认知的具有一定价值的知识信息进行揭示。在进行数据挖掘中的业务数据形式不是单一固定的, 是复杂多样的, 所以数据挖掘得出的分析结果形式能以多种形式表现出来, 可以是具有较强逻辑性的数学表达式, 也可以是容易被一般用户理解的结果。且数据挖掘技术在科学研究、市场分析等领域均得到了广泛的应用。
1.2 数据挖掘技术分类
数据挖掘功能的分类主要是根据数据挖掘功能的不同进行的, 当前的数据挖掘技术主要有关联规则挖掘技术、分类挖掘技术、孤立点挖掘技术以及聚类挖掘技术等。本研究主要对关联规则挖掘算法进行详细探讨。
2 关联规则挖掘算法
2.1 关联规则种类介绍
关联规则按照不同的标准, 能用各种不同的方法分成不同类型。将关联规则分为挖掘频繁项集、闭频繁项集、被约束频繁项集、极大频繁项集, 是根据挖掘模式的完全性分类的;将关联规则分为多层和单层关联规则, 以及单位和多维关联规则是根据规则所涉及的数据进行分类的;将关联规则分为量化关联规则和挖掘布尔型规则是根据规则处理值类型分类的;将关联规则分为序列模式挖掘、频繁项集挖掘以及结构模式挖掘是根据俄关联规则挖掘模式进行分类的;将关联规则分为兴趣度约束、知识类型约束、数据约束, 是根据规则所挖掘的约束类型分类的。
2.2 关联规则挖掘算法分析
2.2.1 Apriori算法分析
关联规则算法中的挖掘完全频繁项集中, Apriori算法该类型中最具有应用价值, 影响力最大的算法。Apriori算法主要有两个步骤:
(1) 发现所有的频繁集;
(2) 生成强关联规则。
在Apriori算法中的第一步是最为重要的步骤, 该算法的核心思路是, 给定一个数据库, 在第一次数据库扫描中找出所有支持度大于等于最小支持度的项目组成频繁1—项集, 也就是L1, 1—项集C1, 由L1进行连接得到;接着进行第二次数据库扫描, 将C1中所有支持度大于等于最小支持度的项集组成频繁2—项集, 也就是L2, 候选2—项集C2由L2连接得到。以此类推, 直到找出最大项频繁集。即在进行第N次数据库扫描时, 找出CN-1中所有支持度大于等于最小支持度的项集组成频繁N—项集, 即是LN, N—项集CN要由LN连接得出, 一直到找不出新的选集为止。在这里还要用到Apriori算法性质, 即是频繁项集是频繁项集的子集, 非频繁项集是非频繁项集的超集。在Apriori算法中对数据库的扫描次数需要大于最大频繁项集的项数。
Apriori算法的操作具有两个明显的缺点。 (1) 该算法的使用需要对数据库进行多次扫描, 因此在读写操作上会花费很多的时间, 从而增加挖掘算法的时间成本, 这种成本的增加不可小觑, 因为它是有数据库存储数据的增加, 以几何级数上升的成本;
(2) Apriori算法会出现众多的候选频繁集, 频发集的产生量在每一步都很大, 这会使算法在广泛度和深入度上的适应性较差。
2.2.2 FP—growth算法分析
FP—growth算法是关联规则算法中属于深度优化的一种算法, 这种算法是深度优化算法中较新且具有较高成效的, 不同于Apriori算法本质的常用算法。FP¬—growth算法的基本基本步骤有两个:
(1) 先将频繁模式树FP—tree生成;
(2) 在生成的FP—tree频繁模式树中搜索频繁项集。
(1) 需要将项集关联信息保留住, 并采用一棵频繁模式树 (FP—tree) 用来容纳压缩后的数据库;
(2) 再将压缩后的FP—tree再分散为几个小的条件数据库, 再分别对这些数据库进行信息挖掘。FP—growth算法相较于Apriori算法, 只需要对数据库进行两次扫描, 不需要多次扫描, 大幅度减少了挖掘算法的时间成本;也不会出现大量的候选项集, 大幅度减少了频繁集的搜索空间。也就是说FP—growth算法能明显提高时间和空间效率。但是该算法也有缺点, 在对庞大且松散的数据库进行挖掘处理过程中, 不管是递归计算还是信息挖掘都需要占据大量的空间。
3 总结
综上所述, 本研究对对数据挖掘技术概念和分类进行了简单的介绍, 并对关联规则的种类进行了详细的分析, 对关联规则中常用的两种算法FP—growth算法和Apriori算法进行了详细的分析。两种算法都还存在各自需要改进缺点, 怎样在挖掘过程中提高挖掘效率, 满足人们对挖掘系统的需求, 这将是数据研究工作者仍然需要突破的重难点。
参考文献
[1]毛国君.数据挖掘技术与关联规则挖掘算法研究[D].北京:北京工业大学, 2015.
[2]张弛, 王本德, 李伟等.数据挖掘技术在水文预报中的应用及水文预报发展趋势研究[J].水文, 2015, 27 (02) :74-77, 85.
[3]魏陵博, 付先军.基于Aprio关联规则挖掘技术分析归心经中药与抗心律失常药理作用的相关因素[J].中西医结合心脑血管病杂志, 2014 (05) :517-518.
[4]付先军, 周永红, 王中琳等.基于频繁项集与关联规则挖掘技术探索王新陆临床用药及处方配伍规律的初步研究[J].中国中医药信息杂志, 2015, 17 (09) :92-94.
相异关系模式挖掘算法 篇3
关键词：序列模式挖掘,负关联规则,相异关系模式
1 引言
序列模式挖掘(Sequential Pattern Mining)是一种非常重要的数据挖掘(Data Mining)技术,它在许多基于事件的或与序列相关的领域中有重要的应用。关联规则(Association Rule)是序列模式挖掘研究的主要领域之一,其任务是发现大量数据中项集之间有趣的联系。Agrawal等人于1993年在文献中首先提出关联规则的概念,1997年,Brin等人又在文献中指出了负关联规则的重要性。本文主要介绍一种类似于负关联规则的相异关系模式挖掘的研究,提出相应的算法挖掘Rdis RP,并通过实验验证算法的可行性和有效性。
2 相关定义
定义1.相异关系:对于序列α1α2…αn,客户序列数据库CSDB中的一条客户序列c包含且仅包含序列α1α2…αn中的某一条序列,则称α1α2…αn相对于客户序列c满足相异关系。如:序列α,β相异表示为:(α,β);多序列α1α2…αn相异表示为:(α1,α2,...,αn)。
定义2.相异度:对于给定的客户序列数据库CSDB,序列模式集SP(Sequential Patterns)中序列α与β的相异度定义为出现α或β的客户序列中满足相异关系的客户序列的频度,即:
定义3.多分支相异的定义:首先我们通过多成员间的两两相异来推广多分支相异,得出拟相异序列后再计算相异度。如在序列α1α2…αn中,若有αi,αj(1≤i
定义4.相异序列模式:假设mindis为用户指定的最小相异度阈值,α和β是序列模式并且满足dissimilar(α,β)≥mindis,那么α和β组成相异序列模式。
3 相关性质
性质1:根据相异关系的定义,dissimilar(x,y)≥mindis,相异关系中的两个序列间不存在次序关系,所以有dissimilar(y,x)≥mindis成立。由此可以判断,若x与y存在相异关系,则y与x同样存在相异关系。
性质2:若序列模式x与y是相异的,则x及x的超模式与y及y的超模式皆构成相异序列模式,反之则不成立。
4 挖掘算法
引理:已知有一条K分支相异模式,那么它的任意一个二分支模式相异。
证明:由多分支相异的定义可知,若α1α2…αn相异,那么对任意的αi,αj(1≤i
这里以五分支为例:若abcde相异,定义可知所有的二分支模式ab、ac、ad、ae、bc、bd、be、cd、ce、de相异,且dissimilar(a,b,c,d,e)≥mindis。用图形化表示为:
算法的基本思路:(1)长度为1的分支模式L1作为初始的种子集。
(2)根据长度为i的种子集Li通过连接操作和剪切操作生成长度为i+1的候选分支模式Ci+1,再扫描客户序列数据库,计算每个候选序列模式的支持度,产生长度为i+1分支的相异模式Li+1,并作为新的种子集。
(3)重复第二步,直到没有新的分支模式或新的候选分支模式产生为止。L1==>C2==>L2==>C3==>L3==>C4==>L 4==>……
产生候选分支模式的步骤:
(1)连接阶段:如果去掉k分支模式S1的第一个项目与去掉k分支模式S2的最后一个项目所得到的序列相同,则可以将S1和S2进行连接,即将S2的最后一个项目添加到S1中。
(2)剪切阶段:若某候选分支模式的某个子序列不是互斥模式,删除该候选分支模式。
例:种子序列<(a,b)c>与
算法Rdis RP
输入:客户序列数据库CSDB,用户给定最小支持度minsup及最小相异度mindis
输出:相异关系模式全集DRPs
方法:1.在CSDB基础上,给定的最小支持度minsup下求序列模式全集SP={sp1,sp2,…,spn}
2.求每条客户序列所支持的序列模式全集Sup p SPij
(1)连接阶段:
(2)剪枝阶段:
5 实践结果
我们对给定数据进行挖掘,从而验证相异关系模式挖掘理论的完备性和有效性。给定CSDB:(1)
首先,进行序列模式挖掘,令最小支持度minsup=40%,得到序列模式集SP。
接着,进行相异序列模式的挖掘,由于本次挖掘的客户序列数据库的客户序列总数为5,所以这里我们分别挖掘最小相异度为mindis=55%,mindis=75%和mindis=95%时的相异序列模式。下图1表示相异关系模式的挖掘结果。
相异关系模式的各分支模式数都是随着最小相异度的增加呈先增加后减少的趋势,并且分支数随着最小相异度的增加而减少。另外,总模式的个数随着最小相异度的增加而减少。此实验验证了本文所述的相异关系模式基本理论的有效性和可行性。
6 结语
本文主要描述了基于序列间相对关系的相异关系模式挖掘,这是在序列模式挖掘基础上的进一步理论研究。主要介绍了相异关系模式的定义、性质、相关的挖掘算法和实验验证,实验结果准确、可靠。这些工作都为进一步的序列模式挖掘的研究奠定了基础。
参考文献
[1]Jiawei Han,范明?等.数据挖掘概念与技术[M].北京:机械工业出版社,2001.
[2]Srikant Ramakrishnan,Agrawal Rakesh.Mining sequentialpatterns:Generalizations and performance improvements.In:Proceedings of the 5th International on Extending DatabaseTechno ERPs.
经典关联规则挖掘算法 篇4
关键词：数据挖掘,关联规则,Apriori算法,FP-growth算法
1 数据挖掘的产生以及应用
浩瀚的知识海洋和纷繁复杂的传媒导向使人们逐渐意识到要适应紧张、高效的工作和生活, 就必须从中提取对我们有用的、隐藏的信息, 而且还要确保信息的安全性、准确性, 以提高我们的工作效率和信息利用率。面对这种实际情况, 数据开采和知识发现 (DMKD) 技术产生了。
数据挖掘是一门基于多种学科的交叉学科, 它综合了人工智能、数据仓库、数据库技术、机器学习、统计学、计算机网络、数据组织等许多学科的基础知识与重要技术, 其中最重要的两门学科是统计学和机器学习。数据挖掘技术是人们对数据库技术进行研究、开发和使用的结果, 最初数据挖掘技术运用在商业中, 从最初简单存储、查询和访问数据到找出各数据之间的潜在关系。主要用到了以下技术:海量数据的搜集和快速访问, 强大、先进的多处理器计算机。数据挖掘逐渐从电子数据处理初期、机器学习、神经网络技术、知识工程演变为现在所熟知的数据库中的知识发现 (Knowledge discovery in database, KDD) 。
2 经典关联规则挖掘算法
关联规则挖掘在国内得到了充分的研究:自1993年R.A grawal等人提出关联规则挖掘问题以后, 众多研究学者又相继提出了较有代表性的Apriori算法, CD (Count Distribution) 算法, 采用Hash技术的DHP算法、PDM (Parallel Data Mining) 算法、Sampling抽样算法、动态项集计数算法DIC、FP-Growth算法、FUP (Fast Update) 算法、Opportune Project算法以及基于云模型的关联规则算法等。关联规则挖掘算法中, 最为经典的是Apriori算法以及FP-Growth算法, 其他大部分算法都是基于以上两种算法的改进研究。以下, 我们先来看看关联分析的概念及基本实现思想。
数据挖掘用来预测未来, 发现潜在的、有用的信息和数据, 对现有的数据资料依照算法进行处理, 得到对我们有利的信息。典型的例子就是啤酒与尿布。可以说“啤酒与尿布”的故事是数据挖掘最经典、最具特色的故事。大致的意思是:美国的沃尔玛———世界著名商业零售连锁企业, 为了准确了解顾客的购买习惯, 对顾客的购物行为进行分析, 主要是想知道顾客常常一起购买的商品组合是什么。一个意外的发现竟是, “尿布与啤酒竟然是很好的组合”。这是数据挖掘对历史数据进行分析后得出的结果, 我们获取的是潜在的价值规律。
如果事务数据库中有s%的事务记录中包含X∪Y, 那么称规则X=>Y在事务集D中具有支持度s;如果事务数据库中包含X的c%的事务记录同时也包含Y, 那么称规则X=>Y在事物数据库中具有置信度c。
2.1 Apriori算法
Apriori算法的主要思想是通过迭代的方法产生频繁项集。如今的大部分关联规则算法都是经典算法Apriori的演绎和改进。在每次迭代过程中, 主要有如下关键步骤:产生候选集, 计算支持度, 根据最小支持度阈值筛选出频繁项集。在迭代产生候选集的过程中会出现大量的冗余, 包含所有满足最小支持度阈值及不满足的记录。候选集产生后, 再次扫描数据库, 以求得候选集中各子项的支持度。最后, 所有支持度s大于最小支持度阈值的项集, 我们称之为频繁项集。
在第一次迭代获得候选项集后, Apriori算法通过去除不满足最小支持度阈值的非频繁项集减少候选项集的数量。在使用Apriori算法时, 从候选项集中产生频繁项集时需要遍历数据库, 那么如何产生最少数目的候选项集同时也具有较好的正确率, 是个十分关键的问题。联合与剪枝是候选项集产生的过程, 使用这种方式, 可以使所有的频繁项集不会遗漏也不会重复。
Apriori算法的主要进程如下:
(1) 先对数据集进行彻底的扫描, 并根据扫描结果确定各1-项集的支持度, 然后将选出的这个满足最小支持度计数minsup的项作为频繁1-项集, 记作L1。
(2) 利用频繁1-项集来生成候选2-项集C2并计算各项集的支持度, 用最小支持度进行筛选, 得出频繁2-项集。
(3) 依照此种方法, 即采用迭代的方式依次生成频繁3-项集L3、4-项集L4…一直到最后所得的项无法满足最小的支持度也无法产生频繁项集, 计算结束。
Apriori算法由于遍历数据库次数过多, 在挖掘过程中生成大量的候选集, 因此这种算法的执行效率不高。
2.2 FP-growth算法
FP-growth算法常用在大型数据库中挖掘频繁项集。FP-Growth算法是一种基于FP树并采用自下向上方式发现频繁项集的数据挖掘算法, 先对数据库进行投影, 得到一个频繁项, 然后构造压缩的数据库结构。同Apriori算法相比, 总结来说, FP-Growth算法的特性如下:
先进行扫描, 将事务记录数据扫描并映射到FP树上, 利用这种方法很大程度地减少了因对数据库多次扫描而产生的I/O时间。因此FP-Growth算法能避免生成大量候选集, 也使数据挖掘的搜索空间在很大程度上降低了。
FP树依次读入每条事务记录, 接着按照事件发生频次将事务中的各项由高到低的排列映射到FP树上的路径。设定FP树的头结点为NULL, 各树中的各分支结点记录了每个结点的频度计数, 通过建立项头表实现前缀路径。然后, 对FP树采取分而治之的挖掘方法去实现频繁项集的挖掘过程:根据项头表和FP建立的路径关系, 找出各所包含的项集组合, 完成项集支持度计数;根据最小支持度对项集组合进行筛选, 并生成频繁项集。第一次扫描数据库D, 得到如下的频繁项列表L:
L={ (a, 4) , (p, 4) , (c, 3) , (b, 3) }。频繁项集在排序时是按照支持度计数递减顺序。
接下来的过程就是创建树的根部ROOT, 第二次扫描数据库。通过对第一个事务扫描得到树的第一个分枝:{ (a, 1) , (p, 1) , (c, 1) , (b, 1) }。通过上述, 我们可以得出, 在频繁项列表L中出现的项才会被选中。在这个分枝中出现的节点计数都是1, 它们表示该节点项出现的次数。对第二个事务进行扫描, 我们发现它有相同的项a, p和c, 它和第一个分枝有相同的前缀{a, p, c}, 并扩展到新的分枝{ (a, 2) , (p, 2) , (c, 2) , (b, 1) }。若有共同的分枝, 计数分别增加1, 两个事务加入到树中后, 依次类推, 最终生成的FP树。
除了以上所提及的关联规则挖掘算法外, 国内外研究学者在算法的优化升级以及更多的利用空间上也倾注了大量的心血, 由于数据库布局的不同以及应用领域的差异产生了各种各样关联规则挖掘算法, 诸如常用的并行挖掘算法、分布式挖掘算法、流数据挖掘算法以及负模式的挖掘等。大家在应用这些算法的时候, 应根据所处的环境有针对性地去选择适用的算法来解决问题。
参考文献
[1]翁光聪.数据挖掘技术在高校人力资源管理系统中的应用[D].同济大学, 2006.
[2]R.Agrawal and R.Srikant.Fast algorithms for mining association rules[A].Proc.1994 Int’l Conf.Very Large Data Bases (VLDB’94) .
[3]任小娟.数据挖掘技术在教学中的应用[J].电脑知识与技术, 2005:211-212.
[4]Mehmed Kantardzic:DATA MINING Concepts, Models, Methods, and Algorithms[M].清华大学出版社, 2003:1-10.
工作流挖掘算法 篇5
1关联规则
设I={i1, i2…, id}是所有项的集合, 而T={t1, ..tn}是所有事务的集合, 每一个事务ti包含的项集都是I的子集, 在关联规则的分析中, 包含多个项的集合被称为项集。例如一个项集包含了k个项, 则此项集被称为k-项集。关联规则表达式X->Y, 其中X和Y是不相交的项集, 即X∩Y=Φ。支持度 (support) 是T中同时包含X和Y的事务占的百分比。置信度 (confi dence) 是T中同时包含X和Y的事务占包含x的事务的百分比。项集的出现频率是包含项集的事务数, 称为项集的支持度计数。支持度确定规则可以用于给定数据集的频繁程度。
关联规则挖掘步骤分为:
(1) 根据给定的最小支持度, 发现频繁项集。
(2) 利用最小置信度, 有频繁项集产生强关联规则。第1步是算法中非常耗时的, 目前大部分改进算法都是针对第1步进行的, 其决定了算法的性能。
2 Apriori算法分析
Apriori算法分为两个过程:
(1) 通过迭代, 发现交易数据库中的全部频繁项集。
(2) 构建满足用户最小信任度规则。即首先找到频繁1-项集, 记为L1, 利用L1构建候选项集C2, 根据C2挖掘出L2, 如此不断重复操作, 直到无法发现更多的频繁k-项集。
Apriori算法描述
3 Apirori改进算法-RF算法
经典Apriori算法中, 要核对每一个交易记录中所有长度的候选项集, 也就是说, 在计算k长度候选项集支持度的时候, 在核对它的出现频率时, 也要包括长度大于k, 等于k及小于k的项集。而在RF算法中, 在计算候选项集支持度时, 只选择交易记录中长度大于或等于候选项集长度的交易记录, 因为长度为k的候选项集是不会出现在长度为k-1的交易记录中, 它只能出现在长度大于或等于k的交易记录中。利用RF算法可以改进经典Aprior算法的效率, 减少算法时间复杂度。
基于Apriori算法的RF算法
4实验分析
从表1和图1可以看出, RF算法与经典Apriori算法相比, 有更高的效率。在分析过程中, 当记录数为400时, 经典Apriori算法需花费6秒, 而RF算法需花费4秒。当记录数量不断增加时, RF算法在执行时间上表现出较好的性能。
5结论
关联规则挖掘具有广泛的适用性, 如市场购物篮分析、医疗诊断和研究分析, 网站导航等领域。文章在分析关联规则挖掘技术及经典Apriori算法的基础上提出一种改进算法-RF算法。传统关联规则算法在发现关联规则过程需要两个或更多的步骤, 而RF算法在发现频繁项集过程中采用同样的步骤, 但比传统的算法花费更少的时间。
摘要：频繁模式挖掘在数据挖掘领域中有着大量的研究和广泛的应用。大型数据库中的频繁模式挖掘已经成为数据挖掘与知识发现领域的一个重要问题。本文在分析经典Apriori算法基础上, 提出一种改进算法RF算法, 该算法在计算候选项集支持度时, 只选择交易记录中长度大于或等于候选项集长度的交易记录, 减少了算法运行时间。实验表明, 改进后的算法执行时间上表现出较好的性能。
关键词：数据挖掘,频发模式,关联规则,项集
参考文献
[1]朱明.数据挖掘[M].合肥:中国科技技术大学出版社, 2007
工作流挖掘算法 篇6
1 数据挖掘技术
数据挖掘技术是一种新型的信息处理技术, 与传统技术相比, 其具有更高的商业价值, 通过应用该技术能够促使人们从低层次的联机查询上升至对数据决策支持分析预测上, 以便于实现更高层次的应用。依据数据挖掘技术知识类型的不同, 可以将其划分为:预测范围知识挖掘、关联范围的知识挖掘、差异范围的知识挖掘、广义范围的知识挖掘;常用的数据挖掘方法主要有:当代数学分析法、数据集成方法、元模式法、证据理论法、数据分析法、近似推理法、不确定性推理法、神经网络Neural Network探索性分析法、遗传算法Genetic Algorithm、信息聚类分析法、数理统计法、计算机学习法等;另一方面, 数据挖掘技术的对象也是多种多样的, 主要可以分为下列几种:多媒体数据库、遗产数据库、空间数据库、文本数据源、异质数据库、时态数据库等。
对常用的几种数据挖掘技术进行简单分析, 主要表现为:
(1) 规则归纳, 这主要是指对数据开展相关的统计, 其主要是对数据项中的一些集合与属性进行反映, 其中一种比较典型的归纳算法就是AQ法, 通过应用数据挖掘技术能够及时发现数据库中一些潜在的位置信息。
(2) 支持向量机, 这主要是指建立在一些数学理论基础上的结构风险, 其主要思想为:通过在高空多维空间中寻找一个超平面, 然后应用该超平面将这两类隔开, 以便于在数据处理过程中保证最小分类的错误率, 但是其显著优点就是线性问题。
(3) 模糊集, 模糊集理论中不具备针对性, 在数据处理过程中主要分为两方面的内容, 已当面是不确定的数据, 另一方面是不完整数据, 应用模糊集理论进行数据处理时, 其处理起来更加的方便有效。
(4) 统计方法, 在该种方法中, 主要是对事物的数量进行统计分析, 以便于推断其规律, 在查找到事物的数据线索之后, 在此基础上进行假设, 并对其可行性进行严重, 应用这种方法的过程中, 其中具有的一个显著优点就是精确性。
2 关联规则挖掘算法
在早期关于数据挖掘技术的研究中, 研究的重点放在数据挖掘模型的建立以及相关算法的研究上, 但是应用这种研究方法所得到结果研究结果是比较孤立的, 难以取得理想的数据处理效果, 随着关于数据挖掘技术研究的深入, 人们发现在开展数据挖掘技术的研究过程中, 想要有效的实现用户相关的挖掘目标, 除了需要加大算法的研究力度之外, 还需要制定出特定的实现机制, 以便于所制定的挖掘计划能够转化成为对一个系统工作的控制, 这样才能促使挖掘项目获得一个理想的挖掘效果, 对于挖掘算法的约束作用, 在挖掘算法开展的任何阶段都可以实现, 并且挖掘算法的基本形式就是交互式数据, 在实际的挖掘算法开展的过程中, 严格按照相关的计算流程开展才能达到快速、准确完成挖掘任务的目的。
在开展数据挖掘计算的过程中, 由于面临着多种因素的影响, 并且其中一些因素是难以把握的, 这直接导致了挖掘算法的结算结果具有不可预测性, 因此还需要为挖掘算法添加反馈机制, 通过有效的反馈机制能够对计算结果进行验证, 并且能够对算法中的数据进行修正, 在该过程中, 不仅要保证所挖掘到数据的正确性, 还需要保证数据是用户所侧重的, 这就需要所挖掘的数据结果不仅具有逻辑上的正确性, 还要能够满足用户的主观偏好, 既要能够满足用户的需求, 这就需要有效的约束来发现算法中的问题, 并及时的开展算法纠正, 这样才能保证所开展的挖掘算法能够满足各方面的实际需求。
但是在实际的开展挖掘算法的过程中, 很容易导致陷入到一个误区当中, 也就是将关注的重点放在一个系统处理所出现的问题上, 但是对系统规模大小的控制没有予以足够的重视, 出现这样的问题会对挖掘算法结果起到反作用, 使得相关问题难以很好的解决。在进行数据挖掘的约束时, 要保证实现系统增量式扩充, 在对用户的实际需求与目标予以明确之后, 需要借助于约束参数, 结合约束参数的形式对一些有待解决的问题实施验证, 一旦确定相关数值之后, 就可以通过实验的交互式输入实现, 最终较大较优值, 该约束机制能够应用于数据挖掘算法的各个不同阶段, 另一方面, 在开展数据的预处理时, 要能够保证约束个数的设置在保证数据挖掘结果正确性的同时, 能够保持数据的规模, 并且可以将约束机制应用于整个项目细分之后的子目标, 从而实现快速约束。为了能够更好的解决相关问题, 可以对不同类型的问题加用不用的约束调节, 特别是在维度较高的数据的除了过程中, 如果所选择的约束条件合适, 能够有效简化挖掘算法。
在选择约束类型的过程中, 时态约束下的关联规则主要是指:一次数据库扫描挖掘算法能够在减少一定的I/O个数的基础上, 促使数据量的不断上升, 这就会导致计算机内存占用量的线性增大, 因此, ISS容量控制就是关联规则数据挖掘算法中非常重要的内容, 并且能够有效减少CPU的占用量, 为了能够有效的改善这一问题, 可以采取对数据进行分批处理的方式, 通过对数据实时有效的组织, 能够有效的改善数据结构, 降低数据内存, 并且能够生成独立的关联规则, 在降低计算机硬件资源占用率的同时, 有效改善精确度。
3 结束语
数据挖掘技术是一种新型的数据处理技术, 不管是数据挖掘技术还是关联规则挖掘算法, 其中所包含的内容比较多, 本文就主要对其进行了简单分析, 对于实际的数据挖掘工作具有一定的参考价值。
参考文献
[1]刘兴明.浅析数据挖掘技术与关联规则挖掘算法[J].无线互联科技, 2014 (08) .
数据挖掘关联规则算法研究 篇7
Web服务器的日志文件通常都是简单的文本文件, 在长期的历史时期只是作为服务器管理员的参考使用, 利用率很低。但其中的信息涵盖丰富, 包含了了用户的上网时间、运行的程序、访问的页面等互联网的有用信息, 通过对这些海量信息的梳理, 只要运用的关联规则分析研究, 即可清晰地记录用户的程序使用习惯和网站访问偏好, 预测用户的喜好, 从而进行个性化推荐, 这在互联网+ 经济时代蕴藏着巨大的商业价值, 是还未充分挖掘的宝藏。
用户的对于兴趣内容的访问习惯和偏好, 下一步的行为可能就是购买等商业行为。因此, 利用Web日志挖掘的个性化推荐关联规则算法对用户关于兴趣内容的访问习惯和偏好挖掘是非常重要的。高效的Web日志挖掘[1], 可以很好地发掘出用户感兴趣的关键字和内容, 很好的预测商机, 为定向的个性化推荐服务打下良好的基础。Web日志挖掘的个性化推荐关联规则算法主要流程是从Web日志中筛选用户访问路径, 然后从梳理好的事务集中使用Apriori算法挖掘出高频访问集, 以此为依据进行个性化推荐服务。
一、Web日志挖掘中个性化推荐关联规则算法
个性化推荐关联规则算法可以分为两个主要步骤: 数据预处理步骤和高频访问模式发现步骤。其中数据预处理是从日志当中杂乱的结构化和非结构化数据进行分析和提取, 梳理出干净的数据, 作为实验中有效的备用访问事务集。通过高频访问模式和基于关联规则的改进Apriori算法挖掘用户的潜在访问路径, 通过从干净的事务集发掘高频访问集得到合适的个性化推荐关联规则算法。
1.1 Hadoop平台搭建。为了模拟云平台集群运行模式, 通过在局域网多台电脑上安装不同操作系统的方式组建计算机集群。在局域网中构建了8 个节点, 其中, 三台电脑为WIN7, 三台电脑为MAC, 两台电脑为Linux。包括三个Name Node节点和五个Data Node节点, 节点间通过局域网通信协议方式进行数据交换。
1.2 Web日志挖掘预处理。Web日志数据预处理本文数据来自某计算机图书在线网站, 选取网站2015 年4 月份的后台日志作为挖掘对象, 日志大小为12.6GB, 保存方式为log文本。
数据清理、用户识别、会话识别、路径补充和事务识别是Web日志数据预处理的主要步骤。
数据清理的主要工作是删除与访问兴趣无关的用户痕迹, 主要通过后缀名去除图片文件, 过滤掉由网络爬虫采集的页面记录, 本文实验过程中选取了htm、html、asp、aspx四种文件格式来保留页面访问记录。数据清理留存了有效数据, 数据存放在User Data表, 存放在Mysql数据库中。数据字段包括访问时间、访问IP地址、访问页面时间等, 为用户识别做好铺垫。
经过数据清理后的数据总共有100 多万条记录, 记录存入User Data数据表中, 再陆续经过用户识别、会话识别、路径补充和事务识别后, 数据预处理完毕, 干净的数据可以为关联规则的发现做好准备。
1.3 高频访问模式发现[2]。本文使用改进的Map Reduce化的Apriori算法发掘高频访问集, 通过给单独网页项目赋予权重值, 较好的衡量了网页的重要程度, 方便高效地挖掘出了关联访问路径, 共发掘出2943 条有效关联规则。置信度、支持度是评价关联规则的重要指标。最小置信度反映了算法挖掘关联规则的效率, 同时满足最小支持度阈值和最小置信度阈值的关联规是强规则。
二、结论
本文通过经典Apriori算法相关思想和理论介绍, 分析和研究了经典Apriori算法的缺陷。提出了改进的基于加权的多支持度的Map Reduce化的Apriori算法, 通过在高频访问模式发现阶段使用改进的Map Reduce化的Apriori算法挖掘频繁访问集, 用实例详细描述了改进的Map Reduce化的Apriori算法流程和手段。个性化推荐关联规则算法实现了通过从服务器日志中提取互联网用户频繁访问集, 然后把频繁访问集通过梳理、存储进本地的MYSQL数据库, 通过对数据库的操作、梳理和分析实现了个性化推荐关联规则算法。
参考文献
[1]陈文.基丁-Fp树的加权频繁模式挖掘算法[J].计算机工程, 2012, 38 (06) :63-65.