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增添不会发生任何一再的项集，另外，与节点相干联的支持度计数应承算法在发生沟通的后缀项时举办支持度计数。

（编辑：湖南网）

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