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

当期目录

2006年 第43卷 第10期    出版日期:2006-10-15
论文
基于词频分类器集成的文本分类方法
姜 远 周志华
2006, 43(10):  1681-1687. 
摘要 ( 531 )   HTML ( 3)   PDF (531KB) ( 978 )  
相关文章 | 计量指标
提出了一种基于词频分类器集成的文本分类方法.词频分类器是在对文本中的单词和它在每个文本中出现的频率进行统计后得到的简单分类器.虽然词频分类器本身泛化能力不强,但它不仅计算代较小,而且在训练样本甚至类别增加时易于进行更新,而整个学习系统的泛化能力可以由集成学习机制来提高,因此,词频分类器很适合用做集成学习的基分类器.在集成时,使用了改进的AdaBoost算法,加入了一种强制重新分布权的机制,避免算法过早停止,更加适合文本分类任务.在标准文集Reuters-21578上的实验结果表明,该方法能取得很好的效果.
文本分类中基于基尼指数的特征选择算法研究
尚文倩 黄厚宽 刘玉玲 林永民 瞿有利 董红斌
2006, 43(10):  1688-1694. 
摘要 ( 596 )   HTML ( 3)   PDF (485KB) ( 804 )  
相关文章 | 计量指标
随着网络的发展,大量的文档数据涌现在网上,用于处理海量数据的自动文本分类技术变得越来越重要,自动文本分类已成为处理和组织大量文档数据的关键技术.对于采用矢量空间模型(VSM)的大多数分类器来说,文本预处理成为分类的瓶颈,高维的特征空间对于大多数分类器来说是难以忍受的,因此采用适当的文本特征选择算法降低原始文本特征空间的维数成为文本分类的首要任务.目前也有很多的文本特征选择算法,介绍了另一种新的基于基尼指数的文本特征选择算法,使用基尼指数原理进行了文本特征选择的研究,构造了基于基尼指数的适合于文本特征选择的特征选择评估函数.实验表明,基于基尼指数的文本特征选择能进一步提高分类性能,而且计算复杂度小.
基于分级神经网络的Web文档模糊聚类技术
雷景生, 马 军, 靳 婷,
2006, 43(10):  1695-1699. 
摘要 ( 317 )   HTML ( 1)   PDF (372KB) ( 560 )  
相关文章 | 计量指标
给出了一种多层向量空间模型,该模型将一篇文档的相关信息从逻辑上划分为多个相对独立的文本段,按照不同位置的文本段确定相应的索引项权重.然后提出了一种简明而有效的基于分级神经网络的模糊聚类算法.与现有方法不同,该模糊聚类方法采用自组织神经网络和模糊聚类网络两部分组成的3层神经网络来实现.首先采用自组织神经网络从原始数据产生一个初始聚类结果,然后运用FCM方法对初始聚类的数目进行优化.实验结果表明,提出的Web文档聚类算法具有较好的聚类特性,它能将与一个主题相关的Web文档较完全和准确地聚成一类.
基于原型超平面的多类最接近支持向量机
杨绪兵 陈松灿
2006, 43(10):  1700-1705. 
摘要 ( 305 )   HTML ( 0)   PDF (569KB) ( 541 )  
相关文章 | 计量指标
基于广义特征值的最接近支持向量机(proximal support vector machine via generalized eigenvalues, GEPSVM)摒弃了传统意义下支持向量机典型平面的平行约束,代之以通过优化使每类原型平面尽可能接近本类样本,同时尽可能远离它类样本的准则来解析获得原型平面;从而避免了SVM的二次规划,其分类性能达到甚至超过了SVM.但GEPSVM仍存在如下不足:①仅对两分类问题而提出,无法直接求解多分类问题;②存在正则化因子的选择问题;③求解原型平面的广义特征值问题中所涉及的矩阵一般仅为半正定,容易导致奇异性问题.通过定义新的准则,构建了一个能直接求解多个原型超平面的多分类方法,称之为基于原型超平面的多类最接近支持向量机,较之GEPSVM,该方法优势在于:①无正则化因子选择的困扰;②可同时求解多个超平面,对两分类问题,分类性能达到甚至优于GEPSVM;③超平面的选择问题转化为简单特征值而非广义特征值求解问题;④原型平面的选择只依赖于本类样本,故不必考虑多分类情形时的数据不平衡问题.
基于嵌入式Bootstrap的主动学习示例选择方法
田春娜 高新波 李 洁
2006, 43(10):  1706-1712. 
摘要 ( 450 )   HTML ( 1)   PDF (748KB) ( 644 )  
相关文章 | 计量指标
在Bootstrap示例选择算法的基础上提出一种新的嵌入式Bootstrap算法.该算法适用于一大类主动机器学习中训练示例的选择问题.新算法在保持和原Bootstrap算法相当的训练时间的前提下可得到更典型的训练示例集,从而解决了计算条件对训练集规模的限制,使训练所得预测器具有更高的性能.从理论上分析了新算法的有效性,然后将其与原Bootstrap算法分别应用到基于AdaBoost的正面人脸检测任务中进行对比实验,实验结果与理论分析一致.
SEFNN:一种基于结构进化的前馈神经网络设计算法
李 宁 谢振华 谢俊元 陈世福
2006, 43(10):  1713-1718. 
摘要 ( 387 )   HTML ( 1)   PDF (512KB) ( 575 )  
相关文章 | 计量指标
遗传算法是一种模拟自然选择和进化的随机搜索算法,它的搜索能够遍及整个解空间,容易得到全局最优解.目前主要的编码方式都是将结构和连接权值等信息编码成串式的基因,这不利于在遗传过程中保留个体的子结构信息,也难于设计兼顾基因型与表现型的遗传算子;在前馈神经网络的进化中引入BP训练方面,也不分良莠对所有后代进行训练,形成资源浪费.为克服这些问题,提出了一种基于结构进化的前馈神经网络设计算法SEFNN,该算法使用一种紧缩矩阵编码、新型结构化交叉算子、修订的变异算子和精英训练法则,充分考虑了基因型与表现型之间的关系,适当加大变异搜索速度,并采用选拔训练方式,从而提高了进化神经网络的效率.实验表明该算法获得的解无论在网络规模还是测试精度上都有优越的性能表现,并已应用于肺癌早期细胞病理诊断系统,具有良好的效果.
基于覆盖的粗糙模糊集模型研究
魏 莱 苗夺谦 徐菲菲 夏富春
2006, 43(10):  1719-1723. 
摘要 ( 418 )   HTML ( 0)   PDF (339KB) ( 571 )  
相关文章 | 计量指标
在研究覆盖粗糙集模型中,发现对覆盖粗糙集上近似的定义并不一致.简述了各个模型的区别,并在一个较合理的覆盖粗糙集上近似定义上,结合覆盖约简理论,重新定义了基于覆盖的粗糙集模型,讨论了它的一些性质.另外,将模型进行推广,定义了基于覆盖的粗糙模糊集模型,证明了它具有一些较好的性质.
基于自适应粒子群算法的约束布局优化研究
雷开友 邱玉辉
2006, 43(10):  1724-1731. 
摘要 ( 433 )   HTML ( 0)   PDF (741KB) ( 711 )  
相关文章 | 计量指标
二维带平衡及不干涉约束的圆集在圆容器内的布局优化问题(如卫星舱布局)在理论上属于带性能约束的布局优化问题,它是NP-hard问题的难点,由于它的复杂性, 传统的粒子群优化算法难于求解.通过对传统的粒子群优化算法的多重改进,提出了一种自适应粒子群优化算法,该算法在整个搜索过程中,既能保持粒子群原有基本结构,同时又能扩大搜索范围,在提高多样性的同时保证搜索精度,从而加快了收敛速度,有效避免早熟收敛问题,得到最优解.将改进后的算法应用于约束布局问题,建立了此类问题的粒子群算法,通过3个算例的数值计算,验证了该算法的可行性和有效性.
基于小波变换的序列间距离严格估算
刘 兵 汪 卫 施伯乐
2006, 43(10):  1732-1737. 
摘要 ( 299 )   HTML ( 1)   PDF (499KB) ( 685 )  
相关文章 | 计量指标
对时间序列的相似性搜索在很多新的数据库应用中的地位变得越来越重要.使用小波变换方法缩减维度是解决高维时间序列查询的一个有效方法.给出小波变换在时间序列相似性查找中对距离上下界的一个严格估计,同时说明传统的算法只是下界的一部分.根据给出的小波变换的下界,相对于传统的算法,可以排除更多的不相似序列.根据给出的上界,可以直接判断出两条序列是否相似,进一步减少需要验证的原始序列的个数.实验结果表明,相对于传统的算法,提出的上下界可以大幅度提高过滤效果,减少查询时间.
基于滑动窗口的数据流闭合频繁模式的挖掘
刘学军, 徐宏炳, 董逸生, 钱江波, 王永利,
2006, 43(10):  1738-1743. 
摘要 ( 487 )   HTML ( 4)   PDF (515KB) ( 630 )  
相关文章 | 计量指标
频繁闭合模式集惟一确定频繁模式完全集并且数量小得多,然而,如何挖掘滑动窗口中的频繁闭合模式集是一个很大的挑战.根据数据流的特点,提出了一种发现滑动窗口中频繁闭合模式的新方法DS_CFI. DS_CFI算法将滑动窗口分割为若干个基本窗口,以基本窗口为更新单位,利用已有的频繁闭合模式挖掘算法计算每个基本窗口的潜在频繁闭合项集,将它们及其子集存储到一种新的数据结构DSCFI_tree中,DSCFI_tree能够增量更新,利用DSCFI_tree可以快速地挖掘滑动窗口中的所有频繁闭合模式.最后,通过实验验证了这种方法的有效性.
论文
高维数据流的在线相关性分析
杨雪梅, 董逸生, 徐宏炳, 刘学军, 钱江波, 王永利,
2006, 43(10):  1744-1750. 
摘要 ( 527 )   HTML ( 1)   PDF (728KB) ( 803 )  
相关文章 | 计量指标
为了解决在资源受限的计算环境下快速检测高维数据流之间相关性的问题,提出一种新颖的在线典型相关性分析(CCA)算法QuickCCA, 针对传统CCA计算中的性能瓶颈, 首先采用不等概列采样技术约减流元组的数量,形成概要矩阵; 然后在概要矩阵的基础上增量地计算多维数据流之间的前k个典型相关系数.经理论分析和实验证明,QuickCCA能够在线精确地识别同步滑动窗口模式下多维数据流之间的相关性.与已有分析多数据流相关性的算法相比,QuickCCA显著地降低了计算复杂度,并且能够在精度和性能之间折中,可以作为通用的分析工具广泛应用于数据流挖掘领域.
一种基于OBDD图的事件复合匹配方法
徐 罡 马建刚 黄 涛
2006, 43(10):  1751-1759. 
摘要 ( 339 )   HTML ( 1)   PDF (669KB) ( 691 )  
相关文章 | 计量指标
基于内容的Pub/Sub系统的核心问题是基于内容的事件匹配.在现有的方法中,订阅者使用简单约束来匹配事件内容,难以支持事件复合匹配.针对此问题,提出新的匹配模型,扩展简单匹配方法为多语义匹配并引入时间约束变量,支持依据语义对事件采取不同的操作和离散事件的处理,增强了事件匹配表达能力.在此基础上,将OBDD图扩展为层次着色OBDD图,证明了图扩展的等价性,给出基于扩展ODBB图的复合匹配算法,分析并验证了该算法的有效性.
基于条件范围约束的越界访问检测方法
夏一民 罗 军 张民选
2006, 43(10):  1760-1766. 
摘要 ( 295 )   HTML ( 1)   PDF (568KB) ( 570 )  
相关文章 | 计量指标
程序执行时的越界访问将导致异常的行为,已有的越界检测方法存在效率低或精度不高的缺点.分两步检测程序中的越界访问语句:在约束产生阶段,提出一个流敏感、过程间的约束状态产生算法,为每条语句建立一个范围约束集合和值约束集合;在约束求解阶段,利用线性规划计算程序访问的内存大小和偏移量,报告可能的越界访问漏洞.实验表明,检测效率明显高于路径敏感的范围分析方法,而平均检测精度高于80%.
构件软件回归测试用例选择策略
毛澄映, 卢炎生,
2006, 43(10):  1767-1774. 
摘要 ( 418 )   HTML ( 0)   PDF (745KB) ( 709 )  
相关文章 | 计量指标
软构件技术虽被广泛应用于软件系统的开发中,但其测试问题并未得到很好地解决.系统构建者对外部提供的构件内部结构及其变更信息缺乏了解,很难选择出与构件变更相关的用例用于下一轮的测试.分析已有回归测试技术的不足,提出了两种改进的回归测试策略:一种是基于增强的构件版本变更信息的方法;另一种则是基于内建式测试设计的方法.通过对几个实例程序的实验分析,初步证实了所提出的方法在实际应用中的可行性与有效性.
一种分级可扩放全序组通信协议——RHGP
王文韬 吴俊敏 许胤龙 李黄海 鲍春健
2006, 43(10):  1775-1781. 
摘要 ( 458 )   HTML ( 1)   PDF (528KB) ( 427 )  
相关文章 | 计量指标
并行分布式系统需要大量成员通过组通信协作完成某些特定的功能.当组中包含大量成员且其关系不断变化时,传统组通信系统将会产生很多不必要的通信开销.提出了一种新型的基于令牌环的分级组通信协议(ring-based hierarchical group protocol,RHGP),支持全序消息递送和组成员的动态变化.该协议通过减少成员改变消息递送的次数,降低了组成员关系改变时的通信开销,增加了协议的可靠性.最后通过协议分析论证了该协议的可靠性和可扩放性,在成员失效率为0.1%、成员个数接近200时协议的可靠性为99.8646%.
面向Agent的软件工程: 现状与挑战
毛新军 常志明 王 戟 王怀民
2006, 43(10):  1782-1789. 
摘要 ( 558 )   HTML ( 3)   PDF (439KB) ( 915 )  
相关文章 | 计量指标
面向Agent软件工程是近年来软件工程领域出现的一个重要的前沿研究方向,它试图将Agent理论和技术与软件工程的思想、原理和原则相结合,从而为基于Agent系统的开发提供工程化手段.近年来,随着Internet上的Web应用以及软件开发社会化的发展,面向Agent软件工程受到了学术界和工业界的高度关注和重视,研究活跃,发展迅速.从应用需求和技术发展两个方面阐述了面向Agent软件工程的产生和发展背景;从技术、管理和工具3个视点综述了现阶段面向Agent软件工程的研究内容;分析了面向Agent软件工程的研究现状;最后讨论了它存在的问题和面临的挑战以指导进一步研究.
基于回溯机制的互联网AS拓扑的Betweenness算法
张国强, 张国清,
2006, 43(10):  1790-1796. 
摘要 ( 509 )   HTML ( 4)   PDF (618KB) ( 478 )  
相关文章 | 计量指标
Betweenness能够刻画节点或边在网络中的重要程度.在Internet中,Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量,能够对网络的动态行为进行预测.但传统的Betweenness计算复杂度较高,为O(n\+3),但这些算法是为加权网络设计的,而很多实际的网络模型并没有考虑权重.另一方面,目前的算法都没有考虑边的语义,而互联网AS(autonomous system)拓扑中的边具有语义.针对简单无权网络提出一种基于回溯的时间复杂度为O(nm)的Betweenness计算方法.在进一步考虑Internet AS拓扑的特殊性,即任意两个相连的AS都具有某种商业关系的基础上提出了互联网AS层拓扑的Betweenness计算方法.
一种基于子元组划分的快速两维包分类算法
刘 彤, 李华伟, 李晓维, 宫曙光,
2006, 43(10):  1797-1803. 
摘要 ( 378 )   HTML ( 2)   PDF (543KB) ( 533 )  
相关文章 | 计量指标
包分类对于支持如防火墙、攻击检测、差分服务等网络应用有着重要的意义.研究人员对此做了大量研究.其中基于Srinivasan提出的元组空间思想的算法都存在着不能够通过预查找的方法直接定位匹配规则的元组的问题,因此此类算法的平均查找性能不稳定.针对两维包分类,提出了将元组划分为子元组的准则,满足准则的子元组可以根据3个独立的一维查找结果确定是否包含匹配规则,通过消除不必要的元组查找来提高查找速度和获得稳定的查找性能.
差异性条件约束下基于PKI的信任域互连
朱鹏飞 戴英侠 鲍旭华
2006, 43(10):  1804-1809. 
摘要 ( 319 )   HTML ( 0)   PDF (428KB) ( 473 )  
相关文章 | 计量指标
基于PKI的信任域之间可能存在的差异,会对不同信任域的实体之间实现互连造成不利影响.提出了信任域兼容性的概念,形式化地分析了信任域差异性对不同信任域间实体实现互连的影响.在此基础上提出了通过条件扩展来实现信任域兼容化,并给出了一种信任域兼容化的实现方案.
使用对技术的基于身份密码学研究综述
田 野, 张玉军, 李忠诚,
2006, 43(10):  1810-1819. 
摘要 ( 471 )   HTML ( 0)   PDF (1034KB) ( 710 )  
相关文章 | 计量指标
密钥管理是基于证书密码学中最复杂的问题,基于身份密码学正是为了简化密钥管理问题提出的.从保障信息安全的3个基本密码学要素(加密、数字签名和密钥协商)出发,对基于身份密码学的研究现状进行了综述,对其中存在的安全模型、执行效率等问题进行了详细分析.由于针对基于身份密码学缺乏实际应用研究,以解决无线移动IPv6网络环境下的接入控制和数据机密性问题为应用场景,讨论了一种基于身份密码技术的应用思路和问题,同时基于身份密码技术本身及其应用两方面指出了未来的研究趋势.
龙芯1号处理器的故障注入方法与软错误敏感性分析
黄海林, 唐志敏, 许 彤,
2006, 43(10):  1820-1827. 
摘要 ( 510 )   HTML ( 0)   PDF (571KB) ( 627 )  
相关文章 | 计量指标
在纳米级制造工艺下以及在航天等特殊应用场合中,可靠性将是处理器设计中的一个重要考虑因素.以龙芯1号处理器为研究对象,探讨了处理器可靠性设计中的故障注入方法,并提出了一种同时运行两个处理器RTL模型的故障注入与分析方法,可以实现连续快速的处理器仿真故障注入.在此基础上,进一步分析了龙芯1号处理器的软错误敏感性,通过快速注入大约30万个软错误,保证了分析结果具有较好的统计意义,可以有效指导后续的容错与可靠性设计.
用于WCET静态分析的MIPS处理器建模方法研究
卞晓丰, 周学海,
2006, 43(10):  1828-1834. 
摘要 ( 392 )   HTML ( 0)   PDF (596KB) ( 561 )  
相关文章 | 计量指标
为获得安全而紧致的WCET估计,需要考虑执行程序的目标处理器的体系结构特征. Cache、流水线等用于提高性能的技术已经广泛地应用于现代处理器中,如果在静态分析过程中不考虑它们带来的影响,必然会导致WCET过估计.以Petri网作为模型工具,以WCET分析为应用目标构造MIPS处理器的体系结构模型,该方法讨论了各种RISC处理器中常见的体系结构特征的抽象以及它们在Petri网模型中的表示方法.通过实验验证,指令序列在Petri网模型上的模拟执行时间与指令序列在DLXView模拟器上的测试结果具有一致性,表明构建处理器的体系结构Petri网模型是一种有效的指令序列执行时间的静态分析方法.
龙芯2号微处理器浮点除法功能部件的形式验证
陈云霁 马 麟 沈海华 胡伟武
2006, 43(10):  1835-1841. 
摘要 ( 388 )   HTML ( 0)   PDF (515KB) ( 573 )  
相关文章 | 计量指标
基于决策图的字级模型检验方法虽然能完全验证运算电路,但它从有缺陷的设计中发现系统规范的反例所需时间较长.而基于SAT的有界模型检验方法虽然能较快地发现反例,但它不支持包含数学公式的系统规范,因而难以用于验证运算电路.提出了基于SAT的字级模型检验方法,该方法将CNF扩展为能混合布尔公式和数学公式的E-CNF用以表示设计和系统规范,并对有界模型检验工具和SAT求解器进行字级的扩展,使它们能分别生成和处理E-CNF.龙芯2号微处理器浮点除法功能部件验证同时采用了基于*PHDD和基于SAT的字级模型检验方法.数据表明,基于SAT的字级模型检验方法能快速地发现运算电路中的设计缺陷.两种方法互为补充,在能完全验证设计的同时显著缩短了设计周期.
一致持久的带外虚拟化系统
张广艳 舒继武 薛 巍 郑纬民
2006, 43(10):  1842-1848. 
摘要 ( 331 )   HTML ( 0)   PDF (626KB) ( 539 )  
相关文章 | 计量指标
存储虚拟化能够全面提升存储区域网络的服务质量,而带外虚拟化与带内虚拟化相比具有性能高和扩展性好等优点.提出了运用按序操作、REDO日志以及日志完整性鉴别,共同保证带外虚拟化跨越系统崩溃或断电事故后仍旧可用;设计了一种基于关系模型的磁盘上虚拟化元数据组织方式,它具有可读性好和容易修改的优点;给出了通过分析磁盘分区表兼容典型遗留存储系统的有效方法,它具有庞大遗留系统零切割时间的特点.基于上述关键技术实现的原型系统,在典型实验中表现了很好的性能.
海量存储网络中的虚拟盘副本容错技术
王 迪 薛 巍 舒继武 沈美明
2006, 43(10):  1849-1854. 
摘要 ( 336 )   HTML ( 1)   PDF (888KB) ( 582 )  
相关文章 | 计量指标
大规模存储网络中的数据可用性和读写性能越来越重要.在海量存储虚拟化系统的基础上,实现了多副本虚拟盘技术来提高网络存储的数据容错能力.同时,通过多副本选择调度与异步副本更新以及副本盘空间布局的动态调整算法,提高了系统的数据读写能力.测试结果表明,加入虚拟盘副本后,在设备数量充足情况下的读性能可提高26%;即使少量磁盘失效,读写操作也能正确执行,且读性能仍然比无副本时提高10%以上.