聚类算法- K-means算法

#include <iostream>

#include <sstream>

#include <fstream>

#include <string>

#include <vector>

#include <ctime>

#include <cstdlib>

#include <limits>

using namespace std;

// 数据类型转换 string 转float

float StringToFloat(string str)

{

    stringstream  sstream;

        float score = 0;

        sstream<<str;

        sstream>>score;

        return score;

}

//读取文件

vector<point_t> OpenFile(const char *dataset)

{

        fstream file;

        vector<point_t> data;

        file.open(dataset,ios::in);

        while(!file.eof())

        {

          string temp;

          file>>temp;

          int split =temp.find(',');

          point_t p;

          p.x = StringToFloat(temp.substr(0,split));

          p.y = StringToFloat(temp.substr(split+1,temp.length()-1));

          p.cluster = 0;

          data.push_back(p);

        }

        file.close();

   return data;

}

//计算两点之间的距离

float SquareDistance(point_t a,point_t b)

{

        return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

//随机选择K个质点

vector<point_t> RandomSeceleK(vector<point_t>dataset,int k)

{

        unsigned int n = 1;

        unsigned int len = dataset.size();

        vector<point_t> centroid;

        srand((int)time(0));        //使用时间设定随机种子

        //随机选择质心,生成K个聚类中心点

        while(n<=k)

        {

                int cen = (float)rand()/(RAND_MAX+1)*len;

                point_t cp;

                cp.x = dataset[cen].x;

                cp.y = dataset[cen].y;

                cp.cluster = n;

                centroid.push_back(cp);

                n++;

        }

        return centroid;

}

//计算所有样本点到聚类中心的距离，根据远近聚类

vector<point_t> DistanceCluster(vector<point_t>dataset,vector<point_t>centroid,int k)

{

        int len = dataset.size();

        int n = 1;

        for(int i=0;i<len;i++)

        {

                n=1;

                float shortest = INT_MAX;

                int cur = dataset[i].cluster;

                while(n<=k)

                {

                        float temp = SquareDistance(dataset[i],centroid[n-1]);                        

                        if(temp<shortest)

                        {

                                shortest = temp;

                                cur = n;

                        }

                        n++;

                }

                dataset[i].cluster = cur;

        }

        return dataset;

}

//更新质心

vector<point_t> UpdateCentroid(vector<point_t>dataset,vector<point_t>centroid,int k)

{

    int len = dataset.size();

        int *cs = new int[k];

        for(int i=0;i<k;i++) cs[i] = 0;

        for(int i=0;i<k;i++)

        {

                centroid[i].x = 0;

                centroid[i].y = 0;

                centroid[i].cluster = i+1;

        }

        for(int i=0;i<len;i++)

        {

                centroid[dataset[i].cluster-1].x += dataset[i].x;

                centroid[dataset[i].cluster-1].y += dataset[i].y;

                cs[dataset[i].cluster-1]++;

        }

        for(int i=0;i<k;i++)

        {

                centroid[i].x /= cs[i];

                centroid[i].y /= cs[i];

        }

        return centroid;

}

//k-means 算法

void k_means(vector<point_t>dataset,int k,int looptimes)

{

        vector<point_t> centroid;   //存放中心点

        int n =1;

        int len = dataset.size();

        //1.随机选择K个质点

        centroid = RandomSeceleK(dataset,k);

        //打印中心点（质点）

        for(int i=0;i<k;i++)

        {

          cout<<"x:"<<centroid[i].x<<"\ty:"<<centroid[i].y<<"\tc:"<<centroid[i].cluster<<endl;

        }

        //循环迭代

        for(int i = 0;i<looptimes;i++)

        {

           //2.计算所有样本点到聚类中心的距离，根据远近聚类

           dataset = DistanceCluster(dataset,centroid,k);          

           //3.更新质心，迭代聚类

           centroid = UpdateCentroid(dataset,centroid,k);   

        }

        //打印所有点聚类情况

         for(int i=0;i<dataset.size();i++)

           {

             cout<<dataset[i].cluster<<endl;

           }

        //打印最后更新质心

        for(int i=0;i<k;i++)

        {

                cout<<"x:"<<centroid[i].x<<"\ty:"<<centroid[i].y<<"\tc:"<<centroid[i].cluster<<endl;

        }

    //写入到文件保存

        fstream clustering;

        clustering.open("clustering.txt",ios::out);

        for(int i=0;i<len;i++)

        {

                clustering<<dataset[i].x<<","<<dataset[i].y<<","<<dataset[i].cluster<<"\n";

        }

        clustering.close();

}

#include "k_means.h"



int main()

{

    vector<point_t> data;

        cout<<"k-means"<<endl;

        data = OpenFile("01.txt");

        k_means(data,2,100);

        while(1);

}