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

2019年4月 - 2023年3月

図と地でとらえる巨大二部グラフクラスタリングとその応用

日本学術振興会  科学研究費助成事業 基盤研究(C)
  • 久保山 哲二

課題番号
19K12125
配分額
(総額)
4,420,000円
(直接経費)
3,400,000円
(間接経費)
1,020,000円

本研究では2種カテゴリ間の2項関係を分析するためのアルゴリズム開発を大規模2部クラスタリングとして捉え、既存のアルゴリズムの性質とデータへの適性を明らかにし、対象データの性質に適した規模耐性のある高速な アルゴリズムを開発することを目的としている。
初年度は、まず既存手法の調査を行った。図からのクラスタ抽出のアプローチとして、極大クリークの列挙アルゴリズムを用いた方法について、大規模実データへの実験をとおしてその性質を調査した。また、地からのクラスタ抽出のアプローチとして、最小カット問題の近似手法として2部グラフの交差最小化に基づくアルゴリズムに着目し、調査・実装を行った。
極大クリークの列挙アルゴリズムについては、実際に約800万ツイートと20万ユーザのデータに対して適用しクラスタリングを行い、得られたクラスタをトピックとして抽出した。2部グラフの交差最小化によるクラスタリングについては、局所解に陥りやすく初期値に大きな影響をうけることがわかった。さらに、行列分解による手法について、スパース動的モード解析と、非負値行列分解に着目し、実データに適用し、その性質を確認した。動的モード分解については、プラズマの時空間計測データを主要な空間パターンとその時系列発展に分解し、短時間フーリエ変換と比較して細粒度の時空間ぱたーんを抽出できることを示した。また、非負値行列分解については、大学の教室の電力消費の時系列データを、時間と教室の双方からクラスタリングし消費パターンを可視化した。
さらに、クラスタリングの基礎的な研究として、情報理論的尺度による教師なし特徴選択手法を通して、高速なクラスタリングを実現するアルゴリズムを開発した。

ID情報
  • 課題番号 : 19K12125