2015年 第52卷 第3期
2015, 52(3): 553-560.
DOI: 10.7544/issn1000-1239.2015.20131546
摘要：
实现了一种通用高效的文本挖掘编程语言,包括其编译器、运行虚拟机和图形开发环境.其工作方式是用户通过编写该语言的代码以定制抽取目标和抽取手段,然后将用户代码编译成字节码并进行优化,再将其与输入文本语义结构做匹配.该语言具有如下特点：1)提供了一种描述文本挖掘的范围、目标和手段的形式化方法,从而能通过编写该语言的代码来在不同应用领域做声明式文本挖掘；2)运行虚拟机以信息抽取技术为核心,高效地实现了多种常用文本挖掘技术,并将其组成一个文本分析流水线；3)通过一系列编译优化技术使得大量匹配指令能够充分并发执行,从而解决了该语言在处理海量规则和海量数据上的执行效率问题.实用案例说明了TML语言的描述能力以及它的实际应用情况.
实现了一种通用高效的文本挖掘编程语言,包括其编译器、运行虚拟机和图形开发环境.其工作方式是用户通过编写该语言的代码以定制抽取目标和抽取手段,然后将用户代码编译成字节码并进行优化,再将其与输入文本语义结构做匹配.该语言具有如下特点：1)提供了一种描述文本挖掘的范围、目标和手段的形式化方法,从而能通过编写该语言的代码来在不同应用领域做声明式文本挖掘；2)运行虚拟机以信息抽取技术为核心,高效地实现了多种常用文本挖掘技术,并将其组成一个文本分析流水线；3)通过一系列编译优化技术使得大量匹配指令能够充分并发执行,从而解决了该语言在处理海量规则和海量数据上的执行效率问题.实用案例说明了TML语言的描述能力以及它的实际应用情况.
2015, 52(3): 561-568.
DOI: 10.7544/issn1000-1239.2015.20131444
摘要：
针对目前光滑孪生支持向量回归机(smooth twin support vector regression, STSVR)中采用的Sigmoid光滑函数逼近精度不高，从而导致算法泛化能力不够理想的问题，引入一种具有更强逼近能力的光滑(chen-harker-kanzow-smale, CHKS)函数，采用CHKS函数逼近孪生支持向量回归机的不可微项，并用Newton-Armijo算法求解相应的模型，提出了光滑CHKS孪生支持向量回归机(smooth CHKS twin support vector regression, SCTSVR).不仅从理论上证明了SCTSVR具有严格凸，能满足任意阶光滑和全局收敛的性能，而且在人工数据集和UCI数据集上的实验表明了SCTSVR比STSVR具有更好的回归性能.
针对目前光滑孪生支持向量回归机(smooth twin support vector regression, STSVR)中采用的Sigmoid光滑函数逼近精度不高，从而导致算法泛化能力不够理想的问题，引入一种具有更强逼近能力的光滑(chen-harker-kanzow-smale, CHKS)函数，采用CHKS函数逼近孪生支持向量回归机的不可微项，并用Newton-Armijo算法求解相应的模型，提出了光滑CHKS孪生支持向量回归机(smooth CHKS twin support vector regression, SCTSVR).不仅从理论上证明了SCTSVR具有严格凸，能满足任意阶光滑和全局收敛的性能，而且在人工数据集和UCI数据集上的实验表明了SCTSVR比STSVR具有更好的回归性能.
2015, 52(3): 569-578.
DOI: 10.7544/issn1000-1239.2015.20131436
摘要：
随着数据集规模的不断增大,提高频繁项集的挖掘效率成为数据挖掘领域的研究重点.频繁项集的增量更新挖掘算法因其可以利用已挖掘发现的信息提高对新数据集的挖掘效率,成为重要的研究方向.但现有频繁项集增量更新算法大多基于APRIORI算法框架,性能提高有限.最近出现的建立在FP-TREE等树形结构上的增量更新算法又往往存在树形结构调整困难、已发现频繁项集及树形结构保存效率较低等问题,算法性能有待进一步地提高.对此,通过分析增量挖掘过程中的关键信息,提出了一种基于磁盘存储1项集计数的增量FP_GROWTH算法(IU_FPGROWTH_1COUNTING).该算法无需保存临时树形结构及临时挖掘结果，可以在原数据集及支持度均发生变化时，减少FP_GROWTH算法对数据集的扫描，提高频繁项集的挖掘效率.在生成以及真实数据集上进行了验证实验以及性能分析,结果表明IU_FPGROWTH_1COUNTING是一种有效的频繁项集增量更新挖掘算法.
随着数据集规模的不断增大,提高频繁项集的挖掘效率成为数据挖掘领域的研究重点.频繁项集的增量更新挖掘算法因其可以利用已挖掘发现的信息提高对新数据集的挖掘效率,成为重要的研究方向.但现有频繁项集增量更新算法大多基于APRIORI算法框架,性能提高有限.最近出现的建立在FP-TREE等树形结构上的增量更新算法又往往存在树形结构调整困难、已发现频繁项集及树形结构保存效率较低等问题,算法性能有待进一步地提高.对此,通过分析增量挖掘过程中的关键信息,提出了一种基于磁盘存储1项集计数的增量FP_GROWTH算法(IU_FPGROWTH_1COUNTING).该算法无需保存临时树形结构及临时挖掘结果，可以在原数据集及支持度均发生变化时，减少FP_GROWTH算法对数据集的扫描，提高频繁项集的挖掘效率.在生成以及真实数据集上进行了验证实验以及性能分析,结果表明IU_FPGROWTH_1COUNTING是一种有效的频繁项集增量更新挖掘算法.
2015, 52(3): 579-587.
DOI: 10.7544/issn1000-1239.2015.20131270
摘要：
强化学习通过与环境交互的方式进行学习，在较大状态空间中其学习效率却很低.植入先验知识能够提高学习速度，然而不恰当的先验知识反而会误导学习过程，对学习性能不利.提出一种基于BP神经网络的双层启发式强化学习方法NNH-QL，改变了传统强化学习过程的盲目性.作为定性层，高层由BP神经网络构成，它不需要由外界提供背景知识，利用Shaping技术，将在线获取的动态知识对底层基于表格的Q学习过程进行趋势性启发.算法利用资格迹技术训练神经网络以提高学习效率.NNH-QL方法既发挥了标准Q学习的灵活性，又利用了神经网络的泛化性能，为解决较大状态空间下的强化学习问题提供了一个可行的方法.实验结果表明：该方法能够较好地提高强化学习的性能且具有明显的加速效果.
强化学习通过与环境交互的方式进行学习，在较大状态空间中其学习效率却很低.植入先验知识能够提高学习速度，然而不恰当的先验知识反而会误导学习过程，对学习性能不利.提出一种基于BP神经网络的双层启发式强化学习方法NNH-QL，改变了传统强化学习过程的盲目性.作为定性层，高层由BP神经网络构成，它不需要由外界提供背景知识，利用Shaping技术，将在线获取的动态知识对底层基于表格的Q学习过程进行趋势性启发.算法利用资格迹技术训练神经网络以提高学习效率.NNH-QL方法既发挥了标准Q学习的灵活性，又利用了神经网络的泛化性能，为解决较大状态空间下的强化学习问题提供了一个可行的方法.实验结果表明：该方法能够较好地提高强化学习的性能且具有明显的加速效果.
2015, 52(3): 588-595.
DOI: 10.7544/issn1000-1239.2015.20131478
摘要：
基于模型诊断是人工智能领域中具有挑战性的问题，包含了很多人工智能中的关键问题，其研究对整个人工智能领域起着重要推动作用.在基于模型诊断中，候选诊断结果通常由所有极小冲突集对应的所有极小碰集所描述，求出所有极小碰集是其核心问题之一.提出一种将极小碰集问题转换为约束满足问题的方法，该方法调用成熟的CSP求解器进行求解，扩展了约束可满足问题的应用领域.首次提出hard-冲突集和soft-冲突集的概念，并给出利用所提的方法分别求解具有一些特征的极小碰集：小于固定长度、不含特定元素及包含hard-冲突集和soft-冲突集.实验结果表明，提出的方法易于实现、扩展性强，对于特定类型极小碰集问题的求解效率较高.
基于模型诊断是人工智能领域中具有挑战性的问题，包含了很多人工智能中的关键问题，其研究对整个人工智能领域起着重要推动作用.在基于模型诊断中，候选诊断结果通常由所有极小冲突集对应的所有极小碰集所描述，求出所有极小碰集是其核心问题之一.提出一种将极小碰集问题转换为约束满足问题的方法，该方法调用成熟的CSP求解器进行求解，扩展了约束可满足问题的应用领域.首次提出hard-冲突集和soft-冲突集的概念，并给出利用所提的方法分别求解具有一些特征的极小碰集：小于固定长度、不含特定元素及包含hard-冲突集和soft-冲突集.实验结果表明，提出的方法易于实现、扩展性强，对于特定类型极小碰集问题的求解效率较高.
2015, 52(3): 596-605.
DOI: 10.7544/issn1000-1239.2015.20131481
摘要：
目标人体识别即非重叠多摄像系统中人的重现(person re-identification)问题,当前多数的目标人体识别都是通过提取人体表观特征，并利用特征的相似性对目标人体进行重识别,这些方法对于一些大部分表观区域相似而小部分区域不同的行人仍然无法给出准确的识别结果.考虑到目标人体识别中的行人几乎都处于站立姿势，同一行人的不同图像在垂直方向上的全局结构比不同行人间的更加相似.在基于稠密块匹配的基础上，提出了全局空间约束块匹配的识别方法.该方法不仅考虑2幅图像中局部块的匹配，还考虑各块在自身图像中垂直方向上的全局空间约束.为了减少背景对识别的负面影响，采用姿势评估的方法来提取大致的人体前景.在实验中，提出的方法在经过最具挑战的公用VIPeR数据库和CUHK02数据库测试后，该方法对人体识别率起到了显著的改善作用.
目标人体识别即非重叠多摄像系统中人的重现(person re-identification)问题,当前多数的目标人体识别都是通过提取人体表观特征，并利用特征的相似性对目标人体进行重识别,这些方法对于一些大部分表观区域相似而小部分区域不同的行人仍然无法给出准确的识别结果.考虑到目标人体识别中的行人几乎都处于站立姿势，同一行人的不同图像在垂直方向上的全局结构比不同行人间的更加相似.在基于稠密块匹配的基础上，提出了全局空间约束块匹配的识别方法.该方法不仅考虑2幅图像中局部块的匹配，还考虑各块在自身图像中垂直方向上的全局空间约束.为了减少背景对识别的负面影响，采用姿势评估的方法来提取大致的人体前景.在实验中，提出的方法在经过最具挑战的公用VIPeR数据库和CUHK02数据库测试后，该方法对人体识别率起到了显著的改善作用.
2015, 52(3): 606-613.
DOI: 10.7544/issn1000-1239.2015.20131147
摘要：
现实世界中存在着大量包含多种类型的对象和联系的异构信息网络，从中挖掘信息获取知识已成为当前的研究热点之一.基于图正则化的半监督学习在近年来得到了广泛的研究，然而，现有的半监督学习算法大都只能应用于同构网络.基于同构节点和异构节点的一致性假设，提出了任意结构的异构信息网络上的半监督学习的正则化分类函数，并得到分类函数的闭式解，以此预测未标记节点的类别.提出了异构信息网络上的半监督学习的迭代框架，标记节点的信息可以在邻近的节点上迭代传播，直至达到稳定状态，并证明了迭代算法将收敛于正则化分类函数的闭式解.DBLP数据集上的实验表明该方法优于经典的半监督学习算法.
现实世界中存在着大量包含多种类型的对象和联系的异构信息网络，从中挖掘信息获取知识已成为当前的研究热点之一.基于图正则化的半监督学习在近年来得到了广泛的研究，然而，现有的半监督学习算法大都只能应用于同构网络.基于同构节点和异构节点的一致性假设，提出了任意结构的异构信息网络上的半监督学习的正则化分类函数，并得到分类函数的闭式解，以此预测未标记节点的类别.提出了异构信息网络上的半监督学习的迭代框架，标记节点的信息可以在邻近的节点上迭代传播，直至达到稳定状态，并证明了迭代算法将收敛于正则化分类函数的闭式解.DBLP数据集上的实验表明该方法优于经典的半监督学习算法.
2015, 52(3): 614-628.
DOI: 10.7544/issn1000-1239.2015.20140491
摘要：
随着近2年慕课(massive open online course, MOOC)的兴起，教育大数据分析正成为一个新兴的研究方向.2013年秋，北京大学在Coursera上开设了6门慕课.通过分析挖掘约8万多人次参与这6门课的海量学习行为数据，力图展现慕课学习活动多个侧面的风貌.同时，首次针对中文慕课中学习行为的特点，将学习者分类，以更加深入地考察学习行为与学习效果之间的关系.在此基础上，通过选择学习者的若干典型行为特征，对他们最后的学习成果进行预测的工作也尚属首次.数据表明：基于学习行为的特征分析能有效地判别一个学习者能否成功完成学习任务获得通过证书，并能找出潜在的认真学习者，这为今后更加精准的慕课教学测评提供了一种依据.
随着近2年慕课(massive open online course, MOOC)的兴起，教育大数据分析正成为一个新兴的研究方向.2013年秋，北京大学在Coursera上开设了6门慕课.通过分析挖掘约8万多人次参与这6门课的海量学习行为数据，力图展现慕课学习活动多个侧面的风貌.同时，首次针对中文慕课中学习行为的特点，将学习者分类，以更加深入地考察学习行为与学习效果之间的关系.在此基础上，通过选择学习者的若干典型行为特征，对他们最后的学习成果进行预测的工作也尚属首次.数据表明：基于学习行为的特征分析能有效地判别一个学习者能否成功完成学习任务获得通过证书，并能找出潜在的认真学习者，这为今后更加精准的慕课教学测评提供了一种依据.
2015, 52(3): 629-638.
DOI: 10.7544/issn1000-1239.2015.20140156
摘要：
针对目标领域带标签数据偏少的问题，综合运用半监督学习、BootStrapping、数据分组、AdaBoost、集成学习等策略与技术，提出了一种基于分组提升集成的跨领域文本情感分类方法.该方法首先利用少量人工标注的目标领域数据，基于合成过抽样技术产生一定数量的虚拟数据.在此基础上，采用BootStrapping方法获得更多目标领域高可信度的带标签数据.在分类器的构建方面，首先将源领域的带标签数据等量分割，并分别与目标领域带标签数据组合，在每个组合数据块上运用AdaBoost方法提升地训练多个分类器，并将这些分类器线性地集成为一个分类器.在亚马逊购物网站4个领域的情感数据集上的实验表明，基于分组提升集成的跨领域文本情感分类方法一定程度上提高了跨领域文本情感分类的精度.
针对目标领域带标签数据偏少的问题，综合运用半监督学习、BootStrapping、数据分组、AdaBoost、集成学习等策略与技术，提出了一种基于分组提升集成的跨领域文本情感分类方法.该方法首先利用少量人工标注的目标领域数据，基于合成过抽样技术产生一定数量的虚拟数据.在此基础上，采用BootStrapping方法获得更多目标领域高可信度的带标签数据.在分类器的构建方面，首先将源领域的带标签数据等量分割，并分别与目标领域带标签数据组合，在每个组合数据块上运用AdaBoost方法提升地训练多个分类器，并将这些分类器线性地集成为一个分类器.在亚马逊购物网站4个领域的情感数据集上的实验表明，基于分组提升集成的跨领域文本情感分类方法一定程度上提高了跨领域文本情感分类的精度.
2015, 52(3): 639-648.
DOI: 10.7544/issn1000-1239.2015.20131473
摘要：
识别虚假评论有着重要的理论意义与现实价值.先前工作集中于启发式策略和传统的全监督学习算法.最近研究表明：人类无法通过先验知识有效识别虚假评论，手工标注的数据集必定存在一定数量的误例，因此简单使用传统的全监督学习算法识别虚假评论并不合理.容易被错误标注的样例称为间谍样例，如何确定这些样例的类别标签将直接影响分类器的性能.基于少量的真实评论和大量的未标注评论，提出一种创新的PU(positive and unlabeled)学习框架来识别虚假评论.首先，从无标注数据集中识别出少量可信度较高的负例.其次，通过整合LDA(latent Dirichlet allocation)和K-means，分别计算出多个代表性的正例和负例.接着，基于狄利克雷过程混合模型(Dirichlet process mixture model, DPMM)，对所有间谍样例进行聚类，混合种群性和个体性策略来确定间谍样例的类别标签.最后，多核学习算法被用来训练最终的分类器.数值实验证实了所提算法的有效性，超过当前的基准.
识别虚假评论有着重要的理论意义与现实价值.先前工作集中于启发式策略和传统的全监督学习算法.最近研究表明：人类无法通过先验知识有效识别虚假评论，手工标注的数据集必定存在一定数量的误例，因此简单使用传统的全监督学习算法识别虚假评论并不合理.容易被错误标注的样例称为间谍样例，如何确定这些样例的类别标签将直接影响分类器的性能.基于少量的真实评论和大量的未标注评论，提出一种创新的PU(positive and unlabeled)学习框架来识别虚假评论.首先，从无标注数据集中识别出少量可信度较高的负例.其次，通过整合LDA(latent Dirichlet allocation)和K-means，分别计算出多个代表性的正例和负例.接着，基于狄利克雷过程混合模型(Dirichlet process mixture model, DPMM)，对所有间谍样例进行聚类，混合种群性和个体性策略来确定间谍样例的类别标签.最后，多核学习算法被用来训练最终的分类器.数值实验证实了所提算法的有效性，超过当前的基准.
2015, 52(3): 649-660.
DOI: 10.7544/issn1000-1239.2015.20131424
摘要：
专利价值指的是在专利购买交易时的交换价值，它可以为专利的拥有者和购买者提供大量关于专利的珍贵信息，为专利的交易提供决策支持.目前的专利价值评估主要是基于训练或引用的方法.前者过于依赖于人工选择的参数，导致专利价值评估结果的可信度较低;后者往往只考虑了直接引用关联，而忽略了间接引用关联和新颖度对专利价值的影响.针对这些问题，提出一种基于潜在引用网络的专利价值评估方法，并设计了相应的算法来评估各个专利的价值.针对基本算法效率较低的问题，提出了专利价值评估改进算法，极大地提高了专利价值评估的效率.最后，由于新专利加入专利集合时各个专利的价值会发生变化，提出了专利价值评估动态更新算法，用于快速地更新各个专利的价值.实验表明，提出的方法是有效的.
专利价值指的是在专利购买交易时的交换价值，它可以为专利的拥有者和购买者提供大量关于专利的珍贵信息，为专利的交易提供决策支持.目前的专利价值评估主要是基于训练或引用的方法.前者过于依赖于人工选择的参数，导致专利价值评估结果的可信度较低;后者往往只考虑了直接引用关联，而忽略了间接引用关联和新颖度对专利价值的影响.针对这些问题，提出一种基于潜在引用网络的专利价值评估方法，并设计了相应的算法来评估各个专利的价值.针对基本算法效率较低的问题，提出了专利价值评估改进算法，极大地提高了专利价值评估的效率.最后，由于新专利加入专利集合时各个专利的价值会发生变化，提出了专利价值评估动态更新算法，用于快速地更新各个专利的价值.实验表明，提出的方法是有效的.
2015, 52(3): 661-670.
DOI: 10.7544/issn1000-1239.2015.20131320
摘要：
无线多跳网络的分布式工作特点和无线传播介质的特性导致其面临着严峻的性能和安全性挑战，而为弥补以往研究过分依赖仿真分析的不足，基于路由代数与统一路由模型，设计并实现了多种设备的试验测试平台(testbed for high-level analysis of wireless ad-hoc routing design，TH-award).该平台采用模块化架构设计了协议库、参数库和测试库，便于用户扩展无线路由协议，有效实现在同一平台上对协议性能与安全性的综合测试，保证了测试平台的可扩展性与兼容性；能以仿真、测试、试验等不同应用模式实现其测试功能，具有良好的适用性与开放性；平台具有分布式管理架构、路由测试引擎等相关设计，能有效实现配置管理、运行分析的自动化，具有很高的可管理性.基于该平台，实现了多种路由协议的快速设置与部署，基于多种场景测试验证了平台的有效性，该平台为研究各种无线路由协议的性能及安全性提供了一种重要手段.
无线多跳网络的分布式工作特点和无线传播介质的特性导致其面临着严峻的性能和安全性挑战，而为弥补以往研究过分依赖仿真分析的不足，基于路由代数与统一路由模型，设计并实现了多种设备的试验测试平台(testbed for high-level analysis of wireless ad-hoc routing design，TH-award).该平台采用模块化架构设计了协议库、参数库和测试库，便于用户扩展无线路由协议，有效实现在同一平台上对协议性能与安全性的综合测试，保证了测试平台的可扩展性与兼容性；能以仿真、测试、试验等不同应用模式实现其测试功能，具有良好的适用性与开放性；平台具有分布式管理架构、路由测试引擎等相关设计，能有效实现配置管理、运行分析的自动化，具有很高的可管理性.基于该平台，实现了多种路由协议的快速设置与部署，基于多种场景测试验证了平台的有效性，该平台为研究各种无线路由协议的性能及安全性提供了一种重要手段.
2015, 52(3): 671-680.
DOI: 10.7544/issn1000-1239.2015.20131376
摘要：
无线网络中通常存在多种身份认证协议可供选择，如何选择一个能够满足用户个性化需求的协议是个尚未解决的问题.从用户的角度出发，针对无线网络的特点，在综合考虑了用户最为关心的几个要素，如协议的安全性、能量消耗、认证时间以及用户偏好的基础上，提出了解决方案.将能量消耗定义为用户发送、接收消息能量消耗以及交互过程中密码操作所涉及的能量消耗之和.其中，密码操作包括Hash算法、RSA密钥交换、数字签名以及对称加解密算法.实验部分对EAP-PEAP，EAP-TLS，EAP-TTLS-MD5和EAP-TTLS-MSCHAPV2这4种最为常用的协议进行比较，结果表明不管用户如何设置权值，EAP-TTLS/MSCHAPV2和EAP-TTLS/MD5总是优于EAP-PEAP，EAP-TLS. 该方案通过考虑用户对身份认证协议的安全性以及性能方面的要求，按照用户的个性化需求进行了协议方案的选择.
无线网络中通常存在多种身份认证协议可供选择，如何选择一个能够满足用户个性化需求的协议是个尚未解决的问题.从用户的角度出发，针对无线网络的特点，在综合考虑了用户最为关心的几个要素，如协议的安全性、能量消耗、认证时间以及用户偏好的基础上，提出了解决方案.将能量消耗定义为用户发送、接收消息能量消耗以及交互过程中密码操作所涉及的能量消耗之和.其中，密码操作包括Hash算法、RSA密钥交换、数字签名以及对称加解密算法.实验部分对EAP-PEAP，EAP-TLS，EAP-TTLS-MD5和EAP-TTLS-MSCHAPV2这4种最为常用的协议进行比较，结果表明不管用户如何设置权值，EAP-TTLS/MSCHAPV2和EAP-TTLS/MD5总是优于EAP-PEAP，EAP-TLS. 该方案通过考虑用户对身份认证协议的安全性以及性能方面的要求，按照用户的个性化需求进行了协议方案的选择.
2015, 52(3): 681-690.
DOI: 10.7544/issn1000-1239.2015.20131255
摘要：
深度包检测(deep packet inspection, DPI)是网络入侵检测与防御系统(network intrusion dete-ction and prevention system, NIDPS)的核心.基于三态内容可寻址存储器(ternary content addressable memory, TCAM)的正则表达式匹配算法提高了数据包的处理速度，成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性，且能耗与存储空间成正比.由于DFA的存储空间开销比较大，且存储空间大小随着DFA步长数的增加而指数倍增，基于TCAM的DFA面临高能耗的问题，特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法(multi-stride parallel character-indexed DFA, PCIDFA)，对确定型有限自动机(deterministic finite automaton, DFA)构造并行字符索引，通过比特位图取交集，减少匹配时激活的TCAM块数，显著降低TCAM能耗.实验结果表明：与多步长DFA相比，多步长PCIDFA在TCAM能耗上减少了99.8%以上，在TCAM存储空间开销上减少了48.5%~65.3%，在吞吐量上提高了1.9~2.6倍.
深度包检测(deep packet inspection, DPI)是网络入侵检测与防御系统(network intrusion dete-ction and prevention system, NIDPS)的核心.基于三态内容可寻址存储器(ternary content addressable memory, TCAM)的正则表达式匹配算法提高了数据包的处理速度，成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性，且能耗与存储空间成正比.由于DFA的存储空间开销比较大，且存储空间大小随着DFA步长数的增加而指数倍增，基于TCAM的DFA面临高能耗的问题，特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法(multi-stride parallel character-indexed DFA, PCIDFA)，对确定型有限自动机(deterministic finite automaton, DFA)构造并行字符索引，通过比特位图取交集，减少匹配时激活的TCAM块数，显著降低TCAM能耗.实验结果表明：与多步长DFA相比，多步长PCIDFA在TCAM能耗上减少了99.8%以上，在TCAM存储空间开销上减少了48.5%~65.3%，在吞吐量上提高了1.9~2.6倍.
2015, 52(3): 691-701.
DOI: 10.7544/issn1000-1239.2015.20131413
摘要：
分层内积加密方案为内积加密体制提供了私钥分发功能，可有效降低系统根节点的任务量.针对现有分层内积加密方案密文长度过长的问题，首先提出一个完全安全且固定密文长度的内积加密方案，并以该方案为基础，构造了一个新的分层内积加密方案，利用对偶系统加密的新技术，在标准模型下证明了该分层内积加密方案是完全安全的.新方案密文长度达到了固定值，并且解密时只需要7个双线性对运算.与现有方案比，新方案计算效率高，且易于实现，占用通信带宽低，具有一定的优势.
分层内积加密方案为内积加密体制提供了私钥分发功能，可有效降低系统根节点的任务量.针对现有分层内积加密方案密文长度过长的问题，首先提出一个完全安全且固定密文长度的内积加密方案，并以该方案为基础，构造了一个新的分层内积加密方案，利用对偶系统加密的新技术，在标准模型下证明了该分层内积加密方案是完全安全的.新方案密文长度达到了固定值，并且解密时只需要7个双线性对运算.与现有方案比，新方案计算效率高，且易于实现，占用通信带宽低，具有一定的优势.
2015, 52(3): 702-717.
DOI: 10.7544/issn1000-1239.2015.20131382
摘要：
实时监测节点完整性状态是资源受限节点安全保护的有效手段.分析针对资源受限节点的主要篡改攻击模式及对散列时间带来的影响，提出基于散列时间有效性检验的纯软件完整性监测手段.基于对散列时间有效性可检验条件分析，提出采用验证值伪造惩罚系数描述散列模块抗篡改能力，设计一种融入程序状态的轻量级散列算法，通过简化算法结构与融入程序状态，增大验证值伪造难度,提高验证值伪造惩罚系数.设计支持消息认证的监测协议防止消息伪造，基于验证值比较与散列时间有效性统计,判定节点完整性状态.实验结果表明：该方案以微小的节点开销为代价，获得了更高的散列时间有效性检验可靠性，增强了对散列时间与消息传输时间波动干扰的容忍能力，提高了资源受限节点防篡改攻击性能.
实时监测节点完整性状态是资源受限节点安全保护的有效手段.分析针对资源受限节点的主要篡改攻击模式及对散列时间带来的影响，提出基于散列时间有效性检验的纯软件完整性监测手段.基于对散列时间有效性可检验条件分析，提出采用验证值伪造惩罚系数描述散列模块抗篡改能力，设计一种融入程序状态的轻量级散列算法，通过简化算法结构与融入程序状态，增大验证值伪造难度,提高验证值伪造惩罚系数.设计支持消息认证的监测协议防止消息伪造，基于验证值比较与散列时间有效性统计,判定节点完整性状态.实验结果表明：该方案以微小的节点开销为代价，获得了更高的散列时间有效性检验可靠性，增强了对散列时间与消息传输时间波动干扰的容忍能力，提高了资源受限节点防篡改攻击性能.
2015, 52(3): 718-728.
DOI: 10.7544/issn1000-1239.2015.20130601
摘要：
网络攻击连接具有行为的多变性和复杂性等特征，利用基于传统聚类的行为挖掘技术来构建异常入侵检测模型是不可行的.针对网络攻击行为的特点，提出了基于特征选择的模糊聚类异常入侵模型.首先通过层次聚类算法改善了FCM聚类算法结果对初始聚类中心的敏感性，再利用遗传算法的全局搜索能力克服了其在迭代时易陷入局部最优的缺点，并将它们结合构成一种AGFCM算法；然后采用信息增益算法对网络攻击连接数据集的特征属性进行排序，同时利用约登指数来删减数据集的特征属性以确定特征属性容量；最后利用低维特征属性集和改进的FCM聚类算法构建了异常入侵检测模型.实验结果表明该模型对绝大多数的网络攻击类型具有很好的检测能力，为解决异常入侵检测模型的误警率和检测率等问题提供了一种可行的解决途径.
网络攻击连接具有行为的多变性和复杂性等特征，利用基于传统聚类的行为挖掘技术来构建异常入侵检测模型是不可行的.针对网络攻击行为的特点，提出了基于特征选择的模糊聚类异常入侵模型.首先通过层次聚类算法改善了FCM聚类算法结果对初始聚类中心的敏感性，再利用遗传算法的全局搜索能力克服了其在迭代时易陷入局部最优的缺点，并将它们结合构成一种AGFCM算法；然后采用信息增益算法对网络攻击连接数据集的特征属性进行排序，同时利用约登指数来删减数据集的特征属性以确定特征属性容量；最后利用低维特征属性集和改进的FCM聚类算法构建了异常入侵检测模型.实验结果表明该模型对绝大多数的网络攻击类型具有很好的检测能力，为解决异常入侵检测模型的误警率和检测率等问题提供了一种可行的解决途径.
2015, 52(3): 729-737.
DOI: 10.7544/issn1000-1239.2015.20131308
摘要：
软件需求跟踪已被公认为影响软件项目成败的一个关键因素.针对大多数基于信息检索的需求跟踪方法都严重依赖于软件制品中的文本质量，提出了一种基于句法分析的动态需求跟踪方法.该方法能够从制品中抽取最有可能刻画自身特征的标引词，并减少制品中噪音对需求跟踪带来的不利影响.为了验证该方法的有效性，在多个来自不同项目且类型不同的软件制品上，比较了基于不同标引词集合的动态需求跟踪方法所建立的跟踪关系.实验结果表明，基于句法分析的动态需求跟踪方法能够有效地提高跟踪关系的准确性.
软件需求跟踪已被公认为影响软件项目成败的一个关键因素.针对大多数基于信息检索的需求跟踪方法都严重依赖于软件制品中的文本质量，提出了一种基于句法分析的动态需求跟踪方法.该方法能够从制品中抽取最有可能刻画自身特征的标引词，并减少制品中噪音对需求跟踪带来的不利影响.为了验证该方法的有效性，在多个来自不同项目且类型不同的软件制品上，比较了基于不同标引词集合的动态需求跟踪方法所建立的跟踪关系.实验结果表明，基于句法分析的动态需求跟踪方法能够有效地提高跟踪关系的准确性.
2015, 52(3): 738-748.
DOI: 10.7544/issn1000-1239.2015.20130683
摘要：
字符串相似性查询是众多应用的基础操作,如数据清洁、拼写校验、生物信息学和信息集成等.随着数据的爆炸性增长,大规模字符串数据日益普遍,现代的信息系统中也广泛使用字符串作为数据的表达形式.现有支持字符串相似性查询的方法大多是基于q-gram的内存倒排索引,在处理大规模字符串集合会消耗无法忍受的内存容量,甚至在数据量过大时造成内存容量不足而无法支持查询处理.现有的外存倒排索引Behm-Index在查询的过滤阶段只支持少数过滤器,不能有效地减少查询I/O代价.提出了LPA-Index：一种支持长度过滤器和位置过滤器的外存倒排索引,并通过选择查询时使用的倒排表来有效地降低查询I/O代价.实验结果表明,与现有性能最好的外存索引Behm-Index相比,LPA-Index能够大幅降低查询的I/O代价,获得了更短的查询响应时间.
字符串相似性查询是众多应用的基础操作,如数据清洁、拼写校验、生物信息学和信息集成等.随着数据的爆炸性增长,大规模字符串数据日益普遍,现代的信息系统中也广泛使用字符串作为数据的表达形式.现有支持字符串相似性查询的方法大多是基于q-gram的内存倒排索引,在处理大规模字符串集合会消耗无法忍受的内存容量,甚至在数据量过大时造成内存容量不足而无法支持查询处理.现有的外存倒排索引Behm-Index在查询的过滤阶段只支持少数过滤器,不能有效地减少查询I/O代价.提出了LPA-Index：一种支持长度过滤器和位置过滤器的外存倒排索引,并通过选择查询时使用的倒排表来有效地降低查询I/O代价.实验结果表明,与现有性能最好的外存索引Behm-Index相比,LPA-Index能够大幅降低查询的I/O代价,获得了更短的查询响应时间.
2015, 52(3): 749-759.
DOI: 10.7544/issn1000-1239.2015.20131390
摘要：
数据集中的强邻近对查询在空间数据挖掘、大数据处理、空间数据库、地理信息系统、数据的相似分析和推理等方面具有重要的作用. 已有的数据查询方法无法有效处理动态数据集中的强邻近对查询问题，针对动态数据集中的强邻近对查询的特点和复杂性，基于Voronoi图和R树空间索引结构提出了处理初始数据环境下的双数据集中的强邻近对查询算法VR_SNP. 针对分布区域不规则且数据点分布密度差异较大的情况利用Voronoi图进行计算查询，反之，则利用R树进行查询. 通过对初始强邻近对集和候选邻近对集进行二次判断计算，筛选出有效结果，给出了数据集动态增加和动态减少环境下的强邻近对查询算法VR_SNP_DA和算法VR_SNP_DE.进一步提出了移动点位置变化情况下的强邻近对查询算法VR_SNP_DL.理论研究和实验比较表明在数据集的数据量、新增点集和删除点集的规模较大、移动点的位置变化次数较多等情况下，所提出的算法具有较为明显的查询优势.
数据集中的强邻近对查询在空间数据挖掘、大数据处理、空间数据库、地理信息系统、数据的相似分析和推理等方面具有重要的作用. 已有的数据查询方法无法有效处理动态数据集中的强邻近对查询问题，针对动态数据集中的强邻近对查询的特点和复杂性，基于Voronoi图和R树空间索引结构提出了处理初始数据环境下的双数据集中的强邻近对查询算法VR_SNP. 针对分布区域不规则且数据点分布密度差异较大的情况利用Voronoi图进行计算查询，反之，则利用R树进行查询. 通过对初始强邻近对集和候选邻近对集进行二次判断计算，筛选出有效结果，给出了数据集动态增加和动态减少环境下的强邻近对查询算法VR_SNP_DA和算法VR_SNP_DE.进一步提出了移动点位置变化情况下的强邻近对查询算法VR_SNP_DL.理论研究和实验比较表明在数据集的数据量、新增点集和删除点集的规模较大、移动点的位置变化次数较多等情况下，所提出的算法具有较为明显的查询优势.
2015, 52(3): 760-768.
DOI: 10.7544/issn1000-1239.2015.20130677
摘要：
实时系统中任务的超时完成可能导致灾难性后果，因此要求系统具备容错处理能力，以保证系统出错后的实时性及可靠性.主/副版本模型是提高实时系统容错能力的有效技术.传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错，为副版本预留的处理器时间在系统运行过程中需动态调整，增加了系统的容错调度开销.提出一种基于res-backwards-RM预分配子算法的容错实时调度算法BCE\+*，通过限制预分配过程中高优先级任务的抢占条件，在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整，降低系统的容错调度开销.仿真实验验证了BCE\+*算法的可行性及有效性，且在系统出错概率及主版本负载较低的环境下，BCE\+*算法对系统容错调度开销的优化效果更显著.
实时系统中任务的超时完成可能导致灾难性后果，因此要求系统具备容错处理能力，以保证系统出错后的实时性及可靠性.主/副版本模型是提高实时系统容错能力的有效技术.传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错，为副版本预留的处理器时间在系统运行过程中需动态调整，增加了系统的容错调度开销.提出一种基于res-backwards-RM预分配子算法的容错实时调度算法BCE\+*，通过限制预分配过程中高优先级任务的抢占条件，在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整，降低系统的容错调度开销.仿真实验验证了BCE\+*算法的可行性及有效性，且在系统出错概率及主版本负载较低的环境下，BCE\+*算法对系统容错调度开销的优化效果更显著.
2015, 52(3): 769-776.
DOI: 10.7544/issn1000-1239.2015.20131508
摘要：
带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集，使得任意2个子集中顶点的权值之和的差异达到极小，并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域，它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下，采用最大化同一子集内部边权之和的策略来构造每一个顶点子集；构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中，直到子集S的顶点权值之和满足要求.此外，采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明，当k分别取值为2，4，8时所提算法分别在86%，81%，68%的基准图上求得的平均解优于当前最新算法求得的平均解；解的最大改进幅度可达60%以上.
带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集，使得任意2个子集中顶点的权值之和的差异达到极小，并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域，它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下，采用最大化同一子集内部边权之和的策略来构造每一个顶点子集；构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中，直到子集S的顶点权值之和满足要求.此外，采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明，当k分别取值为2，4，8时所提算法分别在86%，81%，68%的基准图上求得的平均解优于当前最新算法求得的平均解；解的最大改进幅度可达60%以上.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
