On construction of partial association rules

Mikhail Moshkov; Marcin Piliszczuk; Beata Marta Zielosko

doi:10.1007/978-3-642-02962-2_22

On construction of partial association rules

Mikhail Moshkov, Marcin Piliszczuk, Beata Marta Zielosko

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

8 Scopus citations

Abstract

This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during greedy algorithm work, and results of the study of association rules for the most part of binary information systems. © 2009 Springer Berlin Heidelberg.

Original language	English (US)
Title of host publication	Rough Sets and Knowledge Technology
Publisher	Springer Nature
Pages	176-183
Number of pages	8
ISBN (Print)	3642029612; 9783642029615
DOIs	https://doi.org/10.1007/978-3-642-02962-2_22
State	Published - 2009

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-02962-2_22

Cite this

@inproceedings{058b43ecb4a645cb915b2ea1fad8ec27,

title = "On construction of partial association rules",

abstract = "This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during greedy algorithm work, and results of the study of association rules for the most part of binary information systems. {\textcopyright} 2009 Springer Berlin Heidelberg.",

author = "Mikhail Moshkov and Marcin Piliszczuk and Zielosko, {Beata Marta}",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2009",

doi = "10.1007/978-3-642-02962-2_22",

language = "English (US)",

isbn = "3642029612; 9783642029615",

pages = "176--183",

booktitle = "Rough Sets and Knowledge Technology",

publisher = "Springer Nature",

}

TY - GEN

T1 - On construction of partial association rules

AU - Moshkov, Mikhail

AU - Piliszczuk, Marcin

AU - Zielosko, Beata Marta

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2009

Y1 - 2009

N2 - This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during greedy algorithm work, and results of the study of association rules for the most part of binary information systems. © 2009 Springer Berlin Heidelberg.

AB - This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during greedy algorithm work, and results of the study of association rules for the most part of binary information systems. © 2009 Springer Berlin Heidelberg.

UR - http://hdl.handle.net/10754/564233

UR - http://link.springer.com/10.1007/978-3-642-02962-2_22

UR - http://www.scopus.com/inward/record.url?scp=69049094013&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02962-2_22

DO - 10.1007/978-3-642-02962-2_22

M3 - Conference contribution

SN - 3642029612; 9783642029615

SP - 176

EP - 183

BT - Rough Sets and Knowledge Technology

PB - Springer Nature

ER -

On construction of partial association rules

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this