C語言如何實現K-Means算法

小編給大家分享一下C語言如何實現K-Means算法，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、聚類和聚類算法

聚類，就是將數據對象劃分成若干個類，在同一個類中的對象具有較高的相似度，而不同的類相似度較小。聚類算法將數據集合進行劃分，分成彼此相互聯系的若干類，以此實現對數據的深入分析和數據價值挖掘的初步處理階段。例如在現代商業領域，聚類分析算法可以從龐大的數據集合中對消費者的消費習慣、消費傾向，以方便決策者制訂消費策略。總之，作為數據挖掘中的一個模塊，聚類分析算法可以作為一個單獨的工具已發現數據庫中分布的一些深層信息，并概括出每一類的特點。聚類分析算法也可作為數據挖掘算法中其他分析算法的一個預處理步驟。

在數據挖掘領域，聚類分析算法可以分為一下幾個大類，包括劃分法、層次法、基于密度的方法、基于網絡的方法和基于模型的方法。基于劃分的基本思想就是通過迭代的方法將含有N個數據對象的數據集分成K個聚類。具體的步驟就是，用戶先給出要劃分的個數，然后通過一定的算法反復的進行迭代，使得每次得到的分組比前一次更加接近預期目標，是否優化的判定標準是同組數據之間不同數據之間的相似程度，同組數據相似程度越大，組間似程度越小越優化。

K-means聚類算法的核心思想就是基于對數據集合的劃分，它把N個數據對象劃分成K個類，使每個類中的數據點到該聚類中心的距離平方和最小。下面我將利用C語言來實現K-means算法，并對該算法在輸入不同的聚類個數、改變數據點的密集程度以及初始聚類中心點的選擇三個方面來測試該算法。

二、K-means算法實現步驟

通過對聚類和K-Means算法思想的了解，C語言算法的實現過程如下：

（1）通過文件輸入N個數據點，并選取其中K（K<N）個數據點作為初始聚類中心；

（2）對剩余的數據點分別計算到各個聚類聚點中心的歐氏距離，并將該點劃分到最近的類中；

（3）重新計算各個聚類的聚點中心；

（4）與之前的聚類中心比較，如果聚類中心發生變化，轉到（2），否則結束迭并輸出結果。

三、K-means算法實現

（一）實現思路

通過以上對K-means算法的了解，該算法主要是通過迭代的思想來求解K個聚類的中心。由于傳統數組需要先定義再使用，且在使用的過程中不能實現數組長度的動態增長。同時考慮到設計該算法時，沒有涉及到在迭代過程中各個數據點的插入和刪除，各個數據點具體劃分到那個聚類中，是由結構體成員變量中的className來標識，因此選用了Vector來作為存儲數據的容器，這樣當從文件輸入大量數據時，由程序自己開辟需要的存儲空間。同時，也可通過Vector向量容器提供的size和迭代器方法，實現遍歷并按照所在聚類進行輸出。

每個數據點都含有X、Y坐標，算法初始狀態時，指定聚類的具體個數K，初試狀態的K個聚類中心由輸入文件的前K個數據點來指定。算法在每一次迭代中，需要計算各個點到K個聚類中心坐標的歐氏距離，并選擇距離最近的一個聚類，用該聚類的名稱標識當前數據點。當所有數據點遍歷完后，計算劃分到每個聚類中所有數據點X與Y的均值，并將該均值與前一次聚類中心點的坐標相比較。當X與Y的誤差小于或者等于1e-6時，則結束迭代并輸出收斂后的K歌聚類的中心坐標。

（二）變量和函數說明

（1）定義結構體類型，用于存儲數據點坐標、所在聚類、與聚類中心距離

typedef struct point

{

float x,y;    //數據點的坐標
string className; //所屬的聚類
float distance;  //距離聚類中心的距離

}Point;

（2）變量聲明

vector<Point> dataVector：存儲從文件讀取的數據

vector<Point> classPoints：存儲聚類坐標

vector<Point> &totalPoints)：存儲所有的數據點

（3）函數聲明

字符串轉換函數：將整型變量轉換成字符串類型：

string converToString(int x);

讀入數據函數：從文件讀入坐標數據：

vector<Point> readDataFile(string fileName);

初始化數據集合函數：

void initDataset(int classNum,vector<Point> dataVector,vector<Point> &classPoints,vector<Point> &totalPoints);

計算各個數據點距離聚點中心的歐氏距離的函數：

string computerDistance(Point *p_totalPoints,vector<Point> &classPoints);

將各個點劃分到相應類的函數：

void kMeansClustering(int classNum,vector<Point> totalPoints,vector<Point> classPoints);

（三）核心代碼（部分）

（1）初始化數據集合函數：

void initDataset(int classNum,vector<Point>dataVector,vector<Point>&classPoints, 
         vector<Point>&totalPoints) 
{ 
  int i,j; 
  Point point; 
  for(i=0,j=1; i<dataVector.size(); i++) 
  { 
    if(j<=classNum) //classNum表示聚類的編號 
    { 
      point.x=dataVector[i].x; 
      point.y=dataVector[i].y; 
      point.distance=dataVector[i].distance; 
      point.className=converToString(j);//將整型類型轉換成字符串類型 
      classPoints.push_back(point); 
      j++; 
    } 
    point.x=dataVector[i].x; 
    point.y=dataVector[i].y; 
    point.distance=dataVector[i].distance; 
    totalPoints.push_back(point); 
  } 
}

（2）K-means函數：

void kMeansClustering(int classNum,vector<Point> totalPoints,vector<Point> classPoints) 
{ 
  float tempX=0;//計算聚類中所有數據點X的均值 
  float tempY=0;//計算聚類中所有數據點Y的均值 
  int count=0; //記錄每一個類中數據點的數目 
  float errorX=INT_MAX; //假設初始時誤差最大 
  float errorY=INT_MAX; 
  vector<Point>::iterator p_totalPoints; 
  vector<Point>::iterator p_classPoints; 
  Point temp; 
  int i; 
  while(errorX > 1e-6 && errorY > 1e-6) 
  { 
    for(p_totalPoints=totalPoints.begin(); p_totalPoints!=totalPoints.end(); p_totalPoints++) 
    { 
      //將所有的點就近分類 
      string className=computerDistance(p_totalPoints,classPoints); 
      (*p_totalPoints).className=className; 
    } 
    errorX=0; 
    errorY=0; 
    //按照均值重新劃分聚類中心點 
    for(p_classPoints=classPoints.begin(); p_classPoints!=classPoints.end(); p_classPoints++) 
    { 
      count=0; 
      tempX=0; 
      tempY=0; 
      cout<<"Partition to cluster center "<<p_classPoints->className<<":"; 
      for(p_totalPoints=totalPoints.begin(); p_totalPoints!=totalPoints.end(); p_totalPoints++) 
      { 
        if((*p_totalPoints).className==(*p_classPoints).className) 
        { 
          cout<<" ("<<(*p_totalPoints).x<<","<<(*p_totalPoints).y<<") "; 
          count++; 
          tempX+=(*p_totalPoints).x; 
          tempY+=(*p_totalPoints).y; 
        } 
      } 
      cout<<endl; 
      tempX /=count; 
      tempY /=count; 
      errorX +=fabs(tempX - (*p_classPoints).x); 
      errorY +=fabs(tempY - (*p_classPoints).y); 
      //計算X與Y均值 
      (*p_classPoints).x=tempX; 
      (*p_classPoints).y=tempY; 
    } 
    int i=0; 
    for(p_classPoints=classPoints.begin(); p_classPoints!=classPoints.end(); p_classPoints++,i++) 
    { 
      cout<<"Cluster center "<<i+1<<": x="<<(*p_classPoints).x<<" y="<<(*p_classPoints).y<<endl; 
    } 
    cout<<"-----------------------------------------------------------------"<<endl; 
  } 
  cout<<"Result value convergence"<<endl; 
  i=0; 
  for(p_classPoints=classPoints.begin(); p_classPoints!=classPoints.end(); p_classPoints++,i++) 
  { 
    cout<<"Cluster center "<<i+1<<": x="<<(*p_classPoints).x<<" y="<<(*p_classPoints).y<<endl; 
  } 
  cout<<"-----------------------------------------------------------------"<<endl; 
}

以上是“C語言如何實現K-Means算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！