Probabilistic Structure of Rough Set Flow Graphs

Abstract

The Rough Set Theory, one of the granular computing methods, was put forward by Zdzislaw Pawlak in the early 1980s to deal with uncertain and vague information. One of the main reasons for uncertainty is that the uncertainty stems from the difficulty of observing all the variables of the domain it relates to. Also, although the world to which the observable variables belong is deterministic, it shows random behavior. The rough set theory is based on the assumption that we can obtain information from every single object in the universe. Many studies have been conducted on the theory of rough sets in the period that passed since the theory was introduced. One of these is the flow charts presented by Pawlak, who introduced the theory in the early 2000s. Flow charts provide a graphical framework for reasoning from data and representing the distribution of information flow from data tables for intelligent data analysis. Pawlak explained the flow graphs from the concept proposed by Łukasiewicz that proposes to express probability in logical terms. Flow graphs can be viewed from a theoretical point of view as a generalization of the Łukasiewicz 'ideas. Flow graphs based on rough set theory overlap with other methods that deal with uncertain and incomplete information. One of these is Bayesian networks used as a semantic modeling tool to manage uncertainty in complex domains. The look at Bayes 'theorem presented by the rough set theory reveals that any data set meets the total probability rule and Bayes' theorem. Bayes' Theorem is a mathematical rule that explains how we should change our beliefs up to that point in the presence of new evidence. In other words, it ensures that new information is combined with already existing data and knowledge. Therefore, we can see flow graphs as a special case of Bayesian networks. In addition, flow graphs extend the traditional rough set research by organizing the rules derived from decision tables into Directed Acyclic Graphs (DAGs). Pawlak's flow graphs have attracted the attention of many practical and theoretical researchers due to their ability to visualize the flow of information and have been successfully applied in many areas In this study, basic concepts and properties of flow charts are examined; the relationship of flow graphs with Bayes' theorem and Bayes networks is shown. In addition, a wide literature research on flow charts has been made and the applications and theoretical studies in the related field are mentioned. In the last section of the paper, the decision algorithm on an application is expressed as a finite set of decision rules in the form of “If…Then…”. In addition, the meanings of these decision rules are expressed and evaluated with the strength, certainty and coverage coefficients that provide Bayes' theorem. It is seen here that each decision rules reveal probabilistic properties and meet Bayes' theorem and the total probability rule.

Keywords

• Flow Graph
• Rough Sets
• Bayes Theorem
• Bayesian Networks
• Uncertainty
• Decision Rules
• Decision Algorithms

Kaba Küme Akış Çizgelerinin Olasılıksal Yapısı

Öz

Tanecikli Hesaplama yöntemlerinden biri olan Kaba Kümeler Teorisi 1980’li yılların başlarında Zdzislaw Pawlak tarafından, belirsiz ve muğlak bilgi ile uğraşmak için ortaya atılmıştır. Belirsizliğin en temel nedenlerinden biri, belirsizliğin ilgili olduğu alanın tüm değişkenlerini gözlemlemenin güçlüğünden kaynaklanmasıdır. Ayrıca, gözlemlenebilen değişkenlerin ait oldukları dünya deterministik olmasına rağmen, rasgele davranış gösterir. Kaba kümeler teorisi evrende her bir nesneden bilgi elde edebileceğimiz varsayımı üzerine kuruludur. Teorinin ortaya atılmasından günümüze kadar geçen süre içerisinde kaba kümeler teorisi üzerinde birçok çalışma yapılmıştır. Bunlardan biri de, 2000’li yılların başlarında kuramı ortaya atan Pawlak tarafından, verilerden akıl yürütmek ve akıllı veri analizi için veri tablolarından bilgi akışı dağılımını temsil etmek amacıyla grafiksel bir çerçeve olarak sunulan akış çizgeleridir. Pawlak, akış çizgelerini Łukasiewicz tarafından önerilen olasılığı, mantıksal terimlerle ifade etmeyi öneren kavramdan yola çıkarak açıklamıştır. Akış çizgeleri teorik bakış açısından, Łukasiewicz ’in fikirlerinin bir genellemesi olarak görülebilir. Kaba küme teorisine dayalı akış çizgeleri, belirsiz ve eksik bilgiyle ilgilenen diğer yöntemler ile de örtüşmektedir. Bunlardan birisi de karmaşık alanlarda belirsizliği yönetmek için anlamsal bir modelleme aracı olarak kullanılan Bayes ağlarıdır. Kaba küme teorisi tarafından sunulan Bayes teoremine bakış, herhangi bir veri kümesinin toplam olasılık kuralı ve Bayes teoremini karşıladığını ortaya koymaktadır. Bayes teoremi, yeni bir kanıtın varlığında o ana kadar olan inançlarımızı nasıl değiştirmemiz gerektiğini açıklayan matematiksel bir kuraldır. Diğer bir deyişle, yeni bilgiler ile hali hazırda bulunan verilerin ve bilgilerin birleştirilmesini sağlar. Bu nedenle, akış çizgelerini Bayes ağlarının özel bir durumu olarak görebiliriz. Ayrıca, akış çizgeleri, karar tablolarından elde edilen kuralları Yönlendirilmiş Çevrimsiz Çizge (YDÇ) olarak düzenleyerek geleneksel kaba küme araştırmasını genişletir. Pawlak’ın akış çizgeleri, bilgi akışını görselleştirme yetenekleri nedeniyle hem pratik hem de teorik birçok araştırmacının ilgisini çekmiş ve birçok alanda başarı ile uygulanmıştır. Bu çalışmada, akış çizgelerinin temel kavramları ve özellikleri incelenmiş ve Bayes teoremi ve Bayes ağları ile akış çizgelerinin ilişkisi gösterilmiştir. Ayrıca, akış çizgeleri ile ilgili geniş bir literatür araştırması yapılmış ve uygulamada ve teorik yapılan çalışmalara değinilmiştir. Son bölümde, bir uygulama üzerinde, karar algoritması, sonlu bir “Eğer….O halde….” şeklinde karar kuralları kümesi olarak ifade edilmiştir. Ayrıca, bu karar kurallarının taşıdığı anlamlar Bayes teoremini sağlayan güç, kesinlik ve kapsama katsayıları ile ifade edilmiş ve değerlendirilmiştir. Burada her karar kurallarınıni olasılıksal özellikleri ortaya çıkardığı ve Bayes teoremi ile toplam olasılık kuralını karşıladığı görülmektedir.

Anahtar Kelimeler

• Akış Çizgeleri
• Kaba Kümeler
• Bayes Teoremi
• Bayes Ağları
• Belirsizlik
• Karar Kuralları
• Karar Algoritmaları

Kaynakça

1. Butz, C.J., Yan, W. & Yang, W., (2005). The Computational Complexity of Inference Using Rough Set Flow Graphs, Rough Sets Fuzzy Sets Data Mining and Granular Computing 2005, Lecture Notes in Artificial Intelligence, 3641, Springer Verlag, Berlin, 335 – 344.
2. Butz, C.J., Yan, W. & Yang, W., (2006). An Efficient Algorithms for Inference in Rough Set Flow Graphs, Transaction on Rough Sets V, Lecture Notes in Computer Science, 4100, Springer Verlag, Berlin, 102-122.
3. Chien, C.C. & Tsumoto, S., (2007). On Learning Decision Rules from Flow Graphs, In Proc. of North America Fuzzy Information Processing Society, 655 – 658.
4. Chitchoreon, D. & Pattaraintakorn, P., (2008a). Knowledge Discovery by Rough Sets Mathematical Flow Graphs and its Extension, In Proc. of the 26th IAESTED Int. Conf. on AI and Applications AIA’ 08, ACTA Press, 340 – 345.
5. Chitchoreon, D. & Pattaraintakorn, P., (2008b). Towards Theories of Fuzzy Sets and Rough Set to Flow Graphs, In Proc. of the 2008 IEEE World Congress on Computational Intelligence, Hong Kong, 1675 – 1682.
6. Chitchoreon, D. & Pattaraintakorn, P., (2010). Novel Matrix Forms of Rough Set Flow Graphs with Applicationsto Data Integration, Computers and Mathematics with Applications, 60, 2880-2897.
7. Cooper, G.F., (1990). The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks, Artificial Intelligence, Vol.42 (2-3), 393 – 405.
8. Czyzewski, A., & Kostek, B., (2004a). Musical Metadata Retrieval with Flow Graphs. In Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, Springer Verlag, Berlin, 3066, 691 – 698.

9. Ford, L.R. & Fulkerson, D.R., (1962). Flows in Networks, Princeton University Press. Princeton, New Jersey.
10. Greco, S., Pawlak, Z. & Slowinski, R., (2004). Can Bayesian Confirmation Measures be Useful for Rough Set Decision Rules?, Engineering Applications of Artificial Intelligence, 17, 345 – 361.
11. Grinstead, C.M. & Snell, J.L., (1997). Introduction to Probability, Second Revised Edition, American Mathematical Society.
12. Kaur, K., Ramanna, S. & Henry, C., (2016). Measuring the Nearness of Layered Flow Graphs Application to Content Based Image Retrieval, Intelligent Decision Technology, 10, 165 – 181.
13. Kostek, B. & Czyzewski, A., (2004b). Processing of Minimal Metadata Employing Pawlak’s Flow Graphs, In Transactions on Rough Sets I, Vol.3100, Lecture Notes in Computer Sciences, Springer Verlag, Berlin, 279 – 298.
14. Lisowski, K., & Czyzewski, A., (2015). Pawlak’s Flow Graph Extensions for Video Surveillance Systems, Federated Conf. on Computer Science and Information Systems, 81 – 87.
15. Matusiewicz, Z., & Pancerz, K., (2008). Rough Set Flow Graphs and max-* Fuzzy Relation Equations in State Prediction Problems, In Rough Sets and Current Trends in Computing in Lecture otes in Artificial Intelligence 5306, Springer Verlag, Berlin, 359 – 368.
16. Pal, S.K., & Chakraborty, D.B., (2017). Granular Flow Graph Adaptive Rule Generation and Tracking, IEEE Transactions on Cybernetics, vol.47, 4096 – 4107.
17. Pattaraintakorn, P., (2009). Entropy Measures of Flow Graphs with Applications to Decision Trees, In Rough Sets and Knowledge Technology, Lecture Notes in Computer Sciences, 5589, Springer Verlag, Berlin, 618 – 625.
18. Pattaraintakorn, P., Cercone, N. & Nauredomkul, K., (2006). Rule Learning: Ordinal Prediction based on Rough Set and Soft Computing, Applied Mathematics Letters, 19, 1300-1307.
19. Pawlak, Z., (1982). Rough Sets, Int. Journal of Computer and Information Sciences, 11 (5) , 341 – 356.
20. Pawlak, Z., (1991). Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer, Dordrecht.
21. Pawlak, Z., (2002a). The Rough Set View on Bayes’ Theorem, AFSS 2002, Lecture Notes in Artificial Intelligence, 2275, Springer Verlag, Berlin, 106 – 116.
22. Pawlak, Z., (2002b). Rough Sets, Decision Algorithms and Bayes’ Theorem, European Journal of Operational Research, 136, 181 – 189.
23. Pawlak, Z., (2002c). Rough Set Theory, Journal of Telecommunications and Information Technology, Vol.3, 7 – 10.
24. Pawlak, Z., (2003a). Flow Graphs and Decision Algorithms, The 9th Int. Conf. on RSDGrC 2003, Lecture Notes in Artificial Intelligence, 2639, Springer Verlag, Berlin, 1 – 10.
25. Pawlak, Z., (2003b). Probability, Truth and Flow Graph, Electronic Notes in Theoretical Computer Science, Vol.82 (4), 1 – 9.
26. Pawlak, Z., (2003c). Decision Algorithms and Flow Graphs: A Rough Set Approach, Journal of Telecommunications and Information Technology, 3, 98 – 101.
27. Pawlak, Z., (2004a). Flow Graphs - A New Paradigm for Data Mining and Knowledge Discovery, The Proc. of. 5th International Symposium on Knowledge and Systems Science, JAIST, 147-153.
28. Pawlak, Z., (2004b). Decision Rules and Flow Networks. European Journal of Operational Research, 154, 184 – 190.
29. Pawlak, Z., (2004c). Data Analysis and Flow Graphs, Journal of Telecommunications and Information Technology, Vol.3, 1 – 5.
30. Pawlak, Z., (2005a). Rough Sets and Flow Graphs, Int.Workshop on RSFDGrC, Lecture Notes in Artificial Intelligence, 3641, Springer Verlag, Berlin, 1 – 11.
31. Pawlak, Z., (2005b). Flow Graphs and Data Mining, Transactions on Rough Sets III, Lecture Notes in Computer Sciences, 3400, Springer Verlag, Berlin, 1 – 36.
32. Pawlak, Z., (2006). Decision Trees and Flow Graphs, , In Rough Sets and Current Trends in Computing, Lecture Notes in Artificial Intelligence, 4259, Springer Verlag, Berlin, 268 – 277.
33. Rolka, M. A., & Rolka, L., (2006). Flow Graph and Decision Tables with Fuzzy Attributes, In Proc. of the 8th Int. Conf. AI and Soft Computing, Zakopone, Lecture Notes in Artificial Intelligence, 4029, Springer Verlag, Berlin, 268 – 277.
34. Skowron, A. & Stepaniuk, J., (1996). Tolerance Approximation Spaces, Fundamenta Informaticae, 27, 245 – 253.
35. Sun, J., Liu, H. &Zhang, H., (2006). An Extension of Pawlak’s Flow Graphs, In Proc. of the 1st Int. Conf. on Rough Sets and Knowledge Technology, 1191 – 199.
36. Sun, J., Liu, H., Qi, C. & Zhang, H., (2008). Interpretation of Extended Pawlak’s Flow Graphs Using Granular Computing, In Transaction Rough Sets VIII, Lecture Notes in Computer Sciences, 5084, Springer Verlag, 93 – 115.
37. Suraj, Z., & Pancerz, K., (2007). Flow Graphs as a Tool for Mining Prediction Rule of Changes of Components, In Temporal Information Systems, Rough Sets and Knowledge Technology, Lecture Notes in Artificial Intelligence, 2475, Springer Verlag, Berlin, 468 – 475.
38. Takacs, P., & Csajbok, Z.E., (2017). On the Connection of Flow Graphs and Contingency Tables, The 10th Int. Conf. on Applied Informatics, 295 – 302.
39. Wong, S.K.M., Butz, C.J. & Wu, D., (2000). On the Implication Problem for Probabilistic Conditional Independency, IEEE Transactions on Systems, Man and Cybernetics, Vol.30 (6), 785 – 805.