Clustering points based on their function values and proximity
<p>I have many points <code>X</code> and their function values <code>f</code> stored in <code>numpy</code> arrays. I want to find <strong>all points</strong> in <code>X</code> that don't have a better point (smaller <code>f</code> value) within a distance <code>r</code>.</p>

<p><code>X</code> is hundreds of thousands of points, so I can't precompute <code>sp.spatial.distance.pdist(X)</code> but resort to the following:</p>

<pre><code>def cluster(X,f,r):
    pts,n = np.shape(X)
    centers = []
    for i in range(0,pts):
        pdist = sp.spatial.distance.cdist(X,[X[i]])
        if not np.any(np.logical_and(pdist &lt;= r, f &lt; f[i])):
            centers.append(i)
    return centers
</code></pre>

<p>This takes minutes. Is there a way to quickly cluster based on proximity and another metric?</p>

<p>You can significantly reduce the number of distance computation by keeping a record. For instance, if j is a neighbor of a center i and it has a larger f value, then j can never be a center since one of its neighbors is i which has a smaller f value. Please check the following and let me know if you need clarification.</p>

<pre><code>def cluster4(X,f,r):
    pts,n = np.shape(X)
    centers = np.ones((pts,1),dtype=int)
    for i in range(pts):
        if not centers[i]:
            continue
        pdist = sp.spatial.distance.cdist(X,[X[i]])
        inrange = (pdist &lt;= r)
        inrange[i] = False
        lesser = (f &lt; f[i])
        if np.any(inrange &amp; lesser):
            centers[i] = 0
        centers[inrange &amp; np.invert(lesser)] = 0
    return np.where(centers == 1)[0]
</code></pre>

python numpy scipy cluster-analysis