Doctoral School

January 15, 1992:

Admitted to Ph.D. studies at the Department of Computer Science, the Babes-Bolyai University, Cluj-Napoca, with the Ph.D. thesis "Intelligent Systems in Classification Problems"

September 2, 1992:

Ph.D. exam on subject "Classification and Pattern Recognition"

May 31, 1993:

Ph.D. exam on subject "Mathematics of Fuzzy Systems"

September 9, 1993:

Ph.D. exam on subject "Artificial Intelligence"

May 11, 1994:

Ph.D. report with the title "Trainable Pattern Classifiers and Neural Networks"

October 12, 1994:

Ph.D. report with the title "Metric and Non-Metric Classification"

November 3, 1995:

Public presentation of the Ph.D. Thesis at the Babes-Bolyai University in Cluj-Napoca

March 28-29, 1996:

The National University Titles, Degrees and Certificates Attestation Board confirmed the Ph.D. degree awarded by Babes-Bolyai University

April 3, 1996:

The Romanian Ministry of Education confirmed by its order No. 3543 the decision of the National Attestation Board with respect to the Ph.D. degree awarded by Babes-Bolyai University

May 10, 1996:

The Rector of the Babes-Bolyai University issued the Ph.D. Degree Diploma

Details About the Thesis

This Ph.D. thesis is the result of my research in the field of fuzzy classification, that has begun in 1988 by starting the work for the B.Sc. Thesis.

The fuzzy set appeared as a result of the trials to solve the pattern recognition problem in the context of imprecisely defined categories. In such cases, the membership degree of an object to a class is a problem of nuance.

A first application of the fuzzy sets theory in the cluster analysis is due to Ruspini in 1969 [16]. However, the relevance of the fuzzy sets theory for the classification theory and for pattern recognition was definitely established in 1974, with the paper of Dunn and Bezdek [8] concerning the Fuzzy n-Means algorithm.

The thesis lays on 204 pages, is structured on six chapters, and has a bibliography of 105 titles.

The first chapter shows the fundamental notions of the fuzzy sets theory. There are defined the fuzzy sets and fuzzy points. There are presented the axioms of the fuzzy sets operations. The triangular norms and co-norms and the fuzzy complement are introduced. The properties of the operations induced on fuzzy sets by T₀ and S₀; T_infty and S_infty; two arbitrary connectives T and S, are studied. The disjointness of two fuzzy sets and of a family at most countable of fuzzy sets are discussed. Finally, there are approached metrical notions as distance between two fuzzy sets, diameter of a fuzzy set and distance with respect to a fuzzy set.

The second chapter discusses the problem of convex decomposition of finite fuzzy partitions. There are approached both the degenerate and the non-degenerate convex decomposition. The MiniMax and MiniMiniMax degenerate convex decomposition algorithms are studied. We show that these algorithms have a series of common properties. A comparative statistical study with respect to these two algorithms is presented. In the second part, the problem of non-degenerate convex decomposition is studied. The algorithm DNDCD for non-degenerate convex decomposition of a fuzzy partition is presented. If such a convex decomposition does not exist, the algorithm produces a convex decomposition as less degenerate as possible. The properties of the DNDCD algorithm are then studied.

The third chapter approaches the unsupervised fuzzy classification. The fundamental problem of classification is presented. The most important classes of classification algorithms are discussed. In what follows the algorithms based on optimizing a criterion function will be studied. The (di-)similarity measure is defined. The Classical n-Means algorithm and its fuzzy version, Fuzzy n-Means, are presented. The convergence of the algorithms similar to Fuzzy n-Means is studied. The 'weak points' of the Fuzzy n-Means are discussed. There is approached the cluster validity problem. Different validity functionals are presented. The generalization of the Fuzzy n-Means algorithm for producing the cluster substructure of a fuzzy set, and the fuzzy divisive hierarchical clustering algorithm are studied. The problem of unequal sized clusters is discussed. The algorithms based on adaptive metric and ellipsoidal prototypes are studied. There is studied the problem of the classes' shape and the use of linear prototypes; the use of convex combinations between the criterion functions; the use of adaptive prototypes. Other types of classification are approached: characteristics classification; cross-classification; classification of non-metrical data. The notion of fuzzy set associated to a classical set is then studied. There is presented an algorithm to produce this fuzzy set. Finally, a series of numerical experiments with respect to these algorithms is done.

The fourth chapter studies the problem of supervised fuzzy classification. The Rosenblatt perceptron algorithm is presented. The notion of linear separability with respect to two fuzzy sets is studied. A few generalization of the perceptron algorithm are studied: the fuzzy perceptron algorithm; the generalized fuzzy perceptron algorithm; the Gallant Pocket algorithm; the Keller-Hunt algorithm are presented. The fuzzy relaxation algorithm is studied. This algorithm has a series of interesting properties that allow its use in the case of two linearly non-separable fuzzy sets. A series of fuzzy algorithms based on minimization of the square error are presented: the fuzzy method of the minimal square error; the fuzzy Widrow-Hoff algorithm; the fuzzy Ho-Kashyap algorithm. The fuzzy decision supervised classification is then studied. A series of fuzzy algorithms are discussed: the fuzzy algorithm of the nearest k neighbors; the fuzzy algorithm of the nearest prototype; the Restricted Fuzzy n-Means algorithm. Finally, a series of numerical experiments with respect to these algorithms is done.

The fifth chapter presents the SAADI software (System for Automatic Analysis of Data and for their Interpretation). This system, realized using Borland Pascal with Objects 7.0, implements the algorithms presented in this thesis, together with a series of algorithms aimed to reduce the data dimensionality. The system has effectively been used in the research activity of the Fuzzy Systems Research Group from the Department of Computer Science, as well as in the research activity at other faculties of our university.

The sixth chapter presents a few fuzzy classification applications. There is approached the use of fuzzy sets to optimally selecting the solvents systems; to the study of Roman pottery (terra sigillata); to the classification of Greek muds and pelloids; to the study of importance of fuzzy regression algorithms in chemistry; to the creation of a fuzzy system of chemical elements.

Among the original elements presented throughout this thesis we recall the following:

• study of the properties of MiniMax and MiniMiniMax algorithms (section 2.5);
• comparative statistical study with respect to MiniMax and MiniMiniMax algorithms (section 2.5);
• DNDCD algorithm for degenerate and non-degenerate convex decomposition of finite fuzzy partitions (section 2.7);
• properties of the DNDCD algorithm (section 2.8);
• classification algorithm with adaptive prototypes (section 3.9.3);
• correction made on the classification algorithm for non-metric data, as well as the theorem that justifies this correction (section 3.10.3);
• notion of fuzzy set associated to a classical set, the study of its properties and the algorithm to produce this fuzzy set (section 3.10.4);
• comparative study of the unsupervised classification algorithms, based on numerical experiments (section 3.11);
• generalization for fuzzy sets of the Gallant Pocket algorithm (section 4.4.3);
• generalization of the fuzzy relaxation algorithm as well as the study of its properties (section 4.5);
• fuzzy decision supervised classification (section 4.8);
• comparative study of the supervised classification algorithms, based on numerical experiments (section 4.9);
• greatest part of the remarks concerning the practical functioning of the algorithms studied in chapters 3 and 4;
• SAADI software for data analysis (chapter 5);
• study of the fuzzy classification applications in chemistry and archaeology (chapter 6).

Selected References

1. James C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, New York, 1981
2. James C. Bezdek, C. Coray, R. Gunderson and J. Watson, Detection and characterisation of cluster substructure: I. Linear structure: Fuzzy C-lines, SIAM Journal on Applied Mathematics 40, 2 (1981), 339-357
3. James C. Bezdek, C. Coray, R. Gunderson and J. Watson, Detection and characterisation of cluster substructure: II. Linear structure: Fuzzy C-varieties and convex combinations thereof, SIAM Journal on Applied Mathematics 40, 2 (1981), 358-372
4. D. Dumitrescu, and Horia F. Pop, Convex decomposition of fuzzy partitions, I. Fuzzy Sets and Systems 73 (1995), 365-376
5. D. Dumitrescu and Horia F. Pop, Convex decomposition of fuzzy partitions, II. Fuzzy Sets and Systems 96 (1998), 111-118
6. D. Dumitrescu, Horia F. Pop and Costel Sarbu, Fuzzy hierarchical cross-classification of Greek muds, Journal of Chemical Information and Computer Sciences 35 (1995), 851-857
7. D. Dumitrescu, Costel Sarbu and Horia F. Pop, A fuzzy divisive hierarchical clustering algorithm for the optimal choice of set of solvent systems, Analytical Letters 27, 5 (1994), 1031-1054
8. J. C. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, Journal of Cybernetics 3, 3 (1974), 32-57
9. Horia F. Pop, Adaptive prototypes in fuzzy clustering, B.Sc. thesis, Department of Computer Science, Babes-Bolyai University, Cluj-Napoca, 1991
10. Horia F. Pop, A study of the properties of the Fuzzy Relaxation Algorithm, Studia Universitatis Babes-Bolyai, Series Math. 39, 3 (1994), 67-74
11. Horia F. Pop, D. Dumitrescu and Costel Sarbu, A study of Roman pottery (terra sigillata) using hierarchical fuzzy clustering, Analitica Chimica Acta 310 (1995), 269-279
12. Horia F. Pop and Costel Sarbu, A new fuzzy regression algorithm, Journal of Analytical Chemistry 68 (1996), 771-778
13. Horia F. Pop, Costel Sarbu, Ossi Horowitz and D. Dumitrescu, A fuzzy classification of the chemical elements, Journal of Chemical Information and Computer Sciences 36 (1996), 465-482
14. Enrique H. Ruspini, A new approach to clustering, Information and Control 15 (1969), 22-32
15. Costel Sarbu, Ossi Horowitz and Horia F. Pop, A fuzzy classification of the chemical elements, based both on their physical, chemical and structural features, Journal of Chemical Information and Computer Sciences 36 (1996), 1098-1108