Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2015年 第52卷 第7期    出版日期:2015-07-01
人工智能
混合概率典型相关性分析
张博,郝杰, 马刚,岳金朋,张建华,史忠植
2015, 52(7):  1463-1476.  doi:10.7544/issn1000-1239.2015.20140236
摘要 ( 1236 )   HTML ( 4)   PDF (4303KB) ( 985 )  
相关文章 | 计量指标
典型相关性分析(canonical correlation analysis, CCA)是一种用来分析2组随机变量之间相关性的统计分析工具,但作为一种线性数学模型,CCA不足以揭示真实世界中大量存在的非线性相关现象.采用局部化的方法,在概率典型相关性分析(probabilistic CCA, PCCA)的基础上,使用概率混合模型框架,提出了混合概率典型相关性分析模型(mixture of probabilistic CCA, MixPCCA)以及估计模型参数的2阶段期望最大化(expectation maximization, EM)算法,并给出了使用聚类融合确定局部线性模型数量的方法和MixPCCA模型应用于模式识别的理论框架.在手写体数据集USPS和MNIST上的实验证明,MixPCCA模型通过混合多个局部线性PCCA模型不仅提供了一种捕捉复杂的全局非线性相关性的解决方案,而且还具备检测只在局部区域才存在的相关性的能力.
二阶Newton法训练径向基函数神经网络的算法研究
蔡珣,陈智,Kanishka Tyagi, 于宽,李子强,朱波
2015, 52(7):  1477-1486.  doi:10.7544/issn1000-1239.2015.20140373
摘要 ( 716 )   HTML ( 0)   PDF (2692KB) ( 779 )  
相关文章 | 计量指标
提出了一种混合加权距离测量(weighted distance measure,weighted DM)参数的构建和训练RBF(radial basis function)神经网络的两步批处理算法.该算法在引进了DM系数参数的基础上,采用Newton法分别对径向基函数的覆盖参数、均值向量参数、加权距离测度系数以及输出权值进行了优化,并在优化过程中利用OLS(orthogonal least squares)法来求解Newton法的方程组. 通过实验数据,不仅分析了Newton法优化的各个参数向量对RBF网络训练的影响,而且比较了混合优化加权DM与RLS-RBF(recursive least square RBF neural network)网络训练算法的收敛性和计算成本. 所得到的结论表明整合了优化参数的加权DM-RBF网络训练算法收敛速度比RLS-RBF网络训练算法更快,而且具有比LM-RBF(Levenberg-Marquardt RBF)训练算法更小的计算成本,从而说明OLS求解的Newton法对优化RBF网络参数具有重要应用价值.
针对动态非平衡数据集鲁棒的在线极端学习机
张晶,冯林
2015, 52(7):  1487-1498.  doi:10.7544/issn1000-1239.2015.20140182
摘要 ( 647 )   HTML ( 1)   PDF (5280KB) ( 738 )  
相关文章 | 计量指标
动态数据存在数据量动态改变,数据类别分布非平衡、不稳定等问题,这些问题成为分类的难点.针对该问题,通过对在线极端学习机模型进行拓展,提出鲁棒的权值在线极端学习机算法.为解决动态数据非平衡性,该算法借助代价敏感学习理论生成局部动态权值矩阵,从而优化分类模型产生的经验风险.同时,算法进一步考虑动态数据由于时序性质改变造成的数据分布变化,而引入遗忘因子增强分类器对数据分布变更的敏感性.算法在不同数据分布的24个非平衡动态数据集上测试,取得了较好的效果.
基于朴素贝叶斯模型的单词语义相似度度量
王俊华,左万利,闫昭
2015, 52(7):  1499-1509.  doi:10.7544/issn1000-1239.2015.20140383
摘要 ( 1096 )   HTML ( 4)   PDF (2262KB) ( 747 )  
相关文章 | 计量指标
单词语义相似度度量是自然语言处理领域的经典和热点问题.通过结合朴素贝叶斯模型和知识库,提出一个新颖的度量单词语义相似度度量途径.首先借助通用本体WordNet获取属性变量,然后使用统计和分段线性插值生成条件概率分布列,继而通过贝叶斯推理实现信息融合获得后验概率,并在此基础上量化单词语义相似度.主要贡献是定义了单词对距离和深度,并将朴素贝叶斯模型用于单词语义相似度度量.在基准数据集R&G(65)上,对比算法评判结果与人类评判结果的相关度,采用5折交叉验证对算法进行分析,样本Pearson相关度达到0.912,比当前最优方法高出0.4%,比经典算法高出7%~13%;Spearman相关度达到0.873,比经典算法高出10%~20%;且算法的运行效率和经典算法相当.实验结果显示将朴素贝叶斯模型和知识库相结合解决单词语义相似度问题是合理有效的.
基于局部语义聚类的语义重叠社区发现算法
辛宇,杨静,汤楚蘅, 葛斯乔
2015, 52(7):  1510-1521.  doi:10.7544/issn1000-1239.2015.20140308
摘要 ( 1179 )   HTML ( 2)   PDF (6042KB) ( 1516 )  
相关文章 | 计量指标
语义社会网络是一种包含信息节点及社会关系构成的新型复杂网络,因此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题.针对这一问题,提出基于局部语义聚类的语义社会网络重叠社区发现算法,该算法:1)以LDA(latent Dirichlet allocation)模型为语义信息模型,利用Gibbs取样法建立节点语义信息到语义空间的量化映射;2)以节点间语义坐标的相对熵作为节点语义相似度的度量,建立节点相似度矩阵;3)根据社会网络的局部小世界特性,提出语义社会网络的局部社区结构S-fitness模型,并根据S-fitness模型建立了局部语义聚类算法(local semantic clusterm, LSC);4)提出可度量语义社区发现结果的语义模块度模型,并通过实验分析,验证了算法及语义模块度模型的有效性及可行性.
系统结构
一种面向大规模数据密集计算的缓存方法
周恩强,张伟,卢宇彤,侯红军,董勇
2015, 52(7):  1522-1530.  doi:10.7544/issn1000-1239.2015.20148073
摘要 ( 726 )   HTML ( 0)   PDF (2648KB) ( 701 )  
相关文章 | 计量指标
随着高性能计算机逐步应用在大规模数据处理领域,存储系统将成为制约数据处理效率的主要瓶颈.在分析了影响数据密集型计算I/O性能若干关键因素的基础上,提出使用计算结点本地存储构建协作式非易失缓存、以分布式存储架构加速集中式存储架构的方法.该方法基于应用层协同使用分布化的本地存储资源,使用非易失存储介质构成大缓存空间,存放大规模数据分析的中间过程结果,以此实现高缓存命中率,并利用并发度约束控制等手段避免I/O竞争,充分利用本地存储的特定性能优势保证缓存加速效果,从而有效地提高了大规模数据处理过程的I/O效率.基于多平台多种I/O模式的测试结果证实了该方法的有效性,聚合I/O带宽具有高扩展性,典型数据密集应用的整体性能最大可提升6倍.
基于并发跳表的云数据处理双层索引架构研究
周维,路劲,周可人,王世普,姚绍文
2015, 52(7):  1531-1545.  doi:10.7544/issn1000-1239.2015.20140358
摘要 ( 778 )   HTML ( 0)   PDF (5223KB) ( 590 )  
相关文章 | 计量指标
云数据处理在云计算基础设施中占有极其关键的地位.然而,当前的云存储系统绝大部分都采用基于分布式Hash的健-值对模式来组织数据,在范围查询方面支持不理想、且动态实时性差,有必要构建云环境下辅助动态索引.通过总结、分析云环境中辅助双层索引机制,提出一种基于并发跳表的云数据处理双层索引架构.该架构采用两层体系结构,突破单台机器内存和硬盘的限制,从而扩展系统整体的索引范围.通过动态分裂算法解决局部服务器中的热点问题,保证索引结构整体的负载均衡.通过并发跳表来提高全局索引的承载性能,改善了全局索引的并发性,提高整体索引的吞吐率.实验结果表明,基于并发跳表的云数据处理双层索引架构能够有效支持单键查询和范围查询,具有较强的可扩展性和并发性,是一种高效的云存储辅助索引.
基于对象的OpenXML复合文件去重方法研究
阎芳,李元章,张全新,谭毓安
2015, 52(7):  1546-1557.  doi:10.7544/issn1000-1239.2015.20140093
摘要 ( 724 )   HTML ( 0)   PDF (4054KB) ( 545 )  
相关文章 | 计量指标
现有的重复数据删除技术大部分是基于变长分块(content defined chunking, CDC)算法的,不考虑不同文件类型的内容特征.这种方法以一种随机的方式确定分块边界并应用于所有文件类型,已经证明其非常适合于文本和简单内容,而不适合非结构化数据构成的复合文件.分析了OpenXML标准的复合文件属性,给出了对象提取的基本方法,并提出基于对象分布和对象结构的去重粒度确定算法.目的是对于非结构化数据构成的复合文件,有效地检测不同文件中和同一文件不同位置的相同对象,在文件物理布局改变时也能够有效去重.通过对典型的非结构化数据集合的模拟实验表明,在综合情况下,对象重复数据删除比CDC方法提高了10%左右的非结构化数据的去重率.
面向新型非易失存储器的文件级磨损均衡机制
蔡涛,张永春,牛德姣,倪晓蓉,梁东莺
2015, 52(7):  1558-1566.  doi:10.7544/issn1000-1239.2015.20140019
摘要 ( 692 )   HTML ( 0)   PDF (2110KB) ( 488 )  
相关文章 | 计量指标
自旋转移力矩磁存储器(spin transfer torque random access memory, STTRAM)和磁阻式随机存储器(magnetic random access memory, MRAM)等新型存储器具有接近于DRAM的访问速度,是构建高性能外存系统和提高计算机系统性能的重要手段,但有限的写次数是其重要局限之一.设计了文件系统级磨损均衡机制,使用Hash函数分散文件在外存中的存储,避免在创建和删除文件时反复分配某些存储块,通过分配文件空间时选择写次数较低的存储块,避免写操作的集中;使用主动迁移策略,在外存系统I/O负载较低时主动迁移写次数较高的数据块,减少磨损均衡机制对I/O性能的影响.最后在开源的基于对象存储设备Open-osd上实现了面向新型存储器文件系统级磨损均衡机制的原型,使用存储系统通用测试工具filebench和postmark的多个通用数据集进行了测试与分析,验证了基于新型存储器的文件系统级磨损均衡机制能稳定地将存储块写次数差减少到原来的1/20左右,同时最高仅损失了6%的I/O性能和增加了0.5%的额外写操作,具有高效和稳定的特性.
Asyn-SimRank:一种可异步执行的大规模SimRank算法
王春磊,张岩峰,鲍玉斌,赵长宽,于戈,高立新
2015, 52(7):  1567-1579.  doi:10.7544/issn1000-1239.2015.20140313
摘要 ( 1193 )   HTML ( 0)   PDF (2639KB) ( 538 )  
相关文章 | 计量指标
SimRank算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中.近年来,随着大数据技术的发展,SimRank算法处理的数据不断增大,人们利用MapReduce等分布式计算模型设计实现分布式的大规模SimRank算法来适应大数据处理的需求.但是,由于SimRank算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank算法不能在分布式环境下高效地实现.1)提出Asyn-SimRank算法,该算法采用迭代-累积的方式完成迭代计算,异步执行SimRank的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2)提出关键点优先调度计算,提升了Asyn-SimRank算法的全局收敛速度;3)证明了Asyn-SimRank算法的正确性和收敛性以及关键点优先调度计算的有效性;4)支持异步迭代的分布式框架Maiter上实现了Asyn-SimRank算法.实验结果显示,相比较于Hadoop,Spark上实现的SimRank算法和Delta-SimRank算法,Asyn-SimRank算法大大提升了算法的计算效率,加速了算法收敛.
综述
软件模型检测中的抽象模型研究综述
魏欧,石玉峰,徐丙凤,黄志球,陈哲
2015, 52(7):  1580-1603.  doi:10.7544/issn1000-1239.2015.20140413
摘要 ( 1304 )   HTML ( 4)   PDF (3645KB) ( 1021 )  
相关文章 | 计量指标
抽象是解决模型检测中状态爆炸问题的一个基本方法.对近年来软件模型检测研究中所提出的一系列抽象模型进行综述.首先以抽象解释为理论框架阐述了抽象软件模型检测的各组成部分.然后根据模型的结构和功能特征,将抽象模型分为3类:1)传统的用于支持自上逼近或者自下逼近的布尔Kripke结构;2)分别对应于3值和4值Kripke结构的Kripke模态迁移系统(Kripke modal transition systems, KMTS)和混合迁移系统(mixed transition system, MixTS),可同时支持自上逼近和自下逼近的抽象;3)具有超迁移关系的广义Kripke模态迁移系统(generalized Kripke modal transition system, GKMTS)和超迁移系统(hyper transition system, HTS),可提供更精确的抽象模型检测;重点分析这些模型的提出原因、相应的逼近关系、最优模型及其局限性以及抽象模型完备性的研究结果.最后,分析了目前关于抽象模型的理论和应用研究中存在的问题,给出进一步研究的方向.
软件技术
分布式软件系统交互行为建模、验证与测试
张琛,段振华, 田聪,鱼滨
2015, 52(7):  1604-1619.  doi:10.7544/issn1000-1239.2015.20140244
摘要 ( 795 )   HTML ( 0)   PDF (3760KB) ( 592 )  
相关文章 | 计量指标
为了确保分析与设计阶段分布式软件系统中模块之间交互行为的正确性,提出了一种分布式软件系统模块交互的抽象方法,分别通过系统状态机图和对象状态机图对各模块状态变迁进行建模,使用UML2.0序列图对模块之间交互行为进行描述.采用基于命题投影时序逻辑的模型检测技术,将对象状态机图转换为Promela模型,系统交互性质转换为命题投影时序逻辑公式,通过模型检测器验证交互模型是否满足于系统的性质,若不满足于该性质,则能够获得反例执行的路径.给出了一个分布式软件系统测试框架,在验证后的序列图模型基础上,使用基于模型的测试用例自动生成方法得到测试用例集合,该集合能够实现对交互行为的有效测试.实例结果表明,该方法可以提高分布式软件系统中模块交互行为的有效性和可靠性.
流敏感按需指针别名分析算法
逄龙,苏小红,马培军,赵玲玲
2015, 52(7):  1620-1630.  doi:10.7544/issn1000-1239.2015.20140336
摘要 ( 823 )   HTML ( 0)   PDF (1785KB) ( 735 )  
相关文章 | 计量指标
为了提高交互环境下指针别名查询的响应效率,近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销.典型的代表是基于上下文无关文法的按需别名分析算法.但是,该算法的精度只局限于控制流不敏感.控制流不敏感的别名关系将约束上层分析的精度.针对该不足,提出了具有流敏感精度的按需别名分析算法.首先采用不完全静态单赋值语句形式来区分指针变量赋值实例,然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图,最后将别名关系查询问题转换为在赋值流图上搜索目标结点间在控制流可达条件下赋值路径的可达性问题,进而实现流敏感的按需别名分析.实验表明,与流不敏感的按需别名分析相比,该方法可以在保证查询效率的前提下,有效提高按需别名分析的精度.
基于接口精化的广义无干扰性研究
孙聪,习宁,高胜,张涛,李金库,马建峰
2015, 52(7):  1631-1641.  doi:10.7544/issn1000-1239.2015.20140306
摘要 ( 655 )   HTML ( 2)   PDF (2594KB) ( 394 )  
相关文章 | 计量指标
在复杂构件化软件的设计和实现过程中,由于安全属性的可组合性难以实现,使得系统整体的安全需求难以得到有效保证,因而安全属性的规约和验证问题是构件化软件开发过程中关注的关键问题.针对当前构件化软件设计过程中,信息流安全属性仅局限于二元安全级格模型的问题,在现有安全接口结构基础上提出广义安全接口结构,在广义安全接口结构上定义精化关系,并利用这一精化关系定义了能够支持任意有限格模型的基于安全多执行的无干扰属性,首次将安全多执行的思想应用于构件化系统的信息流安全属性验证.使用Coq定理证明工具实现了接口自动机程序库以及对精化关系的判定过程,并用实例验证说明了无干扰属性定义的特点及判定方法的有效性.
信息安全
基于威胁传播采样的复杂信息系统风险评估
马刚,杜宇鸽,安波,张博,王伟,史忠植
2015, 52(7):  1642-1659.  doi:10.7544/issn1000-1239.2015.20140184
摘要 ( 704 )   HTML ( 2)   PDF (2664KB) ( 564 )  
相关文章 | 计量指标
互联网时代的信息安全已成为全社会关注的问题之一.信息系统是信息的载体,为有效评估大规模分布式复杂信息系统的风险,构建了一种基于威胁传播采样的复杂信息系统风险评估方法.该方法考虑到威胁在复杂信息系统中传播时,对资产结点的转移状态以及资产结点发出的威胁传播边进行采样来生成威胁传播树(threat propagation trees, TPT),然后通过计算威胁传播树中各资产结点的期望损失以及威胁传播树的概率来对整个复杂信息系统进行风险评估.实验分析表明,基于威胁传播采样的复杂信息系统风险评估方法,在生成威胁传播树时具有高效的时间效率,能够对复杂信息系统进行客观准确的风险评估,且在对复杂信息系统资产结点制定安全防护策略时,能够为安全风险管理者提供较为合理的安全指导建议.
基于HIBC的云信任分散统一认证机制
田俊峰,孙可辉
2015, 52(7):  1660-1671.  doi:10.7544/issn1000-1239.2015.20140295
摘要 ( 786 )   HTML ( 3)   PDF (3492KB) ( 592 )  
相关文章 | 计量指标
开放式云环境中,整合在同一云基础设施平台上的服务提供商之间既相互依存,又相互独立,相互合作的同时又相互竞争,不能接受同一个公用中央机构的完全控制.适用于大规模云环境下的统一认证机制面临中央机构安全瓶颈、密钥托管等问题.为解决此类问题,基于HIBC(hierarchical identity-based cryptography)算法,依据信任分散理论,提出了一种将中央机构的秘密值秘密共享给参与主体的思想,构建了一套完整的混合云统一认证机制,既实现了统一认证的需求又提高了参与主体对自身的控制能力,中央机构核心工作改由参与主体合作完成.运用伪公钥和滑动窗口机制有效防止了内部合谋攻击和外部截获攻击,加大了敌手攻击的难度.同时给出了跨域认证方案和会话密钥协商方案.最后,比较分析了所提出的方案在不依赖可信中心、无需证书维护、无密钥托管、跨域认证、监督机制、可规模使用等方面具有的优越性.
一种基于公钥分割的多副本持有性证明方案
付伟,吴晓平,叶清,肖侬,卢锡城
2015, 52(7):  1672-1681.  doi:10.7544/issn1000-1239.2015.20140353
摘要 ( 676 )   HTML ( 0)   PDF (1958KB) ( 519 )  
相关文章 | 计量指标
在数据外包的云存储环境中,如何验证存储服务方是否忠诚地按照客户需求保存足够数量的副本数据是一个挑战性问题.现有方案只能对各个副本逐一进行验证,存在验证效率低、计算开销大和对数据更新支持弱等缺点.提出一种带Collector的多副本云存储模型,在此基础上给出一种基于公钥分割的多副本持有性证明方案(multiple replica possession proving scheme based on public key partition, MRP-PKP).该方案将公钥分割为多个份额并分配给对应的副本存储节点;在验证时,能够一次性对所有副本的持有性进行高效验证.此外,该方案可有效防御同谋攻击,能够方便地支持数据块级更新操作.进一步理论分析和模拟实验表明:与传统方案相比,MRP-PKP方案具有安全性高、通信开销低、运算代价小等优势.
图形图像
基于稀疏轮廓点模型的彩色重叠细胞图像分割
关涛,周东翔,樊玮虹,刘云辉
2015, 52(7):  1682-1691.  doi:10.7544/issn1000-1239.2015.20140324
摘要 ( 1060 )   HTML ( 3)   PDF (3305KB) ( 720 )  
相关文章 | 计量指标
根据对细胞轮廓结构的分析,提出了描述细胞轮廓特征的稀疏轮廓点模型.该模型将细胞轮廓划分为强轮廓和弱轮廓2部分,并用一系列稀疏的轮廓点来近似表示细胞轮廓.在该模型的基础上,算法综合了彩色图像处理与灰度图像处理的方法,首先提取细胞与背景交界处的强轮廓作为基准轮廓.然后提出了一种环形动态轮廓搜索算法,沿着基准轮廓搜索位于重叠细胞区域的弱轮廓.经过轮廓搜索算法获得细胞的稀疏轮廓点组成初始轮廓,采用GVF(gradient vector flow) Snake模型进行细胞的精确分割.通过对2个细胞图像数据集的图像样本进行的分割实验验证了算法对于分割单细胞图像、同种颜色重叠细胞图像和不同颜色重叠细胞图像的准确性.
基于目标分块多特征核稀疏表示的视觉跟踪
胡昭华,袁晓彤,李俊,何军
2015, 52(7):  1692-1704.  doi:10.7544/issn1000-1239.2015.20140152
摘要 ( 757 )   HTML ( 0)   PDF (4749KB) ( 580 )  
相关文章 | 计量指标
大多数现有的基于稀疏表示的跟踪器仅采用单个目标特征来描述感兴趣的目标,因而在处理各种复杂视频时不可避免会出现跟踪不稳定的情况.针对这个问题,提出一种基于多特征联合稀疏表示的粒子滤波跟踪算法.该算法的主要思想是对随时间不断更新的字典模板和抽样粒子的局部块依据其位置进行分类,用字典中所有类别块对抽样粒子的局部块进行稀疏表示,而仅用与字典中具有相同类别的局部块及表示系数进行重构,根据重构误差构建似然函数以确定最佳粒子(候选目标),实现对目标的精确跟踪.该方法不仅实现了局部块的结构稀疏性,而且充分考虑了粒子之间的依赖关系,提高了跟踪精度.将算法进一步推广到采用基于核的多种特征描述,经混合范数约束并利用KAPG(kernelizable accelerated proximal gradient)方法求解联合特征的稀疏系数.定性和定量的实验结果均表明该算法在目标发生遮挡、旋转、尺度变化、快速运动、光照变化等各种复杂情况下,依然可以准确地跟踪目标.