genetic algorithms for clustering

genetic algorithms for clustering

1. genetic algorithms

   • process
     • encode data
       • inicialisation (chromosomes)
         • survival of the fittest
           • evolution
             • selection
               • roulette wheel selection
               • stochastic universal sampling
               • binary tournament selection
             • crossover
               • randomly select a crossover point
               • randomly select two points. Interchange between points
               • binary mask of the same length as chromosomes of 1 and 0 (uniformly generated)
             • mutation
               • should have low probability (0.01)
               • bit-flip
             • elitism
               • save best chromosome in current generation
           • usually use cluster validity index
           • represents the goodness of a chromosome
       • usually binary encoding is used.
       • Principle of minimum alphabet
       • for clustering
         • point-based
         • cluster-based
           • better convergence
   • concepts
     • search from multiple points
     • blind serch, use only payoff information
     • use stochastic operators

2. clustering

   • crisp
   • fuzzy
   • hierarchical
     • agglomerative
       • begin with singleton clusters
       • linkage
         • single
         • average
         • complete
     • divisive
       • biggest cluster is devided into two
   • partitional
     • K-means
       • termination
         • number of iteration
         • stable centers
     • fuzzy C-means
     • medoid
       • used for alleviate outliers problem
       • PAM
       • CLARA
     • K-modes
     • fuzzy K-modes
       • for categorical dataset
   • density-based
     • DBSCAN
       • needs
         • radius of the neighborhood
         • minimum number of points
     • GDBSCAN
     • OPTICS
   • other algorithms
     • simulated annealing
     • balanced iterative reducing
     • BIRCH
     • expectation maximization
     • tree-based graph theoretic clustering
     • spectral clustering
     • self organizing map
     • genetic
   • validity index
     • external indeces
       • Minkovski
       • Rand
       • the percentage of correctly classified pairs
       • adjusted Rand
       • True clustering is needed
     • internal indeces
       • Davies-Bouldin
       • Dunn
       • Partition Coefficient
       • Partition Entropy
       • Xie-Beni
       • Fukuyama-Sugeno
       • Silhouette
       • F
       • K

3. multiobjective optimization

   • Pareto-optimality
     • weakly non-dominated
     • strongly non-dominated
   • Aggregating Approaches
     • Weighted sum
     • Goal programming
       • minimization of deviation from target
     • Goal attainment
     • e-Constrained
       • obj.function optimized, other bound by e
   • Population-Based Non-Pareto Approaches
     • Vector evaluated genetic algorithm
     • Lexicographic ordering
     • Game theory
     • use of gender for identifying the objectives
     • use of contact theorem
   • Pareto-based non-elitist approaches
     • Multiple objective GA
     • Niched Pareto GA
     • Non-dominated Sorting GA
   • Pareto-Based Elitist approaches
     • strength Pareto Evolutionary alg. (two variants)
     • Pareto archived evolutionary strategy
       • 1+1 evolution strategy, adaptive grid for population diversity
     • Pareto envelope-based selection alg. (two variants)
       • internal and external populations. hyper-grid for diversity
     • Elitist Non-dominated sorting GA
       • crowded tournament selection
       • usually used for clustering
     • Archived multiobjective simulated annealing

4. Knowledge discovery process

   • data preporation
   • data mining
     • discriptive
       • association rule mining
         • discovery of rules showing attribute-value asociations
       • clustering
       • deviation detection
       • feature selection
     • predictive
       • classification
         • NN Rule
           • assigns new object to the class of its nearest neighbor
           • 1 - NN
           • K - NN
         • Bayes Maximum Likelihood Classifier
           • for given object choose the class with the highest conditional probability
         • Decision trees
           • can be overfitted, so tree-pruning techniques are used
         • support vector machine classifier
           • maximally separating hyperplane
       • regression
   • knowledge representation

5. Important tasks in computational biology

   • sequence level
     • deal with DNA, RNA, proteins
     • genomic sequencing and fragment assembly
       • reconstruction of DNA = fragment assembly problem (FAP)
         • FAP similar to traveling salesperson (TSP)
     • Sequence alignment
     • Gene finding
       • extrinsic or evidence-based gene-finding systems
       • abinito gene finding
     • phylogenetic tree construction
       • the study of evolutionary relationships
       • similar to traveling salesperson (TSP)
     • Protein sequence classification
   • structure level
     • DNA structure prediction
     • RNA structure prediction
     • protein structure prediction and protein folding
       • homology modeling
   • expression based
   • system level