Weiszfeld Algorithm

Fri 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}}}$$

similarly

$$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.




Notes about Azure ML, Part 10 - An end-to-end AzureML example; Model Optimization

Creation and execution of an AzureML Model Optimization Experiment
machine-learning azure ml hyperparameter tuning model optimization

Notes about Azure ML, Part 9 - An end-to-end AzureML example Pipeline creation and execution

Creation and execution of a multi-step AzureML pipeline the selects the best model for a given dataset.
machine-learning azure ml pipeline

Notes about Azure ML, Part 8 - An end-to-end AzureML example; Workspace creation and data upload

In this first post of a series that will cover an end-to-end machine learning project in Azure Ml we will look at how to create a workspace and upload data to it.
machine-learning azure ml dataset datastore
comments powered by Disqus


machine-learning 25 python 21 fuzzy 14 hugo_cms 11 azure-ml 10 linear-regression 10 gradient-descent 9 type2-fuzzy 8 type2-fuzzy-library 8 type1-fuzzy 5 cnc 4 dataset 4 datastore 4 it2fs 4 excel 3 paper-workout 3 r 3 c 2 c-sharp 2 experiment 2 iot 2 programming 2 robotics 2 weiszfeld_algorithm 2 arduino 1 automl 1 classifier 1 computation 1 cost-functions 1 development 1 embedded 1 fuzzy-logic 1 game 1 hyperparameter-tuning 1 javascript 1 learning 1 mathjax 1 maths 1 model-optimization 1 mxchip 1 pandas 1 pipeline 1 random_walk 1 roc 1 tools 1 vscode 1 wsl 1