James C. Bezdek

Clustering aims to identify groups of similar objects. To evaluate the results of cluster algorithms, an investigator uses cluster-validity indices. While the theory of cluster validity is well established for vector object data, little effort has been made to extend it to relationship-based data. As such, this paper proposes a theory of reformulation for object-data validity indices so that they can be used to rank the results produced by the relational -means clustering algorithms. More specifically, we create a class of relational validity indices, which is called dual-relational indices, that are guaranteed under certain, but easily met, constraints to produce the same results and, hence, the same cluster counts, as their object-data counterparts.

This paper presents a new technique for clustering either object or relational data. First, the data are represented as a matrix D of dissimilarity values. D is reordered to D* using a visual assessment of cluster tendency algorithm. If the data contain clusters, they are suggested by visually apparent dark squares arrayed along the main diagonal of an image I(D*) of D*. The suggested clusters in the object set underlying the reordered relational data are found by defining an objective function that recognizes this blocky structure in the reordered data. The objective function is optimized when the boundaries in I(D*) are matched by those in an aligned partition of the objects. The objective function combines measures of contrast and edginess and is optimized by particle swarm optimization. We prove that the set of aligned partitions is exponentially smaller than the set of partitions that needs to be searched if clusters are sought in D. Six numerical examples are given to illustrate various facets of the algorithm.

Identifying misbehaviors is an important challenge for monitoring, fault diagnosis and intrusion detection in wireless sensor networks. A key problem is how to minimize the communication overhead and energy consumption in the network when identifying misbehaviors. Our approach to this problem is based on a distributed, cluster-based anomaly detection algorithm. We minimize the communication overhead by clustering the sensor measurements and merging clusters before sending a description of the clusters to the other nodes. In order to evaluate our distributed scheme, we implemented our algorithm in a simulation based on the sensor data gathered from the Great Duck Island project. We demonstrate that our scheme achieves comparable accuracy compared to a centralized scheme with a significant reduction in communication overhead

We compare eleven methods for finding prototypes upon which to base the nearest prototype classifier. Four methods for prototype selection are discussed: Wilson+Hart (a condensation+error-editing method), and three types of combinatorial search—random search, genetic algorithm, and tabu search. Seven methods for prototype extraction are discussed: unsupervised vector quantization, supervised learning vector quantization (with and without training counters), decision surface mapping, a fuzzy version of vector quantization, c-means clustering, and bootstrap editing. These eleven methods can be usefully divided two other ways: by whether they employ pre- or postsupervision; and by whether the number of prototypes found is user-defined or “automatic.” Generalization error rates of the 11 methods are estimated on two synthetic and two real data sets. Offering the usual disclaimer that these are just a limited set of experiments, we feel confident in asserting that presupervised, extraction methods offer a better chance for success to the casual user than postsupervised, selection schemes. Finally, our calculations do not suggest that methods which find the “best” number of prototypes “automatically” are superior to methods for which the user simply specifies the number of prototypes. © 2001 John Wiley & Sons, Inc.