CHIRA-Convex Hull Based Iterative Algorithm of Rules Aggregation

• Autorzy: Sikora M. , Gudyś A.
• Języki publikacji: EN

Abstrakty

EN

In the paper we present CHIRA, an algorithm performing decision rules aggregation. New elementary conditions, which are linear combinations of attributes may appear in rule premises during the aggregation, leading to so-called oblique rules. The algorithm merges rules iteratively, in pairs, according to a certain order specified in advance. It applies the procedure of determining convex hulls for regions in a feature space which are covered by aggregated rules. CHIRA can be treated as the generalization of rule shortening and joining algorithms which, unlike them, allows a rule representation language to be changed. Application of presented algorithm allows one to decrease a number of rules, especially in the case of data in which decision classes are separated by hyperplanes not perpendicular to the attribute axes. Efficiency of CHIRA has been verified on rules obtained by two known rule induction algorithms, RIPPER and q-ModLEM, run on 18 benchmark data sets. Additionally, the algorithm has been applied on synthetic data as well as on a real-life set concerning classification of natural hazards in hard-coal mines.

Słowa kluczowe

EN

decision rules; rule aggregation; oblique rules; convex hull

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 2
• Strony: 143--170
• Opis fizyczny: Bibliogr. 53 poz., tab., wykr.

Twórcy

autor

Sikora M.

• Institute of Informatics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland Institute of Innovative Technologies EMAG, Leopolda 31, 40-189 Katowice, Poland

autor

Gudyś A.

• Institute of Informatics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland

Bibliografia

• [1] Agotnes, T., Komorowski, J., Løken, T.: Taming large rule models in rough set approaches, Proc. of the Third European Conference on Principles of Data Mining and Knowledge Discovery, LNAI 1704, Springer-Verlag, London, 1999, 193–203.
• [2] Agrawal, R., Srikant, R.: Fast Algorithms for Mining Association Rules in Large Databases, Proc. of the 20th Int. Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994, 487–499.
• [3] An, A., Cercone, N.:Rule quality measures for rule induction systems – description and evaluation, Computational Intelligence, 17(3), 2001, 409–424.
• [4] Barber, C.B., Dobkin, D.P., Huh, H.:The Quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, 22(4), 1996, 469–483.
• [5] Bazan, J., Szczuka, M., Wróblewski, J.: A new version of rough set exploration system, Proc. of the Third International Conference on Rough Sets and Current Trends in Computing, LNCS 2475, Springer-Verlag, London, 2002, 397–404.
• [6] Bennet, K.P., Blue, J.A: A support vector machine approach to decision trees, Proc. of the IEEE International Joint Conference on Neural Networks, IEEE Press, Anchorage, AK , USA, 1998, 2396–2401.
• [7] Bloedorn, E., Michalski, R.S.: Data-Driven Constructive Induction, IEEE Intelligent Systems, 13(2), 1998, 30–37.
• [8] Bruha, I.: Quality of Decision Rules: Definitions and Classification Schemes for Multiple Rules, in: Machine Learning and Statistics, The Interface (G. Nakhaeizadeh, C.C. Taylor, Eds.), John Wiley and Sons, 1997, 107–131.
• [9] Cantu–Paz, E., Kamath, Ch.: Inducing Oblique Decision Trees with Evolutionary Algorithms, IEEE Transaction on Evolutionary Computetion, 7(1), 2003, 54–68.
• [10] Clark, P., Niblett, T.: The CN2 induction algorithm, Machine Learning, 3(4), 1989, 261–283.
• [11] Cohen,W.W.: Fast effective rule induction, Proc. of the Twelfth International Conference on Machine Learning, Morgan Kaufmann Pub., California, USA, 1995, 115–123.
• [12] Dembczyński, K., Kotłowski, W., Słowiński, R.: ENDER a statistical framework for boosting decision rules, Data Mining and Knowledge Discovery, 21(1), 2010, 52–90.
• [13] Duch, W., Adamczak, R., Grabczewski, K.: A New methodology of extraction, optimization and application of crisp and fuzzy logical rules, IEEE Transaction on Neural Networks, 11(2), 2000, 1–31.
• [14] Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R.: From data mining to knowledge discovery, in: Advances in knowledge discovery and data mining (U.M.. Fayyad, G. Piatetsky-Shapiro, et al. Eds.), Cambridge, MIT-Press, 1996, 37–58.
• [15] Ferguson, D.E.: Fibonaccian searching, Communications of the ACM, 3(12), 1960.
• [16] Fürnkranz, J.: Separate-and-conquer rule learning, Artificial Intelligence Review, 13(1), 1999, 3–54.
• [17] Fürnkranz, J., Flach, P.A.: ROC ’n’ Rule Learning - Towards a Better Understanding of Covering Algorithms, Machine Learning, 58(1), 2005, 39–77.
• [18] Greco, S., Matarazzo, B., Słowiński, R.: Rough sets theory for multi-criteria decision analysis, European Journal of Operational Research, 129(1), 2001, 1–47.
• [19] Grzymała-Busse, J.W., Ziarko, W.: Data mining based on rough sets, in: Data Mining Opportunities and Challenges (J. Wang Ed.), IGI Publishing, Hershey, PA, USA, 2003, 142–173.
• [20] Góra, G., Wojna, A.G.: RIONA: a new classification system combining rule induction and instance-based learning, Fundamenta Informaticae, 51(4), 2002, 369–390.
• [21] Janssen, F., Fürnkranz, J.: On the quest for optimal rule learning heuristics, Machine Learning, 78(3), 2010, 343–379.
• [22] Kim, H., Loh, W.Y.: Classification trees with bivariate linear discriminant node models, Journal of Computational and Graphical Statistics, 12, 2003, 512–530.
• [23] Kavsek, B., Lavrac, N.: APRIORI-SD: Adapting association rule learning to subgroup discovery, Applied Artificial Intelligence, 20, 2006, 543–583.
• [24] Latkowski, R., Mikołajczyk, M.: Data decomposition and decision rule joining for classification of data with missing values, Transaction on Rough Sets I, LNCS 3100, Springer-Verlag, Berlin Heidelberg, 2004, 299–320.
• [25] Lavrac, N., Kavsek, B., Flach, P.: Subgroup discovery with CN2-SD, Journal of Machine Learning Research, 5, 2004, 153–188.
• [26] Michalski, R.S., Mozetic, I., Hong, J., Lavrac, N.: The AQ15 inductive learning system: An overview and experiments, ISG Report No. 20. Department of Computer Sciences, University of Illinois at Urbana-Champaign, 1986.
• [27] Michalski, R.S., Bratko, I., Kubat, M.: Machine learning and data mining, John Wiley and Sons, 1998.
• [28] Mikolajczyk, M.: Reducing number of decision rules by joining, Proc. of the Third International Conference on Rough Sets and Current Trends in Computing, LNAI 2475, Springer-Verlag, Berlin Heidelberg, 2002, 425–432.
• [29] Murthy, S.K., Kasif, S., Salzberg, S.A.: A system for induction of oblique decision trees, Journal of Artificial Intelligence Research, 2(1), 1994, 1–32.
• [30] Nguyen, H. S., Nguyen, S. H.: Some efficient algorithms for rough set methods, Proc. of the Sixth Int. Conference, Information Processing and Management of Uncertainty in Knowledge Based System, Granada, Spain, 1996, 1451–1456.
• [31] Orlau, C., Wehenkel, L.: A complete fuzzy decision tree technique, Fuzzy Sets and Systems, 138(2), 2003, 221–254.
• [32] Pawlak, Z.: Rough sets: Theoretical aspects of reasoning about data, Dordrecht, Kluwer, 1991.
• [33] Pindur, R., Sasmuga, R., Stefanowski, J.: Hyperplane Aggregation of Dominance Decision Rules, Fundamenta Informaticae, 61(2), 2004, 117–137.
• [34] Raś, Z.W., Daradzińska, A., Liu, X.: System ADReD for discovering rules based on hyperplanes, Engineering Applications of Artificial Intelligence, 17(4), 2004, 401–406.
• [35] Sikora, M.: Rules evaluation and generalization for decision classes descriptions improvement, Doctoral Thesis, Silesian University of Technology, April 2002.
• [36] Sikora, M.: An algorithm for generalization of decision rules by joining, Foundations of Computing and Decision Sciences, 30(3), 2005, 227–239.
• [37] Sikora, M.: Rule quality measures in creation and reduction of data rules models, Proc. of the 5th international conference on Rough Sets and Current Trends in Computing, LNAI 4259, Springer-Verlag, Berlin Heidelberg, 2006, 716–725.
• [38] Sikora, M.: Decision rules based data models using TRS and NetTRS - methods and algorithms, Transaction on Rough Sets XI, LNCS 5946, Springer-Verlag, Berlin Heidelberg, 2010, 130–160.
• [39] Sikora, M., Krzystanek, Z., Bojko, B., ´Spiechowicz, K.: Application of hybrid machine learning method for description and on-line assessment of methane hazards in a mine excavation, Journal of Mining Sciences, 47(4), 2011, 493–505.
• [40] Sikora, M., Gruca, A.: Induction and selection of the most interesting Gene Ontology based multiattribute rules for descriptions of gene groups, Pattern Recognition Letters, 32(2), 2011, 258–269.
• [41] Sikora, M.: Induction and pruning of classification rules for prediction of microseismic hazards in coal mines, Expert Systems with Applications, 38(6), 2011, 6748–6758.
• [42] Sikora, M., Wróbel, L.: Data-driven adaptive selection of rules quality measures for improving the rules induction algorithm, Proc. of the Thirteenth International Conference on Rough Sets, Fuzzy Sets and Granular Computing, LNCS 6743, Springer-Verlag, Berlin Heidelberg, 2011, 278–285.
• [43] Skowron, A., Rauszer, C.: The Discernibility Matrices and Functions in Information systems, in: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory (R. Słowiński Ed.), Dordrecht, Kluwer, 1992, 331–362.
• [44] Skowron, A., Wang, H., Wojna, A., Bazan, J.G.: A Hierarchical Approach to Multimodal Classification, Proc. of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, LNAI 3642, Springer-Verlag, Berlin Heidelberg, 2005, 119–127.
• [45] Stefanowski, J.: Rough set based rule induction techniques for classification problems, Proc. of the 6th European Congress of Intelligent Techniques and Soft Computing, Aachen, Germany, 1998, 107–119.
• [46] Stefanowski, J., Vanderpooten, D.: Induction of Decision Rules in Classification and Discovery-Oriented Perspectives, International Journal of Intelligent Systems, 16(1), 2001, 13–27.
• [47] Stefanowski, J.: The Bagging and n2-Classifiers Based on Rules Induced by MODLEM, Proc. of the 4th International Conference on Rough Sets and Current Trends in Computing, LNCS 3066, Springer-Verlag, Berlin Heidelberg, 2004, 488–497.
• [48] Ślezak , D., Wróblewski, J.: Classification Algorithms Based on Linear Combinations of Features, Proc. Of the Third European Conference Principles of Data Mining and Knowledge Discovery, LNCS 1704, Springer-Verlag, Berlin Heidelberg, 1999, 548–553.
• [49] Wang, H., Nguyen, H.S.: Text classification using Lattice Machine, Lecture Notes in Computer Sciences 1609, 1999, 235–243.
• [50] Wang, H., Düntsch, I., Gediga, G., Skowron, A: Hypperrelations in version space, International Journal of Approximate Reasoning, 36(3), 2004, 223–241.
• [51] Webb, G.I.: Further experimental evidence against the utility of Occam‘s razor, Journal of Artificial Intelligence Research, 4(1), 1996, 397–417.
• [52] Witten, I.H., Frank, E.: Data mining: practical machine learning tools and techniques, Morgan Kaufmann 2005.
• [53] Wolpert, D.H.: The lack of a priori distinctions between learning algorithms, Neural Computations, 8(7), 1996, 1341–1390.