基于概率抽样一致性的基础矩阵估计算法

随机抽样一致性算法是应用最广泛的鲁棒性基础矩阵估计算法之一.针对随机抽样一致性算法效率低的问题,提出一种基于概率分析的随机抽样一致性算法.该算法减少首次抽样的次数,利用预检验技术确定一个较优的模型子集,通过定义样本属于该较优模型的概率来选择内点概率大的样本子集,并通过多次迭代得到一个只包含内点样本的子集.模拟数据和真实数据的基础矩阵估计实验表明,算法在计算效率和精度上均优于随机抽样一致性算法.     

基于集值映射的拟划分近似空间中近似算子

在含有缺省值的不完备性信息系统中,一部分对象无法确定的归入特定的类中,此时论域的邻域系统对于论域无法形成覆盖,只能形成论域的不完全划分。从概念上讲,对论域的不完全划分与对论域的覆盖都是对论域的拟划分的两个特例。作为基于覆盖的粗糙集模型的一种推广,将讨论基于拟划分的粗糙集模型中上下近似算子的若干性质,并且讨论了这个模型下近似算子的表示问题。     

基于特定失效概率的软件恢复策略分析

对软件的两阶段失效与恢复模型进行了分析,基于特定失效概率求解最优恢复时间间隔,并利用半马尔可夫过程,得到特定失效概率下的平均恢复成本。为了将恢复成本降到更低,采用了嵌套的基于时间的软件恢复策略,同时考虑应用级和系统级的恢复,并求得了特定失效概率下的最大应用级恢复次数、恢复时间间隔序列以及最低年平均恢复成本。     

划分交互式箱粒子概率假设密度滤波法

针对现有的多机动目标追踪问题,将交互式多模型(interacting multiple model,IMM)思想与箱粒子概率假设密度滤波器(box probability hypothesis density filter,Box-PHD)相结合,并针对箱粒子在区间密集杂波等复杂环境下箱体偏大,所导致的箱粒子冗余和目标跟踪位置估计不精确等问题,引入箱粒子划分技术,提出一种划分交互式概率假设密度滤波(partitioned interacting multiple model probability hypothesis density filter,PIMM-Box-PHD)算法,来处理椭圆形多机动目标的跟踪问题。该算法首先在预测阶段针对多目标的机动问题引入IMM预测,利用多模型交互方法来解决目标运动时模型失配问题;其次,利用箱划分技术将预测得到的箱粒子划分为大小和权值相同的多个子箱,以提高目标位置估计精度;最后,利用Box-PHD滤波对划分后的小箱粒子集进行区间量测更新。利用实验验证了PIMM-Box-PHD算法在多机动目标跟踪方面的良好性能,以及相较于IMM-Box-PHD算法在目标位置估计方面的优势。     

基于中间件的领域软件开发方法

现代信息管理系统的复杂性使得传统软件开发方法难以满足要求。中间件及可重用构件的产生为软件开发带来新的提高。提出基于中间件的特定领域软件开发方法，针对特定领域的软件系统需求，通过领域分析，形成领域模型，以中间件为基础划分和形成可重用构件库，最终集成目标系统；并给出了特定域中的实例。     

基于聚类模式的推荐算法研究

经典的协作式过滤算法基于记忆的非参数局部模型,该模型应用最近邻算法（K-nearest neighbors,KNN）技术,把目标用户近邻对于目标推荐项的喜好,作为向该用户进行有效推荐的标准。该方法在预测时需要较长的运算时间,并且在特定参数的限制下,不能保证对所有的用户进行有效预测。为了解决以上问题,介绍1种基于聚类模式的新的推荐方法。该算法首先假设目标用户和推荐项均能以一定的概率划归于不同的用户模式和推荐项模式中;通过计算各个用户模式对于各个推荐项模式的评分,以及用户属于不同用户模式的概率,推荐项属于不同项目模式的概率;从而产生目标用户对于具体推荐项的预测评分。通过与经典的协作式过滤推荐算法结果的对比,该方案可以在较短的时间预测所有用户对于所有推荐项的评分,并且其推荐效果与其他方法对比有了很好的改进。     

基于GMM多维概率输出的SVM话者确认

提出一种结合统计模型与区分性模型优点的说话人确认方法:基于GMM多维概率输出的SVM话者模型的说话人确认.以目标说话人的GMM模型对一条语音的不同特征分量的概率输出作为特征参数,建立目标说话人的SVM模型.在NIST'05 8conv4w-1conv4w数据库上的实验表明该方法的有效性.     

基于多因素贝叶斯的遮挡目标检测

复杂场景中的遮挡现象会造成目标外观信息损失,致使检测过程中容易出现目标遗漏。通过分析目标表示对特定布局的依赖性,提出一种基于多因素贝叶斯的遮挡目标检测方法。首先,使用部件模型提供目标局部区域的候选提议,然后,根据空间布局关系估计部件的可见性概率,并同时考虑目标部件的外观特征和形变位置,最后,构建基于外观、形变、可见性因素的贝叶斯模型,并采用最大化曲线下方面积设计目标检测评价函数,完成多因素权重学习。实验结果证明在PASCAL数据集中的有效性,优于目标检测的现有方法。     

NU2RA:一种路网中不确定移动对象范围查询分析方法

目前移动对象的各类查询研究大多假设对象的位置确切可知,但实际上除了更新时刻外,其他时间对象的位置只是一个可能的范围.因而大多数基于确切位置的查询算法并不可行.而现有的涉及不确定性的查询方法大多仅针对自由移动的不确定查询或者不确定目标.针对道路网中查询和目标位置均不确定的情况,提出了一种NU2RA分析方法.根据查询范围对网络进行划分,用分布码表示目标的可能分布,得到不确定目标与不确定查询范围的22类拓扑关系,并且给出了目标在不确定查询范围内的概率计算方法.该方法不依赖于具体的不确定移动对象模型,对不确定历史轨迹和不确定的近期将来运动趋势同样适用.     

一种基于概率地图的移动机器人最优期望时间目标搜索

在基于概率地图的移动机器人目标搜索规划中,目标在工作环境中的存在概率通常被设置为服从离散均匀分布,进而采用路径长度指标优化搜索任务的全局路径.然而,真实工作空间中的概率分布绝大多数并不服从均匀分布,这将导致所获搜索策略并非预期的最短时间.对此,根据实际工作环境构建概率测算模型,并基于该模型构建概率地图,进而提出一种以预期最短时间为优化指标的机器人目标搜索路径规划方法.该方法采用分层规划模式,在上层拓扑地图中进行拓扑点序列规划,而在下层特征地图中进行拓扑点间局部路径规划.实验结果表明,该方法可以显著缩短移动机器人目标搜索的期望时间,更适用于目标不服从均匀分布的工作环境.     

Proportional sampling strategy: guidelines for software testing practitioners

Recently, several sufficient conditions have been developed that guarantee partition testing to have a higher probability of detecting at least one failure than random testing. One of these conditions is that the number of test cases selected from each partition is proportional to the size of the partition. We call such a method of allocating test cases the proportional sampling strategy. Although this condition is not the most general one, it is the most easily and practically applicable one. In this paper, we discuss how the proportional sampling strategy can be applied effectively in practice. Some practical issues that need to be attended are identified and guidelines to deal with these issues are suggested.     

Brahms: Byzantine resilient random membership sampling

We present Brahms, an algorithm for sampling random nodes in a large dynamic system prone to malicious behavior. Brahms stores small membership views at each node, and yet overcomes Byzantine attacks by a linear portion of the system. Brahms is composed of two components. The first is an attack-resilient gossip-based membership protocol. The second component extracts independent uniformly random node samples from the stream of node ids gossiped by the first. We evaluate Brahms using rigorous analysis, backed by simulations, which show that our theoretical model captures the protocol’s essentials. We study two representative attacks, and show that with high probability, an attacker cannot create a partition between correct nodes. We further prove that each node’s sample converges to an independent uniform one over time. To our knowledge, no such properties were proven for gossip protocols in the past.     

分布式采样理论综述

采样是一类基本的计算问题.从一个解空间中依特定概率分布进行随机采样,这一问题在近似计数、概率推断、统计学习等方面都有着诸多重要的应用.在大数据时代,采样问题的分布式算法与分布式计算复杂性受到越来越多的关注.近年来,有一系列的工作对分布式采样理论展开系统性的研究.综述了分布式采样的重要结论,主要包括有严格理论保障的分布式采样算法、采样问题在分布式模型上的计算复杂性以及采样与推断等问题在分布式计算模型中的相互联系.     

Hadoop平台的海量数据并行随机抽样

在“信息爆炸”的当今社会,海量数据对数据挖掘提出新的挑战。在数据挖掘转向云计算平台实现并行化的同时,研究并行化数据随机抽样进一步降低处理的数据规模。提出一种单次扫描即可实现清理脏数据并实现等概率抽样的mapreduce并行抽样算法。在hadoop平台上实现并与普通随机抽样方法进行比较,得出其时间效率非常高,是一种行之有效的方法。为以后数据挖掘中的抽样研究和推动数据挖掘在海量数据下的发展奠定良好基础。     

Impulse-doublet sampling of random waveforms

For discrete time systems, the sampling rate is an important design issue. On the one hand, a sampling rate below the Nyquist rate results in spectral aliasing, on the other hand, a sampling rate chosen higher than necessary increases the computational burden. We show in this paper that aliased spectra, arising from sampling a random process below the Nyquist rate, may be completely eliminated. We show that a deterministic or random waveform that is sampled at a rate less than the classical Nyquist rate may be successfully reconstructed if two arbitrarily closely spaced samples are retained each sampling instant. A convergence proof is given for the random waveform case. We suggest a diagonally loaded maximum likelihood estimator approach to reduce the reconstruction errors resulting from timing jitter between the pairs of impulse samples as an area of future research.     

Sampling streaming data with replacement

Simple random sampling is a widely accepted basis for estimation from a population. When data come as a stream, the total population size continuously grows and only one pass through the data is possible. Reservoir sampling is a method of maintaining a fixed size random sample from streaming data. Reservoir sampling without replacement has been extensively studied and several algorithms with sub-linear time complexity exist. Although reservoir sampling with replacement is previously mentioned by some authors, it has been studied very little and only linear algorithms exist. A with-replacement reservoir sampling algorithm of sub-linear time complexity is introduced. A thorough complexity analysis of several approaches to the with-replacement reservoir sampling problem is also provided.     

基于拟随机序列的三维模型表面采样方法

三维模型检索中的形状分布算法使用伪随机序列进行采样,导致检索精度较低、检索结果不稳定。该文采用拟随机序列中的Halton序列在[0, 1]区间内产生分布较均匀的随机数,利用数学变换将其转换为采样空间的随机数进行采样。三维模型检索对比实验结果表明,该方法可以提高检索精度,使检索结果更稳定。     

选取最大可能预测错误样例的主动学习算法

通过选取并提交专家标注最有信息量的样例,主动学习算法中可以有效地减轻标注大量未标注样例的负担.采样是主动学习算法中一个影响性能的关键因素.当前主流的采样算法往往考虑选取的样例尽可能平分版本空间.但这一方法假定版本空间中的每一假设都具有相同的概率成为目标函数,而这在真实世界问题中不可能满足.分析了平分版本策略的局限性.进而提出一种旨在尽可能最大限度减小版本空间的启发式采样算法MPWPS(the most possibly wrong-predicted sampling),该算法每次采样时选取当前分类器最有可能预测错误的样例,从而淘汰版本空间中多于半数的假设.这种方法使分类器在达到相同的分类正确率时,采样次数比当前主流的针对平分版本空间的主动学习算法采样次数更少.实验表明,在大多数数据集上,当达到相同的目标正确率时,MPWPS方法能够比传统的采样算法采样次数更少.     

基于NT技术中链路时延推测算法的分析研究

在研究了当前时延推测算法的基础上,将高斯混合模型推广到有限混合模型,使得算法可以同时推测多条链路的时延分布,利用重要性抽样技术增大研究事件出现的概率,再进行抽样并对样本空间进行调整,保证了指标的无偏性和有效性,同时降低了计算的复杂度,因此此方法具有广泛的适用性。最后在NS2平台上仿真验证,说明该算法是可行的。     

基于限定区域数据取样的密度聚类算法

传统密度算法DBSCAN与DBRS的缺点在于时间性能和聚类精度均较低,为此,提出一种结合限定区域数据取样技术的密度聚类算法——DBLRS。该算法在不增加时间和空间复杂度的基础上利用参数Eps查找核心点的邻域点和扩展点,并在限定区域(Eps,2Eps)内进行数据抽样。实验结果表明,限定区域内选取代表点进行簇的扩充降低了大簇分裂的概率,提高了算法效率与聚类精度。