怎样“求空间内一点到其它所有点的距离之和最小”？首先将这个问题形式化：
公式代码：
\min f(x,y) = \min
\sum_i
\sqrt
{(x - x_i)^2 + (y - y_i)^2}
这里是距离之和，而不是平方和。Kmeans聚类中用的评价标准是平方和，如果只有一个类中心，那么可以直接求偏导得到使得平方和最小的点就是中心。这里问题与平方和的解是不是一样的，比如三角形到三个顶点距离之和最短的点就是费马点。
这里可以用最优化方法中的“搜索”来求解，这一系列方法包括了梯度下降法、牛顿法和共轭梯度法等。在这里用梯度下降法是最简单的，通过这个例子我也明白了为什么实际运用中梯度下降法是应用最广的。相比梯度下降法，牛顿法需要求Hesse矩阵，还是相对麻烦不少。梯度下降法搜索步骤就是每一步都向导数的逆方向将自变量前进一个步长（可变），在这里导数方向就是
公式代码：
\nabla f(x,y) =
\left[
\begin{array}
{lcr}
\displaystyle
\sum_i \frac{x
- x_i}{\sqrt{(x
- x_i)^2 + (y - y_i)^2}} \\
\displaystyle
\sum_i \frac{y
- y_i}{\sqrt{(x
- x_i)^2 + (y - y_i)^2}}
\end{array}
\right]
梯度下降法也有它使用起来让人比较为难的地方，那就是步长很难选取，课本上所给出的例子一般都是针对较简单表达式提出的可变步长计算。在本问题的求解中为简单起见，步长是取的定值。整个过程用Python3实现（起初想用R来做，但是R没法调试……归根结底还是功力不够）实现，结合了scipy和matplotlib两个包，结果看起来还是比较靠谱：
最后附上源代码：
from scipy import *
import pylab
def f(p, pts):
return sum(sum((p - pts) ** 2, axis=1) ** 0.5)
def fd(p, pts):
dx = sum((p[0] - pts[:, 0]) / sum((p - pts) ** 2, axis=1) ** 0.5)
dy = sum((p[1] - pts[:, 1]) / sum((p - pts) ** 2, axis=1) ** 0.5)
s = (dx ** 2 + dy ** 2) ** 0.5
dx /= s
dy /= s
return array([dx, dy])
pts = rand(10, 2)
x = array([0, 0])
t = 0.1
xstep = x
for k in range(100):
y = f(x, pts)
xk = x - t * fd(x, pts)
yk = f(xk, pts)
if y - yk > 1e-8:
x = xk
y = yk
elif yk - y > 1e-8:
t *= 0.5
else:
break
xstep = vstack((xstep, x))
print(x, y)
pylab.plot(pts[:, 0], pts[:, 1], 'bo')
pylab.plot(xstep[:, 0], xstep[:, 1], 'ro')
pylab.plot(xstep[:, 0], xstep[:, 1], 'k-')
pylab.xlabel('iter = %d, Min =
%.3f, p = (%.3f, %.3f), t =
%f' % (k, y, x[0], x[1], t))
pylab.show()
|
