パターンマイニング問題におけるセーフパターンプルーニングを用いたスパースモデルの学習

• Item type: SIG Technical Reports(1)
• 公開日: 2016-08-29
• タイトル: パターンマイニング問題におけるセーフパターンプルーニングを用いたスパースモデルの学習
• タイトル / 言語: en
• タイトル: Sparse learning for pattern mining problem by using Safe Pattern Pruning method
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学
• 著者所属: 名古屋工業大学
• 著者所属: 名古屋工業大学
• 著者所属: 東京大学
• 著者所属: 名古屋工業大学
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者名: 中川, 和也; 鈴村, 真矢; 烏山, 昌幸; 津田, 宏治; 竹内, 一郎
• 著者名(英): Kazuya, Nakagawa; Shinya, Suzumura; Masayuki, Karasuyama; Koji, Tsuda; Ichiro, Takeuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，パターンマイニング問題におけるスパースな予測モデルの学習を考える．予測モデルの学習において我々が提案するセーフパターンプルーニングという手法は，真の最適なモデルに必要なパターンを含む集合を効率的に見つけ出すことを可能とする．この手法は近年研究が行われているセーフ特徴スクリーニングと呼ばれる手法に基づいたものであり，真のモデルに必要のない特徴を学習前に同定し，最適化から取り除くことで効率化を図っている．パターンマイニングのための予測モデルを学習する従来法としてブースティングタイプのものが提案されているが，我々の手法は従来法と比べてパターンのサーチ回数が少ないというメリットがある．本論文ではグラフマイニングとアイテムセットマイニングにおける両者の計算時間を比較し，提案法の有用性を検証した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we study predictive pattern mining problems where the goal is to construct a predictive model based on a subset of predictive patterns in the database. Our main contribution is to introduce a novel method called safe pattern pruning (SPP) for a class of predictive pattern mining problems. The SPP method allows us to efficiently find a superset of all the predictive patterns in the database that are needed for the optimal predictive model. The advantage of the SPP method over existing boosting-type method is that the former can find the superset by a single search over the database, while the latter requires multiple searches. The SPP method is inspired by recent development of safe feature screening. In order to extend the idea of safe feature screening into predictive pattern mining, we derive a novel pruning rule called safe pattern pruning (SPP) rule that can be used for searching over the tree defined among patterns in the database. The SPP rule has a property that, if a node corresponding to a pattern in the database is pruned out by the SPP rule, then it is guaranteed that all the patterns corresponding to its descendant nodes are never needed for the optimal predictive model. We apply the SPP method to graph mining and item-set mining problems, and demonstrate its computational advantage.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11131797
• 書誌情報: 研究報告コンピュータビジョンとイメージメディア（CVIM）; 巻 2016-CVIM-203, 号 23, p. 1-8, 発行日 2016-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8701
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会