データベースから近似的な規則を抽出する高速アルゴリズムの研究

数据库近似规则提取高速算法研究

基本信息

批准号：
12780286
负责人：
下薗真一
金额：
$ 1.15万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

本研究では最大合意問題とよばれる規則獲得の問題を発展させ,例からの規則抽出一般に適用する枠組みを提案した.そして効率のよい近似アルゴリズムを設計するための理論構築を行い,さらに実用性を確かめるためのプロトタイピングを行った.具体的には,エントロピー関数など様々な評価関数を使用できるよう拡張した.アプリケーション面では特に,ネットワーク上のウェブのソースファイル,SGMLファイルなど,従来のデータマイニング手法が苦手とする弱構造の大規模データベースヘの応用を行った.まず最大合意問題の評価関数をより一般に拡張し,例の分類精度をエントロピー,Giniインデックスなどを使って評価する方法を考察した.そして高速なアルゴリズムを設計し,さらにその実装評価を行った.現実の要求に近づけた状況で,メモリやディスクスペースを効果的に使用する技術とアルゴリズムとの親和性を,実験的にも検証した.特に,弱い構造,あるいは疑構造しか仮定できないテキストデータベースに対して,レコードの構造や登録項目(アイテム)をあらかじめ固定して想定する必要のない,入力に対して動的にレコードの処理や登録項目の抽出を行うシステムを構築した.その成果として,現実のテキストデータベースなどを対象とした知識抽出システムのプロトタイピングを行い,最大合意問題に基づくシステムの能力と実用上の問題点を明らかにした.

在这项研究中，我们开发了获得称为最大共识问题的规则的问题，并提出了一个将规则提取从示例中提取到一般示例的框架。然后，我们构建了理论以设计有效的近似算法，并进行了进一步的原型来验证实用性。具体而言，我们扩展了各种评估功能（例如熵功能）的使用。特别是，我们应用于具有弱结构的大规模数据库，例如网络上的Web源文件，SGML文件等，这些文件在常规数据挖掘方法上很差。首先，我们更普遍地扩展了最大共识问题的评估功能，并使用熵，Gini索引等评估了示例的分类精度。我们还研究了高速算法并评估了其实现。我们还通过实验验证了在接近实际需求的情况下有效地使用内存和磁盘空间的技术之间的亲和力。特别是，我们构建了一个系统，该系统会动态处理记录并提取注册的输入项目，而无需将记录的结构和注册项目（项目）预先预先，因为文本数据库只能假设弱或可疑的结构。结果，我们将针对真实文本数据库等的知识提取系统进行制作，从而根据最大共识问题揭示了系统的功能和实际问题。