Weiszfeld Algorithm

March 12, 2021
machine_learning weiszfeld_algorithm

Pierre de Fermat 1607-1665 was a French lawyer and mathematician. In 1640, he proposed a problem to Evangelista Torricelli, a student of the famous Galileo Galilei. Fermat challenged Torricelli to find the point in a triangle whose sum of distances from the vertices is a minimum. Torricelli did solve the problem, in more than a single way, but over the years other solutions where found. In 1937, Endre Weitzfeld came up with an algorithmic solution of this problem, that we shall look into in this post.

The problem of finding the optimal placement of facilities to minimize costs is an application go this algorithm. It is also used in some form in cluster analysis in order to find the centroid of a cluster.

Assuming that all locations have the same weight, we start with finding the total cost of a system where we want to implement a single location scenario, $$Z = \sum_{i=1}^{m} \sqrt{(x_i -c_x)^2+(y_i -c_y)^2}$$

Differentiating with respect to c_x

$$\frac{\partial Z}{\partial c_x} = \sum_{i=1}^{m} \left(-\frac{1}{2} \frac{1}{ \sqrt{(x_i -c_x)^2+(y_i -c_y)^2}} \right) 2(x_i - c_x) (-1)$$

$$ = \sum_{i=1}^{m} \frac{(x_i - c_x)}{ \sqrt{(x_i -c_x)^2+(y_i -c_y)^2} }$$

at the minimum value this value will be equal to zero.

$$ \sum_{i=1}^{m} \frac{(x_i - c_x)}{ \sqrt{(x_i -c_x)^2+(y_i -c_y)^2} } = 0$$

$$c_x = \frac{\sum_{i=1}^{m} \frac{x_i}{\sqrt{(x_i -c_x)^2+(y_i -c_y)^2}}}{\sum_{i=1}^{m} \frac{1}{\sqrt{(x_i -c_x)^2+(y_i -c_y)^2}}}$$

An therefore we can deduce;

$$c_{x}^{k+1} = \frac{\sum_{i=1}^{m} \frac{x_i}{\sqrt{(x_i -c_{x}^{k})^2+(y_i -c_y)^2}}}{\sum_{i=1}^{m} \frac{1}{\sqrt{(x_i -c_{x}^{k})^2+(y_i -c_y)^2}}}$$


$$c_{y}^{k+1} = \frac{\sum_{i=1}^{m} \frac{y_i}{\sqrt{(x_i -c_x)^2+(y_i -c_{y}^{k})^2}}}{\sum_{i=1}^{m} \frac{1}{\sqrt{(x_i -c_x)^2+(y_i -c_{y}^{k})^2}}}$$

if we define $$\delta_x = |c^{k+1}_x - c^{k}_x| $$

and $$\delta_y = |c^{k+1}_y - c^{k}_y| $$

Stop when $$\delta_x \leq \xi$$ and $$\delta_y \leq \xi$$

Otherwise repeat

The attached Excel file illustrates the execution of this algorithm for three and four points.

Mathematical prerequisites for some Clustering techniques

October 14, 2021
maths machine_learning

Simple Python implementation of the Weiszfeld algorithm

March 14, 2021
machine_learning python weiszfeld_algorithm

Notes on Monte Carlo Simulation

March 14, 2021
machine_learning python random_walk
comments powered by Disqus
hugo_cms 11 fuzzy 10 python 9 machine_learning 5 type2_fuzzy_library 5 cnc 4 type1_fuzzy 4 type2_fuzzy 4 r 3 excel 2 iot 2 it2fs 2 weiszfeld_algorithm 2 arduino 1 classifier 1 development 1 game 1 javascript 1 learning 1 mathjax 1 maths 1 mxchip 1 pandas 1 random_walk 1 robot 1 roc 1 set 1 tools 1 type_2_fuzzy 1 vscode 1 wsl 1