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 プログラミング教育のためのWEB上の動作表示システム — Dynamic Visualization of Pascal Programs on WEB
安達 昌弘; Adachi Masahiro; Satou Hiroyuki ... [ほか]
出版情報: 全国大会講演論文集. 55, (4), pp. 490-491, 1997-09-24. 一般社団法人情報処理学会
本文を見る:
概要: 我々は、毎年2,300人の学生を対象とする一般情報処理教育をホームページを用いて行っている. しかし、プログラムの動作は文章や図だけでは初心者には分かりにくい。そこで、パスカルプログラムをWWWブラウザで見せるためのシステムを開発している. これは、パスカルプログラムをJavaアプレットヘ変換する。本稿ではシステム開発の背景と実現方式の概略を述べる。 続きを見る
4.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of グラフパターン言語の計算論的学習理論とグラフマイニングへの応用 — Machine learning theory for graph pattern languages and its applications to graph mining
正代 隆義 ; SHOUDAI Takayoshi
研究期間: 2008-2010
本文を見る:
概要: 化学化合物データやネットワークトラフィックデータといったようなグラフ構造を持つデータを対象として、そのデータに潜むグラフ構造パターンを抽出するための手法を開発した。特に、対象となるグラフ構造データのグラフ理論的な木構造的性質、例えば外平面性や木幅に着目し、一連の表現力豊かなグラフ構造パターンを設計した。我々の提案したアルゴリズムは実データに対して高速に動作し、いくつかの興味深いグラフ構造パターンを発見することに成功した。 続きを見る
5.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of グラフ言語の多項式時間学習アルゴリズムとその応用 — Polynomial Time Algorithms for Learning Graph Structured Pattern Languages and its Applications
正代 隆義 ; SHOUDAI Takayoshi
研究期間: 2005-2007
本文を見る:
概要: 本課題では、グラフ言語の多項式時間学習アルゴリズムとその応用に関する研究を行い、我々は、実世界のグラフ構造データを表現可能ないくつかのグラフパターンを提案し、それらに対する学習アルゴリズムの設計と知識発見システムの開発を行った。主な結果は次のとおりである。 1.ウェブデータを木構造データとみなしたとき、その木の高さはほとんどの場合小さい。そこで、高さ制約代入を用いた木構造パターンの多項式時間照合・発見アルゴリズムを提案し、学習モデルとして正データからの多項式時間帰納推論および質問学習を用いて、現実的に意味のある代入制約の下で提案した木構造パターンのクラスが多項式時間学習可能であることを証明した。 2.区間グラフとは、各頂点が数直線上の互いに異なる区間に対応し、2つの区間が重なっているとき、対応する2つの頂点は辺で結ばれる、というような性質を持つグラフである。我々は、区間グラフに共通するパターンを表現する方法として、単体頂点を変数として持つ区間グラフパターンを定義し、この区間グラフパターン言語のクラスが正データから多項式時間帰納推論可能であることを示した。 3.化学化合物のほとんどが、グラフ理論的には外平面的グラフである。そこで、化学化合物データベースからのデータマイニングを行うために、ブロック保存型外平面的グラフパターン(BPOグラフパターン)を定義し、BPOグラフパターンの多項式時間照合アルゴリズムと頻出グラフパターン発見アルゴリズムを提案した。さらに、そのアルゴリズムを用いてデータマイニングシステムを作成し、計算機実験によってその有効性を確認した。 以上が、本研究課題で得た研究成果の概略である。 続きを見る
6.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 離散構造の法則を発見する並列機械学習システムの開発
正代 隆義
研究期間: 1999-2000
本文を見る:
概要: 本課題では,離散構造の法則を発見する並列機械学習システムの開発に関する研究を行ない,平成12年度は次の2つの結果を得た. 1.木構造は多くの分野でデータを表現するために使われており,木構造を持つHTML/XMLファイルに代表される半構造データからの知識発見が注目を集めている.項木とは,木構造をしたデータのパターンを表現するための,変数を含むデータ構造であり,項グラフよりも表現力が小さいが,一階項よりも表現力が大きい.仮説としての項木が表すパターンと木の適合可能性を判定することは,仮説のチェックをする際に解くべき基本的な問題であり,その計算量を調べる必要がある.よって,入力である項木と木の構造的複雑さに注目してこの問題の計算量を考察し,この問題がどのような場合に効率よく解けるかどうかを調べて,そのアルゴリズムを提案した. 2.一般に,グラフは事象(頂点)とその関係を表すだけで,事象間の距離は考慮されない.しかし,地図や化学分子など,事象の位置が重要な画像データなどをグラフで表すとき,そのグラフを距離空間上で定義する必要がある.本研究課題では,距離空間上のグラフから効率良く知識を獲得するシステムを設計した.まず,この知識獲得システムの出力である仮説(知識)を表現するために,Layout Formal Graph System(LFGS)を定義した.これは,グラフを項として持つ論理プログラムであるFormal Graph System(FGS)に位置情報を加味した規則である.さらに,LFGSで用いるレイアウト項グラフでの多項式時間同型判定アルゴリズムを与えた.最後に,Brandenburgによって定義されたレイアウトグラフ文法とLFGSとの比較を行い,LFGSがレイアウトグラフ文法より表現力が大きいことを示した. これら2つの理論的結果に基づいて,HTML/XMLといったような半構造を持ったデータを対象とした機械学習システムのプロトタイプを作成し,その有効性を確認した. 続きを見る
7.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 探索アルゴリズムの並列化とその計算量の研究
正代 隆義
研究期間: 1995
本文を見る:
概要: 本課題では,探索アルゴリズムの並列化とその計算量について研究を行ない,次の成果を得た. タンパク質や核酸のデータといったゲノムデータを対象とした探索アルゴリズムの開発は宮野(九州大学)等によってその端緒はつけられており,大量ゲノムデータからの知識獲得システムBONSAIとして大きな成功を納めた.しかし,一方では,多種多様なデータを前にして,逐次的手法による探索方式の限界も指摘されている.また,探索の問題は,純粋に理論面からは,C.H.PapadimitriouやM.Yannakakisらによって局所探索の理論が存在するが,様々な探索方式・問題を捉えるためには不十分である. 本研究では,知識獲得システムの核となる探索アルゴリズムの並列化による効率化を行ない,多様なデータに対応できる並列知識獲得システムBONSAI Gardenの開発を行なった.知識獲得システムBONSAIは正負2つの例から,その例を説明する仮説をアルファベットインデキシングをラベルとする決定木として出力する.このシステムは単一のデータからなる膜貫通領域やシグナルペプチドといったようなタンパク質の説明に成果をあげた.しかしながら,2つ以上のデータが混在した例では,単一のBONSAIシステムで,意味のある小さな仮説を出力するには限界があった.この問題を解決するために,複数のBONSAIを並列に動かすアルゴリズムを設計し,知識探索の並列化を行なった.BONSAI Gardenと呼ばれるこのシステムでは,特殊なプロセスGardenerにより管理された複数のBONSAIプロセスが並列に動作し,効率のよい解空間の探索を行なう。このシステムによって、当初の目的の複数の小さな仮説を出すことに成功した.さらに,DNAおよびタンパク質の塩基配列を入力とする実験を行ない,核となる並列探索アルゴリズムの実験的有効性を確かめた. 続きを見る
8.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 離散構造を学習する並列知識発見しステムの開発
正代 隆義
研究期間: 1997-1998
本文を見る:
概要: 本課題では,離散構造を学習する並列知識発見システムの開発の研究を行ない,平成10年度は次の2つの結果を得た. 1. 大規模なデータベースから知識発見を行うときには,データベースの探索手法の開発とともに,データの見方であるビューの確立が必要である.本課題では,最初に,ビューの数学的定式化を行なった.それに基づいて,多種多様な構造を持つデタに対応できる複数の異なるビューを持った知識発見システムのプロトタイプを作成し,分子生物学的データベースを対象として並列計算機上で実験を行なった.従来のデータマイニングの枠組みでは,より複雑な構造を持つ自然科学のデータベースからうまく知識を得ることが難しい.そこで,我々は,ユーザがビューを自由に設計でき,また必要ならばユーザがプラグインとして新たなビューを追加できる新しい知識発見システムの開発を行った, 2. 本年度は,機能や構造が未知であるデータに対する知識発見方式の定式化に基づいて,項木言語の学習可能性について,昨年度に証明した結果の拡張を行った.これにより,タンパク質やRNAといったような離散構造を持つデータから自明でない特徴を見出すためのビューの確立を目指した.項木とは,変数を持つ辺にラベルを付した木である.これは,文字列パターンと同様に,その変数に任意の木を代入することで,ある複数の部分木を持つすべてのラベル付き木を表現することができる.キャタピラは,タンパク質やRNAのトポロジカルな構造を直感的に表現した木の部分クラスである.本年度は,キャタピラをベースとする項木をビューとして確立するために,昨年度の結果より広いクラスについて,キャタピラの項木言語の機械学習可能性を証明した,また,このビューを用いた知識発見システムを構築するにあたって,そのコアとなる多項式時間探索アルゴリズムのいっそうの効率化を行った. 続きを見る
9.
助成・補助金
Kyushu Univ. Production 九州大学成果文献
Cover image of 科学的知識獲得のための並列探索アルゴリズムの研究
正代 隆義
研究期間: 1996
本文を見る:
概要: 本課題では,科学的知識獲得のための並列探索アルゴリズムの研究を行ない,次の成果を得た. 近年,盛んに研究がなされている帰納学習あるいは例からの概念学習とよばれる学習方式を,知識獲得システムとして構築するには探索方式の確立が不可避である.特に,「並列」を知識獲得の観点から論ずる場合, 1.知識獲得システムのコアとなる検索アルゴリズムの並列化による高速化, 2.各種多様なデータに対応できる複数の異なるビューを持ったシステムの構築, を明らかにする必要がある.本研究では,多種多様なデータからinterestingな知識を発見するため,新しいデータマイニングの開発とグラフを表現とした知識発見の2つの研究を行った. データマイニングのおおまかな枠組はIBMのAgrawalらによって確立され,最近盛んに研究されている.我々は,知識の表現の一つである結合ルールに関して研究を行い,結合ルールでは表現し得ない知識の発見を行うため,2分ダイアグラム結合ルールを定義した.さらに,このルールをデータから探索する際に現れる問題に関して計算理論的な考察を行い,遂次および並列計算に関して,いくつかの発見的アルゴリズムを提案した.現在,このルールに基づいたデータマイニングのプロトタイプ作成を行い,ゲノムデータを対象として成果を得ている. また,我々は離散的構造を持ったデータからの知識発見のためにグラフをその知識表現として採用した.実際,RNAやタンパク質の立体構造をグラフで表すいくつかの研究がなされている.本研究では,グラフで表現されたいくつかのデータからそれらに共通したある特徴をもつグラフを発見する問題を帰納推論の枠組で論じた.我々は,内田(広島市立大学)らが定義した項グラフをその表現として用い,グラフ言語の部分クラスであるいくつかのキャタピラ言語が多項式時間推論可能であることを証明した. 続きを見る