判別規準による分割

各項目のスコアを一次元の数直線上にならべると、数直線上での点の近さは項目間の 類似性を表していると考えられる。従って、類似した該当ベクトルを持つ項目を同じ クラスターに割り当てるためには平均クラスター内分散（級内分散）を小さくすれば よい。また、数直線上での順序を無視してクラスターを割り当てると明らかに平均ク ラスター内分散は大きくなる。従って、数直線上の $M$ 個の点を、各クラスターの 点の数を $D$ 以下にするという制約条件のもとで、平均クラスター内分散を最小に するように $K-1$ 個のしきい値によって $K$ 個のクラスターに分割すればよいこと になる。この問題は本質的には、大津の多値化のための自動しきい値選定法 [127,128]と同じになる。日程表作成の場合には、しきい値の組は制約条件 付きダイナミックプログラミングによって求めることができ、その手続きの手間は $O(K(M-K)^2)$ である。従って、全体としてクラスタリングに必要な手間は、数量化 の手間 $O(M^3)$ を加えて$O(M^3)$ となる。