频繁特征模式挖掘（共6篇）
频繁特征模式挖掘 篇1
1基于市场行为的时间序列切分及表示方法
为了对原始时间序列数据进行维约简, 传统的时间序列数据建模通常采用分段表示的方法,整体可划分为2类:基于时域的分段表示方法与基于变换域的分段表示方法。
对于本文的基本研究对象———商品期货, 为充分还原其主要的市场特征,即单边运行模式及震荡情形,本文引入数理统计中线性回归的思想,基于市场行为,对时间序列进行切分处理。
在对时间序列数据进行切分时, 针对每个子序列进行线性回归,当切分得到的子序列的回归判定系数R2大于设定的阈值r时 , 可将时间序列中的下一个数据点加入该子系列中继续计算,否则,可将当前数据点视为切分断点,从该数据点开始搜寻下一个子序列,直至整个序列搜索完毕或到达最新时间点。 对于切分后得到的数据,长度达到3及以上的子序列,即可视为市场单边模式序列,采用线性回归结果进行描述;对于切分断点,相连即得到市场震荡点序列。
以伦敦金属交易所(LME)交易品种之一的伦铜期货为主要研究对象,将2001年1月2日至2015年5月12日的伦铜指数日交易数据的收盘价作为样本, 进行数据的切分处理以及后续的规律挖掘,其中回归判定系数阈值r设定为0.7。
具体可获得3 632个交易日的交易数据,包括各交易日的开盘价、收盘价、最高价、最低价、成交量、持仓量等信息,如表1。
按照上述算法描述,对3 632个交易日收盘价序列进行数据切分,获得单边模式序列及震荡点序列。
如图1所示为2015年3月13日至2015年4月17日40个交易日的收盘价序列的切分结果。
对于切分后得到的线段序列, 每个线段序列以2个属性进行描述:单边模式 / 震荡调整持续时间、单边模式 / 震荡调整趋势幅度。
2关于单边运行深度预测的频繁特征模式挖掘
本节在市场切分后,基于改进的频繁特征模式挖掘过程,对单边运行的深度进行预测。 着重研究对切分得到的单边模式序列及震荡点序列的符号化表示, 在此基础上基于互关联后继树模型的频繁特征模式挖掘算法, 以及通过频繁特征模式匹配实现单边运行深度预测的过程。
传统的时间序列频繁特征模式挖掘基本上可 概括为两 阶段:序列特征的描述及挖掘算法的设计。 即首先利用移动时间窗口对时间序列进行分段,并对各个子段进行聚类,利用形成的符号对序列特征进行描述。 在此基础上,利用关联规则挖掘思想及算法,对上述符号化序列进行频繁特征模式发现。 本文提出,对切分后得到的线段序列,结合市场实际运行特征,对线段在时间轴上的长度及线段的斜率分别进行符号化, 利用得到的二维属性组进行频繁特征模式挖掘。
基于上节思想, 将2001年1月2日至2015年2月5日的伦铜指数日交易数据作为样本,设定回归判定系数阈值为0.75, 进行数据切分,获得了单边模式序列及震荡点序列。对上述1070组切分后形成的线段序列,针对震荡点序列与单边模式序列,按照不同的策略,选取二维属性组(持续时间分类标记、运行深度分类标记),进行符号化表示:
将震荡点序列的持续时间分类标记设为10, 运行深度分类标记设为100;
将单边模式序列持续时间分类标记按照超短期、 短期、中期、长期分别设为1、2、3、4,运行深度按照是否超过相邻的上一单边模式序列的深度分别设为1、-1。
在对上述样本数据切分后形成的1 070组线段序列选取二维属性组(持续时间分类标记、运行深度分类标记),进行符号化表示的基础上, 将2001年至2011年涵盖的833组符号化的线段序列作为主要的训练数据, 根据基于互关联后继树频繁特征模式挖掘过程,对其建立t SIRST(时间序列互关联后继树)模型, 设定最小支持数阈值,并基于t SIRST模型进行频繁特征模式挖掘。 表2所示为设定最小支持数为3, 最小置信度为70%情况下,挖掘得到的频繁特征模式。
根据频繁特征模式的挖掘结果, 设定最小置信度阈值进行筛选,利用筛选后的频繁特征模式,对2012年至2015年市场实时跟踪得到的特征模式进行滚动匹配, 以实现对单边运行深度的预测。
通过精确的频繁模式匹配,实现对单边运行深度的预测,对预测效果的评价设定以下指标:预测准确率、模式覆盖市场机会比率、模式覆盖市场幅度比率。
预测准确率是对挖掘得到的频繁规则在实时跟踪中真实的预测效果的评价。 模式覆盖市场机会比率、模式覆盖市场幅度比率,反映了挖掘得到的频繁规则的市场应用价值。 其比率越高, 说明通过该方式可把握的市场机会越多,参与市场的收益越高。
综上, 基于改进的频繁特征模式挖掘过程, 对2012年至2015年 ,伦铜市场单边运行深度进行滚动预测 ,预测结果如表2所示,其中因样本期内2015年切分后数据较少,将其与2014年合并预测,在频繁特征模式挖掘过程中,设定支持数阈值等于3, 设定置信度阈值等于0.6。
表2表明,在设定的置信度阈值等于0.6时,通过挖掘得到的频繁特征模式数较多, 模式覆盖的市场机会及市场幅度比率都相对较高, 但由此进行的频繁特征模式匹配以实现对单边运行深度的预测,准确率较上述情况偏低。
3结论
综上所述, 对市场切分后得到的单边模式序列及震荡点序列,选取二维属性组(持续时间分类标记、运行深度分类标记),进行符号化表示,在此基础上,建立互关联后继树模型进行频繁特征模式挖掘,并通过频繁特征模式匹配,实现对单边运行深度的预测。 以2001年至2011年涵盖的833组符号化线段序列作为主要的训练数据, 滚动预测2012年至2015年市场单边运行的深度是否可以完全突破或跌破上一单边运行深度, 取得了良好的预测效果。
基于网页日志的频繁模式挖掘 篇2
万维网提供了大量对用户有用的数据, 不同类型的数据应该组织成能够被不同用户有效使用的形式, 因此, 基于网页的数据挖掘技术吸引了越来越多的研究人员。已有几种数据挖掘方法应用于挖掘隐藏在网页中的信息, 当然算法需要进一步调整以适应网页数据的属性。而且, 不只是数据挖掘算法, 还有人工智能, 信息获取, 以及自然语言处理技术都可以在数据挖掘中得到有效应用。因此, 网页挖掘技术已经伸展到自动研究领域。
本文主要介绍基于网页日志的几种不同类型的数据挖掘技术, 这些挖掘技术用于挖掘隐藏在网页中的不同的频繁模式。包括:频繁模式、序列态以及树态。对于每个问题, 都有相应的算法, 用于高效挖掘相应的模态。频繁模式 (高频网页) 挖掘采用文献[1]中介绍的频繁模式算法。频繁模式算法的主要优势在于可以快速挖掘低频繁模式页, 对于更高频繁模式的挖掘效果也得到了增强。序列挖掘算法采用文献[2]中介绍的SM-树算法, 其中可以有效发现树型模式的算法称之为PD树算法。两种算法都可以充分利用自动化理论发现其中的频繁模式。SM树算法采用状态机发现序列模式, PD树算法采用叠加自动机确定在树形数据库中三种模式。
1网页挖掘任务
网页挖掘包括:从网页数据中发现和提取信息;提供有效的机制以使数据访问更加有效和匹配;从用户行为中发现信息, 用户行为信息一般存储在网页日志中, 比如网页缓存[3]。因此网页挖掘可以根据需要挖掘的信息分为三类[4,5,6], 分别是:网页内容挖掘, 网页结构挖掘和网页使用方式挖掘。网页挖掘的相关详细研究请参考文献[4,5,7,8]。
网页内容挖掘的任务是在线发现有用信息。对用户有用的信息包括:多媒体数据, 结构化 (XML) 和半结构化数据 (HTML) , 以及非结构化数据 (如文本) 。网页内容挖掘的目的是建立一个帮助用户发现他们需要的信息的机制。网页内容挖掘包括:组织和聚类文档, 提供相应的引擎以便用户通过相关的关键词信息、分类信息以及内容信息等获取不同的文档。
网页结构挖掘[9,10,11,12]的目的是发现内嵌于网页中超链接。实际上, 网页内容挖掘关注文档内部信息, 网页结构挖掘则关注文档之间的链接结构信息, 其目的是为了标识相关主题的权威或者中心网页。权威网页包含了有用的信息, 通过几个链接指向它, 这意味着这些网页被引用频度很高。一个拥有很多链接的网页可以认为其内容是有用的、更好的和可靠的。中心网页是指包含许多到权威网页的链接的页面, 因此中心网页有助于集中权威网页。网页结构挖掘可以通过门户网页或者整个网页获得。网页结构挖掘也支持网页内容挖掘, 通过获得网页结构信息, 可以更加有效地获取文档, 发现文档的可靠性和相关性也可以更好。网页的图形结构可以通过网页结构挖掘实现, 网页的图形结构挖掘可以提高信息获取的能力, 并提高文档的分类效果。
网页使用模式挖掘是指发现用户浏览和转换网页的行为特征, 其目的是通过理解用户转换网页的喜好增强电子商务的服务质量, 个性化门户网站, 或者提高网页结构和网络服务器的性能[13,14]。这种情况下, 挖掘的数据对象是可以选择作为网页上的间接数据的网页日志, 其中通过网页访问的文档可以理解为初始数据。
有三种类型的网页日志可以用作数据挖掘的对象:存放在服务器端的日志数据, 客户端的日志数据, 以及存放在代理服务器上的数据。由于不止一个地方存储着用户浏览网页的信息, 因此使数据挖掘过程变得困难。真实可靠的数据挖掘结果是建立在以上三种数据俱全的基础上的。这是由于服务器端的数据并不包含存储在代理服务器或者客户端的数据, 除了服务器端的数据, 代理服务器还存储了其他的信息。然而, 存放在客户端的网页请求方面的数据是缺失的。但是, 客户端的所有信息是难以收集完整的。因此, 大多数算法是基于服务器端数据的。一些应用在网页使用模式挖掘的常用的数据挖掘算法包含:规则挖掘, 序列挖掘, 以及聚类挖掘[15]。
2网页使用模式挖掘
网页使用模式挖掘, 从数据挖掘的角度来看, 就是将数据挖掘技术应用到网页数据中, 从而发现使用模式, 为更好理解用户浏览网页的需要服务[16]。类似于其他的数据挖掘过程, 网页数据挖掘过程包括三步:数据预处理;模式发现;模式分析。
本文所说的模式发现是指将前面介绍过的模式发现方法应用到网页日志上。为此, 首先需要将数据进行预处理以使处理后的数据能够符合算法输入的格式。模式分析是指解释数据挖掘结果, 并作出相应的结论。
图1显示了网页使用模式挖掘的实现过程, 这个过程的输入数据为日志数据。这些数据需要进行预处理, 以使其符合算法所需的输入数据格式。不同的算法需要的输入数据格式也不同, 图中所示的预处理过程可以提供三种类型的输入数据。
频繁模式发现过程仅需要用户提供的网页数据。这种情况下, 网页序列是不相关的。相同网页的重复浏览也可以忽略, 网页调用是预先定义的。
在序列挖掘中, 网页浏览序列是重要信息, 同一网页如果在规定时间内被用户浏览多次, 则每次都是相关网页。因此整个系统的预处理模块提供了用户浏览网页的序列信息。
对于用户模式树挖掘, 则不仅需要网页浏览序列信息, 还需要被访网页的结构信息。这种情况下, 后退浏览可以忽略, 只有前向浏览是相关的, 这样, 针对每个用户就形成了一颗树。发现过程完成后, 下面的事情就是模式分析。通过图1的反馈回路看出整个挖掘过程是一个迭代的任务过程。根据分析结果, 可以调整预处理参数 (比如重新选择时间间隔) , 或者调整数据挖掘算法的相关参数 (这意味着需要设定数据挖掘的最小门槛值) 。
本文中的网页使用模式挖掘的目的是发现在同一时间内访问频率最高的网页, 发现用户浏览网页的次序。其结果用于帮助确定门户网页的结构, 从而更好地满足广告要求, 提供更加个性化的网页门户。
3相关工作
网页使用模式挖掘过程中, 有几种数据挖掘算法可以利用。关联规则挖掘用于发现即使没有直接联系也被用户一同访问的网页, 这可以发现组用户之间相关的特殊兴趣[13]。比如这些信息可以用于重组网站结构, 如增加关联网页之间的链接。关联规则挖掘可以参见文献[17,18,19,20]。网页序列挖掘可以用于发现用户浏览相关网页后紧接着浏览的网页。利用这些知识就可以预测用户浏览网页的下一个行为, 并预测下一个将被访问的网页。网页序列挖掘在文献[14]中有详细介绍, 称之为WAP树挖掘, 树形拓扑模式和频率路径转换关系可以参见文献[17]。
网页使用模式挖掘在许多方面都是复杂的, 这个过程中不仅使用数据挖掘技术, 还使用了其他的技术。比如, 文献[6]中采用了称之为Ngram模型的概率语法技术, 通过该模型可以发现用户网页浏览行为模式。Ngram模型假设前面N次浏览的网页影响第N+1次浏览的网页。网页预测可以采用网页日志挖掘技术或者马尔可夫预测器。
4挖掘算法总结
在研究网页使用模式挖掘过程之前, 以及在解释重要的挖掘步骤之前, 首先需要简要介绍频繁模式挖掘算法。理解挖掘机制对于理解挖掘结果是必要的。另外一个重要的方面是, 确定算法输入参数, 有助于数据预处理过程中明确合适的数据输入格式。
就如前面所述, 频繁模式网页是通过ItemSetCode算法完成的。这是基于先验假设基础上的一个备选挖掘算法。算法的目的是为了增强先验假设在更低水平上的使用效果。这意味着, 可以增强低频繁模式网页的发现。通过这种方法, 也可以更快发现高频繁模式的网页。ItemSetCode的思想是将3阶或者4阶频繁模式问题的规模降低到2阶。ItemSetCode可以通过索引矩阵快速发现2阶或者1阶频繁模式网页。2阶问题可以编码解决, 3阶或者4阶问题可以通过成对使用2阶问题编码解决。3阶或者4阶问题可以按照存储结构要求进行存储, 这种方式可以保证高效的使用数组, 而且, 该结构对内存要求也很低, 算法只是部分利用了先验假设的好处, 原因是必须使用压缩存储结构。ItemSetCode算法由于可以快速发现低频繁模式页, 因此可以有效地发现高频繁模式网页, 其独立于问题层次的特点可以保证内存需求与事务多少无关。ItemSetCode算法输入数据格式也可以适用于其他频繁模式挖掘算法。它以行序读取事务, 每行包括了多个数据项。
网页浏览次序挖掘可以使用SM树算法[2]。SM树算法的主要思想是在输入项目的次序只处理一次的情况下测试子序列, 算法的应用基础是状态有限机。通过联合几个自动机, 一种称之为SM树的结构可以建立起来, 该结构可以比采用不同的状态机分别处理每个候选数据更快地处理候选数据。基于这个特点, SM树结构可以得到有效的处理。这个可以通过利用两种类型的状态的优势, 如固定状态和临时状态获得。算法更大的优势在于其内存需求独立于事务的个数。SM树算法的输入格式包含行事务, 其中每行包含了数据项的序列信息。
5数据处理
存储在服务器端的记录用户行为的网页日志数据不能够以其存储的格式直接应用到数据挖掘中。因为这一点, 数据预处理过程必须在模式发现过程之前进行。
数据预处理过程分为三步:首先, 收集的数据必须进行净化, 即删除图形和多媒体数据。其次, 需要将不同的数据分属到不同的用户。当用户在指定网点浏览网页时, 一次会话理解为该用户的一组行为。从原始数据中标识会话是一个复杂的过程, 因为服务器端并不总是存储了所有必需信息。有些服务器端的网页日志没有存储足够的信息重建用户会话过程, 在这种情况下, 可以使用面向时间的启发式方法。会话经过标识后, 数据预处理过程的第一步, 网页浏览次序也就决定了。最后, 需要将数据转化到挖掘算法需要的格式。如果会话和次序标识完毕, 第三步的完成将简便许多。
在本文的实验中, 使用了两种网页服务器日志, 第一种来自msnbc.com 的异步数据, 第二种从ECML/PKDD 2005 Discovery Challenge下载的鼠标单击流数据。两种数据的格式都不一样, 因此数据预处理过程也不一样。
Msnbc日志数据记录了用户于1999.9.28访问Msnbc网站的网页信息。访问按照时间先后序列以URL的形式记录。这意味着预处理数据过程的第一步可以忽略。数据来自msnbc.com中的IIS日志。每一行对应用户在24 h内访问的网页。网页编码格式如表1所示。客户端缓存数据没有记录, 因此这些数据主要包含服务器端日志数据。
这种情况下, 只需要将msnbc的行数据转换为相应的数据项网页浏览次序和树形结构, 则另外一个数据预处理的步骤已经执行。转换过程中忽略重复的网页, 因此直接按照编码序列进行排列。这样, ItemSetCode算法可以在数据表中执行。
为了获得网页序列模式, 行数据转换结果必须体现网页浏览次序。一行实际上代表其中一个数据项的次序。因此, 转换为SM树算法需要的序列格式意味着在每个代码之间插入一个值-1。
为了能够挖掘树形模式, 数据必须转换为树形事务格式。基于这个原因, 每行按照以下的方式进行处理:根为行数据的第一个数据项。从根数据项可以生成分支, 直到相应的数据项已经插入树中。这种情况下, 算法共插入的-1值的个数等于新数据项前面出现的相同数据项之间数据项个数。更多的数据项形成新的分支。比如对给定行:“1 2 3 4 2 5”, 则对应行的树形表示为“1 2 3 4 -1 -1 5”。
鼠标单击流数据中, 数据预处理过程需要更多的工作。包含546个文件, 其中每个文件包含了1 h之内的所有用户行为信息。每一行包含以下部分:
店名, 时间, IP地址, 惟一的会话标识符, 访问网页, 参考。
6数据挖掘和模式分析
就如图1所示的, 网页使用模式挖掘需要完成所有三种频繁模式挖掘任务。对于挖掘过程, 除了输入数据, 还需要设置最小的门槛值, 这是关键之一。用户交互和迭代过程需要持续下去, 直到发现合适的数值为止。由于这个原因, 在挖掘过程中需要用户交互, 建议在整个数据库中迭代执行频繁模式挖掘算法。选择大小合适的数据样本, 如果数据样本准确反映数据库, 程序响应时间很短。
频繁模式数据项发现和关联规则挖掘可以使用ItemsetCode算法完成, ItemsetCode同样需要设置最小的支持门槛值和最小的可信度值。图2显示了根据msnbc.com网站的数据挖掘的关联规则, 其最小支持门槛值为0.1%, 可行度门槛值为85%。通过分析其挖掘结果, 用户可以更好地确定广告方式, 以及门户网页结构。
图2显示了将SM树算法应用到msnbc.com数据的挖掘结果, 图2 (b) 中的百分比值即为支持门槛值。
7结语
主要讨论了如何从服务器端的网页日志数据挖掘潜在有用信息的问题。文中主要介绍了网页日志数据挖掘的过程, 以及如何通过将频繁模式模式挖掘算法应用到网页日志数据挖掘中, 获得关于用户浏览网页的有用信息。
频繁特征模式挖掘 篇3
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.
频繁特征模式挖掘 篇4
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
频繁特征模式挖掘 篇5
为了方便对包含海量信息的视频数据库进行浏览和检索,如何产生原始视频流的摘要成为近来研究热点。所谓视频摘要,就是在对视频数据所包含的信息块、对象和场景等内容进行分析的基础上,实现原始冗长视频流内容压缩,以便自动生成涵盖了原始视频最大语义内容的紧凑表示,方便用户对海量视频所蕴含的丰富语义信息快速了解。
目前视频摘要自动生成算法大致可以分为三类:基于关键帧、基于精彩场景(Highlights)和视频内容综合编辑。采用关键帧来创建视频摘要的方法在目前来说相对比较普遍[1,2],该方法一般依据视频采样帧所包含视觉、听觉或者文本等底层特征之间形成的几何距离来对视频帧进行采样以获取关键帧。视频摘要以关键帧来表现能够让人们从视频中非线性快速定位用户感兴趣的镜头,但由于关键帧选取过程一般忽略了视频语义内容时序连贯特性,难以较全面反映和代表视频语义。精彩场景提取则是指定义先验模板(如进球和爆炸等事件),通过机器学习方法训练得到特定模板分类器,从视频流中检测预先定义的模板内容,如文献[3]通过支持向量机识别足球比赛中观众呐喊声和解说员激昂解说声,来提取进球等精彩场景。文献[4]中通过所建立的用户关注模型框架来提取视频中的精彩场景生成视频摘要。基于精彩场景的视频摘要生成方法需要根据先验知识来训练得到相应识别分类器,限制了其通用性。为了充分利用视频中时序信息,“Video Synopsis”等对视频内容进行综合编辑而产生视频紧凑表示的方法被提出,其基本思路是从连续视频中提取对象运动信息,将其整合到一个视频片段中[5,6]。类似的工作还有融合不同类型媒体特征实现视频摘要生成的方法,如卡耐基梅隆大学在Informedia项目中提出的“Video Collages”[7]以及国立新加坡大学的视频新闻概念检测[8]。但是这些方法本质上还是要对视频中人物、对象、运动和场景等内容进行识别,其通用性也受到了一定限制。
由于频繁镜头系列包含了视频内容的重要信息,本文提出了一种新颖的通过挖掘视频中能够代表视频内容的频繁镜头模式生成视频摘要的算法。它首先通过近邻传播聚类方法将相似镜头组合到一起;然后采用频繁镜头模式挖掘的方法对视频聚类内容进行挖掘,去掉视频中冗余内容部分;最后通过覆盖视频语义信息的频繁镜头模式生成视频摘要。
1 近邻传播聚类
根据底层特征变化来实现镜头边界检测是自动摘要生成的前提,本文使用文献[9]中方法实现渐变和骤变镜头检测。对于检测出来的视频镜头,需要将相似镜头归属到一起,这个过程要靠聚类完成。
传统的k平均聚类算法将数据集分割成若干类,但是其聚类结果易受聚类初始质心影响,难以获得良好结果和聚类收敛性难以保证[10]。
2007年Frey和其同事提出了一种称为“近邻传播聚类AP”的聚类方法[11]。AP聚类的基本思想就是通过消息传递,让数据点相互选择聚类质心和聚类归属集合。近邻传播过程可看作信念度消息在双向图上按照一定概率进行传播,这个双向图模型描述了任意两个数据点之间相似值(如欧氏距离)。通过消息迭代传播,可最终从被聚类数据中挑选出聚类质心和将每个数据点归属到某个最可能聚类集中。与常用的k-中值聚类算法相比,近邻传播聚类并不需要预先设定聚类个数。此外,近邻传播聚类求取的聚类质心是被聚类数据中某些实体数据,而不是如k-平均聚类中得到的虚拟几何中心,因此其聚类结果更符合数据拓扑分布。
在近邻传播聚类中,偏向值(Preference)这一参数被用来控制聚类集合数目。一般而言,偏向值越大,所得到的聚类集合数目越多。进一步研究表明,偏向值和聚类集合个数之间并不存在线性对应关系。但是,随着偏向值增加,总能得到具有更多聚类集合个数的近理想聚类结果。
本文下面结合视频镜头聚类的应用,对AP聚类算法进行解释,更详细的描述可参见文献[8]。假设k和i是任意两个视频镜头中的关键帧,s(i,k)表示镜头k和镜头i之间距离(本文使用关键帧中直方图交来计算镜头之间的相似度),N是被聚类镜头所形成的聚类集合数目,则AP聚类可看作是使得E(c)=-∑
在AP聚类中,节点和节点之间相互传递两类信息,分别是r(responsibility)和a (availability)。其中r(i,k)表示k作为节点i的聚类质心的可信度,a(i,k) 表示节点i选择k作为其聚类质心的可信度。
AP聚类过程如下:
算法 基于AP的镜头聚类
输入: 任意两个节点(即镜头)i和k之间距离s(i,k)
输出: 镜头聚类结果集
算法过程:
初始化:
a(i,k)=0
如下更新节点之间的r值:
如下更新节点之间的a值:
如下更新同一节点自身之间的a值:
上述消息传递过程一旦超过预设迭代阈值,则停止。
对于任意镜头k,如果其与镜头i之间的a(i,k)+r(i,k)最大,则将k归属到以i自身为质心的聚类集合中,完成视频镜头聚类。
值得注意的是,AP聚类算法对海量数据的处理性能不高,为了克服这个问题,文献[12]提出了基于分块信息传递的数据聚类和近似快速信息传递聚类两种方法。前者在基本不损失聚类结果精确度的情况下能够加快密集数据聚类速度,后者在保证聚类效果损失不大的情况下能够呈指数级别的加快聚类的速度。
2 频繁镜头模式挖掘与视频摘要生成
通过上述近邻传播聚类,各个镜头被归属到不同集合,则可通过数据挖掘方法获得视频流中的频繁镜头,最终生成视频摘要。比如在一段新闻对话节目中,假设某个主持人出现的所有镜头被聚类到“A”集合,某个被访者出现的所有头被聚类到“B”集合,而其他镜头被聚类到 “C”集合,则这段视频流可用“ABABABCAB”序列来表示。
通常我们可认为,经常出现的镜头子串包含了视频流所表达内容的最大信息量,可作为视频流的紧凑表示。即为了生成视频流的摘要信息,可通过挖掘视频中频繁镜头模式来实现这一目的。基于这样的考虑,本文采用基于Apriori机制[13,14]的频繁镜头模式算法来对聚类得到的镜头序列进行分析,最终生成视频摘要信息。
2.1 频繁镜头模式
在本文中镜头模式是指视频流中在一定时间间隔中出现镜头序列。用户可以指定一个时间窗口,镜头模式必须在这个时间窗口内出现。用户同时可指定一个最少出现次数,如果镜头模式在视频中出现的次数超过它时认为是一个频繁镜头模式。
对于原始视频流,假设得到了t个视频镜头{si}(1≤i≤t),然后按照近邻传播聚类得到了这t个镜头聚类结果,表示为{cj(1≤j≤m)}(总共有m个聚类集合),那么就可用一个标志来标注属于同一聚类集合中所有镜头,原始视频流就表示为S={c1p,....,csp,c(s+1)q,.....}(1≤s+1≤t,1≤p,q≤m)。其中c1p和csp表示第1个镜头和第s个镜头均属于第p个聚类集合,c(s+1)q表示第s+1个镜头属于第q个聚类集合。
所谓镜头模式指:其是一个原始视频流的子串,并且它所包含的所有元素在时间窗口内出现。如在图1中,镜头被聚类成五类,每类分别被标注为A、B、C、D、E和F。当时间窗口宽度是1时,镜头模式{A,B}出现的次数为3次,而当时间窗口的宽度是3时,镜头模式{A,B}出现次数为4次。
2.2 视频摘要生成
下面介绍本文基于Apriori机制来挖掘频繁镜头模式的方法。频繁镜头模式挖掘算法是基于如下事实:任何模式如果它的子集是非频繁的则它不可能是频繁的。在这个原则下,频繁镜头模式挖掘算法在进行视频挖掘过程中采用了对视频流系列进行多重扫描、候选集生成和测试等步骤。它首先对视频序列S进行扫描,找到所有频繁镜头。在每一遍扫描过程中都生成一个频繁镜头模式的种子集合,这个种子集合用于生成新的候选镜头模式。在频繁镜头模式中镜头个数为频繁镜头模式的长度,在同一轮的扫描中候选镜头模式的长度都相同。然后扫描视频系列找出镜头模式在视频流中出现的次数,所有出现次数不少于某一阈值的镜头模式组成新的频繁镜头模式集合。重复这个过程,直到不能再构造非空的频繁镜头模式集为止。例如在视频镜头系列 “ABCDACDEABCD” 中,通过频繁镜头模式算法挖掘最长的频繁镜头模式为{ABCD},它在视频流系列中出现的次数为2次。
C1={{c}|c∈C},i=1;
while Ci≠ϕdo
对每个镜头模式Ci统计其在一定窗口宽度下,其在视频系列S中的出现次数;
Li=在Ci中所有不小于阈值min_fr的候选集;
Ci+1=新的从Li中构造的候选集;
i=i+1;
for all i,输出Li
频繁镜头模式算法的候选集构造算法与文献 [11]中所采用方法很类似:此方法将所有在Li中的镜头模式集进行连接操作生成候选集。
1) 对在Li中的项目进行连接。
2) 将结果插入到Ci+1中。
3) select{p.Item1,...,p.Itemi,q.Itemi}
from{Li.p,Li.q,p≠q}
where{p.Item1=q.Item1,...,p.Itemi-1=q.Itemi-1}
4) 对任意Ci+1的项,如果它的长度为i的子模式不在Li中,则进行删除。
从上述过程可以看到,一个视频镜头子串能通过频繁镜头模式算法挖掘出来它必须在视频中频繁出现。视频中频繁镜头模式蕴含了视频中重要语义信息,传达视频上下文信息。显然频繁镜头模式很适合用来生成视频摘要。某个频繁镜头模式的长度越长和出现次数越多,则由于其包含了更多视频语义内容信息,于是更加适合作为视频摘要。因此,为了构造视频摘要,可以把通过频繁镜头模式算法得到视频镜头子串按照出现次数进行排序,然后根据用户指定的视频摘要长度,以聚类项目中所在关键帧为中心,选取出一段视频,最后将这些视频片段连接起来,就形成了这段视频的摘要信息。
3 实验建立与分析
根据以上所提到的算法,我们在Window2000下用VC6.0实现了整个系统。对于每个切分得到的视频镜头,从中选取其首帧作为关键帧,从每个关键帧中提取128维保持了内容空间信息的颜色聚合向量CCV(color coherence vector)直方图[15,16]作为每个镜头的特征,CCV之间的相似度量函数采用直方图交。
为了评价视频数据V所生成摘要的有效性,本文采用了摘要压缩比(SCR)和内容覆盖率(CC)两个评判公式:SCR = 摘要长度/视频中关键帧个数,CC = 摘要中情景数/视频中情景数。这里使用内容覆盖率(CC)来评价摘要完整表达原来视频的能力。对于一个同样的摘要压缩比(SCR),如果内容覆盖率(CC)越大,则显然生成的视频摘要越好,越能完整表达原来视频的内容。
表1中显示了一段长度为25分钟的视频,当采用时间窗口宽度为52时,近邻传播聚类中偏向值这一参数p对视频摘要结果影响。可看到偏向值参数p增加时,镜头聚类的数目会随着它相应地增加,经过频繁镜头模式挖掘得到的视频摘要的长度也会相应增加。
对于一段明显存在两个类别的视频流,调整k平均聚类算法和近邻传播聚类算法的参数,使这两种聚类方式对这段视频流均能够正确聚类。选取这个时候的k平均聚类和近邻传播聚类参数,对视频新闻和访谈节目视频流(这些视频流均明显存在两类镜头)进行聚类性能对比分析,结果见表2。
表2中所采用镜头聚类正确率定义为:正确聚类镜头数/所有镜头数。可以看出:由于近邻传播考虑了不同镜头之间的信念度分布和传递,使得聚类效果明显优于k平均聚类。应该指出,由于实验中选取了两种聚类算法的最优参数,使得结果具有可比性,而且随着视频内容丰富程度的增加,由于近邻传播聚类能够根据数据分布判断这些数据能够聚合成几类,不需要人为指定聚类集合数目,因此其聚类结果更加能够反映视频数据分布属性。
一般来说,用户希望生成的视频摘要长度要短,同时包含尽可能多的信息,但同时满足这两个要求是非常困难的。更可行的方法是用户可自行选择视频摘要压缩比。表3给出了视频摘要压缩比分别为15% 和 30%时实验分析数据。在表3生成中,先挖掘视频中的频繁镜头模式以去处冗余内容,然后根据用户指定视频摘要压缩比选择重要视频镜头生成视频摘要。
为了对生成的视频摘要进行评价,我们将视频摘要分为五个等级:很差,差,一般,好和很好,这五个等级分别记为0,0.25,0.50,0.75和1.0。试验中请10个用户对生成的视频摘要进行打分,他们逐个对原始视频进行浏览,然后对每个对应的视频摘要进行打分,对自动生成的视频摘要进行评价。表3显示了用户对自动生成的视频摘要进行评价的平均结果。
从表3中可得到一些有用的结论。大部分的用户在摘要压缩比为0.15时,对本文算法生成的视频摘要感觉好或一般。而当摘要压缩比为0.30时,用户都倾向认为生成的视频摘要质量好或很好。用户很难从较长视频中快速掌握视频中语义信息,压缩比太大的视频摘要并没有太多意义,摘要压缩比为0.15和0.30的视频摘要可以让用户迅速地掌握原始视频中表达的语义信息。
4 结 论
本文提出了一种新颖的视频摘要生成算法对任意视频生成一段视频摘要。对于切分得到的视频镜头,采用近邻传播聚类的方法进行聚类,接着对视频场景进行频繁镜头模式挖掘,去掉视频中冗余部分,最后形成视频摘要。
今后工作集中在如下部分:(1)对更多数据进行测试,以提高算法性能;(2)分析视频数据所包含的视觉、人脸、运动、听觉和字幕(文本)等多媒质信息,自动生成涵盖其最大视觉/听觉语义内容的摘要信息。
摘要：为了有效支持视频数据库浏览和检索,通过视频摘要来对视频进行紧凑表达变得十分重要。提出了一种新颖的基于近邻传播聚类AP(Affinity Propagation)和频繁镜头模式挖掘的视频摘要自动生成算法。视频频繁镜头模式被定义为在一定时间窗口内经常出现的镜头系列。首先通过近邻传播聚类,将相似镜头聚合到一起;然后采用频繁镜头模式挖掘的方法对视频聚类内容进行挖掘,去掉视频中冗余内容部分;最后通过覆盖视频语义信息的频繁镜头模式生成视频摘要。实验结果表明,视频摘要算法取得了良好的效果。
频繁特征模式挖掘 篇6
优化算法, 是指将原来的事务集进行分块, 然后采用挖掘技术对每块进行频繁集的挖掘, 形成原来事务集的频繁集。可通过下面两个相关性质保证使每个分块后的频繁集形成原来事务集的频繁集, 并且要保证它的正确性:在进行分块的时候, 要求块内的事务集之间具有较高的相似度, 而块与块之间事务集中的各个项的相似度应非常的低, 这样可使得在某块上是频繁项, 而在别的块上却不是频繁的, 也就是说支持度小于给定的阈值。
2. 实验测试与分析
2.1 测试环境及测试事务数据库
本文进行数据库测试使用台式计算机的配置为:CPU为Pentium (R) , 2G内存, 操作系统为XP系统, 编程语言为C++语言。
2.2 优化算法测试和分析
2.2.1 采用census数据库进行算法测试
census数据库是由美国加利佛尼亚大学提供的用于数据挖掘和习用的一个测试型数据库。数据库的大小约为10.9M。
设最小支持度为0.01%~80%时, 下图为在不同最小支持度的情况下, 对算法进行了census数据库的测试, 显示了优化算法和普通算法在进行频繁集挖掘时运行需要的时间差别。
2.2.2 在accidents数据库上进行算法测试
accidents是由比利时统计院提供的数据库, 该数据库包含了Flanders地区在1991-2000年期间的交通事故记录, 它的大小约为33.8M, 每条记录种平均记录有45个不同的属性值。
下图为在不同最小支持度的情况下, 对算法进行了accidents数据库的测试, 显示出优化算法和普通算法在进行数据挖掘时运行需要的时间差别。
2.2.3 分析测试结果
由测试结果可以看出, 在最小支持度比较大的情况下, FP-Growth算法的速度要快于优化算法的运行速度。但随着最小支持度持续减小, 减小到给定的阈值时, 优化算法的运行速度就会超过FP-Growth算法的运行速度。建树和频繁项集的挖掘决定了FP-Growth算法的运行速度;而数据库子集的生成是影响优化算法运行时间的主要因素。随着最小支持度的慢慢减小, 小于给定的阈值时, 频繁1-项集的项总数会不断增加, 这时, FP-Growth算法就会在建树时的内存开销和时间开销急剧增大, 反而会影响到挖掘速度变的越来越慢;而优化算法在进行数据库子集生成时, 虽能存在时间开销不断增大的现象, 但是, 优化算法在进行挖掘约束频繁项集时, 由于内存开销相对比较少, 反而时间开销也会变得比较小, 这样, 优化算法的运行速度就比FP-Growth算法快。进行建树及频繁项集挖掘时, 当支持度比较大时, 大于给定的阈值时, 由于频繁1-项集的项总数比较小, 在时间开销上存在很小的差别, 但是优化算法在进行数据库子集生成时, 却存在时间开销, 所以就导致了FP-Growth算法比优化算法的运行速度快。
摘要：本文首先对优化算法进行了简单介绍, 然后在数据库census和accidents对算法进行了测试, 对测试结果和没有优化的算法进行了分析比较, 验证了优化算法的优越性。
关键词：关联,优化算法,性能测试,分析
参考文献
[1]高飞, 谢维信.发现含有第一类项目约束的频繁项集的快速算法.计算机研究与发展.2001, 38 (11)
【频繁特征模式挖掘】推荐阅读：
应用频繁模式挖掘算法12-21
数据流频繁项挖掘02-01
频繁结构01-16
频繁眨眼01-21
频繁跳槽09-24
频繁跳闸原因06-14
频繁项目集12-11
产品特征挖掘08-15
频繁换工作简历如何写10-22
频繁跳槽的简历怎么写06-26