Data Mining Mehmed Kantardzic (good english books to read .txt) 📖

forth. To illustrate this, the genotype [1.5 1.5 10.5 1.5 5.0 5.5] encodes the three centroids: (1.5, 1.5), (10.5, 1.5), and (5.0, 5.5) of clusters C1, C2, and C3 in Table 13.5, respectively.

The second important decision, in applying GAs for clustering, is a selection of appropriate genetic operators. A number of crossover and mutation operators are proposed trying to solve an important problem of the context-insensitivity in GAs. When traditional genetic operators are employed in clustering problems, they usually just manipulate gene values without taking into account their connections with other genes. For example, the crossover operation presented in Figure 13.7 shows how two parents representing the same solution to the clustering problem (different labeling but the same integer encoding) produce the resulting offspring representing clustering solutions different from the ones encoded into their parents. Moreover, assuming that the number of clusters has been fixed in advance as k = 3, invalid solutions with only two clusters have been derived. Therefore, it is necessary to develop specially designed genetic operators for clustering problems. For example, the crossover operator should be repeatedly applied or randomly scrambling mutation performed until a valid child has been found.

Figure 13.7. Equal parents produce different offspring through crossover.

Different clustering validity criteria are adapted as fitness functions to evolve data partitions in clustering problems. They depend primarily on encoding schemes but also on a selected set of genetic operators. We will illustrate in this text only one example of a clustering fitness function when a real, centroid-based encoding scheme is used. Fitness function f minimizes the sum of squared Euclidean distances of the samples from their respective cluster means. Formally, the fitness function f(C1,C2, … , Ck) is:

where {C1, C2, … , Ck} is the set of k clusters encoded into the genotype, xi is a sample in a data set, and zj is the centroid of cluster Cj. It is important to stress that this criterion is valid only if the number of clusters k is given in advance, and it minimizes the intra-cluster distances and maximizes the intercluster distances as well. In general, fitness functions are based on the distance between samples and either cluster centroids or medoids. Although these types of functions are widely used, usually they are biased toward the discovery of spherical clusters, which clearly will be inappropriate in many real-world applications. Other approaches are possible, including a density-based fitness function. In practice, the success of a GA to solve a clustering problem is highly dependent upon how it has been designed in terms of encoding scheme, operators, fitness function, selection procedure, and initial population generation.

13.8 REVIEW QUESTIONS AND PROBLEMS

1. Given a binary string that represents a concatenation of four attribute values:

use this example to explain the basic concepts of a GA and their equivalents in natural evolution.

2. If we want to optimize a function f(x) using a GA where the precision requirement for x is six decimal places and the range is [−1, 2], what will be the length of a binary vector (chromosome)?

3. If v1 = (0 0 1 1 0 0 1 1) and v2 = (0 1 0 1 0 1 0 1) are two chromosomes, and suppose that the crossover point is randomly selected after the fifth gene, what are the two resulting offspring?

4. Given the schema (* 1 * 0 0), what are the strings that match with it?

5. What is the number of strings that match with the schema (* * * * * * * *)?

6. The function f(x) = −x2 + 16x is defined on interval [0, 63]. Use two iterations of a GA to establish the approximate solution for a maximum of f(x).

7. For the function f(x) given in Problem number 6, compare three schemata

with respect to order (O), length (L), and fitness (F).

8. Given a parent chromosome (1 1 0 0 0 1 0 0 0 1), what is the potential offspring (give examples) if the mutation probability is

(a) pm = 1.0

(b) pm = 0.5

(c) pm = 0.2

(d) pm = 0.1

(e) pm = 0.0001

9. Explain the basic principles of the building-block hypothesis and its potential applications.

10. Perform a PMC operation for two strings S1 and S2, in which two randomly selected crossing points are given:

11. Search the Web to find the basic characteristics of publicly available or commercial software tools that are based on GAs. Document the results of your search.

13.9 REFERENCES FOR FURTHER STUDY

Fogel, D. B., ed., Evolutionary Computation, IEEE Press, New York, 1998.

The book provides a collection of 30 landmark papers, and it spans the entire history of evolutionary computation—from today’s research back to its very origins more than 40 years ago.

Goldenberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989.

This book represents one of the first comprehensive texts on GAs. It introduces in a very systematic way most of the techniques that are, with small modifications and improvements, part of today’s approximate-optimization solutions.

Hruschka, E., R. Campello, A. Freitas, A. Carvalho, A Survey of Evolutionary Algorithms for Clustering, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 39, No. 2, 2009, pp. 133–155.

This paper presents a survey of evolutionary algorithms designed for clustering tasks. It tries to reflect the profile of this area by focusing more on those subjects that have been given more importance in the literature. In this context, most of the paper is devoted to partitional algorithms that look for hard clustering of data, although overlapping (i.e., soft and fuzzy) approaches are also covered in the paper. The paper ends by addressing some important issues and open questions that can be the subjects of future research.

Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, Germany, 1999.

This textbook explains the field of GAs in simple terms, and discusses the efficiency of its methods in many interesting test cases. The importance of these techniques is their applicability