Learning of Rule Ensembles for Multiple Attribute Ranking Problems
Inhaltsverzeichnis
Reference
Krzysztof Dembczyński, Wojciech Kotłowski, Roman Słowiński, Marcin Szeląg: Learning of Rule Ensembles for Multiple Attribute Ranking Problems. In: Fürnkranz, J. and Hüllermeier, E.: Preference Learning, 2011, 217-247.
DOI
http://dx.doi.org/10.1007/978-3-642-14125-6_11
Abstract
In this paper, we consider the multiple attribute ranking problem from a Machine Learning perspective. We propose two approaches to statistical learning of an ensemble of decision rules from decision examples provided by the Decision Maker in terms of pairwise comparisons of some objects. The first approach consists in learning a preference function defining a binary preference relation for a pair of objects. The result of application of this function on all pairs of objects to be ranked is then exploited using the Net Flow Score procedure, giving a linear ranking of objects. The second approach consists in learning a utility function for single objects. The utility function also gives a linear ranking of objects. In both approaches, the learning is based on the boosting technique. The presented approaches to Preference Learning share good properties of the decision rule preference model and have good performance in the massive-data learning problems. As Preference Learning and Multiple Attribute Decision Aiding share many concepts and methodological issues, in the introduction, we review some aspects bridging these two fields. To illustrate the two approaches proposed in this paper, we solve with them a toy example concerning the ranking of a set of cars evaluated by multiple attributes. Then, we perform a large data experiment on real data sets. The first data set concerns credit rating. Since recent research in the field of Preference Learning is motivated by the increasing role of modeling preferences in recommender systems and information retrieval, we chose two other massive data sets from this area – one comes from movie recommender system MovieLens, and the other concerns ranking of text documents from 20 Newsgroups data set.
Extended Abstract
Bibtex
@incollection{
year={2011},
isbn={978-3-642-14124-9},
booktitle={Preference Learning},
editor={Fürnkranz, Johannes and Hüllermeier, Eyke},
doi={10.1007/978-3-642-14125-6_11},
title={Learning of Rule Ensembles for Multiple Attribute Ranking Problems},
url={http://dx.doi.org/10.1007/978-3-642-14125-6_11, http://de.evo-art.org/index.php?title=Learning_of_Rule_Ensembles_for_Multiple_Attribute_Ranking_Problems },
publisher={Springer Berlin Heidelberg},
author={Dembczyński, Krzysztof and Kotłowski, Wojciech and Słowiński, Roman and Szeląg, Marcin},
pages={217-247},
language={English}
}
Used References
1. http://people.csail.mit.edu/jrennie/20Newsgroups/20news-18828.tar.gz
2. D. Bouyssou, Ranking methods based on valued preference relations: A characterization of the net flow method. Eur. J. Oper. Res. 60, 61–67 (1992) http://dx.doi.org/10.1016/0377-2217(92)90333-5
3. D. Bouyssou, T. Marchant, M. Pirlot, P. Perny, A. Tsoukiás, P. Vincke (eds.), Evaluation and Decision Models: A critical perspective, Chap.6.1 (Kluwer, 2000), pp. 91–101
4. D. Bouyssou, P. Vincke, Ranking alternatives on the basis of preference relations: A progress report with special emphasis on outranking relations. J. Multi-Crit. Dec. Anal. 6, 77–85 (1997) http://dx.doi.org/10.1002/(SICI)1099-1360(199703)6%3A2%3C77%3A%3AAID-MCDA144%3E3.0.CO%3B2-I
5. W.W. Cohen, Y. Singer, A simple, fast, and effective rule learner, in Proceedings of National Conference on Artificial Intelligence (AAAI 1999)(AAAI/MIT, Orlando, USA, 1999), pp. 335–342
6. K. Dembczyński, S. Greco, W. Kotłowski, R. Słowiński, Statistical model for rough set approach to multicriteria classification, in Knowledge Discovery in Databases (PKDD 2007), vol. 4702 Lecture Notes in Artificial Intelligence, ed. by J.N. Kok, J. Koronacki, R.L. de Mántaras, S. Matwin, D. Mladenič, A. Skowron (Springer, Warsaw, Poland, 2007), pp. 164–175
7. K. Dembczyński, S. Greco, R. Słowiński, Rough set approach to multiple criteria classification with imprecise evaluations and assignments. Eur. J. Oper. Res. 198(2), 626–636 (2009) http://dx.doi.org/10.1016/j.ejor.2008.09.033
8. K. Dembczyński, W. Kotłowski, R. Słowiński, Ensemble of decision rules for ordinal classification with monotonicity constraints, in Rough Sets and Knowledge Technology 2008 (RSKT 2008), vol.5009, Lecture Notes in Artificial Intelligence, ed. by G. Wang, T. Li, J.W. Grzymała-Busse, D. Miao, A. Skowron, Y. Yao (Springer, Chengdu, China, 2008), pp. 260–267
9. K. Dembczyński, W. Kotłowski, R. Słowiński, A general framework for learning an ensemble of decision rules, in Proceedings of the LeGo ’08: From Local Patterns to Global Models, ECML/PKDD 2008 Workshop, ed. by J. Fürnkranz, A. Knobbe (Antwerp, Belgium, 2008), pp. 17–36
10. K. Dembczyński, W. Kotłowski, R. Słowiński, Ordinal classification with decision rules, in Mining Complex Data (MCD 2007), vol.4944, Lecture Notes in Artificial Intelligence, ed. by Z.W. Raś, S. Tsumoto, D. Zighed (Springer, 2008), pp. 169–181
11. M. Doumpos, F. Pasiouras, Developing and testing models for replicating credit ratings: A multicriteria approach. Comput. Econ. 25, 327–341 (2005) http://dx.doi.org/10.1007/s10614-005-6412-4
12. J. Figueira, S. Greco, M. Ehrgott (eds.), Multiple Criteria Decision Analysis: State of the Art Surveys(Springer, Berlin, 2005)
13. J. Figueira, S. Greco, R. Słowiński, Building a set of additive value functions representing a reference preorder and intensities of preference: Grip method. Eur. J. Oper. Res. 195(2), 460–486 (2009) http://dx.doi.org/10.1016/j.ejor.2008.02.006
14. P. Fortemps, S. Greco, R. Słowiński, Multicriteria decision support using rules that represent rough-graded preference relations. Eur. J. Oper. Res. 188(1), 206–223 (2008) http://dx.doi.org/10.1016/j.ejor.2007.03.036
15. E. Frank, M. Hall, A simple approach to ordinal classification. in Proceedings of the European Conference on Machine Learning (ECML 2001), vol. 2167, Lecture Notes in Artificial Intelligence, ed. by L. De Raedt, P.A. Flach (Springer, Freiburg, Germany, 2001), pp. 145–157
16. Y. Freund, R. Iyer, R.E. Schapire, Y. Singer, An efficient boosting algorithm for combining preferences. J. Mach. Learn. Res. 6(4), 933–969 (2003)
17. Y. Freund, R.E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55(1), 119–139 (1997) http://dx.doi.org/10.1006/jcss.1997.1504
18. J.H. Friedman, B.E. Popescu, Importance sampled learning ensembles. Research report, Department of Statistics, Stanford University, 2003
19. J. Fürnkranz, E. Hüllermeier, Pairwise preference learning and ranking, in Proceedings of the European Conference on Machine Learning (ECML 2003), vol.2837 Lecture Notes in Artificial Intelligence, ed. by N. Lavrac, D. Gamberger, L. Todorovski, H. Blockeel (Springer, Cavtat-Dubrovnik, Croatia, 2003), pp. 145–156
20. S. Giove, S. Greco, B. Matarazzo, R. Słowiński, Variable consistency monotonic decision trees, in Rough Sets and Current Trends in Computing (RSCTC 2002), vol.2475 Lecture Notes in Artificial Intelligence, ed. by J.J. Alpigini, J.F. Peters, A. Skowron, N. Zhong (Springer, Malvern, USA, 2002), pp. 247–254
21. S. Greco, B. Matarazzo, R. Słowiński, A new rough set approach to evaluation of bankruptcy risk, in Operational Tools in the Management of Financial Risks, ed. by C. Zopounidis (Kluwer, Dordrecht, 1998), pp. 121–136 http://dx.doi.org/10.1007/978-1-4615-5495-0_8
22. S. Greco, B. Matarazzo, R. Słowiński, Rough approximation of a preference relation by dominance relations. Eur. J. Oper. Res. 117, 63–83 (1999) http://dx.doi.org/10.1016/S0377-2217(98)00127-1
23. S. Greco, B. Matarazzo, R. Słowiński, Dealing with missing data in rough set analysis of multi-attribute and multi-criteria decision problems, in Decision Making: Recent Developments and Worldwide Applications, ed. by S.H. Zanakis, G. Doukidis, C. Zopounidis (Kluwer, Dordrecht, 2000), pp. 295–316
24. S. Greco, B. Matarazzo, R. Słowiński, Rough sets theory for multicriteria decision analysis. Eur. J. Oper. Res. 129, 1–47 (2001) http://dx.doi.org/10.1016/S0377-2217(00)00167-3
25. S. Greco, B. Matarazzo, R. Słowiński, Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules. Eur. J. Oper. Res. 158(2), 271–292 (2004) http://dx.doi.org/10.1016/j.ejor.2003.06.004
26. S. Greco, B. Matarazzo, R. Słowiński, Decision rule approach, in Multiple Criteria Decision Analysis: State of the Art Surveys, Chap.13, ed. by J. Figueira, S. Greco, M. Ehrgott (Springer, Berlin, 2005), pp. 507–561
27. S. Greco, B. Matarazzo, R. Słowiński, Preference representation by means of conjoint measurement and decision rule model, in Aiding Decisions with Multiple Criteria - Essays in Honor of Bernard Roy, ed. by D. Bouyssou, E. Jacquet-Lagrèze, P. Perny, R. Słowiński, D. Vanderpooten, P. Vincke (Kluwer, Boston, 2005), pp. 263–313
28. S. Greco, B. Matarazzo, R. Słowiński, Dominance-based rough set approach to interactive multiobjective optimization, in Multiobjective Optimization: Interactive and Evolutionary Approaches, Chap.5, ed. by J. Branke, K. Deb, K. Miettinen, R. Słowiński (Springer, Berlin, 2008), pp. 121–156
29. S. Greco, B. Matarazzo, R. Słowiński, Granular computing for reasoning about ordered data: the dominance-based rough set approach, in Handbook of Granular Computing, Chap.15, ed. by W. Pedrycz, A. Skowron, V. Kreinovich (Wiley, Chichester, 2008), pp. 347–373
30. S. Greco, B. Matarazzo, R. Słowiński, Dominance-based rough set approach to decision under uncertainty and time preference. Ann. Oper. Res. (2009). http://dx.doi.org/10.1007/s10479-009-0566-8
31. S. Greco, V. Mousseau, R. Słowiński, Ordinal regression revisited: multiple criteria ranking using a set of additive value functions. Eur. J. Oper. Res. 191(2), 415–435 (2008) http://dx.doi.org/10.1016/j.ejor.2007.08.013
32. S. Greco, R. Słowiński, J. Figueira, V. Mousseau, Robust ordinal regression, in New Advances in Multiple Criteria Decision Analysis, ed. by M. Ehrgott, J. Figueira, S. Greco, (Springer, Berlin, 2009)
33. http://www.grouplens.org/node/73.
34. T. Hastie, R. Tibshirani, J.H. Friedman, Elements of Statistical Learning: Data Mining, Inference, and Prediction(Springer, Berlin, 2003)
35. R. Herbrich, T. Graepel, K. Obermayer, Regression models for ordinal data: A machine learning approach. Technical report TR-99/03, TU Berlin, 1999
36. E. Jacquet-Lagrèze, Y. Siskos, Assessing a set of additive utility functions for multicriteria decision making: The UTA method. Eur. J. Oper. Res. 10, 151–164 (1982) http://dx.doi.org/10.1016/0377-2217(82)90155-2
37. T. Joachims, Optimizing search engines using clickthrough data, in Proceedings of the International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD 2002)(ACM, Alberta, Canada, 2002), pp. 133–142
38. W. Kotłowski, K. Dembczyński, S. Greco, R. Słowiński, Stochastic dominance-based rough set model for ordinal classification. Inf. Sci. 178(21), 4019–4037 (2008) http://dx.doi.org/10.1016/j.ins.2008.06.013
39. K. Lang, Learning to filter netnews, in Proceedings of the International Conference on Machine Learning (ICML 1995), ed. by A. Prieditis, Stuart J. Russell (Morgan Kaufmann, Tahoe City, USA, 1995), pp. 331–339
40. P. Langley, H.A. Simon, Fielded applications of machine learning, in Machine Learning and Data Mining, ed. by Ryszard S. Michalski, I. Bratko, M. Kubat (Wiley, New York, 1998), pp. 113–129
41. J.G. March, Bounded rationality, ambiguity, and the engineering of choice, in Decision Making, Descriptive, Normative and Prescriptive Interactions, ed. by David E. Bell, H. Raiffa, A. Tversky (Cambridge University Press, New York, 1988), pp. 33–58 http://dx.doi.org/10.1017/CBO9780511598951.004
42. R.S. Michalski, A theory and methodology of inductive learning, in Machine Learning: An Artificial Intelligence Approach, ed. by R.S. Michalski, J.G. Carbonell, T.M. Mitchell (Tioga Publishing, Palo Alto, 1983), pp. 83–129
43. V. Mousseau, R. Słowiński, Inferring an ELECTRE TRI model from assignment examples. J. Global Optim. 12(2), 157–174 (1998) http://dx.doi.org/10.1023/A%3A1008210427517
44. http://www.netflixprize.com
45. Z. Pawlak, Rough Sets. Theoretical Aspects of Reasoning about Data(Kluwer, Dordrecht, 1991)
46. Z. Pawlak, R. Słowiński, Rough set approach to multi-attribute decision analysis. Eur. J. Oper. Res. 4(3), 443–459 (1994) http://dx.doi.org/10.1016/0377-2217(94)90415-4
47. J. Rennie, N. Srebro, Loss functions for preference levels: Regression with discrete ordered labels, in Proceedings of the IJCAI Multidisciplinary Workshop on Advances in Preference Handling(Edinburgh, Scotland, 2005)
48. B. Roy, Méthodologie Multicritère d’Aide à la Décision(Economica, Paris, 1985)
49. B. Roy, D. Bouyssou, Aide Multicritère à la Décision: Méthodes et Cas(Economica, Paris, 1993)MATH
50. P.J.H. Shoemaker, The expected utility model: its variants, purposes, evidence and limitations. J. Econ. Lit. 20, 529–562 (1982)
51. R. Słowiński, Rough set learning of preferential attitude in multi-criteria decision making, in Methodologies for Intelligent Systems, vol. 689, Lecture Notes in Artificial Intelligence, ed. by J. Komorowski, Z. Raś (Springer, Berlin, 1993), pp. 642–651
52. R. Słowiński, S. Greco, B. Matarazzo, Axiomatization of utility, outranking and decision-rule preference models for multiple-criteria classification problems under partial inconsistency with the dominance principle. Control Cybern. 31(4), 1005–1035 (2002)
53. R. Słowiński, S. Greco, B. Matarazzo, Mining decision-rule preference model from rough approximation of preference relation, in Proceedings of the IEEE Annual International Conference on Computer Software and Applications (COMPSAC 2002)(Oxford, UK, 2002), pp. 1129–1134
54. R. Słowiński, S. Greco, B. Matarazzo, Rough set based decision support. in Introductory Tutorials on Optimization, Search and Decision Support Methodologies, Chap.16, ed. by E. Burke, G. Kendall (Springer, New York, 2005), pp. 457–524
55. N. Srebro, J. Rennie, T. Jaakkola, Maximum margin matrix factorizations, in Advances in Neural Information Processing Systems 17 (NIPS 2004)(MIT, 2005), pp. 1329–1336
56. V. Vapnik, Statistical Learning Theory, (Wiley-Interscience, 1998)
57. P. Vincke, Exploitation of a crisp relation in a ranking problem. Theory Decis. 32, 221–240 (1992) http://dx.doi.org/10.1007/BF00134150
58. I.H. Witten, E. Frank, Data Mining: Practical machine learning tools and techniques, (2nd edn.) (Morgan Kaufmann, San Francisco, 2005)
