幾何学的クラスタリング算法の開発とVLSI設計への応用

Material type: 文書・図像類

Author: 浅野, 哲夫ほか

Publisher: -

Publication date: 1993-08-11

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 金沢大学 / 大阪電気通信大学本研究では、最初に対毎に類似度が与えられたとき、距離が類似度に反比例するように対象を2次元の平面に写像する方法について考察し、主軸変換法がこの目的に適していることを確かめ、実際にプログラムを作成した。次に平面に与えられた多数の点に対して、最も一様に点が分布するようにこれ...

Related materials as well as pre- and post-revision versions

https://kaken.nii.ac.jp/search/?qm=90113133

https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-01550295/

https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-01550295/015502951990kenkyu_seika_hokoku_gaiyo/

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Kanazawa University Repository for Academic Resources
Digital
You can check the holdings of institutions and databases with which 学術機関リポジトリデータベース（IRDB）（機関リポジトリ） is linked at the site of 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）.
Kanazawa University Repository for Academic Resources

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: 幾何学的クラスタリング算法の開発とVLSI設計への応用
Author/Editor: 浅野, 哲夫
Asano, Tetsuo
Author Heading: 浅野, 哲夫
Asano, Tetsuo
Publication Date: 1993-08-11
Publication Date (W3CDTF): 1993-08-11
Alternative Title: Development of Geometric Clustering Algorithms and Applications to VLSI Design
Periodical title: 平成2(1990)年度科学研究費補助金一般研究(C) 研究成果報告書概要 = 1990 Fiscal Year Final Research Report Summary
No. or year of volume/issue: 1989 – 1990
Volume: 1989 – 1990
Pages: 2p.-
Text Language Code: jpn
Subject Heading: クラスタリング
類似度行列
計増幾何学
アルゴリズム
幾何学的変換法
回路分割問題
Target Audience: 一般
Note (General): 金沢大学 / 大阪電気通信大学
本研究では、最初に対毎に類似度が与えられたとき、距離が類似度に反比例するように対象を2次元の平面に写像する方法について考察し、主軸変換法がこの目的に適していることを確かめ、実際にプログラムを作成した。次に平面に与えられた多数の点に対して、最も一様に点が分布するようにこれらを直線上に写像する問題について考察し、従来の結果を非常に改善する結果を得た。本研究では平面上分点集合を2分割する問題を主に考察したが、そのままの形で扱うよりも双対平面上で考えた方が見通しがよい。実際、点を直線に、直線を点に変換すると、点集合は直線の集合に変換されるが、同じ分割を与える直線に対応する点は直線で区切られた同じ小領域に属するので、小領域を全て調べれば全ての(直線による)分割を調べたことになる。そのためにそれらの小領域を順序よく訪問する算法が必要になるが、従来は効率のよいものがなかった。本研究で開発した算法は、直線の本数に比例する記憶量さえあれば小領域の個数に比例する時間で探索を終えることができるので非常に効率がよい。本研究で開発された算法はVLSIの設計に応用することができる。実際、回路分割問題に適用した結果を論文の形にまとめ、近く投稿する予定である。この論文では、VLSIを構成するブロックとブロックを結ぶネットの集合が与えられたとき、ブロックの集合を2分割して2つの部分にまたがるネットの本数を最小にする問題について論じる。従来の方法はグラフ理論を用いていたが、いずれも定式化の段階ですでに問題を含んでいた。これに対して、本研究ではブロック間の接続度を計算した後、その情報に基づいて密接に連結されているブロックは近くに配置されるように写像を施す。その後で幾担学的変換法によって点を直線に変換し、トポロジカルウォ-クの算法を利用して最適な分割を求める。
Grouping similar objects is called cluster analysis. There have been considered a lot of algorithms. When we formulate this problem as a problem in Graph Theory, it may often become NP-complete. Therefore, we rely on heuristic algorithms. In this research we first presented an algorithm for mapping objects into points in the plane so that similar objects are placed closely, based on Principal Coordinate Analysis. Then, applying Geometric Transform, points are mapped into lines. Using Topological Walk Algorithm developed in the research, we can examine all possible regions defined by those lines. This corresponds to examination of all possible partitions of those points in the dual plane. The idea was applied to Circuit Partitioning in VLSI design.
研究課題/領域番号:01550295, 研究期間(年度):1989 - 1990
出典：「幾何学的クラスタリング算法の開発とVLSI設計への応用」研究成果報告書　課題番号01550295（KAKEN：科学研究費助成事業データベース（国立情報学研究所））（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-01550295/015502951990kenkyu_seika_hokoku_gaiyo/）を加工して作成
DOI: 10.24517/00061984
Source: https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55709&item_no=1&attribute_id=26&file_no=1
https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55709&item_no=1&attribute_id=26&file_no=1
Access Restrictions: 限定公開
Rights (production): CC BY-NC-ND
Related Material: https://kaken.nii.ac.jp/search/?qm=90113133
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-01550295/
https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-01550295/015502951990kenkyu_seika_hokoku_gaiyo/
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 金沢大学 : 金沢大学学術情報リポジトリKURA