<commit_before>package hex.kmeans;

import hex.ModelBuilder;
import hex.schemas.KMeansV2;
import hex.schemas.ModelBuilderSchema;
import water.*;
import water.H2O.H2OCountedCompleter;
import water.fvec.Chunk;
import water.fvec.Vec;
import water.util.ArrayUtils;
import water.util.Log;
import water.util.RandomUtils;

import java.util.ArrayList;
import java.util.Random;

/**
 * Scalable K-Means++ (KMeans||)<br>
 * http://theory.stanford.edu/~sergei/papers/vldb12-kmpar.pdf<br>
 * http://www.youtube.com/watch?v=cigXAxV3XcY
 */
public class KMeans extends ModelBuilder<KMeansModel,KMeansModel.KMeansParameters,KMeansModel.KMeansOutput> {
  public enum Initialization {
    None, PlusPlus, Furthest
  }

  // Number of categorical columns
  private int _ncats;

  // Number of reinitialization attempts for preventing empty clusters
  transient private int reinit_attempts;

  // Called from an http request
  public KMeans( KMeansModel.KMeansParameters parms ) { super("K-means",parms); init(); }

  public ModelBuilderSchema schema() { return new KMeansV2(); }


  /** Start the KMeans training Job on an F/J thread. */
  @Override public Job<KMeansModel> trainModel() {
    return start(new KMeansDriver(), _parms._max_iters);
  }

  /** Initialize the ModelBuilder, validating all arguments and preparing the
   *  training frame.  This call is expected to be overridden in the subclasses
   *  and each subclass will start with "super.init();".
   *
   *  Validate K, max_iters and the number of rows.  Precompute the number of
   *  categorical columns. */
  @Override public void init() {
    super.init();
    if( _parms._K < 2 || _parms._K > 9999999 ) error("K", "K must be between 2 and 10 million");
    if( _parms._max_iters < 1 || _parms._max_iters > 999999) error("max_iters", "must be between 1 and a million");
    if( _train == null ) return; // Nothing more to check
    if( _train.numRows() < _parms._K ) error("K","Cannot make " + _parms._K + " clusters out of " + _train.numRows() + " rows.");

    for( Vec v : _train.vecs() )
      if( v.isEnum() ) _ncats++;

    // Sort columns, so the categoricals are all up front.  They use a
    // different distance metric than numeric columns.
    Vec vecs[] = _train.vecs();
    int ncats=0, len=vecs.length; // Feature count;
    while( ncats != len ) {
      while( ncats < len && vecs[ncats].isEnum() ) ncats++;
      while( len > 0 && !vecs[len-1].isEnum() ) len--;
      if( ncats < len-1 ) { _train.swap(ncats,len-1); _valid.swap(ncats,len-1); }
    }
    _ncats = ncats;
  }

  // ----------------------
  private class KMeansDriver extends H2OCountedCompleter<KMeansDriver> {

    @Override protected void compute2() {

      KMeansModel model = null;
      try {
        _parms.lock_frames(KMeans.this); // Fetch & read-lock input frames

        // The model to be built
        model = new KMeansModel(dest(), _parms, new KMeansModel.KMeansOutput(KMeans.this));
        model.delete_and_lock(_key);

        // means are used to impute NAs
        model._output._ncats = _ncats;
        Vec vecs[] = _train.vecs();
        final int N = vecs.length; // Feature count
        double[] means = new double[N];
        for( int i = 0; i < N; i++ )
          means[i] = vecs[i].mean();
        // mults & means for normalization
        double[] mults = null;
        if( _parms._normalize ) {
          mults = new double[N];
          for( int i = 0; i < N; i++ ) {
            double sigma = vecs[i].sigma();
            mults[i] = normalize(sigma) ? 1.0 / sigma : 1.0;
          }
        }

        // Initialize clusters
        Random rand = water.util.RandomUtils.getRNG(_parms._seed - 1);
        double clusters[][];    // Normalized cluster centers
        if( _parms._init == Initialization.None ) {
          // Initialize all clusters to random rows
          clusters = model._output._clusters = new double[_parms._K][_train.numCols()];
          for( double[] cluster : clusters )
            randomRow(vecs, rand, cluster, means, mults);
        } else {
          clusters = new double[1][vecs.length];
          // Initialize first cluster to random row
          randomRow(vecs, rand, clusters[0], means, mults);

          while( model._output._iters < 5 ) {
            // Sum squares distances to clusters
            SumSqr sqr = new SumSqr(clusters,means,mults,_ncats).doAll(vecs);

            // Sample with probability inverse to square distance
            Sampler sampler = new Sampler(clusters, means, mults, _ncats, sqr._sqr, _parms._K * 3, _parms._seed).doAll(vecs);
            clusters = ArrayUtils.append(clusters,sampler._sampled);

            // Fill in sample clusters into the model
            if( !isRunning() ) return; // Stopped/cancelled
            model._output._clusters = denormalize(clusters, _ncats, means, mults);
            model._output._mse = sqr._sqr/_train.numRows();

            model._output._iters++;     // One iteration done

            // This doesn't count towards model building (we didn't account these iterations as work to be done during construction)
            // update(1);          // One unit of work

            model.update(_key); // Early version of model is visible
          }
          // Recluster down to K normalized clusters
          clusters = recluster(clusters, rand);
        }
        model._output._iters = 0;     // Reset iteration count

        // ---
        // Run the main KMeans Clustering loop
        // Stop after enough iterations
        LOOP:
        for( ; model._output._iters < _parms._max_iters; model._output._iters++ ) {
          if( !isRunning() ) return; // Stopped/cancelled
          Lloyds task = new Lloyds(clusters,means,mults,_ncats, _parms._K).doAll(vecs);
          // Pick the max categorical level for clusters' center
          max_cats(task._cMeans,task._cats);

          // Handle the case where some clusters go dry.  Rescue only 1 cluster
          // per iteration ('cause we only tracked the 1 worst row)
          boolean badrow=false;
          for( int clu=0; clu<_parms._K; clu++ ) {
            if (task._rows[clu] == 0) {
              // If we see 2 or more bad rows, just re-run Lloyds to get the
              // next-worst row.  We don't count this as an iteration, because
              // we're not really adjusting the centers, we're trying to get
              // some centers *at-all*.
              if (badrow) {
                Log.warn("KMeans: Re-running Lloyds to re-init another cluster");
                model._output._iters--; // Do not count against iterations
                if (reinit_attempts++ < _parms._K) {
                  continue LOOP;  // Rerun Lloyds, and assign points to centroids
                } else {
                  reinit_attempts = 0;
                  break; //give up and accept empty cluster
                }
              }
              long row = task._worst_row;<commit_msg>Fix bug with validationerrors on KMeans<commit_after>package hex.kmeans;

import hex.ModelBuilder;
import hex.schemas.KMeansV2;
import hex.schemas.ModelBuilderSchema;
import water.*;
import water.H2O.H2OCountedCompleter;
import water.fvec.Chunk;
import water.fvec.Vec;
import water.util.ArrayUtils;
import water.util.Log;
import water.util.RandomUtils;

import java.util.ArrayList;
import java.util.Random;

/**
 * Scalable K-Means++ (KMeans||)<br>
 * http://theory.stanford.edu/~sergei/papers/vldb12-kmpar.pdf<br>
 * http://www.youtube.com/watch?v=cigXAxV3XcY
 */
public class KMeans extends ModelBuilder<KMeansModel,KMeansModel.KMeansParameters,KMeansModel.KMeansOutput> {
  public enum Initialization {
    None, PlusPlus, Furthest
  }

  // Number of categorical columns
  private int _ncats;

  // Number of reinitialization attempts for preventing empty clusters
  transient private int _reinit_attempts;

  // Called from an http request
  public KMeans( KMeansModel.KMeansParameters parms ) { super("K-means",parms); init(); }

  public ModelBuilderSchema schema() { return new KMeansV2(); }


  /** Start the KMeans training Job on an F/J thread. */
  @Override public Job<KMeansModel> trainModel() {
    return start(new KMeansDriver(), _parms._max_iters);
  }

  /** Initialize the ModelBuilder, validating all arguments and preparing the
   *  training frame.  This call is expected to be overridden in the subclasses
   *  and each subclass will start with "super.init();".
   *
   *  Validate K, max_iters and the number of rows.  Precompute the number of
   *  categorical columns. */
  @Override public void init() {
    super.init();
    if( _parms._K < 2 || _parms._K > 9999999 ) error("_K", "K must be between 2 and 10 million");
    if( _parms._max_iters < 1 || _parms._max_iters > 999999) error("_max_iters", "must be between 1 and a million");
    if( _train == null ) return; // Nothing more to check
    if( _train.numRows() < _parms._K ) error("_K","Cannot make " + _parms._K + " clusters out of " + _train.numRows() + " rows.");

    for( Vec v : _train.vecs() )
      if( v.isEnum() ) _ncats++;

    // Sort columns, so the categoricals are all up front.  They use a
    // different distance metric than numeric columns.
    Vec vecs[] = _train.vecs();
    int ncats=0, len=vecs.length; // Feature count;
    while( ncats != len ) {
      while( ncats < len && vecs[ncats].isEnum() ) ncats++;
      while( len > 0 && !vecs[len-1].isEnum() ) len--;
      if( ncats < len-1 ) { _train.swap(ncats,len-1); _valid.swap(ncats,len-1); }
    }
    _ncats = ncats;
  }

  // ----------------------
  private class KMeansDriver extends H2OCountedCompleter<KMeansDriver> {

    @Override protected void compute2() {

      KMeansModel model = null;
      try {
        _parms.lock_frames(KMeans.this); // Fetch & read-lock input frames

        // The model to be built
        model = new KMeansModel(dest(), _parms, new KMeansModel.KMeansOutput(KMeans.this));
        model.delete_and_lock(_key);

        // means are used to impute NAs
        model._output._ncats = _ncats;
        Vec vecs[] = _train.vecs();
        final int N = vecs.length; // Feature count
        double[] means = new double[N];
        for( int i = 0; i < N; i++ )
          means[i] = vecs[i].mean();
        // mults & means for normalization
        double[] mults = null;
        if( _parms._normalize ) {
          mults = new double[N];
          for( int i = 0; i < N; i++ ) {
            double sigma = vecs[i].sigma();
            mults[i] = normalize(sigma) ? 1.0 / sigma : 1.0;
          }
        }

        // Initialize clusters
        Random rand = water.util.RandomUtils.getRNG(_parms._seed - 1);
        double clusters[][];    // Normalized cluster centers
        if( _parms._init == Initialization.None ) {
          // Initialize all clusters to random rows
          clusters = model._output._clusters = new double[_parms._K][_train.numCols()];
          for( double[] cluster : clusters )
            randomRow(vecs, rand, cluster, means, mults);
        } else {
          clusters = new double[1][vecs.length];
          // Initialize first cluster to random row
          randomRow(vecs, rand, clusters[0], means, mults);

          while( model._output._iters < 5 ) {
            // Sum squares distances to clusters
            SumSqr sqr = new SumSqr(clusters,means,mults,_ncats).doAll(vecs);

            // Sample with probability inverse to square distance
            Sampler sampler = new Sampler(clusters, means, mults, _ncats, sqr._sqr, _parms._K * 3, _parms._seed).doAll(vecs);
            clusters = ArrayUtils.append(clusters,sampler._sampled);

            // Fill in sample clusters into the model
            if( !isRunning() ) return; // Stopped/cancelled
            model._output._clusters = denormalize(clusters, _ncats, means, mults);
            model._output._mse = sqr._sqr/_train.numRows();

            model._output._iters++;     // One iteration done

            // This doesn't count towards model building (we didn't account these iterations as work to be done during construction)
            // update(1);          // One unit of work

            model.update(_key); // Early version of model is visible
          }
          // Recluster down to K normalized clusters
          clusters = recluster(clusters, rand);
        }
        model._output._iters = 0;     // Reset iteration count

        // ---
        // Run the main KMeans Clustering loop
        // Stop after enough iterations
        LOOP:
        for( ; model._output._iters < _parms._max_iters; model._output._iters++ ) {
          if( !isRunning() ) return; // Stopped/cancelled
          Lloyds task = new Lloyds(clusters,means,mults,_ncats, _parms._K).doAll(vecs);
          // Pick the max categorical level for clusters' center
          max_cats(task._cMeans,task._cats);

          // Handle the case where some clusters go dry.  Rescue only 1 cluster
          // per iteration ('cause we only tracked the 1 worst row)
          boolean badrow=false;
          for( int clu=0; clu<_parms._K; clu++ ) {
            if (task._rows[clu] == 0) {
              // If we see 2 or more bad rows, just re-run Lloyds to get the
              // next-worst row.  We don't count this as an iteration, because
              // we're not really adjusting the centers, we're trying to get
              // some centers *at-all*.
              if (badrow) {
                Log.warn("KMeans: Re-running Lloyds to re-init another cluster");
                model._output._iters--; // Do not count against iterations
                if (_reinit_attempts++ < _parms._K) {
                  continue LOOP;  // Rerun Lloyds, and assign points to centroids
                } else {
                  _reinit_attempts = 0;
                  break; //give up and accept empty cluster
                }
              }
              long row = task._worst_row;
{'fraction_non_alphanumeric': 0.11561691113028473, 'fraction_numerical': 0.007621512798389416, 'mean_word_length': 2.2482484820177486, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6638292', 'n_tokens_mistral': 4354, 'n_tokens_neox': 4154, 'n_words': 1236}