共同研究・競争的資金等の研究課題

2012年 - 2015年

高次元特徴空間の埋め込みと次元縮小に基づく知識発見基盤の構築

文部科学省  科学研究費補助金(基盤研究(B))
  • 平田 耕一
  • ,
  • 久保山 哲二
  • ,
  • 篠原 武

課題番号
24300060
担当区分
連携研究者
配分額
(総額)
11,440,000円
(直接経費)
8,800,000円
(間接経費)
2,640,000円
資金種別
競争的資金

平成24年度は,(1)離散構造データの埋め込み,(2)本質的な高次元データの次元縮小,(3)離散構造データの高次元ベクトル表現,および,埋め込みと次元縮小という3つの研究目的について,研究目的(1)に対する「(A)離散構造間距離とアルゴリズム」,研究目的(2)に対する「(B)SimpleMap法の歪みの解析と拡張」の研究を進めた.「(A)離散構造間距離のアルゴリズム」では,離散構造間距離の一つである木編集距離に対して,その変種である木の断片距離を新たに定式化し,順序木における二乗時間アルゴリズムを開発した.この断片距離は,既存の木編集距離の変種に対して新たな階層を与えている.また,無順序木の次数2木包含問題を孤立部分木包含問題にまで拡張し,その問題を解く多項式時間アルゴリズムを開発した.離散構造間距離の応用として,塩基配列の位置の関係を比較する手法として進化系統樹に基づいた位置間の剪定距離を新たに導入した.また,バズマーケティングサイトから木編集距離を用いてコミュニティを抽出する手法を開発した.さらに木以外の離散構造としては,超グラフのベルジュ非巡回部分超グラフに対する効率よい列挙問題に取り組んでいる.「(B)SimpleMap法の歪みの解析と拡張」に対しては,主に動画像検索のためのSimpleMap法の拡張に取り組んだ.特に,ヒルベルトR木を用いた検索高速化手法,階層的空間索引構造R-treeを用いたSketch検索の高速化,階層的空間索引を用いた検索高速化のための局所次元縮小射影などを開発した.

リンク情報
URL
https://kaken.nii.ac.jp/d/p/24300060.ja.html