11111
1.什么是距离阈值?我们需要选择距离阈值t,使点是合群点的概率为α。这种计算要求清楚合群点到模型的距离概率分布。实际中,距离阈值靠经验选择。但是,如果假设测量误差服从高斯分布,零均值均方差σ,那么可以计算t。这种情况下,点的距离的平方,d2⊥是高斯变量的平方和,它服从χ2m分布,m是自由度,m等于模型的共轭维度。对于直线,共轭维度是1--只需测量到直线的垂直距离。如果模型是一个点,共轭维度是2,距离的平方是测量误差x和y的平方和。随机变量χ2m的值小于k2的概率根据累计χ2m分布
F(k2)=∫k20χ2m(ζ)dζ确定。根据分布累计,(4.17)
通常α选择设定为0.95,即点是合群点的概率是95%。这表示,合群点被错误排斥的概率是5%。下表列出本书中涉及模型在α=0.95时的t值。
2.采样次数?尝试所有采样通常计算上是不可行也没有必要。当采样次数N足够大,以保证由s个点组成的随机样本中至少有一次没有离群值的概率为p。通常p设定为0.99,假设w是任意选择的点是合群点的概率,因此ε=1-w表示点是离群点的概率。那么至少需要N次选择(每次s个点),其中(1-ws)N=1-p,
所以,(4.18)
表格举例在给定s和ε时并保证至少有一次没有离群值的概率是0.99时所需采样数N;
例4.4.对于图4.7中12个数据点的直线拟合问题,其中有两个点是离群点,所以ε=2/12=1/6。根据表格,当最小数据集大小s=2,至少N=5次采样才能满足要求。如果与每对点均计算的花费相比,需进行66次采样。
注意:
i.采样次数与离群值比例有关而不是数量。这代表,所需采样次数可能比离群数量要小。所以,即使离群值数量非常大时,采样的计算花费也可接受。
ii.对于给定s和ε,采样数量随最小数据集增大而增加。可能会有人认为采用大于最小数据集的数量会更具优势,例如本例直线拟合时采用三个或更多的点,因为这样会获得更好的直线估计,并且测量的支持数更加准确的反应真实的真实数量。但是,增加采样数量会导致计算花费一般远超过测量支持带来的好处。
3.可接受的一致集大小是多少?在给定离群值比例时,如果一致集大小接近于合群值数量时,终结迭代,也就是说对于n个数据,T=(1-ε)n。对于图4.7直线拟合例子,ε的保守估计使ε=0.2,因此T=(1-0.2)12=10。
自适应决定采样次数.通常来说,离群值数据的比例是未知的,在这种情况下,使用最糟糕情况的ε估计值初始化算法,随着更大的一致集被发现而更新估计值。例如,如果最糟糕的情况是ε=0.5,但如果发现合群点的一致集站数据的80%时,那么估计更新为ε=0.2。
这种自适应方法非常起作用,实际中也能覆盖采样次数和终结算法的问题。初始ε可以选择1.0,这种情况下初始N是无穷大。所以,在(4.18)使用一个保守的概率p如0.99是非常明智的。
这一过程中唯一的缺点是,合群和离群数据的分类是不可更改的。当模型最优化满足一致集时,如果把距离阈值应用到该新模型,很可能又有一些点称为合群点。例如,图4.8中根据RANSAC选择的直线<a,b>,有四个支持点,在最优拟合这四个点后,现在有10个点被正确分类为合群点。这两步:最优拟合合群点;使用4.17重新分类合群点;然后不断迭代直到合群点数收敛。根据合群点到模型的距离来加权最小二乘的拟合方法经常在该步骤使用。
在RANSAC中,根据最小集合得到的模型,以数据点在距离阈值中的数量给予分数。另一种方法是通过数据中所有点的距离中位值打分,然后选择中位值最小的模型。这就是最小中位值平方估计LMS,同RANSAC方法一样,最小子集的采样是根据(4.18)得到的采样次数选择的。LMS的优势在于,它对于误差变量不需要设置阈值或者先验。LMS的劣势在于,如果超过一半的数据都是离群,它将失败,因为中位距离是离群值。解决的办法是,使用离群比例决定所选择的距离。例如,如果有超过50%的离群点,那么在中位值以下的距离都应当被使用。
RANSAC和LMS算法都能够处理离群值比例较大的情况。如果离群点数量很小,那么其他鲁棒方法也是足够有效。这包括删短板方法,即每个点轮流被删除并且拟合模型满足剩余数据;迭代加权最小二乘,数据点对拟合的影响需要其残差进行加权。一般来说,这些方法并不推荐。
联系客服