数据直方图 - 优化的二进制宽度优化

以下是我从这里写的这个算法的 Python 版本的端口。我知道 API 可以完成一些工作，但这应该足以让您入门。此代码的结果与 Python 代码针对相同输入数据生成的结果相同。

public class HistSample
{
    public static void CalculateOptimalBinWidth(double[] x)
    {
        double xMax = x.Max(), xMin = x.Min();
        int minBins = 4, maxBins = 50;
        double[] N = Enumerable.Range(minBins, maxBins - minBins)
            .Select(v => (double)v).ToArray();
        double[] D = N.Select(v => (xMax - xMin) / v).ToArray();
        double[] C = new double[D.Length];
        for (int i = 0; i < N.Length; i++)
        {
            double[] binIntervals = LinearSpace(xMin, xMax, (int)N[i] + 1);
            double[] ki = Histogram(x, binIntervals);
            ki = ki.Skip(1).Take(ki.Length - 2).ToArray();
            double mean = ki.Average();
            double variance = ki.Select(v => Math.Pow(v - mean, 2)).Sum() / N[i];
            C[i] = (2 * mean - variance) / (Math.Pow(D[i], 2));
        }
        double minC = C.Min();
        int index = C.Select((c, ix) => new { Value = c, Index = ix })
            .Where(c => c.Value == minC).First().Index;
        double optimalBinWidth = D[index];
    }
    public static double[] Histogram(double[] data, double[] binEdges)
    {
        double[] counts = new double[binEdges.Length - 1];
        for (int i = 0; i < binEdges.Length - 1; i++)
        {
            double lower = binEdges[i], upper = binEdges[i + 1];
            for (int j = 0; j < data.Length; j++)
            {
                if (data[j] >= lower && data[j] <= upper)
                {
                    counts[i]++;
                }
            }
        }
        return counts;
    }
    public static double[] LinearSpace(double a, double b, int count)
    {
        double[] output = new double[count];
        for (int i = 0; i < count; i++)
        {
            output[i] = a + ((i * (b - a)) / (count - 1));
        }
        return output;
    }
}

像这样运行它：

double[] x =
{
    4.37, 3.87, 4.00, 4.03, 3.50, 4.08, 2.25, 4.70, 1.73,
    4.93, 1.73, 4.62, 3.43, 4.25, 1.68, 3.92, 3.68, 3.10,
    4.03, 1.77, 4.08, 1.75, 3.20, 1.85, 4.62, 1.97, 4.50,
    3.92, 4.35, 2.33, 3.83, 1.88, 4.60, 1.80, 4.73, 1.77,
    4.57, 1.85, 3.52, 4.00, 3.70, 3.72, 4.25, 3.58, 3.80,
    3.77, 3.75, 2.50, 4.50, 4.10, 3.70, 3.80, 3.43, 4.00,
    2.27, 4.40, 4.05, 4.25, 3.33, 2.00, 4.33, 2.93, 4.58,
    1.90, 3.58, 3.73, 3.73, 1.82, 4.63, 3.50, 4.00, 3.67,
    1.67, 4.60, 1.67, 4.00, 1.80, 4.42, 1.90, 4.63, 2.93,
    3.50, 1.97, 4.28, 1.83, 4.13, 1.83, 4.65, 4.20, 3.93,
    4.33, 1.83, 4.53, 2.03, 4.18, 4.43, 4.07, 4.13, 3.95,
    4.10, 2.27, 4.58, 1.90, 4.50, 1.95, 4.83, 4.12
};
HistSample.CalculateOptimalBinWidth(x);

检查直方图函数。 如果任何数据元素不幸等于箱边界（第一个或最后一个箱除外），它们将被计入两个连续的箱中。代码需要检查（下<=data[j]&&data[j]<上），并处理所有等于xMax的元素进入最后一个箱的情况。>

nick_w答案的小更新。

如果你真的需要垃圾箱。加上优化了直方图函数中的双循环，并摆脱了linspace函数。

     /// <summary>
     /// Calculate the optimal bins for the given data
     /// </summary>
     /// <param name="x">The data you have</param>
     /// <param name="xMin">The minimum element</param>
     /// <param name="optimalBinWidth">The width between each bin</param>
     /// <returns>The bins</returns>
     public static int[] CalculateOptimalBinWidth(List<double> x, out double xMin, out double optimalBinWidth)
     {
        var xMax = x.Max();
        xMin = x.Min();
        optimalBinWidth = 0;
        const int MIN_BINS = 1;
        const int MAX_BINS = 20;
        int[] minKi = null;
        var minOffset = double.MaxValue;
        foreach (var n in Enumerable.Range(MIN_BINS, MAX_BINS - MIN_BINS).Select(v => v*5))
        {
           var d = (xMax - xMin)/n;
           var ki = Histogram(x, n, xMin, d);
           var ki2 = ki.Skip(1).Take(ki.Length - 2).ToArray();
           var mean = ki2.Average();
           var variance = ki2.Select(v => Math.Pow(v - mean, 2)).Sum()/n;
           var offset = (2*mean - variance)/Math.Pow(d, 2);
           if (offset < minOffset)
           {
              minKi = ki;
              minOffset = offset;
              optimalBinWidth = d;
           }
        }
        return minKi;
     }
     private static int[] Histogram(List<double> data, int count, double xMin, double d)
     {
        var histogram = new int[count];
        foreach (var t in data)
        {
           var bucket = (int) Math.Truncate((t - xMin)/d);
           if (count == bucket) //fix xMax
              bucket --;
           histogram[bucket]++;
        }
        return histogram;
     }

我建议二叉搜索以加快对类间隔的分配。

public void Add(double element)
{
  if (element < Bins.First().LeftBound || element > Bins.Last().RightBound)
    return;
  var min = 0;
  var max = Bins.Length - 1;
  var index = 0;
  while (min <= max)
  {
    index = min + ((max - min) / 2);
    if (element >= Bins[index].LeftBound && element < Bins[index].RightBound)
      break;
    if (element < Bins[index].LeftBound)
      max = index - 1;
    else
      min = index + 1;
  }
  Bins[index].Count++;
}

Bins"是类型为"TrutogramItem"的项目列表，它定义了"Leftbound"，"RightBound"和"Count"等属性。