权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

計算理論的設計による知識抽出モデルに関する研究

基于计算理论设计的知识抽取模型研究

基本信息

批准号：
16092202
负责人：
徳山豪
金额：
$ 8.38万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

本研究の目的はデータマイニングにおける現在の精度限界を打破するための知識抽出モデルの提案と、それに関する理論研究及び実際のシステムの構築である。特に、研究代表者の持つ先端技術である計算幾何学的手法を中心に、計算理論手法による限界突破を目指した。継続中の研究テーマについては研究をさらに進めると共に、過去3年間に行った研究の取りまとめを行った。新たに得られた研究成果については、国内外の会議や研究会にてを発表するとともに、論文に纏めて学術論文誌に投稿をした。以下、新たに得られた結果について簡単に紹介する。昨年までの研究における重要な成果として、ゾーン図に関する結果が挙げられるが、これは点と点の間の3等分線によって描かれる図であった。本年度はこれをさらに発展させ、点と線分の間の3等分線について考え、そのような等分線の一意的存在性を示すと共に、3等分線を効率的に計算するアルゴリズムを提案した。次に、平面上に辺を曲線として描画されたグラフにおいて、辺が交差しない全域部分木を計算する問題を考えた。非交差な全域部分木を持つかどうかの判定はNP困難問題であり、交差数を最小化する問題は近似困難である事が知られている。本研究では、自然なパラメタに対し、パラメトリック計算量(パラメタへの依存度を考慮する計算量)を考察した。対象とするパラメタは、入力されるトポロジカルグラフにおける交差辺対の数、交差辺の数、頂点集合の凸包の内点である頂点数である。また、3-SAT問題への帰着により、この問題に対して計算困難性を示した。

The purpose of this study is to break through the accuracy limits of the current knowledge extraction, theoretical research and practical system construction. In particular, research representatives hold the leading edge of technology, computational geometry, and theoretical methods. Research in the past three years New research achievements, conferences and research meetings at home and abroad, papers and academic papers The following is a summary of the results obtained. The important results of the research conducted last year are as follows: This year, the development of the three bisectors between the points and the bisectors, the existence of the meaning of the bisectors, the calculation of the three bisectors, and the proposal of the bisector. Second, the plane on the curve to draw the middle, the intersection of the whole part of the wood calculation problem Non-cross-difference global partial tree holds In this study, we investigate the calculation of the dependence degree of the natural environment. The number of intersection pairs, the number of intersection pairs, the number of vertex points inside the convex hull of the vertex set, and the number of vertex points in the convex hull of the vertex set. In addition, due to the analysis of the 3-SAT problem, the computational difficulty associated with this problem was demonstrated.