关于数据挖掘的小论文

总结随着计算机和信息技术的发展，数据挖掘技术已广泛应用于数据仓库，人工智能，模式识别，生物信息等许多领域. 在循序渐进的研究过程中，我们面前也出现了越来越多的问题. 人们开始意识到使用图形可以更好地描述这些数据结构，然后在此基础上进行挖掘可以获取更多有用的信息. 因此，对于诸如图的结构化数据数据挖掘论文，它已经成为数据挖掘研究领域中的重要研究方向. 本文首先分析了图挖掘的背景. 图挖掘研究的内容大致分为: 频繁子图挖掘，图聚类和分类，图查询，约束图挖掘等. 其次，介绍与图挖掘相关的概念. 再次，根据gSpan算法，模拟了频繁子图挖掘的效率. 最后是本文的摘要. 关键字数据挖掘；频繁的子图；摘要随着计算机科学和信息技术的发展，数据挖掘技术已广泛应用于数据仓库，人工智能，模式识别，生物信息学等许多领域. 在研究过程中，提出了越来越多的问题，人们开始意识到图形可以更加清晰地描述这些数据结构，因此可以挖掘出更多有用的信息. 因此，以图为主的结构化数据研究已成为重要的研究领域. 首先，本文分析了图挖掘的背景. 图挖掘包括频繁的子图挖掘，图聚类和分类，图查询和约束图挖掘. 其次，介绍与图挖掘相关的概念. 再次，根据gSpan算法，模拟频繁子图挖掘的效率. 最后，对本文进行总结和展望. 关键词数据挖掘；频繁的子图；图挖掘. gSpan算法的仿真1 1.图挖掘背景随着数据挖掘[1]方法的发展，目标数据结构也在悄然发生变化. 传统的非结构化数据挖掘，例如序列，事务，文本等. 该方法已不能满足结构化数据挖掘不断出现的需求.

数据挖掘已从原始的简单结构或简单关系数据集演变为具有许多应用程序背景，对象之间或对象内部关系更加复杂的树形结构模式（XML访问路径，核糖核酸分子结构等）. 结构模式. 图结构是最常见的数据结构类型，它可以描述世界上万物之间的复杂关系. 图挖掘研究的内容大致可分为: 频繁子图挖掘，图聚类和分类，图查询，约束图挖掘[4]等. 在这些面向图的挖掘内容中，频繁的子图挖掘一直是研究人员的关键问题. 图的频繁子图挖掘是从单个大图[5]或许多图中找到满足最小出现次数的公共子图. 它是具有约束的图聚类，分类，查询和图挖掘. 挖掘问题研究的基础. 对于频繁的子图挖掘问题，已经陆续提出了许多相应的算法. 初始频繁子图挖掘算法采用模糊计算方法，得到了近似的挖掘结果. 2000年，Inokuchi和Kuramochi先后将Apriori [2]的思想应用于频繁子图挖掘算法，逐层构造了图的顶点和边缘，从而产生了一种可以完全枚举所有频繁子图的算法，从而正式开创了利用数据挖掘的思想来解决图挖掘的问题. 近年来，基于FP增长思想的gSpan [3]算法将频繁子图挖掘算法的效率提高到了一个新水平.

2 2.概念描述2.1标记图的同构由标记图G和G'提供，如果存在映射函数f :) V（GV（G）'，则满足: （1）V （G）v，））lb（f（v）lb（vii;（2））（），（GE v vji，）（））（），（（'GE vfv fj i ）））（），（（（lb）），（（jij iv fvfvv lb数据挖掘论文，然后说G和G'是同构的，表示为GG. ）2.2带标签图的子图带有带标签图G子图'H与G同构，则G称为H的子图，记为HG如图1所示，图1（b）是图的子图. 1（a）. 图1 2.3图的支持和频繁的子图具有图库}，... ,, {G3 2 1 nG GGGDB和图G'，图G'在图库DB G中的支持|} HG'| {|）'sup（和GDB HHG，即在DB G中以G'作为子图的带标签图的数量.

给出最小支持minsup，在DB G中，支持大于minsup的子图称为频繁子图. 让G'成为一个频繁的子图. 如果没有频繁子图G，则G'是G的子图，则子图G'被称为最大频繁子图. 3 3.关键算法3.1 n gSpan算法gSpan算法的第一步是扫描图形数据集，以删除不常见的顶点和边缘（顶点和边缘的支持小于最小支持）. 第二步将包括k个边缘的频率. 子图k和fG用作图. 根据最右边的扩展规则，生成具有k + 1条边的候选子图1 k cG，计算支持度，并生成具有k + l条边的频繁子图1 k k fG，并使用1，k k fG作为新的图. 在第三步中，重复第二步，直到没有新的候选子图或频繁子图生成为止. gspan算法的描述如下: 3.2算法仿真顾名思义，DFS（深度优先Seareh）编码是深度优先遍历连接图时的路径代码. 对于遍历的边e，使用五元组（jeij il llv ,,,, v表示，其中il代表点iv的标签，lj代表点jv的标签，el代表边e的标签.

如图2所示，相同的连接图（a）可以通过不同的搜索顺序生成不同的搜索路径（b），（c），（d）. 相应的DFS代码如表1所示. 可以看出，图深度优先搜索树不是唯一的，它取决于图顶点的访问顺序. 因此，不可能根据DFS序列判断两个图是否同构. 因此，使用DFS字典顺序和最小DFS编码作为其规范表达式来解决此问题. 图2表1具有给定标签的图形的任意两个边），（e5 4 3 2 1a aaaaa，），（e5 4 3 2 1 bb bbbb线性顺序由以下条件: l）仅当且仅当i ib a，5、4、3、2、1i时； 2）b ae e当且仅当k为5 1k，因此j jb a（kj1）和k kb a； 3）ae eb，否则. 在表1中，对于边缘0e，图2（b）和图2（d）的前4个元素相同，而第5个元素YX，因此）、、 1，0（）、、 1，0（Y a XX a X. 可以推断出（b），（e），（d）的偏序是: 

是图2（a）的最小DFS编码. 两个图的最小DFS编码和同构之间存在重要的关系: 给定两个图G和'G，当且仅当（）（）（'G dfs G dfs. 为了挖掘频繁的子图，只需要对最小的DFS代码执行最右边的扩展，因为这种扩展将确保挖掘结果的完整性图3显示了如何通过最右边的扩展在搜索树中排列所有DFS代码. 根是Null编码，每个节点都是由图形代码形成的DFS代码，每个边沿代表从长度（k-1）的DFS代码到长度k的DFS代码的最右边扩展. 根据DFS字典顺序，左兄弟小于右兄弟. 由于该图至少具有一个DFS代码，因此搜索树可以枚举该图数据集中所有可能的子图，但是，一个图可能具有多个DFS代码，最小和非最小非最小DFS编码搜索不会产生有用的结果. 递归gSpan算法，以便找到他们的频繁后代，直到支持率小于minsup或其编码不再最小为止. 图3本文使用g ++来实现gSpan算法. 在挖掘频繁子图的实验环境中，奔腾IV 2.80GHz处理器，256MB RAM，80G硬盘，Windows XP Professional SP2操作系统.

频繁子图挖掘的结果是: 给定DB G和最小支持minsup，要求能够挖掘满足最小支持的所有最大频繁子图. 例如，在图4中，当2minsup时，可以挖掘（1）和（2）中所示的频繁子图. 图4以节点数为m，边数为n的图为例，DFS编码表示的图的同构判断效率为O（n2）. 对于这样的图形，由于存在n条边，因此在执行深度遍历（即在遍历路径中添加一条边）时，每个边都有两种状态: 选择和未选择，因此在获得最小DFS编码之前，需要n2个遍历路径. 当gSpan放大频繁子图的边时，每个合格边都有机会被选择进行放大，因此其扩展复杂度为O（n2），算法的总复杂度为O（n2 * n2）. 4 4.结论作为数据挖掘领域的一个新的研究热点，图形模式挖掘技术正在迅速发展. 图形模式挖掘的应用已逐渐渗透到现实生活中的许多领域. 它基于图挖掘的思想得到了极大的扩展. 过去，以项目集作为操作对象进行挖掘的能力真正反映了现实生活中的相互联系，并挖掘出更复杂，更现实的模型. 因此，对于图等结构化数据，结合非结构化数据挖掘的经验和方法论，实现结构化数据的有效挖掘已成为数据挖掘领域的重要研究方向.

在图挖掘的开始，Apriori的想法主要用于子图的扩展. 由于生成频繁子图，因此每次从k个频繁图到k + 1个频繁图，都必须调用同构判断算法，在挖掘过程中会生成大量重复的候选子图，从而降低了算法的整体效率. 在随后的算法中，我们采用了深度优先子图增长策略，这大大提高了图挖掘算法的效率. 在图挖掘中，您可以扩展挖掘对象并研究约束子图的挖掘. 在应用方面，它可以扩展到实际化学分子库的图形. 参考文献[1] J. Han，m.. 坎伯. 数据挖掘概念与技术[M]（第二版）. 北京: 机械工业出版社，2006，p489-513. [2] R. Agrawal，T. Imielinski和ANSwalni. 大型中项目集之间的关联规则的挖掘. 在1993年ACM SIGMOD国际日期管理会议论文集，VOL22（2），p207-216，1993 [ 3] YanY，HanJ.gSpan: 基于图的子结构模式挖掘. Proe. ICDM，2002年[4]胡海燕，严希峰，黄宇，韩佳伟，周鸿. 跨生物网络挖掘相干稠密子图以实现功能变迁[J]. 生物信息学，2005，21（l）: i213-i221. [5] LB Holder，DJ Cook，S Djoko. SUBDUE系统中的子结构发现[A]中的Proc AAAI Workshop知识发现[C]. 华盛顿州西雅图市: AAAI出版社，1994.169-180.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-181880-1.html