您现在的位置是:首页 >其他 >【Graph Data Mining】— Apriori-Based 基于Apriori算法挖掘图数据中频繁子结构的方法网站首页其他
【Graph Data Mining】— Apriori-Based 基于Apriori算法挖掘图数据中频繁子结构的方法
简介【Graph Data Mining】— Apriori-Based 基于Apriori算法挖掘图数据中频繁子结构的方法
- Apriori-based算法基于Apriori原理,使用候选生成和支持度计数两个步骤来发现频繁子结构。具体来说,算法首先通过枚举所有可能的子结构来生成候选子结构,然后扫描数据集来计算每个候选子结构的支持度,并筛选出满足最小支持度阈值的频繁子结构。
- Apriori-based算法的优点是可以高效地处理大规模图数据,并且可以发现非常复杂的子结构。与其他频繁子结构挖掘算法相比,Apriori-based算法具有更好的可扩展性和灵活性,可以适应不同类型的图数据。此外,Apriori-based算法还可以用于发现异常子结构、子结构聚类等任务。
- 需要注意的是,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方法的应用能够绘制反应路径,并提供关键的分子信息,从而有助于解释人体制造化合物的毒性问题。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。