一种低复杂度的面向未知分布的序列匹配方法及相关设备

本发明涉及数据安全，具体涉及一种低复杂度的面向未知分布的序列匹配方法及相关设备。

背景技术：

1、网络空间安全作为国家安全体系的重要组成部分，也作为数据开放共享的重要形式，包含用户统计特征的数据集被广泛公开发布，以支持统计分析、数据挖掘及智能决策等应用。通常这些公开数据集会通过删除或屏蔽可直接标识个人身份的字段来实现匿名化处理。然而，匿名化数据在辅助信息存在条件下仍可能面临被重新识别的风险，数据去匿名化问题成为数据安全领域亟需解决的关键基础问题。

2、序列匹配作为数据去匿名化的关键技术，通过量化跨域数据的关联风险，能够揭示现有匿名化技术的局限，进而推动匿名化标准和法规的规范和标准化。网络安全机构可以利用此类去匿名化的技术对网络攻击链进行溯源，复原跨域攻击链条，进而锁定恶意第三方，实现精准预警和主动防御。

3、已有的统计理论序列匹配方案中，使用穷举搜索的序列匹配算法被证明具备广义neyman-pearson标准下的最优性，但其时间复杂度随着观察序列总数增加而指数增加。而实际应用中受限于算力资源与时间等限制，高复杂度算法在大数据时代难以应用。为了降低算法的复杂度，通常需要以牺牲算法性能为代价。因此，如何探索性能与复杂度折衷的序列匹配方案，以同时保证良好的性能和较快的运行速度，是序列匹配实际应用中的一个关键科学问题。此外，已有方法通常假设分布已知，而实际场景中数据库中的数据分布通常未知，因此，面向未知分布的低复杂度序列匹配算法亟待研究。

技术实现思路

1、为解决上述技术问题，本发明提供一种低复杂度的面向未知分布的序列匹配方法及相关设备，旨在通过低复杂度评分函数和聚类思想，在面向未知分布的场景下实现低复杂度的序列匹配。

2、为了实现上述目的，本发明提供以下技术方案：

3、一方面，本发明实施例提供了一种低复杂度的面向未知分布的序列匹配方法，所述方法包括以下步骤：

4、获取第一数据库的多个第一序列、第二数据库的多个第二序列、预设样本长度以及训练好的评分函数，所述第一数据库包含第一数目个所述第一序列，所述第二数据库包含第二数目个所述第二序列，每个所述第一序列服从第一未知分布，每个所述第二序列服从第二未知分布，所述评分函数用于衡量两个序列的生成分布之间的距离；

5、基于所述预设样本长度计算所有所述第一序列与所有所述第二序列之间的评分函数值；

6、将最小的匹配对数目个评分函数值对应的序列对索引赋值给匹配集合并输出所述匹配集合。

7、可选地，所述评分函数包括广义jensen-shannon散度，所述基于所述预设样本长度计算所有所述第一序列与所有所述第二序列之间的评分函数值，包括：

8、将所述第一序列与所述第二序列分别作为第一离散序列和第二离散序列；

9、计算所述第一离散序列的经验分布与所述第二离散序列的经验分布之间的kl散度线性组合；

10、基于所述kl散度线性组合生成所述广义jensen-shannon散度作为所述评分函数值输出。

11、可选地，所述计算所述第一离散序列的经验分布与所述第二离散序列的经验分布之间的kl散度线性组合，包括：

12、计算所述第一离散序列的经验分布相对于加权平均分布的第一kl散度；

13、计算所述第二离散序列的经验分布相对于所述加权平均分布的第二kl散度；

14、将所述第一kl散度与所述第二kl散度进行加权求和，生成所述kl散度线性组合。

15、可选地，所述评分函数包括最大均值差异函数，所述基于所述预设样本长度计算所有所述第一序列与所有所述第二序列之间的评分函数值，包括：

16、将所述第一序列与所述第二序列分别作为第一连续序列和第二连续序列；

17、基于核函数计算所述第一连续序列与所述第二连续序列在再生核希尔伯特空间中的均值嵌入差异；

18、将所述均值嵌入差异的平方作为最大均值差异函数值输出。

19、可选地，所述基于核函数计算所述第一连续序列与所述第二连续序列在再生核希尔伯特空间中的均值嵌入差异，包括：

20、对所述第一连续序列中的每对样本点计算第一核函数值并求平均，生成第一均值嵌入；

21、对所述第二连续序列中的每对样本点计算第二核函数值并求平均，生成第二均值嵌入；

22、对所述第一连续序列与所述第二连续序列中的每对跨序列样本点计算第三核函数值并求平均，生成交叉均值嵌入；

23、基于所述第一均值嵌入、所述第二均值嵌入和所述交叉均值嵌入计算所述均值嵌入差异。

24、可选地，所述方法还包括：

25、基于所述预设样本长度计算所有所述第一序列与所有所述第二序列之间的评分函数值；

26、将小于或等于阈值的评分函数值对应的序列对索引赋值给候选集合；

27、判断所述候选集合是否为空集；

28、若是，则输出空集作为匹配结果；

29、若否，则将所述候选集合作为匹配结果输出。

30、可选地，所述将小于或等于阈值的评分函数值对应的序列对索引赋值给候选集合，包括：

31、将每个所述评分函数值与所述阈值进行比较；

32、当所述评分函数值小于或等于所述阈值时，将所述评分函数值对应的所述第一序列的索引与所述第二序列的索引组成序列对索引；

33、将所述序列对索引添加至所述候选集合。

34、可选地，所述将最小的匹配对数目个评分函数值对应的序列对索引赋值给匹配集合并输出所述匹配集合，包括：

35、对所有所述评分函数值按照从小到大的顺序进行排序，生成排序后的评分函数序列；

36、提取所述排序后的评分函数序列中的前匹配对数目个评分函数值作为目标评分函数值；

37、将每个所述目标评分函数值对应的所述第一序列的索引与所述第二序列的索引组成序列对索引；

38、将所有所述序列对索引收集到所述匹配集合中并输出。

39、另一方面，本发明实施例提供了一种低复杂度的面向未知分布的序列匹配系统，包括：

40、至少一个处理器；

41、至少一个存储器，用于存储至少一个程序；

42、当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现上述的方法。

43、另一方面，本发明实施例提供了一种计算机可读存储介质，其中存储有处理器可执行的程序，所述处理器可执行的程序在由处理器执行时用于执行上述的方法。

44、本发明实施例包括以下有益效果：

45、本发明引入低复杂度评分函数广义jensen-shannon散度和最大均值差异函数，分别适用于离散序列和连续序列，基于观测数据的经验分布设计，不依赖于生成分布，有效解决了实际场景中数据分布未知的问题。

46、本发明在匹配对数目已知和未知两种情况下均提出了对应的低复杂度序列匹配算法，采用聚类思想并利用低复杂度评分函数显著降低了计算复杂度，将已有最优算法的指数复杂度降低为多项式复杂度。

47、本发明通过仿真对比已有算法，证明所提低复杂度算法在离散数据和连续数据下都能够以更少的时间实现相同的性能，从而实现算法性能与计算复杂度的均衡，为海量数据场景下的序列匹配提供了高效可靠的技术方案。

48、本发明通过对比匹配对数目已知和未知两种情形，揭示了匹配对数目未知即先验知识缺失会导致算法性能的下降，为实际应用中算法参数的选择提供了理论指导。