C語言實現(xiàn)K-Means算法
一、聚類和聚類算法
聚類，就是將數(shù)據(jù)對象劃分成若干個類，在同一個類中的對象具有較高的相似度，而不同的類相似度較小。聚類算法將數(shù)據(jù)集合進行劃分，分成彼此相互聯(lián)系的若干類，以此實現(xiàn)對數(shù)據(jù)的深入分析和數(shù)據(jù)價值挖掘的初步處理階段。例如在現(xiàn)代商業(yè)領域，聚類分析算法可以從龐大的數(shù)據(jù)集合中對消費者的消費習慣、消費傾向，以方便決策者制訂消費策略?？傊鳛閿?shù)據(jù)挖掘中的一個模塊，聚類分析算法可以作為一個單獨的工具已發(fā)現(xiàn)數(shù)據(jù)庫中分布的一些深層信息，并概括出每一類的特點。聚類分析算法也可作為數(shù)據(jù)挖掘算法中其他分析算法的一個預處理步驟。
在數(shù)據(jù)挖掘領域，聚類分析算法可以分為一下幾個大類，包括劃分法、層次法、基于密度的方法、基于網絡的方法和基于模型的方法。基于劃分的基本思想就是通過迭代的方法將含有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ā)生變化，轉到（2），否則結束迭并輸出結果。
三、K-means算法實現(xiàn)
（一）實現(xiàn)思路
通過以上對K-means算法的了解，該算法主要是通過迭代的思想來求解K個聚類的中心。由于傳統(tǒng)數(shù)組需要先定義再使用，且在使用的過程中不能實現(xiàn)數(shù)組長度的動態(tài)增長。同時考慮到設計該算法時，沒有涉及到在迭代過程中各個數(shù)據(jù)點的插入和刪除，各個數(shù)據(jù)點具體劃分到那個聚類中，是由結構體成員變量中的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時，則結束迭代并輸出收斂后的K歌聚類的中心坐標。
（二）變量和函數(shù)說明
（1）定義結構體類型，用于存儲數(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ù)聲明
字符串轉換函數(shù)：將整型變量轉換成字符串類型：
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);
將各個點劃分到相應類的函數(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);//將整型類型轉換成字符串類型
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; //假設初始時誤差最大
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;
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了直接插入排序與折半插入排序，有需要的朋友可以參考一下2013-12-12
隊列只允許一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO的性質；隊列可用數(shù)組和鏈表 的方法實現(xiàn)，使用鏈表的結構實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組節(jié)，出隊列時刪去首元素需要將整個數(shù)組前移，效率比較低2023-02-02
本文主要介紹了C語言動態(tài)內存管理的實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家詳細介紹了如何利用c++實現(xiàn)解析zip文件,并對流式文件pptx內容的修改,文中的示例代碼講解詳細,有需要的小伙伴可以參考一下2023-12-12
本篇文章重點講解了兩種創(chuàng)建對象的方式：一種是在棧上創(chuàng)建，形式和定義普通變量類似；另外一種是在堆上使用 new 關鍵字創(chuàng)建，必須要用一個指針指向它，下面和小編一起來學習下面為文章的內容2021-09-09
這篇文章主要介為大家詳細紹了如何使用C語言繪制統(tǒng)計圖中的曲線圖,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-02-02
這篇文章主要介紹了C++中的RTTI機制詳解,本文詳細的總結了RTTI的相關知識,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細介紹了C++隨機生成迷宮算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
本文將通過圖片重點為大家介紹一下C語言中快速排序三種方法的單趟實現(xiàn)：分別是hoare法、挖坑法、雙指針法，文中示例代碼講解詳細，感興趣的可以了解一下2022-06-06
C語言實現(xiàn)選擇排序、直接插入排序、冒泡排序的示例
這篇文章主要介紹了C++實現(xiàn)選擇排序、直接插入排序、冒泡排序的代碼示例,相當簡潔直觀,也是算法和數(shù)據(jù)結構學習中的基礎,需要的朋友可以參考下2016-02-02