K語近接相関パタンの高速発見アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
与えられた大量の文書の集積から, 分類精度を最大にする文字列パタンを見つける問題を考察する.複数の文字列の近接した出現を記述する近接語相関パタンを導入し, 文字出現が独立で一様な確率分布にしたがうランダムテキストに対して, 分類精度を最大化する近接度がkでd個の語からなる語相関パタンを平均計算時間O(k^<d-1>nlog^<d+1>n)および領域O(k^<d-1>n)で計算するアルゴリズムを与える.このアルゴリズムは, すべての部分語を枚挙する自明なアルゴリズムの時間計算量O(n^<2d+1>)に対して, 著しい高速化を達成しており, 遺伝子情報データのようなほぼランダムなテキストに対するデータマイニング問題に適用可能である.この結果は, 任意個数の語からなる近接相関パタンに対して, 分類精度最適化問題が多項式時間近似スキームをもたない事実と対照的である.
- 1998-11-20
著者
-
有川 節夫
九州大学副学長、附属図書館長、大学院システム情報科学研究院教授
-
下薗 真一
九州工業大学 情報工学部
-
有村 博紀
九州大学 システム情報科学研究院
-
下薗 真一
九州工業大学知能情報工学科
-
下薗 真一
九州工業大学
-
有川 節夫
九州大学 大学院システム情報科学研究科
関連論文
- 発見科学の構想と展開(発見科学)
- 帰納的実数値関数の帰納推論における論駁性と信頼性
- BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
- 九州大学総長 有川節夫氏--多様な専門性を生かしグローバルな視点で大学の役割を果たす (新春トップインタビュー トップが語る2011年)
- 九州大学 総長 有川節夫氏 自由闊達な研究活動をベースとしグローバルに評価される大学に (新春トップインタビュー トップが語る2010年)
- 九州大学 総長 有川節夫氏 都市とともに栄え、市民が誇りを持ち、頼りにする大学づくりを目指す (新春トップインタビュー トップが語る2009年)
- 頻出順序木パターンを見つけるオンラインアルゴリズム (計算機科学基礎理論の新展開)
- 滑走窓や忘却の概念を用いたオンライン型半構造データマイニングアルゴリズム
- 滑走窓や忘却の概念を用いたオンライン型半構造データマイニングアルゴリズム
- 半構造データマイニングのための部分構造パターンの効率的探索
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 平衡直線的プログラムに対するパターン照合アルゴリズム
- 2G-2 圧縮テキストに対する文字列照合のための統一的枠組み
- 2G-1 データ圧縮による文字列照合の高速化
- 複数文字列パターンによるアミノ酸配列からのタンパク質モティーフの発見
- 複数文字列パターンによる正例からのタンパク質モチーフの発見
- 文字列パターン照合のための損失のあるデータ圧縮
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- AI・ニューロ・ファジィ : 1990年11月25日(於:池袋サンシャイン集会室)
- Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)
- 表面実相ロボットの実相シーケンスの決定に対する巡回セールスマン問題のアルゴリズムの適用
- パネル討論「機械学習の理論と実際」 : 1991年6月28日第5回人工知能学会全国大会(於:学習院大学大講堂)にて (「機械学習の理論と実際」)
- ウェブデータマイニング(「データマイニング特集号」)
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- 学習における計算論的アプローチ : 機械学習に向けて (計算的学習理論とその応用)
- 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
- 1Q-4 図書目録イメージデータの検索システム
- 国立大学図書館の課題と解決の試み
- 大学図書館の将来像(大学図書館)
- 分散記憶型並列計算機における大規模接尾辞配列の構築法
- テキストマイニングを用いたウェブデータからのキーワード獲得
- 分散記憶型並列計算機における大規模接尾辞配列の構築法
- HTMLからのテキストの自動切り出しアルゴリズムと実装
- イメージによる図書目録カード検索システム : 遡及入力問題の一解決法
- イメージによる図書目録カード検索システム : 遡及入力問題の一解決法
- 複数文字列照合技法を用いたEFS処理系の実現
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
- ALT'96報告
- K語近接相関パタンの高速発見アルゴリズム
- 最適パタン発見に基づくテキストデータマイニング : 大規模テキスト索引における高速な実装方式
- 「知財の編集・流通・管理のためのメディアアーキテクチャを目指して」へのコメントと回答(AIマップ)
- On Approximation Algorithms for Local Multiple Alignment (合同研究会"AIシンポジウム'99"(第10回))
- 文字列相関パタンの分類精度最大化問題について
- ユーザのオンラインWeb探索をサポートするエージェントモデルについて
- 省スペースな線形時間文法圧縮アルゴリズム
- DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- Minimum Multiset Covering 問題の近似アルゴリズムについて
- 平面巡回セールスマン問題の高速な近似アルゴリズム
- 無矛盾最小OBDD問題の近似困難性について
- ALT '94報告
- イメージデータ化された図書目録カードの検索システム
- 数値デ-タからの微分方程式の学習
- 巨大テキストデータからの高速パタン発見
- モデル推論 (計算的学習理論とその応用)
- 部分語相関ルール発見のための高速アルゴリズム (アルゴリズムと計算の理論)
- 最適パタン発見に基づくテキストデータマイニング
- 大規模テキストデータのための探索的文書ブラウジング
- 基調講演 発見科学の展開 (2003年情報学シンポジウム講演論文集--データの共有と知識の発見・創造) -- (知識発見:現状と展望)
- 木の変換規則の例からの学習 (小特集 「発見科学」及び一般演題)
- 部分語計数問題の接尾辞配列を用いた高速アルゴリズム (計算モデルとアルゴリズム)
- 1T-10 仮想接尾辞木 : テキストデータマイニングのための接尾辞配列を用いた高速な部分語頻度計算法
- 動的パターン照合機の効率的な実現法
- 発見科学 : もうひとつの永遠の課題
- 九州大学大学院システム情報科学研究科情報理学専攻
- 「AIマップ : 機械学習から機械発見へ」へのコメントと回答
- 機械学習から機械発見へ
- 学習アルゴリズムによる機械発見
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 決定木とアトム列の汎化
- 名誉会員 北川敏男先生を追悼する〔含 肖像・略歴〕
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 小さな国際会議
- 30年後の情報社会
- 人工知能基礎論研究会と関連分野の動向
- 九州大学理学部基礎情報学研究施設有川研究室