數(shù)據(jù)挖掘報告,聚類分析 kmeans算法

本文格式為Word版，下載可任意編輯——數(shù)據(jù)挖掘報告,聚類分析kmeans算法

kmeans算法數(shù)據(jù)源為synthetic_control.data

數(shù)據(jù)挖掘試驗報告

班級：姓名：學(xué)號：

1.數(shù)據(jù)來源描述

本次數(shù)據(jù)挖掘試驗的數(shù)據(jù)源來自加州大學(xué)計算機與信息院，是用于合成控制圖時間序列聚類分析的一組數(shù)據(jù)。數(shù)據(jù)集中一共包含600組數(shù)據(jù)，每一組數(shù)據(jù)都有60個分量，也就是數(shù)據(jù)是60維的。數(shù)據(jù)一共可以分成6個聚類，分別是：

1-100Normal（正常）101-200Cyclic（循環(huán)）

201-300Increasingtrend（增加趨勢）301-400Decreasingtrend（減少趨勢）401-500Upwardshift（上升變化）501-600Downwardshift（下降變化）

2.數(shù)據(jù)預(yù)處理

由于本數(shù)據(jù)集的數(shù)據(jù)維數(shù)較多，所以本試驗采用了結(jié)構(gòu)體來存儲60維的數(shù)據(jù)，并使用指針來進行對數(shù)據(jù)的操作，以提高速度。在數(shù)據(jù)預(yù)處理過程中，首先將數(shù)據(jù)從data文件中讀出，后依次存入結(jié)構(gòu)體數(shù)組dataset[600]中。3.k-means聚類算法

k-means算法接受參數(shù)k；然后將事先輸入的

n個數(shù)據(jù)對

象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對

kmeans算法數(shù)據(jù)源為synthetic_control.data

象相像度較高；而不同聚類中的對象相像度較小。聚類相像度是利用各聚類中對象的均值所獲得一個“中心對象〞（引力中心）來進行計算的。

K-means算法是最為經(jīng)典的基于劃分的聚類方法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一。K-means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。（1）算法思路：

首先從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相像度（距離），分別將它們分派給與其最相像的（聚類中心所代表的）聚類；然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復(fù)這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù).k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

該算法的最大優(yōu)勢在于簡單和快速。算法的關(guān)鍵在于初始中心的選擇和距離公式。（2）算法步驟：

step.1初始化距離K個聚類的質(zhì)心（隨機產(chǎn)生）step.2計算所有數(shù)據(jù)樣本與每個質(zhì)心的歐氏距離，將數(shù)據(jù)樣本參與與其歐氏距離最短的那個質(zhì)心的簇中（記錄其數(shù)據(jù)樣本的編號）

kmeans算法數(shù)據(jù)源為synthetic_control.data

step.3計算現(xiàn)在每個簇的質(zhì)心，進行更新，判斷新質(zhì)心是否與原質(zhì)心相等，若相等，則迭代終止，若不相等，回到step2繼續(xù)迭代。

4.數(shù)據(jù)挖掘?qū)崿F(xiàn)的源代碼

//111060850.cppKMeans聚類算法//

#includestdafx.h#includeiostream#includemath.h#includestdlib.h#includestring#includefstream#includetime.h

usingnamespacestd;

constintN=36000;//數(shù)據(jù)個數(shù)constintD=60;//數(shù)據(jù)維度

structDataSet{//用來存儲數(shù)據(jù)的結(jié)構(gòu)體doublearg[D];};

constintK=6;//集合個數(shù)

int*CenterIndex;//質(zhì)心索引集合

//structDataSet*Center;//質(zhì)心集合//structDataSet*CenterCopy[];

DataSetCenter[K];//保存現(xiàn)在的質(zhì)心

DataSetCenterCopy[K];//保存上一次迭代中的質(zhì)心//double*DataSet;

intCluster[6][N/D];//保存每個簇包含的數(shù)據(jù)的索引值int*Top;ifstreamfin;charch;

stringfDataSet[N/D][D];/*算法描述:

kmeans聚類算法采用的是給定類的個數(shù)K,將N個元素(對象)分派到K個類中去使得類內(nèi)對象之間的相像性最大,而類之間的相像性最小*///數(shù)據(jù)存儲在結(jié)構(gòu)體中

//函數(shù)聲明部分

voidInitData(structDataSet*dataset);

//對數(shù)據(jù)集進行初始化，從文件中將其讀取出后轉(zhuǎn)化為double型依次存入結(jié)構(gòu)

kmeans算法數(shù)據(jù)源為synthetic_control.data

體中

voidInitCenter(structDataSet*dataset);//初始化質(zhì)心

voidCreateRandomArray(intn,intk,int*centerIndex);//隨機產(chǎn)生一組索引值，用于初始化質(zhì)心

voidCopyCenter(structDataSet*dataset);//復(fù)制保存上一次迭代的質(zhì)心

voidUpdateCluster(structDataSet*dataset);//更新簇

voidUpdateCenter(structDataSet*dataset);//更新質(zhì)心

intGetIndex(structDataSet*dataset,structDataSet*centerIndex);//本程序的核心，計算每一數(shù)據(jù)元素屬于哪一個聚類，并返回其索引值voidAddtoCluster(intindex,intvalue);//根據(jù)索引值將數(shù)據(jù)元素的索引參與到簇之中voidprint(structDataSet*dataset);

boolIsEqual(structDataSet*value1,structDataSet*value2);//判斷現(xiàn)有質(zhì)心和上一次迭代的質(zhì)心是否相等doubleDoubletoString(constchar*str);//string轉(zhuǎn)化為double型的函數(shù)

doubleEuclidean(structDataSet*value1,structDataSet*value2);//計算歐幾里得距離函數(shù)

intmain(intargc,char*argv[]){

intFlag=1;

doublettime=0,start=0,end=0;start=clock();

DataSetdataset[N/D];InitData(dataset);

/*for(inti=0;iN/D;i++){for(intj=0;jD;j++)

coutdataset[i].arg[j];coutendl;}*/

while(Flag){

UpdateCluster(dataset);UpdateCenter(dataset);

if(IsEqual(Center,CenterCopy)){

Flag=0;}

kmeans算法數(shù)據(jù)源為synthetic_control.data

else{

CopyCenter(dataset);}}

end=clock();

ttime=(double)(end-start)/CLOCKS_PER_SEC;print(dataset);getchar();

return0;}

voidInitData(structDataSet*dataset){

inti=0,j=0;

CenterIndex=newint[sizeof(int)*K];Top=newint[sizeof(int)*K];

//Cluster=newint*[sizeof(int*)*K];

//從文件中讀入數(shù)據(jù)，存入fDataSet數(shù)組中，此數(shù)組為string類型//然后通過轉(zhuǎn)化成double型存入DataSet數(shù)組之中。cout開始從文件讀入數(shù)據(jù)endl;fin.open(synthetic_control.data);for(i=0;iN/D;i++)for(j=0;jD;j++){

while(fin.peek()!='\n'fin.peek()!='')//從文件中取出數(shù)字（字符串形式），略過空格和換行{finch;

fDataSet[i][j]=fDataSet[i][j]+ch;

dataset[i].arg[j]=DoubletoString(fDataSet[i][j].c_str());}

while(fin.peek()=='\n'||fin.peek()=='')fin.get();}

fin.close();

cout數(shù)據(jù)已讀入endl;InitCenter(dataset);UpdateCluster(dataset);}

kmeans算法數(shù)據(jù)源為synthetic_control.data

voidInitCenter(structDataSet*dataset){

inti=0;

//產(chǎn)生隨即的K個N的不同的序列

CreateRandomArray(N/D,K,CenterIndex);for(i=0;iK;i++){

for(intj=0;jD;j++)

Center[i].arg[j]=dataset[CenterIndex[i]].arg[j];//coutCenter[i]endl;}

CopyCenter(dataset);}

voidCreateRandomArray(intn,intk,int*centerIndex){

inti=0,j=0;

for(i=0;iK;i++){

inta=rand()%n;for(j=0;ji;j++){

if(centerIndex[j]==a)break;}

if(j=i){

centerIndex[i]=a;}else{

i--;}}}

voidCopyCenter(structDataSet*dataset){

inti=0;

for(i=0;iK;i++)

kmeans算法數(shù)據(jù)源為synthetic_control.data

{

CenterCopy[i]=Center[i];}}

voidUpdateCluster(structDataSet*dataset){

inti=0;inttindex;

for(;iK;i++){

Top[i]=0;}

for(i=0;iN/D;i++){

tindex=GetIndex(dataset[i],Center);//tindex是指dataset[i]屬于第tindex個簇

AddtoCluster(tindex,i);//把dataset[i]參與到所屬的簇當中}}

intGetIndex(structDataSet*value,structDataSet*center){

inti=0;

intindex=i;

//doublemin=fabs(value-center[i]);doublemin=Euclidean(value,center[i]);for(i=0;iK;i++){

if(Euclidean(value,center[i])min){

index=i;

min=Euclidean(value,center[i]);}}

returnindex;}

kmeans算法數(shù)據(jù)源為synthetic_control.data

voidAddtoCluster(intindex,intvalue){

Cluster[index][Top[index]]=value;Top[index]++;}

doubleDoubletoString(constchar*str){

doubletemp=0.0,wt=10.0;boolflag=true;inti;

for(i=0;i*(str+i)!='\0';i++){

if(flag*(str+i)==46)//若遇到小數(shù)點則置標志位為false，則后面讀入的

flag=false;//char轉(zhuǎn)化為小數(shù)形式

elseif(flag)//整數(shù)部分temp=(int)(*(str+i)-48)+temp*10;else{

temp=temp+(int)(*(str+i)-48)/wt;//小數(shù)部分wt=wt*10;}}

returntemp;}

doubleEuclidean(structDataSet*value1,structDataSet*value2){

doubletemp=0,sum=0;for(inti=0;iD;i++)sum=(value1-arg[i]-value2-arg[i])*(value1-arg[i]-value2-arg[i]);temp=sqrt(sum);returntemp;}

boolIsEqual(structDataSet*value1,structDataSet*value2){

inti;

for(i=0;iK;i++)

kmeans算法數(shù)據(jù)源為synthetic_control.data

{

for(intj=0;jD;j++)

if(value1[i].arg[j]!=value2[i].arg[j])return0;}

return1;}

voidUpdateCenter(structDataSet*dataset){

inti=0,j=0;doublesum;

for(i=0;iK;i++){

for(intd=0;dD;d++){

sum=0.0;

for(j=0;jTop[i];j++){

sum+=dataset[Cluster[i][j]].arg[d];}

if(Top[i]0){

Center[i].arg[d]=sum/Top[i];}}}}

voidprint(structDataSet*dataset){

inti,j,d;

ofstreamfout(result.txt);

cout====================================endl;fout====================================endl;for(i=0;iK;i++){

cout第i組：質(zhì)心為：;for(d=0;dD;d++)

coutCenter[i].arg[d]'\t';coutendl;

cout數(shù)據(jù)元素為:\n;

kmeans算法數(shù)據(jù)源為synthetic_control.data

////輸入文件中

fout第i組：質(zhì)心為：;for(d=0;dD;d++)

foutCenter[i].