多値分割（マルチバリュー・パーティショニング）は、データ空間や値域を複数の意味論的に一貫したサブセットに分割する数学的手法の総称である。応用数学の一分野として機械学習、情報理論、組み合わせ最適化などで広く用いられ、古典的な二値分割が各要素を正／負の二クラスに分類するのに対し、三値以上のクラスや連続的な値域の離散化を扱う点に特徴がある。本項では、多値分割の定義、理論的枠組み、代表的なアルゴリズム、応用事例、および数理的課題について解説する。
1.1 多値分割の定義と基本概念
多値分割とは、与えられた集合 \( X \) を、互いに素な部分集合 \( X_1, X_2, \dots, X_k \)（\( k \ge 3 \)）に分割する操作を指す。各部分集合は「クラス」「カテゴリ」「領域」などと呼ばれ、分割は全射 \( f: X \to \{1, 2, \dots, k\} \) として表現される。この分割は、データの構造や目的に応じて、情報理論的な基準や幾何学的な条件に基づいて決定される。基本概念として、分割の一貫性（各部分集合内の類似性が高く、異なる部分集合間の差異が大きいこと）や、分割の粒度（クラス数の選択問題）が重要となる。
1.2 二値分割との差異
二値分割（バイナリ・パーティショニング）は、各要素を正／負の二クラスに分類する単純な構造を持つ。これに対して多値分割は、三つ以上のクラスを同時に扱うため、分割の評価指標（後述の情報利得やコスト関数）が多クラス対応に拡張される必要がある。また、二値分割では単一の閾値で分離可能な問題が多いが、多値分割では複数の閾値や複雑な境界が必要となる。計算複雑性の観点では、多値分割は一般に二値分割よりも高いコストを伴う。
1.3 関連分野との関係
多値分割は、機械学習における多クラス分類や決定木、クラスタリング、画像分割、符号理論における多値量子化、暗号理論の秘密分散法、組合せ最適化における資源配分問題など、多くの分野と密接に関連する。これらの分野では、データの特性や目的に応じて異なる分割手法が採用され、理論と実践の両面から研究が進められている。
多値分割の数学的基盤は、集合分割の理論、半順序構造、評価指標の最適化問題によって構成される。本章では、これらの基礎概念を整理し、最適分割の存在や計算複雑性について述べる。
2.1 集合分割と半順序構造
集合 \( X \) の分割とは、\( X = \bigcup_{i=1}^k X_i \) かつ \( i \neq j \) ならば \( X_i \cap X_j = \emptyset \) を満たす部分集合族 \( \{X_i\} \) である。この分割全体の集合は、細分関係に基づく半順序構造を持つ。すなわち、分割 \( P \) が分割 \( Q \) よりも「細かい」とは、\( P \) の各ブロックが \( Q \) のいずれかのブロックに完全に含まれることをいう。この構造は、階層的クラスタリングや決定木の再帰的分割において重要な役割を果たす。
2.2 分割の評価指標
分割の品質を数値化するため、いくつかの評価指標が用いられる。代表的なものとして情報利得と分割コスト関数がある。
2.2.1 情報利得とエントロピー
情報理論に基づく指標として、エントロピーを用いた情報利得が広く利用される。データ集合 \( S \) が \( k \) 個のクラスに分割されたとき、エントロピー \( H(S) \) は \( H(S) = -\sum_{i=1}^k p_i \log_2 p_i \) で定義される（\( p_i \) は各クラスの出現確率）。分割後のエントロピーと元のエントロピーの差が情報利得であり、値が大きいほど分割が有効であると判断される。決定木の学習（C4.5など）では、この指標を用いて最適な分割点を選択する。
2.2.2 分割コスト関数
コスト関数は、分割の質を最小化問題として定式化する際に用いられる。例えば、k-meansクラスタリングでは、各クラスタ内の平方和誤差（SSE）がコストとして定義される。また、一次元データの最適分割では、各区間内の分散や誤差の総和がコストとなる。一般に、コスト関数は凸性や単調性などの性質を持ち、効率的な最適化アルゴリズムの設計に寄与する。
2.3 最適分割の存在と一意性
与えられた評価指標の下で最適な分割を求める問題は、数学的に興味深い性質を持つ。ただし、多くの実用的な設定では解の一意性は保証されず、複数の局所最適解が存在する。
2.3.1 凸最適化との接点
コスト関数が凸である場合、最適分割問題は凸最適化問題に帰着できる。例えば、一次元データに対する動的計画法による分割では、コスト関数が凸であれば、単調性を利用した効率的なアルゴリズム（例えば、Convex Hull Trick）が適用可能である。また、情報利得の最大化は凹関数の最大化問題として捉えられることがある。
2.3.2 NP困難性と近似可能性
一般に、多値分割の最適化問題はNP困難であることが知られている。特に、kが固定されていない場合や、多次元空間における分割では、厳密解を多項式時間で求めることは不可能と予想される。そのため、近似アルゴリズムやヒューリスティック手法（貪欲法、局所探索など）が重要な役割を果たす。例えば、k-means++やCARTの貪欲分割は、実用的な近似解を与える。
多値分割を実現するためのアルゴリズムは、再帰的分割法、クラスタリングに基づく手法、動的計画法による最適分割などに分類される。本章では代表的なものを紹介する。
3.1 再帰的分割法（決定木系）
決定木は、再帰的にデータ空間を分割することで多値分類を実現する。二値分割の決定木を多値に拡張したバリエーションが存在する。
3.1.1 CARTの多値拡張
CART（Classification And Regression Tree）は通常二値分割を行うが、カテゴリカル変数に対しては多値分割を自然に扱う。具体的には、各カテゴリを一つの枝として分割する方法や、カテゴリをグループ化して二値に還元する方法が用いられる。また、回帰問題では連続値の離散化を伴う多値分割が実装される。
3.1.2 C4.5とそのバリエーション
C4.5は情報利得比を用いて多値分割を直接行う決定木アルゴリズムである。カテゴリカル属性では各値に対応する枝を生成し、連続値属性では閾値による二値分割を複数回適用することで多値分割を実現する。後続のC5.0やSee5などのバリエーションでは、ブースティングやコスト考慮型の学習が加えられ、分類性能が向上している。
3.2 クラスタリングに基づく分割
クラスタリングは、データを類似性に基づいて複数のグループに自動分割する手法であり、多値分割の一形態と見なせる。
3.2.1 k-meansの多値適用
k-meansは、指定されたクラスタ数 \( k \) にデータを分割する代表的なアルゴリズムである。各クラスタの重心を更新しながら、各点を最も近い重心に割り当てる操作を収束まで繰り返す。これは、SSEを最小化する多値分割の近似解法として広く利用される。初期値依存性やクラスタ数選択の問題があるが、高速性から実用的に多用される。
3.2.2 階層的クラスタリング
階層的クラスタリングは、データを段階的に統合または分割することで、樹形図（デンドログラム）を生成する。凝集型（ボトムアップ）では、最も類似したクラスタを逐次結合し、分割型（トップダウン）では、全体を再帰的に分割する。この結果得られる階層構造は、任意の段階で切り出すことで多値分割を得ることができ、クラスタ数の決定が容易である。
3.3 動的計画法による分割
動的計画法は、特に一次元の順序付きデータに対して、厳密な最適多値分割を効率的に求める手法を提供する。
3.3.1 一次元データの最適分割
一次元データ列 \( x_1, x_2, \dots, x_n \) を \( k \) 個の区間に分割する問題では、各区間のコスト（例：分散の総和）を最小化する。動的計画法では、状態 \( dp[i][j] \) を「最初の \( i \) 個の要素を \( j \) 個の区間に分割したときの最小コスト」と定義し、遷移式 \( dp[i][j] = \min_{t < i} \{ dp[t][j-1] + cost(t+1, i) \} \) を計算する。前処理としてコスト計算の高速化（例：Knuth optimizationやConvex Hull Trick）が可能であり、\( O(nk) \) や \( O(n \log n) \) で求解できる場合がある。
3.3.2 多次元への拡張と制約
多次元データへの動的計画法の直接適用は、状態空間が爆発的に増大するため困難である。しかし、軸平行分割（各軸ごとに閾値を設定する分割）や直交分割（グリッド状の分割）に制限することで、動的計画法が有効になる場合がある。例えば、画像分割における領域分割や、多次元ヒストグラムの最適離散化などで応用される。また、制約として各領域のサイズや形状に関する条件を加えることで、現実的な計算量で解を得ることが可能となる。
多値分割は、機械学習、情報理論、組合せ最適化など多岐にわたる分野で実用的に用いられている。本章では代表的な応用例を概説する。
4.1 機械学習とデータマイニング
データの前処理や分類器の構築において、多値分割は中心的な役割を果たす。
4.1.1 多クラス分類器の構築
決定木、ランダムフォレスト、k近傍法など多くの分類器は、内部で多値分割を利用する。特に、決定木は各ノードでデータを複数の子ノードに分割することで、多クラス分類を階層的に実現する。また、サポートベクターマシンを多クラスに拡張する際には、one-vs-restやone-vs-oneなどの分割戦略が用いられる。
4.1.2 特徴量の離散化
連続値の特徴量を離散値に変換する離散化処理は、多値分割の典型的な応用である。等間隔分割や等頻度分割、情報利得に基づく分割（エントロピーベース離散化）などが用いられ、ナイーブベイズ分類器や決定木の性能向上に寄与する。
4.2 情報理論と符号化
情報理論においては、連続量を有限個のシンボルに写像する量子化や、秘密情報を複数のシェアに分割する秘密分散法が多値分割の枠組みで扱われる。
4.2.1 多値量子化
アナログ信号をデジタル信号に変換する際、振幅を複数のレベルに分割する量子化は多値分割の一種である。スカラー量子化では、入力範囲を \( k \) 個の区間に分割し、各区間を代表値で近似する。最適量子化器の設計は、平均二乗誤差を最小化する分割問題として定式化され、Lloyd-Maxアルゴリズムなどで求解される。
4.2.2 秘密分散法（石井・岸本スキーム等）
秘密分散法は、秘密情報を \( n \) 個のシェアに分割し、\( k \) 個以上のシェアが集まれば復元できるようにする暗号技術である。多値分割の考え方は、シェアの生成やアクセス構造の定義に利用される。石井・岸本スキームは、有限体上の多項式補間を用いた (k,n) しきい値法の一種であり、シェアの値域が有限体の要素となるため、多値分割として解釈できる。この手法は、情報理論的安全性を提供する実用的な秘密分散法として知られる。
4.3 組合せ最適化とゲーム理論
資源配分や投票メカニズムなど、複数の選択肢や参加者を扱う問題において、多値分割が応用される。
4.3.1 資源配分問題への応用
限られた資源（予算、時間、人員など）を複数のプロジェクトや部門に配分する問題では、資源をどのように分割するかが重要となる。多値分割の手法を用いて、各部門の優先度や制約条件を考慮した最適な配分比率を決定する。例えば、公平性を重視した分割（envy-free分割）や効率性を最大化する分割などが研究されている。
4.3.2 投票理論における分割
投票理論では、有権者を複数の選挙区に分割する区割り問題が存在する。各選挙区の有権者数が均等になるよう分割する（人口均衡）ことや、特定の政党に有利になるように分割する（ゲリマンダリング）ことが問題となる。多値分割の数学的枠組みは、公平な区割りの設計や、その評価指標の提供に貢献している。
多値分割は成熟した理論と応用を持つ一方で、計算複雑性や動的な環境への適応など、未解決の課題も多い。本章では現在の研究動向と今後の展望を述べる。
5.1 計算複雑性と現実的な解法
多値分割の最適化問題は多くの場合NP困難であり、厳密解を求めることは非現実的である。そのため、近似アルゴリズムやヒューリスティックの改良が進められている。特に、大規模データに対する高速な分割手法（例えば、k-meansの並列化やストリームデータへの適応）や、近似精度の理論保証を持つアルゴリズム（例えば、k-means++やCoreset-based手法）の研究が活発である。
5.2 動的・適応的分割の研究動向
静的なデータセットに対する分割だけでなく、データが逐次的に到着するストリーム環境や、時間とともに分布が変化する非定常環境での分割手法が注目されている。動的計画法のオンライン版や、逐次更新が可能なクラスタリング手法（例えば、BIRCHやストリームk-means）、概念ドリフトに対応する適応的分割などが研究されている。また、強化学習の枠組みを用いて、分割方策を学習する手法も提案されている。
5.3 深層学習との融合可能性
深層学習の進展に伴い、多値分割の概念がニューラルネットワークの内部表現と融合する研究が進んでいる。例えば、自己組織化マップ（SOM）やベクトル量子化を応用した離散表現学習、決定木とニューラルネットワークを組み合わせた「ニューラル決定木」、また、注意機構を用いたソフトな分割（ソフトクラスタリング）などが挙げられる。これらの手法は、エンドツーエンドの学習と解釈可能性の両立を目指しており、今後の発展が期待される。