nach oben

Data Mining and Knowledge Discovery

Erschienen in:

01.09.2006

A systematic approach to the assessment of fuzzy association rules

verfasst von: Didier Dubois, Eyke Hüllermeier, Henri Prade

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 2/2006

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In order to allow for the analysis of data sets including numerical attributes, several generalizations of association rule mining based on fuzzy sets have been proposed in the literature. While the formal specification of fuzzy associations is more or less straightforward, the assessment of such rules by means of appropriate quality measures is less obvious. Particularly, it assumes an understanding of the semantic meaning of a fuzzy rule. This aspect has been ignored by most existing proposals, which must therefore be considered as ad-hoc to some extent. In this paper, we develop a systematic approach to the assessment of fuzzy association rules. To this end, we proceed from the idea of partitioning the data stored in a database into examples of a given rule, counterexamples, and irrelevant data. Evaluation measures are then derived from the cardinalities of the corresponding subsets. The problem of finding a proper partition has a rather obvious solution for standard association rules but becomes less trivial in the fuzzy case. Our results not only provide a sound justification for commonly used measures but also suggest a means for constructing meaningful alternatives.

Vorheriger Artikel A Model-Based Frequency Constraint for Mining Associations from Transaction Data

Nächster Artikel Mining top-K frequent itemsets from data streams

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Some authors reserve the term “quantitative association rule” for the case where partitions are not predefined.

In fact, there are of course cases where the number of frequent itemsets will hardly be reduced. In sparse domains, for example, most frequent itemsets are already closed.

See Fig. 2 for an illustration of the product t-norm.

A definition of an additive generator can be found in the appendix.

A definition of an ordinal sum is given in the appendix.

Strictly speaking, such a rule is of course forbidden if an attribute is not allowed to be part of the antecedent and consequent at the same time.

This operator is the core of all residuated implications (20).

This conjunctive approach to modeling fuzzy rules has first been proposed by Mamdani and Assilian (1975) in the context of fuzzy control and is now widely known as Mamdani rules.

Using the definition (20) of a residuated implication, this equality is easy to prove.

Aggarwal CC, Yu PS (1998) A new framework for itemset generation. In: PODS-98, symposium on principles of database systems. Seattle, WA, USA, pp 18–24

Agrawal R, Srikant R (1994) Fast algorithms for mining association rules. In: Proceedings of the 20th conference on VLDB. Santiago, Chile, pp 487–499

Alsina C (1985) On a family of connectives for fuzzy sets. Fuzzy Sets Syst 16:231–235CrossRefMathSciNet

Alsina C, Trillas E, Valverde L (1983) On some logical connective for fuzzy sets theory. J Math Anal Appl 93:15–26MATHCrossRefMathSciNet

Au W-H, Chan KCC (1998) An effective algorithm for discovering fuzzy rules in relational databases. In: Proceedings of the IEEE World Congress on computational intelligence. Piscataway, NJ, pp 1314–1319

Au W-H, Chan KCC (1999) FARM: A data mining system for discovering fuzzy association rules. In: Proceedings of the FUZZ-IEEE-99. Seoul, Korea, pp 1217–1222

Au W-H, Chan KCC (2003) Mining fuzzy association rules in a bank-account database. IEEE Trans Fuzzy Syst 11(2):238–248CrossRef

Au W-H, Chan KCC (2005) Mining changes in association rules: A fuzzy approach. Fuzzy Sets Syst 149(1):87–104MATHCrossRefMathSciNet

Barber B, Hamilton HJ (2003) Extracting share frequent itemsets with infrequent subsets. Data Min Knowl Disc 7:153–185CrossRefMathSciNet

Belohlavek R (1999) Fuzzy Galois connections. Math Logic J 45(4):497–504MATHMathSciNet

Bosc P, Dubois D, Pivert O, Prade H (2001) On fuzzy association rules based on fuzzy cardinalities. In: Proceedings of the FUZZ-IEEE-2001, 10th IEEE international conference on fuzzy systems. Melbourne, Australia

Bosc P, Pivert O (2001) On some fuzzy extensions of association rules. In: Proc. IFSA/NAFIPS-2001. Vancouver, Canada

Cai CH, Fu A, Cheng CH, Kwong WW (1998) Mining association rules with weighted items. In: IDEAS-98, International database engineering and application symposium. Cardiff, Wales, pp 68–77

Chen G, Wei Q (2002) Fuzzy association rules and the extended mining algorithms. Inf Sci 147(1–4):201–228MATHCrossRefMathSciNet

Chen G, Wei Q, Kerre E, Wets G (2003) Overview of fuzzy associations mining. In: Proceedings of the ISIS-2003, 4th International symposium on advanced intelligent systems. Jeju, Korea

Chen G, Wei Q, Kerre EE (2000) Fuzzy data mining: Discovery of fuzzy generalized association rules. In: Bordogna G, Pasi G (eds) Recent issues on fuzzy databases. Springer-Verlag

Chien BC, Lin ZL, Hong TP (2001) An efficient clustering algorithm for mining fuzzy quantitative association rules. In: Proceedings of the 9th international fuzzy systems association World Congress. Vancouver, pp 1306–1311

Coenen F, Goulbourne G, Leng P (2004a) Tree structures for mining association rules. Data Min Knowl Disc 8:25–51CrossRefMathSciNet

Coenen F, Leng P, Ahmed S (2004b) Data structures for association rule mining: T-trees and P-trees. IEEE Trans Knowl Data Eng 16(6):774–778CrossRef

DeFinetti B (1936) La logique des probabilités. Int Cong de Philosophie Scientifique 5:1–9

DeGraaf JM, Kosters WA, Witteman JJW (2001) Interesting fuzzy association rules in quantitative databases. In: Proceedings of the 5th European conference on principles and practice of knowledge discovery in databases, PKDD-01. Freiburg, Germany, pp 140–151

Delgado M, Marin N, Sanchez D, Vila MA (2003) Fuzzy association rules: general model and applications. IEEE Trans Fuzzy Syst 11(2):214–225CrossRef

Delgado M, Sanchez D, Vila MA (2000) Acquisition of fuzzy association rules from medical data. In: Barro S, Marin R (eds) Fuzzy logic in medicine. Physica Verlag

Dougherty J, Kohavi R, Sahami M (1995) Supervised and unsupervised discretization of continuous features. In: Prieditis A, Russell S (eds) Machine learning: Proceedings of the 12th international conference. Morgan Kaufmann, pp 194–202

Dubois D, Hüllermeier E, Prade H (2003) A note on quality measures for fuzzy association rules. In: Proceedings of the IFSA-03, 10th international fuzzy systems association world congress, number 2715 in LNAI. Springer-Verlag, Istambul, pp 677–648

Dubois D, Prade H (1980) New results about properties and semantics of fuzzy-set-theoretic operators. In: Wang PP, Chang SK (eds) Fuzzy sets: theory and applications to policy analysis and information systems. Plenum Publication, pp 59–75

Dubois D, Prade H (1985) Fuzzy cardinality and the modeling of imprecise quantification. Fuzzy Sets Syst 16:199–230MATHCrossRefMathSciNet

Dubois D, Prade H (1992) Gradual inference rules in approximate reasoning. Inf Sci 61(1,2):103–122MATHCrossRefMathSciNet

Dubois D, Prade H (1994) Conditional objects as non-monotonic consequence relationships. IEEE Trans Syst Man Cybern 24(12):1724–1739CrossRefMathSciNet

Dubois D, Prade H (1996) What are fuzzy rules and how to use them. Fuzzy Sets Syst 84:169–185MATHCrossRefMathSciNet

Dubois D, Prade H (2000) Fuzzy sets in data summaries—outline of a new approach. In: Proceedings of the IPMU-2000, international conference on information processing and management of uncertainty in knowledge-based systems. Madrid, Spain, pp 1035–1040

Dubois D, Prade H, Sudkamp T (2003) A discussion of indices for the evaluation of fuzzy associations in relational databases. In: Proceedings of the IFSA-03, 10th international fuzzy systems association world congress. Istambul, pp 111–118

Dubois D, Prade H, Sudkamp T (2005) On the representation, measurement, and discovery of fuzzy associations. IEEE Trans on Fuzzy Syst 13(2):250–262CrossRef

Fodor J, Roubens M (1994) Fuzzy preference modelling and multicriteria decision support. Kluwer

Frank MJ (1979) On the simultaneous associativity of \(f(x,y)\) and \(x+y-f(x,y)\). Aeq Math 19:194–226

Fu A, Wong MH, Sze SC, Wong WC, Wong WL, Yu WK (1998) Finding fuzzy sets for the mining of fuzzy association rules for numerical attributes. In: IDEAL-98, 1st International symposium on intelligent data engineering and learning. Hong Kong, pp 263–268

Fu Y, Han J (1995) Meta-rule-guided mining of association rules in relational databases. In: KDOOD/TDOOD. Singapore, pp 39–46

Goethals B, Zaki MJ (2003) Advances in frequent itemset mining implementations. In: Goethals B, Zaki MJ (eds) Proceedings of the IEEE ICDM workshop on frequent itemset mining implementations. Melbourne, Florida, USA

Goethals B, Zaki MJ (2004) Advances in frequent itemset mining implementations: Report on FIMI'03. SIGKDD Explorations 6(1):109–117CrossRef

Goodman IR, Nguyen HT, Walker EA (1991) Conditional inference and logic for intelligent systems. North-Holland, Amsterdam

Gyenesei A (2000) A fuzzy approach for mining quantitative association rules. Technical Report 336, Turku Centre for Computer Science

Gyenesei A (2000) Mining weighted association rules for fuzzy quantitative items. Technical Report 346, Turku Centre for Computer Science

Gyenesei A (2001) A fuzzy approach for mining quantitative association rules. Acta Cybern 15:305–320MATHMathSciNet

Gyenesei A (2001) Interestingness measures for fuzzy association rules. In: Proceedings of the 5th European conference on principles and practice of knowledge discovery in databases, PKDD-01. Freiburg, Germany, pp 152–164

Hamacher H (1978) Über logische Aggregationen nichtbinär explizierter Entscheidungskriterien; Ein axiomatischer Beitrag zur normativen Entscheidungstheorie (About logical aggregation of non-binary explicated decision criteria; an axiomatic contribution to normative decision theory). R.G. Fischer Verlag

Han J, Fu Y (1995) Discovery of multi-level association rules from large databases. In: Proceedings of the international conference on very large databases. Zurich, Switzerland, pp 420–431

Han J, Pei J, Yin Y, Mao R (2004) Mining frequent patterns without candidate generation. Data Min Knowl Disc 8:53–87CrossRefMathSciNet

Harper WL, Stalnaker R, Pearce G (eds) (1981) IFS. D. Reidel, Dordrecht, The Netherlands

Hipp J, Güntzer U, Nakhaeizadeh G (2000) Algorithms for association rule mining—a general survey and comparison. Newsl Spec Int Group Knowl Disc Data Min 2(1):58–64

Hüllermeier E (2001) Fuzzy association rules: Semantic issues and quality measures. In: Proceedings of the international conference on computational intelligence—7th fuzzy days, number 2206 in LNCS. Springer-Verlag, Dortmund, Germany, pp 380–391

Hüllermeier E (2001) Implication-based fuzzy association rules. In: Proceedings of the 5th European conference on principles and practice of knowledge discovery in databases, PKDD–01. Springer-Verlag, Freiburg, Germany, pp 241–252

Hüllermeier E, Beringer J (2003) Mining implication-based fuzzy association rules in databases. In: Bouchon-Meunier B, Foulloy L, Yager RR (eds) Intelligent systems for information processing: From Representation to applications. Elsevier

Kaufmann A (1975) Introduction to the theory of fuzzy subsets. Academic Press, New YorkMATH

Kaya M, Alhajj R (2005) Genetic algorithm based framework for mining fuzzy association rules. Fuzzy Sets Syst 152(3):587–601MATHCrossRefMathSciNet

Klement EP, Mesiar R, Pap E (2000) Triangular norms. Kluwer

Klemettinen M, Mannila H, Ronkainen P, Toivonen H, Verkamo A (1994) Finding interesting rules from large sets of discovered association rules. In: Proceedings of the third international conference on information and knowledge management, CIKM–94, pp 401–407

Klir GJ, Folger TA (1988) Fuzzy sets, uncertainty, and information. Prentice Hall

Kraus S, Lehmann D, Magidor M (1990) Nonmonotonic reasoning, preferential models and cumulative logics. Artif Intell 44:167–207MATHCrossRefMathSciNet

Kuok CM, Fu A, Hon Wong M (1998) Mining fuzzy association rules in databases. SIGMOD Record 27:41–46CrossRef

Lent B, Swami A, Widom J (1997) Clustering association rules. In: Proceedings of the ICDE–97. Birmingham, UK

Lewis D (1973) Probabilities of conditionals and conditional probabilities. J Philos Logic 3

Ling CH (1965) Representations of associative functions. Publ Math Debrecen 12:189–212MathSciNet

De Luca A, Termini S (1972) A definition of non-probabilistic entropy in the setting of fuzzy sets theory. Inf Control 24:301–312CrossRefMathSciNet

Lucchesse C, Orlando S, Perego R (2004) DCI-closed: A fast and memory efficient algorithm to mine frequent closed itemsets. In: Goethals B, Zaki MJ (eds) Proceedings of the IEEE ICDM workshop on frequent itemset mining implementations. Brighton, UK

Luo J, Bridges S (2000) Mining fuzzy association rules and fuzzy frequency episodes for intrusion detection. Int J Intell Syst 15(8):687–703MATHCrossRef

Mamdani E, Assilian S (1975) An experiment in linguistic synthesis with a fuzzy logic controller. Int J Man-Mach Stud 7:1–13MATHCrossRef

Miller RJ, Yang Y (1999) Association rules over interval data. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 452–461

Nelsen RB (1999) An introduction to copulas. Springer-Verlag.

Ohsaki M, Kitaguchi S, Okamoto K, Yokoi H, Yamaguchi T (2004) Evaluation of rule interestingness measures with a clinical dataset on hepatitis. Springer-Verlag, Pisa, Italy, pp 362–373

Park JS, Chen MS, Yu PS (1995) An efficient hash-based algorithm for mining association rules. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 175–186

Pasquier N, Bastide Y, Taouil R, Lakhal L (1999) Discovering frequent closed itemsets for association rules. In: Proceedings of the 7th international conference on database theory, number 1540 in LNCS. Springer, pp 398–416

Pedrycz W (1996) Data mining and fuzzy modeling. In: Proceedings of the biennial conference of the NAFIPS. Berkeley, CA, pp 263–267

Pei J, Han J, Lakshmanan LVS (2001) Mining frequent itemsets with convertible constraints. In: Proceedings of the 17th international conference on data engineering. Heidelberg, Germany, pp 433–442

Prade H (1988) Raisonner avec des règles d'inférence graduelle - Une approche basée sur les ensembles flous. Revue d'Intelligence Artificielle 2(2):29–44

Ruspini EH (1969) A new approach to clustering. Inf Contr 15:22–32MATHCrossRef

Savasere A, Omiecinski E, Navathe S (1995) An efficient algorithm for mining association rules in large databases. In: VLDB–95, Proceedings of 21th international conference on very large data bases. Zurich, pp 11–15.

Schweizer B, Sklar A (1983) Probabilistic metric spaces. North-Holland, New York

Shu-Yue J, Tsang E, Yengg D, Daming S (2000) Mining fuzzy association rules with weighted items. In: Proceedings of the IEEE international conference on systems, man, and cybernetics. Nashville, TN, pp 1906–1911

Srikant R, Agrawal R (1995) Mining generalized association rules. In: Proceedings of the international conference on very large databases. Zurich, Switzerland, pp 407–419

Srikant R, Agrawal R (1996) Mining quantitative association rules in large relational tables. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 1–12

Srikant R, Vu Q, Agrawal R (1997) Mining association rules with item constraints. In: Proceedings of the 3rd international conference on knowledge discovery in databases and data mining. Newport Beach, California, pp 67–73

Steinbach M, Tan PN, Kumar V (2004) Support envelopes: A technique for exploring the structure of association patterns. In: Proceedings of the 10th ACM SIGKDD conference. Seattle, WA

Strauss O, Comby F, Aldon MJ (2000) Rough histograms for robust statistics. In: ICPR-2000, 15th International conference on pattern recognition. Barcelona, pp 2684–2687

Stumme G, Taouil R, Bastide Y, Pasquier N, Lakhal L (2001) Intelligent structuring and reducing of association rules with formal concept analysis. In: Proceedings of the 24th German conference on artificial intelligence, vol 2174 of LNCS. Springer-Verlag

Sudkamp T (2005) Examples, counterexamples, and measuring fuzzy associations. Fuzzy Sets Syst 149(1)

Tan P, Kumar V, Srivastava J (2002) Selecting the right interestingness measure for association patterns. In: Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining. ACM Press, pp 32–41

Tao F, Murtagh F, Farid M (2003) Weighted association rule mining using weighted support and significance framework. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining. Washington, DC, pp 661–666

Uno T, Kiyomi M, Arimura H (2004) LCM ver. 2: Efficient mining algorithms for frequent/closed/maximal itemsets. In Goethals B, Zaki MJ (eds) Proceedings of the IEEE ICDM workshop on frequent itemset mining implementations. Brighton, UK

Wong C, Shiu S, Pal SK (2001) Mining fuzzy association rules for web access case adaptation. In: Shiu S, Pal SK, Dillon TS (eds) ICCBR-workshop on soft computing in case-based reasoning. Vancouver

Xu B, Lu J, Zhang Y, Xu L, Chen H, Yang H (2003) Parallel algorithm for mining fuzzy association rules. In: international conference on Cyberworlds. Singapore

Yager RR (1979) On the measure of fuzziness and negation-part I: Membership in the unit interval. Int J Gen Syst 5:221–229MATHCrossRefMathSciNet

Yahia SB, Jaoua A (2000) A top-down approach for mining fuzzy association rules. In: Proceedings of the 8th international conference on information processing and management of uncertainty in knowledge-based systems. Madrid, pp 952–959

Yahia SB, Jaoua A (2001) Discovering knowledge from fuzzy concept lattice. In: Kandel A, Last M, Bunke H (eds) Data mining and computational intelligence, vol 68 of Studies in Fuzziness and Soft Computing. Physica-Verlag, pp 167–190

Yang Y, Singhal M (1999) Fuzzy functional dependencies and fuzzy association rules. In: Data warehousing and knowledge discovery, proceedings DAWAK-99. Springer-Verlag, pp 229–240

Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353MATHCrossRefMathSciNet

Zaki M, Hsiao CJ (2005) Efficient algorithms for mining closed itemsets and their lattice structure. IEEE Trans Knowl Data Eng 17(4):462–478CrossRef

Zaki MJ (2000) Scalable algorithms for association mining. IEEE Trans Knowl Data Eng 12(3):372–390CrossRefMathSciNet

Zaki MJ, Parthasarathy S, Ogihara M, Li W (1997) New algorithms for fast discovery of association rules. Technical Report 651, Computer Science Department, University of Rochester, Rochester, NY 14627

Zhang W (1999) Mining fuzzy quantitative association rules. In: Proceedings of the 11th IEEE international conference on tools with artificial intelligence, Chicago, Illinois

Titel: A systematic approach to the assessment of fuzzy association rules
verfasst von: Didier Dubois
Eyke Hüllermeier
Henri Prade
Publikationsdatum: 01.09.2006
Verlag: Springer US
Erschienen in: Data Mining and Knowledge Discovery / Ausgabe 2/2006
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-005-0032-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2006

Mining top-K frequent itemsets from data streams

A Model-Based Frequency Constraint for Mining Associations from Transaction Data

VizRank: Data Visualization Guided by Machine Learning

Hyperclique pattern discovery

Support measures for graph data*

Premium Partner