Jenks自然断点是确定性的吗？

Question

4

即，对于一个一维数字列表，该算法是否总是返回相同的结果？费舍尔的自然断点（Jenks的O(knlog(n))优化）是否是确定性的？

- user8396610

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

Fisher的自然分组方法使用动态规划找到最优解，是确定性的。Jenk的自然分组方法有两种变体。

1. 一种方法将一个单位从方差最大的类别移动到方差最小的类别。该方法并不总是返回最优答案。这基于任意的初始类别，因此是不确定性的。 2. 另一种方法检查所有的分区，这将始终返回最优答案，并且是确定性的。

该页面提供了Fisher算法的最优性证明，并指出基本的Jenk算法无法给出最优答案。迭代地将高变化类别的值移动到低变化类别在维基百科上有讨论，但这并不总是导致最优解。