kmeans_init()

static void kmeans_init ( POINT4D *  objs, uint32_t  n, POINT4D *  centers, uint32_t  k  )

static

Definition at line 175 of file lwkmeans.c.

{
        double *distances;
        uint32_t p1 = 0, p2 = 0;
        uint32_t duplicate_count = 1; /* a point is a duplicate of itself */
        double max_dst = -1;
 
        /* k=0, k=1: any point will do */
        assert(n > 0);
        if (k < 2)
        {
                centers[0] = objs[0];
                return;
        }
 
        /* k >= 2: find two distant points greedily */
        for (uint32_t i = 1; i < n; i++)
        {
                /* if we found a larger distance, replace our choice */
                double dst_p1 = distance3d_sqr_pt4d_pt4d(&objs[i], &objs[p1]);
                double dst_p2 = distance3d_sqr_pt4d_pt4d(&objs[i], &objs[p2]);
                if ((dst_p1 > max_dst) || (dst_p2 > max_dst))
                {
                        if (dst_p1 > dst_p2)
                        {
                                max_dst = dst_p1;
                                p2 = i;
                        }
                        else
                        {
                                max_dst = dst_p2;
                                p1 = i;
                        }
                }
                if ((dst_p1 == 0) || (dst_p2 == 0))
                        duplicate_count++;
        }
        if (duplicate_count > 1)
                lwnotice(
                    "%s: there are at least %u duplicate inputs, number of output clusters may be less than you requested",
                    __func__,
                    duplicate_count);
 
        /* by now two points should be found and non-same */
        assert(p1 != p2 && max_dst >= 0);
 
        /* accept these two points */
        centers[0] = objs[p1];
        centers[1] = objs[p2];
 
        if (k > 2)
        {
                /* array of minimum distance to a point from accepted cluster centers */
                distances = lwalloc(sizeof(double) * n);
 
                /* initialize array with distance to first object */
                for (uint32_t j = 0; j < n; j++)
                        distances[j] = distance3d_sqr_pt4d_pt4d(&objs[j], &centers[0]);
                distances[p1] = -1;
                distances[p2] = -1;
 
                /* loop i on clusters, skip 0 and 1 as found already */
                for (uint32_t i = 2; i < k; i++)
                {
                        uint32_t candidate_center = 0;
                        double max_distance = -DBL_MAX;
 
                        /* loop j on objs */
                        for (uint32_t j = 0; j < n; j++)
                        {
                                /* empty objs and accepted clusters are already marked with distance = -1 */
                                if (distances[j] < 0)
                                        continue;
 
                                /* update minimal distance with previosuly accepted cluster */
                                double current_distance = distance3d_sqr_pt4d_pt4d(&objs[j], &centers[i - 1]);
                                if (current_distance < distances[j])
                                        distances[j] = current_distance;
 
                                /* greedily take a point that's farthest from any of accepted clusters */
                                if (distances[j] > max_distance)
                                {
                                        candidate_center = j;
                                        max_distance = distances[j];
                                }
                        }
 
                        /* Checked earlier by counting entries on input, just in case */
                        assert(max_distance >= 0);
 
                        /* accept candidate to centers */
                        distances[candidate_center] = -1;
                        /* Copy the point coordinates into the initial centers array
                         * Centers array is an array of pointers to points, not an array of points */
                        centers[i] = objs[candidate_center];
                }
                lwfree(distances);
        }
}

References distance3d_sqr_pt4d_pt4d(), lwalloc(), lwfree(), and lwnotice().

Referenced by kmeans().

Here is the call graph for this function:

Here is the caller graph for this function: