将float数组划分为相似的段（集群）

Question

我有这样一个浮点数组：

[1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200]

现在，我想像这样对数组进行分区：

[[1.91, 2.87, 3.61] , [10.91, 11.91, 12.82] , [100.73, 100.71, 101.89] , [200]]

// [200]由于集群支持较少，将被视为异常值

我必须为多个数组找到这种段，但我不知道分区大小应该是多少。我试图通过使用层次聚类（聚集）来做到这一点
，它为我提供了令人满意的结果。但是，问题是，建议我不要对一维问题使用聚类算法，因为这样做没有任何理论上的依据（因为它们是针对多维数据的）。

我发现了另一个建议，而不是聚类，即自然休息优化。但是，这还需要像K-means一样声明分区号（对吗？）。

这是相当令人困惑的（特别是因为我必须在几个数组上执行那种分段，并且不可能知道最佳的分区号）。

是否有任何方法可以找到分区（因此我们可以减少分区内的方差并最大化分区之间的方差），并且具有一些理论上的依据？

任何具有理论依据的指向文章/论文的指针（如果可用的C / C ++ / Java实现）将对我非常有帮助。

Answer 1

我认为我将对数据进行排序（如果尚未排序），然后采用相邻的差异。将差异除以较小的数字，即得出百分比变化之间的差异。设置一个阈值，当更改超过该阈值时，启动一个新的“集群”。

编辑：C ++中的快速演示代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <functional>

int main() {
    std::vector<double> data{ 
        1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200 
    };

    // sort the input data
    std::sort(data.begin(), data.end());

    // find the difference between each number and its predecessor
    std::vector<double> diffs;
    std::adjacent_difference(data.begin(), data.end(), std::back_inserter(diffs));

    // convert differences to percentage changes
    std::transform(diffs.begin(), diffs.end(), data.begin(), diffs.begin(),
        std::divides<double>());

    // print out the results
    for (int i = 0; i < data.size(); i++) {

        // if a difference exceeds 40%, start a new group:
        if (diffs[i] > 0.4)
            std::cout << "\n";

        // print out an item:
        std::cout << data[i] << "\t";
    }

    return 0;
}

结果：

1.91    2.87    3.61
10.91   11.91   12.82
100.71  100.73  101.89
200