1算法设计目标

输入不同的命令是用户使用Linux服务器的基本途径，通过长时间采集不同用户在使用服务器过程中所使用的命令序列，挖掘其中频繁出现的命令序列，可以帮助我们了解用户使用该服务器的基本规律。

此外，如果存在多台服务器，那么我们可以分析挖掘这些服务器中用户输入的命令序列，挖掘其中存在的频繁模式，可以了解用户使用这些服务器的根本目的。如果当这些服务器被同一个黑客攻击，或者这些服务器遭受了同一种类型的攻击，那么我们挖掘出的频繁命令模式中会存在黑客输入的命令序列，据此可以尝试理解黑客的攻击手段，还原攻击场景，为防范奠定基础。

本项目拟采用FP-Growth算法实现用户输入命令序列频繁模式的挖掘，以在不同时间段采集到的用户输入命令序列为基础，通过用户shell+ip+主机名按不同用户的登录（三者都相同才视为同一用户）构建事务，以此为基础实现用户输入命令序列频繁模式的挖掘

2 算法基本原理

FP-Growth算法主要解决挖掘在多个集合中出现次数达到一定阈值的频繁项的集合。FP树是一种输入数据的压缩表示，它通过逐个读入事务，并把事务映射到FP树中的一条路径来构造，由于不同的事务可能会有若干个相同的项，因此它们的路径可能部分重叠。路径相互重叠越多，使用FP树结构获得的压缩效果越好。下表显示了一个数据集，它包含10个事务和5个项。

2.1 FP树构造的基本过程

在下图给出了读入三个事务之后的FP树的结构以及最终完成构建的FP树，初始，FP树仅包含一个根节点，用符号null标记，随后，用如下方法扩充FP树：

Step1：扫描一次数据，确定每个项的支持度计数，丢弃非频繁项，而将频繁项按照支持度递减排序，对于上面给出的数据集，出现频度由高到低依次是a,e。

Step2：算法第二次扫描数据集，构建FP树，读入第一个事务{a,b}后，创建标记为a和b的节点，然后形成null->a->b的路径，对该事务编码，该路径上的所有节点频度为1。

Step3：读入第二个事务{b,d}之后，为项b,d创建新的节点集，然后连接null->b->c->d形成一条新的节点集，形成一条代表该事务的路径，该路径的每个节点的频度计数也等于1，尽管前两个事务有一个共同项b,但是他们的路径不相交，因为这两个事务没有共同的前缀

Step4：第三个事务{a,e}与第一个事务共享一个共同前缀项a,所以第三个事务的路径null->a->c->d->e与第一个事务的路径null->a->b部分重叠，因为他们的路径有重叠，所以节点a的频度计数增加为2，而新创建的节点c,d和e的频度计数等于1

Step5：继续该过程直到每个事务都映射到FP树的一条路径，读入所有的事务后形成FP树

Step6：FP树还包含一个连接具有相同项的节点的指针列表，这些指针再上图中用虚线表示，有助于快速访问树中的项。

2.2 频繁项挖掘的过程

FP-growth是一种以自底向上方式探索树，由FP树产生频繁项集的算法，给定上面构建的FP树，算法按e,a的顺序在每一颗条件FP树中递归查找以其结尾的频繁项集。由于每一个事务都映射到FP树中的一条路径，因此通过仅考察包含特定节点（例如e）的路径，就可以发现以e结尾的频繁项集，使用与节点e相关联的指针，可以快速访问这些路径。

第一步收集包含e节点的所有路径，这些初始的路径称为前缀路径，如下图a所示。

Step1：由图a中所显示的前缀路径，通过把与节点e相关联的支持度计数相加得到e的支持度计数。假定最小支持度为2，因为{e}的支持度是3所以它是频繁项集

Step2：由于{e}是频繁的，因此算法必须解决发现以de,ce,be和ae结尾的频繁项集的子问题，在解决这些问题之前，必须先将前缀路径转化为条件FP树，除了用于发现以某特定后缀结尾的频繁项集之外，条件FP树的结构与FP树类似，条件FP树通过以下步骤得到。

Step2.1：首先，必须更新前缀路径上的支持度计数，因为某些计数包含那些不含项e的事务。例如，下图中的最右边路径null->b:2->c:2->e:1,包含并不含项e的事务{b,c},因此,必须将前缀路径上的计数调整为1，以反映包含{b,e}事务的实际个数。

Step2.2：删除e的节点，修剪前缀路径，删除这些节点是因为，沿这些前缀路径的支持度计数已经更新，以反映包含e的那些事务，并且发现以de,be,ae结尾的频繁项集的子问题不再需要节点e的信息。

Step2.3：更新沿前缀路径上的支持度计数之后，某些项可能不再是频繁的，例如，节点b只出现了一次，它的支持度计数等于1，这就意味着只有一个事务同时包含b和e,因为所有以be结尾的项集一定都是非频繁的，所以在以后的分析中可以安全的忽略b。

Step2.4：e的条件FP树显示在下图b中，该树看上去与原来的前缀路径不同，因为频度计数已经更新，并且节点b和e已经被删除，由于不是单个路径的树，所以需要继续挖掘。

Step2.5：FP增长使用e的条件FP树来解决发现以de,和ae结尾的频繁项集的子问题，为了发现以de结尾的频繁项集，从项e的条件FP树收集d的所有前缀路径，通过将与节点d相关联的频度计数求和，得到项集{d,e}的支持度计数。因为项集{d,e}支持度计数等于2，所以它是频繁项集，接下来，算法采用上一个步骤中的方法构建de的条件FP树。更新了支持度计数并删除了非频繁项c之后，de的条件FP显示在下图d中，因为该条件FP树只包含一个支持度等于最小支持度的项a，是单路径FP树，所以将路径上的节点排列组合与{e,d}组合，提取出{a,e}并转到下一个子问题，产生以ce结尾频繁项集，处理c的前缀路径后，只发现项集{c,e}是频繁的，接下来，算法继续解决下一个子问题并发现项集{a,e}是剩下唯一的频繁项集。

发现以e结尾的频繁项集之后，算法通过处理与节点d相关联的路径，进一步寻找以d为结尾的频繁项集，继续该过程，直到处理了所有与节点c,b和a相关联的路径为止。每一次递归，都要通过更新前缀路径中的支持度计数和删除非频繁的项来构建条件FP树，由于子问题时不相交的，因此FP增长不会产生任何重复的项集，此外，与节点相关联的支持度计数允许算法在产生相同的后缀项时进行支持度计数。

（编辑：源码网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!