In knowledge discovery and data mining many measures of interestingness have been proposed in order to measure the relevance and utility of the discovered patterns. Among these measures, an important role is played by Bayesian confirmation measures, which express in what degree a premise confirms a conclusion. In this paper, we are considering knowledge patterns in a form of “if…, then…” rules with a fixed conclusion. We investigate a monotone link between Bayesian confirmation measures, and classic dimensions being rule support and confidence. In particular, we formulate and prove conditions for monotone dependence of two confirmation measures enjoying some desirable properties on rule support and confidence. As the confidence measure is unable to identify and eliminate non-interesting rules, for which a premise does not confirm a conclusion, we propose to substitute the confidence for one of the considered confirmation measures in mining the Pareto-optimal rules. We also provide general conclusions for the monotone link between any confirmation measure enjoying the desirable properties and rule support and confidence. Finally, we propose to mine rules maximizing rule support and minimizing rule anti-support, which is the number of examples, which satisfy the premise of the rule but not its conclusion (called counter-examples of the considered rule). We prove that in this way we are able to mine all the rules maximizing any confirmation measure enjoying the desirable properties. We also prove that this Pareto-optimal set includes all the rules from the previously considered Pareto-optimal borders.

Mining Pareto-optimal rules with respect to support and confirmation or support and anti-support

GRECO, Salvatore;
2007-01-01

Abstract

In knowledge discovery and data mining many measures of interestingness have been proposed in order to measure the relevance and utility of the discovered patterns. Among these measures, an important role is played by Bayesian confirmation measures, which express in what degree a premise confirms a conclusion. In this paper, we are considering knowledge patterns in a form of “if…, then…” rules with a fixed conclusion. We investigate a monotone link between Bayesian confirmation measures, and classic dimensions being rule support and confidence. In particular, we formulate and prove conditions for monotone dependence of two confirmation measures enjoying some desirable properties on rule support and confidence. As the confidence measure is unable to identify and eliminate non-interesting rules, for which a premise does not confirm a conclusion, we propose to substitute the confidence for one of the considered confirmation measures in mining the Pareto-optimal rules. We also provide general conclusions for the monotone link between any confirmation measure enjoying the desirable properties and rule support and confidence. Finally, we propose to mine rules maximizing rule support and minimizing rule anti-support, which is the number of examples, which satisfy the premise of the rule but not its conclusion (called counter-examples of the considered rule). We prove that in this way we are able to mine all the rules maximizing any confirmation measure enjoying the desirable properties. We also prove that this Pareto-optimal set includes all the rules from the previously considered Pareto-optimal borders.
File in questo prodotto:
File Dimensione Formato  
MiningParetoEngApplArInt2007.pdf

solo gestori archivio

Tipologia: Versione Editoriale (PDF)
Licenza: Non specificato
Dimensione 258.41 kB
Formato Adobe PDF
258.41 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/26288
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 29
social impact