摘要:对于二维矩形Packing 这一典型的NP 难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper 和Turton 提出的21 个著名的二维矩形Packing 问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC 机上的平均计算时间未超过7 分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.

摘要:单重线性循环程序的终止性问题已被广泛研究,而有关非线性循环终止性判定的结果甚少.利用不动点理论研究了n 维单重非线性循环的终止性问题,并建立了相应的符号判定算法.同时,对几类特殊循环的终止性进行了分析,得出了相应的结论.

摘要:为了满足在计算资源受限的环境下高维数据流处理的实时性要求,提出一种方法——基于GPU(graphicprocessing unit)的非规则流中高维数据流的处理模型和具体的可行架构,并分析设计了相关的并行算法.该六层模型是将GPU 处理数据的高宽带性能结合进滑动窗口中数据流的分析,进而在该框架下基于统一计算设备架构(compute unified device architecture,简称CUDA),使用数据立方模型以及降维约简技术并行分析了多条高维数据流的典型相关性.理论分析和实验结果均表明,该并行处理方法能够在线精确地识别同步滑动窗口模式下高维数据流之间的相关性.相对于纯CPU 方法,该方法具有显著的速度优势,很好地满足了高维数据流的实时性需求,可以作为通用的分析方法广泛应用于数据流挖掘领域.

摘要:讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1 个任务可以在任何一台机器上加工,第2 个任务只能在第1 个任务完成后在第2 台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2 个任务可以在第1 个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS 模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5 的多项式时间近似算法.对于NSHFS 模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3 的多项式时间近似算法.

摘要:基于树核函数,提出了从使用中心理论、集成竞争者信息和融入语义角色相关信息这3 个方面对结构化句法树进行动态扩展来提升中英文代词消解的性能.首先探索了3 种基本结构化句法树捕获方案,并使用SVMLight 中提供的卷积树核函数直接进行基于结构化句法树的相似度计算,从而完成指代消解任务;其次,在分析3 种结构化句法树捕获方案的基础上,从中心理论、竞争者信息和语义角色相关信息等几方面对捕获的结构化句法树进行了扩展;最后,通过ACE 2004 NWIRE 英文语料和ACE 2005 NWIRE 中文语料上的实验,说明了这些扩展能够提升代词消解的性能.

摘要:话题跟踪是一项针对新闻话题进行相关信息识别、挖掘和自组织的研究课题,其关键问题之一是如何建立符合话题形态的统计模型.话题形态的研究涉及两个问题,其一是话题的结构特性,其二是话题变形.对比分析了现有词包式、层次树式和链式这3 类主流话题模型的形态特征,尤其深入探讨了静态和动态话题模型拟合话题脉络的优势和劣势,并提出一种基于特征重叠比的核捕捉衰减评价策略,专门用于衡量静态和动态话题模型追踪话题发展趋势的能力.在此基础上,分别给出突发式增量式学习方法和时序事件链的更新算法,借以提高动态话题模型的核捕捉性能.实验基于国际标准评测语料TDT4,采用NIST(National Institute of Standards and Technology)提出的最小检测错误权衡系数评测法,并结合所提出的核捕捉衰减评价方法,对各类主要话题模型进行测试.实验结果显示,结构化的动态话题模型具有最佳的跟踪性能,且突发式增量式学习和时序事件链的更新算法分别给予动态话题模型0.4%和3.3%的性能改进.

摘要:为了提高基于短语的机器翻译系统的重排序能力,提出了一个基于源语言端的中心-修饰依存结构的重排序模型,并将该重排序模型以软约束的方式加入到机器翻译系统中.该排序模型提出了一种在机器翻译中应用句法树资源的方法,将句法树结构,通过将句法树映射成中心-修饰词的依存关系集合.该重排序模型在基于短语系统的默认参数设置下,显著地提升了系统的翻译质量.在系统原有的词汇化的重排序模型基础上,该重排序模型在翻译模型中融入了句法信息.实验结果显示,该模型可以明显地改善机器翻译系统的局部调序.

摘要:当前,boosting 集成学习算法研究主要集中于最大化弱学习器凸组合的间隔或软间隔,该凸组合几乎使用了生成的所有弱学习器,然而这些弱学习器间存在大量的相关性和冗余,增加了训练和分类过程的时空复杂度.针对这一问题,在LPBoost 基础上提出了一种选择性boosting 集成学习算法,称为SelectedBoost.在每次迭代生成新的弱学习器以后,通过计算新生成的弱学习器与已有弱学习器的相关度和差异度,并结合当前集成的强学习器的准确率来判断是否选择该弱学习器.另外,当前的一系列boosting 算法(如AdaBoost,LPBoost,ERLPBoost 等),本质上是基于已生成的1 个或者多个弱学习器来更新样本权重,但与弱学习器相比,强学习器更能代表当前的决策面.因此,SelectedBoost 通过在带约束的间隔最大化问题中引入更加严格的强学习器边界约束条件,使得该算法不仅参考弱学习器边界,同时还参考已生成的强学习器来更新样本权重,进而提高算法的收敛速度.最后,与其他有代表性的集成学习算法进行实验比较,结果表明,该方法在收敛率、分类准确性以及泛化能力等方面均具有比较明显的优势.

摘要:随着云计算的发展,云数据库的重要性和价值日益显现.介绍了云数据库的特性、影响、相关产品.详细讨论了云数据库领域的研究问题,包括数据模型、系统体系架构、事务一致性、编程模型、数据安全、性能优化和测试基准等.最后讨论了云数据库未来的研究方向.

摘要:不一致数据无法正确反映现实世界,其上的查询结果内含错误或矛盾,而现有的很多不一致数据查询处理相关研究都存在信息丢失的问题. AQA(annotation based query answer)针对这一问题采用信任标签在属性级别上区分一致和不一致数据,避免了信息丢失.但AQA 假设记录在依赖左边属性上的分量可信,且只针对函数依赖一种约束,具有应用局限性.在综合约束(函数依赖、包含依赖和域约束)范围内、不确定属性任意的情况下扩展了AQA,重新审视了AQA 的数据模型及其上的查询代数,讨论了任意约束在查询结果上的蕴含约束计算问题.实验结果表明,扩展后的AQA非连接类查询的性能和普通的SQL基本相同,连接查询经优化后性能接近普通SQL查询,但AQA不丢失信息,与部分同类研究相比有很大优势.

摘要:提出了一种数据流预测算法Predictor.该算法为每个待匹配的一般形式的情节规则分别使用了一个自动机,通过单遍扫描数据流来同时跟踪这些自动机的状态变迁,以搜索每个规则前件最近的最小且非重叠发生.这样不仅将无界的数据流映射到有限的状态空间,而且避免了对情节规则的过于匹配.另外,算法预测的结果是未来多个情节的发生区间和发生概率.理论分析和实验评估表明,Predictor 具有较高的预测效率和预测精度.

摘要:提出了一种快速的稀有类检测算法——CATION(rare category detection algorithm based on weightedboundary degree).通过使用加权边界度(weighted boundary degree,简称WBD)这一新的稀有类检测标准,该算法可利用反向k 近邻的特性来寻找稀有类的边界点,并选取加权边界度最高的边界点询问其类别标签.实验结果表明,与现有方法相比,该算法避免了现有方法的局限性,大幅度地提高了发现数据集中各个类的效率,并有效地缩短了算法运行所需要的运行时间.

摘要:在无线网络中,媒介的广播、共享特性使其易于受到干扰性质的拒绝服务攻击,严重影响着网络的性能和安全.分析了当前存在的干扰攻击测度标准和攻击模型;从干扰攻击的检测、防御以及干扰源定位3 个方面对当前具有代表性的研究工作进行了详细的分析和总结.最后给出未来可能的研究方向和研究重点.

摘要:提出了一种能量高效均衡、非均匀分簇和簇间多跳路由有机结合的无线传感器网络分布式分簇路由协议DEBUC(distributed energy-balanced unequal clustering routing protocol).该协议采用基于时间的簇头竞争算法,广播时间取决于候选簇头的剩余能量和其邻居节点的剩余能量.同时,通过控制不同位置候选簇头的竞争范围,使得距离基站较近的簇的几何尺寸较小.这样,网络中不同位置节点之间的簇内和簇间通信能耗得以互相补偿.DEBUC 采用簇间多跳路由,根据节点剩余能量、簇内通信代价和簇间通信代价,每个簇头在邻居簇头集合中运用贪婪算法选择其中继节点.仿真实验结果表明,DEBUC 能够有效地节约单个节点能量、均衡网络能耗、延长网络生存周期.

摘要:研究了支持相继干扰消除(successive interference cancellation,简称SIC)的无线网络中链路调度算法的设计与分析.首先,为刻画SIC 的顺序检测特性,提出M-level 非累积干扰模型与有序累积干扰模型.然后,由于两种模型下的调度均为NP-hard 问题,研究了近似调度的性能:(1) 给出了一种工作于有序累积干扰模型的调度机制,其近似比为O(g),其中,g 为网络的链路多样性指数;(2) 给出了一种工作于M-level 非累积干扰模型的调度机制,其近似比为常数.最后,通过仿真实验考察了SIC 对调度性能的影响.

摘要:利用自然图像信号的分段统计稳态性可以有效地对图像信号进行建模.其分段统计稳态区域往往具有非规则的形态.采用规则窗口对图像统计稳态区域内的统计量进行估计存在较大的误差.提出一种基于概率描述的隐式分段自回归模型来刻画分段统计稳态区域形态,并基于该模型提出了一种改进的图像插值算法.实验结果表明,该方法可以较好地改善插值图像中在边缘处的模糊、振铃和噪声等瑕疵现象.

摘要:基于信任委托的思想,提出一种移动环境下的跨可信域的直接匿名(direct anonymous attestation,简称DAA)证明方案,采用代理签名技术和直接匿名证明方法,实现对移动终端在多可信域之间漫游时的可信计算平台认证,并在认证过程中协商会话密钥,增强了远程证明体系的安全性.利用Canetti-Krawczyk(CK)模型对方案的认证协议的认证安全性和匿名安全性进行了形式化分析和证明.分析表明,该方案能够抵抗平台伪装攻击和重放攻击,其性能适用于无线网络环境.

摘要:针对Http 洪泛Web DDoS(distributed denial of service)攻击,提出了一种检测机制.该机制首先采用型方法量化处理用户访问的网页序列,以得到用户访问不同网页的实际点击概率分布;然后,利用大偏差统计模型分析了用户访问行为的实际点击概率分布与网站先验概率分布的偏差;最后,依据大偏差概率检测恶意DDoS 攻击.对该机制的性能进行仿真,结果表明,正常用户的大偏差概率大于恶意攻击者,并且大部分正常用户的大偏差概率大于10^-36,而大部分恶意攻击者的大偏差概率则小于10^-40.由此,该机制能够有效地检测Http 洪泛Web DDoS 攻击,当检测门限设置为10^-60 时,其有效检测率可达97.5%,而误检率仅为0.6%.另外,将该机制与基于网页转移概率的检测方法进行性能比较,结果表明,该检测机制的检测率优于基于网页专业概率的检测机制,并且在误检率小于5%的情况下,该机制的检测率比现有检测机制提高0.6%.

摘要:自动聚焦是全自动显微成像中的关键技术.为了解决在极低内容密度(稀疏内容)情况下传统聚焦方法无法成功找到焦平面的问题,提出一种基于图像内容重要度加权的聚焦函数增强算法.该算法利用聚焦过程中当前图像和参考图像中对应像素沿光轴方向的梯度变化规律对像素进行分类,并根据不同像素对图像清晰程度判决的贡献大小自适应调整当前像素的重要度因子,通过这种方式增强了图像内容像素的计算权重并有效抑制了镜头杂质及背景噪声,极大地增强了聚焦曲线的陡峭度.在此基础上,采用图像分块的方式来克服显微镜Z 轴机械系统误差对算法性能的影响并降低算法复杂度.实验结果表明,在图像内容非常稀疏的情况下,该算法的聚焦成功率高达90%,而传统聚焦算法的成功率仅为24%.

摘要:图像语义检索的一个关键问题就是要找到图像底层特征与语义之间的关联,由于文本是表达语义的一种有效手段,因此提出通过研究文本与图像两种模态之间关系来构建反映两者间潜在语义关联的有效模型的思路.基于该模型,可使用自然语言形式(文本语句)来表达检索意图,最终检索到相关图像.该模型基于稀疏典型性相关分析(sparse canonical correlation analysis,简称sparse CCA),按照如下步骤训练得到:首先利用隐语义分析方法构造文本语义空间,然后以视觉词袋(bag of visual words)来表达文本所对应的图像,最后通过Sparse CCA 算法找到一个语义相关空间,以实现文本语义与图像视觉单词间的映射.使用稀疏的相关性分析方法可以提高模型可解释性和保证检索结果稳定性.实验结果验证了Sparse CCA 方法的有效性,同时也证实了所提出的图像语义检索方法的可行性.

摘要:四边形网格的结构特点要求网格单元满足全局一致性,难以取得网格质量与表达效率之间的平衡.为此,提出一种基于全局的各向异性四边形主导网格重建方法,可生成网格质量好且冗余程度低的四边形网格.重建过程以主曲率线为基本采样单元,首先计算模型表面的主曲率场并对主曲率场积分,得到密集的主曲率线采样;再根据贪心算法,利用几何形体自身的各向异性找出冗余度最高的主曲率线并予以删除;如此循环,直至达到理想的采样密度.该重建方法适用于任意拓扑网格模型,所得到的各向异性四边形主导网格在网格模型分辨率下降时,由于始终保留重要主曲率线,从而可以更好地保持模型特征.同时,在基于贪心算法的渐进式主曲率线删除过程中,可产生分辨率连续可调的四边形主导网格.

摘要:基于学习的超分辨率方法通常根据低分辨率图像从样本库中选取若干特征相似的匹配对象,再使用优化算法进行超分辨率估计,但其结果受匹配对象的质量限制,并且匹配特征一般只选择图像的几何结构信息,匹配准确性较低.提出了稀疏字典编码的超分辨率模型,将高、低分辨率图像特征块统一进行稀疏编码,建立高、低分辨率图像的稀疏关联,同步实现匹配搜索和优化估计,突破了上述方法的限制.应用形态分量分析法提取图像的特征数据,提高了特征匹配的准确性,并同步实现超分辨率重建和降噪功能.优化方法采用稀疏K-SVD算法以提高稀疏字典编码的计算速度.采用自然图像进行实验,与其他基于学习的超分辨率算法相比,重建所得到的图像质量更优.

摘要:提出一套基于自适应网格变形的图像编辑算法框架,包括图像中特征物的平移、旋转和变形,以及保持特征物的任意几何边界图像适应.该算法将图像表示为基于图像特征的自适应三角网格,由此将图像编辑问题转换为带约束的网格变形问题.网格变形由一个二次型能量函数所控制,特征物的平移、旋转和变形可以表述为该能量优化问题的约束;代表特征物的三角网格在网格变形过程中只允许发生刚性变换.该能量优化问题的全局最优解可以通过求解1 个或多个稀疏方程组得到.实验结果表明,该算法效果理想、鲁棒性好、运行效率高,可以有效地应用于图像处理软件中.