Computationally efficient sup-t transitive closure for sparse fuzzy binary relations

[journal]

Full reference

M. Wallace, Y. Avrithis and S. Kollias, Computationally efficient sup-t transitive closure for sparse fuzzy binary relations, Fuzzy Sets and Systems 157(3), pp. 341-372, 2006

Abstract

The property of transitivity is one of the most important for fuzzy binary relations, especially in the cases when they are used for the representation of real life similarity or ordering information. As far as the algorithmic part of the actual calculation of the transitive closure of such relations is concerned, works in the literature mainly focus on crisp symmetric relations, paying little attention to the case of general fuzzy binary relations. Most works that deal with the algorithmic part of the transitive closure of fuzzy relations only focus on the case of max-min transitivity, disregarding other types of transitivity. In this paper, after formalizing the notion of sparseness and providing a representation model for sparse relations that displays both computational and storage merits, we propose an algorithm for the incremental update of fuzzy sup-t transitive relations. The incremental transitive update (ITU) algorithm achieves the re-establishment of transitivity when an already transitive relation is only locally disturbed. Based on this algorithm, we propose an extension to handle the sup-t transitive closure of any fuzzy binary relation, through a novel incremental transitive closure (ITC) algorithm. The ITU and ITC algorithms can be applied on any fuzzy binary relation and t-norm; properties such as reflexivity, symmetricity and idempotency are not a requirement. Under the specified assumptions for the average sparse relation, both of the proposed algorithms have considerably smaller computational complexity than the conventional approach; this is both established theoretically and verified via appropriate computing experiments.

Download

Click here to access the paper.

15 known citations

1. R. Jensen and Q. Shen, New approaches to fuzzy-rough feature selection, IEEE Transactions on Fuzzy Systems, vol 14, no 4, pp 828-838, 2009
2. W. Pedrycz and F. Gomide, Fuzzy Systems Engineering: Toward Human-Centric Computing, Wiley-IEEE Press, August 2007
3. N. MacParthalain, R. Jensen and Q. Shen, Finding Fuzzy-rough Reducts with Fuzzy Entropy, Proceedings of the 17th International Conference on Fuzzy Systems, 2008
4. L. Garmendia, A. Salvador, and J. Montero, Computing a T-transitive lower approximation or opening of a proximity relation, Fuzzy Sets and Systems 160(14), 2009
5. N. Mac Parthalain, Rough Set Extensions for Feature Selection, PhD Thesis, Aberystwyth University, Wales, 2009
6. A. Mirzaei, M. Rahmati, M., A novel hierarchical-clustering-combination scheme based on fuzzy-similarity relations, IEEE Transactions on Fuzzy Systems, 18 (1), pp. 27-39, 2010
7. R. Jensen and Q. Shen, Computational Intelligence and Feature Selection: Rough and Fuzzy Approaches, Wiley-IEEE Press, 2008
8. R. Jensen, A. Tuson, S. Qiang, Extending propositional satisfiability to determine minimal fuzzy-rough reducts, IEEE International Conference on Fuzzy Systems, 18-23 July 2010
9. J. Ignjatovic, M. Ciric, V. Simovic, Fuzzy relation equations and subsystems of fuzzy transition systems, Knowledge-Based Systems, vol 38, pp 48-61, 2013
10. N. MacParthalain, R. Jensen, Q. Shen, Finding Fuzzy-rough Reducts with Fuzzy Entropy, IEEE International Conference on Fuzzy Systems, Cadair, 2008
11. X. Kang , D. Li , S. Wang, K. Qu, Formal concept analysis based on fuzzy granularity base for different granulations, Fuzzy Sets and Systems, 203, p.33-48, September, 2012
12. R. Jensen, A. Tuson, Q. Shen, Finding rough and fuzzy-rough set reducts with SAT, Information Sciences: an International Journal, 255, p.100-120, January, 2014
13. G.N. Deng, K. Hu and H.X. Li, Algorithms for computing the optimal transitive approximation of a proximity relation, Soft Computing, vol 15, pp. 1023-1038, 2011
14. W. Pedrycz, P. Ekel and R. Parreiras, Fuzzy Multicriteria Decision-Making: Models, Methods and Applications, John Wiley & Sons, Jun 15, 2011
15. J. Ignjatovic, M. Ciric, B. Seselja and A. Tepavcevic, Fuzzy relational inequalities and equations, fuzzy quasi-orders, closures and openings of fuzzy sets, Fuzzy Sets and Systems, 2014