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

当期目录

2014年 第51卷 第4期    出版日期:2014-04-15
软件技术
微博数据挖掘研究综述
丁兆云, 贾 焰, 周 斌,
2014, 51(4):  691-706. 
摘要 ( 1914 )   HTML ( 10)   PDF (2806KB) ( 1796 )  
相关文章 | 计量指标
随着近几年微博的快速发展与普及,微博凭借平台的开放性、终端扩展性、内容简洁性和低门槛等特性,在网民中快速渗透,已发展成一个重要的社会化媒体,微博成为网民获取新闻时事、人际交往、自我表达、社会分享以及社会参与的重要媒介以及社会公共舆论的重要平台,对国家安全和社会发展产生了深远的影响.微博是人类在虚拟网络世界生活的抽象概括和延伸,与一般信息网络不同,微博本身具有大规模、噪音数据多样性、快速传播演化性、非线性、社会媒体性以及多关系等特征,因此其在分析方法和挖掘目标上都与传统信息系统具有很大差别,在相关技术的研究上也带来了更大的挑战.针对微博的新特性,研究了微博近几年的相关研究现状,同时分析了Twitter数据集特征,且总结了未来研究面临的挑战.
人工智能
在大规模数据集上进行快速自适应同步聚类
应文豪, 许 敏, 王士同, 邓赵红,
2014, 51(4):  707-720. 
摘要 ( 706 )   HTML ( 0)   PDF (4024KB) ( 653 )  
相关文章 | 计量指标
现有的同步聚类方法Sync在同步过程中需要将样本中的每一个分量看作相位振子进行计算,具有较高的时间复杂度,因此在大规模数据集上聚类时具有相当大的局限性.为了解决这一问题,提出了快速自适应同步聚类方法(fast adaptive KDEbased clustering by synchronization, FAKCS).FAKCS首先引入基于压缩集密度估计和中心约束最小包含球技术的快速压缩方法对大规模数据集进行压缩,然后通过使用DaviesBouldin指标,在压缩集上进行ε参数自适应的同步聚类,并采用新定义的序列参量来评价局部同步的程度.另外,研究了序列参量和核密度估计间的联系,从理论上揭示了样本点的局部同步在概率密度意义下的本质.FAKCS可以在大规模数据集上得到任意形状、个数、密度的聚类而无需预设聚类数目.在图像分割和大规模UCI数据集上的实验验证了FAKCS的有效性.
基于Bayesian学习的适应性优化协商模型
侯 薇, 董红斌, 印桂生,
2014, 51(4):  721-730. 
摘要 ( 611 )   HTML ( 0)   PDF (2177KB) ( 434 )  
相关文章 | 计量指标
在复杂的自动协商环境中,设计能够处理不完全信息和动态情形的协商agent有效学习机制正成为具有挑战性的议题.提出了一种基于Bayesian学习的时间依赖的双边多议题协商优化模型(BLMSEAN).通过只观察对手的历史报价,将Bayesian学习和基于混合策略的演化算法相结合,所提模型使得协商agent能够对于对手协商参数的概率分布有更精确的估计(如期限、保留报价和议题权重等),能够适应性地调整让步策略使协商双方都受益,提高了协商的成功率和效用.通过实验可以显示所提的模型学习对手私有信息和适应性调整让步策略的有效性.
一种基于混合模型的数据流概念漂移检测算法
郭躬德 李 南 陈黎飞
2014, 51(4):  731-742. 
摘要 ( 739 )   HTML ( 2)   PDF (3316KB) ( 523 )  
相关文章 | 计量指标
由于在信用卡欺诈分析等领域的广泛应用,学者们开始关注概念漂移数据流分类问题.现有算法通常假设数据一旦分类后类标已知,利用所有待分类实例的真实类别来检测数据流是否发生概念漂移以及调整分类模型.然而,由于标记实例需要耗费大量的时间和精力,该解决方案在实际应用中无法实现.据此,提出一种基于KNNModel和增量贝叶斯的概念漂移检测算法KnnM-IB.新算法在具有KNNModel算法分类被模型簇覆盖的实例分类精度高、速度快优点的同时,利用增量贝叶斯算法对难处理样本进行分类,从而保证了分类效果.算法同时利用可变滑动窗口大小的变化以及主动学习标记的少量样本进行概念漂移检测.当数据流稳定时,半监督学习被用于扩大标记实例的数量以对模型进行更新,因而更符合实际应用的要求.实验结果表明,该方法能够在对数据流进行有效分类的同时检测数据流概念漂移及相应地更新模型.
基于量子精英蛙的最小属性自适应合作型协同约简算法
丁卫平, 王建东, 管致锦,
2014, 51(4):  743-753. 
摘要 ( 521 )   HTML ( 1)   PDF (2581KB) ( 446 )  
相关文章 | 计量指标
属性约简是粗糙集理论研究的重要内容之一,现已证明求决策表的最小属性约简是一个典型NP-Hard问题.提出一种基于量子精英蛙的最小属性自适应合作型协同约简算法.该算法首先将进化蛙群编码为多状态量子染色体形式,利用量子精英蛙快速引导进化蛙群进入最优化区域寻优,有效增强进化蛙群的收敛速度和全局搜索能力.然后构建一种自适应合作型协同进化的最小属性约简模型,融合蛙群最优执行经验和分配信任度自适应分割属性约简集,并以模因组内最优精英蛙优化各自选择的属性子集,提高属性约简的协同性和高效性,快速找到全局最小属性约简集.实验研究表明提出的算法在搜索最小属性约简解时具有较高的执行效率和精度.
二元进化策略的全局收敛与早熟收敛
张宇山, 郝志峰, 黄 翰,
2014, 51(4):  754-761. 
摘要 ( 435 )   HTML ( 0)   PDF (1009KB) ( 420 )  
相关文章 | 计量指标
离散状态马尔科夫链理论已经广泛应用于进化算法的收敛性和时间复杂度分析中,而连续状态马尔科夫过程理论由于需要用到比较高深的数学工具,应用还不多.引入连续状态马尔科夫过程理论,以测度论为工具,借助公理化的条件数学期望理论推导出关键的转移概率的计算公式,分析了以(1+1)ES为代表的连续型进化算法的收敛性,从理论上证明若采用常变异算子,包括正态分布、柯西分布在内的一大类常用变异分布可使(1+1)ES依概率收敛到全局最优解的ε-邻域;构造了一个带适应值平台的函数,从理论上证明某些自适应变异算子即使以正态分布、柯西分布为变异分布也会导致(1+1)ES陷入早熟收敛.通过仿真实验验证了理论分析.结果表明自适应调整机制并非总是有效的.
基于消失点和主方向估计的道路分割算法
田 峥, 徐 成, 米 超, 李仁发, 王晓栋,
2014, 51(4):  762-772. 
摘要 ( 573 )   HTML ( 0)   PDF (3931KB) ( 686 )  
相关文章 | 计量指标
现有基于消失点估计的道路分割算法要求消失点位于图像内部,并且算法计算复杂度高,难以排除局部纹理特征较强的干扰点.针对这些问题,提出一种基于道路主方向的消失点估计和道路分割算法.首先根据道路主方向的定义对有效投票点进行筛选,然后提出一种多维投票策略,记录待定消失点在各纹理方向的投票信息,并运用该信息判断消失点是否在图像内;最后提出基于道路主方向的边界拟合策略,利用多维投票数据来进行道路边界提取.主观评价和量化分析表明,与经典算法相比,所提算法具有更好的精确度和执行速度,并且当消失点位于图像外部时算法仍有较好的分割效果.
基于fMRI的思维数据分析方法研究
邓红霞, 相 洁, 游 雅, 李海芳,
2014, 51(4):  773-780. 
摘要 ( 884 )   HTML ( 0)   PDF (3678KB) ( 486 )  
相关文章 | 计量指标
利用功能磁共振成像(functional magnetic resonance imaging, fMRI)技术解读思维数据,已经实现大脑活动的功能定位,但是大脑的思维过程具体如何运行还不得而知;利用何种分析方法更能揭示思维过程也待进一步研究.采用解决4×4数独问题和图像情感反应的两种刺激任务获取思维过程数据,来分别解读不同的思维状态,探索适用于不同思维数据的分析方法.实验数据证明t-test的特征选择方法、峰值所在时间点的特征提取的方法和SVM分类算法较适用于分析这两种不同思维状态的fMRI数据,揭示正确的思维状态.
时间序列异常点及突变点的检测算法
苏卫星, 朱云龙, 刘 芳, 胡琨元,
2014, 51(4):  781-788. 
摘要 ( 3631 )   HTML ( 18)   PDF (2315KB) ( 3432 )  
相关文章 | 计量指标
针对传统突变点检测算法具有大延时的问题以及实际数据中同时含有突变点、异常点的实际情况,提出一种基于小波变换有效分数向量的异常点、突变点检测算法.该方法通过引入有效分数向量作为检测统计量,有效避免了传统检测统计量随着数据增多而无限增大的缺点;提出利用小波分析统计量的办法,有效地克服了传统突变点检测算法中存在大延时的缺陷;利用李氏指数及小波变换的关系,实现了在一个检测框架内同时在线检测异常点以及突变点,使得该检测算法更符合突变点及异常点同时存在的实际情况.仿真实验和性能比较结果证明了提出的异常点、突变点检测算法具有一定的有效性和实用性.
基于仿生模式识别的用户概貌攻击集成检测方法
周全强 张付志
2014, 51(4):  789-801. 
摘要 ( 505 )   HTML ( 1)   PDF (3719KB) ( 466 )  
相关文章 | 计量指标
针对有监督方法在检测用户概貌攻击时准确率不高的问题,通过引入仿生模式识别理论和集成学习技术提出一种集成检测方法.首先,通过计算被覆盖直线段与最近邻真实概貌的距离,提出一种自适应神经元超球半径计算算法,为每个神经元确定合适的超球半径;然后利用该超球半径对现有的一个3层神经网络进行重新设计,使其能够对攻击概貌样本进行更合理覆盖,以提高分类性能;最后,提出一种用户概貌攻击集成检测框架,通过组合多种攻击类型,利用提出的基训练集生成算法建立不同的基训练集,以训练新设计的神经网络生成基分类器,基于信息论得分(information theoretic score, ITS)算法提出一种选择性集成检测算法对基分类器进行筛选,并采用多数投票策略融合基分类器的输出结果.在MovieLens和Netflix两个不同规模的真实数据集上的实验结果表明,所提出的集成检测方法能够在保持较高召回率的条件下有效提高用户概貌攻击检测的准确率.
图形图像
一种鲁棒高精度的人脸三维运动跟踪算法
於 俊, 汪增福,
2014, 51(4):  802-812. 
摘要 ( 621 )   HTML ( 1372)   PDF (3232KB) ( 442 )  
相关文章 | 计量指标
提出了一种在粒子滤波框架下的结合在线外观模型(online appearance model, OAM)和柱状人头模型(cylinder head model, CHM)的人脸三维运动跟踪方案,具体包括:1)融合多种观测信息来降低OAM的光照敏感性和个体相关性;2)针对OAM适合跟踪局部运动但在大姿态下会跟踪失败的问题,将OAM与适合于大姿态下全局运动跟踪的CHM结合起来,在当前帧将CHM匹配得到的全局运动参数作为OAM匹配的初始值,将OAM匹配得到的人脸运动参数作为下一帧CHM匹配的初始值;3)基于局部优化和改进重采样来改进粒子运动滤波策略.实验表明:该系统在大姿态、表情剧烈变化、遮挡和强光照下能得到较好的跟踪效果,且OAM+CHM的跟踪正确率高于OAM的24%,OAM+CHM的姿态跟踪范围大于OAM的11%.主观实验表明:由跟踪得到的人脸运动参数合成的虚拟人脸具有较高的辨识度.
基于动态遮挡阈值的多视角多目标协作追踪
周良毅, 王 智, 王营冠,
2014, 51(4):  813-823. 
摘要 ( 704 )   HTML ( 1)   PDF (3159KB) ( 469 )  
相关文章 | 计量指标
多移动目标相互运动过程中产生的相互遮挡造成目标间的复杂空间关系,为视觉传感器网络的多目标信息融合、协同处理和协作追踪带来困难,提出动态遮挡阈值的多视角多目标协作追踪的多视角多目标协同追踪算法.为克服多视觉传感器中的信息融合及目标一致性表征问题,在基于贝叶斯理论的多视角移动追踪中引入遮挡变量,来描述多目标间的空间关系;通过分析不同视角包含的目标信息量及其对于融合的贡献,给出了遮挡阈值的动态表达式;通过动态调整和比较遮挡阈值来判断目标间的遮挡状态,改进了目标遮挡的判决标准和公共平面中的目标融合特征;并通过结合改进粒子滤波得到基于遮挡变量的多视角目标协作追踪算法,保证了追踪系统的稳定性.实验结果表明,引入遮挡变量以及动态遮挡阈值有效解决了传统追踪算法中的目标不一致性、尺寸变化等难题,提高了目标追踪精度,在目标被遮挡的情况下仍然能够保持良好的追踪效果.
软件技术
基于粒子群优化的测试数据生成及其实证分析
毛澄映, 喻新欣, 薛云志,
2014, 51(4):  824-837. 
摘要 ( 789 )   HTML ( 1)   PDF (6472KB) ( 656 )  
相关文章 | 计量指标
运用元启发式搜索进行结构性测试数据生成已经被证实是一种有效的方法.在讨论基于搜索的测试数据生成基本框架的基础上,以分支覆盖作为测试覆盖准则,给出了基于粒子群优化(particle swarm optimization, PSO)的测试数据生成算法,并通过分析分支谓词的结构特征提出了一种新的适应函数构造形式.在此基础上,针对一些公开的程序集开展对比性实验分析,证实粒子群优化算法在平均覆盖率、全覆盖成功率、平均收敛代数和搜索时间4项指标上均要优于遗传算法和模拟退火算法.同时,编程实现了4种典型的PSO变体算法并进行测试数据生成效果的实证分析,结果表明:基本PSO是解决测试数据生成问题的首选算法,而综合学习式PSO算法的表现则相对较差.
BPEL谓词约束建模及可行路径分析
王 进, 黄志球, 唐佳俊, 陈 哲, 肖芳雄,
2014, 51(4):  838-847. 
摘要 ( 473 )   HTML ( 1)   PDF (2451KB) ( 392 )  
相关文章 | 计量指标
为了解决由于缺乏谓词约束表达式的建模和分析带来的业务流程执行语言(business process execution language, BPEL)中路径分析不准确问题,提出了一种针对BPEL中XPath表达式的谓词约束分析和建模方法,并在此基础上提出了BPEL可行路径的分析算法.与以往BPEL建模中大多仅考虑结构化行为不同,该方法系统分析了数据封装对执行路径的影响.该方法综合考虑BPEL中表达式的语法结构以及结构化活动对BPEL中变量的影响,采用扩展行为影响的变量结构树对BPEL中原子数据表达式进行建模,并进一步考虑了复合谓词表达式的建模和基于此模型的BPEL可行路径分析方法.最后,结合案例分析了该方法的可行性.
一种嵌入式实时系统软件能耗建模与分析的方法
祝 义, 肖芳雄, 周 航, 张广泉,
2014, 51(4):  848-855. 
摘要 ( 597 )   HTML ( 1)   PDF (1306KB) ( 607 )  
相关文章 | 计量指标
随着嵌入式实时系统低能耗研究的不断深入,软件能耗已经成为影响系统的主要因素,并朝着定量分析方向发展.针对嵌入式实时系统缺乏有效的软件能耗建模与分析的方法,提出一种基于进程代数的嵌入式实时系统软件能耗建模与分析的方法.通过在时间通信顺序进程上扩展价格信息得到价格时间通信顺序进程,将嵌入式实时系统指令的功耗映射成价格时间通信顺序进程的价格,利用价格时间通信顺序进程对嵌入式实时系统软件能耗建模并进行量化分析,提出的最优路径算法可以对建模结果进行指令功耗可满足性检查,并计算当前最低能耗可达路径.该方法可以从很大程度上提高嵌入式实时系统软件能耗计算和分析的准确性,计算结果有助于嵌入式实时系统软件能耗的量化分析和优化设计.
Radl算法到Apla程序的生成系统
谢武平 薛锦云
2014, 51(4):  856-864. 
摘要 ( 480 )   HTML ( 1)   PDF (1601KB) ( 453 )  
相关文章 | 计量指标
算法设计是一项创造性工作,传统的设计与描述方法难以保证算法的正确性.在PAR方法中通过定义具有数学引用透明性的算法描述语言Radl,可实现对问题规约进行形式化推导得到用递推关系描述的算法.Radl算法的核心就是递推关系组,从而易于进行形式化推导和证明.通过深入剖析Radl算法特性,揭示Radl算法与抽象顺序程序Apla(abstract programming language)间本质关系,定义基于Radl语法产生式的Apla程序生成规则,实现了Apla程序自动生成系统,并对其可靠性进行系统研究,着重形式化验证了实现系统的核心算法.使用PAR方法开发的算法是正确的,采用形式化证明的生成系统具有可靠性保证,从而保证了算法从设计到实现的高可靠性,并通过实现自动化开发工具提高了程序的开发效率.
面向有效错误定位的测试用例优选方法
王克朝, 王甜甜, 苏小红, 马培军, 童志祥,
2014, 51(4):  865-873. 
摘要 ( 488 )   HTML ( 1)   PDF (2039KB) ( 502 )  
相关文章 | 计量指标
针对已有测试用例选择方法在提高错误定位有效性方面存在局限性的问题,首先,定义“失效覆盖向量相似度优先排序”准则,将执行路径与失效执行路径相似的成功测试用例赋予较高的优先级;然后定义“失效覆盖等价划分优化选择”准则,选择能够最大区分失效执行语句的成功测试用例集合;在此基础上,建立测试用例优选模型(effective selection, ES).不同于已有方法,ES充分利用失效执行路径来提高错误定位的有效性.该模型被应用于优选Siemens测试用例集合,其结果被应用于Tarantula等4种错误定位方法.结果表明,ES在约简率Reduction和衡量错误定位有效性的Expense_increase两个指标方面,均优于已有的基于语句和基于向量的测试用例约简方法.ES不但可以获得97%以上的约简率,提高错误定位的效率,而且具有较低的Expense_increase,显著提高了错误定位的有效性.
MujavaX: 一个支持非均匀分布的变异生成系统
孙昌爱, 王 冠,
2014, 51(4):  874-881. 
摘要 ( 529 )   HTML ( 0)   PDF (1578KB) ( 504 )  
相关文章 | 计量指标
变异分析是一种广泛用来评估软件测试技术性能的方法.已有的变异分析技术通常将变异算子平均地应用于原始程序.由于现实程序中的故障分布往往具有群束的特征,采用平均分布的变异分析方法不能客观地评估软件测试技术的性能.前期研究工作中提出了非均匀分布的变异分析方法,采用实例研究验证了不同的故障分布对测试技术性能评估的影响.为了增强非均匀分布的变异分析方法的实用性,开发了支持非均匀分布的变异生成系统MujavaX,该系统是对广泛实践的Mujava工具的扩展与改进.采用一个实例系统验证了开发的MujavaX的正确性与可行性,实验结果表明该系统能够生成指定分布的非均匀变体集合.
选择稀疏矩阵乘法最优存储格式的研究
李佳佳, 张秀霞, 谭光明, 陈明宇,
2014, 51(4):  882-894. 
摘要 ( 778 )   HTML ( 1)   PDF (4134KB) ( 853 )  
相关文章 | 计量指标
稀疏矩阵向量乘法(sparse matrix vector multiplication, SpMV)是科学和工程领域中重要的核心子程序之一,也是稀疏基本线性代数子程序(basic linear algebra subprograms, BLAS)库的重要函数.目前很多SpMV的优化工作在不同程度上获得了性能提升,但大多数优化工作针对特定存储格式或一类具有特定特征的稀疏矩阵缺乏通用性.因此高性能的SpMV实现并没有广泛地应用于实际应用和数值解法器中.另外,稀疏矩阵具有众多存储格式,不同存储格式的SpMV存在较大性能差异.根据以上现象,提出一个SpMV的自动调优器(SpMV auto-tuner, SMAT).对于一个给定的稀疏矩阵,SMAT结合矩阵特征选择并返回其最优的存储格式.应用程序通过调用SMAT来得到合适的存储格式,从而获得性能提升,同时随着SMAT中存储格式的扩展,更多的SpMV优化工作可以将性能优势在实际应用中发挥作用.使用佛罗里达大学的2366个稀疏矩阵作为测试集,在Intel上SMAT分别获得9.11GFLOPS(单精度)和2.44GFLOPS(双精度)的最高浮点性能,在AMD平台上获得了3.36GFLOPS(单精度)和1.52GFLOPS(双精度)的最高浮点性能.相比Intel的核心数学函数库(math kernel library, MKL)数学库,SMAT平均获得1.4~1.5倍的性能提升.
异构信息空间中实体关联关系挖掘算法CFRQ4A
杨 丹, 申德荣, 聂铁铮, 于 戈, 寇 月,
2014, 51(4):  895-904. 
摘要 ( 642 )   HTML ( 0)   PDF (2341KB) ( 452 )  
相关文章 | 计量指标
丰富的实体关联关系是在异构信息空间中进行数据分析、数据挖掘、知识发现和语义查询等许多应用的前提条件和关键所在.然而不同于同构信息网络,由于异构信息空间中实体关联关系的复杂性、多样性和异构性使得实体关联关系挖掘并不是一件简单的任务,更具有挑战性.以作者文献网络为例,提出了一个通用的,由聚类、过滤、推理和量化4步骤组成的异构信息空间中基于聚类的实体关联关系挖掘算法CFRQ4A(clustering,filtering,reasoning and qualifying for associations).CFRQ4A算法不仅利用了异构实体自身的属性值,还利用了异构信息网络的结构(路径)信息;在挖掘过程中引入关联关系约束来保证关联关系的语义和逻辑正确性,并且针对实体关联关系的特点提出了关联强度量化模型.在真实数据集DBLP上的实验结果表明所提出算法是可行和有效的.
面向混合类型关键词查询的非合作结构化深网数据源选择
万常选 邓 松 刘德喜 江腾蛟 刘喜平
2014, 51(4):  905-917. 
摘要 ( 337 )   HTML ( 0)   PDF (2787KB) ( 442 )  
相关文章 | 计量指标
为有效地利用深网中的资源,深网集成应运而生.为了提高深网集成的效率和返回结果的质量,数据源选择成为深网集成的关键技术.深网数据源大多数是结构化和非合作型的.当前已有的非合作结构化深网数据源选择的研究分为2类:一类是面向离散型关键词查询的源选择;另一类是面向字符型关键词查询的源选择,而未见面向混合类型关键词查询的结构化数据源选择的相关研究.基于此,将用户查询关键词分为检索型关键词和约束型关键词,基于主题词与主题词、主题词与特征词和直方图与直方图的关联特征构建了面向检索型、约束型混合关键词查询的层次化数据源摘要,有效地反映了非合作结构化深网数据源选择中检索型关键词的检索意图和约束型关键词的约束相关性,并依据此摘要给出了相应的数据源选择策略.实验结果表明,该方法在面向混合类型关键词查询的非合作结构化深网数据源选择时具有较好的记录召回率及准确率.
基于关系数据库的top-k聚合关键词查询
张东站 苏志锋 林子雨 薛永生
2014, 51(4):  918-929. 
摘要 ( 670 )   HTML ( 0)   PDF (2922KB) ( 476 )  
相关文章 | 计量指标
基于关系数据库的关键词查询,使得用户在不需要掌握结构化查询语言和数据库模式的情况下,可以方便地进行关系数据库查询.给定一个关键词查询,已有的方法通过数据库中的主外键关联,查询得到包含关键词的元组集合.但是,在很多实际应用中,元组集合的聚合结果对用户更有价值;研究了基于关系数据库的top-k聚合关键词查询,提出了基于递归的聚合单元枚举算法——基于递归的完全搜索(recursion-based full search, RFS).为了获得更好的查询性能,设计了新的排序方法、二维索引和快速搜索算法——基于输出的快速搜索(output-based quick search, OQS),从而可以高效地枚举top-k个聚合单元;在不同的数据集上进行了大量的实验,实验结果表明OQS算法具有良好的查询性能.