挖掘算法

挖掘算法（精选十篇）

挖掘算法 篇1

数据挖掘 (Data Mining, 简称DM) 技术是一种能够自动和智能地把先前未知的、大量的和对决策有潜在实用价值的信息转化后予人有利的信息和知识的技术; 是智能化和数据库快速发展的产物; 是这几年国际上数据库与信息系统最前沿的研究方向之一。DM的主要算法有关联规则、聚类模式分析、时序模式、决策树、 神经网络算法等[1]。其中 , 关联规则是数据挖掘领域中一个重要的研究热点! 购物篮分析就是关联规则挖掘的一个典型案例。关联规则研究有利于发现交易数据库中不同项 (商品) 之间潜在的联系, 找出顾客购买行为模式, 如购买一种商品对另一种商品的影响。分析结果可以应用于商品货存安排、货架布局以及根据购买模式对用户进行分类。

1993年 , Agrawal等人首次提出了交易数据库中项集 (项的集合) 之间的关联规则问题, 其核心方法是基于频集理论的递推方法[2]; 之后 , 众多的研究人员和工作者对关联规则的挖掘问题进行大量深入的研究。有的工作包括对原有的算法进行优化[3], 如引入随机采样、并行的思想等 , 对关联算法进行推广; 有人 (如J.Han等) 独立于Agrawal的频集方法的工作, 以避免频集方法存在的一些缺陷, 探索挖掘关联规则的新方法。还有一些工作者 (如J.Kleinberg等) 注重于对挖掘到的模式的价值进行评估, 提出了一些值得努力的研究方向。

2 关联规则

设是项的集合。设数据库事务的集合D是由任务相关的数据构成, 其中每一个事务T都是项的集合, 使得成立。每一个事务都有一个标识符,称作TD。设A是一个项集, 事务T包含A当且仅当。关联规则是形如的蕴涵式, 其中, 并且A与B没有公共 项 , 即。规则在事 务集D中成立, 具有支持度s (support), 其中s是在事务集D中所占的百分比, 即概率。规则在事务集合D中具有置信度c (confidence), 也就是如果当D中包含A的事务, 同时也包含B的百分比是c, 即条件概率。显然,

(2.1)

(2.2)

称同时满足最小支持度阀值 (min_sup) 和最小置信度阀值 (min_conf) 的规则为强规则。

顾名思义, 项的集合称为项集, 包含项集的事物数目称为项集的频率或计数 (count)。如果项集的出现频率满足最小支持度, 则称该项集为频繁项集。

由概率统计知识 (2.2) 和相应的约定, 有

上式 (2.3) 表明: 一旦掌握A、B和的支持度计数,便能得到对应的关联规则和并能判断是否为强规则; 因此, 挖掘关联规则的问题可归结为挖掘频繁项集。

目前, 经典的关联规则挖掘算法几乎都是基于Apriori算法和Fp-Growth算法及其改进后的算法, 这些算法在关联规则挖掘中有着举足轻重的地位。因此, 下面分别介绍这两个经典的关联规则挖掘算法。

2.1 Apriori 算法的分析

Apriori算法运用逐层搜索的迭代方法 , 其中的k项集由(k-1) 项集探索寻找得到。首先 , 通过全面扫描数据库 , 累加计算每一个项的计数, 同时也收集满足最小支持度 (min_sup)的项, 并找出频繁1项集的集合, 记该集合为L1; 然后 , 用已经找出的L1寻求出频繁2项集的集合, 记这个集合为L2;接着使用L2找出L3,L4,…。按照这样不断迭代 , 直到再不能找到频繁k项集, 在找出每一个LK时都需要完整扫描一次数据库。为了改进和提高逐层生成频繁项集的效率, Apriori算法采用一种称作先验性质的重要性质来压缩搜索空间。

先验性质: 频繁项集的那些非空的子集也都必须是频繁的。

利用已知的LK-1项集来查找LK项集, 这个过程包括连接(join) 和剪枝 (prune) 两个步骤。

(1) 连接步骤 : 为了找出LK, 首先通过让LK-1与自身连接生成候选k项集的集合, 记该候选项集的集合为GK, 设l1和l2是LK-1中的项集。用记号lij表示lj的第j项。为了更加有效的实现, Apriori算法约定事务或项集中的项按照字典排序法排序; 对于 (k-1) 项集li, 把相应的项进行排序 , 使得li1

因为 (l1(k-1)

(2) 剪枝步骤: 称GK是LK的超集, 也就是说, GK的元素可以是也可以不是频繁的, 但所有的频繁k项集都包含在GK中, 扫描数据库, 确定GK中每个候选集的计数, 从而确定LK。

Apriori算法是通过限制候选产生发现频繁项集 , 因多次扫描数据库, 需产生和测试大量的候选项集; 如果能够减少或避免产生数目如此巨大的候选项集, 算法的效率必将大大提升, 而优化了的FP-Growth算法在产生频繁项集时不产生候选项集, 很大程度上提高了挖掘的效率。

2.2 FP-Growth 算法的分析

正如众人的希冀, 期待某种算法在产生频繁项集时不产生候选项集。一种有效改善的方法称为频繁模式增长 (Frequent-Patern Growth), 简称为FP-Growth.该算法 , 采用下述分治策略:

( 1) 将代表频 繁项集的 数据库压 缩到一颗 频繁模式 树(FP-树), 但该树仍需保留项集的关联信息。

(2) 将这种压缩后的数据库划分成一组条件数据库 (一种特殊类 型的投影 数据库), 每一个数 据库关联 一个频繁 项或“模式段”, 并分别挖掘每一个条件数据库 ; 对于每个“模式片段”, 只需考察与它相关联的数据库。

3 关联规则分类

自Agrawal等提出关联规则挖掘问题以后, 一批有效的挖掘关联规则的算法在过去几年中得到了长远的发展。其主要的研究方向有: 基于规则中涉及到的数据维数的挖 掘算法、基于规则中数据的抽象层次的挖掘算法、 基于规则中处理变量类别的挖掘算法和其他关联规则算法等。

3.1 按基于规则中涉及到的数据维数的挖掘算法划分

(1) 单维关联规则: 处理数据时只涉及变量的一个维度 (即一个变量)。其主要的算法有Agrawal等提出的Ariori, AIS算法、J.Roberto等提出的Max-Miner算法、J.S.Park等提出的DPH算法及基于以上方法优化的方法, 如Savasere等设计的基于划分 (partition) 的算法与Mannila等发现的基于采样的算法等等。

(2) 多维关联规则 : 处理数据时涉及多个维度 ( 即两个或两个以上的变量)。

3.2 按基于规则中数据的抽象层次的挖掘算法划分

(1) 单层关联规则 : 若关联规则中的某一项或某一属性只涉及一个概念分层, 则称此为单层关联规则; 否则, 就称为多层关联规则。

(2) 多层关联规则 : 相对单层而言 ; 涉及多个概念分层。主要算法有Han等提出的ML-T2L1算法及其变种算法。

3.3按基于规则中处理变量类别的挖掘算法划分

(1) 布尔型关联规则。

(2) 多值属性关联规则。

3.4 其他关联规则算法

除了以上枚举的关联规则, 还有一些研究方向, 如图像的关联规则发现算法、并行发现算法、加权关联规则算法等。

4 挖掘关联规则的步骤

关联规则的挖掘问题可以分解为以下步骤:

( 1) 频繁一项 集的生成 。根据给 定的支持 度找出支 持度≥min_sup的项, 为频繁一项集。

(2) 循环处理。第k步根据k-1步频繁的k-1项集LK-1按照Apriori_gen产生的候选k项集GK, 对候选的k项集计算每一项的支持度, 找出支持度≥min_sup的项, 作为频繁k项集。

(3) 按照规则结论中的项目数把规则进行分类 , 计算每类中各个的置信度, 找出置信度≥给定置信度min_conf的规则即可。

5 关联规则算法研究现状与挖掘效率比较

自1993年Agrawal等人提出 关联规则 的挖掘问 题以来 ,该领域的众多研究者对该问题进行了大量、深入的研究工作;截止当前, 已取得包括: 动态项目计数法算法、增量式更新算法、多值关联规则挖掘算法、并行/分布式挖掘算法、多层关联规则挖掘算法、基于约束的关联规则挖掘算法、基于概念格的关联规则挖掘算法和多循环方式挖掘算法 (层次挖掘算法) 等等在内的主要研究成果。而Brin等人提出动态项目计数法算法, 具有较好的并行性能等优点; 存在的不足是在应用中存在若干问题, 如对数据分布较敏感, 对区间的选择较敏感, 动态计数过程中存在误差累计效应等; 增量式更新算法主要有, 当目标数据库发生变时的更新与指定的最小支持度和最小置信度发生变化时的更新两类。其好处为在最低支持度为绝对数且不变的条件下, 只需考察所有真子集均为频繁项目集, 而本身却不是频繁的项目集, 但其仍需存储相关的频繁项目集, 来减少关联规则的更新消耗; 多值关联规则挖掘算法的形式为:, 前件与后件都是对应单一数值, 而不是区间, 算法比较简单, 但若需挖掘所有属性之间的关联规则时, 会面临规则的组合爆炸问题; 多循环方式挖掘算法的核心思想是“层次算法”, 主要包括Apriori算法、DHP算法、分区算法、抽样算法和FP-Growth算法; 其中J.S.Park等提出的DHP算法利用Hashing技术有效地改进候选频繁项集的生成过程, 产生比以前算法更小的候选频繁项集, 同时缩减数据库规模, 减少I/O时间, 比起Apriori算法的效率有明显提高。文献[10]表明: FP-Growth算法对不同长度(下转第23页)的规则都有很好的适应性, 大约比Apriori算法快一个数量级。

而对于大 家常见的10种关联规 则算法 : Apriori算法、AIS算法、SETM算法、Apriori Tid算法、Apriori Hybrid算法、DHP算法、Partition算法、FP-Growth算法、DLG算法和AVM算法的挖掘性能进行分析、比较。其中AVM算法效率最高[11],但只适用于布尔类型的关联规则; SETM算法效率最低, 但它与DBMS集成的最好。显然, 当支持度降低时, 生成的频繁项集增多, 所有算法执行的时间均延长。

6 结语

18大经典数据挖掘算法小结 篇2

2015-03-05 CSDN大数据 CSDN大数据

csdnbigdataCSDN分享Hadoop、Spark、NoSQL/NewSQL、HBase、Impala、内存计算、流计算、机器学习和智能算法等相关大数据观点，提供云计算和大数据技术、平台、实践和产业信息等服务。本文所有涉及到的数据挖掘代码的都放在了github上了。

地址链接: https://github.com/linyiqun/DataMiningAlgorithm 大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望能够帮助大家学习。

1.C4.5算法。C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42395865 2.CART算法。CART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法，详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42558235 3.KNN(K最近邻)算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42613011 4.Naive Bayes(朴素贝叶斯)算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42680161 5.SVM(支持向量机)算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42780439 6.EM(期望最大化)算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42921789 7.Apriori算法。Apriori算法是关联规则挖掘算法，通过连接和剪枝运算挖掘出频繁项集，然后根据频繁项集得到关联规则，关联规则的导出需要满足最小置信度的要求。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43059211 8.FP-Tree(频繁模式树)算法。这个算法也有被称为FP-growth算法，这个算法克服了Apriori算法的产生过多侯选集的缺点，通过递归的产生频度模式树，然后对树进行挖掘，后面的过程与Apriori算法一致。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43234309 9.PageRank(网页重要性/排名)算法。PageRank算法最早产生于Google,核心思想是通过网页的入链数作为一个网页好快的判定标准，如果1个网页内部包含了多个指向外部的链接，则PR值将会被均分，PageRank算法也会遭到Link Span攻击。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43311943 10.HITS算法。HITS算法是另外一个链接算法，部分原理与PageRank算法是比较相似的，HITS算法引入了权威值和中心值的概念，HITS算法是受用户查询条件影响的，他一般用于小规模的数据链接分析，也更容易遭受到攻击。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43311943 11.K-Means(K均值)算法。K-Means算法是聚类算法，k在在这里指的是分类的类型数，所以在开始设定的时候非常关键，算法的原理是首先假定k个分类点，然后根据欧式距离计算分类，然后去同分类的均值作为新的聚簇中心，循环操作直到收敛。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43373159 12.BIRCH算法。BIRCH算法利用构建CF聚类特征树作为算法的核心，通过树的形式，BIRCH算法扫描数据库，在内存中建立一棵初始的CF-树，可以看做数据的多层压缩。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43532111 13.AdaBoost算法。AdaBoost算法是一种提升算法，通过对数据的多次训练得到多个互补的分类器，然后组合多个分类器，构成一个更加准确的分类器。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43635115 14.GSP算法。GSP算法是序列模式挖掘算法。GSP算法也是Apriori类算法，在算法的过程中也会进行连接和剪枝操作，不过在剪枝判断的时候还加上了一些时间上的约束等条件。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43699083 15.PreFixSpan算法。PreFixSpan算法是另一个序列模式挖掘算法，在算法的过程中不会产生候选集，给定初始前缀模式，不断的通过后缀模式中的元素转到前缀模式中，而不断的递归挖掘下去。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43766253 16.CBA(基于关联规则分类)算法。CBA算法是一种集成挖掘算法，因为他是建立在关联规则挖掘算法之上的，在已有的关联规则理论前提下，做分类判断，只是在算法的开始时对数据做处理，变成类似于事务的形式。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43818787 17.RoughSets(粗糙集)算法。粗糙集理论是一个比较新颖的数据挖掘思想。这里使用的是用粗糙集进行属性约简的算法，通过上下近似集的判断删除无效的属性，进行规制的输出。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43876001 18.gSpan算法。gSpan算法属于图挖掘算法领域。，主要用于频繁子图的挖掘，相较于其他的图算法，子图挖掘算法是他们的一个前提或基础算法。gSpan算法用到了DFS编码，和Edge五元组，最右路径子图扩展等概念，算法比较的抽象和复杂。

高敏感度网页效用挖掘算法研究 篇3

关键词：敏感度；数据库；计算

中图分类号：TP182 文献标识码：A文章编号：1007-9599 (2011) 06-0000-01

High Sensitivity Web Utility Mining Algorithm Research

Lin Zhu,Zhang Peng

Abstract:With the emergence of the Internet media,and rapid prosperity,many problems follow.Mining the effectiveness of this

"utility" concept introduced to measure the degree of sensitivity on the page method,the key words of the sensitivity and the sensitivity of web content as the basis for the quantitative study,sensitive keywords presented based on the sensitivity of group pages method,and then be able to effectively identify and distinguish the importance of sensitive pages.

Keywords:Sensitivity;Database;Calculation

一、网页敏感度挖掘模型

（一）相关概念及定义

1.数据挖掘。是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程[1]。2.文本挖掘。是一个从非结构化文本信息中获取用户感兴趣或者有用的模式的过程。3.向量空间模型。将每一篇文档都映射为一组规范化的正交词条矢量组成的向量空间中的一个点，将词作为文档的特征。4.tf-idf。用以评估一个词对与一个文档集中一篇文档的重要程度，词的重要性与它在文件中出现的次数成正比，但同时与它在文档集中出现的频率成反比。5.Web挖掘。涉及Web，数据挖掘，文本挖掘，计算机语言学等多个领域的一项综合技术[2，3]。6.效用。作为数据项本身有用性和重要性的一种综合度量，反映了数据项的重要程度。7.效用挖掘。是数据挖掘的一个分支，其挖掘的目标是找到高效用的项集。8.敏感词表。将用户指定的敏感词集合按一定的检索顺序排列而成的词表。本文根据敏感词对社会危害程度、影响范围等因素将词表分为四级：普通（Ⅳ级）、严重（Ⅲ级）、非常严重（Ⅱ级）和警报（I级）等四级，并分别赋予不同的权值。9.否定词表。将不是、从不、没有、不能、几乎不等表示否定意义的形容词集合。否定词效用表是在否定词表的基础上赋予一定的权值而得到的词表。

（二）网页敏感效用计算模型

将经过处理的网页内容看作向量空间模型中的一个向量，将敏感词表和否定词表中的词看作项，词的效用值看作项的主观价值，将一个词在一篇网页中出现的频率看作该项在该事物中的客观值。具体定义如下：

W={w1，w2，…，wm}，由敏感词表中的敏感词所组成的集合，wi为敏感词。

N={n1，n2，…，nm}，由否定词表中的否定词所组成的集合，ni为否定词。

D={D1，D2，…，Dm}，由VSM中的空间向量所组成的数据库，每个向量代表一个网页的内容。

o（wp，Dq），客观值，为敏感词wp在网页Dq中出现的频率值。

f（np），否定词值，为否定词np在否定词表中的效用值，由用户设定。本文f（np）=–1。

e（wp，Dq），否定客观值，否定词集N在网页Dq中敏感词wp第n次出现时，在wp前第一个分句标点到敏感词wp范围内出现的频率值为Mn。

s（wp），敏感度值，为敏感词wp在词表中的敏感级别，由用户设定，反映出词的敏感程度。s（wp）>s（wq）说明s（wp）比s（wq）影响力更强。敏感度值独立于数据库D。

u（wp，Dq），效用公式u（wp，Dq）=e（wp，Dq）s（wp）

s（X，Dq），网页Dq的敏感度，s（X，Dq）=

ε，网页敏感度阀值，由用户设定。对于网页Dq，如果s（X，Dq）>ε，则称之为高敏感度网页，反之为低敏感度网页。

二、敏感网页挖掘系统的设计与应用

（一）系统设计

系统流程如下图所示：1.系统通过网络蜘蛛从互联网上抓取网页，得到网页集合；2.对得到的网页集进行网页清洗、分词、去停用词，并保留网页url，得到网页文本集合；3.使用tf-idf权重模型建立向量空间模型；4.使用敏感词效用表及否定词效用表对网页向量敏感度进行计算，得到敏感向量集合；5.与用户预设的敏感度阈值进行比较，只保留高于阈值的敏感网页向量，并按敏感度由高到低的顺序进行排序，得到最终的敏感向量结果集合；6.使用保留的url信息将文本向量还原成网页返回给用户。

（二）实验结果

实验数据采用经人工筛选的包含敏感网页的新闻网页的数据集作为样本。并设定本系统的高敏感度关键词集阀值为2.5%，关键词敏感度级别值为W1=8、W2=4、W3=2、W4=1。

经更换样本空间反复测试，本算法结果查准率和查全率均在96%以上。并能够按照敏感程度由高到低排序。给互联网网络管理者提供了很大程度的方便。

三、需要注意的问题

在建立向量空间模型时，只保留敏感词前第一个分句标点到敏感词范围内的否定词。在计算否定客观值e（wp，Dq）时，否定词频率以相加计数的方式累计到其后面出现第一个敏感词的Mn上。

参考文献：

[1]Jiawei Hn,Micheline K,etc.数据挖掘概念与技术[M].范明,孟小峰等译.北京:机械工业出版社,2001

[2]李盛韬.基于主题的Web信息采集技术研究[D].北京:中国科学院计算技术研究所,2002

[3]林冬雪.基于改进向量空间模型的web信息检索技术研究[D].重庆:重庆大学工,2005

数据挖掘算法之关联规则算法的研究 篇4

数据挖掘是从大量的、不确定的、模糊的数据信息中挖掘到具有潜在应用价值的数据, 数据挖掘是从统计学、人工智能、模糊识别、数据库等领域发展起来的, 并从中挖掘出潜在的模式, 为决策者进行决策提供技术支持。

2、关联规则算法概述

关联规则挖掘是数据挖掘中的一个热门领域, 管理规则挖掘主要是指从大量的数据信息中发现项集之间的联系, 即找出事件中频繁发生的属性的子集以及各个子集之间的联系。关联规则挖掘是通过计算机自动从大量的数据信息中找出数据之间的联系。从计算机的角度进行分析, 计算机将相应的事件看做一个事务, 通过扫描每一个事务来确定其关联规则。

关联规则的定义如下所示:具有形式的蕴含式, 其中。置信度和支持度是衡量关联规则的关键因素。

3、关联规则算法的挖掘过程

关联规则挖掘是从各个事务中挖掘出满足需求的最小置信度和最小支持度的关联规则, 整个挖掘过程包含以下两个方面: (一) 从所有的事务中提取所有的频繁项集。频繁项集与项集的支持度有关系。找出频繁项集的目的是为了利用相关的算法来找出大于最小支持度的项集。 (二) 根据第一步中的频繁项集得到与之对应的强关联规则。

4、关联规则算法

4.1 Apriori算法

Apriori算法在关联规则算法中的经典算法之一, 在关联规则官大中具有非常大的影响力。Apriori算法算法利用逐层迭代的搜索方法找到数据信息中所有的频繁项集。首先, 对事务数据库进行扫描, 从而得到频繁1-项目集的集合L1, 第二次对L1数据库进行扫描, 确定出频繁2-项目集的集合L2, 根据此方法进行迭代, 直到找不到频繁k-项目集为止, 停止扫描。在此过程中, 每一次找到一个项目集的集合Lk都需要对数据库进行一次扫描。Aprior算法以递归统计的方式形成频繁项集, 思路相对比较简单, 易于实现。然而, 在每次对候选项集数据库进行全面扫描时都会产生一个候选项集, 且扫描次数过多, 影响算法的时间复杂度和空间复杂度。当数据库中存放着大量的事物数据信息时, 由于计算机的内存是有效的, 当系统的输入输出负载增大的情况下, 扫描数据库的时间会增加, 从而使得扫描效率变低。

4.2 APriori Tid算法

APriori Tid算法与Apriori算法有类似的地方, 都是用前一次扫描形成的频繁项集作为下一次扫描的数据库, 而不需要考虑其他事务。然而, APriori Tid算法在对全局的事务数据库进行第一次扫描后, 就不需要利用数据库对数据项集的支持度进行计算, 而是利用生成的集合项集来对数据项集Lk的支持度进行计算。当某一个事务中不包含任意候选项集时, 该事务的标识符则不包含在Lk中。因此随着扫描的不断进行, 需要扫描的数据库就逐渐减小, 从而有效的提高了APriori Tid算法的运行效率。

4.3 DHP算法

DHP算法是对APriori算法的改进, 是在散列表的基础上形成的候选集。在对数据库进行一次扫描后, 会得到候选K-项集的支持度, 并形成频繁K-项集, DHP算法对任意一个事务进行分析, 并利用哈利函数的规则, 将其可能的 (K+1) 项集以散列表的形式进行呈现。在该散列表中, 每一栏的信息都包含所有经过散列规则而映射到散列表中的信息。以散列表为基础, 可以形成相应的位向量, 如果在该散列表中该栏的数字比候选项集的最小支持度小, 则散列表中该栏对应的位置标为0, 反之则将其标为1。这种方法可以对下一次形成的候选集进行过滤, 从而减少下一次扫描时候选集的规模。因此, 在一定的条件下, DHP算法会提高相应的运行效率。

4.4 FP-growth算法

FP-growth算法即频繁模式增长算法, 该算法是为了应对Apriori算法中形成大量候选频繁项集的一种方法, FP-growth算法只需要对数据库扫描两次, 在对数据库进行第一次扫描后, 会生产频繁1-项集, 在对数据库进行第二次扫描时, 会根据频繁1项集对数据库中的非频繁项集进行过滤, 与此同时可以得到FP-tree, 即包含了所有的频繁项集, 接下来就是在得到的FP-tree中进行递归算法, 从而得到任意一个频繁模式。FP-growth算法构造出了具有紧凑特点的FP-tree, 在FP-tree中保存了有关频繁模式的所有数据信息。FP-tree中仅仅存在长度为1的节点信息, 频度高的节点距离树的根节点较近, 这种特点也加快了扫描的效率。FP-growth算法降低了扫描的次数, 减少了扫描数据库时的输入输出次数, 同时也大量的减少了候选项集的出现, 效率有了很大程度的提升。

5、结语

关联规则挖掘是数据挖掘中的一个研究热点, 对着互联网技术的不断提升, 关联数据挖掘在遇到巨大机遇的同时也面临着巨大的挑战。关联规则挖掘还有许多可以改进的地方, 应该不断加强对数据挖掘的研究, 以期对数据挖掘的应用进行扩展, 提高数据挖掘的效率。

参考文献

[1]芦海燕.数据挖掘中关联规则算法的研究[J].电脑知识与技术.2011, 7 (26) :6324-6325.

[2]陈莉平, 屈百达.基于关联规则的数据挖掘算法的研究与应用[J].2009 (20) :71-73.

挖掘算法 篇5

关键词：数据挖掘 属性约简 重要度

数据挖掘是从海量的且不断动态变化的数据中，借助有效的方法挖掘出潜在、有价值的知识过程。而粗糙集理论它是一种刻画不完整性和不确定性的数学工具，能在保持分类能力不变的前提下，通过知识约简从中发现隐含的知识，揭示潜在的规律，是由波兰科学家Pawlak在1982年提出的。而属性约简是粗糙集理论研究的核心内容之一，它能保证在分类能力不变的情况下，消除重复、冗余的属性和属性值，减少数据挖掘要处理的信息量，提高数据挖掘的效率。本文提出了通过计算单个属性的重要性，以重要性大于零的属性为核，来选取其它属性加入核中形成新的集合RED，直至剩下的所有属性的重要性为零，得到的集合REDn即为属性约简。粗糙集的基本理论[1-2]

定义1设 是一个信息系统，其中 是对象的非空有限集合，即;是属性的非空有限集合;，是属性 的值域;是一个信息函数，即每个对象在每个属性上对应的信息值。若，其中 为非空有限条件属性集合，为非空有限决策属性集合，且，则称信息系统为决策表。

定义2对决策表，，考虑单决策属性的情况，即，则的分辨矩阵是一个 矩阵，其中的元素定义如下：

定义3对分辨矩阵中每个，用布尔函数 来表示，若，则决策表的分辨函数 可定义为：。基于粗糙集的数据挖掘的属性约简算法[3-4]

2.1 算法分析

第一步：求核。通过求条件属性C中的每个属性a对在整个条件属性集C的重要性SigC(x)来确定属性核CORE(x)，重要性SigC(x)>0的属性为核属性。

第二步：通过向属性核CORE(x)中依次加入重要性大的属性来确定属性集x的最小约简，详细步骤如下：(1)把a加入到属性集R 中，计算重要性，选择重要性最大的属性;(2)如果两个属性有相同的重要性，取离散值小的属性。

2.2 算法复杂度

通过算法的分析，在对决策表进行划分的时间复杂度为O(n2)。而计算条件属性的重要性也是满足划分的线性关系，因此所求属性核的时间复杂度为O(n2)，依次添加次重要度的属性也没有增加额外的开销，因此整个时间复杂度还是O(n2)。

2.3 实例及分析

为了进一步验证算法的可行性，下面以表1中的决策表为例进行分析说明，其中对象集，条件属性集，决策属性。

以上对计算出的实验数据的重要性进行统计得出信息系统的两个约简为{c1,c4}和{c2,c4}。结语

本文针对属性约简算法中的属性重要度的计算来确定核，适合对海量数据的挖掘，不仅节省了存储空间，而且在时间复杂度开销少，通过实验分析验证了算法的可行性与有效性，为决策表的属性约简提供了一条高效的途径。

参考文献：

[1]张文修,吴伟志.粗糙集理论与方法[M].北京:科学出版社,2001:18-19

[2]周献中,黄兵，李华雄,等.不完备信息系统知识获取的粗糙集理论与方法[M].南京:南京大学出版社,2010:10-11

[3]饶泓,夏叶娟,李娒竹.基于分辨矩阵和属性重要度的规则提取算法[J].计算机工程与应用，2008,44(3):163-165

挖掘算法 篇6

摘要：在Web信息检索中，如何能够提取出与某个主题信息相关的网页变得异常重要，web结构挖掘作为web数据挖掘的一个重要方面，主要挖掘web潜在的链接结构模式，通过分析一个网页链接和被链接数量以及对象来建立web自身的链接结构模式，可以用于网页归类，本文探讨了Trawling算法在Web结构挖掘中的应用。

关键词：Trawling算法 web 数据挖掘 结构挖掘

0 引言

随着互联网的飞速发展，人们越来越多地在互联网上发布和获取信息。web已经成为信息制造、发布、加工和处理的主要平台，其涵盖的信息面之广阔、信息量之丰富、都使得它毫无疑问地成为当前最大的信息资源库。随着海量信息涌入万维网，互联网中特有的许多问题，诸如超大规模的非结构化文档数量、良荞不齐的网页质量，包含在文档中的大量多媒体信息，甚至相当含糊或不规范的用户查询表示等，必然给检索数据带来很大的困难。因此，在Web信息检索中，如何能够提取出与某个主题信息相关的网页变得异常重要。将传统的数据挖掘技术跟web结合起来，进行web挖掘活动将更有效的从web中抽取感兴趣的、潜在的、有用的信息。web挖掘是一项综合技术，涉及了统计学、人工智能、模式识别、并行计算、机器学习、数据库等多个领域。web结构挖掘作为web数据挖掘的一个重要方面，主要挖掘web潜在的链接结构模式，通过分析一个网页链接和被链接数量以及对象来建立web自身的链接结构模式，可以用于网页归类，并且可以由此获得有关不同网页间相似度及关联度的信息，有助于用户找到相关主题的权威站点。

1 Web数据结构挖掘

1.1 web数据挖掘 web数据挖掘起源于数据挖掘，数据挖掘(Data Mining)是指从大型数据库的数据中提取人们感兴趣的知识，而这些知识是隐含的、事先未知的、潜在的有用信息。数据挖掘的提出最初是针对大型数据库的，但是从更广泛的角度来讲，数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。因而，数据挖掘的对象不仅仅可以是数据库，还可以是任何组织在一起的数据集合，如www信息资源等。WWW以超文本的形式给用户提供了包含从技术资料、商业信息到新闻报道、娱乐信息等多种类别和形式的信息，可以说是web当今世界上最大的电子信息仓库，蕴含着巨大潜在价值的知识。然而，Internet是一个具有开放性、动态性、异构性的全球分布式网络，资源分布分散，没有统一的管理和结构，这就导致了信息、知识获取的困难，即所谓的Rich Data poor Information的问题。因此，运用现有数据挖掘技术对分布的、异构的web信息资源进行挖掘，就成为了数据挖掘技术的挑战和未来的发展方向，由此产生了基于web的数据挖掘。web数据挖掘(web Data Mining)，简称Web挖掘，是一项综合技术，涉及web、数据挖掘、计算机语言学、信息学、数据库技术等多个领域。web数据挖掘是针对包括web页面内容、页面之间的结构、用户访问信息、电子商务信息等在内的各种web数据源，在一定基础上应用数据挖掘的方法以发现有用的隐含的知识的过程。

1.2 Web数据结构挖掘 在逻辑上可以把Web看作是位于物理网络之上的一个有向图G=(V，E)，其中节点集V对应于Web上的所有文档，而有向边集E则对应于节点之间的超链接(Hyperlink)。对节点集作进一步的划分，V={Vi，Vj}所有的非叶节点Vij是HTML文档，其中除了包括文本以外，还包含了标记以指定文档的属性和内部结构，或者嵌入了超链接以表示文档间的结构关系。叶节点Vi可以是HTML文档，也可以是其他格式的文档。Web上信息的多样性决定了Web知识发现的多样性，当前Web上的信息主要分为三类:①Web页面中的内容，包括文本信息和各种多媒体信息；②Web页面中超链接之间相互引用的数据；③Web服务器上的用户登录网站的访问日志数据。

由此Web数据挖掘可以分为Web内容挖掘(web Content Mining)、web结构挖掘(Web Strueture Mining)、Web使用挖掘(Web usage Mining)三大类（图1）。

Web结构挖掘即挖掘Web潜在的超链接结构模式，通过分析一个网页链接和被链接数量以及对象来建立Web自身的链接结构模式。这种模式可以用于网页归类，并且由此可以获得有关不同网页间相似度及关联度的信息，帮助用户找到相关主题的权威站点。Web结构挖掘的主要内容在于超链接分析，即通过分析页面的链接关系来研究网页的引用关系。超链接分析最早被用于搜索引擎，它的基本原理就是通过统计分析互联网上哪些页面被链接的次数多，那么该网页就被认为是比较重要的页面或者权威页面(Authority Pages)。与传统的搜索引擎使用的基于词频统计的查询结果排序算法相比，基于超链接分析的算法的优势在于它提供了一种客观的、不容易作弊(一些Web文档通过增加不可见的字符串用来欺骗传统搜索引擎)的Web资源评价方法。Web结构挖掘还应用于网站架构上，一个架构完善的网站可以提高使用者浏览的兴趣、吸引更多的使用者上线浏览。此外，Web结构挖掘还可以用于对Web页进行分类，预测用户的链接使用以及链接属性的可视化，对各个商业搜索引擎的Web页数量进行统计分析等。

2 基于有向二分图的Trawling算法在Web结构挖掘的应用

拖网(trawling)算法是建立在web页面上集心页面与权威页面的二分图关系上的。它从二分有向图的角度对互联网上的社给出了一种明确的定义描述。根据随机二分图的理论，一个足够大而稠密的随二分图将以很高的概率包含一个完全二分有向图，那么如果将某个社区的链接构看作一个大而稠密的二分有向图，则社区的核就可以用一个完全二分有向图complete bipartite graph)来表示。具体到互联网环境中，可以对上述概念有如下观的理解:如果在互联网上存在一个某种主题的社区，那么这种二分的核必将含在其中。一个二分有向图是这样一个图:图Kij的节点集合可以被分为两个集合，用(ran)和c(center)来表示。集合F中有i个节点，集合C中有j个节点，并且合F中的每个节点到集合C中的每个节点都存在一条有向边。拖网算法数据来源不是依据某个主题，而采用的是一般的爬取结果，通过扫描数据集合发现所有潜在的Fan集合，同时也确定了Center集合。然后通过重复的包含/排除剪枝得到所有的核，最后采用关联规则挖掘算法(Priorial gorithm)聚类为较小规模的核的集合。最后，每个核就是一个社区。

拖网算法为:①获取数据源，如web搜索结果的备分；②删除所有重复或镜像页面，以防产生虚假网站核；③由于只考虑那些潜在的网站，所以删去入度超过某一值(比如50)的所有）center；④考虑每一条边，对于指定的有向完全二分图的要求，或者产生一个相应的网站核，或者删除这条边，无论如何，都将移去这条边；⑤对于扫描到的较小规模的网站核，即有向完全二分图，滤去那些fans中包含来自同一个域的多个fans的结果；⑥一个有向完全二分图的任何真子集都是有向完全二分图，通过aPriori算法发现所有更大规模的网站核；⑦对于找到的网站核，使用HITS算法将他们扩展为真正的网站。HITS(Hypertext Indueed Topic Seareh)算法是关于超链接的检索算法。该算法通过对网络中超链接的分析，利用页面的被引用次数及其链接数目来决定不同网页的权威性。Hub和Anthority的关系可以用图2来表示:

因此，一个Hub页应该指向许多好的权威页，而被许多Hub页指向的一定是权威页。HITs算法中网页的Anthority权重和Hub权重有相互增强的关系。HITS算法的实现过程:根据用户查询请求，首先用一个现有的商业搜索引擎进行查询，取其部分查询结果(约200个左右)作为算法的根集(RootSet)，记为RQ。由于这些页面中的许多页面是假定与搜索内容相关的，因此它们中应包含指向最权威页面的指针。所以，对RQ中每一个节点，将所有指向该节点或该节点所指向的网页补充进来形成基集(BaseSet)，记为BQ。计算BQ中每一个网页的Anthority权重和Hub权重，这是一个递归的过程。

拖网算法中使用的共同引用过于严格而排除了一些可能的潜在网站，造成有用网站的遗漏。通过宽松引用(relaxed-cocited)重新定义了稠密二分有向图和完全二分有向图，使得一些原来被排斥在外的页面包括进来。拖网算法是针对整个Web爬取结果进行的，因此，发现的网站较为完整。而且，拖网的结果是客观的，与主题无关。

参考文献：

[1]Gordons.Linoff Michael J.A.Berry等著.沈钧毅，燕彩蓉等译.Web数据结构挖掘:将客户数据转化为客户价值.北京.电子工业出版社.2004.

[2]秦拯，张玲，李娜.改进的PagcRank在Web信息搜集中的应用.计算机研究与发展.2006(6).

业务流程挖掘算法研究 篇7

目前,大多数企业使用信息系统来支持业务流程的执行,如工作流管理系统( WFMS) 、企业资源规划系统( ERP) 、客户关系管理系统等。这些信息系统可能包含显式的流程模型,也可能仅支持流程所涉及的任务而无需定义显式的流程模型,或仅仅保留了执行任务的轨迹。然而,这些信息系统都可以自动生成执行日志来记录业务流程的实际执行情况。流程挖掘的目标就是从这些执行日志中自动发现和流程有关的信息。挖掘结果可用于设计一个新的业务流程,或者作为反馈工具审计、分析和改进现有的业务流程。因此,流程挖掘对实现业务流程的优化和智能管理有着十分重要的意义[1]。

流程挖掘分为三个视图[2]: 控制流视图、组织视图和实例视图。其中,控制流视图关注流程中活动的执行顺序和控制流结构,常用的建模语言[2,3]有WF-net、C-net、EPCs、BPMN和YAWL等。组织视图关注流程的资源信息,如哪个活动由哪个执行者实施以及它们之间的关系。目标是发现和展示人之间的关系,即建立一个社会关系网。实例视图关注与流程实例相关的属性,既可用活动表示,也可用实例中的执行者表示,还可以用流程处理的数据对象来表示。本文仅从控制流角度论述流程挖掘技术的关键问题和研究现状。文献[1]仅介绍了较早期的部分工作流挖掘算法。针对近几年国内在流程挖掘综述方面的文章较少,本文较全面地介绍了具有代表性的流程挖掘算法,包括基于遗传算法的流程挖掘、基于日志分类的挖掘算法和基于执行模式的挖掘算法。从日志完整性、控制流结构、噪声处理和模型质量控制等方面对它们进行了分析和比较。

1 流程挖掘的基本概念

1. 1 日志

流程挖掘的输入是执行日志,表1 是一个会议流程的执行日志。每一行表示一个事件,记录了与事件有关的各种信息,如: 该事件对应的活动,事件发生的时间等,用事件ID标识。实例是流程的一次执行过程,用实例ID标识,每个事件属于某一实例。如果只关注流程的控制流视图,一个实例可用其所有事件所对应的活动序列来表示。因此,可对表1 中的日志进行化简,化简后的日志如表2 所示。表中共包含6 个流程实例,14个活动。

日志的形式化定义[3]如下:

定义1 设T是活动的有限集合,σ ∈ T*是一条活动序列,L ∈ B( T*) 是一个流程执行日志。其中,T*表示集合T的Kleene闭包。

例如: T = { a,b,c,d} ,L = [< a,b,c,d >3,< a,b,c,d >2,< a,b,c,d >]是一个包含6 个实例的执行日志。

1. 2 流程模型表示方法

流程的控制流结构可用不同的建模语言[2]来描述,如:WF-net、C-net、Process Tree等。不同挖掘算法使用的流程模型表示方法也不同,例如: α 系列算法使用的是WF-net,启发式算法使用的是C-net,而基于遗传算法的流程挖掘使用的是Petri网或Process Tree。因此,算法具有各自的表达偏好。这些建模语言之间可以相互转换,也可以转换成语义表达能力更强的高级流程建模语言,如YAWL、BPMN、EPCs等。高级建模语言一般提供给业务人员建模使用,本文不做介绍。下面介绍几种常用的流程模型表示方法。

1. 2. 1 工作流网WF-net( Workflow Net)

首先,介绍经典的Petri net[4],它是由库所和变迁这两类节点组成的二部图,节点之间通过有向弧连接。形式化定义如下:

定义2一个Petri网是一个三元组(P,T,F),其中:

(a)P是一个有限的库所集;

(b)T是一个有限的变迁集;

(c)是弧的集合。

Petri网的状态通常被称为标记,是token在各库所的分布情况的描述。Petri网在执行过程中,变迁根据触发规则[31]改变Petri网的状态。

标签化的Petri网是一个五元组( P,T,F,A,l) ,其中( P,T,F) 同定义2,A是一组活动的集合,l ∈ T → A是Petri网中变迁到活动的映射。直观地,就是为Petri网中的变迁打上活动的标签,变迁一旦被触发则说明对应的活动也被执行。

定义3 一个标签化的Petri网PN = ( P,T,F,A,l) 是一个工作流网WF-net[2],当且仅当:

(a)存在一个起始库所i∈P使得;

(b)存在一个终止库所o∈P使得;

(c)每个节点都位于从i到o的一条路径上。

若对会议流程日志( 表2) 使用合适的挖掘算法,得到的流程模型如图1 所示。

图1 中,矩形表示变迁,圆圈表示库所,变迁和库所之间使用有向弧连接。每个库所上都标有活动的名称,当触发库所时,相应的活动被执行。根据定义3,该流程是一个WF-net。

定义4一个WF-net N = ( P,T,F,A,l) 是一个SWFnet[2],当且仅当:

( a) 对于所有的p ∈ P,t ∈ T,( p,t) ∈ F,若| p·| > 1,则|·t | = 1 ;

( b) 对于所有的p ∈ P,t ∈ T,( t,p) ∈ F,若|·t | > 1,则|·p | = 1 ;

( c) 不存在隐式库所。

1. 2. 2 Causal net ( C-net)

Causal net表达流程中活动和活动之间的依赖关系。每个活动有一组输入约束和输出约束。如图2 ( a) 所示,活动a是开始活动,因此,没有输入约束,输出约束是{ b,d} 和{ c,d} ,表示执行活动a后,执行b和d,或者c和d。活动e是结束活动,没有输出约束,输入约束为{ b,d} 和{ c,d} ,说明在执行活动e之前,执行了b和d,或者c和d。

与图2( a) 中的C-net等价的WF-net模型如图2( b) 所示。它们所有的可执行流程实例相同,有< a,b,d,e > ,< a,c,d,e > ,< a,d,b,e > ,< a,d,c,e > 。以下是Causal net的形式化定义。

定义5 Causal net[2]是一个六元组(A,ai,ao,D,I,O)。

其中:

A是活动的有限集合;

I∈A→AS是活动的输入约束;

O∈A→AS是活动的输出约束;

例如,图2( a) 所示的Causal net,

1. 2. 3 流程树

流程树[5]也可作为流程模型的表示方式。其中,节点分为叶子节点和非叶子节点。叶子节点( 也称为活动节点) 表示活动。非叶子节点( 也称为操作节点) 表示流程的控制流结构。四种控制流结构的流程树表示方法如图3 所示。→ × ∧分别表示顺序、选择、并行和循环结构。

使用流程树表示的流程模型是一种“块结构”的流程模型,其最大的好处是流程可避免死锁。

2 流程挖掘中的关键问题

2. 1 控制流结构

以WF-net为例,常用的控制流结构包括: 顺序结构、并行结构、选择结构、循环结构、非自由选择结构[6]、隐式活动和重复活动。会议流程的WF-net模型( 图1) 包含了上述所有的控制流结构。观察执行日志( 表2) ,若参会者坐火车前往开会,则同样坐火车返回; 若开车前往,则同样开车返回。可见,返程的方式取决于前去开会的方式。在图1 中,库所i后面的选择不是由前面的“返程”活动决定,而是由库所c后面的活动决定。若库所c后选择的是坐火车,则库所i后选择的也是坐火车; 若库所c后选择的是开汽车,则库所i后选择的也是开汽车,这称为是非自由选择结构。另外,流程中两个活动的名称相同,导致了重复活动。在日志中,有的参会者在会上没有发表演讲,这通过隐式活动实现。隐式活动是WF-net模型中黑色的矩形,常用来辅助实现某些控制流结构。在日志中,有的参会者没有提问,而有的提问多次,这通过循环结构实现。

流程挖掘算法应当尽可能多的支持各种控制流结构。但由于各种因素,如: 日志信息不完整、建模语言表达能力有限,算法本身的局限性等,算法可能无法处理某些控制流结构。

2. 2 日志噪声和不完整性

大多数挖掘算法假设日志数据是正确的。但实际上,由于流程执行异常或日志记录错误,日志数据往往存在一些噪声。噪声的特点是出现频率低。利用这个特点,一种方法是对日志进行预处理,或对结果模型进行“剪枝”。但这种方法没有体现算法本身的健壮性,而有些挖掘算法本身能够处理日志噪声,如启发式算法、遗传挖掘算法等。

日志的完整性对挖掘结果也起到重要的作用。但实际上,某些合法的流程实例可能没有记录在日志中。例如,流程模型中有10 个可并发执行的活动,要满足日志完整性,则至少包含10! 条流程实例,但实际上可能只有其中1000 条流程实例被记录在日志中。如果模型中存在循环结构,则可执行的流程实例无穷多,显然不可能全部记录在日志中。日志完整性可分成不同级别[7],不同的挖掘算法对日志有不同的完整性要求。

( 1) 全局完整性GC: 流程模型描述的所有可能的流程实例都至少在日志中出现一次。通常情况下,全局完整性是一种理想情况,很多情况下日志信息是不完整的或者不可能做到完整,例如流程中有循环结构时。

( 2) 继发完整性DS: 任何两个允许相继执行的任务,它们相继执行的流程实例至少在日志中出现一次。

( 3) 2 元短循环完整性DS + : 若活动a和b组成长度为2的循环结构,则序列< a,b,a > < b,a,b > 必须至少在日志中出现一次。

( 4) 长循环完整性DS ++ : 长循环指流程中包含长度大于2的循环结构。长循环的实例必须至少在日志中出现一次。

( 5) 频率完整性FS: 日志中记录流程实例发生的次数。因此,通过日志可以得出哪些活动经常相继发生。

2. 3 日志多样性

日志多样性指由于流程本身错综复杂而导致日志中的实例也呈现出复杂多样的特征。例如,医疗系统的执行日志就存在多样性的特点。因为每位患者的病情、体质或者经济状况都不同,采取的治疗手段也互不相同。如果使用传统的流程挖掘算法,得到的流程模型结构非常复杂、难以理解。

一种解决方法是采用聚类方法对日志中的执行实例进行聚类从而产生多个子日志,降低日志的多样性。然后对每个子日志分别实施已有的挖掘算法。这种方法得到的模型结构大大简化,但得到的不是完整的流程模型。另一种方法是抽取日志中的通用执行模式( 活动序列片段) ,根据模式对日志进行迭代化简,然后对化简后的日志和执行模式分别施用已有的挖掘算法得到层次流程模型。

2. 4 流程模型质量评价

通常从四个方面[8,9,10]来评价流程模型的质量: 重现度、精确度、通用性和简单性。

重现度: 指流程模型对日志中执行实例的可重现程度。给定一个流程模型和一个执行实例,如果执行实例可通过执行该流程获得,则称该流程可重现该实例。流程模型可重现的执行实例越多,对日志的重现度就越高。

精确度: 如果通过执行流程模型可以产生许多日志中不包含的实例,那么该流程模型的精确度就较低,称为弱拟合。

通用性: 与精确度相反,通用性指流程模型不仅反映日志中的行为,还允许日志以外的正确行为。这是因为实际应用中,日志通常是不完整的。好的流程模型应当有这样的“预见性”使得新的执行实例符合流程模型的规范。如果通用性过低,称流程模型过拟合。

简单性: 在保证其他三个指标的情况下,流程模型越简单越好。可从模型中节点的数量或节点的出入度等方面来评价。

精确度和通用性存在一定程度的对立,精确度较高的流程模型,通用性往往较差,反之亦然。简单性与精确性和通用性也有一定的关系,通常通用性较高的模型结构较简单,而精确性较高的模型结构较复杂。如何使流程模型质量在这四个方面达到一种平衡,或者能够控制这四个方面的不同需求也是流程算法应该解决的问题。

3 流程挖掘算法

3. 1 直接算法

这类算法的基本思想是: 首先,扫描日志中的所有实例,抽象出活动之间的基本关系。然后,根据基本关系的类型,直接构造流程的控制流结构。这类算法的代表是 α 及其扩展算法[6,11,12,13,14],包括 α、α+、α+ +、α#、α*等。

以 α 算法[13]为例,活动之间的基本关系有:

根据四种基本关系,构造控制流结构。构造方法为: a → b:顺序结构; a >Lb,a >Lc,b#Lc: 选择分叉; a >Lc,b >Lc,a#Lb: 选择合并; a >Lb,a >Lc,b‖Lc: 并行分叉; a >Lc,b >Lc,a‖Lb : 并行合并。

α 算法无法处理长度为2 的短循环结构。因为对< a,b,a,b > 这样的活动序列,α 算法抽象出两种基本关系: a >Lb和b >La。根据构造方法把a和b做并行结构处理。事实上,α 算法的结果流程模型是不包含短循环结构的SWF-net,且流程中没有隐式活动和重复活动。

α+算法[11]是对 α 算法的第一次扩展,它能够处理 α 算法不能处理的长度为1 或2 的短循环结构。为了识别长度为2 的循环活动序列,α+算法首先扩展了活动之间的基本关系:

a△Wb: 当且仅当存在一个流程实例 σ = t1,t2,…,tn,i ∈{ 1,…,n - 2} ,ti= ti +2且ti = 1= b ;

a◇Wb: 当且仅当a△Wb且b△Wa 。

然后对原来的三个基本关系a →Lb,a‖Lb,a#Lb也作了相应的改进。α+算法的具体过程是: 先识别日志中长度为1 的循环活动序列,将它们暂时从日志中过滤掉。对过滤后的日志,使用与 α 算法相同的方法得到中间模型。然后,将长度为1 的循环结构添加到相应的位置。α+算法的结果流程模型是不带隐式活动和重复活动的SWF-net。

α 与 α+算法关注的是活动之间的直接( 显式) 依赖关系。而在有些流程中,两个非直接相邻的活动之间也可能存在依赖关系,即隐式依赖。α+ +算法[6]考虑了依赖距离大于1 的隐式依赖关系,因此能够处理非自由选择结构。α+ +算法的关键是快速有效地发现任意两个活动之间的隐式依赖。

α#算法[12]是对 α+算法的扩展,能够处理隐式变迁。如图1 所示,一个黑色的变迁上没有标识对应的活动,该变迁称为隐式变迁。通常,隐式变迁是为了保证WF-net的正确性,或构造复杂控制流结构而加入的。隐式变迁分为SIDE,SKIP和SWITCH三种类型。α#算法先抽象活动之间的虚假依赖关系,再根据构造规则,构造出三种不同类型的隐式变迁。

α*算法[14]用于处理重复活动。在WF-net中,如果变迁T到活动A的映射是1 对1 关系,即不存在多个变迁映射到一个活动的情况,则流程不存在重复活动。α、α+、α+ +、α#算法均不能处理重复活动。如表2 中的第1 个实例: < 开始,准备,坐火车,开会,提问,参观,晚宴,返程,坐火车,结束> ,当扫描到第3个活动“坐火车”时,不能确定该活动是对应模型( 图3) 中的哪个“坐火车”变迁。α*算法是对 α 算法的扩展,在抽象活动之间关系的同时,记录了活动的上下文活动。因此,可通过上下文环境判断日志中的活动对应WF-net中的哪个变迁。

3. 2 启发式算法

α 及其扩展算法虽然分别能够处理各种控制流结构,但却不能处理日志中的噪声。而在实际应用中,日志中的噪声是不可避免的。噪声出现的原因可能是日志记录错误或流程执行异常等,日志噪声的存在将影响算法最终的挖掘结果。启发式算法[15,16]考虑流程实例在日志中出现的频率,可用于挖掘流程的主要行为,忽略各种细节或异常处理,也可用于处理日志噪声。启发式挖掘算法可处理的常用控制流结构: 顺序、并行、选择、循环和非自由选择结构。启发式算法的流程表示是C-net ( A,ai,ao,D,I,O) 。

第一步计算活动之间的依赖度,计算公式如下:

其中,| a >Lb | 表示a >Lb在所有流程实例中出现的总次数。

长度为2 的循环结构的依赖度的计算公式如下:

其中,表示序列< a,b,a > 在所有流程实例中出现的总次数。计算结果的取值范围是- 1 到1。越接近1,说明依赖程度越强。越接近0,说明依赖程度越弱。

第二步设定阈值,构造依赖图。假设包含五个活动a,b,c,d,e的执行日志L = [< a,e >1,< a,b,c,e >10,< a,c,b,e >10,< a,b,e >1,< a,c,e >1,< a,d,e >1,< a,d,d,e >2,< a,d,d,d,e >1],两两活动之间相继执行的次数如表3 所示,根据式( 1) 计算得到的活动之间的依赖度如表4 所示。设阈值为0. 7,则依赖度大于0. 7 的两个活动之间用有向弧连接,如图4( a) 所示。例如,| a >Lb | = 0. 92,则活动a到活动b之间有一条有向弧,箭头指向活动b,表示b依赖于a 。同时,弧上标明了活动之间的依赖度。

第三步在依赖图基础上进一步确定并行和选择分支。假设依赖图中活动a有三个输出b、c和e。如果b和e是并行结构,则序列< e,b > 和< b,e > 在日志中多次出现。如果b和c是选择结构,则序列< b,c > 不可能出现。因此,计算aLb ∧ c ,公式如下:

计算值越接近1,说明b和c越可能是并行结构,如果越接近0,说明b和c越可能是选择结构。可设定一个阈值,当计算值大于阈值,作并行结构处理; 小于阈值,则作选择结构处理。计算。若设阈值为 0. 8,则活动b和c之间是并行结构,得到C-net模型,如图4 ( b) 所示。它是在依赖图的基础上,进一步标识活动之间的并行或选择关系。

3. 3 遗传算法

遗传算法[5,17]是一种模拟生物进化过程的搜索技术。首先,随机产生一组初始种群,利用适应值函数计算个体的质量,对质量优良的个体做杂交变异操作形成新一代种群。重复这一过程,直到满足终止条件。由于搜索空间不受限制,所以遗传算法可以同时处理各种控制流结构。基于遗传算法的流程挖掘的关键是: ( 1) 流程模型的表示方式; ( 2) 评价流程模型的适应值函数; ( 3) 遗传算子( 杂交、变异) 。

可用流程树[5]作为流程模型表示方式。遗传算法适应值函数将四个质量指标( 见2. 4 节) 综合起来,使得产生的结果模型具有较高的综合质量,适应值函数的计算公式为:

其中,Fr、Pe、Gv和Sm分别为流程模型在重现度、精确度、通用性和简单性四方面的计算值。w1、w2、w3和w4分别是四个质量指标的权重。用户可以根据自己的偏好设置流程模型在这四方面的权重。利用适应值函数计算当前流程模型的适应值,按照一定比例将适应值最高的多个流程模型直接保留到下一代。其余的流程使用锦标赛方法选出并通过杂交变异产生。具体方法如下:

( 1) 杂交

参与杂交的两棵流程树随机选择各自的子树进行交换。已知两棵流程树P1、P2,随机选中各自的一棵子树,如图5 所示,P1 选中子树st1,P2 选中子树st2。将两棵子树交换后,得到两棵新的流程树P1'和P2'。

( 2) 变异

变异分为以下三种情况: 节点变异、删除活动节点、添加活动节点。

节点变异包括操作节点( 非叶子节点) 变异和活动节点变异。对于操作节点,改变其控制流结构类型; 对于活动节点,改变其代表的活动类型。例如,将流程树P1 中的代表并行结构的操作节点( 节点E的父节点) 变成顺序结构,变异结果如图6( b) 所示; 将P1 中活动节点D的活动类型变成C,变异结果如图6( c) 所示。

删除活动节点时,为了保证流程树的正确结构,有时需要同时删除其父节点。例如,要将流程树P1 中的活动节点E删除,需要同时删除它的父节点,并将节点F变成节点G的兄弟节点,变异结果如图6( d) 所示。

添加活动节点指随机产生一个活动节点,将它添加到任意一个操作节点下。为了保证流程树的正确结构,有时需要同时添加父节点。例如,在流程树P1 中,将活动节点C添加到活动节点D的父节点下。在该父节点下创建一个同样代表顺序结构的操作节点,将节点C和D添加到该操作节点下,变异结果如图6( e) 所示。

遗传算法虽然能够处理各种控制流结构和日志噪声,但由于初始种群是随机产生的,因此结果流程也具有随机性,可能得不到最优的流程模型。

3. 4 基于日志分类的算法

日志的多样性导致已有的流程挖掘算法得到的流程结构错综复杂,难以理解。为了解决这个问题,一种方法是对日志中的执行实例进行聚类,将其划分成多个子日志,然后对各子日志施用已有的挖掘算法。这种方法的关键在于如何对执行实例进行聚类。聚类的好坏将影响最终的挖掘结果。

聚类的基本方法[8,18]是: 根据某种规则构造执行实例的特征向量,如: 实例中各活动( 或一组活动) 出现的次数、处理的数据对象或性能参数等。假设日志L = [< a,b,d,e,f,g > ,< a,b,c,e,g > ,< a,b,d,e,f,g > ,< a,b,c,d,g > ,< a,b,c,d,e,g > ,< a,b,d,g > ],按照活动出现与否构造实例的特征向量,如表5 所示。

利用已有的相似度计算方法,如: 欧几里得距离、汉明距离、Jaccard距离等,计算各特征向量之间的相似度。利用已有的聚类算法对这些执行实例进行聚类,形成多个子日志。

采用以上方法对聚类后的子日志施用已有的挖掘算法得到的是局部流程。要得到完整的流程模型,可使用3. 5 节的方法挖掘层次流程模型。

3. 5 基于执行模式的算法

解决日志多样性问题,还有一种方法是挖掘层次模型[19],挖掘步骤如图7 所示。首先,通过分析日志中的所有执行实例,发现所有最大重复活动序列片段,即通用执行模式[20]。然后,通过活动映射得到通用执行模式的等价类[21]。利用Hasse图构造等价类之间的偏序关系。Hasse图的顶端节点即为模式摘要。

重新扫描日志,将所有执行实例中属于某摘要的通用执行模式用一个抽象活动代替。对处理后的日志施用已有的挖掘算法,得到完整的流程模型。其中,某些活动是抽象活动,代表子流程的位置。对属于同一模式摘要的所有通用执行模式施用挖掘算法得到子流程。

已知通用执行模式有{ ab,ac,bc,aad,add,aba,abc,acb,acd} 。按照活动将它们映射成等价类[21]: [{ a,b} ] = { ab,aba} ,[{ a,c} ] = { ac} ,[{ b,c} ] = { bc} ,[{ a,d} ] = { aad,add} ,[{ a,b,c} ] = { abc,acb} ,[{ a,c,d} ] = { acd} 。利用等价类之间的包含偏序关系构造Hasse图,如图8 所示。

图8 中,{ a,b,c} 和{ a,c,d} 是Hasse图中最上层的顶点,因此作为模式摘要。处理日志实例时,顶点{ a,b,c} 及其所覆盖的所有子节点{ a,b} ,{ a,c} ,{ b,c} 所对应的通用执行模式用抽象活动A表示; 顶点{ a,c,d} 及其所覆盖的子节点{ a,d} 所对应的通用执行模式用抽象活动B表示。节点{ a,c} 同时被{ a,b,c} 和{ a,c,d} 包含,可人为规定{ a,c} 属于{ a,b,c} 。对抽象处理后的日志可进一步抽取模式摘要,用它对当前日志进一步处理得到新的抽象日志。不断重复以上操作,可获得各层次的抽象日志。对顶层日志施用已有的挖掘算法得到全局流程模型。对各层次的模式摘要所对应的通用执行模式施用挖掘算法得到各层次的子流程。

4 算法比较

第3 节介绍了经典的流程挖掘算法的实现原理,以及它们各自的适用范围和局限性。本节将从日志完整性( cmp) ,控制流结构,如: 顺序结构( seq) 、选择结构( cho) 、并行结构( par) 、循环结构( loo) 、非自由选择结构( nfc) 、重复活动( dup) ,以及噪声处理等方面对这些算法进行分析和比较,比较结果如表6 所示。基于日志分类和执行模式的算法都是对日志进行预处理,挖掘阶段仍使用现有的流程挖掘算法,因此处理控制流结构的能力与选用的具体挖掘算法有关。

α 算法只能处理长度大于2 的长循环结构,而不能处理长度为1 或2 的短循环结构。因此,在表6 中,α 算法的“loo”项为“√/ × ”,表示只能处理部分循环结构。

表7 对从处理日志噪声、日志多样性和模型质量控制等方面对算法进行了比较。启发式算法和遗传算法能够处理日志噪声。模型质量方面,一般的流程挖掘算法得到结果流程模型后,可通过一致性检查计算四个维度的模型质量。而遗传算法可通过调节适应值函数中的权重控制结果模型在四个质量维度上的表现。基于日志分类和执行模式的算法能够很好地处理日志多样性问题。

5 结语

流程挖掘技术作为流程再设计和分析的一项关键技术,为流程变化管理和诊断提供了良好的解决方案。本文总结了流程挖掘中遇到的关键问题,介绍了5 种流程挖掘算法,并从日志完整性、控制流结构、处理噪声、模型质量控制等方面对它们进行了分析和比较。

高效用项集挖掘算法综述 篇8

频繁项集挖掘是数据挖掘研究中的一个重要技术, 它适用于多种类型的数据库, 如事务数据库、数据流数据库及时间序列数据库等。为了解决现实数据库中不同的项分布不均衡及不同的项的重要程度不完全相同的问题, 研究人员在经典的Apriori算法[1,2]的基础上, 提出了改进算法——加权关联规则挖掘[3,4]。然而, 在加权关联规则算法中, 由于项集没有随项集增长或减小而具有某种向上或向下的封闭性, 从而导致算法并不高效。针对这一问题, 研究人员又提出了加权向下封闭的概念。尽管加权关联规则算法考虑了项之间的区别, 但在一些实际应用场合, 如在事务数据库中, 加权关联规则算法并没有将项的出现频数考虑在影响最终挖掘结果的因素之内。因此, 研究人员提出了效用项集挖掘[5,6]来解决上述问题。

效用项集挖掘是通过一定的策略, 挖掘满足条件的项集。在进行挖掘前应事先定义需要挖掘的目标, 再给定一个最小效用值作为判定条件。找出数据库中所有超过最小效用值的项集的过程就是效用挖掘, 其找出的项集则被称为高效用项集。在引入效用之后, 科研人员发现, 原来的频繁项集可能在这种评估模式中对目标贡献较小, 但挖掘得到的项集却更具有针对性。因此, 效用项集挖掘对一些实际应用场景中的决策问题起到了更直观、更直接的支持作用。

Yao H.等在2004年的论文中[7]提出了挖掘高效用项集的思想之后, 该领域的研究人员也陆续提出了若干种高效用项集挖掘算法, 本文对其中具有代表性的三个算法, 即IHUP算法[8]、UP-Growth算法[9]和HUI-Miner算法[10]进行了介绍、分析及优缺点比较。

1 相关描述

本文在此先对高效用项集挖掘中的问题描述及相关定义、定理进行介绍。对于一个有限项数的项目集合I={i1, i2, …, ik}, 并且该集合中的项目ip (1≤p≤k) 都有唯一确定的利润值p (ip) , 则将该项目的集合称为项集, 若项集含有k个项目, 则称其为k-项集。事务数据库D={T1, T2, …, Tn}是一组事务的集合, D中的每一个事务Td都有唯一的标识d, 称作TID。此外, 每一个事务Td都是I的一个子集, Td中的每个项目ip, 都关联一个数量q (ip, Td) , 用来表示项目ip在事务Td中出现了q次。

本文所使用的示例数据库如表1所示, 其中每个项目的利润值如表2所示[9], 本文假设所有利润值均为非负整数。

定义1项目ip在事务Td中的效用值用u (ip, Td) 表示, u (ip, Td) =p (ip) ×q (ip, Td) 。

例如, 在表1中, 项目A在事务T1中的效用值为u ({A}, T1) =5×1=5。

定义2项集X在事务Td中的效用值用u (X, Td) 表示, u (X, Td) =∑ip∈X∧X⊆Tdu (ip, Td) 。

例如, 在表1中, u ({AD}, T1) =u ({A}, T1) +u ({D}, T1) =5×1+2×1=7。

定义3项集X在数据库D中的效用值用u (X) 表示, u (X) =∑X⊆Td∧Td∈Du (X, Td) 。

例如, 在表1中, u ({AD}) =u ({AD}, T1) +u ({AD}, T3) = (5×1+2×1) + (5×1+2×6) =24。

定义4对于指定的最小效用阀值min_utility, 若存在u (X) ≥min_utility, 则称项集X为高效用项集, 否则将其称为低效用项集。

例如, 在表1中, u ({B}) =u ({B}, T3) +u ({B}, T4) +u ({B}, T5) =4+8+4=16, u ({BD}) =u ({BD}, T3) +u ({BD}, T4) =16+14=30, 若min_utility=30, 则{B}是一个低效用项集, 而{BD}则是一个高效用项集。

定义5事务Td在数据库D中的效用值用TU (Td) 表示, TU (Td) =u (Td, Td) 。

例如, 在表1中, TU (T1) =u (T1, T1) =u ({ACD}, T1) =8。

定义6项集X在数据库D中的事务加权效用值用TWU (X) 表示, TWU (X) =∑X⊆Td∧Td∈DTU (Td) 。

例如, 在表1中, TWU (A) =u (T1, T1) +u (T2, T2) +u (T3, T3) =8+27+30=65。若存在TWU (X) ≥min_utility, 则称项集X为高事务加权效用项集。

定理1事务加权向下闭合[8]。若项集X不是高事务加权效用项集, 则项集X的任何超集都不是高效用项集。需要注意的是, 在此定理中需要计算的是项集X的事务加权效用值。

例如, 在表1中, 若存在TWU (X) <min_utility, 则项集X的任何超集的事务加权效用值均低于min_utility。

2 算法综述

2.1 IHUP算法

IHUP算法是基于树结构存储的算法, 该算法使用树结构来记录项目的基本信息和效用信息。IHUP算法包括两个阶段, 在第一阶段, 需要计算出每个事务的事务效用TU, 例如, 事务T1的事务效用为8。然后需要找出数据库中所有的项目, 并计算其事务加权效用TWU。每一个项目的事务加权效用是包含该项目的所有事务的事务效用总和, 例如, 项目{A}出现在事务T1、T2和T3中, 它们的事务效用分别是8、27和30, 所以, 项目{A}的事务加权效用为65。接下来, IHUP算法会删除那些TWU小于最小效用阀值的项目, 由定理1可知, 删除掉的这些项目的任何超集都不是高效用项集, IHUP算法中将TWU不小于最小效用阀值的项集称为HTWUIs。例如, min_utility为40时, 则项目{C}, {E}, {A}, {B}, {D}为HTWUIs。那么对于每一个事务而言, IHUP算法会将每个事务中的项目按TWU降序排列, 并将事务中低效用项集的项目删除, 在本文的示例中, 删除了项目{F}和{G}。需要注意的是, 此处仅删除了事务中的若干项目, 每一个事务的效用值的计算仍然按照完整的项目进行计算。按照上述操作后的“新”数据库信息如表3所示。

之后, IHUP算法将每一条事务插入和FP-树结构类似的IHUPTWU-树中。树结构的每个节点上均记录了某个项目的出现次数及事务加权效用值, 如图1所示[9]。

在第二阶段, IHUP算法将再次扫描原始数据库, 通过识别HTWUIs来确定高效用项集及其效用值。

相较IHUP之前的一些算法, 该算法占用的内存更小, 执行速度更快;IHUPTWU-树结构具有“一次创建, 多次挖掘”的特性;从本文描述的算法的两个阶段可以看出, IHUPTWU-树结构最多只需扫描数据库两次;大量的性能分析显示, IHUPTWU-树结构在增长式和交互式高效用项集挖掘中是非常高效的;此外, I-HUP算法具有一定的可扩展性, 可以用于处理项目和事务量较大的数据。

尽管如此, IHUP算法在第一阶段依然会产生大量候选项集, 这将严重影响第二阶段的效率;并且当数据库中包含大量的含项目数较多的事务或含大量的低于最小效用阀值的项目时也会严重影响算法的挖掘效率。

2.2 UP-Growth算法

为了解决IHUP算法中存在的问题, Vincent S.Tseng等提出了高效用项集算法UP-Growth[9]算法。算法中提出了四个策略, 分别是DGU (Discarding Global Unpromising items) 、DGN (Discarding Global Node utilities) 、DLU (Discarding Local Unpromising items) 和DLN (Discarding Local Node utilities) , 这些策略有效的减少了第一阶段产生的候选项集。

与IHUP算法的不同之处在于, UP-Growth算法在计算出各个项目的TWU之后, 使用DGU策略减少每一个事务的事务效用。从表3中可以看出, IHUP算法仅仅是对事务进行了重组, 即只删除了低效用项目, 而在DGU策略下, 不仅要删除这些低效用项目, 同时数据库中的每一个事务效用也仅仅计算了事务中保留下来的高效用项目的效用和, 如表4所示。

接下来, 使用DGN策略创建树结构UP-树, UP-树的结构类似于IHUP-树, 其不同于IHUP-树的地方在于UP-树中树节点的效用要比IHUP-树中树节点的效用小很多, 通过本文上面介绍的DGU策略, 很容易理解树节点保存的效用值变小的原因, 如图2所示[9]。

通过DGN策略有效的减小了树节点的效用值后, UP-Growth算法将会构造条件模式基和本地UP-树。和FP-Growth算法不同的是, UP-Growth算法使用DLU策略来构造条件模式基, 因此, 本地UP-树中树节点的效用值可以进一步减少。UP-Growth算法在第一阶段产生的候选项集大幅小于IHUP算法产生的候选项集, 所以该算法在第二阶段的挖掘过程中性能得到了提升。

实验表明UP-Growth算法性能大大优于IHUP算法, 并且对于大型数据库有良好的可扩展性。尤其是当数据库中包含大量的项目数量较大的事务时, UP-Growth算法的在某些数据集上执行速度比IHUP算法快不止10, 000倍[9]。

2.3 HUI-Miner算法

由于大多数高效用项集挖掘算法是先产生候选项集, 再从候选项集中识别出高效用项集, 如IHUP算法、UP-Growth算法等。尽管不同的算法会采取不同的策略, 但这些算法的实现过程中仍然会产生大量的候选项集, 并且大部分候选项集并不是高效用项集, 这将大大影响算法挖掘效率。因此, Liu等人提出了高效用项集挖掘算法HUI-Miner[10], HUI-Miner提出了使用效用列表的结构, 用来储存项集的效用信息和修剪HUI-Miner的搜索空间的检索信息。

在HUI-Miner算法中, 每一个项集都有一个效用列表。通过两次扫描数据库, 初始效用列表保存了数据库的效用信息。首先, 通过扫描数据库, 计算事务加权效用, 删除掉事务加权效用小于最小效用阀值的项目, 并将高事务加权效用的项目按降序排列。通过第二次扫描数据库, HUI-Miner算法构造了初始效用列表, 列表中保存了TID、Iutil (项目在事务中的效用) 、Rutil (事务中除去某项目后的事务效用) 信息, 如图3所示。

无需再次扫描数据库, 通过插入项目的效用列表即可构造2-项集效用列表;通过不断插入项目的效用列表可以构造k-项集效用列表。构建初始效用列表之后, 如同Eclat算法[11]挖掘频繁项集一样, HUI-Miner算法可以从效用列表中高效地挖掘出所有高效用项集。

在高效用项集的挖掘过程中, 完全检索可以发现所有的高效用项集, 但由于许多数据库中的项目数量庞大, 所以该检索过程会耗费大量的时间。假设一个数据库中有n个项目, 那么完全检索则需检索2n个项集。为了减小检索空间, 需要有效利用项集效用列表中的Iutils和Rutils。算法中规定若Iutils和Rutils的总和超过最小效用阀值, 则该项集为高效用项集, HUI-Miner中项集是否需要被修剪掉的关键依据是判断该项集是否为高效用项集。

通过避免对大量候选项集的产生和效用计算, HUI-Miner可以通过效用列表高效的挖掘高效用项集。通过对不同数据库进行实验, 结果表明HUI-Miner在执行速度和内存占用情况均优于那些通过产生候选项集来挖掘高效用项集的算法。

3 总结与展望

目前, 高效用项集挖掘已经取得了令人瞩目的成绩, 但对下列问题的研究工作仍是具有挑战性的。

(1) 列存储的数据库的挖掘。目前大多数高效用项集挖掘是基于事务数据库的算法, 挖掘所用的数据或是文本数据, 或是传统的行存储的数据, 列存储有区别于行存储的特点及优势, 所以设计应用于列存储的数据库的高效用项集算法也将是十分有意义的工作。

(2) 制定更加合理的衡量高效用项集的标准, 现有的高效用项集挖掘算法对效用的设定均为非负数, 也应考虑当项集效用为负数时, 现有的衡量标准、挖掘策略是否依然合理、可行。

(3) 可视化挖掘。设计一个灵活、易于操作的交互界面, 并可以对挖掘的结果进行丰富的可视化展示, 使普通用户也能方便的进行挖掘工作。

(4) 并行高效用项集挖掘。随着实际应用场景中的数据量的不断增长、数据的复杂度不断提高、分布式存储及并行计算的广泛应用, 再加上挖掘系统本身的一些局限性, 并行的高效用项集挖掘算法的研究工作也具有很大的挑战。

基于矩阵算法的关联规则挖掘 篇9

现有关联规则挖掘算法主要有三大类,它们是Apriori算法、DHP算法和PDM算法(并行挖掘算法),其它的算法多是对这三种算法的改进[1]。

Apriori算法是由Agrawal和Srikant提出的[2],是传统的应用最广泛的关联规则挖掘算法。算法使用频繁项集性质的先验知识,k项集用于探索k+1项集。算法过程是首先通过扫描数据库,对每个项计数,找出频繁1项集L1,用L1再去找L2,如此下去,直到不能再找到频繁项集,每找一个频繁项集都要扫描一次数据库[3],在扫描数据库上要用较多的时间。

DHP算法与Apriori算法相似,也是用k项集探索k+1项集,不同的是DHP算法循环计数时建立一张Hash表,生成候选集时通过Hash表对候选集进行过滤,从而大大减少候选集的规模,提高算法的效率。

PDM算法应用于分布式数据库系统的数据挖掘中,PDM算法是对DHP算法的并行化处理。

1 关联规则的概念

设D为事务数据库,I是D中所有项目的集合,D中包含若干个事务T,每个事务T包含若干个项目,每个事务T具有唯一的标识符TID。则D,I可以表示如下:

ij为属性项,简称项。其中j=1,…,m,表示D中共有m个项。

每个事务Ti是项集,Ti I,标识符为TIDi。

定义:设A,B是项集,且A∩B=,则蕴涵式AB称为规则。它最基本的意思是包含项集A的也趋向于包含项集B。

设D表示数据库中事务总数,support(A∪B)表示D中同时包含A和B的事务的数目,类似support(A)表示D中包含A的事务数目。

设支持度为

则称规则有支持度s。

设置信度c为

则称规则A B有置信度c。

项集的支持度表明了模式发生的频率,置信度表明了蕴涵的强度。

给定最小支持度Cmin和最小置信度Smin,如果规则A B同时满足c≥Cmin,s≥Smin,则称其为关联规则或强关联规则。一般Cmin和Smin由用户指定,挖掘关联规则就是从数据库找出那些满足最小支持度和最小置信度的规则。

关联规则的挖掘一般可分为如下两个步骤:

(1)产生所有满足最小支持度的项的组合,称为频繁项集。

(2)从频繁项集中产生所有满足最小置信度的规则,即生成关联规则。

第一步是关联规则挖掘的核心所在,首先要生成候选项集,满足最小支持度的候选项集就是频繁项集。目前的各种算法主要都是针对频繁项集的生成上,它需要对数据库进行扫描,计算支持数等,而且在生成的频繁大项集的时候会产生数量庞大的候选项集和频繁小项集,计算的工作量特别的大,耗费的资源也多,需要很多的优化处理。文献[4]介绍了生成频繁项集的几种优化算法。第二步则相对简单,因为最终生成的频繁大项集毕竟数量不多,在其上生成的规则也是有限的,只需要分别计算它们的置信度,满足最小置信度的就可作为关联规则。

2 矩阵算法

在Apriori算法中,寻找最大频繁项集需要对数据集进行多步处理,需要多次扫描数据库,使得算法的效率不高。矩阵算法在寻找频繁项集的时候只需要扫描一次数据库,生成由0和1组成的矩阵,之后的工作就是对矩阵的操作。

2.1 关系矩阵的生成

设项集I={i1,i2,…,in},事务集合T={t1,t2,…,tm}。则事务关系矩阵A按如下方式生成:矩阵A的每一个元素{aij}定义如下,

此矩阵共有m行n列,每一行表示一个事务,每一列表示一项。若事务ti包含项集I的第j项,则矩阵的第i行第j列的值为1,即aij=1,否则为0。把矩阵A还可表示成m个n维的行向量a1,a2,…,am,称之为事务向量。

下面举例说明矩阵的生成过程,如表1所示的事务数据,

由表1中数据我们可知I={I1,I2,I3,I4,I5},则生成的事务矩阵和事务向量为

a1={1,1,0,0,1}其它类似。

2.2 频繁项集的生成

频繁项集的生成是关联规则挖掘的核心,算法的性能和效率关键是对频繁项集这个问题的处理上。矩阵算法的频繁项集生成过程如下。

2.2.1 频繁1项集的生成

候选1项集C1中的元素由项集I中的所有单个项组成即

为了计算C1中每一个项集的支持数,把每一个项集表示为一个n维的行向量。如项集{ik}表示为向量Sk1={0,…,1,…,0}即第k个元素为1,其它的元素为0的向量,称之为项集向量,上标表示项的数量,2项集就表示为Sk2。上面例子中S11={1,0,0,0,0}。项集{ik}的支持数记为support({ik})

其中[,]表示两个向量的内积运算。项集支持数就是项集向量分别与每个事务向量做内积运算然后求和。项集{ik}的支持度记为Sk。

频繁项集用L表示,Lk表示频繁k项集。如果sk≥Smin则{ik}∈L1,由此生成频繁1项集L1。

2.2.2 频繁2项集的生成

候选2项集C2是通过频繁1项集L1与自身连接得到的,即表示自然连接。C2中的每一个元素都是形如{ik,ij},(k

为计算C2中每个项集的支持数,同样把C2中每个项集表示为一个n维的行向量。项集{ik,ij}对应的行向量为第k个和第j个元素为1,其它元素为0的n维向量,Sk2,j={0,…,0,1,0,…,0,1,0,…,0},其中为值为1的是第k和第j项。支持度计数用下式计算:

其中是向下取整运算,如取比其内值小的最大整数。同样sk,j=support({ik,ij})/如果sk,j≥Smin,那么{ik,ij}∈L2。从而可生成频繁2项集。

2.2.3 频繁k项集的生成

候选k项集Ck是通过频繁k-1项集Lk-1与自身接得到的(k>2)。设l1和l2是Lk-1中的项集。li[j]表示li中的第j项,j=1,2,…,k-1(例如,l1[k-2]表示l1的倒数第2项)。假定项集中的项按字典序排序,对于k-1项集中的li有li[1]

其中条件l1[k-1]

同样,把Ck中每个项集表示为一个n维的行向量。设Ck的元素形式为{ij1,ij2,…,ijk},把其表示成n维行向量为Skj1,j2,…jk={0,…,0,1,0…,0,1,0…,0},其中第ij1,ij2,…,ijk项元素值为1,其余为0。支持数按下式计算:

重复上面的过程,直到Ck和Lk为空集。经过k步,这个过程终止,得到所有的频繁项集的集合为

2.3 由频繁项集产生关联规则

产生关联规则有如下两个步骤:

(1)对于每个频繁项集l产生l的所有非空子集。

(2)对于l的每个非空子集m,如果

则有关联规则

3 结论

矩阵算法的使用的仍是支持度和置信度框架体系,和传统的Apriori算法产生频繁项集是一致的,由其产生的关联规则也是一致的。矩阵算法在支持度计数上采用了比传统Apriori算法更为有效的方法,不需要重复扫描数据库。生成频繁1项集所花费的时间比Apriori算法要多,因为需要扫描数据库生成矩阵和所需的相应向量,所以产生1项集的时候要进行扫描和转化两个操作,比Apriori算法多了转化的过程。但在后边的工作上矩阵算法则不需要扫描数据库,而扫描数据库是很费时间的,所以频繁大项集所含的项数越多矩阵算法表现出的优越性就越大,矩阵算法适合于较大规模数据库的关联规则挖掘。同时矩阵算法还具有良好的并行性和可伸缩性。

参考文献

[1]袁玉波,杨传胜,黄廷祝,等.数据挖掘与最优化技术及其应用.北京:科学出版社,2007

[2]Agrawal R,Srikant R.Fast algorithm for mining association rules.In:Proceeding1994International conference Very Large Data Bases(VLDB94).Santiago,Chile.Sept,1994:487—499

[3]颜雪松,蔡之华.一种基于Apriori的高效关联规则挖掘算法的研究.计算机工程与应用,2002;10:209—211

[4]谢廷婷.频繁集挖掘算法研究.计算机与现代化,2007;3:60—63

数据挖掘常用分类算法研究 篇10

数据分类技术在日常很多领域都有过应用, 譬如银行经常要使用分类模型来进行相应的商业评估;学校的教务系统要使用分类模型对学生的成绩以及各种评价来进行评估;研究生、博士生等发表论文, 使用数据挖掘分类模型来对各种期刊进行细致的分类, 这样才能有效的评价科研能力的好坏;还有例如百度、谷歌这样的大型搜索引擎, 提供的推荐功能, 分类技术已经融入了我们日常生活的方方面面, 各个领域也提出了很多分类算法理论。

最开始的数据挖掘分类算法都是基于内存的算法。经过长时间的发展, 数据挖掘算法也由使用内存开始逐步地使用外存以获得处理大数据的能力, 以下对一些经典的分类算法进行介绍。

1) 决策树分类算法

决策树分类算法是数据挖掘十分经典的分类算法。它使用自顶向下递归的方式构造决策树模型。决策树上的每一个结点都采用信息增益度量来选择所要测试的属性。也可以从已经生成的决策树上提取出分类规则。

2) 向量空间模型VSM算法

VSM的概念十分简单, 就是把对文本内容的处理转化为对空间向量中的向量运算,

而且可以使用空间中的相似度参数来表示文本中语义的相似度, 非常的直观简单。在向量空间模型中, 文本包含了各种机器可以读取的记录信息。不妨用D表示, 文本的特征集合可以表示为D (T1, T2, …, Tn) , 其中Tk是特征项, 1<=k<=N。当文本集合被表示空间模型时, 那么文本的相似度就可以表示为特征向量的内积。

VSM方法在预处理阶段需要进行大量的特征类别向量的计算, 而特征类别向量的建立由依靠类别向量所包含的特征项。当所包含的非零特征向量越多, 则每个特征向量的对于类别的表达能力越弱, 所以VSM向量空间模型算法适合进行文献的分类工作。

3) K最近邻分类算法

K最近邻分类算法是一种理论上成熟的方法。这个算法实现的思路很简单:假设一个样本在其特征空间中的K个最相似的样本均属于同一个类别, 则这个样本也属于该类别。这个算法只根据相邻最近的一个或者几个样本的所属类别来决定待分类样本的类别。

K最近邻分类算法虽然从原理上来说基于极限定理, 但在类别决策的时候, 却只与少量有限的样本有关。因此, 使用这种方法可以避免样本选择失衡的问题。另外, 由于K最近邻算法不是根据类域来确定样本的类别, 而是根据相邻的少量的样本来确定, 故对于样本类域的重合或相交的比较多的待分类样本集来说, K最近邻分类算法较其他算法更为适合。

K最近邻分类算法的应用范围十分的广泛, 包含分类和回归。对一个数据集样本进行分析得到该样本集的K个最近邻的样本, 然后将这些近邻样本的属性的平均值分配给该样本, 得到该样本的属性。

该算法一个比较大的缺点是, 当所选样本失衡时, 例如一个类域的样本容量非常大, 而其他类域样本容量又比较小时, 这就有可能导致当输入一个新样本时, 该样本的K个邻居中大容量类域的样本占多数。故而可以采用计算各个类域权值的方法 (和该样本距离小的邻居权值大) 来改进。该方法的另一个缺点是计算量比较大, 因为对每一个待分类的样本都要计算它到全体已知样本的距离, 才能求得它的K个最近邻点。现在的解决方法是, 对已知样本进行预处理, 对已知样本点进行剪切, 事先除去对分类作用不大的样本。该算法比较适合样本容量比较大的类域的自动分类, 而那些样本容量较小的类域采用这种算法比较容易产生误分。

4) 支持向量机SVM算法

支持向量机SVM分类算法具有良好的性能。该算法是一个建立在数学统计学基础上的机器学习算法。通过该算法, 可以自动找到那些对于分类有比较好的区分能力的向量, 通过使用该算法生成的构造器可以很好的提高分类的适应能力和分类的准确率。该算法需要通过各个类域的边界样本的类别来决定最后样本的分类结果。

SVM算法的重点是在数据集样本中确定一个超平面, 使得能够将数据集样本进行分类后分开, 因此, SVM算法又名最大边缘化算法。待分数据集样本中的大部分样本并不是支持向量, 所以, 减少或者除去这些样本对分类结果没有影响。当样本数据集的规模比较小时, 使用SVM支持向量机算法可以很好的得到分类结果, 效果很好。

2 决策树算法实例实现

决策树分类算法是数据挖掘分类算法中最先介绍的算法。决策树, 顾名思义就是用来做决定的树, 一个分支就是一个决策过程。每个决策过程中涉及一个数据的属性, 而且只涉及一个。然后递归地, 贪心地满足决策条件 (即可以得到明确的决策结果) 。

实现决策树算法首先需要有一些有价值的数据样本集 (能够通过该数据集预测出结果) 做训练, 通过分析样本数据得到每个属性对结果的影响大小。

我们通过使用信息增益的理论去描述它, 期间也涉及到熵的概念。

下面结合实例说一下决策树实现过程中的上述关键概念。

假设我们有如下数据:

1) 我们首先要通过计算找到哪个属性的所有属性值能更好地表达class字段的不同。通过计算, 我们发现house的属性值最能表现class字段的不同。这个衡量标准其实就是信息增益。计算方法是:首先计算全部数据的熵, 然后除class之外的其他属性逐个遍历, 找到熵最小的那个属性 (house) , 然后将全部数据的熵减去按照house属性划分数据之后的数据的熵。

这个值如果满足条件假如 (>0.1) , 我们认为数据应该按照这个节点进行分裂, 也就是说这个属性 (house) 构成了我们的一次决策过程。

2) 再按照house分裂的每个数据集上, 针对其他属性 (house除外) 进行与1) 相同的过程, 直到信息增益不足以满足数据分裂的条件。这样, 我们就得到了一个关于属性数据划分的一棵树。可以作为class字段未知的数据的决策依据。

3) 经过编码运行后得到实验结果如下图:

根据该决策树的输出, 我们可以得到如下的挖掘规则:首先根据house属性判断, 当house属性为1时, 走到索引为2的节点, 此时该节点是叶子节点, 预测值class为1.

4) 决策树算法的评价

根据上面实验的分析, 我们可以发现决策树的一些优缺点:决策树算法所产生的分类规则十分的易于人理解, 准确率很高;但是在构建决策树的过程中, 需要对数据集进行多次的扫描排序, 效率还有待进一步提高。

3 总结

本文主要先详细介绍了数据挖掘分类技术目前的常用经典算法, 后面部分主要描述了决策树算法的实现, 决策树算法是一个基于信息熵理论的具有良好性能的分类算法。该文通过对数据的分析, 然后通过编程实现决策树算法对该数据进行处理, 得到一个决策树的结构, 根据该树可以归纳得到分类规则, 最后可以得到评价结果。决策树算法对数据无任何前置要求, 应用在金融和教育产业中效果也比较好, 故发展前景十分良好, 可以继续深入研究。

参考文献

[1]郭超峰, 李梅莲.基于ID3算法的决策树研究与应用[J].许昌学院学报, 2007 (2) .

[2]Pang-Ning Tan, SteinBach M, Kumar V.数据挖掘导论[M].范明, 范宏建, 译.北京:人民邮电出版社, 2007.