一种基于频繁子图挖掘的网络系统关联服务发现方法与流程

1.本发明涉及关联数据挖掘与服务发现问题，具体涉及一种基于频繁子图挖掘的网络系统关联服务发现方法。

背景技术：

2.网络系统关联服务发现在现实的数据中心网络中很重要。面对海量的数据流，不仅要正确有效的统计出每个ip地址的访问与被访问次数等信息，还应根据这些信息检测出哪些节点提供了服务以及与提供服务的这些节点有所关联或者关联程度较高的一系列节点信息。一方面这有利于更有效的维护数据中心网络安全，避免某些未报备的提供服务的节点对网络内其它服务节点造成不好的影响。另一方面，这有利于对数据中心网络进行维护，在检测出网络系统关联服务后，可以更有针对性地对某些关联度较高或者关联面广的节点进行维护，从而在一定程度上减少维护成本，提高维护效率。
3.目前已存在众多的数据统计及相关数据挖掘技术。但并未有一个与此目标问题结合较深的解决方法，所以如何利用相关技术，并结合该问题场景，有效地完成网络系统关联服务发现，这是需要思考和解决的问题。

技术实现要素：

4.本发明的目的在于提出一种基于频繁子图挖掘的网络系统关联服务发现方法，能够有效地解决目前还未有结合相关挖掘技术并适用于上述任务场景的问题。
5.为了实现以上发明目的，本发明的技术方案如下：
6.一种基于频繁子图挖掘的网络系统关联服务发现方法，包括以下步骤：
7.(1)为每个ip地址设置一个全局coco sketch(以下简称为sketch)，在接收到网络流数据后，解析得到源ip地址、目的ip地址等信息，将这些信息更新到每个ip对应的全局sketch中；
8.(2)访问统计后的sketch信息文件，按照一定的时间间隔提取(源ip，源端口，目的ip，目的端口)等生成图序列所需要的信息，并整合所有提取后的信息，生成包含访问被访问等关系的图序列数据集并通过k-means聚类方法，将图序列数据集进行进一步划分；
9.(3)根据上一步得到的包含网络访问相关信息的图序列数据集，对图集中的图进行深度优先遍历，生成图的该单边频繁子图的所有单边频繁子图树，并且以一棵树为基树把该图的其它单边频繁子图树都重叠到该树上；
10.(4)生成最初基树的图的边的五元素并以边在存储结构中的顺序作为边的唯一标识符保存到设定的存储结构映射边集中；然后将图序列数据分别与映射树进行重叠操作，通过映射树中边上记录的对应映射边集中边的编号，把重叠成功的边在映射边集中作标记，重叠不成功的边添加到映射边集中并作标记；
11.(5)在每一个单边频繁子图对应的映射边集按边频率降序排列，统计大于最小支持度的每个支持度数对应的所有的边并统计边节点出现次数等相关信息，进而统计得到网
络系统相关服务信息并根据相关频率降序存入文件；
12.(6)读取上一步所得数据文件并设置最小支持度计数min_count；对文件内容进行扫描到频繁项集m；并将m中各项按支持度递减排序，同时对原数据文件进行二次扫描生成相关树，并通过相关约束组合得到具体的频繁项集；
13.(7)对图集中各个子图进行计算筛选，获得相应的候选子图，而后对候选子图以及上一步所得的频繁项集进行比对，进一步筛选，完成网络系统关联服务发现。
14.进一步地，使用的coco sketch是一种概率数据结构，用于大规模流式数据的频率查询，同时其根据哈希值的范围确定所需的存储空在创建时就已经确定，与查询的错误率有关。每一行与一个哈希函数相关联，共有d个相互独立的哈希函数。当新事件到来时，利用d个哈希函数获得d个对应的列索引，并且在每一行的对应位置上计数加一。查询阶段需要统计某个事件i的计数，可以类似地获得d个对应的列索引，然后取对应位置中的最小值。其思想与计数布隆过滤器大致相当。但是，coco sketch的单元格数量是亚线性的，与其所需要达到的精度有关；相对而言计数布隆过滤器的大小与集合元素线性相关。
15.进一步地，在步骤(1)中为了统计相关网络数据流信息，构造五个不同的cocosketch，分别记录每个源ip发起访问总数，每个目的ip接受访问总数，每个目的ip端口接收访问总数，主机之间访问总数，每个源ip访问服务器应用的总数。
16.进一步地，在步骤(2)中对统计后的sketch信息文件进行进一步提取统计相关信息，并利用这些信息生成图序列。并进一步的采用k-means聚类方法，对所生成的图序列数据集进行聚类划分。
17.进一步地，对图序列数据集中的图进行深度优先遍历，得到图的所有单边频繁子图树，同时以一棵树为基树把该图的其它单边频繁子图树重叠到基树上。
18.进一步地，生成最初基树的图中边的五元素并以边在存储结构中的顺序作为边的唯一标识符保存到设定的存储结构映射边集中。
19.进一步地，在步骤(6)中，对文件内容进行二次扫描，生成相关树，而后倒序遍历项头表，判断与被约束子树端点相同且端点的支持度是否满足条件，满足条件，则通过组合方式得到新的频繁项集，反之，通过递归挖掘被约束子树获得新的频繁项集。
20.进一步地，将图集中的各个子图的邻接矩阵按照正规化算法进行正规化并转换成正准形，求出所对应的编码，并按编码值从小到大升序排列各图；按编码大小的升序序列将每个k阶邻接矩阵分别与后面的矩阵结合。每两个k阶的邻接矩阵，判断其二者的编码，若其编码的前k-2项相同，说明两矩阵包含同一个k-1阶子矩阵，可以生成候选k+1阶子图，若不相等，则放弃结合，继续判断其后面的矩阵；对k-l阶子图集进行剪枝，计算针1阶候选子图的支持度，并根据最小支持度进行判断生成k+l阶频繁图；重复以上步骤直到不再产生新的候选子图为止。
21.进一步地，通过比对候选子图每个节点与网络系统服务记录以及比对候选子图各边关系与新频繁项集，实现网络系统关联服务发现。
22.有益效果：本发明使用cocosketch数据结构来统计网络数据流信息，并提出了一种基于频繁子图挖掘的网络系统关联服务发现方法，将统计后的网络数据流信息转化为图序列数据集而后采用频繁子图挖掘相关技术，挖掘出网络系统中的关联服务相关信息。
附图说明
23.图1是基于频繁子图挖掘的网络系统关联服务发现方法的流程图。
具体实施方式
24.一种基于频繁子图挖掘的网络系统关联服务发现方法，包括以下步骤：
25.(1)为每个ip地址设置一个全局coco sketch(以下简称为sketch)，在接收到网络流数据后，解析得到源ip地址、目的ip地址等信息，将这些信息更新到每个ip对应的全局sketch中；
26.(2)访问统计后的sketch信息文件，按照一定的时间间隔提取(源ip，源端口，目的ip，目的端口)等生成图序列所需要的信息，并整合所有提取后的信息，生成包含访问被访问等关系的图序列数据集并通过k-means聚类方法，将图序列数据集进行进一步划分；
27.(3)根据上一步得到的包含网络访问相关信息的图序列数据集，对图集中的图进行深度优先遍历，生成图的该单边频繁子图的所有单边频繁子图树，并且以一棵树为基树把该图的其它单边频繁子图树都重叠到该树上；
28.(4)生成最初基树的图的边的五元素并以边在存储结构中的顺序作为边的唯一标识符保存到设定的存储结构映射边集中；然后将图序列数据分别与映射树进行重叠操作，通过映射树中边上记录的对应映射边集中边的编号，把重叠成功的边在映射边集中作标记，重叠不成功的边添加到映射边集中并作标记；
29.(5)在每一个单边频繁子图对应的映射边集按边频率降序排列，统计大于最小支持度的每个支持度数对应的所有的边并统计边节点出现次数等相关信息，进而统计得到网络系统相关服务信息并根据相关频率降序存入文件；
30.(6)读取上一步所得数据文件并设置最小支持度计数min_count；对文件内容进行扫描到频繁项集m；并将m中各项按支持度递减排序，同时对原数据文件进行二次扫描生成相关树，并通过相关约束组合得到具体的频繁项集；
31.(7)对图集中各个子图进行计算筛选，获得相应的候选子图，而后对候选子图以及上一步所得的频繁项集进行比对，进一步筛选，完成网络系统关联服务发现。
32.进一步地，使用的coco sketch是一种概率数据结构，用于大规模流式数据的频率查询，同时其根据哈希值的范围确定所需的存储空在创建时就已经确定，与查询的错误率有关。每一行与一个哈希函数相关联，共有d个相互独立的哈希函数。当新事件到来时，利用d个哈希函数获得d个对应的列索引，并且在每一行的对应位置上计数加一。查询阶段需要统计某个事件i的计数，可以类似地获得d个对应的列索引，然后取对应位置中的最小值。其思想与计数布隆过滤器大致相当。但是，coco sketch的单元格数量是亚线性的，与其所需要达到的精度有关；相对而言计数布隆过滤器的大小与集合元素线性相关。
33.进一步地，在步骤(1)中为了统计相关网络数据流信息，构造五个不同的cocosketch，分别记录每个源ip发起访问总数，每个目的ip接受访问总数，每个目的ip端口接收访问总数，主机之间访问总数，每个源ip访问服务器应用的总数。
34.进一步地，在步骤(2)中对统计后的sketch信息文件进行进一步提取统计相关信息，并利用这些信息生成图序列。并进一步的采用k-means聚类方法，对所生成的图序列数据集进行聚类划分。
35.进一步地，对图序列数据集中的图进行深度优先遍历，得到图的所有单边频繁子图树，同时以一棵树为基树把该图的其它单边频繁子图树重叠到基树上。
36.进一步地，生成最初基树的图中边的五元素并以边在存储结构中的顺序作为边的唯一标识符保存到设定的存储结构映射边集中。
37.进一步地，在步骤(6)中，对文件内容进行二次扫描，生成相关树，而后倒序遍历项头表，判断与被约束子树端点相同且端点的支持度是否满足条件，满足条件，则通过组合方式得到新的频繁项集，反之，通过递归挖掘被约束子树获得新的频繁项集。
38.进一步地，将图集中的各个子图的邻接矩阵按照正规化算法进行正规化并转换成正准形，求出所对应的编码，并按编码值从小到大升序排列各图；按编码大小的升序序列将每个k阶邻接矩阵分别与后面的矩阵结合。每两个k阶的邻接矩阵，判断其二者的编码，若其编码的前k-2项相同，说明两矩阵包含同一个k-1阶子矩阵，可以生成候选k+1阶子图，若不相等，则放弃结合，继续判断其后面的矩阵；对k-l阶子图集进行剪枝，计算针1阶候选子图的支持度，并根据最小支持度进行判断生成k+l阶频繁图；重复以上步骤直到不再产生新的候选子图为止。
39.进一步地，通过比对候选子图每个节点与网络系统服务记录以及比对候选子图各边关系与新频繁项集，实现网络系统关联服务发现。
40.具体算法：
41.算法1是根据本发明实施例的网络数据流信息统计和图序列生成算法。对每一条数据流，算法先分析其报头中的信息，根据其源ip地址等信息生成键值对并插入到相关sketch中。当接受完所有数据流之后，可以通过sketch查询每个ip地址的相关访问信息。而后通过这些信息按照一定时间进行提取生成图序列所需要的信息并进行相关处理。
42.[0043][0044]
算法2是根据本发明实施例的网络系统服务发现算法，通过利用上述算法处理得到的图序列数据集等信息，统计出图集中频繁出现的边的信息，并按照一定规则排序，进一步将这些边整合到一颗基树上并进行相应处理，得到网络系统服务信息。
[0045][0046]
算法3是根据本发明实施例的网络系统服务发现算法，通过读取上一步所得数据文件并设置最小支持度计数min_count，对文件内容进行扫描到频繁项集；并将频繁项集中各项按支持度递减排序，同时对原数据文件进行二次扫描生成相关树，并通过相关约束组合得到具体的频繁项集。对图集中各个子图进行计算筛选，获得相应的候选子图，而后对候选子图以及上一步所得的频繁项集进行比对，进一步筛选，完成网络系统关联服务发现。
[0047]
[0048][0049]
在本技术的一个实施例中，能够根据提供的网络数据流信息准确挖掘出该网络系统中的关联服务集以及关联服务相关的信息，最终结果以文件的形式存储下来。
[0050]
以上详细描述了本发明的优选实施方式，但是，本发明并不限于上述实施方式中的具体细节，在本发明的技术构思范围内，可以对本发明的技术方案进行多种等同变换，这些等同变换均属于本发明的保护范围。

技术特征：

1.一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，该方法包括以下步骤：（1）为每个ip地址设置一个全局coco sketch，简称为sketch，在接收到网络流数据后，解析得到源ip地址、目的ip地址等信息，将这些信息更新到每个ip对应的全局sketch中；（2）访问统计后的sketch信息文件，按照一定的时间间隔提取源ip、源端口、目的ip、目的端口生成图序列所需要的信息，并整合所有提取后的信息，生成包含访问被访问等关系的图序列数据集并通过k-means聚类方法，将图序列数据集进行进一步划分；（3）对给定的图集g，称图集g的只含有一条边的频繁子图为单边频繁子图；对图集g的所有单边频繁子图按出现的频度升序排列，得到单边频繁子图的集合e={e1，e2，
…ꢀ
,e
n
},我们称对应边e
i
的修正后的图的生成树为对应该单边频繁子图的单边频繁子图树；根据前述所得的包含网络访问相关信息的图序列数据集，对图集中的图进行深度优先遍历，生成图的单边频繁子图的所有单边频繁子图树，并且以一棵树为基树把该图的其它单边频繁子图树都重叠到该树上；（4）生成最初基树的图的边的五元素并以边在存储结构中的顺序作为边的唯一标识符保存到设定的存储结构映射边集中；然后将图序列数据分别与映射树进行重叠操作，通过映射树中边上记录的对应映射边集中边的编号，把重叠成功的边在映射边集中作标记，重叠不成功的边添加到映射边集中并作标记；（5）在每一个单边频繁子图对应的映射边集按边频率降序排列，统计大于最小支持度的每个支持度数对应的所有的边并统计边节点出现次数等相关信息，进而统计得到网络系统相关服务信息并根据相关频率降序存入文件；（6）读取上一步所得数据文件并设置最小支持度计数min_count；对文件内容进行扫描到频繁项集m；并将m中各项按支持度递减排序，同时对原数据文件进行二次扫描生成相关树，并通过相关约束组合得到具体的频繁项集；（7）对图集中各个子图进行计算筛选，获得相应的候选子图，而后对候选子图以及上一步所得的频繁项集进行比对，进一步筛选，完成网络系统关联服务发现。2.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，步骤（1）中为了统计相关网络数据流信息，构造不同的cocosketch，分别记录每个源ip发起访问总数，每个目的ip接受访问总数，每个目的ip端口接收访问总数，主机之间访问总数。3.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，在步骤（2）中对统计后的sketch信息文件进行进一步提取统计相关信息，并利用这些信息生成图序列，并进一步采用k-means聚类方法，对所生成的图序列数据集进行聚类划分。4.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，对图序列数据集中的图进行深度优先遍历，得到图的所有单边频繁子图树，同时以一棵树为基树把该图的其它单边频繁子图树重叠到基树上。5.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，生成最初基树的图中边的五元素并以边在存储结构中的顺序作为边的唯一标识符保存到设定的存储结构映射边集中。
6.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，在步骤（6）中，对文件内容进行二次扫描，生成相关树，包括根节点、项前缀子树、顶头表，其中项前缀子树中每个节点包4个域:项所对应的序号、节点计数值、指向父节点或最左子女节点的指针、指向同名节点链中下一个节点或者右兄弟节点的指针，而后倒序遍历项头表，判断是否与被约束子树端点相同且端点的支持度技术≥min_count，满足条件，则通过组合方式得到新的频繁项集，反之，通过递归挖掘被约束子树获得新的频繁项集。7.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，将图集中的各个子图的的邻接矩阵按照正规化算法进行正规化并转换成正准形，求出所对应的编码，并按编码值从小到大升序排列各图；按编码大小的升序序列将每个k阶邻接矩阵分别与后面的矩阵结合；每两个k阶的邻接矩阵，判断其二者的编码，若其编码的前k-2项相同，说明两矩阵包含同一个k-1阶子矩阵，可以生成候选k+1阶子图，若不相等，则放弃结合，继续判断其后面的矩阵；对k-l阶子图集进行剪枝，计算针1阶候选子图的支持度，并根据最小支持度进行判断生成k+l阶频繁图；重复以上步骤直到不再产生新的候选子图为止。8.根据权利要求1所述的一种基于频繁子图挖掘的网络系统关联服务发现方法，其特征在于，通过比对候选子图每个节点与网络系统服务记录以及比对候选子图各边关系与新频繁项集，实现网络系统关联服务发现。

技术总结

本发明公开了一种基于频繁子图挖掘的网络系统关联服务发现方法，使用Coco哈希和最小堆这两种数据结构来统计网络流数据中各个节点的访问信息，并使用相应的图序列生成算法来对各类数据进行处理生成频繁子图挖掘所需的图序列数据。在处理完所有网络流数据后，运行网络系统服务发现算法快速地挖掘出相关的网络系统服务。最终使用网络系统关联服务发现算法来挖掘出已统计的IP访问数据中的一些相互关联的数据，筛选出之间存在一定关系的IP地址组成的频繁项集，然后进一步处理准确统计出网络系统关联服务。本发明将统计后的网络数据流信息转化为图序列数据集而后采用频繁子图挖掘相关技术，挖掘出网络系统中的关联服务相关信息。信息。信息。