Not all of my ideas for machine learning algorithms work out well. I usually do quite a bit of thinking before putting an idea down in code, so my failure rate with new algorithms is quite low. But recently I botched thinking through an idea.

My idea (which wasn’t good as it turns out) was to improve the k-means++ clustering algorithm by using tournament selection instead of roulette wheel selection. I coded up an implementation of my idea, and it works, but it doesn’t improve upon k-means++ with roulette wheel. Because k-means++ with roulette wheel is a de facto standard, any new algorithm must be significantly better to be appealing. My idea of tournament initialization is equal at best.

The k-means++ roulette wheel initialization picks a data item to act as a mean. The technique picks a data item in a way that is proportional to the squared distances to the closest means. The consequence is that any data item could be picked, even though a data item that is far from its closest mean will be most likely to be picked (which is good).

My idea of k-means clustering using tournament initialization works, but it didn’t improve upon standard k-means++ initialization. Darn.

For example, suppose there are only five data items (in a realistic scenario there’d be hundreds or thousands) and the distances to the associated closest mean are (2.0, 5.0, 1.0, 4.0, 3.0). The squared distances are (4, 25, 1, 16, 9). You want to pick item [1] because it has the largest squared distance.

Roulette wheel selection picks an item according to the probabilities (4/55, 25/55, 1/55, 16/55, 9/55) = (0.07, 0.45, 0.02, 0.29, 0.17). You will probably get a good data item that’s far from its mean but you could get a poor item that’s close to its means.

Tournament selection with tournPct = 0.80 picks the best item from an 80% of randomly selected items based on distance (not squared distance). My incorrect thought was that this would increase the chances of getting a good item compared to roulette wheel selection. My reasoning was that if the five distances-to-closest-means were very close to each other, then roulette wheel selection could easily give you the fifth best data item.

My reasoning was correct but it didn’t go far enough. The second part is that if the distances-to-closest-means are very close then it doesn’t matter if you get the fifth best data items because all five are pretty good.

Argh.

But I wasn’t really annoyed at all with myself for coding up an idea that didn’t go anywhere. I learned a lot and picked up some new ideas and coding techniques that could be valuable in the future. As one of many similar saying goes, “Don’t be afraid to try and then fail; be afraid to fail to try.” It doesn’t take too much courage to take risks with machine learning algorithms — you only risk time.

The first moon landing in 1969 is clearly one of the greatest accomplishments in history. There were many heroic men who weren’t afraid to take risks, when failure had serious consequences. Left: Yuri Gagarin, the Soviet cosmonaut who was the first man into space in 1961. Right: The crew of Apollo 11, the first men to reach the surface of the moon. Neil Armstrong, Michael Collins, Edwin Aldrin.

  private static void InitTourn(double[][] data, int[] clustering,
    double[][] means, Random rnd, double tournPct)
  {
    //  k-means init using tournament selection
    // clustering[] and means[][] exist
    int N = data.Length;
    int dim = data[0].Length;
    int K = means.Length;

    // select one data item index at random
    int idx = rnd.Next(0, N); // [0, N)
    for (int j = 0; j (lt) dim; ++j)
      means[0][j] = data[idx][j];

    for (int k = 1; k (lt) K; ++k) // find each remaining mean
    {
      double[] distVals = new double[N];  // to nearest mean

      for (int i = 0; i (lt) N; ++i) // each data item
      {
        // compute distances from data[i] to
        // each existing mean (to find closest)
        double[] distances = new double[k]; // curre have k means

        for (int ki = 0; ki (lt) k; ++ki)
          distances[ki] = EucDistance(data[i], means[ki]);

        int mi = ArgMin(distances);  // index of closest mean
        distVals[i] = distances[mi];
      } // i

      // select an item far from its mean using tournament
      // if an item has been used as a mean distance will be 0
      // so it's very unlikely to be selected again
      int newMeanIdx = TournSelect(distVals, rnd, tournPct);
      for (int j = 0; j (lt) dim; ++j)
        means[k][j] = data[newMeanIdx][j];
    } // k remaining means

      UpdateClustering(clustering, data, means);
  } // InitTourn

  static int TournSelect(double[] vals, Random rnd, double pct)
  {
    // find index of a large value in vals
    int n = vals.Length;
    int[] indices = new int[n];
    for (int i = 0; i (lt) n; ++i)
      indices[i] = i;
    Shuffle(indices, rnd);

    int numCands = (int)(pct * n);  // number random candidates
    int maxIdx = indices[0];
    double maxVal = vals[maxIdx];
    for (int i = 0; i (lt) numCands; ++i)
    {
      int idx = indices[i];  // pts into vals
      if (vals[idx] (gt) maxVal)
      {
        maxVal = vals[idx];
        maxIdx = idx;
      }
    }
    return maxIdx;
  }

  private static void Shuffle(int[] indices, Random rnd)
  {
    int n = indices.Length;
    for (int i = 0; i (lt) n; ++i)
    {
      int ri = rnd.Next(i, n);
      int tmp = indices[ri];
      indices[ri] = indices[i];
      indices[i] = tmp;
    }
  }

  private static double EucDistance(double[] item,
    double[] mean)
  {
    // Euclidean distance from item to mean
    double sum = 0.0;
    for (int j = 0; j (lt) item.Length; ++j)
      sum += (item[j] - mean[j]) * (item[j] - mean[j]);
    return Math.Sqrt(sum);
  }