Skip to main content

1981 | Buch

Pattern Recognition with Fuzzy Objective Function Algorithms

verfasst von: James C. Bezdek

Verlag: Springer US

Buchreihe : Advanced Applications in Pattern Recognition

insite
SUCHEN

Über dieses Buch

The fuzzy set was conceived as a result of an attempt to come to grips with the problem of pattern recognition in the context of imprecisely defined categories. In such cases, the belonging of an object to a class is a matter of degree, as is the question of whether or not a group of objects form a cluster. A pioneering application of the theory of fuzzy sets to cluster analysis was made in 1969 by Ruspini. It was not until 1973, however, when the appearance of the work by Dunn and Bezdek on the Fuzzy ISODATA (or fuzzy c-means) algorithms became a landmark in the theory of cluster analysis, that the relevance of the theory of fuzzy sets to cluster analysis and pattern recognition became clearly established. Since then, the theory of fuzzy clustering has developed rapidly and fruitfully, with the author of the present monograph contributing a major share of what we know today. In their seminal work, Bezdek and Dunn have introduced the basic idea of determining the fuzzy clusters by minimizing an appropriately defined functional, and have derived iterative algorithms for computing the membership functions for the clusters in question. The important issue of convergence of such algorithms has become much better understood as a result of recent work which is described in the monograph.

Inhaltsverzeichnis

Frontmatter
1. Models for Pattern Recognition
Abstract
Section 1 (S1) describes specifically the problems to be discussed in succeeding chapters. In S2 a short analysis of the modeling process suggests that information and uncertainty will be key concepts in the development of new mathematical structures for pattern recognition. Fuzzy sets are introduced in the third section as a natural and tractable way to model physical situations which seem to require something more than is offered by deterministic or stochastic representations.
James C. Bezdek
2. Partitions and Relations
Abstract
In this chapter the foundations for models of subsequent chapters are discussed. S4 contains some definitions and first properties of fuzzy sets. The important device of mathematical embedding first appears here. Interestingly enough, however, a property of the embedded structure (that a subset and its complement reproduce the original set under union) which is not preserved under embedment turns out to be one of its most useful aspects! In S5 partitions of finite data sets are given a matrix-theoretic characterization, culminating in a theorem which highlights the difference between conventional and fuzzy partitions. S6 is devoted to exploration of the algebraic and geometric nature of the partition embedment: the main results are that fuzzy partition space is compact, convex, and has dimension n (c − 1). S7 considers hard and fuzzy relations in finite data sets and records some connections between relations and partitions that tie the observational and relation-theoretic approaches together.
James C. Bezdek
3. Objective Function Clustering
Abstract
S8 illustrates some of the difficulties inherent with cluster analysis; its aim is to alert investigators to the fact that various algorithms can suggest radically different substructures in the same data set. The balance of Chapter 3 concerns objective functional methods based on fuzzy c-partitions of finite data. The nucleus for all these methods is optimization of nonlinear objectives involving the weights u ik ; functionals using these weights will be differentiable over M fc —but not over M c —a decided advantage for the fuzzy embedding of hard c-partition space. Classical first- and second-order conditions yield iterative algorithms for finding the optimal fuzzy c-partitions defined by various clustering criteria.
James C. Bezdek
4. Cluster Validity
Abstract
Section 14 reviews the validity problem. The main difficulty is this: complex algorithms stand squarely between the data for which substructure is hypothesized and the solutions they generate; hence it is all but impossible to transfer a theoretical null hypothesis about X to UM fc which can be used to statistically substantiate or repudiate the validity of algorithmically suggested clusters. As a result, a number of scalar measures of partition fuzziness (which are interesting in their own right) have been used as heuristic validity indicants. Sections 15, 16, and 17 discuss three such measures: the Anderson iris data surfaces in S15 and S17. S18 contains several approaches aimed towards connecting a null hypothesis about X to UM fc : this idea is currently being heavily studied, and S18 is transitory at best. Sections 19 and 20 discuss measures of hard cluster validity which have been related by their inventors to fuzzy algorithms in several ways. S19 contains a particularly interesting application to the design of interstellar navigational systems. S20 provides an additional insight into the geometric property that data which cluster well using FCM algorithm (A11.1) must have.
James C. Bezdek
5. Modified Objective Function Algorithms
Abstract
In this chapter we discuss three modifications of previous algorithms which have been proposed in an attempt to compensate for the difficulties caused by variations in cluster shape. The basic dilemma is that “clusters” defined by criterion functions usually take mathematical substance via metrical distances in data space. Each metric induces its own unseen but quite pervasive topological structure on ℝ p due to the geometric shape of the open balls it defines. This often forces the criterion function employing d to unwittingly favor clusters in X having this basic shape—even when none are present! In S21, we discuss a novel approach due to Backer which “inverts” several previous strategies. S22 considers an interesting modification of the FCM functional J m due to Gustafson and Kessel,(54) which uses a different norm for each cluster! S23 and S24 discuss generalization of the fuzzy c-means algorithms (A11.1) in a different way—the prototypes v i for J m (U, v) become r-dimensional linear varieties in ℝ p , 0 ≤ rp − 1.
James C. Bezdek
6. Selected Applications in Classifier Design
Abstract
In this final chapter we consider several fuzzy algorithms that effect partitions of feature space ℝ p , enabling classification of unlabeled (future) observations, based on the decision functions which characterize the classifier. S25 describes the general problem in terms of a canonical classifier, and briefly discusses Bayesian statistical decision theory. In S26 estimation of the parameters of a mixed multivariate normal distribution via statistical (maximum likelihood) and fuzzy (c-means) methods is illustrated. Both methods generate very similar estimates of the optimal Bayesian classifier. S27 considers the utilization of the prototypical means generated by (A11.1) for characterization of a (single) nearest prototype classifier, and compares its empirical performance to the well-known k-nearest-neighbor family of deterministic classifiers. In S28, an implicit classifier design based on Ruspini’s algorithm is discussed and exemplified.
James C. Bezdek
Backmatter
Metadaten
Titel
Pattern Recognition with Fuzzy Objective Function Algorithms
verfasst von
James C. Bezdek
Copyright-Jahr
1981
Verlag
Springer US
Electronic ISBN
978-1-4757-0450-1
Print ISBN
978-1-4757-0452-5
DOI
https://doi.org/10.1007/978-1-4757-0450-1