遺伝的アルゴリズムを用いた非階層的クラスタリング

情報処理学会 Web Site 被引用文献4件 参考文献12件

書誌事項

タイトル別名
  • イデンテキ アルゴリズム オ モチイタ ヒ カイソウテキ クラスタリング
  • Non - hierarchical Clustering by a Genetic Algorithm
  • 遺伝的アルゴリズム

この論文をさがす

説明

分類操作は 大きく階層的分類と非階層的分類に分けられ それぞれに多くの手法(クラスタリング手法)が提案されている. 本論文では 多値の遺伝子表現を採用した遺伝的アルゴリズムに基づく非階層的クラスタリング手法を提案する. 一般にクラスタリング手法は クラスタの評価基準および分類の具体的な手順を定めるものである. 非階層的クラスタリング手法では データを k 個のクラスタに分割する際 分割数 k は与えられるか 手法の一部として決定される. 非階層的クラスタリング手法の主たる戦略として まず仮のクラスタ分割を与え 評価基準がよりましな分割に逐次改良していく方法(分割最適化法)がある. この方法では 初期の分割あるいはクラスタの核といった初期条件が最終の分割結果に根本的な影響を及ぼし ときとして局所最適解(分割)に陥る場合も多い. 一方 遺伝的アルゴリズムは 局所最適解を回避することができる多点探索の特長を持っている. 本研究は 遺伝的アルゴリズムの多点探索能力をいかし ロバストな非階層的クラスタリングの実現をめざすものである. 提案する手法は 優性遺伝をモデルとした新たな遺伝的アルゴリズムによって構成されている. 本手法の特性を確認するため 分割最適化法の代表的な手法である k-means 法に基づく比較実験を行った. 実験では 2変量データ(点配置パターン)を用い 評価基準は平方和分解の原理に基づくクラスタ内平方和の総和を採用した. 実験結果として 在来の手法では数%しか最適な分割を得ることができない対象に対して 本稿で提案する手法によれば 80%に近い割合で最適な分割が得られることを確認した.

This paper treats a clustering procedure by using the genetic algorithm. As is well-known, existing clustering procedures are classified into two types; i.e., hierarchical and non-hierarchical types. In this paper, a non-hierarchical clustering procedure based on the genetic algorithm has been presented. We call it GA procedure. Our GA procedure can be characterized by its strong power of the multi-point search. From this, the probability to obtain the optimum solution can be made higher than existing procedures. In our experiment, the GA procedure and a typical existing procedure for the so-called k-means method have been compared in terms of probability to obtain the optimum solution and other related aspects. For three kinds of experimental point patterns, the GA procedure had shown its robustness in searching the optimum solution.

収録刊行物

被引用文献 (4)*注記

もっと見る

参考文献 (12)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ