/*
 * Copyright (C) 2018 Edward Raff
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */

package jsat.clustering;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.atomic.AtomicIntegerArray;
import java.util.concurrent.atomic.LongAdder;
import java.util.stream.DoubleStream;
import jsat.DataSet;
import static jsat.clustering.SeedSelectionMethods.selectIntialPoints;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.utils.concurrent.AtomicDoubleArray;
import static jsat.utils.concurrent.ParallelUtils.*;
import static java.lang.Math.*;
import java.util.*;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * This class implements the TRIKMEDS algorithm for PAM clustering. It returns
 * the exact same result that would have been computed by PAM, but uses the
 * triangle inequality to avoid unnecessary distance calculations. Expected
 * runtime is O( n sqrt(n)), but still has worst case complexity
 * O(n2). It also requires that the distance metric used be a valid
 * distance metric.
 *
 * @author Edward Raff
 */
public class TRIKMEDS extends PAM
{

    public TRIKMEDS(DistanceMetric dm, Random rand, SeedSelectionMethods.SeedSelection seedSelection)
    {
        super(dm, rand, seedSelection);
    }

    public TRIKMEDS(DistanceMetric dm, Random rand)
    {
        super(dm, rand);
    }

    public TRIKMEDS(DistanceMetric dm)
    {
        super(dm);
    }

    public TRIKMEDS()
    {
        super();
    }

    @Override
    public void setDistanceMetric(DistanceMetric dm)
    {
        if(!dm.isValidMetric())
            throw new IllegalArgumentException("TRIKMEDS requires a valid distance metric, but " + dm.toString() + " does not obey all distance metric properties");
        super.setDistanceMetric(dm); 
    }

    @Override
    protected double cluster(DataSet data, boolean doInit, int[] medioids, int[] assignments, List cacheAccel, boolean parallel)
    {
        LongAdder changes = new LongAdder();
        Arrays.fill(assignments, -1);//-1, invalid category!
        
        List X = data.getDataVectors();
        final List accel;
        
        if(doInit)
        {
            TrainableDistanceMetric.trainIfNeeded(dm, data);
            accel = dm.getAccelerationCache(X);
            selectIntialPoints(data, medioids, dm, accel, rand, seedSelection);
        }
        else
            accel = cacheAccel;
        
        //N : number of training samples
        final int N = data.getSampleSize();
        final int K = medioids.length;
        //medioids = m
        //m(k) : index of current medoid of cluster k,m(k) ∈ {1, . . . ,N}
        final AtomicIntegerArray m = new AtomicIntegerArray(K);
        //c(k) : current medoid of cluster k, that is c(k) = x(m(k))
        final int[] c = medioids;
        //n_1(i) : cluster index of centroid nearest to x(i)
        
        //a(i) : cluster to which x(i) is currently assigned
        final int[] a = assignments;
        
        //d(i) : distance from x(i) to c(a(i))
        final double[] d = new double[N];
        final double[] d_tilde = new double[N];
        //v(k) : number of samples assigned to cluster k
        final AtomicDoubleArray v = new AtomicDoubleArray(K);
        //V (k) : number of samples assigned to a cluster of index less than k +1
        //We don't use V in this implementation. Paper uses it as a weird way of simplifying algorithm description. But not needed
        
        //lc(i, k) : lowerbound on distance from x(i) tom(k)
        double[][] lc = new double[N][K];
        
        //ls(i) : lowerbound on
        AtomicDoubleArray ls = new AtomicDoubleArray(N);
        
        //p(k) : distance moved (teleported) by m(k) in last update
        double[] p = new double[K];
        
        //s(k) : sum of distances of samples in cluster k to medoid k
        AtomicDoubleArray s = new AtomicDoubleArray(K);

        List> ownedBy = new ArrayList<>(K);
        for(int i = 0; i < K; i++)
            ownedBy.add(new ConcurrentSkipListSet<>());
        
        //Working sets used in updates
        final AtomicDoubleArray delta_n_in = new AtomicDoubleArray(K);
        final AtomicDoubleArray delta_n_out = new AtomicDoubleArray(K);
        final AtomicDoubleArray delta_s_in = new AtomicDoubleArray(K);
        final AtomicDoubleArray delta_s_out = new AtomicDoubleArray(K);
        
        // initialise //
        for(int k = 0; k < K; k++)
            m.set(k, c[k]);
        run(parallel, N, (start, end) -> 
        {
            for(int i = start; i < end; i++)
            {
                double a_min_val = Double.POSITIVE_INFINITY;
                int a_min_k = 0;
                for(int k = 0; k < K; k++)
                {
                    //Tightly initialise lower bounds on data-to-medoid distances
                    lc[i][k] = dm.dist(i, m.get(k), X, accel);
                    if(lc[i][k] <= a_min_val)
                    {
                        a_min_val = lc[i][k];
                        a_min_k = k;
                    }
                }
                //Set assignments and distances to nearest (assigned) medoid
                a[i] = a_min_k;
                d[i] = a_min_val;
                //Update cluster count
                v.getAndAdd(a[i], 1);
                ownedBy.get(a_min_k).add(i);
                //Update sum of distances to medoid
                s.addAndGet(a[i], d[i]);
                //Initialise lower bound on sum of in-cluster distances to x(i) to zero
                ls.set(i, 0.0);
            }
        });
        
        for(int k = 0; k < K; k++)
            ls.set(m.get(k), s.get(k));
        //end initialization
        
        int iter = 0;
        do
        {
            changes.reset();
            
            ///// update-medoids() //////
            boolean[] medioid_changed = new boolean[K];
            Arrays.fill(medioid_changed, false);
            run(parallel, N, (i)->
            {
                for(int k = 0; k < K; k++)
                {
                    // If the bound test cannot exclude i asm(k)
                    if(ls.get(i) < s.get(k))
                    {
                        // Make ls(i) tight by computing and cumulating all in-cluster distances to x(i),
                        double ls_i_new = 0;
                        for(int j : ownedBy.get(k))
                        {
                            d_tilde[j] = dm.dist(i, j, X, accel);
                            ls_i_new += d_tilde[j];
                        }
                        ls.set(i, ls_i_new);
                        //// Re-perform the test for i as candidate for m(k), now with exact sums. 
                        //If i is the new best candidate, update some cluster information
                        
                        if(ls_i_new < s.get(k))
                        {
                            /* Normally we would just check once. But if we are 
                             * doing this in parallel, we need to make the 
                             * switch out safe. So syncrhonize and re-peat the 
                             * check to avoid any race condition. We do the
                             * check twice b/c the check may happen often, but 
                             * only return true a few times. So lets avoid 
                             * contention and just do a re-check after we found 
                             * out we needed to do an update. */
                            synchronized (s)
                            {
                                if (ls_i_new < s.get(k))
                                {
                                    s.set(k, ls_i_new);
                                    m.set(k, i);
                                    medioid_changed[k] = true;
                                    for(int j : ownedBy.get(k))
                                        d[j] = d_tilde[j];
                                }
                            }
                        }
                        //Use computed distances to i to improve lower bounds on sums for all samples in cluster k (see Figure X)
                        for(int j : ownedBy.get(k))
                            ls.accumulateAndGet(j, d[j]*v.get(k), (ls_j, d_jXv_k) -> max(ls_j, abs(d_jXv_k-ls_j)));
                    }
                }
            });
            
            // If the medoid of cluster k has changed, update cluster information
            run(parallel, K, (k)->
            {
                if(medioid_changed[k])
                {
                    p[k] = dm.dist(c[k], m.get(k), X, accel);
                    c[k] = m.get(k);
                }
                
                //lets sneak in zero-ing out the delta arrays for the next stwp while are are doing a parallel loop
                delta_n_in.set(k, 0.0);
                delta_n_out.set(k, 0.0);
                delta_s_in.set(k, 0.0);
                delta_s_out.set(k, 0.0);
            });
            ///// assign-to-clusters()  //////
            run(parallel, N, (i)->
            {
                // Update lower bounds on distances to medoids based on distances moved by medoids
                for(int k = 0; k < K; k++)
                    lc[i][k] -= p[k];
                // Use the exact distance of current assignment to keep bound tight (might save future calcs)
                lc[i][a[i]] = d[i];
                // Record current assignment and distance aold
                int a_old = a[i];
                double d_old = d[i];
                // Determine nearest medoid, using bounds to eliminate distance calculations
                for(int k = 0; k < K; k++)
                    if(lc[i][k] < d[i])
                    {
                        lc[i][k] = dm.dist(i, c[k], X, accel);
                        if(lc[i][k] < d[i])
                        {
                            a[i] = k;
                            d[i] = lc[i][k];
                        }
                    }
                // If the assignment has changed, update statistics
                if(a_old != a[i])
                {
                    v.getAndDecrement(a_old);
                    v.getAndIncrement(a[i]);
                    changes.increment();
                    ownedBy.get(a_old).remove(i);
                    ownedBy.get(a[i]).add(i);
                    ls.set(i, 0.0);
                    delta_n_in.getAndIncrement(a[i]);
                    delta_n_out.getAndIncrement(a_old);
                    delta_s_in.getAndAdd(a[i], d[i]);
                    delta_s_in.getAndAdd(a_old, d_old);
                }
            });
            ///// update-sum-bounds() ///////
            double[] J_abs_s = new double[K];
            double[] J_net_s = new double[K];
            double[] J_abs_n = new double[K];
            double[] J_net_n = new double[K];
            for(int k = 0; k < K; k++)
            {
                J_abs_s[k] = delta_s_in.get(k) + delta_s_out.get(k);
                J_net_s[k] = delta_s_in.get(k) - delta_s_out.get(k);
                J_abs_n[k] = delta_n_in.get(k) + delta_n_out.get(k);
                J_net_n[k] = delta_n_in.get(k) - delta_n_out.get(k);
            }
            run(parallel, N, (start, end)->
            {
                for(int i = start; i < end; i++)
                {
                    double ls_i_delta = 0;
                    for(int k = 0; k < K; k++)
                        ls_i_delta -= min(J_abs_s[k]-J_net_n[k]*d[i], J_abs_n[k]*d[i] - J_net_s[k]);
                    ls.getAndAdd(i, ls_i_delta);
                }
            });
        }
        while( changes.sum() > 0 && iter++ < iterLimit);
        
        return streamP(DoubleStream.of(d), parallel).map(x->x*x).sum();
    }
    
    /**
     * Computes the medoid of the data 
     * @param parallel whether or not the computation should be done using multiple cores
     * @param X the list of all data
     * @param dm the distance metric to get the medoid with respect to
     * @return the index of the point in X that is the medoid
     */
    public static int medoid(boolean parallel, List X, DistanceMetric dm)
    {
        IntList order = new IntList(X.size());
        ListUtils.addRange(order, 0, X.size(), 1);
        List accel = dm.getAccelerationCache(X, parallel);
        return medoid(parallel, order, X, dm, accel);
    }
    
    /**
     * Computes the medoid of a sub-set of data
     * @param parallel whether or not the computation should be done using multiple cores
     * @param indecies the indexes of the points to get the medoid of 
     * @param X the list of all data
     * @param dm the distance metric to get the medoid with respect to
     * @param accel the acceleration cache for the distance metric
     * @return the index value contained within indecies that is the medoid 
     */
    public static int medoid(boolean parallel, Collection indecies, List X, DistanceMetric dm, List accel)
    {
        final int N = X.size();
        AtomicDoubleArray l = new AtomicDoubleArray(N);
        
        AtomicDouble e_cl = new AtomicDouble(Double.POSITIVE_INFINITY);
        
        IntList rand_order = new IntList(indecies);
        Collections.shuffle(rand_order, RandomUtil.getRandom());
        ThreadLocal d_local = ThreadLocal.withInitial(() -> new double[N]);
        ParallelUtils.streamP(rand_order.streamInts(), parallel).forEach(i ->
        {
            double[] d = d_local.get();
            double d_avg = 0;
            if (l.get(i) < e_cl.get())
            {
                for (int j : indecies)
                    d_avg += (d[j] = dm.dist(i, j, X, accel));
                d_avg /= indecies.size() - 1;
                final double l_i = d_avg;
                // set l(i) to to be tight, that is l(i) = E(i)
                l.set(i, l_i);
                if (l_i < e_cl.get())//We might be the best?
                    e_cl.getAndUpdate(val -> min(val, l_i));//atomic set to maximum
                //l(j)←max(l(j), |l(i)−d(j)|) // using ||x(i)−x(j)|| to possibly improve bound.
                for (int j : indecies)
                    l.getAndUpdate(j, (l_j) -> max(l_j, abs(l_i - d[j]) ) );
            }
        });
        
        //OK, who had the lowest energy? Thats our median. 
        for(int i : indecies)
            if(l.get(i) == e_cl.get())//THIS IS SAFE, we explicily set l and e_cl to the same exact values in the algorithm. So we can do a hard equality check on the doubles
                return i;

        return -1;//Some error occred
    }
}

 

Ads help maintain this website.