最小二乘法三维(k维)直线拟合

上篇文章已经实现了二维直线\(Ax+By+C=0\)的拟合算法。如果要拟合三维直线怎么办?首先,方程\(Ax+By+Cz+D=0\)是不可以的,因为他是三维空间中的一个平面。如果要表达一条直线,需要两个三维平面的联立,似乎也不是个好办法。这里我们可以采用直线的“点+向量”方程\(l = A + dD\)的方式。其中A为直线上一点,D为直线方向向量。在计算几何中,这是一种常用的表达方式。

已知,采样点$$\{(x_1,y_1),(x_2,y_2),…,(x_n,y_n)\}$$欲求直线\(l = A + dD\),使得各点到直线的距离的平方和最小。

采样点\(X_i(x_i,y_i)\)到直线\(l\)的距离可以用\(X_i\)到\(A\)的向量 \(Y_i = X_i -A\) 与\(Y_i\)在直线上的投影\((Y_i^TD)D\)做差求得。因此可以列目标方程为

$$f = \sum (Yi^2 – (D\cdot Y_i)^2)$$

解题的技巧在与对上式的重组。先求 A。\( \frac {\partial f}{\partial A} = \frac {\partial f}{\partial Y} \cdot \frac {\partial Y}{\partial A} = – \frac {\partial f}{\partial Y} =0 \)

$$f = \sum (Y_i^2 – (D^TY_i)^2) $$

$$\frac {\partial f}{\partial Y} = \sum(2Y_i – 2DD^TY_i ) =2 (I-DD^T) \sum Y_i =0$$

可以得出 \(\sum Y_i =\sum (X_i-A)=0\),解出 \( A = \frac {\sum X_i }{n} = \bar X\)。即直线经过所有点的中心点。

将\(f\)改写为$$f = \sum (Y_i^2 – (Y_i^TD)^2) =\sum (D^TY_i^TY_iD – D^TY_iY_i^TD ) = D^T \sum ((Y_i^TY_i)I – Y_iY_i^T)D$$

这里要解释一下 因为约束了 \(D^TD=1\),所以\(Y_i^2 = D^TY_i^TY_iD^T\)。

令 \(S =\sum ((Y_i^TY_i)I – Y_iY_i^T) \), 简化成

$$f = D^T SD; ||D||=1$$

这个函数的形式与前一篇文章一样,f的最小值为S对应最小特征值时的特征向量。这里不再重复说明。

总结一下,本文提出的直线方程具有一般性,不仅适用于二维、三维空间直线,更能适用于k-D直线。因此,可以应用与其他业务领域,如统计、机器学习算法等等。

发表评论

电子邮件地址不会被公开。