摘要:针对传统支持向量机方法中存在对噪声或野值敏感的问题,提出了一种基于紧密度的模糊支持向量机方法.在确定样本的隶属度时,不仅考虑了样本与类中心之间的关系,还考虑了类中各个样本之间的关系.通过样本之间的紧密度来描述类中各个样本之间的关系,利用包围同一类中样本的最小球半径大小来度量样本之间的紧密度.样本的隶属度依据样本在球中的位置,按照不同的规律确定与基于样本与类中心之间关系构建的模糊支持向量机方法相比,该方法有利于将野值或含噪声样本与有效样本进行区分.实验结果表明,与传统支持向量机方法及基于样本与类中心之间关系的模糊支持向量机方法相比,基于紧密度的模糊支持向量机方法具有更好的抗噪性能及分类能力.

摘要:提出了一种基于图像序列的飞行器接近角的估计方法.飞行器的接近角对于飞行器的着陆来说是一个非常重要的参数,是指飞行器在着陆时的飞行轨迹与地平面之间的夹角.飞行器在着陆时近似作平移运动,在这种情况下,图像上的极点称作FOE(focus-of-expansion),地平面的消失线被称作Horizon.首先给出了从已标定的图像序列中提取FOE和Horizon的方法,然后由这两个参数估计出飞行器的接近角.模拟实验和真实图像实验表明该方法是可行的.

摘要:扩展模糊描述逻辑EFALCN(extendedfuzzy attributive concept descriptionlanguage with complements and unqualified number restriction)是支持数量约束的描述逻辑ALCN的模糊扩展,但该逻辑的推理问题缺乏相应的算法和复杂性证明.提出EFALCN推理问题基于约束传播的Tableau算法,并证明该算法可在PSPACE(polynomial space)约束下执行.由ALCN(attributive concept descriptionlanguage with complements and unqualified number restriction)的推理问题可多项式时间归约到EFALCN推理问题,且ALCN的推理问题是PSPACE-complete问题.所以,EFALCN推理问题是PSPACE-hard问题.综上所述,EFALCN推理问题是PSPACE-complete问题.

摘要:定性的空间推理在地理信息系统、人工智能、数据库及多媒体等领域中的应用越来越引起人们的注意.空间推理的基础理论以及相应算法也在不断地创新和发展.方向关系推理是空间推理研究领域的重要分支,利用区间代数及矩形代数理论,以物体的极小边界盒(minimum bounding rectangle,简称MBR)为模型,提出了一种基于MBR的主方向关系与矩形代数关系相结合的推理方法.利用该方法,可以将矩形代数良好的计算性质应用于空间方向关系推理中,实现了矩形代数与基于MBR主方向关系的相互转换方法、主方向关系合成及求反方法、主方向关系中凸(convex)关系判定方法及方向关系一致性检验算法.

摘要:语音库裁剪或语音库去冗余,是大语料库语音合成技术的一个重要问题.提出了虚拟不定长替换的概念,以弥补不定长的损失.结合合成使用变体的频度,构建了语音库裁剪算法StaRp-VPA.该算法能够以任意比例裁剪语音库.实验表明:当裁剪率小于50%时,合成自然度几乎没有下降;当裁剪率大于50%时,合成自然度也不会严重降低.

摘要:XML文档作为一种新的数据形式,成为当前的研究热点.XML文档间相似度的计算是XML文档分析、管理及文本挖掘的基础.结构链接向量模型(structuredlink vector model,简称SLVM)是一种综合考虑XML文档结构信息与内容信息进行XML文档相似度量的方法.体现XML文档结构单元关系的核矩阵在结构链接向量模型中扮演着重要角色.为自动捕获XML文档结构单元关系,提出了两种核矩阵的学习算法,分别是基于支持向量机(support vector machine,简称SVM)的回归学习算法和基于矩阵迭代的学习算法.相似搜索实验对比结果表明,基于核矩阵学习方法的XML文档相似度量方法的准确性明显优于其他方法.进一步实验表明,基于矩阵迭代学习的核矩阵学习算法与基于支持向量机的回归学习算法相比,不仅具有更高的准确性,而且所需训练文档更少、计算代价更小.

摘要:提出了视觉跟踪任务中目标动态建模的一种方法.该方法首先针对跟踪序列中的当前帧图像观测进行Haar变换,从而得到图像的过完备特征描述;然后根据Fisher准则,评价每个Haar特征对目标和当前背景的区分能力,目标模型由那些区分能力最强的Haar特征构成.在跟踪过程中,采用卡尔曼滤波算法预测目标下一时刻的可能位置,从而根据目标的图像观测和目标下一时刻可能的位置附近的背景图像观测,对Haar特征的区分能力进行动态评价.通过保留区分能力强的特征,同时淘汰区分能力弱的特征,维护目标模型的强可区分性和低计算复杂性.该方法的主要策略是,在最大程度地保持可区分性的前提下,减少计算的复杂性.实验结果表明,在存在诸多不确定性因素的真实长序列视频上,该跟踪方法能够实时地完成复杂的目标跟踪任务.

摘要:孤立点是不具备数据一般特性的数据对象.划分的方法是通过将数据集中的数据点分布的空间划分为不相交的超矩形单元集合,匹配数据对象到单元中,然后通过各个单元的统计信息来发现孤立点.由于大多真实数据集具有较大偏斜,因此划分后会产生影响算法性能的大量空单元.由此,提出了一种新的索引结构--CD-Tree(cell dimension tree),用于索引非空单元.为了优化CD-Tree结构和指导对数据的划分,提出了基于划分的数据偏斜度(skew of data,简称SOD)概念.基于CD-Tree与SOD,设计了新的孤立点检测算法.实验结果表明,该算法与基于单元的算法相比,在效率及有效处理的维数方面均有显著提高.

摘要:基于频繁模式的关联分类是近年来出现的一种分类方法,该方法利用各类别频繁出现的模式构造分类规则,并对新文本进行分类.但现有关联分类方法应用于文本分类时存在两方面不足:一方面,用以构造分类规则的频繁模式仅考虑特征词在文本中出现与否,从而忽视了出现频度;另一方面,当产生的规则数量较多时,为提高分类效率需要进行规则修剪,修剪后的分类准确性明显降低.为此,提出了基于分类规则树的带词频的频繁模式文本分类方法.研究结果表明,词频的引入可以提高关联分类的准确率;而采用分类规则树可使分类时间明显加快又确保不降低分类质量.这两方面的措施弥补了现有关联分类应用于文本分类的不足.与3种典型文本分类方法比较后发现,在低维特征空间中,关联分类的性能优于Bayes,kNN(k nearest neighbor)和SVM(support vectormachines),因此是一种很有应用前景的文本分类方法.

摘要:在大规模或实时环境要求下,机器学习算法的计算效率非常重要.描述了用于最大熵模型执行系统的一种高效的数据结构及其相关的生成和查找算法.这种数据结构称为稀疏特征树,用于表示特征集合,以提高特征查找(或特征匹配)的速度,从而提高概率计算和执行系统的速度.基本短语识别和词性标注的实验显示,这种新的数据结构的确能够极大地加快最大熵方法执行系统的速度,同时保持空间复杂度不变.

摘要:使用反例压缩算法,从反例中剔除冗余信息,从而使反例易于理解,是目前的研究热点.然而,目前压缩率最高的BFL(brute force lifting)算法,其时间开销过大.为此,提出一种基于悖论分析和增量式SAT(boolean satisfiablilty problem)的快速反例压缩算法.首先,根据反证法和排中律原理,该算法对每一个自由变量v,构造一个SAT问题,以测试v是否能够避免反例.而后对其中不可满足的SAT问题,进行悖论分析,抽取出导致悖论的变量集合.所有不属于该集合的变量,均可作为无关变量直接剔除.同时,该算法使用增量式SAT求解方法,以避免反复搜索冗余状态空间.理论分析和实验结果表明,与BFL算法相比,该算法能够在不损失压缩率的前提下获得1～2个数量级的加速.

摘要:时间序列预测是一类非常重要的问题,但基本上局限于参数不可变问题的研究,而对实际问题中经常出现的更重要的参数可变系统的预测,由于构成几乎所有已有预测技术基础的Taken嵌入定理不再成立,所以这方面的研究成果极少.使用一种将(多)小波变换与反向传播神经网络相结合的新型网络结构--(多)小波神经网络,尝试对参数可变时间序列的预测.因为(多)小波神经网络的误差函数是一个凸函数,这在一定程度上可以避免经典神经网络容易陷入局部极小、收敛速度慢等问题.对著名的Ikeda参数可变系统的实验表明,多小波神经网络的预测性能较单小波神经网络要好,而单小波神经网络的性能较BP网要好.因此,该方法不失为时间可变系统预测的一种好的推荐.

摘要:互联网络中信息量的快速增长使得增量搜集技术成为网上信息获取的一种有效手段,它可以避免因重复搜集未曾变化的网页而带来的时间和资源上的浪费.网页变化规律的发现和利用是增量搜集技术的一个关键.它用来预测网页的下次变化时间甚至变化程度;在此基础上,增量搜集系统还需要考虑网页的变化频率、变化程度和重要性,选择一种最优的任务调度算法来决定不同网页的搜集频率和相对搜集次序.针对网页变化和增量搜集技术这一主题,对最近几年的研究成果作总结,并介绍最新的研究进展.首先论述对网页变化规律的建模、模型参数估计和估计效率等问题;然后介绍几个著名的增量搜集系统,着重分析它们的任务调度算法;最后,从理论上分析和总结增量搜集系统的最佳任务调度算法及其一个基于启发式策略的近似解,并预测其将来的研究趋势.该工作对增量搜集系统的设计和Web演化规律的研究具有参考意义.

摘要:服务组合可以整合网络上现有的多种异构服务,形成新的服务.针对服务组合中服务路径的选择和负载均衡问题,提出了一种自适应的分布式负载均衡算法--LCB(load capacity based algorithm)算法.LCB算法使用服务路由来查找服务和转发数据,使用负载容率(load capacity,简称LC)测度来进行服务副本的选择,从而建立一条适当的组合服务路径.LC测度是对服务器负载的估算,它根据服务器的负载波动信息不断地进行自适应的调整,从而实现多个服务副本之间的负载均衡.与现有的服务组合负载均衡算法相比,LCB算法不需要知道服务器的最大负载量和当前负载信息,而且具有更好的可扩展性,更适用于分布式环境下动态服务副本的组合.模拟实验表明,LCB算法具有良好的负载均衡效果.

摘要:研究了TCP(transmission control protocol)流在多跳无线自组网络中的公平性问题,发现IEEE802.11DCF协议在此环境下会导致严重的不公平性,即部分节点垄断了网络带宽而其他节点被饿死.首先,通过仿真分析了产生TCP流不公平性的原因,指出其根源在于MAC(media access and control)协议的不公平性,同时,TCP的超时机制加剧了不公平性的产生;然后,利用概率模型定量分析了TCP不公平性与MAC协议参数之间的关系,发现TCP流的公平性与TCP报文长度直接相关,并且增加MAC协议初始竞争窗口的大小能够有效提高公平性.据此,提出了一种根据TCP报文长度动态调节初始回退窗口大小的自适应回退MAC协议改进算法.理论分析和仿真表明,该算法在很大程度上可以有效缓解不公平性问题的产生,并且不会引起网络吞吐量的严重降低.

摘要:XML只能表示语法而不能表达形式化语义,这个问题导致XML数据集成以及扩展当前Web到语义Web非常困难.为了解决该问题,提出了一种XML语义定义语言XSDL,让XML文档作者清晰地表达XML文档中的语义信息,并提出了一种XML的模型论语义.这样,XML成为一种表达能力比资源描述框架(resource description framework,简称RDF)稍弱的Web知识表示语言,且XML数据可以保留语义转换到RDF数据.此外,还提出了XML文档的语义有效性和XML文档的推理问题,并把它们规约到描述逻辑语言∑HOIN(△)的知识库不可满足性问题.

摘要:资源发现是P2P应用所面临的最核心问题之一.相关的无结构P2P系统主要采用了查询消息泛洪和信息索引机制,这会造成严重的网络带宽负担以及巨大的索引维护开销.给出了一种无结构P2P环境下能够节约带宽、容易维护的自适应搜索策略PeerRank.PeerRank依据用户结点命中查询的历史信息赋予结点相应权值作为查询消息路由的依据,引导查询快速接近目标资源.自适应缓存机制和索引机制的引入使搜索性能大为加强.最后的实验表明,附带自适应缓存和索引的PeerRank以其高搜索成功率、多副本发现和很短的时间响应,能够显著地提高资源发现性能.

摘要:在结构化P2P网络上构建基于内容的发布/订阅系统,可以很好地支持大规模、高度动态的分布式应用.然而,现有的基于内容的路由协议在P2P网络上只能提供弱的可靠性保证.根据结构化P2P网络的路由协议的特点,设计了一种新型的基于内容的路由协议--基于编码区间的路由(identifier range based routing,简称IRBR)协议.IRBR协议具有良好的容错性,只要事件的发布者与订阅者之间在P2P网络中是可达的,则订阅者一定能够收到它所订阅的事件,且只收到一次.同时,该协议也比现有的协议具有更高的事件路由效率.在Pastry上开发了一个原型系统,模拟实验表明了该协议的效率和容错性.

摘要:Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.

摘要:提出一种具有大容量、低复杂性的鲁棒水印算法,主要适合于(但不局限于)JPEG图像和MPEG视频流的实时水印嵌入与检测,因为该算法直接运行于DCT(discrete cosine transform)块数据上.算法主要通过在感知范围内修改DCT块的中低频系数来调制块能量.在能量调制过程中,利用Watson视觉感知模型推导出一条准则,用于限制DCT系数的修改幅度.该系统具有较大的水印容量,可实现在512×512图像中嵌入2 048比特.实验表明,算法不仅具有较好的透明性,而且对一些常见的攻击(如高斯噪声、低通滤波、JPEG压缩、增减亮度等)和部分几何攻击(如线性偏移、剪切等)具有较好的鲁棒性.

摘要:为了同时检测量子随机错误和量子突发错误,提出了量子事件错误检错码.通过利用构造的错误图样,该码不但检测并纠正错误发生的事件类型,而且可以检测到错误发生的种类、随机错误的数量、错误发生的长度甚至错误发生的位置.

摘要:随机早检测(random early detection,简称RED)是IETF推荐部署的主动队列管理(active queue management,简称AQM)算法.RED存在参数难以配置、无法得到与流量无关的平均队长等问题.ARED(adaptive RED)是RED的自适应版本,它根据平均队长动态调节最大标记概率参数,从而得到稳定的平均队长.但ARED没有克服瞬时队列长度振荡问题,且在动态流量环境下性能明显降低.分析了ARED性能问题的原因,并提出了一种链路负载自适应的主动队列管理算法LARED(load adaptiveRED).LARED具有两个特点:自适应链路负载、快速响应队长变化.分析和仿真实验表明,与ARED等其他AQM算法相比,LARED在保持高链路利用率和低时延的同时可以得到稳定的瞬时队长,并且具有良好的响应性和鲁棒性.

摘要:Delaunay三角剖分已广泛地应用于计算流体力学、统计学、气象学、固体物理学、计算几何学等多个领域.随着无线Ad Hoc网络的发展,一些研究者提出了可以保证网络任意节点对之间分组顺利传输的几何路由协议,而这些协议的网络基础拓扑同样可以用Delaunay三角剖分的思想来实现.提出了一种新型的用于发现移动节点间通信路径的在线路由算法GLNFR(greedy and local neighbor face routing).利用局部构造法,构造出局部化的Delaunay三角剖分作为网络的基础拓扑.在该网络拓扑中进行的GLNFR路由算法可以保证节点间分组的顺利传输,对网络变化具有更好的可扩展性和适应性.在NS(network simulator)模拟器上仿真了该路由算法.结果表明,在分组成功传输率和路由分组开销性能方面,这一在线路由协议要优于先前提出的一些几何路由协议.

摘要:无线传感器网络是传感技术、计算技术和通信技术的融合.由于传感器节点的能量限制,能量有效性是设计无线传感器网络所关注的一个主要内容,并且已成为一个最大的挑战.提出了一种网络拓扑算法--一种动态、能量有效的层次分簇算法(DEEH).与其他算法不同,该算法无须知道传感器节点的任何本地信息.该算法可应用于更实际的大规模无线传感器网络,如节点具有不同的能量等级、不同的传输半径.将DEEH算法与经典的分簇算法LEACH相比较,仿真结果表明:当网络节点密度很大时,DEEH优于LEACH.同时,还考虑了网络中存在自私节点的情况,并分析了自私节点对网络分簇所带来的影响.在DEEH算法中引入机制设计理论,以克服网络中自私节点的影响.实验结果表明:采用机制设计理论,自私节点的占优策略真实地报告它们的能量.这一策略延长了网络的寿命,保证了拓扑结构的稳定性.

摘要:

摘要:对等(peer-to-peer)网络的非集中结构、良好的自治性及容错性等特征,使其可能成为Internet上有效的信息共享模型.然而,内容定位问题仍然是大规模P2P网络中信息共享所面临的挑战.SemreX系统是一种P2P网络环境下的文献检索系统.针对SemreX系统,提出一种基于语义相似度的P2P拓扑管理和查询路由算法.仿真实验结果表明,语义拓扑能够有效地提高系统的搜索效率.

摘要:Web services组合是Web services领域的研究热点,虽然已经提出了很多组合的方法,但从体系结构方面去研究Web services组合,则是一个新的研究角度.BPEL4WS是当前工业界主流的Web services组合描述语言.给出了基于BPEL4WS的Web services组合系统体系结构风格,并针对这种风格设计了体系结构描述语言WSC/ADL(Web services composition/architecture description language),WSC/ADL是基于体系结构的、自顶向下的Web services组合开发的研究基础,其组成包含描述Web services的服务构件、描述Web services之间交互的连接件以及建立服务构件和连接件实例联系的配置.给出了WSC/ADL的详细分析介绍和实例说明,并与相关工作进行了比较.

摘要:针对J2EE(Java 2 platform enterprise edition)应用服务器集成Web容器的传统实现方式存在的不足,提出一个两层结构的Web容器集成框架:外层独立于Web容器实现,满足管理工具、部署工具等其他模块与Web容器的交互;内层则是对特定Web容器的包装、扩展或改良.该框架已在J2EE应用服务器PKUAS(Peking Universitv Application Server)上得以实现.测试结果表明,该框架具有良好的可插拔性,实现了应用服务器配置和管理机制的统一,且性能良好.

摘要:合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式限制于(r,s)-CNF.对于正整数r≥3,有一个临界函数f(r),使得(r,f(r))-CNF中的公式都是可满足的,而(r,f(r)+1)-SAT却是NP-完全的.函数f是否可计算是一个开问题,除了知道f(3)=3,f(4)=4外,只能估计f(r)的界.描述了极小不可满足公式在CNF公式类之间转换中的作用.为使转换过程中引入较少的新变元,给出了CNF公式到3-CNF公式的一种新的转换方法,对于长度为l(＞3)的子句,仅需引入|l/2|个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法.

摘要:针对静态物化视图集动态适应能力的不足,提出一种动态cache优化算法DCO(dynamic cacheoptimization).它在保持静态算法获取最优物化集能力的基础上,将cache机制直观、快速的动态特性结合进来,以提高数据仓库的动态自适应性能.在cache机制具体实现中提出了一种新颖的空间申请方法,可以充分利用系统剩余空间提高查询响应性能.实验结果在表明算法有效、可行的同时,也显示出该算法可以在一定程度上克服静态物化集存在的空间-性能饱和效应(space-performance saturation effect,简称SPSE),使通过增加物化空间进一步提高数据仓库对查询的响应速度成为可能.

摘要:K-匿名化(K-anonymization)是数据发布环境下保护数据隐私的一种重要方法.目前,K-匿名化方法主要针对单一约束条件进行处理,而实际应用中涉及到大量的多约束条件,使K-匿名化问题更加复杂.如果简单地将单一约束K-匿名化方法应用到多约束情况,会造成大量的信息损失及过低的处理效率.根据多约束之间的关系,通过继承Classfly算法的元组概括过滤思想,提出多约束K-匿名化方法Classfly⁺及相应的3种算法,包括朴素算法、完全IndepCSet算法和部分IndepCSet的Classfly⁺算法.实验结果显示,Classfly⁺能够很好地降低多约束K-匿名化的信息损失,改善匿名化处理的效率.

摘要:时序约束是判断实时系统运行是否正确的重要规约.为了减小测试时由于对系统进行插装而产生的对实时系统行为的影响,提出了一种混合式监控方法.它对系统的时间干扰比纯软件方式小,并支持对系统的完全测试.此外,还提出一种基于WCET(worst-case execution time)分析技术的目标系统时间补偿方法,在精确地计算插入断言对目标系统的时间影响基础上,给出时间补偿.

摘要:Walsh函数在信号处理、图像处理、通信等众多领域有着广泛的应用.Walsh函数系是一个正交而完备的函数系,可以通过多种方法生成这一函数系.其中,Swick提出的复制方法应用最为广泛,该方法以Walsh函数的序码作为复制信息,可以复制出任意给定序数的Walsh函数.其本质是基于向量的处理,不适于类似快速变换等二维信号的处理.Walsh函数系可用Walsh方阵Wk表示.提出了基于W_k的行复制和块复制方法.基于对称性引入复制算子,并发现了一种新序(类Walsh序).利用Kronecker积推导了6种序的Walsh方阵的递推公式并绘制了它们的计算机图像,发现这些图像具有分形意义上的自相似结构.结果表明,基于矩阵的复制是比基于序码的复制更先进的复制方法.前者性能更优,适于快速变换的设计.而且,利用它发现了Walsh函数系的第4种对称的序:类Walsh序.通过分析和比较各种序的计算机图像,得出类Walsh序更适合作为Walsh序的逆反形式的猜想.

摘要: