基于确定图的频繁子图挖掘技术概述

化学信息学、生物信息学、医学和社会科学等领域的科学研究的迅速发展积累了大量的图数据,如何从复杂和庞大的图数据中挖掘出有效信息成为数据挖掘领域的热点。通过介绍现阶段图数据挖掘技术的进展,特别是确定图挖掘技术中有代表性的频繁子图挖掘技术研究,讨论并预测了频繁子图挖掘研究的发展趋势。     

从不确定图中挖掘频繁子图模式

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.     

基于路径的频繁子图挖掘算法研究

图挖掘是数据挖掘的一个重要研究方向,而图挖掘主要集中在图数据集内频繁子图的挖掘。频繁子图挖掘技术的关键是建立有效机制减少冗余候选子图,以便高效计算和处理所需的频繁子图。提出了一种基于路径的频繁子图挖掘算法,该算法首先找出所有频繁边从而挖掘出频繁单路径,然后通过组合、双射和操作扩展出较多的频繁路径,再通过连接操作产生所有频繁子图候选集。通过定理证明了该算法的正确性和完整性,从理论上分析了该算法时间复杂度低于现有的算法,最后进行了2个图数据集实验,在候选集产生的数量和时间性能2方面验证了算法的优越性。     

频繁子图挖掘算法研究

图像能表达丰富语义,但增加了数据结构的复杂性和感兴趣子结构的挖掘难度。综合应用图论知识和数据挖掘的各种技术,对图像进行规范化编码,通过连接和扩展操作产生所有候选子图,引用嵌入集概念,计算候选子图的支持度和频繁度。提出频繁子图挖掘算法FSubgraphM,能从图数据库中挖掘频繁导出子图。     

基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

Apriori算法用于频繁子图挖掘的改进方法

AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。     

基于动态行为和特征模式的异常检测模型

该文针对现有的异常检测方法大多只关注系统调用出现的频率或者局部变化的情况,提出了一种将动态行为和全局特征结合起来的检测模型（DBCPIDS）．文章针对满足支持度要求的系统调用短序列,给出了特征模式的概念,并以此为基础提出了基于改进的隐马尔科夫方法（IHMM）．当利用该模型进行检测时,首先用程序轨迹匹配特征模式,如果不匹配再用IHMM进行检测,从而使得该检测模型充分利用了程序正常运行的全局特征和程序运行期间的局部变化．通过实验表明,利用该模型进行异常检测,具有很高的检测率和较低的误报率．     

基于序列模式挖掘的入侵检测系统的研究

对入侵检测和数据挖掘从定义和分类等各方面等进行了基本介绍,提出了一个基于数据挖掘的入侵检测系统的总体框架,其整个系统分为训练阶段和测试阶段,对其中各个模块进行基本的功能分析。为了提高数据挖掘的效率,可以将序列模式挖掘引入该入侵检测系统中。将关联规则算法和序列模式挖掘算法同时使用,增加挖掘的粒度。对序列模式挖掘的算法进行了具体分析,并通过具体的实例来说明引入序列模式挖掘能更好地提高数据挖掘的效率。     

利用MapReduce平台实现高效并行的频繁子图挖掘

频繁子图挖掘是数据挖掘领域的一个重要问题,并且有着广泛的应用。在Hadoop平台上实现了一种基于MapReduce的高效频繁子图挖掘算法Cloud-GFSG（cloud-global frequent subgraph）。该算法基于Apriori思想,在扩展边生成新的子图时,使用已经挖掘出的k-1阶的频繁子图生成k阶的频繁子图。同时,检查是否存在待扩展生成的子图,设定生成的频繁子图表示规则,保证了频繁子图信息的唯一性。较同类算法相比,该算法在挖掘频繁子图时更具通用性,并且在扩展边时避免产生大量的复制图,从而使得算法的正确性得以保证,且运行效率显著提高。     

关联规则挖掘算法在入侵检测中的研究与应用

本文提出了一种有效的频繁模式挖掘算法,通过研究Sendmail各进程中的系统调用号之间的关联关系,建立正常以及异常行为序列库,利用该频繁模式挖掘算法对各序列库进行频繁模式挖掘,以关联规则的形式获得能区分正常进程与正常进程的典型模式,继而找出所有满足置信度的分类规则,从而检测各进程序列中的入侵行为。     

Network intrusion detection based on system calls and data mining

Anomaly intrusion detection is currently an active research topic in the field of network security. This paper proposes a novel method for detecting anomalous program behavior, which is applicable to host-based intrusion detection systems monitoring system call activities. The method employs data mining techniques to model the normal behavior of a privileged program, and extracts normal system call sequences according to their supports and confidences in the training data. At the detection stage, a fixed-length sequence pattern matching algorithm is utilized to perform the comparison of the current behavior and historic normal behavior, which is less computationally expensive than the variable-length pattern matching algorithm proposed by Hofmeyr et al. At the detection stage, the temporal correlation of the audit data is taken into account, and two alternative schemes could be used to distinguish between normalities and intrusions. The method gives attention to both computational efficiency and detection accuracy, and is especially suitable for online detection. It has been applied to practical hosted-based intrusion detection systems, and has achieved high detection performance.     

一种基于序列挖掘的网络入侵检测新方法

网络入侵检测是信息安全重要的研究问题。近年来,这方面的研究取得了很多很好的成果,但大部分方法面临检测率不高的特点。基于异常的入侵检测通常是人为选择网络连接属性,这些属性在正常和异常时具有比较明显的区别,以此来判断未知的网络连接正常与否。该方法具有一定的随机性,从而影响检测率。首先提出一种基于正常网络连接序列内在规则的属性选择算法,实现属性选择的自动化,并同时将多维序列压缩到一维序列;其次使用序列挖掘的方法训练网络连接得到正常规则库,然后利用正常网络连接规则库判断新的网络连接是否正常;最后,在KDD99数据集上进行试验,结果显示,算法检测率较高。     

频繁模式挖掘的约束算法

在频繁模式挖掘过程中能够动态改变约束的算法比较少.提出了一种基于约束的频繁模式挖掘算法MCFP.MCFP首先按照约束的性质来建立频繁模式树,并且只需扫描一遍数据库,然后建立每个项的条件树,挖掘以该项为前缀的最大频繁模式,并用最大模式树来存储,最后根据最大模式来找出所有支持度明确的频繁模式.MCFP算法允许用户在挖掘频繁模式过程中动态地改变约束.实验表明,该算法与iCFP算法相比是很有效的.     

基于频繁序列挖掘的文件系统缓存算法设计

传统缓存算法存在命中率低、交换率高等问题,且现有缓存算法在分布式大数据存储系统中并不适用,为此提出了一种基于频繁序列挖掘的自适应缓存策略。该方法使用数据挖掘算法挖掘历史访问窗口内的频繁序列,将频繁序列模糊合并后构建匹配模式集合以供查询。当新的访问来临时,将固定访问长度内的子序列与匹配模式集合进行匹配,然后根据匹配结果预取数据,同时结合修改后的S4LRU(4-segmented least recently used)数据结构进行缓存数据换出。在公开的大数据处理trace集上进行了仿真实验,实验结果表明,在不同的缓存大小下,提出算法与现有典型缓存算法相比,平均命中率提高了0.327倍,平均交换率降低了0.33倍,同时具有低开销和高时效的特点。此结果表明,该方法较传统替换算法而言是一个更为有效的缓存策略。     

基于频繁模式发现的时间序列异常检测方法

针对传统异常片段检测方法在处理增量式时间序列时效率低的问题,提出一种基于频繁模式发现的时间序列异常检测（TSAD）方法。首先,将历史输入的时间序列数据进行符号转化;其次,利用符号化特征找出历史序列数据集中的频繁模式;最后,结合最长公共子序列匹配方法度量频繁模式与当前新增加时间序列数据之间的相似度,从而发现新增加数据中的异常模式。与基于滑动窗口预测的水文时间序列异常检测方法（TSOD）和基于扩展符号聚集近似的水文时间序列异常挖掘方法（ESAA）相比,对于实验选择的三种类型的时间序列数据,TSAD的检测率都超过90%;TSOD对规则性较强的序列检测率较高,能达到99%,但对噪声干扰较大的序列检测率较低,对数据偏向性较强;ESAA对三种类型的数据检测率均不超过70%。实验结果表明,TSAD在时间序列异常检测中能够较好地发现异常片段。     

一种基于动态聚类的异常入侵检测方法

运用数据挖掘方法进行入侵检测已经成为网络安全领域的一个重要研究方向。提出一种动态聚类的数据挖掘方法进行异常入侵检测,该方法将不同用户行为的特征动态聚集,根据各个子的类支持度与预设的检测阈值比较来区分正常与异常。由于动态聚类算法在每次聚类过程中都检验归类的合理性,因此获得很好的聚类效果。实时检测试验得到了较高的检测率和较低的误报率。     

基于异常的入侵检测技术浅析

入侵检测是一个比较新的、迅速发展的领域,已成为网络安全体系结构中的一个重要的环节。详细介绍了基于异常的入侵检测技术的原理和基本流程,并结合现有的基于异常的入侵检测系统,重点分析了几种常用的异常检测技术,讨论了基于异常的入侵检测技术的优点和存在的问题。