private void learn(T[] data, RNNSearch<T,T> nns, int k, double radius, int[] y) {
        if (k < 2) {
            throw new IllegalArgumentException("Invalid k: " + k);
        }

        if (radius <= 0.0) {
            throw new IllegalArgumentException("Invalid radius: " + radius);
        }

        this.k = k;
        this.nns = nns;
        this.radius = radius;
        this.y = y;
        this.size = new int[k];

        int n = data.length;
        for (int i = 0; i < n; i++) {
            size[y[i]]++;
        }

        // Initialize the neighborhood list for each sample.
        double[] px = new double[n];

        // Neighbors of each sample.
        ArrayList<ArrayList<Integer>> neighbors = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            ArrayList<Neighbor<T,T>> list = new ArrayList<>();
            nns.range(data[i], radius, list);
            ArrayList<Integer> neighbor = new ArrayList<>(list.size());
            neighbors.add(neighbor);
            for (Neighbor<T,T> nt : list) {
                neighbor.add(nt.index);
            }
            px[i] = (double) list.size() / n;
        }

        // Initialize a posterior probabilities.

        // The count of each cluster in the neighborhood.
        int[][] neighborhoodClusterSize = new int[n][k];
        // The most significant cluster in the neighborhood.
        int[] mostSignificantNeighborhoodCluster = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j : neighbors.get(i)) {
                neighborhoodClusterSize[i][y[j]]++;
            }
        }

        for (int i = 0; i < n; i++) {
            int max = 0;
            for (int j = 0; j < k; j++) {
                if (neighborhoodClusterSize[i][j] > max) {
                    mostSignificantNeighborhoodCluster[i] = j;
                    max = neighborhoodClusterSize[i][j];
                }
            }
        }

        // The number of samples with nonzero conditional entropy.
        entropy = 0.0;
        for (int i = 0; i < n; i++) {
            if (!neighbors.get(i).isEmpty()) {
                int ni = neighbors.get(i).size();
                double m = 0.0;
                for (int j = 0; j < k; j++) {
                    double r = ((double) neighborhoodClusterSize[i][j]) / ni;
                    if (r > 0) {
                        m -= r * Math.log2(r);
                    }
                }

                m *= px[i];
                entropy += m;
            }
        }

        double eps = 1.0;
        while (eps >= 1E-7) {
            for (int i = 0; i < n; i++) {
                if (mostSignificantNeighborhoodCluster[i] != y[i]) {
                    double oldMutual = 0.0;
                    double newMutual = 0.0;

                    for (int neighbor : neighbors.get(i)) {
                        double nk = neighbors.get(neighbor).size();

                        double r1 = (double) neighborhoodClusterSize[neighbor][y[i]] / nk;
                        double r2 = (double) neighborhoodClusterSize[neighbor][mostSignificantNeighborhoodCluster[i]] / nk;
                        if (r1 > 0) {
                            oldMutual -= r1 * Math.log2(r1) * px[neighbor];
                        }
                        if (r2 > 0) {
                            oldMutual -= r2 * Math.log2(r2) * px[neighbor];
                        }

                        r1 = (neighborhoodClusterSize[neighbor][y[i]] - 1.0) / nk;
                        r2 = (neighborhoodClusterSize[neighbor][mostSignificantNeighborhoodCluster[i]] + 1.0) / nk;
                        if (r1 > 0) {
                            newMutual -= r1 * Math.log2(r1) * px[neighbor];
                        }
                        if (r2 > 0) {
                            newMutual -= r2 * Math.log2(r2) * px[neighbor];
                        }
                    }

                    if (newMutual < oldMutual) {
                        for (int neighbor : neighbors.get(i)) {
                            --neighborhoodClusterSize[neighbor][y[i]];
                            ++neighborhoodClusterSize[neighbor][mostSignificantNeighborhoodCluster[i]];
                            int mi = mostSignificantNeighborhoodCluster[i];
                            int mk = mostSignificantNeighborhoodCluster[neighbor];
                            if (neighborhoodClusterSize[neighbor][mi] > neighborhoodClusterSize[neighbor][mk]) {
                                mostSignificantNeighborhoodCluster[neighbor] = mostSignificantNeighborhoodCluster[i];
                            }
                        }

                        size[y[i]]--;
                        size[mostSignificantNeighborhoodCluster[i]]++;
                        y[i] = mostSignificantNeighborhoodCluster[i];
                    }
                }
            }

            double prevObj = entropy;
            entropy = 0.0;
            for (int i = 0; i < n; i++) {
                if (!neighbors.get(i).isEmpty()) {
                    int ni = neighbors.get(i).size();
                    double m = 0.0;
                    for (int j = 0; j < k; j++) {
                        double r = ((double) neighborhoodClusterSize[i][j]) / ni;
                        if (r > 0) {
                            m -= r * Math.log2(r);
                        }
                    }

                    m *= px[i];
                    entropy += m;
                }
            }

            eps = prevObj - entropy;
        }

        // Collapse clusters by removing clusters with no samples.
        int nk = 0;
        for (int i = 0; i < k; i++) {
            if (size[i] > 0) {
                nk++;
            }
        }

        int[] count = new int[nk];
        for (int i = 0, j = 0; i < k; i++) {
            if (size[i] > 0) {
                count[j] = size[i];
                size[i] = j++;
            }
        }

        for (int i = 0; i < n; i++) {
            y[i] = size[y[i]];
        }

        this.k = nk;
        size = count;
    }
private void learn ( T [ ] data , RNNSearch < T , T > nns , int k , double radius , int [ ] y ) { if ( k < 2 ) { throw new IllegalArgumentException ( "Invalid k: " + k ) ; } if ( radius <= 0.0 ) { throw new IllegalArgumentException ( "Invalid radius: " + radius ) ; } this . k = k ; this . nns = nns ; this . radius = radius ; this . y = y ; this . size = new int [ k ] ; int n = data . length ; for ( int i = 0 ; i < n ; i ++ ) { size [ y [ i ] ] ++ ; } double [ ] px = new double [ n ] ; ArrayList < ArrayList < Integer > > neighbors = new ArrayList < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { ArrayList < Neighbor < T , T > > list = new ArrayList < > ( ) ; nns . range ( data [ i ] , radius , list ) ; ArrayList < Integer > neighbor = new ArrayList < > ( list . size ( ) ) ; neighbors . add ( neighbor ) ; for ( Neighbor < T , T > nt : list ) { neighbor . add ( nt . index ) ; } px [ i ] = ( double ) list . size ( ) / n ; } int [ ] [ ] neighborhoodClusterSize = new int [ n ] [ k ] ; int [ ] mostSignificantNeighborhoodCluster = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j : neighbors . get ( i ) ) { neighborhoodClusterSize [ i ] [ y [ j ] ] ++ ; } } for ( int i = 0 ; i < n ; i ++ ) { int max = 0 ; for ( int j = 0 ; j < k ; j ++ ) { if ( neighborhoodClusterSize [ i ] [ j ] > max ) { mostSignificantNeighborhoodCluster [ i ] = j ; max = neighborhoodClusterSize [ i ] [ j ] ; } } } entropy = 0.0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! neighbors . get ( i ) . isEmpty ( ) ) { int ni = neighbors . get ( i ) . size ( ) ; double m = 0.0 ; for ( int j = 0 ; j < k ; j ++ ) { double r = ( ( double ) neighborhoodClusterSize [ i ] [ j ] ) / ni ; if ( r > 0 ) { m -= r * Math . log2 ( r ) ; } } m *= px [ i ] ; entropy += m ; } } double eps = 1.0 ; while ( eps >= 1E-7 ) { for ( int i = 0 ; i < n ; i ++ ) { if ( mostSignificantNeighborhoodCluster [ i ] != y [ i ] ) { double oldMutual = 0.0 ; double newMutual = 0.0 ; for ( int neighbor : neighbors . get ( i ) ) { double nk = neighbors . get ( neighbor ) . size ( ) ; double r1 = ( double ) neighborhoodClusterSize [ neighbor ] [ y [ i ] ] / nk ; double r2 = ( double ) neighborhoodClusterSize [ neighbor ] [ mostSignificantNeighborhoodCluster [ i ] ] / nk ; if ( r1 > 0 ) { oldMutual -= r1 * Math . log2 ( r1 ) * px [ neighbor ] ; } if ( r2 > 0 ) { oldMutual -= r2 * Math . log2 ( r2 ) * px [ neighbor ] ; } r1 = ( neighborhoodClusterSize [ neighbor ] [ y [ i ] ] - 1.0 ) / nk ; r2 = ( neighborhoodClusterSize [ neighbor ] [ mostSignificantNeighborhoodCluster [ i ] ] + 1.0 ) / nk ; if ( r1 > 0 ) { newMutual -= r1 * Math . log2 ( r1 ) * px [ neighbor ] ; } if ( r2 > 0 ) { newMutual -= r2 * Math . log2 ( r2 ) * px [ neighbor ] ; } } if ( newMutual < oldMutual ) { for ( int neighbor : neighbors . get ( i ) ) { -- neighborhoodClusterSize [ neighbor ] [ y [ i ] ] ; ++ neighborhoodClusterSize [ neighbor ] [ mostSignificantNeighborhoodCluster [ i ] ] ; int mi = mostSignificantNeighborhoodCluster [ i ] ; int mk = mostSignificantNeighborhoodCluster [ neighbor ] ; if ( neighborhoodClusterSize [ neighbor ] [ mi ] > neighborhoodClusterSize [ neighbor ] [ mk ] ) { mostSignificantNeighborhoodCluster [ neighbor ] = mostSignificantNeighborhoodCluster [ i ] ; } } size [ y [ i ] ] -- ; size [ mostSignificantNeighborhoodCluster [ i ] ] ++ ; y [ i ] = mostSignificantNeighborhoodCluster [ i ] ; } } } double prevObj = entropy ; entropy = 0.0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! neighbors . get ( i ) . isEmpty ( ) ) { int ni = neighbors . get ( i ) . size ( ) ; double m = 0.0 ; for ( int j = 0 ; j < k ; j ++ ) { double r = ( ( double ) neighborhoodClusterSize [ i ] [ j ] ) / ni ; if ( r > 0 ) { m -= r * Math . log2 ( r ) ; } } m *= px [ i ] ; entropy += m ; } } eps = prevObj - entropy ; } int nk = 0 ; for ( int i = 0 ; i < k ; i ++ ) { if ( size [ i ] > 0 ) { nk ++ ; } } int [ ] count = new int [ nk ] ; for ( int i = 0 , j = 0 ; i < k ; i ++ ) { if ( size [ i ] > 0 ) { count [ j ] = size [ i ] ; size [ i ] = j ++ ; } } for ( int i = 0 ; i < n ; i ++ ) { y [ i ] = size [ y [ i ] ] ; } this . k = nk ; size = count ; }
Clustering the data.
@param data the dataset for clustering.
@param y the initial clustering labels, which could be produced by any
other clustering methods.
@param nns the data structure for neighborhood search.
@param k the number of clusters. Note that this is just a hint. The final
number of clusters may be less.
@param radius the radius for neighbor range search.