階層的クラスタリングにおける最適解と局所最適解に関する一考察

スポンサーリンク

概要

• 論文の詳細を見る

• コンピュータビジョン、パタン認識の手法の中でクラスタ解析は最も応用範囲の広い手法のひとつであり、カラー画像のセグメンテーション、知覚における群化、Hough変換などに応用されている。しかし最適クラスタリングを求める問題はNP-hardとなりうる。このため、我々は準最適な手法を検討せねばならない。本稿では、ある種の階層的クラスタリング問題における2種類の準最適な手法によって得られた解と最適解との違いを調べる実験を行なったので報告する。まず、少数の点の集合に対して、しらみつぶしにより全てのクラスタリングを求め、真の最適解を求めた。次に、準最適化手法により局所的最適解を求め、これと真の最適解を比較した。この結果、通常、局所的最適解は目的関数の値においては真の最適解に極めて近いが、求められるクラスタ木のトポロジカルな構造は極めて異なる場合が多いことがわかった。

• 1990-09-04

著者

• 末永 康仁

  Ntt Human Interface Laboratories Nippon Telegraph And Telephone Corporation

• ワレス リチャード.S

  NTT Human Interface Laboratories Nippon Telegraph and Telephone Corporation

関連論文

• Representation of Rotational Sweeps using Quadratic Surfaces and Toruses
• 階層的クラスタリングにおける最適解と局所最適解に関する一考察

スポンサーリンク