一個利用Tensorflow求解幾何問題的例子

03-05

知乎上有一個問題，內容是已知空間三個點的坐標，求三個點所構成的圓的圓心坐標（編程實現）？

根據圓的定義，這道題的核心就是找到一個點，到已知的三個點的距離相等，利用數學知識可以求解如下：

例如：給定a（x1,y1） b（x2,y2） c（x3,y3）求外接圓心坐標O（x，y）

1. 首先，外接圓的圓心是三角形三條邊的垂直平分線的交點，我們根據圓心到頂點的距離相等，可以列出以下方程：
(x1-x)*(x1-x)+(y1-y)*(y1-y)=(x2-x)*(x2-x)+(y2-y)*(y2-y);
(x2-x)*(x2-x)+(y2-y)*(y2-y)=(x3-x)*(x3-x)+(y3-y)*(y3-y);
2.化簡得到：

2*(x2-x1)*x+2*(y2-y1)y=x2^2+y2^2-x1^2-y1^2;
2*(x3-x2)*x+2*(y3-y2)y=x3^2+y3^2-x2^2-y2^2;
令:A1=2*(x2-x1)；
B1=2*(y2-y1)；
C1=x2^2+y2^2-x1^2-y1^2;

A2=2*(x3-x2)；
B2=2*(y3-y2)；
C2=x3^2+y3^2-x2^2-y2^2;
即:A1*x+B1y=C1;
A2*x+B2y=C2;

3.最後根據克拉默法則：
x=((C1*B2)-(C2*B1))/((A1*B2)-(A2*B1))；
y=((A1*C2)-(A2*C1))/((A1*B2)-(A2*B1))；

當然，我們今天不是來學習數學公式和數學推導的。Tensorflow是google開源的一款深度學習的工具，其實我們可以利用Tensoflow提供了強大的數學計算能力來求解類似的數學問題。

這道題，我們可以利用梯度下降演算法，因為圓心是一個最優解，任何其它點都不滿條件。（前提是這三個點不在一條直線上，否則是沒有解的）

好了，我們先看代碼先，然後在解釋。

import tensorflow as tfimport numpy# Parameterslearning_rate = 0.1training_epochs = 3000display_step = 50# Training Data, 3 points that form a triangeltrain_X = numpy.asarray([3.0,6.0,9.0])train_Y = numpy.asarray([7.0,9.0,7.0])# tf Graph InputX = tf.placeholder("float")Y = tf.placeholder("float")# Set vaibale for centercx = tf.Variable(3, name="cx",dtype=tf.float32)cy = tf.Variable(3, name="cy",dtype=tf.float32)# Caculate the distance to the center and make them as equal as possibledistance = tf.pow(tf.add(tf.pow((X-cx),2),tf.pow((Y-cy),2)),0.5)mean = tf.reduce_mean(distance)cost = tf.reduce_sum(tf.pow((distance-mean),2)/3)# Gradient descentoptimizer = tf.train.GradientDescentOptimizer(learning_rate).minimize(cost)# Initialize the variables (i.e. assign their default value)init = tf.global_variables_initializer()# Start trainingwith tf.Session() as sess: sess.run(init) # Fit all training data for epoch in range(training_epochs): sess.run(optimizer, feed_dict={X: train_X, Y: train_Y}) c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) if (c - 0) < 0.0000000001: break #Display logs per epoch step if (epoch+1) % display_step == 0: c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) m = sess.run(mean, feed_dict={X: train_X, Y:train_Y}) print "Epoch:", %04d % (epoch+1), "cost=", "{:.9f}".format(c), "CX=", sess.run(cx), "CY=", sess.run(cy), "Mean=", "{:.9f}".format(m) print "Optimization Finished!" training_cost = sess.run(cost, feed_dict={X: train_X, Y: train_Y}) print "Training cost=", training_cost, "CX=", round(sess.run(cx),2), "CY=", round(sess.run(cy),2), "R=", round(m,2),

運行以上的python代碼，結果如下：

Epoch: 0050 cost= 0.290830940 CX= 5.5859795 CY= 2.6425467 Mean= 5.657848835Epoch: 0100 cost= 0.217094064 CX= 5.963002 CY= 3.0613017 Mean= 5.280393124Epoch: 0150 cost= 0.173767462 CX= 5.997781 CY= 3.5245996 Mean= 4.885882378Epoch: 0200 cost= 0.126330480 CX= 5.9999194 CY= 4.011508 Mean= 4.485837936Epoch: 0250 cost= 0.078660280 CX= 5.9999976 CY= 4.4997787 Mean= 4.103584766Epoch: 0300 cost= 0.038911112 CX= 5.9999976 CY= 4.945466 Mean= 3.775567770Epoch: 0350 cost= 0.014412695 CX= 5.999998 CY= 5.2943544 Mean= 3.535865068Epoch: 0400 cost= 0.004034557 CX= 5.999998 CY= 5.5200934 Mean= 3.390078306Epoch: 0450 cost= 0.000921754 CX= 5.999998 CY= 5.6429324 Mean= 3.314131498Epoch: 0500 cost= 0.000187423 CX= 5.999998 CY= 5.7023263 Mean= 3.278312683Epoch: 0550 cost= 0.000035973 CX= 5.999998 CY= 5.7292333 Mean= 3.262284517Epoch: 0600 cost= 0.000006724 CX= 5.999998 CY= 5.7410445 Mean= 3.255288363Epoch: 0650 cost= 0.000001243 CX= 5.999998 CY= 5.746154 Mean= 3.252269506Epoch: 0700 cost= 0.000000229 CX= 5.999998 CY= 5.7483506 Mean= 3.250972748Epoch: 0750 cost= 0.000000042 CX= 5.999998 CY= 5.749294 Mean= 3.250416517Epoch: 0800 cost= 0.000000008 CX= 5.999998 CY= 5.749697 Mean= 3.250178576Epoch: 0850 cost= 0.000000001 CX= 5.999998 CY= 5.749871 Mean= 3.250076294Epoch: 0900 cost= 0.000000000 CX= 5.999998 CY= 5.7499437 Mean= 3.250033140Optimization Finished!Training cost= 9.8869656e-11 CX= 6.0 CY= 5.75 R= 3.25

經過900多次的迭代，圓心位置是（6.0，5.75），半徑是3.25。

# Parameterslearning_rate = 0.1training_epochs = 3000display_step = 50

learning_rate 是梯度下降的速率，這個值越大，收斂的越快，但也有可能會錯過最優解
training_epochs是學習迭代的次數
display_step是每多少次迭代顯示當前的計算結果

# Training Data, 3 points that form a triangeltrain_X = numpy.asarray([3.0,6.0,9.0])train_Y = numpy.asarray([7.0,9.0,7.0])# tf Graph InputX = tf.placeholder("float")Y = tf.placeholder("float")# Set vaibale for centercx = tf.Variable(3, name="cx",dtype=tf.float32)cy = tf.Variable(3, name="cy",dtype=tf.float32)

train_X,train_Y是三個點的x，y坐標，這裡我們選了（3，7）（6，9）（9，7）三個點
X，Y是計算的輸入，在計算過程中我們會使用訓練數據輸入X，Y
cx，cy是我們想要找的圓心點，初始值設置為（3，3），一般的學習演算法會使用隨機的初始值，這裡我選了三角形中的一個點，這樣做一般會減少迭代的次數。

# Caculate the distance to the center and make them as equal as possibledistance = tf.pow(tf.add(tf.pow((X-cx),2),tf.pow((Y-cy),2)),0.5)mean = tf.reduce_mean(distance)cost = tf.reduce_sum(tf.pow((distance-mean),2)/3)# Gradient descentoptimizer = tf.train.GradientDescentOptimizer(learning_rate).minimize(cost)

這幾行代碼是演算法的核心。

distance是利用兩個點的距離公式算出三個點到圓心的距離
mean是三個距離的平均值
cost是三個距離的方差，我們的目標是讓三個點到圓心的距離一樣，也就是方差最小（cx/cy為圓心的時候，這個方差為零）
optimizer是梯度下降的訓練函數，目標是使得cost（方差）最小

下面就是訓練的過程了：

# Start trainingwith tf.Session() as sess: sess.run(init) # Fit all training data for epoch in range(training_epochs): sess.run(optimizer, feed_dict={X: train_X, Y: train_Y}) c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) if (c - 0) < 0.0000000001: break #Display logs per epoch step if (epoch+1) % display_step == 0: c = sess.run(cost, feed_dict={X: train_X, Y:train_Y}) m = sess.run(mean, feed_dict={X: train_X, Y:train_Y}) print "Epoch:", %04d % (epoch+1), "cost=", "{:.9f}".format(c), "CX=", sess.run(cx), "CY=", sess.run(cy), "Mean=", "{:.9f}".format(m) print "Optimization Finished!" training_cost = sess.run(cost, feed_dict={X: train_X, Y: train_Y}) print "Training cost=", training_cost, "CX=", round(sess.run(cx),2), "CY=", round(sess.run(cy),2), "R=", round(m,2),

初始化tf的session
開始迭代
計算cost值，當cost小於一定的值的時候，推出迭代，說明我們已經找到了圓心
最後列印出訓練的結果

原題目是空間上的點，我的例子是平面上的點，其實沒有本質差別。可以加一個Z軸的數據。這個題，三維其實是多餘的，完全可以把空間上的三個點投影到平面上來解決。

我用JS實現過另一個演算法，但是不是總收斂。大家可以參考著看一看：

其中，綠色三個點條件點，紅色的圓是最終的學習結果，黃色的中心點學習的軌跡。

利用這個例子，我想說的是：

Tensorflow不僅僅是一個深度學習的工具，它提供了強大的數據計算能力，可以用於解決很多的數學問題
機器學習的本質是通過一組數據來找到答案，這也是數學的作用，所以很多的數學問題都可以用機器學習的思路來解決。