質的データを扱うクラスタリングにおける最適化アプローチの研究

点击翻译按钮获取中文摘要

本研究では，「質的データを扱うクラスタリングにおける最適化アプローチの研究」と題し，クリーク分割問題を効率よく解くための定式化とアルゴリズムについて研究を行なうことを目的とした．クリーク分割問題は質的データのクラスタリングに対する有効なモデルであるが，応用場面から生じる中規模程度の入力例ですら求解が困難であり，実際，理論的にも難しいこと（NP-困難性）が知られている．本年度は，理論と実験の両面からクリーク分割問題の難しさを解析・理解し，応用場面に役立つアルゴリズムの構築を目指し，以下の成果を得た．クリーク分割問題の難しさは，その数理最適化問題としての定式化の大規模性にある．この定式化は自然かつ素直であるが，特に大量の制約式を扱うという弱点を持つ．本年度は，制約式の冗長性に着目し，それらを検出するための理論的な枠組みについて研究した．具体的には，制約式が冗長になるための十分条件を導出した．これらの結果と昨年度までに得られた結果をソルバーに組み込むことで，実用的な時間で解ける入力例の規模が大幅に拡大されることを確認した．一方，応用場面から生じる入力例の難しさを知るために，計算量の解析を行なった．ここでは，近年コミュニティ検出の分野で注目され，クリーク分割問題の特殊ケースとなる問題がNP-困難であることを証明した．また，上述のクリーク分割問題の定式化を頂点彩色問題に応用し，疎グラフに強力な定式化を得たり，冗長な制約式に関する解析をクリーク分割問題と似た構造を有する線形順序付け問題に応用したりと，得られた成果を他の組合せ問題に拡張することにも精力的に取り組んだ．