基于约束的频繁模式挖掘方法以及应用研究

《基于约束的频繁模式挖掘方法以及应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中圈科孽敢求犬誊博士学位论文基于约束的频繁模式挖掘方法以及应用研究作者姓名：学科专业：导师姓名：张磊计算机应用技术陈恩红教授刘贵全副教授完成时间：二。一四年五月IUllUlIIIIIIIIIlY2589839UniversityofScienceandTechnologyofChinaAdissertationfordoctordegreeConstraint．．．BasedFrequentPatternMining：NovelApplicationsandNewTechniquesAuthor：Speciality：Supervisor：LeiZhangComputerApplicat

2、ionTechnologyProf．EnhongChenAsso．Prof．GuiquanLiuFinishedTime：May)2014中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：追盟中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，

3、允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。公弄保密——年作者签名：啦导师签名：{!止塾!二一签字日期：五!!生!曼：丝摘要基于约束的频繁模式挖掘是数据挖掘研究中最基本问题之一，具有广泛的实际应用。然而，在这个研究领域中，仍然存在三个方面的挑战：(1)如何拓展新的应用?具体而言，除了模式的“支持度”，怎样设计一些新模式指标更好地去度量模式的兴趣度，以满足新应用的需求；(2)和模式支持度的反单调性不同，所提新模

4、式指标的性质通常都比较复杂，比如它不满足单调性、反单调性、可转换性、简明性等。那么对一个模式，如何快速计算其所有父模式关于该指标的J=／-F界，并利用这个新模式指标的特性设计出高效算法；(3)通常，不同的应用，有不同新模式指标的提出，然后分别提出不同的模式上／下界的计算方法。那么有没有一种通用方法可以计算任一模式指标的J=／-F界?针对以上问题和挑战，本文开展了基于约束的频繁模式挖掘的方法及其应用研究，主要成果及贡献如下：首先，提出了一个基于模式挖掘的网页内容推荐方法。网页内容推荐就是从网页中找到重要的内容块组合推荐给用户，有着很多的应用(比如网页智能打印、移动设备上的电子阅读等)。目前

5、有许多的方法试图去解决这个问题，但在这些方法中，要么就是针对于特定网页(比如新闻、博客类的网页)，要么就是半自动化的(用户需要额外的操作去选择网页的内容块)。针对于任一类型的网页，如何全自动地提取网页中的有效内容，目前还没有得到很好地解决。为此，本文利用之前用户对相似网页的选择方式，将该问题形式化成一个模式挖掘推荐问题，提出了一个基于模式挖掘的网页内容推荐方法，可以为任一类型的网页提供更加准确的网页内容推荐。具体而言，推荐给用户的内容块组合(模式)不仅要频繁被其它用户选择，而且要越完整越好。鉴于此，本文提出了一个新的模式兴趣指标，即占有度，来衡量模式在其支持数据库上的完整度。结合模式的支

6、持度和占有度，可以提供给用户更加准确、满意的网页内容推荐。最后，同基准方法比较，在真实的数据集上的实验结果表明所提方法能取得更加满意的推荐结果和运行效率。摘要其次，提出了一个基于占有度的频繁模式挖掘通用高效算法。本章分别对占有度的定义、界估算方法以及应用三个层面进行深度扩展。具体而言，基于不同的加权平均(算术平均和调和平均)，提出了两种不同的占有度定义，即算术占有度和调和占有度。与模式支持度的反单调性不同，占有度的性质即不满足单调性、反单调性，又不满足可转换性、简明性，那么对一个模式，如何快速计算其所有父模式关于占有度的一个上界?为此，对于每一种占有度定义，本文分别提出了三种上界：高效、

7、最‘紧’和折中上界。高效上界对于单个结点计算比较高效，但是比较松散，需要搜索结点数比较多；最‘紧’上界得到的界比较紧凑，因而搜索很少的结点，但是计算单个结点比较耗时；为此，本文提出了一个折中上界，在松紧度和计算复杂度之间达到一个均衡，使算法整体性能达到最优。占有度的概念不仅对于事务数据库上的应用很重要(比如网页内容打印推荐)，而且对于序列数据库中上的应用也非常重要(比如旅游餐景点推荐)，为此，本文提出了一个通用算法DOFRA可以同时