2022年 第59卷 第7期
2022, 59(7): 1409-1427.
DOI: 10.7544/issn1000-1239.20210142
摘要:
卷积神经网络(convolutional neural network, CNN)模型量化可有效压缩模型尺寸并提升CNN计算效率.然而,CNN模型量化算法的加速器设计,通常面临算法各异、代码模块复用性差、数据交换效率低、资源利用不充分等问题.对此,提出一种面向量化CNN的嵌入式FPGA加速框架FAQ-CNN,从计算、通信和存储3方面进行联合优化,FAQ-CNN以软件工具的形式支持快速部署量化CNN模型.首先,设计面向量化算法的组件,将量化算法自身的运算操作和数值映射过程进行分离;综合运用算子融合、双缓冲和流水线等优化技术,提升CNN推理任务内部的并行执行效率.然后,提出分级编码与位宽无关编码规则和并行解码方法,支持低位宽数据的高效批量传输和并行计算.最后,建立资源配置优化模型并转为整数非线性规划问题,在求解时采用启发式剪枝策略缩小设计空间规模.实验结果表明,FAQ-CNN能够高效灵活地实现各类量化CNN加速器.在激活值和权值为16 b时,FAQ-CNN的加速器计算性能是Caffeine的1.4倍;在激活值和权值为8 b时,FAQ-CNN可获得高达1.23TOPS的优越性能.
卷积神经网络(convolutional neural network, CNN)模型量化可有效压缩模型尺寸并提升CNN计算效率.然而,CNN模型量化算法的加速器设计,通常面临算法各异、代码模块复用性差、数据交换效率低、资源利用不充分等问题.对此,提出一种面向量化CNN的嵌入式FPGA加速框架FAQ-CNN,从计算、通信和存储3方面进行联合优化,FAQ-CNN以软件工具的形式支持快速部署量化CNN模型.首先,设计面向量化算法的组件,将量化算法自身的运算操作和数值映射过程进行分离;综合运用算子融合、双缓冲和流水线等优化技术,提升CNN推理任务内部的并行执行效率.然后,提出分级编码与位宽无关编码规则和并行解码方法,支持低位宽数据的高效批量传输和并行计算.最后,建立资源配置优化模型并转为整数非线性规划问题,在求解时采用启发式剪枝策略缩小设计空间规模.实验结果表明,FAQ-CNN能够高效灵活地实现各类量化CNN加速器.在激活值和权值为16 b时,FAQ-CNN的加速器计算性能是Caffeine的1.4倍;在激活值和权值为8 b时,FAQ-CNN可获得高达1.23TOPS的优越性能.
2022, 59(7): 1428-1438.
DOI: 10.7544/issn1000-1239.20210181
摘要:
现场可编程门阵列(field programmable gate array, FPGA)极易遭受由空间高能粒子辐射引发的故障,进而影响片上任务的正常执行.目前常采用三模冗余(triple modular redundance, TMR)进行容错设计,尽管可以取得较好的容错效果但存在资源开销大的问题.尤其当辐射水平较低时,对全部任务采用三模冗余方式执行能使上述资源开销大的问题更加严重.针对此,提出了一种基于动态自适应冗余的容错方法(fault tolerance based on dynamic self-adaptive redundancy, FTDSR).首先,利用片上块存储(block RAM, BRAM)对空间粒子辐射的高敏感性,设计改进了基于BRAM的辐射水平监测器,周期性监测空间环境的辐射水平;其次,以每个任务执行周期的松弛度时间和当前辐射水平为标准评估任务的可靠性等级,进而在不同辐射水平下以单个任务为粒度动态自适应地匹配冗余策略,保证片上任务成功执行,同时避免高资源开销.仿真实验表明,采用FTDSR的FPGA在不同辐射水平下具备高可靠性,与目前主流的FPGA冗余容错方法相比,在同一辐射水平条件下,片上任务完成量平均提高了57.2%.
现场可编程门阵列(field programmable gate array, FPGA)极易遭受由空间高能粒子辐射引发的故障,进而影响片上任务的正常执行.目前常采用三模冗余(triple modular redundance, TMR)进行容错设计,尽管可以取得较好的容错效果但存在资源开销大的问题.尤其当辐射水平较低时,对全部任务采用三模冗余方式执行能使上述资源开销大的问题更加严重.针对此,提出了一种基于动态自适应冗余的容错方法(fault tolerance based on dynamic self-adaptive redundancy, FTDSR).首先,利用片上块存储(block RAM, BRAM)对空间粒子辐射的高敏感性,设计改进了基于BRAM的辐射水平监测器,周期性监测空间环境的辐射水平;其次,以每个任务执行周期的松弛度时间和当前辐射水平为标准评估任务的可靠性等级,进而在不同辐射水平下以单个任务为粒度动态自适应地匹配冗余策略,保证片上任务成功执行,同时避免高资源开销.仿真实验表明,采用FTDSR的FPGA在不同辐射水平下具备高可靠性,与目前主流的FPGA冗余容错方法相比,在同一辐射水平条件下,片上任务完成量平均提高了57.2%.
2022, 59(7): 1439-1469.
DOI: 10.7544/issn1000-1239.20210119
摘要:
联邦学习(federated learning)将模型训练任务部署在移动边缘设备,参与者只需将训练后的本地模型发送到服务器参与全局聚合而无须发送原始数据,提高了数据隐私性.然而,解决效率问题是联邦学习落地的关键.影响效率的主要因素包括设备与服务器之间的通信消耗、模型收敛速率以及移动边缘网络中存在的安全与隐私风险.在充分调研后,首先将联邦学习的效率优化归纳为通信、训练与安全隐私保护3类.具体来说,从边缘协调与模型压缩的角度讨论分析了通信优化方案;从设备选择、资源协调、聚合控制与数据优化4个方面讨论分析了训练优化方案;从安全与隐私的角度讨论分析了联邦学习的保护机制.其次,通过对比相关技术的创新点与贡献,总结了现有方案的优点与不足,探讨了联邦学习所面临的新挑战.最后,基于边缘计算的思想提出了边缘化的联邦学习解决方案,在数据优化、自适应学习、激励机制和隐私保护等方面给出了创新理念与未来展望.
联邦学习(federated learning)将模型训练任务部署在移动边缘设备,参与者只需将训练后的本地模型发送到服务器参与全局聚合而无须发送原始数据,提高了数据隐私性.然而,解决效率问题是联邦学习落地的关键.影响效率的主要因素包括设备与服务器之间的通信消耗、模型收敛速率以及移动边缘网络中存在的安全与隐私风险.在充分调研后,首先将联邦学习的效率优化归纳为通信、训练与安全隐私保护3类.具体来说,从边缘协调与模型压缩的角度讨论分析了通信优化方案;从设备选择、资源协调、聚合控制与数据优化4个方面讨论分析了训练优化方案;从安全与隐私的角度讨论分析了联邦学习的保护机制.其次,通过对比相关技术的创新点与贡献,总结了现有方案的优点与不足,探讨了联邦学习所面临的新挑战.最后,基于边缘计算的思想提出了边缘化的联邦学习解决方案,在数据优化、自适应学习、激励机制和隐私保护等方面给出了创新理念与未来展望.
2022, 59(7): 1470-1485.
DOI: 10.7544/issn1000-1239.20210124
摘要:
图神经网络能够有效学习网络语义信息,在节点分类任务上取得了良好的效果.但仍面临挑战:如何充分利用异质网络丰富语义信息和全面结构信息使节点分类更精准.针对上述问题,提出了一种基于图卷积的异质网络节点分类框架(heterogeneous network node classification framework, HNNCF),包括异质网络约简和图卷积节点分类,解决异质网络节点分类问题.通过设计转换规则约简异质网络,将异质网络化简为语义化同质网络,利用节点间的关系表示保留异质网络多语义信息,降低网络结构建模复杂度;基于消息传递框架设计图卷积节点分类方法,在语义化同质网络上学习无1-sum约束的邻居权重等网络结构信息,深入挖掘关系语义特征,发现不同连接关系和邻居语义提取的差异性,生成节点的异质语义表示用于节点分类,识别节点类别标签.在3个公开的节点分类数据集上进行了实验,结果表明HNNCF能够充分利用异质网络多种语义信息,有效学习邻居节点权重等网络结构信息,提升节点分类效果.
图神经网络能够有效学习网络语义信息,在节点分类任务上取得了良好的效果.但仍面临挑战:如何充分利用异质网络丰富语义信息和全面结构信息使节点分类更精准.针对上述问题,提出了一种基于图卷积的异质网络节点分类框架(heterogeneous network node classification framework, HNNCF),包括异质网络约简和图卷积节点分类,解决异质网络节点分类问题.通过设计转换规则约简异质网络,将异质网络化简为语义化同质网络,利用节点间的关系表示保留异质网络多语义信息,降低网络结构建模复杂度;基于消息传递框架设计图卷积节点分类方法,在语义化同质网络上学习无1-sum约束的邻居权重等网络结构信息,深入挖掘关系语义特征,发现不同连接关系和邻居语义提取的差异性,生成节点的异质语义表示用于节点分类,识别节点类别标签.在3个公开的节点分类数据集上进行了实验,结果表明HNNCF能够充分利用异质网络多种语义信息,有效学习邻居节点权重等网络结构信息,提升节点分类效果.
2022, 59(7): 1486-1495.
DOI: 10.7544/issn1000-1239.20210376
摘要:
在小样本条件下,由于低数据问题,即标记数据较少且难以收集,采用传统的深度学习很难训练出一个好的分类器.最近的研究中,基于低维局部信息度量方法和标签传播网络(transductive propagation network, TPN)算法取得了较好的分类效果,并且局部信息可以很好地度量特征与特征之间的关系,但是低数据问题依然存在.为了解决低数据问题,提出基于多尺度的标签传播网络(multi-scale label propagation network, MSLPN)方法,其核心思想在于利用多尺度生成器生成多个尺度的图像特征,通过关系度量模块获得多个不同尺度特征下的样本相似性得分,并通过集成不同尺度的相似性得分获得分类结果,具体地,方法首先通过多尺度生成器生成不同尺度的图像特征,然后利用多尺度信息的相似性得分进行标签传播,最后通过多尺度标签传播结果计算获得分类结果.与TPN相比,在数据集miniImageNet上,5-way 1-shot和5-way 5-shot设置中的分类准确率分别提高了2.77%和4.02%;在数据集tieredImageNet上,5-way 1-shot和5-way 5-shot设置中分类准确率分别提高了1.16%和1.27%.实验结果表明,利用多尺度特征信息可有效提高分类准确率.
在小样本条件下,由于低数据问题,即标记数据较少且难以收集,采用传统的深度学习很难训练出一个好的分类器.最近的研究中,基于低维局部信息度量方法和标签传播网络(transductive propagation network, TPN)算法取得了较好的分类效果,并且局部信息可以很好地度量特征与特征之间的关系,但是低数据问题依然存在.为了解决低数据问题,提出基于多尺度的标签传播网络(multi-scale label propagation network, MSLPN)方法,其核心思想在于利用多尺度生成器生成多个尺度的图像特征,通过关系度量模块获得多个不同尺度特征下的样本相似性得分,并通过集成不同尺度的相似性得分获得分类结果,具体地,方法首先通过多尺度生成器生成不同尺度的图像特征,然后利用多尺度信息的相似性得分进行标签传播,最后通过多尺度标签传播结果计算获得分类结果.与TPN相比,在数据集miniImageNet上,5-way 1-shot和5-way 5-shot设置中的分类准确率分别提高了2.77%和4.02%;在数据集tieredImageNet上,5-way 1-shot和5-way 5-shot设置中分类准确率分别提高了1.16%和1.27%.实验结果表明,利用多尺度特征信息可有效提高分类准确率.
2022, 59(7): 1496-1508.
DOI: 10.7544/issn1000-1239.20210126
摘要:
随着获取多模态或多视图数据的日益容易,多视图聚类研究受到广泛关注.然而,很多方法直接从原始数据中学习邻接矩阵,忽视了数据中噪声的影响.此外,还有一些方法将各个视图同等对待,而实际上各视图在聚类过程中所发挥的作用是不同的.为解决上述问题,提出了一种基于Markov链的聚类算法,名为一致性引导的自适应加权多视图聚类(consensus guided auto-weighted multi-view clustering, CAMC).首先为每个视图构造转移概率矩阵;然后,以自适应加权的方式获得一致性转移概率矩阵,并对一致性转移概率矩阵的拉普拉斯矩阵进行了秩约束,确保拉普拉斯图中连通分量的数目正好等于簇的数目.此外,基于交替方向乘子法(alternating direction method of multipliers, ADMM)优化策略对问题进行求解.在1个人造数据集和7个真实数据集上的实验结果证明了该算法的有效性,其聚类性能优于现有的8种基准算法.
随着获取多模态或多视图数据的日益容易,多视图聚类研究受到广泛关注.然而,很多方法直接从原始数据中学习邻接矩阵,忽视了数据中噪声的影响.此外,还有一些方法将各个视图同等对待,而实际上各视图在聚类过程中所发挥的作用是不同的.为解决上述问题,提出了一种基于Markov链的聚类算法,名为一致性引导的自适应加权多视图聚类(consensus guided auto-weighted multi-view clustering, CAMC).首先为每个视图构造转移概率矩阵;然后,以自适应加权的方式获得一致性转移概率矩阵,并对一致性转移概率矩阵的拉普拉斯矩阵进行了秩约束,确保拉普拉斯图中连通分量的数目正好等于簇的数目.此外,基于交替方向乘子法(alternating direction method of multipliers, ADMM)优化策略对问题进行求解.在1个人造数据集和7个真实数据集上的实验结果证明了该算法的有效性,其聚类性能优于现有的8种基准算法.
2022, 59(7): 1509-1521.
DOI: 10.7544/issn1000-1239.20210016
摘要:
基于异构信息网络嵌入的推荐技术能够有效地捕捉网络中的结构信息,从而提升推荐性能.然而现有的基于异构信息网络嵌入的推荐技术不仅忽略了节点的属性信息与节点间多种类型的边关系,还忽略了节点不同的属性信息对推荐结果不同的影响.为了解决上述问题,提出一个自注意力机制的属性异构信息网络嵌入的商品推荐(attributed heterogeneous information network embedding with self-attention mechanism for product recommendation, AHNER)框架.该框架利用属性异构信息网络嵌入学习用户与商品统一、低维的嵌入表示,并在学习节点嵌入表示时,考虑到不同属性信息对推荐结果的影响不同和不同边关系反映用户对商品不同程度的偏好,引入自注意力机制挖掘节点属性信息与不同边类型所蕴含的潜在信息并学习属性嵌入表示.与此同时,为了克服传统点积方法作为匹配函数的局限性,该框架还利用深度神经网络学习更有效的匹配函数解决推荐问题.AHNER在3个公开数据集上进行大量的实验评估性能,实验结果表明AHNER的可行性与有效性.
基于异构信息网络嵌入的推荐技术能够有效地捕捉网络中的结构信息,从而提升推荐性能.然而现有的基于异构信息网络嵌入的推荐技术不仅忽略了节点的属性信息与节点间多种类型的边关系,还忽略了节点不同的属性信息对推荐结果不同的影响.为了解决上述问题,提出一个自注意力机制的属性异构信息网络嵌入的商品推荐(attributed heterogeneous information network embedding with self-attention mechanism for product recommendation, AHNER)框架.该框架利用属性异构信息网络嵌入学习用户与商品统一、低维的嵌入表示,并在学习节点嵌入表示时,考虑到不同属性信息对推荐结果的影响不同和不同边关系反映用户对商品不同程度的偏好,引入自注意力机制挖掘节点属性信息与不同边类型所蕴含的潜在信息并学习属性嵌入表示.与此同时,为了克服传统点积方法作为匹配函数的局限性,该框架还利用深度神经网络学习更有效的匹配函数解决推荐问题.AHNER在3个公开数据集上进行大量的实验评估性能,实验结果表明AHNER的可行性与有效性.
2022, 59(7): 1522-1532.
DOI: 10.7544/issn1000-1239.20200949
摘要:
自然场景下监控设备所拍摄的行人图片总是存在被各种障碍物遮挡的情况,因此遮挡是行人再辨识面临的一个很大的挑战.针对遮挡问题,提出了一种集成空间注意力和姿态估计(spatial attention and pose estimation, SAPE)的遮挡行人再辨识模型.为了同时兼顾全局特征和局部特征,实现特征的多细粒度表示,构建了多任务网络.通过空间注意力机制将感兴趣区域锚定到图像中未遮挡的空间语义信息,从全局结构模式中挖掘有助于再辨识的视觉知识;然后结合分块匹配的思想,将残差网络提取到的特征图水平均匀分割成若干块,通过局部特征的匹配增加辨识的细粒度;在此基础之上,改进姿态估计器去提取图像中行人的关键点信息,并与卷积神经网络抽取的特征图相融合,然后设置阈值去除掉遮挡区域,得到辨识性强的特征,以消除遮挡对再辨识结果的影响.在Occluded-DukeMTMC, Occluded-REID, Partial-REID这3个数据集上验证了SAPE模型的有效性,实验结果表明提出的针对遮挡的模型具有良好的效果.
自然场景下监控设备所拍摄的行人图片总是存在被各种障碍物遮挡的情况,因此遮挡是行人再辨识面临的一个很大的挑战.针对遮挡问题,提出了一种集成空间注意力和姿态估计(spatial attention and pose estimation, SAPE)的遮挡行人再辨识模型.为了同时兼顾全局特征和局部特征,实现特征的多细粒度表示,构建了多任务网络.通过空间注意力机制将感兴趣区域锚定到图像中未遮挡的空间语义信息,从全局结构模式中挖掘有助于再辨识的视觉知识;然后结合分块匹配的思想,将残差网络提取到的特征图水平均匀分割成若干块,通过局部特征的匹配增加辨识的细粒度;在此基础之上,改进姿态估计器去提取图像中行人的关键点信息,并与卷积神经网络抽取的特征图相融合,然后设置阈值去除掉遮挡区域,得到辨识性强的特征,以消除遮挡对再辨识结果的影响.在Occluded-DukeMTMC, Occluded-REID, Partial-REID这3个数据集上验证了SAPE模型的有效性,实验结果表明提出的针对遮挡的模型具有良好的效果.
2022, 59(7): 1533-1552.
DOI: 10.7544/issn1000-1239.20210373
摘要:
车辆共乘可有效提升运输资源利用率,降低出行成本,缓解交通拥堵并降低环境污染.针对动态车辆共乘问题构建了整数规划模型,并提出了一种基于离线匹配和在线匹配的双模式协作匹配算法.在离线匹配阶段,以共乘比率和绕行距离为标准对匹配价值进行评估,设计了基于带权路径搜索树的通用共乘比率生成算法对共乘参与者进行准确高效的预匹配.在在线匹配阶段,提出了基于首尾距离度的实时订单插入算法,并对离线匹配结果中的行驶路径进行修正.通过双模式协作,可有效兼顾算法的实时性和结果质量.基于真实数据的大量实验结果表明,该算法给出的匹配方案在总匹配价值和求解效率上均优于实验中的对比算法,其平均离线匹配率达93.71%、平均双模式协作匹配率达85.53%,增加运输资源利用率82.86%,减少车辆并发数84.86%.
车辆共乘可有效提升运输资源利用率,降低出行成本,缓解交通拥堵并降低环境污染.针对动态车辆共乘问题构建了整数规划模型,并提出了一种基于离线匹配和在线匹配的双模式协作匹配算法.在离线匹配阶段,以共乘比率和绕行距离为标准对匹配价值进行评估,设计了基于带权路径搜索树的通用共乘比率生成算法对共乘参与者进行准确高效的预匹配.在在线匹配阶段,提出了基于首尾距离度的实时订单插入算法,并对离线匹配结果中的行驶路径进行修正.通过双模式协作,可有效兼顾算法的实时性和结果质量.基于真实数据的大量实验结果表明,该算法给出的匹配方案在总匹配价值和求解效率上均优于实验中的对比算法,其平均离线匹配率达93.71%、平均双模式协作匹配率达85.53%,增加运输资源利用率82.86%,减少车辆并发数84.86%.
2022, 59(7): 1553-1568.
DOI: 10.7544/issn1000-1239.20210031
摘要:
随着Web信息的不断增长与发展,对用户稀疏行为的预测已成为目前推荐系统的研究热点.近年来,因子分解机(factorization machine, FM)的提出在一定程度上缓解了稀疏场景下预测精度不准确的问题.它的主要思想是通过2阶特征交互来获取特征间丰富的语义关系.随后,感知交互因子分解机(interaction-aware factorization machines, IFM)在FM的特征交互基础上引入类别交互的概念来扩展潜在的交互特性,通过把特征和类别分别进行交互后再融合来得到更准确的预测结果.在IFM的基础上,提出了一种特征-类别交互因子分解机(FIFM)模型.FIFM不仅保留了特征交互和类别交互机制,还设计了一种新的特征-类别交互机制(FIM)来进一步挖掘交互信息中的有效信息,并利用融合交互感知来预测不同稀疏场景下的用户行为模式.此外,还基于深度学习提出了一种实现FIFM的神经网络模型GFIM.相比于FIFM,GFIM的参数量和时间复杂度更高,但同时也能捕获更多高阶的非线性特征交互信息,能适合算力较高的应用场景.在4个真实数据集上的实验结果表明,FIFM和GFIM在RMSE指标上超越了当前最好的方法IFM.实验工作探究了多类稀疏场景下的预测结果,记录了时间和空间复杂度的消耗情况,并进行了分析讨论.
随着Web信息的不断增长与发展,对用户稀疏行为的预测已成为目前推荐系统的研究热点.近年来,因子分解机(factorization machine, FM)的提出在一定程度上缓解了稀疏场景下预测精度不准确的问题.它的主要思想是通过2阶特征交互来获取特征间丰富的语义关系.随后,感知交互因子分解机(interaction-aware factorization machines, IFM)在FM的特征交互基础上引入类别交互的概念来扩展潜在的交互特性,通过把特征和类别分别进行交互后再融合来得到更准确的预测结果.在IFM的基础上,提出了一种特征-类别交互因子分解机(FIFM)模型.FIFM不仅保留了特征交互和类别交互机制,还设计了一种新的特征-类别交互机制(FIM)来进一步挖掘交互信息中的有效信息,并利用融合交互感知来预测不同稀疏场景下的用户行为模式.此外,还基于深度学习提出了一种实现FIFM的神经网络模型GFIM.相比于FIFM,GFIM的参数量和时间复杂度更高,但同时也能捕获更多高阶的非线性特征交互信息,能适合算力较高的应用场景.在4个真实数据集上的实验结果表明,FIFM和GFIM在RMSE指标上超越了当前最好的方法IFM.实验工作探究了多类稀疏场景下的预测结果,记录了时间和空间复杂度的消耗情况,并进行了分析讨论.
2022, 59(7): 1569-1588.
DOI: 10.7544/issn1000-1239.20210391
摘要:
关键蛋白质作为蛋白质中的关键物质,不仅对研究细胞生长调控有着重要意义,也为更深层次的疾病研究奠定理论基础.目前,针对关键蛋白质的识别方法大多为应用基因表达信息和蛋白质相互作用网络,提出识别关键蛋白质的静态和动态网络方法,但这些方法未考虑基因表达调控的周期性规律,无法准确地刻画受基因周期调控的蛋白质网络.为此,在基因表达动态性的基础上引入了基因周期性表达的概念,提出了一种动态网络切分方法.该方法通过构建基因“活性”表达矩阵,利用切分后的“活性”表达矩阵作用于蛋白质相互作用网络,从而形成蛋白质周期子网络,最终综合各周期子网络来衡量蛋白质结点在网络中的重要性.实验结果表明,该方法在酵母、大肠杆菌和人类膀胱数据中可以有效地提高关键蛋白质预测率.
关键蛋白质作为蛋白质中的关键物质,不仅对研究细胞生长调控有着重要意义,也为更深层次的疾病研究奠定理论基础.目前,针对关键蛋白质的识别方法大多为应用基因表达信息和蛋白质相互作用网络,提出识别关键蛋白质的静态和动态网络方法,但这些方法未考虑基因表达调控的周期性规律,无法准确地刻画受基因周期调控的蛋白质网络.为此,在基因表达动态性的基础上引入了基因周期性表达的概念,提出了一种动态网络切分方法.该方法通过构建基因“活性”表达矩阵,利用切分后的“活性”表达矩阵作用于蛋白质相互作用网络,从而形成蛋白质周期子网络,最终综合各周期子网络来衡量蛋白质结点在网络中的重要性.实验结果表明,该方法在酵母、大肠杆菌和人类膀胱数据中可以有效地提高关键蛋白质预测率.
2022, 59(7): 1589-1609.
DOI: 10.7544/issn1000-1239.20210503
摘要:
异常检测对于网络管理与安全至关重要.国内外大量研究提出了一系列网络异常检测方法,其中大多数方法更关注数据包及其独立时序数据流的分析、检测与告警,这类方法仅仅利用了网络数据之间的时间相关性,无法检测新类型的网络异常,且难以定位以及剔除异常数据.为了解决上述问题,相关研究融合多时间序列数据流,提出基于低秩分解的网络异常检测方法.该方法充分利用网络数据之间的时间-空间相关性,无监督地定位异常数据所在位置,同时将异常数据剔除,从而还原网络正常数据.首先,根据其对正常数据与异常数据的不同类型约束,将基于低秩分解的异常检测方法分为4类,并介绍每一类方法的基本思想和优缺点;然后,探讨现有基于低秩分解的异常检测方法存在的挑战;最后,对未来可能的发展趋势进行了展望.
异常检测对于网络管理与安全至关重要.国内外大量研究提出了一系列网络异常检测方法,其中大多数方法更关注数据包及其独立时序数据流的分析、检测与告警,这类方法仅仅利用了网络数据之间的时间相关性,无法检测新类型的网络异常,且难以定位以及剔除异常数据.为了解决上述问题,相关研究融合多时间序列数据流,提出基于低秩分解的网络异常检测方法.该方法充分利用网络数据之间的时间-空间相关性,无监督地定位异常数据所在位置,同时将异常数据剔除,从而还原网络正常数据.首先,根据其对正常数据与异常数据的不同类型约束,将基于低秩分解的异常检测方法分为4类,并介绍每一类方法的基本思想和优缺点;然后,探讨现有基于低秩分解的异常检测方法存在的挑战;最后,对未来可能的发展趋势进行了展望.
2022, 59(7): 1610-1624.
DOI: 10.7544/issn1000-1239.20210397
摘要:
针对现有本地编码机制与本地扰动机制在收集空间数据时不具有保距性的问题,提出了基于局部敏感Hash结构(locality-sensitive hashing, LSH)的近似k-近邻(k nearest neighbor, kNN)查询算法PELSH与PULSH.这2种算法利用具有多Hash函数的多Hash表对所有用户位置数据进行索引,结合多Hash表结构响应近似kNN查询.每个用户结合收集者所共享的多Hash表副本,将自身位置数据以汉明空间嵌入方式编码成0/1串.借助LSH结构对0/1串进行Hash压缩,并利用GRR机制与按位扰动机制对压缩后的0/1串进行本地处理.收集者利用每个用户的报告值重构多Hash表索引结构,遍历多Hash表响应空间近似kNN查询.为了有效地利用LSH索引结构的特点,PELSH和PULSH算法结合隐私预算分割与用户分组策略来重构多Hash表结构,基于这2种策略设计了4种本地扰动算法PELSHB,PELSHG,PULSHB和PULSHG.PELSH和PULSH算法与现有的近似kNN查询算法在真实的大规模空间数据集上的实验结果表明,所设计的近似空间kNN查询效果优于同类算法.
针对现有本地编码机制与本地扰动机制在收集空间数据时不具有保距性的问题,提出了基于局部敏感Hash结构(locality-sensitive hashing, LSH)的近似k-近邻(k nearest neighbor, kNN)查询算法PELSH与PULSH.这2种算法利用具有多Hash函数的多Hash表对所有用户位置数据进行索引,结合多Hash表结构响应近似kNN查询.每个用户结合收集者所共享的多Hash表副本,将自身位置数据以汉明空间嵌入方式编码成0/1串.借助LSH结构对0/1串进行Hash压缩,并利用GRR机制与按位扰动机制对压缩后的0/1串进行本地处理.收集者利用每个用户的报告值重构多Hash表索引结构,遍历多Hash表响应空间近似kNN查询.为了有效地利用LSH索引结构的特点,PELSH和PULSH算法结合隐私预算分割与用户分组策略来重构多Hash表结构,基于这2种策略设计了4种本地扰动算法PELSHB,PELSHG,PULSHB和PULSHG.PELSH和PULSH算法与现有的近似kNN查询算法在真实的大规模空间数据集上的实验结果表明,所设计的近似空间kNN查询效果优于同类算法.
2022, 59(7): 1625-1635.
DOI: 10.7544/issn1000-1239.20210117
摘要:
基于聚类的k-匿名机制是共享数据脱敏的主要方法,它能有效防范针对隐私信息的背景攻击和链接攻击。然而,现有方案都是通过寻找最优k-等价集来平衡隐私性与可用性.从全局看,k-等价集并不一定是满足k-匿名的最优等价集,隐私机制的可用性最优化问题仍然未得到解决.针对上述问题,提出一种基于最优聚类的k-匿名隐私保护机制.通过建立数据距离与信息损失间的函数关系,将k-匿名机制的最优化问题转化为数据集的最优聚类问题;然后利用贪婪算法和二分机制,寻找满足k-匿名约束条件的最优聚类,从而实现k-匿名模型的可用性最优化;最后给出了问题求解的理论证明和实验分析.实验结果表明该机制能最大程度减少聚类匿名的信息损失,并且在运行时间方面是可行有效的.
基于聚类的k-匿名机制是共享数据脱敏的主要方法,它能有效防范针对隐私信息的背景攻击和链接攻击。然而,现有方案都是通过寻找最优k-等价集来平衡隐私性与可用性.从全局看,k-等价集并不一定是满足k-匿名的最优等价集,隐私机制的可用性最优化问题仍然未得到解决.针对上述问题,提出一种基于最优聚类的k-匿名隐私保护机制.通过建立数据距离与信息损失间的函数关系,将k-匿名机制的最优化问题转化为数据集的最优聚类问题;然后利用贪婪算法和二分机制,寻找满足k-匿名约束条件的最优聚类,从而实现k-匿名模型的可用性最优化;最后给出了问题求解的理论证明和实验分析.实验结果表明该机制能最大程度减少聚类匿名的信息损失,并且在运行时间方面是可行有效的.