当期目录

    2016年 第36卷 第7期 刊出日期:2016-07-10
    网络与通信
    基于软件定义网络的媒体分发网络的接入控制
    曹浩, 殷保群, 曹杰, 陆效农
    2016, 36(7):  1767-1771.  DOI: 10.11772/j.issn.1001-9081.2016.07.1767
    摘要 ( )   PDF (957KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对软件定义网络(SDN)环境下的媒体分发网络的接入控制问题,提出了一种综合考虑服务节点和传输链路服务性能优化问题的接入控制方案。该方案利用SDN控制器对路由器的直接管控和对全网的感知能力,对应用层上服务节点服务性能和网络层上服务节点到用户之间的传输链路的服务性能进行联合优化,减少了链路拥塞对数据传输和用户服务质量的影响。首先,为SDN服务系统的接入控制过程建立部分可观Markov决策过程(POMDP)模型;然后,使用基于观测的随机策略作为系统的接入控制策略;最后,通过策略梯度算法对接入控制策略进行优化,求解出模型的最优策略。仿真结果表明,与尽力而为的服务策略相比,基于POMDP模型的最优接入控制策略使系统性能提高了10%,验证了所提方法的有效性。
    数据流特征感知的交换机流表智能更新方法
    姜立立, 曾国荪, 丁春玲
    2016, 36(7):  1772-1778.  DOI: 10.11772/j.issn.1001-9081.2016.07.1772
    摘要 ( )   PDF (1117KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对软件定义网络(SDN)中交换机流表匹配率低的问题,提出了数据流特征感知的交换机流表智能更新方法。首先,论述流表项的生存超时时间timeout对数据包匹配的影响,并且分析比较基于先进先出(FIFO)、近期最少使用(LRU)等一般方法存在的不足;其次,根据流表项的生存时间和数据流的特征密切相关的思想,利用基于隐马尔可夫模型(HMM)的深度流检测(DFI)技术对数据流进行分类;最后,根据流表资源和控制器计算资源状况,实现对不同类型数据流流表项的智能更新。采用校园数据中心网络行为数据的模拟实验表明,与流表更新的一般方法相比,智能方法能使流表匹配率提高5%以上,对SDN交换机的管理有实际意义。
    非强占有限优先权M/G/1排队系统
    黄业文, 邝神芬, 杨荣领, 杨春侠
    2016, 36(7):  1779-1783.  DOI: 10.11772/j.issn.1001-9081.2016.07.1779
    摘要 ( )   PDF (847KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题,提出了一种非强占有限优先权M/G/1排队系统模型的方法。该系统模型引入控制完全优先权的参数n,使得数据帧的完全优先权变成有限优先权,考虑了不同优先级队伍之间的公平性,降低了计算机网络数据服务系统拥塞的风险,使得网络系统在有限优先权下有较好的稳定性。在模型研究中,运用全概率拆解方法获得各级队伍平均等待时间、平均逗留时间和平均队长的理论结果。对模型采用Matlab 2010a软件实验仿真,实验得到的各级队伍平均等待时间和理论平均等待时间的平均绝对误差为0.951%。实验中,有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值。实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的,该模型具有更稳定的系统特性。
    软件定义网络架构下基于流调度代价的数据中心网络拥塞控制路由算法
    孙三山, 汪帅, 樊自甫
    2016, 36(7):  1784-1788.  DOI: 10.11772/j.issn.1001-9081.2016.07.1784
    摘要 ( )   PDF (797KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对传统数据中心网络极易发生拥塞的问题,提出了在软件定义网络(SDN)的架构下设计基于流调度代价的拥塞控制路由算法加以解决。首先,进行拥塞链路上的大小流区分,并对所有大流的各条等价路径进行路径开销权重的计算,选择权重最小的路径作为可用调度路径;然后,使用调度后路径开销变化量和流占用带宽比例来共同定义流调度代价;最终选择调度代价最小的流进行调度。仿真结果表明,所提算法能在网络发生拥塞时降低了拥塞链路上的负荷,并且与仅进行流路径选择的拥塞控制算法相比,提高了链路利用率,减少了流传输时间,使得网络链路资源得到更好的利用。
    基于复杂网络的车载自组织网络抗毁性分析
    冯慧芳, 李彩虹
    2016, 36(7):  1789-1792.  DOI: 10.11772/j.issn.1001-9081.2016.07.1789
    摘要 ( )   PDF (791KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对车载自组织网络(VANET)的抗毁性问题,分析了其在随意攻击和蓄意攻击下网络的抗毁性特征。首先,提出以最大连通度、连通分支平均规模、临界点移除比例及网络效率为评价指标的VANET拓扑抗毁性参数;然后,基于带有车辆换道功能的智能驾驶员模型,应用VanetMobisim仿真软件建立VANET;最后,通过仿真实验分析了网络节点数、通信半径以及攻击模式对VANET抗毁性的影响。实验结果表明由于车辆节点度分布的不均匀性,VANET对随意攻击具有较强的抗毁性,而在蓄意攻击下显得比较脆弱;基于节点介数的蓄意攻击对网络的破坏更快、更强。这些规律为优化VANET拓扑控制、网络协议开发和网络管理提供新的指导。
    先进计算
    基于切片原理的海量点云并行简化算法
    官亚勤, 赵学胜, 王鹏飞, 李大朋
    2016, 36(7):  1793-1796.  DOI: 10.11772/j.issn.1001-9081.2016.07.1793
    摘要 ( )   PDF (595KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对传统点云简化算法效率低且处理点数少的缺陷,结合快速成型领域的切片原理顾及特征计算复杂度低的特点,设计并实现了适合千万级海量激光雷达(LiDAR)点云的并行切片简化算法。该算法根据切片原理对点云模型分层并按照角度排序,利用NVIDA的统一计算设备架构(CUDA)和可编程图形处理器(GPU)高度并行的性能优势,使用GPU多线程高效并行地执行单层切片点云简化,提高了算法效率。最后,应用3组不同数量级点云模型分别进行简化对比实验。实验结果表明:在保持模型特征与压缩比不变的情况下,所提算法效率高出传统基于CPU的串行切片算法1~2个量级。
    海量图片快速去重技术
    韩逢庆, 宋志坚, 余锐
    2016, 36(7):  1797-1800.  DOI: 10.11772/j.issn.1001-9081.2016.07.1797
    摘要 ( )   PDF (568KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对海量图片中的去除重复图片效率低的问题,提出一种基于图片特征的并行化海量图片快速去重技术。首先,对图片提取图片颜色、纹理、形状等特征,用来全面描述图片;其次,使用度量标准对图片之间的特征距离进行度量计算;最后,利用如果两个点到任意一点距离相等则这两点有可能是同一个点的思想实现根据特征距离对重复图片的快速定位,达到重复图片检测与去重的目的。结合实验数据分析验证该技术不仅能够准确地去重图片,且采用i5四核处理器的单机计算方式仅10 min左右即可处理500万级图片量,与一般的两两计算相比,提高了海量图片去重的时效性,使得计算时间大幅度缩短。
    基于OpenCL的尺度不变特征变换算法的并行设计与实现
    许川佩, 王光
    2016, 36(7):  1801-1806.  DOI: 10.11772/j.issn.1001-9081.2016.07.1801
    摘要 ( )   PDF (966KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对尺度不变特征变换(SIFT)算法实时性差的问题,提出了利用开放式计算语言(OpenCL)并行优化的SIFT算法。首先,通过对原算法各步骤进行组合拆分、重构特征点在内存中的数据索引等方式对原算法进行并行化重构,使得算法的中间计算结果能够完全在显存中完成交互;然后,采用复用全局内存对象、共享局部内存、优化内存读取等策略对原算法各步骤进行并行设计,提高数据读取效率,降低传输延时;最后,利用OpenCL语言在图形处理单元(GPU)上实现了SIFT算法的细粒度并行加速,并在中央处理器(CPU)上完成了移植。与原SIFT算法配准效果相近时,并行化的算法在GPU和CPU平台上特征提取速度分别提升了10.51~19.33和2.34~4.74倍。实验结果表明,利用OpenCL并行加速的SIFT算法能够有效提高图像配准的实时性,并能克服统一计算设备架构(CUDA)因移植困难而不能充分利用异构系统中多种计算核心的缺点。
    改进的超越函数分段线性逼近方法
    田征, 杜慧敏, 黄小康
    2016, 36(7):  1807-1810.  DOI: 10.11772/j.issn.1001-9081.2016.07.1807
    摘要 ( )   PDF (568KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对超越函数计算中所采用的分段线性逼近算法存在的无法提前确定精度及部分区间资源浪费的问题,提出一种改进的分段线性逼近超越函数算法。该算法由预定义的逼近区间端点计算出用于逼近的线性函数,根据被逼近函数的凹凸性对所计算线性函数进行调整,在此基础上计算出预定义逼近区间内调整后函数与被逼近函数之间的最大误差;按照所需精度的要求,自动调整逼近区间,通过该过程的迭代,获得了较少分段次数。算法结果在Matlab上进行仿真,仿真结果表明,所提算法的分段数相比等分法减少了60%。所提算法在保证精度的前提下,降低了查找表(LUT)的资源消耗。
    网络空间安全
    面向云平台的多样化恶意软件检测架构
    高超, 郑小妹, 贾晓启
    2016, 36(7):  1811-1815.  DOI: 10.11772/j.issn.1001-9081.2016.07.1811
    摘要 ( )   PDF (949KB) ( )  
    参考文献 | 相关文章 | 计量指标
    近年来,恶意软件对物理机和云平台上虚拟机均构成巨大的安全威胁。在基础设施即服务(IaaS)云平台上部署传统的杀毒软件、防火墙等恶意软件检测工具存在以下问题:1)检测工具可能被破坏或者关闭;2)单一的检测工具效果不理想;3)检测工具可能被加壳等方式绕过;4)需要给每台客户机安装额外软件,难以部署实施。为此提出一种面向云平台的多样化恶意软件检测架构。该架构利用虚拟化技术截获客户机的特定行为,抓取客户机内软件释放的代码,通过多种杀毒软件多样化的扫描确定软件的恶意性。采用的动态内存提取的方式对客户机完全透明。最后在Xen上部署该架构并进行恶意软件检测测试,该架构对加壳恶意软件的检测率为85.7%,比杀毒软件静态扫描的检测率高14.3个百分点。实验结果表明,在云平台上采用多样化恶意软件检测框架能更好地保障客户机的安全。
    基于代理重签名的支持用户可撤销的云存储数据公共审计方案
    张新鹏, 许春香, 张新颜, 赛伟, 韩兴阳, 刘国平
    2016, 36(7):  1816-1821.  DOI: 10.11772/j.issn.1001-9081.2016.07.1816
    摘要 ( )   PDF (927KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对用户动态可撤销需要新的数据管理员对其前任所管理的数据进行完整性验证的问题,基于单向代理重签名技术提出了具有隐私保护的支持用户可撤销的云存储数据公共审计方案。首先,该方案中所采用的单向代理重签名算法,其代理重签名密钥由当前用户私钥结合已撤销用户公钥生成,不存在私钥泄露问题,能够安全实现数据所有权的转移;其次,该方案证明了恶意的云服务器不能产生伪造的审计证明响应信息来欺骗第三方审计者(TPA)通过审计验证过程;更进一步,该方案采用了随机掩饰码技术,能够有效防止好奇的第三方审计者恢复原始数据块。和Panda方案相比较,所提方案在增加抗合谋攻击功能的基础上,其审计过程中通信开销与计算代价仍全部低于Panda方案。
    混合云环境下基于属性的密文策略加密方案
    陈亮, 杨庚, 屠袁飞
    2016, 36(7):  1822-1827.  DOI: 10.11772/j.issn.1001-9081.2016.07.1822
    摘要 ( )   PDF (901KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对现有云存储的数据和访问控制的安全性不高,从而造成用户存储的敏感信息被盗取的现象,结合现有的基于密文策略属性加密(CP-ABE)方案和数据分割的思想,提出了一个基于混合云的高效数据隐私保护模型。首先根据用户数据的敏感程度将数据合理分割成不同敏感级别的数据块,将分割后的数据存储在不同的云平台上,再根据数据的安全级别,进行不同强度的加密技术进行数据加密。同时在敏感信息解密阶段采取“先匹配后解密”的方法,并对算法进行了优化,最后用户进行一个乘法运算解密得到明文。在公有云中对1 Gb数据进行对称加密,较单节点提高了效率一倍多。实验结果表明:该方案可以有效保护云存储用户的隐私数据,同时降低了系统的开销,提高了灵活性。
    面向移动云存储的属性基解密服务中间件
    蔡孟飞, 何倩, 程东生, 王士成
    2016, 36(7):  1828-1833.  DOI: 10.11772/j.issn.1001-9081.2016.07.1828
    摘要 ( )   PDF (896KB) ( )  
    参考文献 | 相关文章 | 计量指标
    属性基加密(ABE)算法支持对云端数据的细粒度访问控制。针对属性基解密计算复杂度高,难以在资源受限的移动终端上实现的问题,提出并实现了一种面向移动云存储的属性基解密服务中间件。在保证密文信息不被中间件获取的前提下,中间件为移动终端代理属性基解密服务,实现了基于树形结构的线性秘密共享(LSSS)矩阵求解,降低了终端的计算与通信开销,提高了解密速度;属性权威可以在不需要用户参与的条件下,即时、细粒度地撤销用户属性;所有接口均使用Restful服务,保证了通用性。实验结果表明,属性基解密服务中间件提高移动设备解密性能近30倍,具备较好的并发性能,属性撤销具有实用性。
    云系统中多域安全策略规范与验证方法
    蔡婷, 蔡宇, 欧阳凯
    2016, 36(7):  1834-1840.  DOI: 10.11772/j.issn.1001-9081.2016.07.1834
    摘要 ( )   PDF (1108KB) ( )  
    参考文献 | 相关文章 | 计量指标
    为了有效管理云系统间跨域互操作中安全策略的实施,提出一种适用于云计算环境的多域安全策略验证管理技术。首先,研究了安全互操作环境的访问控制规则和安全属性,通过角色层次关系区分域内管理和域间管理,形式化定义了基于多域的角色访问控制(domRBAC)模型和基于计算树逻辑(CTL)的安全属性规范;其次,给出了基于有向图的角色关联映射算法,以实现domRBAC角色层次推理,进而构造出了云安全策略验证算法。性能实验表明,多域互操作系统的属性验证时间开销会随着系统规模的扩大而增加。技术采用多进程并行检测方式可将属性验证时间减少70.1%~88.5%,其模型优化检测模式相比正常模式的时间折线波动更小,且在大规模系统中的时间开销要明显低于正常模式。该技术在规模较大的云系统安全互操作中具有稳定和高效率的属性验证性能。
    自动下载行为检测
    黄吉鲲, 龚伟刚, 游伟, 秦波, 石文昌, 梁彬
    2016, 36(7):  1841-1846.  DOI: 10.11772/j.issn.1001-9081.2016.07.1841
    摘要 ( )   PDF (903KB) ( )  
    参考文献 | 相关文章 | 计量指标
    目前,很多恶意网页仅利用常规的Web编程技术使得浏览器自动下载木马等恶意软件并诱骗用户执行。这种恶意行为被称为自动下载。浏览器中现有的防御机制并不能有效地识别这种攻击。针对此类恶意行为,提出了一种防御方法。该方法通过监控网页中能导致自动下载的操作,并在下载实际发生时判断是否由用户触发,来识别自动下载行为并加以阻断。此防御方法已经在WebKitGtk+2.8.0和Chromium 38.0.2113.1两个浏览器中实现,并进行了评估:两个检测防御系统针对现存的攻击样本均无误报和漏报,额外的性能开销分别为1.26%和7.79%。实验结果表明,该方法能够有效地监测并阻断自动下载攻击且性能开销较小。
    基于改进Apriori算法的审计日志关联规则挖掘
    徐开勇, 龚雪容, 成茂才
    2016, 36(7):  1847-1851.  DOI: 10.11772/j.issn.1001-9081.2016.07.1847
    摘要 ( )   PDF (771KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对安全审计系统中存在的智能程度低、日志信息没有充分利用的问题,提出一个基于关联规则挖掘的安全审计系统。该系统充分利用已有审计日志,结合数据挖掘技术,建立用户及系统的行为模式数据库,做到及时发现异常情况,提高了计算机的安全性。在传统Apriori算法的基础上提出一种改进的E-Apriori算法,该算法可以缩小待扫描事务集合的范围,降低算法的时间复杂度,提高运行效率。实验结果表明基于关联规则挖掘的审计系统对攻击类型的识别能力提升在10%以上,改进的E-Apriori算法相比经典Apriori算法和FP-GROWTH算法在性能上得到了提高,特别是在大型稀疏数据集中最高达到51%。
    基于地址随机和段隔离的全局偏移表保护方法
    林键, 郭玉东, 周少皇
    2016, 36(7):  1852-1855.  DOI: 10.11772/j.issn.1001-9081.2016.07.1852
    摘要 ( )   PDF (771KB) ( )  
    参考文献 | 相关文章 | 计量指标
    在可执行和可链接格式(ELF)的可执行程序中,存在一个全局偏移表(GOT),用于存放引用库函数的绝对地址,但是在Linux系统中,GOT解引用和GOT覆写是两种比较常用的漏洞利用方法。通过分析GOT的特性,提出并实现了基于地址随机和段隔离的GOT保护方法。通过修改Linux的可执行程序加载器,将与GOT有数据指向关系的节均加载到随机内存地址;同时使用段隔离技术,对GOT的代码引用的指令使用一个新的段寄存器进行间接引用。实验结果证明,该方法不仅能够有效地防御针对GOT的漏洞利用方法,而且性能损耗极低,只有平均2.9 ms的额外开销。
    基于容错学习的GSW-型全同态层次型IBE方案
    戴晓明, 张薇, 郑志恒, 李镇林
    2016, 36(7):  1856-1860.  DOI: 10.11772/j.issn.1001-9081.2016.07.1856
    摘要 ( )   PDF (779KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对传统的基于身份的加密(IBE)方案不能够对密文直接进行计算这一功能上的缺陷,提出了一个新的IBE方案。该方案利用Gentry等提出的同态转化机制,结合Agrawal等构造的层次型IBE方案,构造了一个具有全同态性质的层次型IBE方案。与Gentry等提出的全同态加密(GSW)方案(GENTRY C,SAHAI A,WATERS B. Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based. CRYPTO 2013:Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin:Springer,2013:75-92)和Clear等提出的全同态IBE(CM)方案(CLEAR M,MCGOLDRICK C. Bootstrappable identity-based fully homomorphic encryption. CANS 2014:Proceedings of 13th International Conference on Cryptology and Network Security. Berlin:Springer,2014:1-19)相比,该方案构造方法更加自然,空间复杂度由立方级降低到平方级,效率更高。在当前云计算背景下,有助于基于容错学习(LWE)的全同态加密方案从理论向实践转化。通过性能分析并在随机预言机模型下验证了所提方案具有完全安全下的选择明文攻击(IND-ID-CPA)安全性。
    理想格上基于身份的环签名方案
    孙意如, 梁向前, 商玉芳
    2016, 36(7):  1861-1865.  DOI: 10.11772/j.issn.1001-9081.2016.07.1861
    摘要 ( )   PDF (889KB) ( )  
    参考文献 | 相关文章 | 计量指标
    现有的签名方案大多是基于双线性对,但在量子计算环境下此类方案被证明是不安全的。格具有运算简单、困难问题难以破解等特点,为了抵抗量子攻击,基于格中标准的小整数解(SIS)困难假设,利用Ducas等提出的理想格技术(DUCAS L,MICCIANCIO D. Improved short lattice signatures in the standard model. Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Berlin:Springer,2014:335-352),构造了一种能够在标准模型下给出安全性证明的基于身份的环签名方案。该方案主要分为4个步骤:主密钥生成算法、签名私钥生成算法、签名算法和验证算法。输出的签名为单个向量。相比同类型格上的签名方案,在一定程度上缩减了公钥、签名私钥及签名的长度,提高了运算效率,适用于轻量级认证,算法的安全性也间接保证了电子商务和云计算等领域的安全性。
    基于单个服务器的双线性对运算外包算法
    蒋铁金, 任艳丽
    2016, 36(7):  1866-1869.  DOI: 10.11772/j.issn.1001-9081.2016.07.1866
    摘要 ( )   PDF (546KB) ( )  
    参考文献 | 相关文章 | 计量指标
    双线性对运算是公钥密码算法的基本运算之一,在基于身份加密、基于属性加密等密码体制中有重要应用。现有可行的双线性对外包算法均基于两个不可信服务器,这在实际应用中不易实现。针对此问题,提出一种基于单个服务器的双线性对运算外包算法。通过少量的预计算,即可对用户的输入进行盲化处理,实现输入及输出的保密性,并能有效地验证外包结果的正确性。实验结果表明,所提算法只需进行常数次点加和模乘运算,极大地降低用户的计算代价,并且可验证性概率可达到2/5。与现有的双线性外包算法相比,所提算法仅需要调用一个不可信服务器,在实际应用中更易实现。
    人工智能
    基于适应性动态步长的变异果蝇优化算法
    王行甫, 陈静, 王琳
    2016, 36(7):  1870-1874.  DOI: 10.11772/j.issn.1001-9081.2016.07.1870
    摘要 ( )   PDF (768KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对基本果蝇优化算法(FOA)容易陷入局部最优值、后期收敛速度变慢和收敛精度较低的缺点,提出了一种基于适应性动态步长的变异果蝇优化算法(MFOAADS)。首先,利用佳点集法选取种群初始位置,降低算法初始点选取的随机性和陷入局部最优值的概率;然后,采用适应性动态步长优化策略,提高收敛速度和求解精度;最后,若算法陷入了早熟,则对种群最优个体按一定概率执行柯西变异扰动,赋予其跳出局部最优的能力。经5个经典函数测试表明,固定迭代次数时MFOAADS的收敛精度与收敛速度明显优于FOA;固定目标精度时,MFOAADS相对于FOA平均迭代次数有着大幅下降且成功率达97%以上。实验结果表明,所提算法求解精度、运行效率以及可靠性相对于基本FOA算法都有着显著提高。
    基于信息关联拓扑的互联网社交关系挖掘
    刘锦文, 邢凯, 芮伟康, 张利萍, 周慧
    2016, 36(7):  1875-1880.  DOI: 10.11772/j.issn.1001-9081.2016.07.1875
    摘要 ( )   PDF (1000KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对目前基于监督学习的关系抽取方法需要标注大量训练数据和预先定义关系类型,提出了一种基于词语共现信息构建关联网络并在关联网络上进行图聚类分析的人物关系提取方法。首先,从新闻标题数据获得关联度较高的500个人物对用于关系抽取研究;然后,抓取关联人物对所在新闻数据,对其进行预处理,并利用词频-逆向文档频率(TF-IDF)得到人物对共现句子中的关键词;其次,基于词语共现信息得到词语之间的关联,进而建立关键词关联网络;最后,利用对关联网络进行图聚类分析以获得人物关系。在关系抽取的实验中,与传统基于词语共现和模式匹配的中文实体关系提取方法相比,所提方法在准确率、召回率和平衡F分数(F-score)上分别提升了5.5,3.7和4.4个百分点。实验结果表明,所提算法能够在没有标注训练数据的条件下,有效地从新闻数据中抽取丰富且高质量的人物关系数据。
    中文异构百科知识库实体对齐
    黄峻福, 李天瑞, 贾真, 景运革, 张涛
    2016, 36(7):  1881-1886.  DOI: 10.11772/j.issn.1001-9081.2016.07.1881
    摘要 ( )   PDF (1027KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对传统实体对齐方法在中文异构网络百科实体对齐任务中效果不够显著的问题,提出一种基于实体属性与上下文主题特征相结合的实体对齐方法。首先,基于百度百科及互动百科数据构造中文异构百科知识库,通过统计方法构造资源描述框架模式(RDFS)词表,对实体属性进行规范化;其次,抽取实体上下文信息,对其进行中文分词后,利用主题模型对上下文建模并通过吉布斯采样法求解模型参数,计算出主题-单词概率矩阵,提取特征词集合及对应特征矩阵;然后,利用最长公共子序列(LCS)算法判定实体属性相似度,当相似度位于下界与上界之间时,进一步结合百科类实体上下文主题特征进行判定;最后,依据标准方法构造了一个异构中文百科实体对齐数据集进行仿真实验。实验结果表明,与经典的属性相似度算法、属性加权算法、上下文词频特征模型及主题模型算法进行比较,所提出的实体对齐算法在人物领域和影视领域的准确率、召回率与综合指标F值分别达到97.8%、88.0%、92.6%和98.6%、73.0%、83.9%,比其他方法均有较大的提高。实验结果验证了在构建中文异构百科知识库场景中,所提算法可以有效提升中文百科实体对齐效果,可应用到具有上下文信息的实体对齐任务中。
    基于无监督学习算法的推特文本规范化
    邓加原, 姬东鸿, 费超群, 任亚峰
    2016, 36(7):  1887-1892.  DOI: 10.11772/j.issn.1001-9081.2016.07.1887
    摘要 ( )   PDF (945KB) ( )  
    参考文献 | 相关文章 | 计量指标
    推特文本中包含着大量的非标准词,这些非标准词是由人们有意或无意而创造的。对很多自然语言处理的任务而言,预先对推特文本进行规范化处理是很有必要的。针对已有的规范化系统性能较差的问题,提出一种创新的无监督文本规范化系统。首先,使用构造的标准词典来判断当前的推特是否需要标准化。然后,对推特中的非标准词会根据其特征来考虑进行一对一还是一对多规范化;对于需要一对多的非标准词,通过前向和后向搜索算法,计算出所有可能的多词组合。其次,对于多词组合中的非规范化词,基于二部图随机游走和误拼检查,来产生合适的候选。最后,使用基于上下文的语言模型来得到最合适的标准词。所提算法在数据集上获得86.4%的F值,超过当前最好的基于图的随机游走算法10个百分点。
    智能环境下分布式Rete算法
    汪成亮, 温鑫
    2016, 36(7):  1893-1898.  DOI: 10.11772/j.issn.1001-9081.2016.07.1893
    摘要 ( )   PDF (942KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对智能环境中基于Rete的规则推理引擎需要将数据集中到sink节点,导致传感器网络中数据传输量过大的问题,建立了Rete网络代价模型,并提出了最小传输代价的Rete分布的算法(MCoRDS)。该算法通过统计Rete网络中子模式对事实数据的依赖,发现大部分子模式在对应事实数据采集Sensor附近便具备了计算推理条件,故将Rete网络中的子模式规则分布到最早汇集其所需所有事实数据的Sensor中,即可避免事实数据进一步往sink节点的传输,从而大量减少传感器网络中的数据传输量。对比将Rete网络放置在sink节点的集中式推理进行了4组仿真实验。其中第4组实验,传感器网络总跳数由85000减至8036,减少约90.5%;其余组实验传输跳数也有一定的减少。实验结果表明,最小代价的Rete分布具有更小的数据传输量,在规则触发频率低、规则规模较大的情况下尤甚。
    基于免疫克隆特征选择和欠采样集成的垃圾网页检测
    卢晓勇, 陈木生, 吴政隆, 张百栈
    2016, 36(7):  1899-1903.  DOI: 10.11772/j.issn.1001-9081.2016.07.1899
    摘要 ( )   PDF (808KB) ( )  
    参考文献 | 相关文章 | 计量指标
    为解决垃圾网页检测过程中的“维数灾难”和不平衡分类问题,提出一种基于免疫克隆特征选择和欠采样(US)集成的二元分类器算法。首先,使用欠采样技术将训练样本集大类抽样成多个与小类样本数相近的样本集,再将其分别与小类样本合并构成多个平衡的子训练样本集;然后,设计一种免疫克隆算法遴选出多个最优的特征子集;基于最优特征子集对平衡的子样本集进行投影操作,生成平衡数据集的多个视图;最后,用随机森林(RF)分类器对测试样本进行分类,采用简单投票法确定测试样本的最终类别。在WEBSPAM UK-2006数据集上的实验结果表明,该集成分类器算法应用于垃圾网页检测:与随机森林算法及其Bagging和AdaBoost集成分类器算法相比,准确率、F1测度、AUC等指标均提高11%以上;与其他最优的研究结果相比,该集成分类器算法在F1测度上提高2%,在AUC上达到最优。
    基于二次聚类和隐马尔可夫链的持卡消费行为预测
    宋涛, 王星
    2016, 36(7):  1904-1908.  DOI: 10.11772/j.issn.1001-9081.2016.07.1904
    摘要 ( )   PDF (786KB) ( )  
    参考文献 | 相关文章 | 计量指标
    银行卡支付在社会消费行为中占很大比例,在促进经济增长中发挥重大作用,因此,预测持卡消费行为具有重要意义。然而,传统方法难以有效应对复杂数据和动态变化。为此,提出基于二次聚类和隐马尔可夫链(HMC)理论的个体消费行为预测方法。首先,对消费行为按照序列进行模式聚类,并引入惩罚聚类进行二次聚类,对序列模式中的层次状态进行平衡划分;其次,利用HMC来估计序列中消费层次的状态转移,对用户的未来消费行为进行预测。最后,通过实验比较分析传统聚类、无惩罚序列聚类和带惩罚项的聚类结果表明,提出的基于二次聚类和隐马氏链的方法更适用于消费者行为预测。
    基于人工神经网络的秀丽隐杆线虫趋温性行为的建模与仿真
    李明旭, 邓欣, 王进, 王潇, 张笑谋
    2016, 36(7):  1909-1913.  DOI: 10.11772/j.issn.1001-9081.2016.07.1909
    摘要 ( )   PDF (771KB) ( )  
    参考文献 | 相关文章 | 计量指标
    为了模拟秀丽隐杆线虫的趋温性行为,提出一种通过人工神经网络对秀丽隐杆线虫的趋温性行为进行建模的方法,并进行实验仿真。首先,建立秀丽隐杆线虫的运动模型;然后,通过设计非线性函数逼近线虫趋温性的运动逻辑,实现运动速度和偏向角度的改变功能;最后,通过人工神经网络对该非线性函数进行学习,从而在Matlab环境中对上述过程进行实验仿真,模拟出了秀丽隐杆线虫的趋温性行为。实验结果表明,在更接近生物体本质的条件下,反馈(BP)神经网络比径向基函数(RBF)神经网络能更好地模拟线虫的趋温性行为。同时也表明所提方法能够很好地模拟秀丽隐杆线虫的趋温性行为,在一定程度上揭示了线虫趋温性的实质,理论上支持了爬虫机器人的趋温性研究。
    虚拟现实与数字媒体
    基于曲度特征的三维模型检索算法
    周继来, 周明全, 耿国华, 王小凤
    2016, 36(7):  1914-1917.  DOI: 10.11772/j.issn.1001-9081.2016.07.1914
    摘要 ( )   PDF (732KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对如何提高复杂曲面的三维模型的检索精度的问题,提出了一种基于曲度特征的三维模型检索算法。首先,在模型表面选取随机采样点,计算点所在局部曲面的高斯曲率和平均曲率,通过高斯曲率和平均曲率求出随机点的曲度值,曲度值表明了曲面的凹凸属性。然后,以模型的质心为球心,以随机点与质心距离和曲度值为坐标轴建立坐标系,统计出一定距离范围内曲度值分布的概率,构建距离与曲度的分布矩阵,以此分布矩阵作为三维模型特征描述符。该特征描述符具有旋转不变性和平移不变性,能够很好地反映复杂曲面的几何特征。最后,通过比较分布矩阵给出不同模型间的相似度。实验结果表明,该方法相比形状分布算法的检索性能有较大提高,尤其适用于具有复杂曲面的三维模型检索。
    基于新的空间关系特征的图像检索方法
    郭倩, 杨红菊, 梁新彦
    2016, 36(7):  1918-1922.  DOI: 10.11772/j.issn.1001-9081.2016.07.1918
    摘要 ( )   PDF (794KB) ( )  
    参考文献 | 相关文章 | 计量指标
    图像与图像之间没有清晰的空间结构,这样就不能有效利用图像间空间结构上的相关性信息,针对此问题提出一种基于新的空间关系特征的图像检索方法。首先,提取待查询图像在内的全部图像的特征向量。然后,计算特征向量每两个之间的相似性,形成相似性矩阵。将相似性矩阵的列集合作为新特征向量,命名为新的空间关系特征向量,从而将原来的特征向量映射到一个欧氏空间上。最后,在新特征空间上计算相似性,特征向量之间的相似性问题就转化为新的空间关系特征向量之间的相似性问题。在新特征空间上,图像与图像之间的空间结构变得清晰了,有利于图像检索准确度的提高。在Corel数据库上进行实验,所提方法在平均检索查准率、查全率-查准率和可视化评价指标上都优于基于颜色直方图的图像检索方法。结果表明,基于新的空间关系特征的图像检索方法有效利用了图像间空间结构上的相关性信息,具有更好的检索效果。
    结合快速鲁棒性特征改进ORB的特征点匹配算法
    白雪冰, 车进, 牟晓凯, 张英
    2016, 36(7):  1923-1926.  DOI: 10.11772/j.issn.1001-9081.2016.07.1923
    摘要 ( )   PDF (626KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对定向二进制简单描述符(ORB)算法不具备尺度不变性的问题,提出一种结合快速鲁棒性特征(SURF)算法和ORB的改进算法。首先,利用Hessian矩阵检测特征点的方法,使得提取出的特征点具有尺度不变性;然后,用ORB生成特征描述子;接着采用K-近邻算法进行粗匹配;最后,通过比率测试、对称测试、最小平方中值(LMedS)定理进行提纯。尺度变化时,该算法比ORB的匹配精度提高了74.3个百分点,比SURF的匹配精度提高了4.8个百分点;旋转变化时,该算法比ORB的匹配精度提高了6.6个百分点;匹配时间高于SURF低于ORB。实验结果表明,改进算法不仅保持了ORB的旋转不变性,而且具备了尺度不变性,在不失速度的前提下,匹配精度得到较大提高。
    基于四元数小波变换的清晰度评价
    王治文, 罗晓清, 张战成
    2016, 36(7):  1927-1932.  DOI: 10.11772/j.issn.1001-9081.2016.07.1927
    摘要 ( )   PDF (1213KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对当前各种图像清晰度评价方法在清晰度判别过程中单调性和区分度不够以及适用范围较小的问题,提出了一种基于四元数小波变换(QWT)幅值与相位的图像清晰度评价方法。该算法通过四元数小波变换将图像从空间域变换到频率域,对得到的四元数小波变换系数进一步计算之后获得低频子带与高频子带的幅值与相位信息,求得低频子带幅值各方向的梯度之后与对应方向的相位相乘求和,最终得到两个清晰度指标值。采用该算法与多种现有算法对不同内容的图像、不同程度模糊的图像以及含有不同程度噪声的图像进行清晰度评价实验:相对于现有算法,所提算法在对上述多种图像的清晰度评价中都保持着很好的单调性与区分度。实验结果表明,所提算法不但克服了现有算法在单调性与区分度上的不足,而且所提清晰度评价指标可以应用在图像处理中。
    多阈值提取平面点云边界点的方法
    廖中平, 刘科, 向雨, 蔡晨光
    2016, 36(7):  1933-1937.  DOI: 10.11772/j.issn.1001-9081.2016.07.1933
    摘要 ( )   PDF (751KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对基于切片技术的点云数据重建算法需要提取切片内点云边界点,及现有算法效率低、提取效果不好等问题,提出一种多阈值提取平面点云边界点的算法。通过选取判断点的k个近邻点,计算相邻两点与判断点连线间夹角,由于边界点必存在最大夹角,通过判断最大夹角是否超过设定阈值,从而快速提取边界点。通过对阈值设值分析,不同点云数据的边界提取实验及几种方法间比较,该方法不受点云形状影响,均能较好提取边界点,且优于其他3种算法。结果表明该方法在保证原始点云特征信息的前提下,可较好提取边界点,提高后续点云重建速度与效率。
    帧内微块复制的屏幕图像编码算法
    赵利平, 林涛, 龚迅炜, 朱蓉
    2016, 36(7):  1938-1943.  DOI: 10.11772/j.issn.1001-9081.2016.07.1938
    摘要 ( )   PDF (985KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对现有的帧内块复制(IBC)算法不能很好地适应屏幕图像具有各种不同大小和形状样图的问题,为了进一步提高屏幕图像的编码效率,提出了一种帧内微块复制(IMBC)算法。该算法首先将当前编码单元(CU)划分成L个微块。然后以每个微块作为最小的匹配和复制单元,采用匹配微块组选择算法,在参考像素集合R中找到与当前微块最匹配的“参考微块”。用L个位移矢量(DV)来表示“参考微块”所在位置与当前CU所在位置的位移关系。最后,对L个位移矢量应用预测算法以消除位移矢量之间的相关性后进行熵编码。对于屏幕图像标准测试数据集合中的视频序列,IMBC算法与IBC算法相比,在编码复杂度增加较低的前提下,在全帧内(AI)、随机接入(RA)、低延迟(LB)三种编码配置中,有损BD-rate降低率分别达3.4%、2.9%、2.6%,无损Bit-rate降低率分别达9.5%、5.2%、5.1%,能有效提高屏幕图像的编码效率。
    基于结构张量的视频超分辨率算法
    严宏海, 卜方玲, 徐新
    2016, 36(7):  1944-1948.  DOI: 10.11772/j.issn.1001-9081.2016.07.1944
    摘要 ( )   PDF (996KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对传统正则化超分辨率(SR)重建模型中,正则化参数选择过大会使重建结果模糊,导致边缘和纹理等细节丢失,选择过小模型去噪能力又不足的问题,提出一种基于结构张量的双正则化参数的视频超分辨率重建算法。首先,利用局部结构张量对图像进行平滑区域和边缘的检测;然后,利用差异曲率对全变分(TV)进行先验信息加权;最后,对平滑区域和边缘采用不同的正则化参数进行超分辨率重建。实验数据显示提出的算法将峰值信噪比(PSNR)提高了0.033~0.11 dB,具有较好的重建效果。实验结果表明:该算法能够有效地提升低分辨率(LR)视频帧重建效果,可应用于低分辨率视频增强、车牌识别和视频监控中感兴趣目标增强等方面。
    基于图像抠图技术的多聚焦图像融合方法
    张盛林, 易本顺, 李卫中, 刘红玉
    2016, 36(7):  1949-1953.  DOI: 10.11772/j.issn.1001-9081.2016.07.1949
    摘要 ( )   PDF (880KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对多聚焦图像融合容易出现信息丢失、块效应明显等问题,提出了一种新的基于图像抠图技术的多聚焦图像融合算法。首先,通过聚焦检测获得源图像的聚焦信息,并根据所有源图像的聚焦信息生成融合图像的三分图,即前景、背景和未知区域;然后,利用图像抠图技术,根据三分图获得每一幅源图像的精确聚焦区域;最后,将这些聚焦区域结合起来构成融合图像的前景和背景,并根据抠图算法得到的确定前景、背景对未知区域进行最优融合,增强融合图像前景、背景与未知区域相邻像素之间的联系,实现图像融合。实验结果表明,与传统算法相比,所提算法在客观评价方面能获得更高的互信息量(MI)和边缘保持度,在主观评价方面能有效抑制块明显效应,得到更优的视觉效果。该算法可以应用到目标识别、计算机视觉等领域,以期得到更优的融合效果。
    基于贪心优化策略的网格排布算法
    娄自婷, 张亚萍
    2016, 36(7):  1954-1958.  DOI: 10.11772/j.issn.1001-9081.2016.07.1954
    摘要 ( )   PDF (959KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题,提出了一种基于贪心优化策略的三角形排布算法,通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类,根据改进的代价函数选择代价度量最小的顶点作为活动顶点;然后绘制(即输出)其所有未绘制的邻接三角形,并将相邻顶点压入缓存,算法迭代执行直到所有顶点的邻接三角形都绘制完成,得到重新排列后的三角形序列。实验结果表明,该算法不仅具备较高的顶点缓存命中率,还提高了渲染速度,减少了排序的时间,有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。
    基于加锁机制的静态手势识别方法
    王红霞, 王坤
    2016, 36(7):  1959-1964.  DOI: 10.11772/j.issn.1001-9081.2016.07.1959
    摘要 ( )   PDF (981KB) ( )  
    参考文献 | 相关文章 | 计量指标
    基于RGB-D(RGB-Depth)的静态手势识别的速度高于其动态手势识别,但是存在冗余手势和重复手势而导致识别准确性不高的问题。针对该问题,提出了一种基于加锁机制的静态手势识别方法来识别运动中的手势。首先,将通过Kinect设备获取RGB数据流和Depth数据流融合成人体骨骼数据流;然后,在静态手势方法中引入加锁机制,并与之前建立好的骨骼点特征模型手势库进行比对计算;最后,设计一款“程序员进阶之路”益智类网页游戏进行应用与实验。实验验证在6种不同运动手势情况下,该方法与纯静态手势识别方法相比,平均识别准确率提高了14.4%;与动态手势识别相比,识别速度提高了14%。实验结果表明,提出的基于加锁机制的静态手势识别方法,既保留了静态识别的速率,实现了实时识别;又能很好地剔除冗余手势和重复手势,提高了识别正确性。
    复杂环境下通用的手势识别方法
    杜堃, 谭台哲
    2016, 36(7):  1965-1970.  DOI: 10.11772/j.issn.1001-9081.2016.07.1965
    摘要 ( )   PDF (948KB) ( )  
    参考文献 | 相关文章 | 计量指标
    用来解决手势识别中光照变化、背景干扰等问题的方法,往往计算量大,耗时长。针对这一问题,提出了一种复杂环境下通用的手势识别方法。该方法利用二进制方式实现支持向量机(SVM)模型并且使用位运算代替滑动窗口从而完成目标快速筛选,然后用统一计算设备架构(CUDA)实现卷积神经网络对初筛区域进行二次判断和识别。该方法不依赖于动态手势识别技术,可以应用于动态和静态的手势识别,能够同时处理光照变化、背景干扰的问题。实验结果表明所提算法的计算效率相比基于滑动窗口的算法有100至1000倍的提升,处理一幅图片的时间约为0.01 s。在修正后的Marcel数据集上实验结果达到了96.1%的准确率和100%的召回率。效率上的提升使得算法能够实时进行复杂环境下的手势识别。
    不确定性估计结合主动外观模型三维特征提取的人脸识别方法
    卜宇, 任晓芳, 唐学军, 孙挺
    2016, 36(7):  1971-1975.  DOI: 10.11772/j.issn.1001-9081.2016.07.1971
    摘要 ( )   PDF (750KB) ( )  
    参考文献 | 相关文章 | 计量指标
    对于人脸识别分类结果中的可信度问题,提出一种基于不确定性理论的人脸识别方法。首先,为了估计3D特征,使用主动外观模型(AAM)和三角测量处理两幅未知对象的2D图像;然后,估计数据库中每个对象的分数,通过不确定性进一步处理两幅图像;最后,决策过程根据估计的分数和估计的不确定性分类列表,其中分类列表中存储了所有已识别对象及其对应的可信度。实验采用含两个摄像头的立体视觉系统采集各种姿态的人脸图像。与类似的概率预测测量方法相比,所提方法的正确检测率提高10%左右,漏检率至少降低了9%。实验结果表明,所提方法通过构建3D图像特征的不确定性信息和采用合适的统计方法提高了分类结果的准确率。
    基于纹理和草图的图像铅笔画绘制
    孙玉红, 张元科, 孟静, 韩丽娟
    2016, 36(7):  1976-1980.  DOI: 10.11772/j.issn.1001-9081.2016.07.1976
    摘要 ( )   PDF (853KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对目前铅笔画生成方法中的线条不够灵活、纹理缺少方向感的问题,提出了一种基于带方向的纹理和线条草图将一幅图像转换为铅笔画风格的方法。首先,对输入图像进行直方图匹配得到图像的色调图,并将图像分割为多个区域,对每个区域,根据其颜色和形状计算其色调和方向,以此决定铅笔纹理的色调和方向;然后,通过可调整的线性卷积方法得到铅笔画的线条草图;最后,将纹理和草图结合得到铅笔画效果。运用提出的方法对不同类型的自然图像进行了铅笔画的转换,并与已有的线卷积积分方法和基于色调的方法进行了对比。实验结果表明带方向的区域纹理能更好地模拟手工铅笔画纹理的方向,可调整的线条能够更好地模拟手工铅笔画的线条的随意性和灵活性。
    大数据
    基于改进核模糊C均值类间极大化聚类算法
    李斌, 狄岚, 王少华, 于晓瞳
    2016, 36(7):  1981-1987.  DOI: 10.11772/j.issn.1001-9081.2016.07.1981
    摘要 ( )   PDF (886KB) ( )  
    参考文献 | 相关文章 | 计量指标
    传统的核聚类仅考虑了类内元素的关系而忽略了类间的关系,对边界模糊或边界存在噪声点的数据集进行聚类分析时,会造成边界点的误分问题。为解决上述问题,在核模糊C均值(KFCM)聚类算法的基础上提出了一种基于改进核模糊C均值类间极大化聚类(MKFCM)算法。该算法考虑了类内元素和类间元素的联系,引入了高维特征空间的类间极大惩罚项和调控因子,拉大类中心间的距离,使得边界处的样本得到了较好的划分。在各模拟数据集的实验中,该算法在类中心的偏移距离相对其他算法均有明显降低。在人造高斯数据集的实验中,该算法的精度(ACC)、归一化互信息(NMI)、芮氏指标(RI)指标分别提升至0.9132,0.7575,0.9138。
    改进的多数据流协同频繁项集挖掘算法
    王鑫, 刘方爱
    2016, 36(7):  1988-1992.  DOI: 10.11772/j.issn.1001-9081.2016.07.1988
    摘要 ( )   PDF (769KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对已有的多数据流协同频繁项集挖掘算法存在内存占用率高以及发现频繁项集效率低的问题,提出了改进的多数据流协同频繁项集挖掘(MCMD-Stream)算法。首先,该算法利用单遍扫描数据库的字节序列滑动窗口挖掘算法发现数据流中的潜在频繁项集和频繁项集;其次,构建类似频繁模式树(FP-Tree)的压缩频繁模式树(CP-Tree)存储已发现的潜在频繁项集和频繁项集,同时更新CP-Tree树中每个节点生成的对数倾斜时间表中的频繁项计数;最后,通过汇总分析得出在多条数据流中多次出现的且有价值的频繁项集,即协同频繁项集。相比A-Stream和H-Stream算法,MCMD-Stream算法不仅能够提高多数据流中协同频繁项集挖掘的效率,并且还降低了内存空间的使用率。实验结果表明MCMD-Stream算法能够有效地应用于多数据流的协同频繁项集挖掘。
    基于卡方分布的高维数据相似性连接查询算法
    马友忠, 贾世杰, 张永新
    2016, 36(7):  1993-1997.  DOI: 10.11772/j.issn.1001-9081.2016.07.1993
    摘要 ( )   PDF (829KB) ( )  
    参考文献 | 相关文章 | 计量指标
    为了解决高维数据相似性连接查询中存在的维度灾难和计算代价高等问题,基于p-稳态分布,将高维数据映射到低维空间。根据卡方分布的性质,证明了如果低维空间的距离大于,则原始空间距离大于ε的概率具有一定的下界,从而可以在低维空间以较低的计算代价进行有效过滤。在此基础上,提出了基于卡方分布的高维数据相似性连接查询算法。为了进一步提高查询效率,提出了基于双重过滤的高维数据相似性连接查询算法。利用真实数据集进行了实验,实验结果表明所提方法具有较好的性能。基于卡方分布的相似性连接查询算法召回率可以达到90%以上。基于双重过滤的相似性连接查询算法可以进一步提高性能,但是会损失一定的召回率。对时间性能要求比较高、对召回率要求不太严格的查询任务可以采用基于双重过滤的相似性连接查询算法;反之,可以采用基于卡方分布的相似性连接查询算法。
    基于参考节点嵌入的图可达性查询
    温菊屏, 胡小生, 林冬梅, 曾亚光
    2016, 36(7):  1998-2005.  DOI: 10.11772/j.issn.1001-9081.2016.07.1998
    摘要 ( )   PDF (1390KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明:所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。
    基于巴氏系数和Jaccard系数的协同过滤算法
    杨家慧, 刘方爱
    2016, 36(7):  2006-2010.  DOI: 10.11772/j.issn.1001-9081.2016.07.2006
    摘要 ( )   PDF (729KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对传统基于邻域的协同过滤推荐算法存在数据稀疏性及相似性度量只能利用用户共同评分的问题,提出一种基于巴氏系数和Jaccard系数的协同过滤算法(CFBJ)。在项目相似性度量中,该算法引入巴氏系数和Jaccard系数,巴氏系数利用用户所有评分信息克服共同评分的限制,Jaccard系数可以增加相似性度量中共同评分项所占的比重。该算法通过提高项目相似度准确率来选取最近邻,优化了对目标用户的偏好预测和个性化推荐。实验结果表明,该算法比平均值-杰卡德差分(MJD)算法、皮尔森系数(PC)算法、杰卡德均方差(JMSD)算法、PIP算法误差更小,分类准确率更高,有效缓解了用户评分数据稀疏所带来的问题,提高了推荐系统的预测准确率。
    融合时间衰减与偏好波动的协同偏好获取方法
    杨立, 胡运红, 邵桂荣
    2016, 36(7):  2011-2015.  DOI: 10.11772/j.issn.1001-9081.2016.07.2011
    摘要 ( )   PDF (709KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对现有的推荐系统多采用近邻用户的偏好行为来预测当前用户的偏好,而不考虑用户的偏好会随着时间的变化而改变,影响了推荐准确率的问题,提出了一种基于时间衰减与偏好波动的协同偏好获取方法。首先,基于时间因素、用户历史偏好等获取偏好衰减增量与衰减速度,并据此生成衰减函数,使用衰减函数对用户历史行为数据进行衰减修正;其次,基于用户的历史偏好分布获取其偏好波动幅度;最后,将衰减函数与偏好波动幅度分别加入到最近邻获取与偏好获取流程,协同为用户生成推荐列表。在大规模真实数据集上的实验结果表明,所提出的方法与基于属性评分分布的协同过滤(RDCF)与最优Top-N的协同过滤(OTCF)相比,平均绝对误差(MAE)值分别降低了近6.42%和7.73%。实验结果表明所提方法能够提高推荐准确度,提升推荐质量。
    计算机软件技术
    面向嵌套式系统结构的端口自动机行为表达方法
    薛岗, 张云春, 刘笛, 姚绍文
    2016, 36(7):  2016-2020.  DOI: 10.11772/j.issn.1001-9081.2016.07.2016
    摘要 ( )   PDF (847KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对系统多层嵌套式结构范畴模型的动态行为描述与分析问题,提出一种基于端口自动机的行为表达方法(PAM)。该方法基于系统状态、输入和输出端口来定义对象和结构上的运算。通过证明发现:PAM在运算上具有结构保持特征,是一个函子。基于PAM,还就并行、串行和反馈等行为组合,以及应用等相关问题进行了讨论和分析,相关结论表明PAM可被应用于描述或分析具有嵌套式结构的系统动态行为。
    基于版本间克隆映射的演化模式识别及谱系构建
    张久杰, 翟晔, 王春晖, 张丽萍, 刘东升
    2016, 36(7):  2021-2030.  DOI: 10.11772/j.issn.1001-9081.2016.07.2021
    摘要 ( )   PDF (1721KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对当前克隆谱系的构建方法较为复杂、演化模式亟需扩充等问题,提出了新的克隆代码演化模式,并根据软件版本间的克隆代码映射关系自动构建了克隆谱系。首先,针对软件每一版本进行克隆检测并利用潜在狄利克雷分配(LDA)抽取克隆代码的主题信息;然后,根据克隆代码主题的相似度确定版本间克隆代码的映射关系;进而,根据已有的映射关系为克隆代码添加演化模式并分析演化特征;最终,结合映射信息与演化模式信息完成克隆谱系的构建。针对4款开源软件进行了克隆谱系的构建实验,实验结果表明所提克隆谱系构建方法可行,证实了新提出的演化模式在克隆代码演化过程中确实存在。实验发现约90%的克隆代码在软件演化过程中比较稳定,约67%的克隆群经历的发布版本数不超过发布版本总数的一半。实验结论及理论分析将为克隆代码的后续研究及克隆代码的维护与管理提供有力支持。
    基于改进向量空间模型的克隆群映射方法
    陈桌, 张丽萍, 王欢, 张久杰, 王春晖
    2016, 36(7):  2031-2037.  DOI: 10.11772/j.issn.1001-9081.2016.07.2031
    摘要 ( )   PDF (1026KB) ( )  
    参考文献 | 相关文章 | 计量指标
    针对Type-3克隆代码映射方法少且效率低等问题,提出了一种基于改进向量空间模型(VSM)的映射方法。该方法将改进的VSM引入到克隆代码分析中,从而得到一种可有效映射Type-1、Type-2以及Type-3克隆代码的克隆群映射方法。首先,将克隆群文档预处理得到去除无用词的代码文档,同时提取克隆群文档的文件名、函数名等特征项;其次,提取并构建克隆群词频向量空间,利用余弦算法计算出克隆群相似度;然后,通过克隆群相似度和特征项的匹配构建克隆群映射,最终得到克隆群映射结果。对5款开源软件进行实验并人工验证,所提方法能在低时耗的前提下,保证查全率和查准率均不低于96.1%和97.1%。实验结果表明了所提方法的可行性,为后期软件演化分析提供数据支撑。
    行业与领域应用
    群智感知中基于反拍卖模型的众包激励方法
    朱旋, 杨麦顺, 安健, 向乐乐, 杨蔷薇
    2016, 36(7):  2038-2045.  DOI: 10.11772/j.issn.1001-9081.2016.07.2038
    摘要 ( )   PDF (1176KB) ( )  
    参考文献 | 相关文章 | 计量指标
    激励是实现群智感知(CS)众包服务的主要方法,针对现有方法在服务过程中没有充分考虑节点参与数量和恶意竞争对群智感知带来的影响,提出一种基于反拍卖模型的激励(RVA-IM)方法。首先,研究众包的激励机制,结合反拍卖与Vickrey拍卖思想,构建面向任务覆盖的反拍卖模型;其次,对模型中涉及的任务覆盖、反拍卖选择和奖励实施等关键技术问题进行深入分析与研究;最后,从计算有效、个人理性、预算平衡、真实性和诚实性五个方面分析RVA-IM激励方法的有效性。实验结果表明,与IMC-SS和MSensing激励方法相比,RVA-IM在有效性和可行性方面均有较好的表现,能够解决现有方法中的恶意竞争问题,并能够平均提升众包服务完成率约21%。
    基于呼叫详细记录数据的城市功能区识别
    江贵林, 胡访宇, 石立兴
    2016, 36(7):  2046-2050.  DOI: 10.11772/j.issn.1001-9081.2016.07.2046
    摘要 ( )   PDF (782KB) ( )  
    参考文献 | 相关文章 | 计量指标
    不同城市功能区区域之间具有外在物理差异和内在功能差异,且随时间和人类活动不断发生演变。针对卫星遥感等传统监测方法存在运行周期长、成本高,不能表征内在功能差异等问题,利用通信运营商提供的用户生活数据——呼叫详细记录(CDR),进行城市功能区识别研究。首先,以人工标注的方法对基站小区进行功能区分类,得到住宅区、办公区、商业区、高校区、景点区五类训练样本;然后,提取各功能区内用户群体的通话行为和移动行为特征,进行差异性对比分析;最后,利用高斯混合模型(GMM)设计出多特征加权判决的功能区识别算法,并用训练集对该算法进行仿真。实验结果表明,CDR数据可以对城市功能区之间的内在差异进行表征,功能区性质与用户的通话行为和移动行为存在对应关系;判决权重为0.6时,该算法在现有数据集下的功能区召回率达到了最大,为51.08%。结合误差分析表明CDR数据在城市功能区识别应用上具有可行性。
    基于仿生学原理的云资源自主监控系统设计与实现
    孙鹏, 许瀚, 陈晶晶, 曹旭东
    2016, 36(7):  2051-2055.  DOI: 10.11772/j.issn.1001-9081.2016.07.2051
    摘要 ( )   PDF (811KB) ( )  
    参考文献 | 相关文章 | 计量指标
    为了解决现有监控系统因主控节点功能太过集中而导致某些时刻网络流量过大、系统扩展性差和无法及时应对节点失效的问题,提出了一种基于仿生自主神经系统(BANS)的新型云资源监控系统。首先,系统中引入了多级存储、分批上报的机制,将需要上报的监控信息分批次分时段上传汇总,使得在任何单一时刻系统内不会产生过大的流量和负载,保证了系统的稳定性;其次,系统中加入了类动态主机配置协议(DHCP)的主动发现机制以及定期轮询策略,使得系统在处理新节点加入,节点故障问题时,获得了类似仿生自主神经系统一样的自组织、自修复能力。实验结果表明,基于BANS的云资源监控系统实现了自组织与自修复的功能,并且可以有效降低系统内的通信流量,某些单一时刻能将流量降低到仅有原来的三分之一。
    基于开源场景图形的三维可视化与信息管理系统设计
    张文英, 何坤金, 张荣丽, 刘宇兴
    2016, 36(7):  2056-2060.  DOI: 10.11772/j.issn.1001-9081.2016.07.2056
    摘要 ( )   PDF (830KB) ( )  
    参考文献 | 相关文章 | 计量指标
    对于产品虚拟装配的三维呈现过程中难以实现零件信息管理问题,结合电动车模型的拆装,提出三维可视化与信息管理技术融为一体的设计方案。首先,建立三维模型库,并根据电动车模型的拓扑结构和辅助信息,如零件的材质、型号等,建立信息库;其次,读取信息库中零件与子装配体间的父子关系信息建立目录树,根据子装配体与场景树均为“多叉树”组成结构的原理进行子装配体的三维呈现,再对子装配体的各个节点设置动画完成拆装呈现;最后,采用多线程方法将电动车配件信息管理与可视化有机结合,实现支持三维的拾取交互查询和检索定位查询等功能。系统以世纪鸟电动车进行验证,实现了三维可视化技术与信息系统相融合,能快速有效地为电动车的三维呈现和虚拟装配提供技术支持。实例验证表明,所设计系统可以有效地将零件的信息管理融入到虚拟装配的三维可视化中。
2022年 42卷 6期
刊出日期: 2022-06-10
文章目录
过刊浏览
荣誉主编:张景中
主  编:徐宗本
副主编
:申恒涛 夏朝晖

国内邮发代号:62-110
国外发行代号:M4616
地址:四川成都双流区四川天府新区
   兴隆街道科智路1369号
   中科信息(科学城园区) B213
   (计算机应用编辑部)
电话:028-85224283-803
   028-85222239-803
网址:www.joca.cn
E-mail: bjb@joca.cn
期刊微信公众号
CCF扫码入会