ダウンロード数: 327
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s10994-010-5215-6.pdf | 339.61 kB | Adobe PDF | 見る/開く |
タイトル: | Efficiently mining δ-tolerance closed frequent subgraphs |
著者: | Takigawa, Ichigaku https://orcid.org/0000-0001-5633-995X (unconfirmed) Mamitsuka, Hiroshi https://orcid.org/0000-0002-6607-5617 (unconfirmed) |
著者名の別形: | 瀧川, 一学 |
キーワード: | Frequent subgraph mining δ-tolerance closedness Partial reverse search |
発行日: | Feb-2011 |
出版者: | Springer, Part of Springer Science+Business Media |
誌名: | Machine Learning |
巻: | 82 |
号: | 2 |
開始ページ: | 95 |
終了ページ: | 121 |
抄録: | The output of frequent pattern mining is a huge number of frequent patterns, which are very redundant, causing a serious problem in understandability. We focus on mining frequent subgraphs for which well-considered approaches to reduce the redundancy are limited because of the complex nature of graphs. Two known, standard solutions are closed and maximal frequent subgraphs, but closed frequent subgraphs are still redundant and maximal frequent subgraphs are too specific. A more promising solution is δ-tolerance closed frequent subgraphs, which decrease monotonically in δ, being equal to maximal frequent subgraphs and closed frequent subgraphs for δ=0 and 1, respectively. However, the current algorithm for mining δ-tolerance closed frequent subgraphs is a naive, two-step approach in which frequent subgraphs are all enumerated and then sifted according to δ-tolerance closedness. We propose an efficient algorithm based on the idea of “reverse-search” by which the completeness of enumeration is guaranteed and for which new pruning conditions are incorporated. We empirically demonstrate that our approach significantly reduced the amount of real computation time of two compared algorithms for mining δ-tolerance closed frequent subgraphs, being pronounced more for practical settings. |
著作権等: | The final publication is available at www.springerlink.com この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
URI: | http://hdl.handle.net/2433/139467 |
DOI(出版社版): | 10.1007/s10994-010-5215-6 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。