AI - Normal Float

2 secs 1024 MB

これは $k$ -median problem の一種です。
一般には NP 困難であることが知られていますが、1 次元の場合のみ動的計画法を用いた $O(MN^2)$ の解法が知られています。
以下の解法は 4 つのステップで構成されます。

データポイントを昇順にソートします。これにより、連続した区間としてクラスタを扱うことができます。

区間コストの計算
ソートされたデータの部分区間（位置 i から j まで）について、その区間内のデータを 1 つの値に丸めたときの誤差を計算します。このコストは以下のように計算されます。

$\text{cost}(i, j) = \sum |x_l - m_{ij}|$

ここで、 $m_{ij}$ は区間 $[i, j]$ の中央値です。
コストの前計算
全ての区間についてコストを計算し、二次元配列に保存します。計算量は $O(N^2)$ です。

DP テーブルの定義
( dp[i][k] ) を、最初の i 個のデータポイントを k 個のクラスタに分割したときの最小コストとします。
初期化
( dp[0][0] = 0 ) とし、他の初期値は無限大に設定します。
状態遷移
以下の再帰式で DP テーブルを更新します。

$dp[i][k] = \min_{0 \leq p < i} (dp[p][k-1] + \text{cost}(p+1, i))$

ここで、 $\text{cost}(p+1, i)$ はデータポイント $p+1$ から $i$ までを 1 つのクラスタにまとめたときのコストです。

DP テーブルを逆にたどることで、最適なクラスタの境界と各クラスタの中央値を復元します。

計算量は動的計画法がネックとなり $O(MN^2)$ で解が求められます。
ちなみにどうして各クラスタにおいて中央値へ丸めることが最適と言えるのかは、下記サイトが参考になります。
「平均値は二乗誤差最小，中央値は絶対誤差最小」 - 高校数学の美しい物語様