您现在的位置是:首页 >其他 >【Graph Data Mining】— Apriori-Based 基于Apriori算法挖掘图数据中频繁子结构的方法网站首页其他

【Graph Data Mining】— Apriori-Based 基于Apriori算法挖掘图数据中频繁子结构的方法

之墨_ 2024-06-14 17:20:31
简介【Graph Data Mining】— Apriori-Based 基于Apriori算法挖掘图数据中频繁子结构的方法
  1. Apriori-based算法基于Apriori原理,使用候选生成和支持度计数两个步骤来发现频繁子结构。具体来说,算法首先通过枚举所有可能的子结构来生成候选子结构,然后扫描数据集来计算每个候选子结构的支持度,并筛选出满足最小支持度阈值的频繁子结构。
  2. Apriori-based算法的优点是可以高效地处理大规模图数据,并且可以发现非常复杂的子结构。与其他频繁子结构挖掘算法相比,Apriori-based算法具有更好的可扩展性和灵活性,可以适应不同类型的图数据。此外,Apriori-based算法还可以用于发现异常子结构、子结构聚类等任务。
  3. 需要注意的是,Apriori-based算法的效率和性能取决于最小支持度阈值的设置。如果设置的阈值过低,可能会产生大量的候选子结构,导致搜索空间过大;如果设置的阈值过高,可能会忽略一些有用的频繁子结构。因此,在实际应用中,需要根据具体情况选择合适的最小支持度阈值。

论文:
An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data

Basic Information:

  • Title: An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data (基于Apriori算法挖掘图数据中频繁子结构的方法)
  • Authors: Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda
  • Affiliation: I.S.I.R., Osaka University (日本大阪大学智能信息系统研究所)
  • Keywords: graph data, frequent substructures, adjacency matrix, association rules, Apriori algorithm
  • URLs: Paper, GitHub

Note: The GitHub link is to the code for the AGM algorithm, which is based on the approach proposed in this paper.

概要:

  • a. 本文的研究背景:
    • 本文提出了一种新的方法,名为apriori-based graph mining (AGM),用于有效地从图结构数据中挖掘频繁的子结构和关联规则。
  • b. 过去的方法、问题和动机:
    • 通过叠加支持和置信度,以及进行基于图的归纳矩阵变换,来生成归纳子图,这些方法可能由于其贪婪的搜索策略而错过重要的模式,所以需要提出一个新的方法。
  • c. 本文中提出的研究方法:
    • AGM方法将邻接矩阵的数学图表示与篮子分析的扩展Apriori算法相结合。
  • d. 方法在本文中实现的任务和性能:
    • AGM在人工模拟数据和牛津大学和NTP的癌症数据上进行了评估,证明了它在解决实际问题时的优越性能。

背景:

  • a. 主题和特征:
    • 本文关注的主题是从图结构数据中发掘频繁的子结构和关联规则,并使用计算方法实现。
  • b. 历史发展:
    • 随着越来越多的数据转化为非结构化数据和半结构化数据,发现有效的挖掘技术变得至关重要。随着研究的深入,一些基于图的算法相继被提出,例如子图挖掘和归纳算法。
  • c. 过去的方法:
    • 过去的方法包括子图挖掘和SUBDUE,这些方法由于其贪婪的搜索策略会错过重要的模式。
  • d. 过去研究的缺陷:
    • 过去的方法效率不高,无法处理大型结构化数据。
  • e. 需要解决的当前问题:
    • 必须寻找一种新的,更高效的算法来处理大型结构化数据,识别其中的重要模式和关联规则。

方法:

  • a. 该研究的理论基础:

    • AGM方法将邻接矩阵的数学图表示与篮子分析的扩展Apriori算法相结合,以发现图交易数据中的频繁归纳子图。
  • b. 本文的技术路线(逐步实现):

    • 该算法使用支持和置信度概念通过产生级别搜索来生成归纳子图。
    • 然后,对邻接矩阵中的节点进行排序,并通过变换矩阵将矩阵转换为其正常形式。
    • 由于产生具有等效归纳子图的多个正常形式,因此对于这些形式,定义了一个规范形式来计算支持值。
    • 然后使用先前已知的转换矩阵将每个正常形式索引到其规范形式,从而可以有效地计算支持值。
    • join过程为所有可能的值对创建多个Zk+1,并使用自下而上的方法将非正常形式的邻接矩阵转换为正常形式。
    • 直到在中间层产生的所有子图都处于它们的正常形式中,才确认该算法有效。
    • 归一化是通过对原始矩阵的行和列进行置换来构造的,并用于计算子图的出现频率。
  • c. 该方法和之前工作的创新、性能和工作量:

    • 与先前开发的技术相比,AGM方法是发现频繁结构的新型替代方法,并且在性能上要比之前更好。
    • 该方法在处理大型结构化数据时具有高效性能,能够识别表征癌症的更重要的子结构。

    结论:

  • a. 研究工作的意义:

    • AGM方法是有效分析给定图数据集的技术,可以用于挖掘出经常出现的诱导子图和它们之间的关联规则。
  • b. 创新、性能和工作量:

    • AGM方法的计算复杂度可控且可行,并在实际评估中表现出强大的性能。
    • 通过实际评估,AGM在特定条件下表现出强有力的性能,成为分析现实世界数据的有价值工具。
  • c. 研究结论(列出点):

    • AGM方法可以在区分样本中发现更多并且更特殊的规律,因此对于寻找关键图模式信息具有重要意义。
    • AGM方法使用简单有效的算法来挖掘高级别子结构,从而提供了一种比存在算法更先进的数据分析工具。
    • AGM方法的应用能够绘制反应路径,并提供关键的分子信息,从而有助于解释人体制造化合物的毒性问题。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。