8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> Fast search algorithms are proposed and studied for vector quantization encoding using the K-dimensional (K-d) tree structure. Here, the emphasis is on the optimal design of the K-d tree for efficient nearest neighbor search in multidimensional space under a bucket-Voronoi intersection search framework. Efficient optimization criteria and procedures are proposed for designing the K-d tree, for the case when the test data distribution is available (as in vector quantization application in the form of training data) as well as for the case when the test data distribution is not available and only the Voronoi intersection information is to be used. The criteria and bucket-Voronoi intersection search procedure are studied in the context of vector quantization encoding of speech waveform. They are empirically observed to achieve constant search complexity for O(log N) tree depths and are found to be more efficient in reducing the search complexity. A geometric interpretation is given for the maximum product criterion, explaining reasons for its inefficiency with respect to the optimization criteria. > <s> BIB001 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> The K-means algorithm for clustering is very much dependent on the initial seed values. We use a genetic algorithm to find a near-optimal partitioning of the given data set by selecting proper initial seed values in the K-means algorithm. Results obtained are very encouraging and in most of the cases, on data sets having well separated clusters, the proposed scheme reached a global minimum. <s> BIB002 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> An alternate training technique for the fuzzy min-max clustering neural network is introduced. The original fuzzy min-max clustering neural network utilized an algorithm similar to leader clustering and adaptive resonance theory to place hyperboxes in the pattern space. An alternative clustering technique is introduced, which utilizes evolutionary programming and information criteria to produce a set of hyperboxes. > <s> BIB003 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> This paper presents the results of an experimental study of some common document clustering techniques. In particular, we compare the two main approaches to document clustering, agglomerative hierarchical clustering and K-means. (For K-means we used a “standard” K-means algorithm and a variant of K-means, “bisecting” K-means.) Hierarchical clustering is often portrayed as the better quality clustering approach, but is limited because of its quadratic time complexity. In contrast, K-means and its variants have a time complexity which is linear in the number of documents, but are thought to produce inferior clusters. Sometimes K-means and agglomerative hierarchical approaches are combined so as to “get the best of both worlds.” However, our results indicate that the bisecting K-means technique is better than the standard K-means approach and as good or better than the hierarchical approaches that we tested for a variety of cluster evaluation metrics. We propose an explanation for these results that is based on an analysis of the specifics of the clustering algorithms and the nature of document <s> BIB004 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> The process of partitioning a large set of patterns into disjoint and homogeneous clusters is fundamental in knowledge acquisition. It is called Clustering in the literature and it is applied in various fields including data mining, statistical data analysis, compression and vector quantization. The k-means is a very popular algorithm and one of the best for implementing the clustering process. The k-means has a time complexity that is dominated by the product of the number of patterns, the number of clusters, and the number of iterations. Also, it often converges to a local minimum. In this paper, we present an improvement of the k-means clustering algorithm, aiming at a better time complexity and partitioning accuracy. Our approach reduces the number of patterns that need to be examined for similarity, in each iteration, using a windowing technique. The latter is based on well known spatial data structures, namely the range tree, that allows fast range searches. <s> BIB005 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> This paper proposes two new approaches to using PSO to cluster data. It is shown how PSO can be used to find the centroids of a user specified number of clusters. The algorithm is then extended to use K-means clustering to seed the initial swarm. This second algorithm basically uses PSO to refine the clusters formed by K-means. The new PSO algorithms are evaluated on six data sets, and compared to the performance of K-means clustering. Results show that both PSO clustering techniques have much potential. <s> BIB006 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> The clustering algorithm DBSCAN relies on a density-based notion of clusters and is designed to discover clusters of arbitrary shape as well as to distinguish noise. In this paper, we generalize this algorithm in two important directions. The generalized algorithm—called GDBSCAN—can cluster point objects as well as spatially extended objects according to both, their spatial and their nonspatial attributes. In addition, four applications using 2D points (astronomy), 3D points (biology), 5D points (earth science) and 2D polygons (geography) are presented, demonstrating the applicability of GDBSCAN to real-world problems. <s> BIB007 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> A new approach to data clustering is proposed, in which two or more measures of cluster quality are simultaneously optimized using a multiobjective evolutionary algorithm (EA). For this purpose, the PESA-II EA is adapted for the clustering problem by the incorporation of specialized mutation and initialization procedures, described herein. Two conceptually orthogonal measures of cluster quality are selected for optimization, enabling, for the first time, a clustering algorithm to explore and improve different compromise solutions during the clustering process. Our results, on a diverse suite of 15 real and synthetic data sets – where the correct classes are known – demonstrate a clear advantage to the multiobjective approach: solutions in the discovered Pareto set are objectively better than those obtained when the same EA is applied to optimize just one measure. Moreover, the multiobjective EA exhibits a far more robust level of performance than both the classic k-means and average-link agglomerative clustering algorithms, outperforming them substantially on aggregate. <s> BIB008 </s> 8 A Review of Major Application Areas of Differential Evolution <s> Data Clustering <s> Clustering algorithms typically assume that the available data constitute a random sample from a stationary distribution. As data accumulate over time the underlying process that generates them can change. Thus, the development of algorithms that can extract clustering rules in non-stationary environments is necessary. In this paper, we present an extension of the k-windows algorithm that can track the evolution of cluster models in dynamically changing databases, without a significant computational overhead. Experiments show that the k-windows algorithm can effectively and efficiently identify the changes on the pattern structure. <s> BIB009
Clustering is a fundamental step in the process of transforming data to knowledge. It aims at discovering groups (clusters) in a set of objects such that similarity among the objects in the same group is higher than that of objects belonging to different clusters. The application domain of clustering techniques is very wide including data mining, text mining, statistical data analysis, compression and vector quantization, global optimization and web personalization   BIB001  . Clustering algorithms are traditionally categorized into three main categories, Hierarchical, Partitioning BIB004 and Distance-based. Hierarchical clustering algorithms construct hierarchies of clusters in a top-down (agglomerative) or bottom-up (divisive) fashion. Hierarchical clustering algorithms have proved to yield high quality results especially for applications involving clustering text collections. Nonetheless, their high computational requirements, usually limits their applicability in real life applications, where the number of samples and their dimensionality is typically high (the cost is quadratic to the number of samples). Partitioning clustering algorithms, start from an initial clustering (that can be randomly formed) and create partitionings by iteratively adjusting the clusters based on the distance of the data points from a representative member of the cluster. The most commonly used partitioning clustering algorithm is k-means. This algorithm initializes k centers and iteratively assigns each data point to the cluster whose centroid minimizes the Euclidean distance from the data point. Algorithms of this type can give good clustering results at low cost, since their running time is proportional to kN , where N is the number of patterns present in the dataset. However, their results rely heavily on their initialization and they can converge to arbitrary local optima. Distance based clustering algorithms create a partitioning by considering neighbors of data points. DBSCAN BIB007 is a distance-based clustering algorithm that has proved quite effective for spatial databases. Clusters are considered as high density neighborhoods of data points. Although the density parameter is critical for the successful application of DBSCAN, recently proposed heuristics appear to yield high quality results. The computational complexity of DBSCAN comes up to O(N log(N )) under the assumption that the data are organized in a spatial index (R * -tree). In evolutionary clustering, a solution to the clustering problem is typically encoded as a chromosome. By employing evolutionary operators and a population of solutions the algorithm probes the search space to find a globally optimum partition of the data. In early approaches   , chromosomes encoded the partition of n objects into K clusters and Genetic Algorithms were employed to identify the best partition. However, the sensitivity of GAs to the selection of the various parameters like population size, and crossover and mutation probabilities, as well as, the difficulties associated with the representation scheme, presented a major problem. Better results were obtained through hybrid approaches BIB002 . However, it is possible to represent the clustering procedure as an optimization problem of locating the optimal centroids of clusters. Thus, all evolutionary techniques can be employed since a clustering solution can be represented as a real-valued vector of the centroids. Previous approaches employed Evolutionary Strategies  , Evolutionary Programming BIB003 , and recently Particle Swarm Optimization BIB006 . All these approaches demonstrated that it is possible to obtain high quality partitions, but at a high computational cost. Here we attempt to tackle the high computational cost of traditional evolutionary techniques by introducing a new fitness criterion. This criterion is based on a windowing technique already employed in other clustering algorithms BIB009 BIB005 . A critical and open issue in cluster analysis, is the determination of the number of clusters present in a dataset. The evolutionary clustering techniques proposed so far, with the exception of BIB008 , require from the user to specify the number of clusters present in the data prior to the execution of the algorithm. The described approach can provide an approximation to the number of clusters present in a dataset.