Closed frequent itemset mining with arbitrary side constraints

Gokberk Kocak; Ozgur Akgun; Ian James Miguel; Peter William Nightingale

doi:10.1109/ICDMW.2018.00175

Closed frequent itemset mining with arbitrary side constraints

Gokberk Kocak, Ozgur Akgun, Ian James Miguel, Peter William Nightingale

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Frequent itemset mining (FIM) is a method for finding regularities in transaction databases. It has several application areas, such as market basket analysis, genome analysis, and drug design. Finding frequent itemsets allows further analysis to focus on a small subset of the data. For large datasets the number of frequent itemsets can also be very large, defeating their purpose. Therefore, several extensions to FIM have been studied, such as adding high-utility (or low-cost) constraints and only finding closed (or maximal) frequent itemsets. This paper presents a constraint programming based approach that combines arbitrary side constraints with closed frequent itemset mining. Our approach allows arbitrary side constraints to be expressed in a high level and declarative language which is then translated automatically for efficient solution by a SAT solver. We compare our approach with state-of-the-art algorithms via the MiningZinc system (where possible) and show significant contributions in terms of performance and applicability.

Original language	English
Title of host publication	2018 IEEE International Conference on Data Mining Workshops (ICDMW)
Editors	Hanghang Tong, Zhenhui (Jessie) Li, Feida Zhu, Jeffrey Yu
Publisher	IEEE Computer Society
Pages	1224 - 1232
Number of pages	9
ISBN (Electronic)	9781538692882
ISBN (Print)	9781538692899
DOIs	https://doi.org/10.1109/ICDMW.2018.00175
Publication status	Published - 17 Nov 2018
Event	Workshop on Optimization Based Techniques for Emerging Data Mining Problems (OEDM 2018) - Sentosa Island, Singapore Duration: 17 Nov 2018 → 20 Nov 2018 https://qizhiquan.github.io/OEDM-18/

Workshop

Workshop	Workshop on Optimization Based Techniques for Emerging Data Mining Problems (OEDM 2018)
Abbreviated title	OEDM 2018
Country/Territory	Singapore
City	Sentosa Island
Period	17/11/18 → 20/11/18
Internet address	https://qizhiquan.github.io/OEDM-18/

Keywords

Data mining
Pattern mining
Frequent itemset mining
Closed frequent itemset mining
Constraint modelling

Access to Document

10.1109/ICDMW.2018.00175

essence-mining
© 2018, IEEE. This work has been made available online in accordance with the publisher's policies. This is the author created accepted version manuscript following peer review and as such may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1109/ICDMW.2018.00175
Accepted author manuscript, 254 KB

Closed frequent itemset mining with arbitrary side constraints (dataset)
Kocak, G. (Creator), Akgun, O. (Creator), Miguel, I. J. (Creator) & Nightingale, P. W. (Creator), GitHub, 2018
https://github.com/stacs-cp/OEDM18-mining
Dataset

Cite this

@inproceedings{921a03b374654acdb3cf8b608e1ef86a,

title = "Closed frequent itemset mining with arbitrary side constraints",

abstract = "Frequent itemset mining (FIM) is a method for finding regularities in transaction databases. It has several application areas, such as market basket analysis, genome analysis, and drug design. Finding frequent itemsets allows further analysis to focus on a small subset of the data. For large datasets the number of frequent itemsets can also be very large, defeating their purpose. Therefore, several extensions to FIM have been studied, such as adding high-utility (or low-cost) constraints and only finding closed (or maximal) frequent itemsets. This paper presents a constraint programming based approach that combines arbitrary side constraints with closed frequent itemset mining. Our approach allows arbitrary side constraints to be expressed in a high level and declarative language which is then translated automatically for efficient solution by a SAT solver. We compare our approach with state-of-the-art algorithms via the MiningZinc system (where possible) and show significant contributions in terms of performance and applicability.",

keywords = "Data mining, Pattern mining, Frequent itemset mining, Closed frequent itemset mining, Constraint modelling",

author = "Gokberk Kocak and Ozgur Akgun and Miguel, {Ian James} and Nightingale, {Peter William}",

year = "2018",

month = nov,

day = "17",

doi = "10.1109/ICDMW.2018.00175",

language = "English",

isbn = "9781538692899",

pages = "1224 -- 1232",

editor = "Hanghang Tong and Li, {Zhenhui (Jessie)} and Feida Zhu and Jeffrey Yu",

booktitle = "2018 IEEE International Conference on Data Mining Workshops (ICDMW)",

publisher = "IEEE Computer Society",

address = "United States",

note = "Workshop on Optimization Based Techniques for Emerging Data Mining Problems (OEDM 2018), OEDM 2018 ; Conference date: 17-11-2018 Through 20-11-2018",

url = "https://qizhiquan.github.io/OEDM-18/",

}

Kocak, G, Akgun, O , Miguel, IJ & Nightingale, PW 2018, Closed frequent itemset mining with arbitrary side constraints. in H Tong, Z Li, F Zhu & J Yu (eds), 2018 IEEE International Conference on Data Mining Workshops (ICDMW)., 8637581, IEEE Computer Society, pp. 1224 - 1232, Workshop on Optimization Based Techniques for Emerging Data Mining Problems (OEDM 2018), Sentosa Island, Singapore, 17/11/18. https://doi.org/10.1109/ICDMW.2018.00175

Closed frequent itemset mining with arbitrary side constraints. / Kocak, Gokberk; Akgun, Ozgur ; Miguel, Ian James et al.
2018 IEEE International Conference on Data Mining Workshops (ICDMW). ed. / Hanghang Tong; Zhenhui (Jessie) Li; Feida Zhu; Jeffrey Yu. IEEE Computer Society, 2018. p. 1224 - 1232 8637581.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Closed frequent itemset mining with arbitrary side constraints

AU - Kocak, Gokberk

AU - Akgun, Ozgur

AU - Miguel, Ian James

AU - Nightingale, Peter William

PY - 2018/11/17

Y1 - 2018/11/17

N2 - Frequent itemset mining (FIM) is a method for finding regularities in transaction databases. It has several application areas, such as market basket analysis, genome analysis, and drug design. Finding frequent itemsets allows further analysis to focus on a small subset of the data. For large datasets the number of frequent itemsets can also be very large, defeating their purpose. Therefore, several extensions to FIM have been studied, such as adding high-utility (or low-cost) constraints and only finding closed (or maximal) frequent itemsets. This paper presents a constraint programming based approach that combines arbitrary side constraints with closed frequent itemset mining. Our approach allows arbitrary side constraints to be expressed in a high level and declarative language which is then translated automatically for efficient solution by a SAT solver. We compare our approach with state-of-the-art algorithms via the MiningZinc system (where possible) and show significant contributions in terms of performance and applicability.

AB - Frequent itemset mining (FIM) is a method for finding regularities in transaction databases. It has several application areas, such as market basket analysis, genome analysis, and drug design. Finding frequent itemsets allows further analysis to focus on a small subset of the data. For large datasets the number of frequent itemsets can also be very large, defeating their purpose. Therefore, several extensions to FIM have been studied, such as adding high-utility (or low-cost) constraints and only finding closed (or maximal) frequent itemsets. This paper presents a constraint programming based approach that combines arbitrary side constraints with closed frequent itemset mining. Our approach allows arbitrary side constraints to be expressed in a high level and declarative language which is then translated automatically for efficient solution by a SAT solver. We compare our approach with state-of-the-art algorithms via the MiningZinc system (where possible) and show significant contributions in terms of performance and applicability.

KW - Data mining

KW - Pattern mining

KW - Frequent itemset mining

KW - Closed frequent itemset mining

KW - Constraint modelling

U2 - 10.1109/ICDMW.2018.00175

DO - 10.1109/ICDMW.2018.00175

M3 - Conference contribution

SN - 9781538692899

SP - 1224

EP - 1232

BT - 2018 IEEE International Conference on Data Mining Workshops (ICDMW)

A2 - Tong, Hanghang

A2 - Li, Zhenhui (Jessie)

A2 - Zhu, Feida

A2 - Yu, Jeffrey

PB - IEEE Computer Society

T2 - Workshop on Optimization Based Techniques for Emerging Data Mining Problems (OEDM 2018)

Y2 - 17 November 2018 through 20 November 2018

ER -

Closed frequent itemset mining with arbitrary side constraints

Abstract

Workshop

Keywords

Access to Document

Fingerprint

Datasets

Closed frequent itemset mining with arbitrary side constraints (dataset)

Cite this