close
1.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 構造化ウェブデータからの並列分散データマイニングシステム — Distributed Data Mining Systems for Structured Web Data
正代 隆義 ; SHOUDAI Takayoshi
研究期間: 2002-2004
本文を見る:
概要: 本研究課題の目的は,HTMLやXMLファイルなどのウェブデータから知識発見を行う分散型計算環境に適したデータマイニングシステムの実現と,そのシステムの理論的基礎となる木構造パターンの機械学習理論の構築である. 近年,高速なネットワークと大容量記憶装置の発達を背景として,ウェブページに代表されるテキストデータの利用が急速に進みつつある.とくに,HTMLやXMLデータはテキストデータでありながら,タグを入れ子とする構造を持つので半構造データ,あるいは木構造データとよばれる.本研究課題では,木構造データからのデータマイニングの基礎理論を構築するため,木構造データを非順序木とみなす場合と,順序木とみなす場合の両方について,帰納学習あるいは例からの概念学習とよばれる基礎的研究を行った.また,提案した学習アルゴリズムを用いたデータマイニングシステムを開発した. 木構造データから意味がある知識を抽出するためには,それらに頻出する木構造パターンを発見することが必要である.そこで,まず柔軟性に富む木構造パターンとして項木を定義した.項木は,いくつかの構造的変数と辺ラベルを持つ木構造からなるパターンであり,変数にはあらかじめ定められた条件を満たす非順序木または順序木を代入することができる.我々は,変数の代入条件,項木の表現能力,およびデータ提示および質問に関する様々な設定のもとで,項木言語の多項式時間機械学習アルゴリズムを与えた.また,理論の有効性を確認するため,提案した学習アルゴリズムをエンジンとするメタサーチシステムを開発した.このメタサーチシステムは,タグやキーワードの意味を全く考えず,木の構造だけから自動でラッパーを生成する機能を持つ.このメタサーチシステムにより複数の検索サイトの統合が実現できることを確認した.以上が,本研究課題で得た研究成果の概略である. 続きを見る
2.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of クラス指向グラフパターン設計手法の開発とグラフマイニングへの応用
正代 隆義
研究期間: 2011-2013
本文を見る:
概要: 本研究課題の目的は、グラフ理論的なグラフクラスには現れない新しいグラフクラスの設計手法の確立と、そのグラフクラスをベースとするグラフマイニングシステムの開発を行うことである。平成23年度は、グラフ構造データベースに含まれるグラフ構造がどのように生成されたかについてグラフ上の演算・操作に着目し、グラフパターンの機械学習アルゴリズムの設計と解析を行った。 第一の結果として、cographと呼ばれるグラフクラスに対する多項式時間機械学習アルゴリズムの提案があげられる。Cographは1個の頂点から和演算と補演算を繰り返して生成できるグラフである。Cographのクラスは、ある種のスケジューリング問題や索引のクラスタリングなどで用いられている。本研究では、cographをベースとする新しいグラフパターンを設計し、その多項式時間機械学習アルゴリズムを提案した。また、本結果とともに一般のグラフをcographにする手法を用いることで、実データに対する効率の良いグラフマイニング手法の開発が期待できる。 第二の結果として、辺で結ばれた2頂点を1つの頂点に融合する操作「辺縮約」に基づくグラフ構造の新しいパターン表現の提案がある。本研究では、そのグラフ構造パターンの照合アルゴリズムを提案し、グラフ構造パターンの木幅が定数と見なせる場合、多項式時間で動作することを示した。ほとんどの化学化合物グラフは木幅が定数とみなせることから、本アルゴリズムを用いたグラフマイニングシステムを開発することで、化学化合物における新しい知識発見が期待される。 その他の結果として、ストリームデータに頻出する時系列を列挙する近似ストリームアルゴリズムの提案がある。提案したアルゴリズムは、時間変化するグラフデータの特徴をグラフパターンとして捉えるための基礎と成り得る。 以上が、本年度に得た研究実績の概要である。 続きを見る
3.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of データ圧縮と高速文字列照合アルゴリズムを用いた知的全文検索システムの開発 — Development of Intelligent full text retrieval system based on data compression and fast string pattern matching algorithms
篠原 歩 ; SHINOHARA Ayumi
研究期間: 2001-2003
本文を見る:
概要: 文字列に対する索引構造として,接尾辞木(suffix tree)や有向無閉路文字列グラフ(DAWG)がよく知られているが,我々はその両方の性質を持つ,よりコンパクトなデータ構造であるコンパクト有向無閉路文字列(CDAWG)に着目し,そのためのオンライン構築アルゴリズムを示した.また,文字列のすべての接頭辞に対するDAWGを合わせた構造に対する構築アルゴリズムを示し,与えられた文字列のすべての部分列を受理するオートマトン(部分列オートマトン)の状態数の下限の証明も行った.これらの結果はいずれも,アプリケーションの高速化の基盤技術として用いられている.また,日本語テキストなど,アルファベットサイズが大きい場合に有効なDAWGの実装技術として,三分木構造を活用したデータ構造を提唱し,その有効性を実証した. 一方,これら文字列に対するデータ構造の性質をより探求するために,グラフ構造からそれに適合する文字列を推論するという逆問題を新たに提案し,DAWG,部分列オートマトン,そして接尾辞配列に対する線形時間アルゴリズムの開発した.さらに,文字列の代数的な性質として,1変数の文字列方程式の解の長さの上限を初めて明示的に証明することに成功した. データ圧縮に関しては,まず我々はテキストに対応したコンパクトな文脈自由文法を出力する枠組みにおいて,出力される文法のサイズの近似率を保証した,領域効率もよいアルゴリズムの開発とその解析に成功した.また,長さ優先で置換を行っていくヒューリスティクスに関しても,全行程を線形時間で行うことを可能にするアルゴリズムを与えた. また、大量のデータから現実的な時間内に有用な規則を抽出しようとするパターン発見アルゴリズムに関しても,より一般化したさまざまなパターンについてそれぞれ独自の高速ナルゴリズムを開発することに成功した.特に,誤りを許した近似パターンについても,効率のよいアルゴリズムを与え,その効果を計算機実験によって検証した. 続きを見る
4.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 超高次元データに基づく非線形多変量解析手法の開発と応用 — Nonlinear multivariate analysis based on high-dimensional data and its application
小西 貞則 ; KONISHI Sadanori
研究期間: 2005-2008
本文を見る:
概要: 高次元データに基づく複雑現象解明を目的として, 非線形多変量解析の理論・方法論の開発研究と応用研究に取り組み, 現象の構造を有効に捉える非線形回帰モデリング, ロジスティックモデルに基づく非線形識別・判別法, リスクを定量的に評価・予測するリスク予測モデルを提唱した. また, 観測・測定されたデータを関数化処理し, 処理した関数化データ集合に基づく解析手法について研究し, 回帰, 識別・判別, 次元圧縮に関して, 関数データ解析手法を提唱することができた. 開発した解析手法は, 生命科学, システム工学, 地球環境科学などの問題解決に応用した. 続きを見る
5.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of リンク情報とWebデータの半構造性を融合した高品質コンテンツ・マイニング
廣川 佐千男
研究期間: 2003
本文を見る:
概要: 多量な同系統文書群は高品質であるというヒューリスティックに基づき,Web上の高品質文書群を効率良く発見するための研究を行なっている.本年度は,リンク構造と構造類似性で特徴付けられる「シリーズ型文書群」という概念を提案し,そのような文書群を効率的に発見収集するWebロボットの実装を行ない,その収集効率を定量的に評価した.また,シリーズ型文書群に対するメタデータを自動的に構成する手法を開発した.これとは別に,同系統文書群の発見について,部分文字列の出現頻度に着目した「部分文字列増幅法」を開発した.このアルゴリズムは,入力サイズの線形時間で動作し,類似構造を持つ文書群を網羅的に検出すると同時にクラスタリングも行なうものである. 本年度は,Web上半構造化データからの高品質同系統データ抽出について,HTMLファイルに繰り返し現われる特徴的なタグ・パターンの抽出法の開発と,コンテンツ収集を動的に制御できる目的指向Webロボット開発に重点を置き研究を進めた.前者については,部分文字列の出現頻度だけで重要パターンを高精度で抽出する部分文字列増幅法という新しい手法が開発できた.後者については,従来ターゲットとしてきた大学のシラバスについては1万件以上の収集が達成できた.さらにシラバス以外の一般的な「シリーズ型Web文書群」についてのWebロボット開発の目処がたち,その文書群に対するメタデータの自動生成手法を構築できた. 続きを見る
6.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of データ圧縮とパターン照合に基づく高速機械発見システムの開発 — Development of efficient machine discovery system based on data compression and pattern matching
竹田 正幸 ; TAKEDA Masayuki
研究期間: 2003-2005
本文を見る:
概要: 本研究では,高速な機械発見システム開発のために以下の3つの項目について研究し,多くの成果を得た。 ・テキスト圧縮とパターン照合 文法変換に基づく圧縮法に焦点をあて,効率的な圧縮アルゴリズムを開発した。これらを基盤技術として用いながら,圧縮文字列照合問題に取り組み,効率的な圧縮文字列照合アルゴリズムの開発に成功した。 ・テキストと半構造データの高速処理 テキストデータの高速処理のために,索引構造の開発を行った。部分文字列パターンに対する索引構造として接尾辞木とDAWGが知られている。そこで,両方の性質を持つCDAWGに着目し,オンライン線形時間CDAWG構築アルゴリズムを開発した。これに基づき,スライド窓に対応したCDAWG構築アルゴリズムを考案し,テキストデータ圧縮に活用した。また,日本語テキストなどアルファベットサイズの大きなテキストデータに適した新たな索引構造を与え,その有用性を示した。一方,部分列パターンの照合のための索引構造である部分列オートマトンについて解析し,部分列パターン発見の高速化に関する知見を得た。さらに,十数年ものあいだ未解決であった語接尾辞木のオンライン線形時間構築アルゴリズムを考案した。 半構造データの高速処理のために,ビット並列化技法に基づく高速木パターン照合アルゴリズムを開発した。 ・パターン発見と情報抽出 大量のデータから現実的な時間内に有用な規則を抽出するパターン発見アルゴリズムに関して,様々なパターン族についてそれぞれ独自の高速アルゴリズムを開発した。また,形式的体系(EFS)の質問学習や半構造データからの知識発見に関する研究も行った。これらのアルゴリズムを実働化しそのパフォーマンスを評価した。 以上の研究で得られた成果を統合し,計算機上に高速な知識発見システムを構築した。言語データおよび文学作品データに適用し,言語学および文学の専門家の立場から有効性を検証した。 続きを見る
7.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 半構造テキストデータの一般構造を推論する高度情報抽出アルゴリズムの構築
坂本 比呂志
研究期間: 2003-2004
本文を見る:
概要: XMLを中心とする半構造データの登場により,情報抽出は次の新しい局面を迎えている.本研究の目的は,半構造データからの情報抽出問題を木構造へ一般化し,複雑な抽出を効率的に行うための枠組みを提案することである.これまでの枠組みでは半構造データからデータの場所を推論してテキストのみを取り出していた.これに対して本研究では『構造化テキスト』すなわち半構造データの部分木に相当する部分を学習によって抽出する.学習アルゴリズムの目標は与えられたデータから一般構造を取り出してラッパー(抽出規則)を構築することであり,抽出アルゴリズムはラッパーと未知のデータをマッチングさせて適切なデータを取り出す.これらのアルゴリズムを実現するために研究計画として以下の3つの課題を設けているが,最終年度はそのうち3.について成果をあげた. 1.多様な論理構造を持つデータを表現できる木構造ラッパーを定式化する.一般の文字列は変数や関数記号を導入することでより一般的な表現になる.この考えを応用して正規表現の概念を木構造へ導入する. 2.半構造データを一般化する手続きを確立し,木構造ラッパーを学習するアルゴリズムを構築する.この枠組みでは複数の木構造を同時に一般化するため,ダイナミックプログラミングを応用してメモリーを圧迫しない学習アルゴリズムの実現を目指す. 3.高速な抽出アルゴリズムを実装し,実験によって有効性を示す.素朴な手法によって抽出アルゴリズムを実装する場合,未知のデータを一度構文解析する必要があり,このままでは高速化は難しい.そこで従来の文字列照合問題を木構造データのマッチングへ拡張し,構文解析を必要としない手法を確立する. 本研究における一般化によって,データの構造を学習し複雑な抽出を行うことができる. 続きを見る
8.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 高次非線形モデリングの統合的研究
小西 貞則
研究期間: 2009-2013
本文を見る:
概要: 電子化された計測・測定技術の高度な発展は,諸科学,産業界で大規模かつ高次元の多様なデータの獲得と蓄積を可能とし,データの中から有益な情報やパターンを効率的に抽出するための新たなデータ解析手法の開発研究が求められるようになってきた.本研究は,昨年度までの研究実績を踏まえてこれをさらに発展させて,本年度は以下のような研究成果を挙げた. 1.複雑な非線形構造を内包する現象のモデル化を目的として,ベイズアプローチに基づく非線形手法の一つである関連ベクターマシンについて研究し,予測に有効に機能する新たな非線形回帰モデリングを提唱した.また,確率分布モデルのベイズ推定である予測分布モデルを評価するためのモデル評価基準を導出した.現在,開発したモデリング手法を地球環境データ,生命科学におけるゲノムデータの解析に応用し,その有効性を検証中である. 2.自己回帰成分を持つ時系列的回帰モデルに対して,自己回帰の次数,説明変数や時間遅れ次数を選択する問題について研究し,重み付き最小2乗法による母数推定に関するGIC基準を求め,車両運転装置に応用する解析手法を開発した. 3.森林被覆率を人口密度と起伏量で説明する空間依存性をもつ柔軟な非線形回帰モデルを考察した.これは従来のパラメトリックな平均構造で記述されるモデルを大きく改良することがわかった. 4.分布関数及び密度関数のカーネル型推定量の高次漸近分布について研究し,正規近似の精密化であるエッジワース展開を導出することができた.またジャックナイフ及びブートストラップ分散推定量の平均2乗誤差について理論的な評価を求めることができた. 続きを見る
9.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 情報量概念を基盤とした学習理論の展開 — Development of Learning Theory based on Information Measure
竹内 純一 ; TAKEUCHI Junichi
研究期間: 2007-2010
本文を見る:
概要: 機械学習,情報理論,およびそれらの応用に関する諸課題について,記述長最小原理に基づく統一的視点のもとに研究を行った.特に,Markovモデルの幾何学的構造と確率的複雑度の関係,通信路容量と確率的複雑度の関係について考察し新たな知見を得た.また,アンサンブル学習等に関して考察し,効率的アルゴリズムや推定法を提案した.さらに,これら基礎的知見に基づき,ネットワークセキュリティにおけるインシデント検知,ポートフォリオ(分散投資戦略),超解像などについて,新たな学習手法を提案し,その有効性を示した. 続きを見る
10.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 生体情報の統計的解析による認証に有用な情報の発見
馬場 謙介
研究期間: 2010-2012
本文を見る:
概要: 本研究の目的は,安全で利便性の高い生体認証システムを開発するために,生体情報の中に潜む認証のために利用可能な情報を統計的な解析により発見することである.研究期間を通して,以下を目標に研究を進めている. 1.生体情報中に,それが確かに生体から採取されたことを保証する情報を発見する 2.データ処理の効率化による認証精度向上の可能性を明らかにする 3.生体情報中に,時間の経過を示す情報を発見する 平成23年度は前年度に引き続き,上の項目のうち2ついて,生体情報の種類として指紋画像を対象に識別の高速化と高精度化を行った.指紋の特異点を利用した画像の分割による指紋画像の分類手法を提案し,処理時間と精度の間の効率的なトレードオフを得た.まず,画像分割のために有効な特異点抽出の手法を明らかにし,次に,提案手法による時間と精度の変化を実験により評価した.この成果は,それぞれ,国際会議および論文誌にて発表した.今後は,この成果を他の生体画像へと応用する予定であり,既に掌紋画像への応用で成果を得ている(未公開,国際会議論文として採択済).また,これらの研究の過程で,生体画像による個人認証に関する一般的な知識と実装のノウハウを得た.これについて,生体画像による個人認証の新しいフレームワークの提案にとして,国際会議にて発表を行った.これらめ知見やサンプルを利用して,上の項目の1や3を実現する情報を取得するための生体情報の採取方法を模索する予定である. 続きを見る