| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/stat/TeKMeansGrouping.h
Go to the documentation of this file.

    00001 /************************************************************************************
    00002 TerraLib - a library for developing GIS applications.
    00003 Copyright © 2001-2007 INPE and Tecgraf/PUC-Rio.
    00004
    00005 This code is part of the TerraLib library.
    00006 This library is free software; you can redistribute it and/or
    00007 modify it under the terms of the GNU Lesser General Public
    00008 License as published by the Free Software Foundation; either
    00009 version 2.1 of the License, or (at your option) any later version.
    00010
    00011 You should have received a copy of the GNU Lesser General Public
    00012 License along with this library.
    00013
    00014 The authors reassure the license terms regarding the warranties.
    00015 They specifically disclaim any warranties, including, but not limited to,
    00016 the implied warranties of merchantability and fitness for a particular purpose.
    00017 The library provided hereunder is on an "as is" basis, and the authors have no
    00018 obligation to provide maintenance, support, updates, enhancements, or modifications.
    00019 In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
    00020 indirect, special, incidental, or consequential damages arising out of the use
    00021 of this library and its documentation.
    00022 *************************************************************************************/
    00026 #ifndef  __TERRALIB_INTERNAL_KMEANSGROUPING_H
    00027 #define  __TERRALIB_INTERNAL_KMEANSGROUPING_H
    00028
    00029 #include "TeGroupingAlgorithms.h"
    00030
    00031 template<typename I, typename T>  int
    00032 TeMinimumDistance(I it, T& centroides )
    00033 {
    00034            double distmin = TeMAXFLOAT, dist;
    00035            int j = -1;
    00036            for (int i=0; i< centroides.size(); i++)
    00037            {
    00038                 dist = TeEuclidianDistance(it,centroides[i]);
    00039                 if ( dist < distmin )
    00040                 {
    00041                                   j = i;
    00042                                   distmin = dist;
    00043                        }
    00044            }
    00045            return j;
    00046 }
    00047
    00048 template<typename I, typename T>
    00049 double
    00050 TeEuclidianDistance(I it, T& centroide)
    00051 {
    00052            double val = 0;
    00053            int n = centroide.size();
    00054            for (int i=0; i<n; i++)
    00055            {
    00056                       double v1 = (*it)[i];
    00057                       double v2 = centroide[i];
    00058                       val += pow(v1-v2,2);
    00059            }
    00060            return sqrt(val);
    00061 }
    00062
    00063
    00064 template<typename T>
    00065 void
    00066 Initialize(T& centroide, vector<double>& minValue, vector<double>& maxValue)
    00067 {
    00068            int n = centroide.size();
    00069            for (int i=0; i<n; i++)
    00070            {
    00071                       double val = (rand()* (maxValue[i]-minValue[i]))/RAND_MAX;
    00072                       centroide[i] = val;
    00073            }
    00074            return;
    00075 }
    00076
    00077 template<typename T>
    00078 bool
    00079 CheckConvergence(T& toUpdate, T& newCentroides, double limiar )
    00080 {
    00081
    00082            int k = newCentroides.size();
    00083            int n = newCentroides[0].size();
    00084            for (int i=0; i<k; i++)
    00085                       for (int j = 0; j<n; j++)
    00086                       {
    00087                                  double num = newCentroides[i][j];
    00088                                  double den = toUpdate[i][j];
    00089 /*                               if (num > den)
    00090                                  {
    00091                                             double aux = den;
    00092                                             den = num;
    00093                                             num = aux;
    00094                                  }
    00095                                  val = (1-num/den)*100.;
    00096                                  if (val > limiar)
    00097                                             return false;
    00098 */
    00099                                  if (num != den)
    00100                                             return false;
    00101                       }
    00102            return true;
    00103 }
    00104
    00105 template<typename It, typename C>
    00106 void
    00107 ReCalculate(It it, C& nearest)
    00108 {
    00109            for (int i=0; i<nearest.size(); i++)
    00110                       nearest[i] = (nearest[i] + (*it)[i])/2.0;
    00111            return;
    00112 }
    00113
    00114
    00115 template<typename It, typename C> void
    00116 TeKMeans (It begin, It end, C& result, double conv)
    00117 {
    00118            srand( static_cast<unsigned>(time(NULL)));
    00119            C centroides(result), centr_aux(result);
    00120
    00121            int n = result[0].size();
    00122            vector<double> minValue(n);
    00123            vector<double> maxValue(n);
    00124
    00125            TeMinimumValue(begin, end, minValue);
    00126            TeMaximumValue(begin, end, maxValue);
    00127
    00128            for (int i=0; i<result.size();  i++)
    00129            {
    00130                       // Falta verificar se não gera centroides iniciais iguais
    00131                       Initialize(centroides[i], minValue, maxValue);
    00132            }
    00133
    00134            centr_aux = centroides;
    00135            bool converge = false;
    00136            int  j, niter=0;
    00137
    00138            while (!converge)
    00139            {
    00140                       for (It it=begin; it!= end; it++)
    00141                       {
    00142                                  j = TeMinimumDistance(it, centroides);
    00143                                  ReCalculate(it,centr_aux[j]);
    00144                       }
    00145                       converge = CheckConvergence(centroides, centr_aux,conv);
    00146                       centroides = centr_aux;
    00147                       niter++;
    00148    }
    00149    result = centroides;
    00150 }
    00151
    00152 template<typename ItIn, typename C, typename ItOut> void
    00153 TeEuclidianClassify (ItIn begin, ItIn end, ItOut& result, C& kmeans)
    00154 {
    00155            int j;
    00156            for (ItIn it=begin; it!= end; it++)
    00157            {
    00158                       j = TeMinimumDistance(it, kmeans);
    00159                       (*result) = j;
    00160                       result++;
    00161            }
    00162 }
    00163 #endif

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines