<div dir="ltr">Hello,<div><br></div><div>Thank you so much for the review! Here are some of my other comments on what's going on there:<br><br>XMeans is technically just an outer loop outside of main KMeans that picks K for you by trying to split clusters in the output of KMeans by running 2-Means and checks that after split things became better, then polishes the split with another run of KMeans. It's by definition slower than KMeans and is a price you pay for not knowing your K.<br><br>The original paper is using BIC, Bayesian Information Criteria, to understand that "things are good". Most of my doubts are in implementation of that thing: I got it explained to me twice and still don't fully understand how it works in our 2.5D spherical surface and what will be a good choice of parameters (are we almost-2D as we're nearly flat surface of the planet or must it be a 3D since we have x.y.z?). The thing is supposed to measure how roundish the clusters are and prefer more roundish ones. I would appreciate more attention to that part of the code or links to better explanations on dimensionality of our world.</div><div><br></div><div>The other finding is that BIC is rather costly to calculate. I was using Kontur Population dataset (<a href="https://data.humdata.org/dataset/kontur-population-dataset">https://data.humdata.org/dataset/kontur-population-dataset</a>) casted as points and the algorithm converged in hours for me, on millions of points. Clustering looks rather nice, but hours frighten me - still are useful for some scenarios, it's a machine working not you picking the best K.</div><div><br></div><div>The useful piece was to check that other criterias can be used. max_radius was simple to implement, converges quickly and has an easy to grasp meaning - "no clusters larger than 500m". That's what I really needed for walkability analysis in the past and I'm tempted to rip away the parts with BIC scores and just add min_radius to KMeans if I don't get a chance to fix this thing to perfection for 3.2.<br><br>Other thing is that XMeans lets you run KMeans in 2 ways: you can either init all the clusters from the start, or just init some and let the others be initialized by XMeans by splitting the ones you had initially. Second way seems nice, as it's easy to parallelize (you're running lots of 2-means splitting your clusters in 2 on separate CPUs) and code's structured to allow that instrumentation to be easy, maybe using OpenMP comments. I've seen some cases where the second way is faster already, since our KMeans init is O(KN) and with high K the recursive XMeans can be lower.</div><div><br></div><div>Original paper also suggests that this whole thing should not be done as is but should be done via tree lookups, then on KMeans loops computation complexity will go even lower. That's also not implemented. I've done a full-SQL XMeans in the past where it was done using Voronoi partition and GiST lookups and that seemingly worked good enough too, but hard to pack into PostGIS function.</div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Apr 3, 2021 at 11:53 AM Han Wang <<a href="mailto:hanwgeek@gmail.com">hanwgeek@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi all,<div><br></div><div>I just reviewed the code of `xmeans`(<a href="https://github.com/postgis/postgis/pull/592/commits" target="_blank">https://github.com/postgis/postgis/pull/592/commits</a>) which plans to replace conventional kmeans. I would like to know if there is anyone to test its performance? I think it may costs multiple times than kmeans.</div><div><br></div><div>Best regards,</div><div>Han</div></div>
_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr">Darafei "Komяpa" Praliaskouski<br>OSM BY Team - <a href="http://openstreetmap.by/" target="_blank">http://openstreetmap.by/</a><br></div></div>