%0 Report %1 Cristofor01aninformation-theoretical %A Cristofor, Dana %A Simovici, Dan A. %D 2001 %K 2009 clustering seminar %T An Information-Theoretical Approach to Genetic Algorithms for Clustering %U http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.9662 %X In a database with categorical attributes each attribute denes a partition whose classes can be regarded as natural clusters of rows. The main theme of this paper is nding a partition of the rows of the database that is as close as possible to the partitions associated to each attribute. The classes of this partition will then be treated as clusters of rows. We evaluate the closeness of two partitions by using certain generalizations of the classical conditional entropy. From this perspective, we wish to construct a partition (referred to as the median partition) such that the sum of the dissimilarities between this partition and all the partitions determined by the attributes of the database is minimal. Then, the problem of nding the median partition is an optimization problem over the space of all partitions of the rows of the database for which we give an approximative solution. To search more eciently the space of possible partitions, which can be very large, we are using a genetic algorithm. Partitions are represented by chromosomes and we tested both the classical techniques of mutation and crossover and certain special mutation and crossover methods that contain specic knowledge of the problem domain. Keywords: median partition, Shannon entropy, Gini index, mutations, crossover operations 1

@techreport{Cristofor01aninformation-theoretical, abstract = {In a database with categorical attributes each attribute denes a partition whose classes can be regarded as natural clusters of rows. The main theme of this paper is nding a partition of the rows of the database that is as close as possible to the partitions associated to each attribute. The classes of this partition will then be treated as clusters of rows. We evaluate the closeness of two partitions by using certain generalizations of the classical conditional entropy. From this perspective, we wish to construct a partition (referred to as the median partition) such that the sum of the dissimilarities between this partition and all the partitions determined by the attributes of the database is minimal. Then, the problem of nding the median partition is an optimization problem over the space of all partitions of the rows of the database for which we give an approximative solution. To search more eciently the space of possible partitions, which can be very large, we are using a genetic algorithm. Partitions are represented by chromosomes and we tested both the classical techniques of mutation and crossover and certain special mutation and crossover methods that contain specic knowledge of the problem domain. Keywords: median partition, Shannon entropy, Gini index, mutations, crossover operations 1 }, added-at = {2009-11-12T15:49:09.000+0100}, author = {Cristofor, Dana and Simovici, Dan A.}, biburl = {https://www.bibsonomy.org/bibtex/293bed8651ee5b7943a3b1d5ea9630f89/k.e.}, description = {An Information-Theoretical Approach to Genetic Algorithms for Clustering}, interhash = {09c65b0bba58a8332c6af079431d7112}, intrahash = {93bed8651ee5b7943a3b1d5ea9630f89}, keywords = {2009 clustering seminar}, timestamp = {2009-11-12T15:49:09.000+0100}, title = {An Information-Theoretical Approach to Genetic Algorithms for Clustering}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.9662}, year = 2001 }