欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)K-Means算法

 更新時間:2018年02月23日 11:21:26   作者:Deng笨蛋  
這篇文章主要為大家詳細介紹了C語言實現(xiàn)K-Means算法,具有一定的參考價值,感興趣的小伙伴們可以參考一下

一、聚類和聚類算法

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

在數(shù)據(jù)挖掘領(lǐng)域,聚類分析算法可以分為一下幾個大類,包括劃分法、層次法、基于密度的方法、基于網(wǎng)絡(luò)的方法和基于模型的方法?;趧澐值幕舅枷刖褪峭ㄟ^迭代的方法將含有N個數(shù)據(jù)對象的數(shù)據(jù)集分成K個聚類。具體的步驟就是,用戶先給出要劃分的個數(shù),然后通過一定的算法反復的進行迭代,使得每次得到的分組比前一次更加接近預期目標,是否優(yōu)化的判定標準是同組數(shù)據(jù)之間不同數(shù)據(jù)之間的相似程度,同組數(shù)據(jù)相似程度越大,組間似程度越小越優(yōu)化。

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

二、K-means算法實現(xiàn)步驟

通過對聚類和K-Means算法思想的了解,C語言算法的實現(xiàn)過程如下:

(1)通過文件輸入N個數(shù)據(jù)點,并選取其中K(K<N)個數(shù)據(jù)點作為初始聚類中心;

(2)對剩余的數(shù)據(jù)點分別計算到各個聚類聚點中心的歐氏距離,并將該點劃分到最近的類中;

(3)重新計算各個聚類的聚點中心;

(4)與之前的聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)到(2),否則結(jié)束迭并輸出結(jié)果。

三、K-means算法實現(xiàn)

(一)實現(xiàn)思路

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

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

(二)變量和函數(shù)說明

(1)定義結(jié)構(gòu)體類型,用于存儲數(shù)據(jù)點坐標、所在聚類、與聚類中心距離

typedef struct point

{

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

}Point;

(2)變量聲明

vector<Point> dataVector:存儲從文件讀取的數(shù)據(jù)

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

vector<Point> &totalPoints):存儲所有的數(shù)據(jù)點

(3)函數(shù)聲明

字符串轉(zhuǎn)換函數(shù):將整型變量轉(zhuǎn)換成字符串類型:

string converToString(int x);

讀入數(shù)據(jù)函數(shù):從文件讀入坐標數(shù)據(jù):

vector<Point> readDataFile(string fileName);

初始化數(shù)據(jù)集合函數(shù):

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

計算各個數(shù)據(jù)點距離聚點中心的歐氏距離的函數(shù):

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

將各個點劃分到相應(yīng)類的函數(shù):

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

(三)核心代碼(部分)

(1)初始化數(shù)據(jù)集合函數(shù):

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);//將整型類型轉(zhuǎn)換成字符串類型 
      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函數(shù):

void kMeansClustering(int classNum,vector<Point> totalPoints,vector<Point> classPoints) 
{ 
  float tempX=0;//計算聚類中所有數(shù)據(jù)點X的均值 
  float tempY=0;//計算聚類中所有數(shù)據(jù)點Y的均值 
  int count=0; //記錄每一個類中數(shù)據(jù)點的數(shù)目 
  float errorX=INT_MAX; //假設(shè)初始時誤差最大 
  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; 
} 

以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

  • C++ 繼承,虛繼承(內(nèi)存結(jié)構(gòu))詳解

    C++ 繼承,虛繼承(內(nèi)存結(jié)構(gòu))詳解

    C++繼承和虛繼承的內(nèi)存模型是一個老生常談的話題,實現(xiàn)方法主要依賴于編譯器,本文從多個角度通過代碼詳解C++中虛繼承的內(nèi)存模型知識,感興趣的朋友跟隨小編一起看看吧
    2021-09-09
  • 淺談mwArray和一般數(shù)組的區(qū)別

    淺談mwArray和一般數(shù)組的區(qū)別

    下面小編就為大家?guī)硪黄獪\談mwArray和一般數(shù)組的區(qū)別。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • 二叉樹遍歷 非遞歸 C++實現(xiàn)代碼

    二叉樹遍歷 非遞歸 C++實現(xiàn)代碼

    對于二叉樹,有前序、中序以及后序三種遍歷方法。因為樹的定義本身就是遞歸定義,因此采用遞歸的方法去實現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法,就要采用棧去模擬實現(xiàn)
    2013-09-09
  • C語言 坐標移動詳解及實例代碼

    C語言 坐標移動詳解及實例代碼

    這篇文章主要介紹了C語言 坐標移動詳解及實例代碼的相關(guān)資料,需要的朋友可以參考下
    2017-01-01
  • C語言中的強符號和弱符號介紹

    C語言中的強符號和弱符號介紹

    這篇文章主要介紹了C語言中的強符號和弱符號介紹,本文用多個實例來講解強符號和弱符號,需要的朋友可以參考下
    2015-03-03
  • C++中變量的類型與作用域?qū)W習教程

    C++中變量的類型與作用域?qū)W習教程

    這篇文章主要介紹了C++中變量的類型與作用域,C++是面向?qū)ο蟮木幊陶Z言,一定要注意局部變量與全局變量的作用范圍,需要的朋友可以參考下
    2016-05-05
  • 單詞小助手C語言版

    單詞小助手C語言版

    這篇文章主要為大家詳細介紹了C語言版的單詞小助手,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-10-10
  • C++可擴展性與多線程超詳細精講

    C++可擴展性與多線程超詳細精講

    這篇文章主要介紹了C++可擴展性與多線程,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習吧
    2022-10-10
  • 淺析C++淺拷貝與深拷貝的聯(lián)系和區(qū)別

    淺析C++淺拷貝與深拷貝的聯(lián)系和區(qū)別

    在c++中,深拷貝和淺拷貝也算是一個難點,特別是對于初學者來說,往往在不知道兩者區(qū)別的情況下而錯誤的使用了淺拷貝,從而導致了野指針之類的問題,但是又因為缺少理解所以很難定位到問題所在
    2022-09-09
  • C++使用fdk-aac實現(xiàn)將音頻PCM編碼成aac

    C++使用fdk-aac實現(xiàn)將音頻PCM編碼成aac

    mp4的音頻流通常是aac編碼,我們做音視頻采集的時候就需要將,采集的音頻PCM編碼成aac,本文就來為大家介紹一下C++如何使用fdk-aac實現(xiàn)將音頻PCM編碼成aac吧
    2023-11-11

最新評論