Class KDTreePruningKMeans.Instance

    • Field Detail

      • iter

        protected DBIDArrayMIter iter
        Iterator into the k-d-tree entries.
      • indices

        protected int[] indices
        Array of candidate indexes.
      • clusterSums

        protected double[][] clusterSums
        To aggregate the sum of a cluster.
      • clusterSizes

        protected int[] clusterSizes
        Number of elements in each cluster.
    • Constructor Detail

      • Instance

        public Instance​(Relation<? extends NumberVector> relation,
                        NumberVectorDistance<?> df,
                        double[][] means)
        Constructor.
        Parameters:
        relation - Relation of data points
        df - Distance function
        means - Initial means
    • Method Detail

      • buildTreeMidpoint

        protected KDTreePruningKMeans.KDNode buildTreeMidpoint​(Relation<? extends NumberVector> relation,
                                                               int left,
                                                               int right)
        Build the k-d-tree using midpoint splitting.
        Parameters:
        relation - Data relation
        left - Left subinterval
        right - Right subinterval
        Returns:
        Root node
      • iterate

        protected int iterate​(int iteration)
        Description copied from class: AbstractKMeans.Instance
        Main loop function.
        Specified by:
        iterate in class AbstractKMeans.Instance
        Parameters:
        iteration - Iteration number (beginning at 1)
        Returns:
        Number of reassigned points
      • traversal

        protected int traversal​(KDTreePruningKMeans.KDNode u,
                                int alive)
        The tree traversal algorithm.
        Parameters:
        u - Current node
        alive - Number of alive centers
        Returns:
        Number of relabeled point
      • labelSubtree

        protected int labelSubtree​(double[] sum,
                                   int start,
                                   int end,
                                   int index)
        Label an entire subtree.
        Parameters:
        sum - Node sum
        start - Start offset
        end - End offset
        index - New mean index
        Returns:
        Number of reassigned points (for convergence)
      • pruning

        protected int pruning​(KDTreePruningKMeans.KDNode u,
                              int alive)
        The pruning algorithm.
        Parameters:
        u - Current node
        alive - Range of alive means
        Returns:
        Updated range.
      • getMinMaxDist

        protected double getMinMaxDist​(double[] mid,
                                       double[] halfwidth,
                                       int alive)
        Get the smallest maximum distance for pruning.
        Parameters:
        mid - Midpoint
        halfwidth - Half width
        alive - Number of alive centers
        Returns:
        Smallest maximum distance
      • mindist

        protected double mindist​(double[] mean,
                                 double[] mid,
                                 double[] halfwidth)
        Get the smallest maximum distance for pruning.
        Parameters:
        mean - Cluster mean
        mid - Midpoint
        halfwidth - Half width
        Returns:
        Minimum distance
      • traverseLeaf

        protected int traverseLeaf​(int start,
                                   int end,
                                   int alive)
        Traversal of a leaf (assuming alive > 1)
        Parameters:
        start - Start index
        end - End index
        alive - Number of alive means
        Returns:
        Number of relabeled points (for convergence)