Nonparametric clustering algorithms, including mode-seeking, valley-seeking, and unimodal set algorithms, are capable of identifying generally shaped clusters of points in metric spaces. Most mode and valley-seeking algorithms, however, are iterative and the clusters obtained are dependent on the starting classification and the assumed number of clusters. In this paper, we present a noniterative, graph-theoretic approach to nonparametric cluster analysis. The resulting algorithm is governed by a single-scalar parameter, requires no starting classification, and is capable of determining the number of clusters. The resulting clusters are unimodal sets.

The problem of clustering N objects into M classes may be viewed as a combinatorial optimization algorithm. In the literature on clustering, iterative hill-climbing techniques are used to find a locally optimum classification. In this paper, we develop a clustering algorithm based on the branch and bound method of combinatorial optimization. This algorithm determines the globally optimum classification and is computationally efficient

The provision of many public services is accomplished by means of a network of facilities. As demand for the service grows, the facilities in the network must be reinforced. Alternatives may exist, however, which temporarily defer one or more reinforcements. A model is presented which enables the optimal deferral policy in a single terminal flow network to be determined. The algorithm is illustrated by its application to a telephone exchange cable network.

Feature extraction has been recognized as a useful technique for pattern recognition. Feature extraction is accomplished by constructing a mapping from the measurement space to a feature space. Often, the mapping is chosen from an arbitrarily specified parametric family by optimizing the parameters with respect to a separability criterion.

The problem of clustering multivariate observations is viewed as the replacement of a set of vectors with a set of labels and representative vectors. A general criterion for clustering is derived as a measure of representation error. Some special cases are derived by simplifying the general criterion. A general algorithm for finding the optimum classification with respect to a given criterion is derived. For a particular case, the algorithm reduces to a repeated application of a straightforward decision rule which behaves as a valley-seeking technique. Asymptotic properties of the procedure are developed. Numerical examples are presented for the finite sample case.

A family of nonparametric clustering criteria has been previously proposed by the authors. One particular member of this family was subjected to analysis and experimentation. This criterion was shown by heuristic argument, experimentation, and approximate asymptotic analysis to exhibit ``valley-seeking'' behavior. In this paper, we consider a more general class of valley-seeking criteria. The results bear a close resemblance to Parzen's theory of probability density estimation. This similarity is exploited to develop sufficient conditions for a criterion to be valley seeking in the asymptotic sense.

The Karhunen-Lo6ve expansion has been used previously to extract important features for representing samples taken from a given distribution. A method is developed herein to use the Karhunen-Loeve expansion to extract features relevant to classification of a sample taken from one of two pattern classes. Numerical examples are presented to illustrate the technique.

Many algorithms for grouping data without supervision depend on some criterion. We state two basic requirements such criteria should meet and we discuss several criteria in terms of these requirements. An attempt to satisfy both requirements simultaneously with a simple criterion leads us to introduce a linear transformation of the data. Although our principal result is for a two category problem, we present discussion and an example for the many category problem as well.