一维投影方差分割

为了研究上面提出的这个问题,还是把问题先拉回到一维直线点集上。

在一条直线 \(l\)上分布的点集\(A=\{ a_i ∈ l | i=1,2,…N\}\) ,如何选择一个分割点 \(x\),使得这些点到这个分割点的距离\(d\)方差最大。不妨将直线 \(l\)与\(x\)轴重合,点集自然变换成 \(A=\{ x_i ∈ l | i=1,2,…N\}\) 。

距离方差可描述为:

\[ H = \sum\limits_{i = 1}^N {{{({x_i} – x)}^2}} \]

对此式进行整理,并求其极值。

\[ H = \sum\limits_{i = 1}^N {{{({x_i} – x)}^2}} = N \cdot {x^2} – 2 \cdot x \cdot \sum\limits_{i = 1}^N {{x_i} + \sum\limits_{i = 1}^N {x_i^2} } \]

显然当

\[ x = – \frac{b}{{2a}} = – \frac{{2\sum\limits_{i = 1}^N {{x_i}} }}{{2N}} = \frac{1}{N}\sum\limits_{i = 1}^N {{x_i}} \]

时\(H\)存在极值。也即:这个分割点\(x\)要选择为点集\(A\)的质心。