Paper Abstract and Keywords |
Presentation |
2016-09-05 15:45
Sparse learning for pattern mining problem by using Safe Pattern Pruning method Kazuya Nakagawa, Shinya Suzumura, Masayuki Karasuyama (NIT), Koji Tsuda (Univ. of Tokyo), Ichiro Takeuchi (NIT) PRMU2016-70 IBISML2016-25 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
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. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Pattern mining / Sparse learning / Safe screening / Convex optimization / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 116, no. 209, IBISML2016-25, pp. 127-134, Sept. 2016. |
Paper # |
IBISML2016-25 |
Date of Issue |
2016-08-29 (PRMU, IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
PRMU2016-70 IBISML2016-25 |
Conference Information |
Committee |
PRMU IPSJ-CVIM IBISML |
Conference Date |
2016-09-05 - 2016-09-06 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
|
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
IBISML |
Conference Code |
2016-09-PRMU-CVIM-IBISML |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Sparse learning for pattern mining problem by using Safe Pattern Pruning method |
Sub Title (in English) |
|
Keyword(1) |
Pattern mining |
Keyword(2) |
Sparse learning |
Keyword(3) |
Safe screening |
Keyword(4) |
Convex optimization |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Kazuya Nakagawa |
1st Author's Affiliation |
Nagoya Institute of Technology (NIT) |
2nd Author's Name |
Shinya Suzumura |
2nd Author's Affiliation |
Nagoya Institute of Technology (NIT) |
3rd Author's Name |
Masayuki Karasuyama |
3rd Author's Affiliation |
Nagoya Institute of Technology (NIT) |
4th Author's Name |
Koji Tsuda |
4th Author's Affiliation |
University of Tokyo (Univ. of Tokyo) |
5th Author's Name |
Ichiro Takeuchi |
5th Author's Affiliation |
Nagoya Institute of Technology (NIT) |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2016-09-05 15:45:00 |
Presentation Time |
30 minutes |
Registration for |
IBISML |
Paper # |
PRMU2016-70, IBISML2016-25 |
Volume (vol) |
vol.116 |
Number (no) |
no.208(PRMU), no.209(IBISML) |
Page |
pp.127-134 |
#Pages |
8 |
Date of Issue |
2016-08-29 (PRMU, IBISML) |
|