逐步最佑扩展的频繁子图挖掘算法

gSpan算法是一种高效的频繁子图挖掘算法,它通过最右扩展图的标准编码得到图集中的所有频繁子图,但它需要通过子图同构判断来计算支持度,由于子图同构问题是NP完全问题,其计算比较复杂.针对上述问题提出一种优化的算法IgSpan,通过改进的ADI++存储结构将图的最右扩展和支持度的计算相结合,避免直接的子图同构判断,经实验...     

基于对gSpan改进的有向频繁子图挖掘算法

提出的新算法对gSpan算法做了适用性改进,算法所采用的图编码技术与传统的频繁子图挖掘（FSG）,快速频繁子图挖掘（FFSM）,基于先验的图挖掘（AGM）等算法对图结构的编码均不同,由于对有向图进行了新的二维特征定义,因此可使算法适用范围有效地扩展至对有向图的学习,称之为基于对gSpan改进的有向频繁子图挖掘算法（DF...     

单图中的近似频繁子图挖掘算法

图数据的挖掘工作是数据挖掘工作中的重要组成部分,已经有许多人在这个领域进行了深入的研究.由于数据获取不可避免噪音数据,故在挖掘频繁图时考虑近似十分重要.然而许多此前的工作只考虑了子图间编辑距离(Graph Edit Distance,GED)的绝对值,而没有考虑子图间编辑距离与子图大小的相对关系.提出了一种在单图中进行近似频繁子图挖掘的新算法,并在计算近似程度时考虑当前子图的大小.该算法通过对近似频繁子图的大小上限进行预测,并通过局部反单调性进行剪枝,提高了算法的效率.实验表明,该算法能够挖掘出传统算法无法发现的近似频繁子图,且相比对比算法具有更好的时间性能.     

基于有向频繁子图挖掘的移动性模式网络构建方法

挖掘大量移动轨迹数据获取移动性知识,可为城市交通、智慧医疗等众多行业领域提供辅助决策.但现有的移动性知识表达方式过于简单,不能反映产生移动轨迹数据复杂系统的潜在运行规律,需要从网络的视角分析移动性知识之间的复杂关系.提出了一种基于有向频繁子图挖掘的移动性模式网络构建方法,包括移动轨迹数据到轨迹有向图的转换,基于有向图的...     

两个经典频繁子图挖掘算法的对比与分析

AGM算法和HSIGRAM算法是两个经典的频繁子图挖掘算法,在基于图的数据挖掘中有重要的应用.从算法思想和应用技术两个方面分析了AGM算法和HSIGRAM算法的异同点,结合基于图的数据挖掘的特性,提出针对这两个算法的改进策略.     

基于加权频繁子图挖掘的图模型在文本分类中的应用

针对传统文本分类算法的分类精度低和计算复杂度高的问题,提出一种基于加权频繁子图挖掘的图模型文本分类算法。首先将文档集表示成图集;然后运用加权图挖掘算法提取频繁子图;最后,对特征向量进行分类。提出的算法仅提取最重要的子图,使其整体具有较好的分类效果和较高的计算效率。为评估该算法有效性,将其与多种现有分类算法分别对一个数据集进行分类实验,实验结果表明,提出的算法具有更高的识别精度和更少的运行时间。     

一种基于频繁模式有向无环图的数据流频繁模式挖掘算法

频繁模式挖掘中基于FP-growth的算法需要扫描两次事务数据库,预先给定支持度,且不支持时间敏感型数据。本文提出了一种基于频繁模式有向无环图的数据流频繁模式挖掘算法,它根据事务到来的时间给每个事务一个序号,每个事务中的数据项在存储前按数据项的顺序进行调整,频繁模式有向无环图的构建遵循这个顺序并用序号来记录事务与数据项的包含关系,模式增长过程只需要增加有向边上的序号。通过逆向遍历带有相同序号的有向边,产生条件模式基,根据动态定义的阈值抽取条件模式基信息,一次扫描数据库得到频繁模式。实验结果表明,本文算法的执行效率优于FP-growth算法,且存储节点的数目明显减少。     

基于图的挖掘关联规则改进算法

关联知识挖掘算法中一种广为人知的算法就是Aprior算法,之后所有关联规则挖掘算法的基本思想都是基于频繁项目集发现算法的基础上进行了改进.为了提高关联规则挖掘效率,首先回顾了基于图的关联规则挖掘算法;然后,在此基础上进行了改进,把关联规则挖掘中寻找频繁项集的问题转换为图中寻找完全子图的问题,通过在图中查找完全子图来寻找频繁项集.提出了一种基于图的关联规则挖掘改进算法,并且对原算法和改进的算法从时间和空间的性能进行了比较分析,得出改进的算法是有效可行的.最后从实验结果得出结论GenerateItemsets算法比DGBFIG算法优.     

基于图的频繁项集挖掘

通过对Apriori算法的频繁项目集的分析研究,给出了基于图的频繁项集挖掘算法.该算法在求频繁K-项集的过程中只需一次扫描数据库,避免了Apriori算法需多次扫描数据库的不足.同时,由于在有向图中利用有限节点之间的路径求频繁K-项集,该算法减少了Apriori算法中需多次进行连接运算的不足.     

一种基于特征子图的不确定图分类算法

采用频繁子图作为特征子图,对不确定图进行分类.提出AGF频繁子图挖掘算法,该算法将频繁子图挖掘问题转换为频繁项挖掘问题,可有效提高频繁子图生成效率.利用频繁子图构造分类模型,首次应用于不确定图,通过实验证明,给出的分类算法具有良好的分类正确率.     

基于图的数据挖掘算法研究

对图数据频繁模式的挖掘是近年的研究热点,而从图数据库中挖掘频繁模式的关键是子图测试和候选子图生成操作。与传统广泛研究的频繁项集、频繁序列、频繁子树挖掘相比较,频繁子图的挖掘更复杂、更有难度,因为图同构问题是一个NP-完全问题。因此,必须有个好的规范化编码和有效的算法来避免子图同构这个难题。     

基于图模型的云平台应用部署技术研究

为了实现与平台无关的应用部署,提出了一种基于“部署图”的应用部署方案,给出一个通用云平台应用部署体系,重点介绍了部署工具的设计与实现技术,并实现了一个原型系统,结合部署实例证明所提部署方案是可行的且具有平台无关、可视化、可复用等优点.     

有向图的同构

证明“图Ｇ与图Ｆ同构当且仅当它们有机合的ＶＣ算法”的结论,对于简单有向图依然成立。     

不一致数据库中基于用户语义模板的评论可信度计算

在清洗算法不能有效地纠正不一致数据的情况下,“知情”用户给出的关于其正确取值的评论,对数据库的其他用户意义重大,可以帮助他们甄别错误数据,并在不丢失信息的前提下,尽可能地从不一致数据库中获取有用信息,但只有正确可信的评论才能有如此意义.因此,评论的可信度估算是这类应用中的一个关键问题.和互联网评论不同,数据库一般向系统内用户开放,用户的特征更易于提取,其语义确定.由于数据是对现实世界的描述,能对同一评论对象,发出类似评论的用户往往具有相同的背景或语义特征.文章提出了一种基于用户的特征分析的评论可信度计算算法,有针对性地解决了上述问题.算法首先根据语义特征,对历史评论者进行用户社区挖掘,得到在某准确度下评论过某对象的用户公共特征,形成用户模板;其次,对于任意给定新评论,通过其评论者和用户公共特征模板的匹配程度,并综合该评论者可信度、评论者和评论对象的语义相关性等关键因素,计算出该评论的可信度.实验证明,该算法在时间和准确率两方面都是有效的.     

基于gSpan算法的未知化合物毒性预测

gSpan算法是一种基于频繁图的挖掘算法。该算法基于无候选人产生的频繁子图,在图中建立字典序标号,将每个图映射为最小DFS code,再采用深度优先搜索策略挖掘频繁连接子图。与前人算法相比,该算法在生成候选子图时,冗余子图的产生量大大减少;在计算候选子图支持度时避免了大量重复扫描数据库,性能卓越。该文的贡献是将gSpan算法应用在挖掘与已知毒性化合物具有相同子结构的化合物研究工作中,进行未知化合物的毒性预测,对相关领域应用发展具有重要意义。     

频繁闭图挖掘算法在中医方剂中的应用

通过分析传统中医药物间的影响关系和图结构数据节点间关系的共通性, 将中医方剂学中处方的药物联系按规则转换为图结构数据, 采用频繁闭图挖掘算法CloseGraph对图结构化的处方数据进行操作, 得到图结构中代表具有特定功能的频繁闭图, 再转换解释获得各中医方剂中对特定病症起决定疗效的核心药物组合及组合形式. 结果表明, 该方法可行、 有效, 成功地将图挖掘策略引入了中医方剂研究领域.