<博士論文>
クラスタリングに基づく情報の検索と視覚化

作成者
指導教員等
本文言語
学位授与年度
学位授与大学
学位
学位種別
出版タイプ
アクセス権
JaLC DOI
概要 データ検索,情報フィルタリングやデータマイニングなど大量の構造的データの探索においてクラスタリングは重要なデータ構造要約法の一つであり,これまでに多くの手法が提案されている。データ構造は,ハイパーテキストなど陽に有向グラフとして表されるものから,文献とキーワードのデータ行列など,グラフとは明示的な関係がない多変量データに至るまで一般に無向あるいは有向グラフとして表すと扱い易くなる。そこでグラフ構造...データのクラスタリング法が上記のデータ探索において有用になると思われる。しかし,クラスタリングにグラフ理論的手法を用いるというアプローチは研究されているが,グラフそのものをクラスタリングの対象とした研究は少ないようである。ましてファジークラスタリングに関してはファジーc 平均法などのようにデータの特徴量に基づく手法がほとんどであり,グラフを対象とした研究はほとんどされていない。
そこで本論文では,グラフの節点集合をファジークラスタ(ファジー部分グラフ)に分割するクラスタリング法を提案し,データの検索と視覚化に応用する。また,クラスタリングを利用して画像検索を高速化する方法も提案する。
第1 章では,本研究の目的と背景を示し,あわせて論文の概要について述べる。
第2 章では,類似度行列からファジークラスタを逐次に抽出する方法を提案する。はじめに,類似度行列からファジークラスタを抽出する問題が固有値問題に帰着されることを示す。次に,各データの残存率を類似度行列の要素に掛けて抽出済みのクラスタを取り除くことにより,逐次にクラスタを抽出していく方法を示す。抽出処理はクラスタの凝集度の変化に基づき,ある程度の大きさのクラスタが抽出されたら終了する。提案手法の有効性を,簡単な2 次元データに対する実験とグレイスケール画像のセグメンテーション,およびビデオのセグメンテーションの実験例で示す。
第3 章では,グラフの隣接行列に基づいて節点集合をファジークラスタに分割する方法を提案する。はじめに,節点と辺に重みを持つ無向グラフに第2 章で提案したファジークラスタ逐次抽出法を適用し,続いてそれを有向グラフや2 部無向グラフに拡張してグラフ構造データからファジークラスタを逐次に抽出する方法を提案する。簡単なデータによる実験により本手法の有効性を示す。
第4 章では,第3 章のファジークラスタ逐次抽出法を,複数のグラフが混成された複雑なグラフに適用できるように拡張する。複雑なグラフ構造データからファジークラスタを抽出する問題は固有値問題に帰着できないため,べき乗法を一般化した反復法による抽出法を導く。はじめに,無向グラフと2 部無向グラフ,および有向グラフから反復法に基づいてファジークラスタを逐次に抽出する方法を示す。次に,有向グラフと2 部無向グラフが組合わさったグラフからファジークラスタを抽出する方法を示す。また,これらの反復法の収束性を証明する。最後に,簡単な実験例を示し,提案手法の有効性を検証する。
第5 章では,クラスタリングに基づいて数量化理論によってデータ構造を視覚化する方法を提案する。まず,数量化3 類と数量化4 類についてデータ行列に基づく視覚化に関する比較実験を行い,両者の長所と短所を明らかにする。次に,数量化4 類を重み付きデータに拡張し,クラスタリングの結果を重み付き数量化4 類により逐次展開して表示する方法を提案し実験例を示す。
第6 章では,ファジークラスタリングに基づくハンティング検索法とブラウジング検索法を提案する。はじめに,ハンティング検索について簡単な例題を用いて潜在意味解析法と比較を行いながら説明する。次に,グラフ構造データの表示法として,第5 章の数量化3類による視覚化法をグラフデータに応用し,メンバシップ値を第3 軸とする3 次元表示によって各データ点の主要度も把握できるように拡張した表示法を提案する。いくつかの具体的な例題により提案手法の有効性を示す。
第7 章では,画像の類似検索を高速化する手法として,次元削減とクラスタリングに基づくフィルタリングによる高速化法を提案する。クラスタリング法としてk 平均法を用いる。はじめに,2 次形式距離の不等式に基づくフィルタリングによって近隣検索を高速化する方法を概説する。このフィルタリングをk 平均法に適用することにより,クラスタリングの計算時間が短縮されることを実験で示す。続いてクラスタリングと三角不等式を利用するフィルタリング法を示し,特徴ベクトルの次元削減とクラスタリングとを組合せたフィルタリングを用いて画像の類似検索の計算量を削減する方法を提案する。実験により類似検索がフィルタリングによって高速化されることを示す。
第8 章では,特徴ベクトルの次元圧縮とクラスタリングを組合せて近似類似検索を行うことにより画像検索を高速化する方法を提案する。提案手法では,画像間の非類似度をカラーヒストグラム間の2 次形式距離で測り,主成分分析によってヒストグラムを次元圧縮する。この低次元でデータベース画像を予めクラスタリングしておき,クエリが入力されたらクエリに近いクラスタを何個か選び,選ばれたクラスタに含まれる画像全体のなかからクエリに近いものを複数個選んで出力する。この方法により,第7 章のフィルタリング法よりも更に高速に画像検索が行えることを実験で示す。
最後に第9 章では,本研究のまとめと今後の課題を示す。
続きを見る
目次 目次
第1章 序論
第2章 類似度行列に基づくファジークラスタリング
第3章 重み付きグラフからのファジークラスタ抽出
第4章 混成グラフからのファジークラスタ抽出
第5章 数量化理論によるデータの視覚化
第6章 グラフ構造データの検索と視覚化
第7章 次元削減とクラスタリングに基づくフィルタリングによる画像検索の高速化
第8章 次元削減とクラスタリングに基づく画像の近似kNN検索
第9章 結論
謝辞
付録A LSI法
付録B 2次形式距離
付録C 多次元尺度構成法
付録D 自己組織化マップ
付録E スプリングモデル
参考文献
続きを見る

本文情報を非表示

k060-001 pdf 19.1 KB 67 表紙
k060-002 pdf 274 KB 63 目次
k060-003 pdf 881 KB 63 第1章
k060-004 pdf 5.23 MB 186 第2章
k060-005 pdf 1.1 MB 136 第3章
k060-006 pdf 1.03 MB 69 第4章
k060-007 pdf 14.6 MB 98 第5章
k060-008 pdf 14.6 MB 95 第6章
k060-009 pdf 1.07 MB 71 第7章
k060-010 pdf 903 KB 76 第8章
k060-011 pdf 352 KB 91 第9章
k060-012 pdf 50.5 KB 73 謝辞
k060-013 pdf 320 KB 45 付録A
k060-014 pdf 9.99 MB 82 付録B
k060-015 pdf 4.83 MB 56 付録C
k060-016 pdf 5.69 MB 56 付録D
k060-017 pdf 4.52 MB 68 付録E
k060-018 pdf 415 KB 77 参考文献

詳細

レコードID
査読有無
学位記番号
授与日(学位/助成/特許)
受理日
部局
所蔵場所
所在記号
登録日 2014.01.24
更新日 2020.10.06

この資料を見た人はこんな資料も見ています