Package gov.nih.mipav.model.algorithms

Class AgglomerativeInformationBottleneck

  • All Implemented Interfaces:
    java.awt.event.ActionListener, java.awt.event.WindowListener, java.lang.Runnable, java.util.EventListener
    public class AgglomerativeInformationBottleneck
extends AlgorithmBase
    Copyright (C) 2007-11, Andrea Vedaldi and Brian Fulkerson Copyright (C) 2012-13, The VLFeat Team All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    • Field Detail

      • BETA_MAX

        private double BETA_MAX

      • nrows

        private int nrows

      • ncols

        private int ncols

      • Pic

        private double[][] Pic

      • verbose

        private int verbose

      • cluster_null

        private boolean cluster_null

    • Constructor Detail

      • AgglomerativeInformationBottleneck

        public AgglomerativeInformationBottleneck()

      • AgglomerativeInformationBottleneck

        public AgglomerativeInformationBottleneck​(ModelImage image,
                                          int nrows,
                                          int ncols,
                                          double[][] Pic,
                                          int verbose,
                                          boolean cluster_null)

    • Method Detail

      • testSample

        public void testSample()

      • test_basic

        public void test_basic()

      • test_cluster_null

        public void test_cluster_null()

      • vl_aib_get_parents

        public int[] vl_aib_get_parents​(AgglomerativeInformationBottleneck.VlAIB aib)
        ------------------------------------------------------------------
        Parameters:
        aib - AIB filter.
        Returns:
        An array of parents

      • vl_aib_get_costs

        public double[] vl_aib_get_costs​(AgglomerativeInformationBottleneck.VlAIB aib)
        ------------------------------------------------------------------
        Parameters:
        aib - AIB filter.
        Returns:
        An array of costs

      • vl_aib_normalize_P

        public void vl_aib_normalize_P​(double[][] P)
        ------------------------------------------------------------------
        Parameters:
        P - The array of probabilities
        nelem - The number of elements in the array

      • vl_aib_new_nodelist

        public int[] vl_aib_new_nodelist​(int nentries)
        ------------------------------------------------------------------
        Parameters:
        nentries - The size of the list which will be created
        Returns:
        an array containing elements 0...nentries

      • vl_aib_new_Px

        public double[] vl_aib_new_Px​(double[][] Pcx,
                              int nvalues,
                              int nlabels)
        ------------------------------------------------------------------
        Parameters:
        Pcx - A two-dimensional array of probabilities
        nvalues - The number of rows in Pcx
        nlabels - The number of columns in Pcx
        Returns:
        an array of size @a nvalues which contains the marginal distribution over the rows.

      • vl_aib_new_Pc

        public double[] vl_aib_new_Pc​(double[][] Pcx,
                              int nvalues,
                              int nlabels)
        ------------------------------------------------------------------
        Parameters:
        Pcx - A two-dimensional array of probabilities
        nvalues - The number of rows in Pcx
        nlabels - The number of columns in Pcx
        Returns:
        an array of size @a nlabels which contains the marginal distribution over the columns

      • vl_aib_min_beta

        public void vl_aib_min_beta​(AgglomerativeInformationBottleneck.VlAIB aib,
                            int[] besti,
                            int[] bestj,
                            double[] minbeta)
        ------------------------------------------------------------------
        Parameters:
        aib - A pointer to the internal data structure
        besti - The index of one member of the pair which has mininum beta
        bestj - The index of the other member of the pair which minimizes beta
        minbeta - The minimum beta value corresponding to (@a i, @a j) Searches @a aib->beta to find the minimum value and fills @a minbeta and

      • vl_aib_merge_nodes

        public void vl_aib_merge_nodes​(AgglomerativeInformationBottleneck.VlAIB aib,
                               int i,
                               int j,
                               int new_index)
        ------------------------------------------------------------------
        Parameters:
        aib - A pointer to the internal data structure
        i - The index of one member of the pair to merge
        j - The index of the other member of the pair to merge
        new - The index of the new node which corresponds to the union of (@a i, @a j). Nodes are merged by replacing the entry @a i with the union of @c ij, moving the node stored in last position (called @c lastnode) back to jth position and the entry at the end. After the nodes have been merged, it updates which nodes should be considered on the next iteration based on which beta values could potentially change. The merged node will always be part of this list.

      • PLOGP

        public double PLOGP​(double x)

      • vl_aib_update_beta

        public void vl_aib_update_beta​(AgglomerativeInformationBottleneck.VlAIB aib)
        ------------------------------------------------------------------
        Parameters:
        aib - AIB data structure. The function calculates @c beta[i] and @c bidx[i] for the nodes @c i listed in @c aib->which. @c beta[i] is the minimal variation of mutual information (or other score) caused by merging entry @c i with another entry and @c bidx[i] is the index of this best matching entry. Notice that for each entry @c i that we need to update, a full scan of all the other entries must be performed.

      • vl_aib_calculate_information

        public void vl_aib_calculate_information​(AgglomerativeInformationBottleneck.VlAIB aib,
                                         double[] I,
                                         double[] H)
        ------------------------------------------------------------------
        Parameters:
        aib - A pointer to the internal data structure
        I - The current mutual information (out).
        H - The current entropy (out). Calculates the current mutual information and entropy of Pcx and sets

      • vl_aib_new

        public AgglomerativeInformationBottleneck.VlAIB vl_aib_new​(double[][] Pcx,
                                                           int nvalues,
                                                           int nlabels)
        ------------------------------------------------------------------
        Parameters:
        Pcx - A pointer to a 2D array of probabilities
        nvalues - The number of rows in the array
        nlabels - The number of columns in the array Creates a new @a VlAIB struct containing pointers to all the data that will be used during the AIB process. Allocates memory for the following: - Px (nvalues*sizeof(double)) - Pc (nlabels*sizeof(double)) - nodelist (nvalues*sizeof(vl_uint)) - which (nvalues*sizeof(vl_uint)) - beta (nvalues*sizeof(double)) - bidx (nvalues*sizeof(vl_uint)) - parents ((2*nvalues-1)*sizeof(vl_uint)) - costs (nvalues*sizeof(double)) Since it simply copies to pointer to Pcx, the total additional memory requirement is: (3*nvalues+nlabels)*sizeof(double) + 4*nvalues*sizeof(vl_uint)

      • vl_aib_delete

        public void vl_aib_delete​(AgglomerativeInformationBottleneck.VlAIB aib)
        ------------------------------------------------------------------
        Parameters:
        aib - data structure to delete.

      • vl_aib_process

        public void vl_aib_process​(AgglomerativeInformationBottleneck.VlAIB aib)
        ------------------------------------------------------------------
        Parameters:
        aib - AIB object to process The function runs Agglomerative Information Bottleneck (AIB) on the joint probability table @a aib->Pcx which has labels along the columns and feature values along the rows. AIB iteratively merges the two values of the feature @c x that causes the smallest decrease in mutual information between the random variables @c x and @c c. Merge operations are arranged in a binary tree. The nodes of the tree correspond to the original feature values and any other value obtained as a result of a merge operation. The nodes are indexed in breadth-first order, starting from the leaves. The first index is zero. In this way, the leaves correspond directly to the original feature values. In total there are @c 2*nvalues-1 nodes. The results may be accessed through vl_aib_get_parents which returns an array with one element per tree node. Each element is the index the parent node. The root parent is equal to zero. The array has @c 2*nvalues-1 elements. Feature values with null probability are ignored by the algorithm and their nodes have parents indexing a non-existent tree node (a value bigger than @c 2*nvalues-1). Then the function will also compute the information level after each merge. vl_get_costs will return a vector with the information level after each merge. @a cost has @c nvalues entries: The first is the value of the cost functional before any merge, and the others are the cost after the

      • cluster_null_nodes

        public void cluster_null_nodes​(int[] parents,
                               int nvalues,
                               double[] cost,
                               int verbosity)
        ------------------------------------------------------------------ Null nodes are nodes with null probability and are not merged by AIB. It is convenient, however, to treat them as follows: - we pretend that AIB merged those nodes at the very beginning into a single cluster (as they, after all, yield zero information drop). - we attach this cluster to the root as the very last step (as we do not want to change other nodes.

      • runAlgorithm

        public void runAlgorithm()
        Description copied from class: AlgorithmBase
        Actually runs the algorithm. Implemented by inheriting algorithms.
        Specified by:
        runAlgorithm in class AlgorithmBase

      • vl_aib

        public void vl_aib​(int[] parents,
                   double[] cost,
                   double[][] Pcxsource)

      • mi

        public double mi​(double[][] P)

      • vl_aibcut

        public void vl_aibcut​(int[] cut,
                      int[] map,
                      java.util.Vector<java.lang.Integer> shortc,
                      int[] parents,
                      int n)
        Parameters:
        cut -
        map -
        shortc -
        parents -
        n -

      • setdiff

        public void setdiff​(java.util.Vector<java.lang.Integer> C,
                    java.util.Vector<java.lang.Integer> ia,
                    java.util.Vector<java.lang.Integer> A,
                    java.util.Vector<java.lang.Integer> B)

      • vl_aibhist

        public int[] vl_aibhist​(int[] parents,
                        double[][] data,
                        boolean histmode)
        % VL_AIBHIST Compute histogram over VL_AIB tree % H = VL_AIBHIST(PARENTS, DATA) computes the histogram of the data % points DATA on the VL_AIB tree defined by PARENTS. Each element of % DATA indexes one of the leaves of the VL_AIB tree. % % H = VL_AIBHIST(PARENTS, DATA, 'HIST') treats DATA as an histograms. % In this case each compoment of DATA is the number of occurences of % the VL_AIB leaves corresponding to that component. % % H has the same dimension of parents and counts how many data points % are descendent of the corresponding node of the VL_AIB tree.

      • vl_aibcutpush

        public int[] vl_aibcutpush​(int[] map,
                           int[] x)
        function y = vl_aibcutpush(map, x) % VL_AIBCUTPUSH Quantize based on VL_AIB cut % Y = VL_AIBCUTPUSH(MAP, X) maps the data X to elements of the AIB % cut specified by MAP. % % The function is equivalent to Y = MAP(X).

      • vl_aibcuthist

        public int[] vl_aibcuthist​(int[] map,
                           int[] x,
                           java.lang.String mode)

      • vl_demo_aib

        public void vl_demo_aib()

      • quantize

        public int[] quantize​(double[][] X,
                      int D,
                      int K)

      • plottree

        public void plottree​(int D,
                     int K,
                     int[] parents,
                     int numClusters)