F-016
中心性指標の分布に基づく局所改善クラスタリングの性能評価

◎山岸祐己・斉藤和巳（静岡県大）

オブジェクト集合のクラスタリングでは，一般に，K-平均法よりも K-メディアン問題の方が外れ値などにロバストであり，多様な状況下でも適用可能であることが知られている．この問題は，貪欲法で求まる近似解により，ある程度妥当な精度で最悪ケースの解品質が理論的に保証されているが，貪欲法のみでは比較的プアーな局所解にトラップされる恐れがある．これに対し，局所改善法による解決が考えられるが，計算量が大幅に増大する傾向があるため，大規模な問題になるほど，局所改善法を適用する前にその有効性を推定することが重要となる．よって，我々は各オブジェクトの中心性指標を導入し，その分布の歪度を用いることによって，局所改善法の有効性を推定することを試みる．