0

estoy aplicando el algoritmo de agrupacion kmeans y actualmente estoy en la parte de actualizar los centroides pero me sale un error de violacion de segmento cuando trato de sumar los puntos de cada centroide y dividirlo entre el numero total de punto correspondientes a cada centroide, quizas si alguien me puede ayudar a identificar porque se da ese error se lo agradeceria.

Este es el codigo, el error se me presenta en a funcion newCentroids.

    using namespace std;
    using SPoint = vector<pair<size_t, double>>;
    using Rates = map<pair<string, string>, double>; // (user,movie) -> rate


    Rates readNetflix(const string& fname) {
      ifstream input(fname);
      string line;
      size_t lines = 0;

      Rates rates;

      string currMovie;

      while (getline(input, line)) {
        if (line.back() == ':') {
          line.pop_back();
          currMovie = line;
          cout << "Movie: " << currMovie << endl;
        } else {
          size_t endUser = line.find_first_of(",");
          string currUser = line.substr(0, endUser);
          line.erase(0, endUser + 1);
          size_t endRate = line.find_first_of(",");
          string currRate = line.substr(0, endRate);
          rates[{currUser, currMovie}] = stoi(currRate);
        }
        lines++;
      }
      return rates;
    }


    vector<SPoint> createPoints(const Rates& rates) {
      map<string, size_t> normUsers;
      map<string, size_t> normMovies;
      for (const auto& e : rates) {
        const auto& user = e.first.first;
        const auto& movie = e.first.second;

        if (normUsers.count(user) == 0)
          normUsers[user] = normUsers.size();

        if (normMovies.count(movie) == 0)
          normMovies[movie] = normMovies.size();
      }
      cout << "End of normalization " << normUsers.size() << " "
           << normMovies.size() << endl;

      vector<SPoint> users(normUsers.size(),SPoint());
      for (const auto& e : rates) {
        size_t user = normUsers[e.first.first];
        size_t movie = normMovies[e.first.second];
        double rate = e.second;
        pair<size_t,double> p= make_pair(movie, rate);
        users[user].push_back(p);
      }
      return users;
    }



    double angle( const SPoint& p, const SPoint& q) {

      double p_punto=0;
      double norma_A=0;
      double norma_B=0;
      #pragma omp parallel for
      for (size_t i = 0; i < p.size(); i++) {
        p_punto=(p[i].first*q[i].first)+(p[i].second*q[i].second);
        norma_A=(sqrt(pow(p[i].first,2)+pow(p[i].second,2)));
        norma_B=(sqrt(pow(q[i].first,2)+pow(q[i].second,2)));
      }

      double A_Punto_B=norma_A*norma_B;
      double division=0;
        if (A_Punto_B != 0) {
           division=p_punto/A_Punto_B;
         }

      double arc_cos=acos(division);
      double rad_grados=(arc_cos*180)/3.1415926535;

      return rad_grados;
    }

    void printClustering(const vector<SPoint>& dataset,
                         const vector<size_t>& clustering, size_t k) {

      size_t n = dataset.size();
      vector<size_t> count(k, 0);
      for (size_t i = 0; i < n; i++) {
        size_t ci = clustering[i];
        count[ci]++;
      }
      for(size_t i = 0; i < k; i++) {
        cout << " cluster " << i << ": " << count[i] << endl;
      }
    }


    vector<SPoint> randomPoints(size_t k, const vector<SPoint>& ds) {
      random_device rd;
      mt19937 generator(rd());
      uniform_int_distribution<> unif(0, ds.size()-1);
      size_t dim = ds[0].size();
      vector<SPoint>  c(k,SPoint());
      //#pragma omp parallel
      //{
       //#pragma omp parallel for
       for (size_t i = 0; i < k; i++) {
         size_t r = unif(rd);
         pair<size_t,double> p= make_pair(r, r);
         c[i].push_back(p);
       }
      //}
      return c;
    }

    tuple<size_t, double> closestCentroid(const SPoint& p,
                                          const vector<SPoint>& centroids) {
      double d = numeric_limits<double>::max();
      size_t c = 0;
      //#pragma omp parallel
      //{
       //#pragma omp parallel for
       for (size_t i = 0; i < centroids.size(); i++) {
         double dt = angle(p, centroids[i]);
         if (dt < d) {
           d = dt;
           c = i;
         }
       }
      //}

      return make_tuple(c,d);
    }

    pair<vector<size_t>, double> cluster(const vector<SPoint>& dataset,
                                         const vector<SPoint>& centroids) {
      size_t n = dataset.size();
      vector<size_t> clustering(n, 0);
      double ssd = 0.0;
      for (size_t i = 0; i < n; i++) {
        size_t c;
        double d;
        tie(c, d) = closestCentroid(dataset[i], centroids);
        clustering[i] = c;
        ssd += d;
      }
      return {clustering, ssd};
    }

    vector<SPoint> newCentroids(const vector<size_t>& clustering,
                                const vector<SPoint>& dataset,
                                vector<SPoint>& centroids) {
      size_t k = centroids.size();
      size_t dim = centroids[0].size();
      vector<SPoint>  newCentroids(k,SPoint());
      vector<size_t> count(k, 0.0);

      for (size_t i = 0; i < dataset.size(); i++) {
        size_t ci = clustering[i];
        cout <<"ci: " << ci<<endl;
        for (size_t j = 0; j < dim; j++) {
          newCentroids[ci][j].first += dataset[i][j].first;
          newCentroids[ci][j].second += dataset[i][j].second;
        }
        count[ci]++;
      }



      //#pragma omp parallel
      for (size_t i = 0; i < k; i++) {
        for (size_t j = 0; j < dim; j++) {
            newCentroids[i][j].first /= count[i];
        }
      }
      return newCentroids;
      }
    //}

    vector<size_t> kmeans(const vector<SPoint>& dataset, size_t k, double epsilon,
                          size_t maxIter) {
      size_t dim = dataset[0].size();
      size_t n = dataset.size();
      vector<SPoint> centroids = randomPoints(k, dataset);
      vector<size_t> clustering(n, 0);
      double ssd = 0.0;
      double ssdPrev = 0.0;
      double d;
      size_t iter = 0;
      do{
        ssdPrev = ssd;
        cout << "Iteration " << iter << endl;
        tie(clustering, ssd) = cluster(dataset, centroids);
        cout << "SSD: " << ssd << endl;
        centroids = newCentroids(clustering,dataset,centroids);
        iter++;
        d = abs(ssdPrev - ssd);
        cout << "----> " << d << endl;

      }while(d>epsilon);

      return clustering;
    }


    int main(int argc, char** argv) {
      if (argc != 2)
        return -1;
      string fname(argv[1]);
      Rates rates = readNetflix(fname);
      vector<SPoint> ds = createPoints(rates);
      vector<size_t> clustering(21462,0);
      clustering = kmeans(ds, 3, 0.001, 8);
      printClustering(ds, clustering, 3);

      return 0;
    }
1
  • La violación de segmento sucede cuando se intenta acceder a memoria fuera de la asignada al programa. Posiblemente a alguno de los std::vector que usas le estás pasando un índice fuera de su rango, depura el comportamiento de vector<SPoint> users (normUsers.size() elementos indexado sobre rates.size()), vector<size_t> count (k elementos indexado sobre n), vector<SPoint>& ds, etc... Commented el 7 may. 2018 a las 6:12

1 respuesta 1

1
for (size_t j = 0; j < dim; j++) {
      newCentroids[ci][j].first += dataset[i][j].first;
      newCentroids[ci][j].second += dataset[i][j].second;
    }

Antes de acceder a los elementos tienes que asegurarte de de que el objeto "dataset[i][j]" es valido y no es nullptr, por si ha sido eliminado en algún punto o es invalido intentar dereferenciarlo provoca un segmetation fault

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.