Weighted K-means with GPS Data
<p><strong>OBJECTIVE</strong></p>

<ul>
<li><p>Aggregate store locations GPS information (longitude, latitude) </p></li>
<li><p>Aggregate size of population in surrounding store area (e.g 1,000,000
residents) </p></li>
<li>Use K-means to determine optimal distribution centers,
given store GPS data and local population (i.e distribution centers
are located closer to urban stores vs. rural stores due to higher
demand).</li>
</ul>

<p><strong>ISSUES</strong></p>

<ol>
<li>I've been <a href="http://cs.au.dk/~simina/weighted.pdf" rel="nofollow">researching</a> on how to add weighted variables to a k-means algorithm, but am unsure on the <em>actual</em> process of weighting the variables. For example, if I have the [lat, long, and population (in thousands)] (e.g "New York" = <code>[40.713, 74.005, 8406]</code>) wouldn't this construct the centriod in 3-dimensional space? If so, wouldn't the distances be improperly skewed and mis-represent the best location for a warehouse distribution center?</li>
<li>Additional <a href="https://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf" rel="nofollow">research</a> alludes to UPGMA, "Unweighted Pair Group Method" where the size of the cluster is taken into account. However, I haven't fully reviewed this method and the intricacies associated with this method. </li>
</ol>

<p><strong>REFERENCES</strong></p>

<p>Reference 1:  <a href="http://cs.au.dk/~simina/weighted.pdf" rel="nofollow">http://cs.au.dk/~simina/weighted.pdf</a> (page 5)</p>

<blockquote>
  <p>It can also be shown that a few other algorithms similar to k-means, namely k-median and k-mediods are also
  weight-separable. The details appear in the appendix. Observe that all of these popular objective functions are highly
  responsive to weight.</p>
</blockquote>

<p>Reference 2: <a href="https://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf" rel="nofollow">https://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf</a> (page 39: "Ability to Handle Different cluster sizes"</p>

<p>1) You only want to do k-means in the (longitude, latitude) space. If you add population as a 3rd dimension, you will bias your centroids towards the midpoint between large population centres, which are often far apart.</p>

<p>2) The simplest hack to incorporate a weighting in k-means is to repeat a point (longitude, latitude) according to its population weight. </p>

<p>3) k-means is probably not the best clustering algorithm for the job, as travel times do not scale linearly with distance. Also, you are basically guaranteed to never have a distribution centre bang in the middle of a large population centre, which is probably not what you want. I would use DBSCAN, for which scikit-learn has a nice implementation:
<a href="http://scikit-learn.org/stable/modules/clustering.html" rel="nofollow">http://scikit-learn.org/stable/modules/clustering.html</a></p>

python numpy statistics k-means