2024-03-28T19:01:30Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000502802023-04-27T10:00:04Z01164:04402:04422:04423
Cl - GBI : A Novel Strategy to Extract Typical Patterns from Graph DataCl - GBI : A Novel Strategy to Extract Typical Patterns from Graph Dataenghttp://id.nii.ac.jp/1001/00050280/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=50280&item_no=1&attribute_id=1&file_no=1Copyright (c) 2004 by the Information Processing Society of JapanInstitute of Scientific and Industrial Research Osaka UniversityInstitute of Scientific and Industrial Research Osaka UniversityInstitute of Scientific and Industrial Research Osaka UniversityInstitute of Scientific and Industrial Research Osaka UniversityPHUCHIENNGUYENKOUZOU, OHARAHIROSHI, MOTODATAKASHI, WASHIOA machine learning technique called Graph-Based Induction (GBI) extracts typical patterns from graph data by stepwise pair expansion (pair-wise chunking). Because of its greedy search strategy it is very efficient but suffers from incompleteness of search. Also it cannot give the correct number of occurrences as well as the positions of patterns in each transaction of the graph data. Improvement is made on its search capability by using a new search strategy where frequent pairs are never chunked but used as pseud-nodes in the subsequent steps thus allowing extraction of overlapping subgraphs. This new algorithm called Cl-GBI (Chunkingless Graph-Based Induction) was tested against two datasets the promoter dataset from UCI repository and the hepatitis dataset provided by Chiba University and shown successful in extracting more typical substructures.Graph-Based Induction(GBI法)は,多頻出ノードペアを逐次結合(チャンク)することによりグラフ構造データから典型的なパターンを抽出する機械学習手法である.Greedy探索を採用することにより,GBI法は非常に効率的である反面,その探索は完全ではなく,この不完全性のためにパターンの頻度を正しく計算できない場合があるという問題をもつ.また,抽出されたパターンが元のグラフのどこに現れるかという情報も探索過程で失われる.これらの問題を解消するために,本研究では多頻出ノードペアを実際にはチャンクせずに1つの擬似ノードとして処理する新たな探索手法Chankingless Graph-Based Induction (Cl-GBI法)を提案する.これにより,従来のGBIでは同時に抽出することができなかった(部分構造を共有する)複数の重複パターンを抽出することが可能となる.本稿では,Cl-GBI法の詳細を述べるとともに,カリフォルニア大学アーバイン校の機械学習用データセットに含まれるPromoterデータセット,および千葉大学医学部から提供された肝炎データセットを対象に,Cl-GBI法がより多くの典型的なパターンを抽出できることを示す.AA11135936情報処理学会研究報告知能と複雑系(ICS)2004125(2004-ICS-138)1051102004-12-052009-06-30