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

当期目录

2008年 第45卷 第11期    出版日期:2008-11-15
论文
广义超球面SVM研究
张新峰 刘垚巍
2008, 45(11):  1807-1816. 
摘要 ( 424 )   HTML ( 0)   PDF (907KB) ( 404 )  
相关文章 | 计量指标
超球面支撑向量机是不均衡样本分类的一种重要方法.然而,目前引入间隔的超球面支撑向量机中,当一类样本集中不存在支撑向量时,两类样本之间的间隔解是不确定的;在两类样本均存在正常支撑向量的情况下,两类样本之间的间隔为零.间隔不确定或为零在很大程度上影响分类器的推广性能.为此提出了一种广义的超球面支撑向量机算法,通过引入参数n和b,理论推导得出n>b,这样可以保证获得不为零的间隔解.理论分析和实验结果表明,所提供算法在具有较小经验风险的同时,可获得较好的推广性能.
一种直推式多标记文档分类方法
姜 远 佘俏俏 黎 铭 周志华
2008, 45(11):  1817-1823. 
摘要 ( 595 )   HTML ( 0)   PDF (751KB) ( 554 )  
相关文章 | 计量指标
真实世界的文档往往同时属于多个类别,因此,利用多标记学习技术进行文档分类是一个重要的研究方向. 现有多标记文档分类方法需要利用大量有正确分类标记的文档才能获得好的分类性能,然而,在实际应用中往往只能得到少量的有标记文档作为分类所需的训练文档. 出于利用未标记文档的想法,提出一种基于随机游走的直推式多标记文档分类方法,可以利用大量的未标记文档来辅助提高分类性能. 实验结果表明,该方法的性能优于现有直推式多标记分类方法CNMF.
一种基于启发式轮廓表的逻辑强化学习方法
刘 全, 高 阳, 陈道蓄, 孙吉贵, 姚望舒,
2008, 45(11):  1824-1830. 
摘要 ( 595 )   HTML ( 1)   PDF (907KB) ( 446 )  
相关文章 | 计量指标
强化学习通过试错与环境交互获得策略的改进,其自学习和在线学习的特点使其成为机器学习研究的一个重要分支.针对强化学习一直被“维数灾”问题所困扰的问题,提出在关系强化学习的基础上,引入启发式轮廓表的方法,采用含轮廓表的一阶谓词表示状态、活动和Q-函数,充分发挥Prolog表的优势,将逻辑谓词规则与强化学习相结合,形成一种新的逻辑强化学习方法——CCLORRL,并对其收敛性进行了证明.该方法使用轮廓形状谓词产生形状状态表,大幅度地减少状态空间;利用启发式规则指导动作的选择,减少了样本中不存在状态选择的盲目性.CCLORRL算法应用于俄罗斯方块中,实验表明,该方法是比较高效的.
自组织分治求解分布式约束优化问题
黄 晶 刘大有 杨 博 金 弟
2008, 45(11):  1831-1839. 
摘要 ( 526 )   HTML ( 1)   PDF (916KB) ( 382 )  
相关文章 | 计量指标
分布式约束优化问题(DCOP)是在大规模、开放、动态网络环境中的优化问题,在计算网格、多媒体网络、电子商务、企业资源规划等领域中都有广泛应用.除了具有传统优化问题的非线性、约束性等特点,DCOP还具有动态演化、信息区域化、控制局部化、网络状态异步更新等特点.寻求一种解决DCOP的大规模、并行、具有智能特征的求解方法已成为一个具有挑战性的研究课题.目前已提出多种求解DCOP的算法,但大多不是完全分散的算法,存在集中环节,需要网络的全局结构作为输入,不适合处理由规模巨大、地理分布、控制分散等因素导致的全局结构难以获取的分布式网络.针对该问题,提出一个基于自组织行为的分治策略求解DCOP.在不具有全局网络知识的情况下,分布在网络中的多个自治Agent基于局部感知信息、采用自组织的方式协作求解.与已有算法相比,它是一个完全分散式算法,并在求解效率和求解质量方面都展现出很好的性能.
基于问题结构的启发式策略在析取时态问题求解中的应用
刘越畅 姜云飞 钱 红
2008, 45(11):  1840-1849. 
摘要 ( 381 )   HTML ( 0)   PDF (1845KB) ( 443 )  
相关文章 | 计量指标
智能规划和调度中的许多时态(或时序)问题可以表达为析取时态问题(DTP).目前,多数析取时态问题求解器将析取时态问题看作约束可满足问题(CSP)或可满足问题(SAT),并使用标准的CSP(或SAT)技术来求解DTP.虽然这些技术在求解DTP时已经可以达到较好的效率,然而,文献中极少研究者关注利用DTP本身特殊的结构中隐含的信息来帮助DTP求解.尝试从DTP的拓扑结构中提取出一种启发式策略.这种启发式策略试图从DTP的结构中提取出定性和定量的标准(TVS)来选择优先赋给当前变量的值,同时基于这种定量值选择标准设计了一个动态变量选择策略(TVO).这种技术基于定义的一种DTP的图模型——析取时态网络(DTN).实验结果显示TVS和TVO策略均可以有效减小搜索中节点访问次数;同时它与已有的RSV值选择策略效果相当,而TVO优于最少剩余值(MRV)方法(节省一个数量级以上的访问节点数);此外,配合其他CSP启发技术,可以得到一个高效的DTP求解算法DTN-DTP.
进化规划算法的时间复杂度分析
黄 翰, 郝志峰, 秦 勇,
2008, 45(11):  1850-1857. 
摘要 ( 627 )   HTML ( 0)   PDF (777KB) ( 599 )  
相关文章 | 计量指标
进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov过程模型,以期望收敛时间作为研究进化规划算法时间复杂度的指标,提出了进化规划算法期望收敛时间的估算方法,并以此作为算法时间复杂度分析的理论依据.最后分析了Gauss变异进化规划算法的期望收敛时间,作为提出理论的应用举例.
增强型单类支持向量机
冯爱民, 薛 晖, 刘学军, 陈松灿, 杨 明,
2008, 45(11):  1858-1864. 
摘要 ( 678 )   HTML ( 0)   PDF (924KB) ( 648 )  
相关文章 | 计量指标
现有基于超平面的单类分类器,包括one-class SVM(OCSVM)和马氏one-class SVM(MOCSVM),由于未考虑数据的结构信息或粒度较粗,寻找的超平面很可能是次优解.为此,增强型单类支持向量机(enhanced OCSVM, EnOCSVM)通过在现有SVM算法中加入数据先验信息以克服其不足.首先,EnOCSVM通过聚类得到数据的内在分布簇,而后将各簇结构信息嵌入到OCSVM框架中,最大化间隔的同时,优化输出空间中各簇数据的紧性.由于保留了SVM框架不变,EnOCSVM仍具备原算法的全部优点,并因结合了数据的簇结构信息而具有更好的推广性.标准数据集上的实验表明,EnOCSVM的推广性能较OCSVM和MOCSVM均有显著提高.
联合聚类非线性相关的时序基因表达数据
闫雷鸣 孙志挥 吴英杰 张柏礼
2008, 45(11):  1865-1873. 
摘要 ( 755 )   HTML ( 1)   PDF (933KB) ( 505 )  
相关文章 | 计量指标
为聚类非线性相关的数据对象,引入广义信息论中二次互信息作为相似性度量,利用矩阵理论降低了二次互信息的计算量,并结合滑动窗口技术,建立了一种时序数据非线性相关模型.在此基础上提出了适用于时序基因表达数据的确定性联合聚类算法MI-TSB.该算法将时序数据转化为抽象字符序列,然后插入到MI-泛化后缀树中,避免了穷举各种组合,从而快速索引全部聚类结果.实验结果显示MI-TSB算法具有良好的运行性能,成功聚类出非线性相关的对象;利用Gene Ontology对聚类结果进行基因注释,也验证了聚类结果的生物学意义.
一种结合独立性模型与差异评估的Co-Training改进方案
唐焕玲, 林正奎, 鲁明羽, 邬 俊,
2008, 45(11):  1874-1881. 
摘要 ( 451 )   HTML ( 1)   PDF (744KB) ( 396 )  
相关文章 | 计量指标
Co-Training算法要求两个特征视图满足一致性和独立性,但是,许多应用中不存在自然划分且满足这种假设的两个视图.为此,提出利用互信息(MI)或者CHI统计量评估特征之间的相互独立性,建立特征相互独立性模型(MID-Model).基于该模型,提出了新的特征子集划分方法PMID-MI与PMID-CHI算法,能有效地将一个特征集合划分成两个独立性较强的子集.并且利用多种差异评估法,进一步验证两个子集的独立性.基分类器之间的差异性能够减少两个基分类器给同一个未标注文本都标注错误的可能性.最后,提出了对Co-Training的改进算法SC-PMID.实验结果表明SC-PMID算法能够明显提高半监督分类精度.
基于动态贝叶斯网络的连续语音识别框架及其Token传递模型
苗夺谦 王睿智 冉 巍
2008, 45(11):  1882-1891. 
摘要 ( 760 )   HTML ( 0)   PDF (1467KB) ( 503 )  
相关文章 | 计量指标
近年来,由于动态贝叶斯网络(DBN)相对于传统的隐马尔可夫模型(HMM)更具可解释性、可分解性以及可扩展性,基于DBN的语音识别引起学者们越来越多的关注.但是,目前关于基于DBN的语音识别的研究主要集中在孤立语音识别上,连续语音识别的框架和识别算法还远没有HMM成熟和灵活.为了解决基于DBN的连续语音识别的灵活性和可扩展性,将在基于HMM的连续语音识别中很好地解决了上述问题的Token传递模型加以修改,使之适用于DBN.在该模型基础上,为基于DBN的连续语音识别提出了一个基本框架,并在此框架下提出了一个新的独立于上层语言模型的识别算法.还介绍了作者开发的一套基于该框架的可用于连续语音识别及其他时序系统的工具包DTK.
自适应多Agent系统的面向Agent软件开发方法学ODAM
毛新军 屈婷婷 王 戟
2008, 45(11):  1892-1901. 
摘要 ( 481 )   HTML ( 0)   PDF (1515KB) ( 498 )  
相关文章 | 计量指标
面向Agent软件工程被视为是一种可有效支持复杂系统开发的新颖软件开发范型.为支持复杂多Agent系统的开发,面向Agent软件工程的研究需发挥Agent技术的潜力和灵活性,借鉴软件工程领域已取得的成果,提出了一个面向Agent软件开发方法学ODAM以支持自适应多Agent系统的开发.ODAM以动态绑定机制作为自适应多Agent系统的核心机制,借助于组织学的概念和思想对自适应多Agent系统进行高层抽象和自然建模,以管理和控制系统的复杂度;集成了迭代开发和MDA方法以适应Agent技术平台的多样性,简化复杂自适应系统的开发.介绍了ODAM的方法学框架和具体的技术细节,包括动态绑定机制、基于组织抽象的元模型和建模语言、基于迭代开发和MDA的软件开发过程,并进行了案例分析.
一种基于上下文协商的动态服务组合方法
唐 磊, 淮晓永, 李明树,
2008, 45(11):  1902-1910. 
摘要 ( 366 )   HTML ( 0)   PDF (1222KB) ( 384 )  
相关文章 | 计量指标
普适计算的计算环境和交互信息动态变化,为了提供适时适地的服务,服务组合除了满足用户的需求之外,还要适应环境的变化.以面向普适计算的分布式文档管理系统为例,提出一种基于上下文协商的动态服务组合方法,适应普适计算环境下资源动态变化的特点,同时满足用户对服务的需求.首先定义上下文和带有上下文信息的服务模型;然后给出服务和设备以及服务和用户之间的上下文协商约束条件,根据约束条件提出基本算法实现服务动态组合,并对基本算法进行优化;最后通过原型系统和实验验证算法的性能和有效性,并通过实验数据分析上下文对于服务组合的影响.实验数据说明:提出的方法能够应用在普适计算环境中上下文敏感的服务组合问题上,提高服务组合的动态适应性和网络资源利用率.
基于遗传规划的行为模型精化方法
王帅强 马 军 王海洋 万建成
2008, 45(11):  1911-1919. 
摘要 ( 376 )   HTML ( 2)   PDF (1014KB) ( 453 )  
相关文章 | 计量指标
行为模型的精化是软件工程中的基于模型驱动开发的关键问题.基于针对环境的形式化行为模型和形式化方法中的精化理论,提出了一种基于遗传规划的行为模型的自动精化方法.该方法将精化看作可执行的基本操作的组合过程.首先通过分析抽象行为的后置条件公式,执行基于逻辑归约的精化方法,从而生成循环结构和其他简单新行为的描述.然后利用基于遗传规划的精化方法对新行为继续精化,直到产生的程序最终由基本操作构成.由于传统的遗传规划方法对选择结构难以演化,提出了组合终止条件的概念.通过测试组合终止条件,选择结构也能较好的产生.最后以排序问题为例,给出实际的演化过程,结果说明该方法具有较强的可行性.事实上该方法适用于任何由若干基本操作组合以完成复杂操作的问题求解过程.
基于动态网格划分的移动无线传感器网络定位算法
魏叶华 李仁发 罗 娟 陈洪龙
2008, 45(11):  1920-1927. 
摘要 ( 482 )   HTML ( 0)   PDF (1170KB) ( 536 )  
相关文章 | 计量指标
定位技术是无线传感器网络中关键的基础支撑技术,目前提出了许多静态网络的节点定位算法,移动无线传感器网络的定位研究相对较少.针对定位节点和参考节点随机运动的网络模型,提出了一个基于动态网格划分的蒙特卡罗定位算法.算法中当接收的参考节点数超过一定阈值时使用最远距离节点选择模型,选出部分参考节点参与定位和信息转发,节约能耗.接着基于选择的或所有接收的参考节点构建采样区域,进行网格划分,使用网格单元数计算最大采样次数,在采样区域内采样并使用误差补偿的运动模型进行过滤,提高了采样效率,减少了计算开销,并保证了较好的定位精度.仿真实验表明算法在定位精度,计算开销、能耗等方面都具有较好的性能.
P2P网络环境下的一种高效虚拟协同服务模型
乐光学, 李仁发,
2008, 45(11):  1928-1938. 
摘要 ( 405 )   HTML ( 0)   PDF (1642KB) ( 426 )  
相关文章 | 计量指标
在现实网络中,资源主要集中在少数的重要节点中,大量节点是服务请求者.由于P2P网络是建立在Internet之上的应用层虚拟网络,加上网络中搭便车现象日益严重,在广域环境下,不可避免地存在拥塞、单点失效、效率和服务质量不高的问题.针对这些问题,通过在系统中动态地构造由协同服务盟员组成的服务池来解决.提出了一种有盟主的虚拟协同服务组织模型,旨在现实环境下针对盟主的目标需求,解决盟主如何动态组织自主的协同伙伴和构建虚拟组织协同进行求解的问题.构造了基于D-S证据推理的服务盟员选择策略,运用节点交易历史信息和推荐证书的方法来表征备选服务盟员的全局信任特征属性,给出了构建虚拟协同服务池的数学模型、约束条件和构造规则,并进行了较为详细的分析.仿真实验表明,动态构造服务池的负载平衡策略能较好地解决P2P网络中存在拥塞、单点失效、效率和服务质量不高的问题,极大地改善了P2P网络的服务质量.
基于部分信道信息反馈的多用户MIMO传输机制研究
杨育波, 田 霖, 周继华, 张玉成, 石晶林,
2008, 45(11):  1939-1946. 
摘要 ( 387 )   HTML ( 0)   PDF (787KB) ( 380 )  
相关文章 | 计量指标
在宽带无线通信系统中,多天线技术的实现依赖于多用户MIMO传输机制及信道信息反馈的有效解决.提出一种发送端进行干扰消除的TIE算法及相应的用户选择算法和功率分配算法,并提出一种基于向量量化的部分信道信息反馈机制,可以在多用户环境中提高系统性能并能有效降低信道信息反馈开销.分析了采用部分信道反馈机制的TIE算法的性能,论证了其性能特征.实验结果表明,与其他算法相比TIE算法可以有效地提高系统数据速率,而部分信道反馈机制可以在保持系统数据速率的前提下极大地降低信道反馈信令的开销.
基于FPGA的高速椭圆曲线标量乘法结构
陈 婧, 蒋俊洁, 王 石, 邓小铁, 汪东升,
2008, 45(11):  1947-1954. 
摘要 ( 484 )   HTML ( 0)   PDF (795KB) ( 458 )  
相关文章 | 计量指标
椭圆曲线密码系统是最近十几年来获得迅速发展的一类密码系统.为了提高椭圆曲线密码系统的处理速度,针对其中最关键的运算——椭圆曲线标量乘法设计并实现了一种基于FPGA的硬件结构,完成GF(2/+m)上的椭圆曲线标量乘法计算.该结构最大程度地对标量乘算法的内部模块进行了并行处理,缩短最大延迟路径,从而达到提高运算速度的目的.这一结构在FPGA上实现后,计算一次GF(2/+/{163/})上的椭圆曲线标量乘法只需要36μs,这一性能是目前国际上已知的基于FPGA的标量乘法器中最好的.
两阶段无监督顺序前向分形属性规约算法
闫光辉 李战怀
2008, 45(11):  1955-1964. 
摘要 ( 456 )   HTML ( 0)   PDF (899KB) ( 405 )  
相关文章 | 计量指标
采用单个属性多重分形维数及属性合并之后分形维数变化程度作为属性相关性的度量依据,以结果属性子集分形维数与属性全集分形维数的差值作为评价结果属性子集优劣的标准,将分形属性规约问题转化为属性个数受限的最大无关分形属性子集搜索问题.针对高维属性空间搜索的“组合爆炸”现象,设计了结合相关性分析与冗余性分析的两阶段顺序前向无监督分形属性规约算法.初步分析了算法的时空复杂性,基于标准与合成数据集的实验结果表明,算法能够以较低的分形维数计算工作量得到较优的属性子集.
一种基于Quartet Puzzling和邻接法的进化树构建算法
李建伏 郭茂祖 刘 扬
2008, 45(11):  1965-1973. 
摘要 ( 737 )   HTML ( 2)   PDF (2463KB) ( 535 )  
相关文章 | 计量指标
最大似然法是目前较准确的一种进化树构建方法,但是其时间复杂度非常高.在实际应用中,用分治策略实现最大似然法的Quartet Puzzling(QP)得到了人们的关注.它首先估计Quartet拓扑结构集合Q,然后利用重组技术将Q中的信息合并到一起构成一个包含所有序列的进化树.研究表明,QP的准确性不像人们所期望的那样高.如何快速有效地将Q所包含的信息融合在一起仍然是QP所面临的一个问题.为了提高QP,结合邻接法提出一种新的进化树构建方法QPNJ.理论上,QPNJ与QP具有相同的时间复杂度.通过模拟实验将QPNJ与QP以及目前流行的进化树构建方法进行了比较.结果表明,QPNJ比QP和邻接法更准确,并且其性能不依赖于模型树的结构,从而证明了QPNJ的有效性.
基于Gaussian-Hermite 矩和改进的Poincare Index的指纹奇异点提取
翁大伟 尹义龙 杨公平 亓秀燕
2008, 45(11):  1974-1984. 
摘要 ( 796 )   HTML ( 5)   PDF (2900KB) ( 383 )  
相关文章 | 计量指标
在指纹分类和匹配中,准确、可靠地提取奇异点十分重要.针对低质量指纹图像奇异点检测中精确定位和可靠性判断这一难题,提出了一种两阶段的奇异点提取算法.首先,针对现有Poincare index方法存在伪点检出较多和抗噪性较弱的问题,通过对其改进实现候选奇异点位置的确定;然后,再通过计算候选奇异点周围圆形邻域的Gaussian-Hermite矩分布属性值来判断其真伪.方法有效结合了奇异点周围邻域的纹线方向和纹线一致性信息,能够从指纹图像中较为准确、可靠地检测出奇异点.在NIST-4和南京大学活体指纹库上的实验结果验证了该方法的有效性和鲁棒性.在从NIST-4中随机抽取的500幅指纹图像上,奇异点的检测准确率为93.05%(Core点准确率为96.93%,Delta点准确率为86.43%).
一种基于多核流水的多标准视频编解码器体系结构
张 鹏 杜建国 解晓东 高 文
2008, 45(11):  1985-1993. 
摘要 ( 385 )   HTML ( 2)   PDF (1143KB) ( 412 )  
相关文章 | 计量指标
多标准已成为视频编解码器的发展趋势,这给系统设计带来了性能和灵活性双重的挑战.根据视频标准间算法的异同点,提出并实现了一种多标准视频编解码器芯片的体系结构,支持包括H.264/AVC,AVS和VC-1的多个标准.系统级采用了基于宏块的多核流水线结构,在保持可编程性的基础上显著提高了系统级的并行度.模块级进行了详细的软硬划分设计,可配置的专用数据通路用以加速各模块的特定运算.VLSI实现表明,芯片面积仅为961kgate,且能保证NTSC(30fps)和PAL(25fps)的实时编解码.