最適な欠損値処理

欠損値処理を最適化でする方法が提案されている．とはいっても，最適化すべき問題は非凸の難しい問題になるので，簡単な近似解法（貪欲改善法もどき）で行われている．それでも結果が良くなるという実験結果もあるので，SCOPでちゃんと最適化してみたらどうかと考えてみた．

K-近傍法でカテゴリーデータだけの場合だと，データi,j間の距離 d[i,j] はデータのd番目の特徴が異なるものの数として定義される．これは，データiの特徴dをとした変数を準備して，その値変数をクラスとすれば，非凸の2次式で書ける．

さらに欠損値のあるデータiに対して，どのデータが近傍になるかを表す0-1変数z[i,j]を準備して，z[i,j] とd[i,j] の積の和を最小化すれば良い．もちろん，z[i,j]の合計はKとする．

最適な決定木もカテゴリカルデータの分類問題なら，簡単にSCOPで最適化できるので，最適決定木の欠損値処理も最適化できる．