数据挖掘报告,聚类分析 kmeans算法

kmeans算法 数据源为synthetic_control.data

数据挖掘实验报告

班级： 姓名： 学号：

1. 数据来源描述

本次数据挖掘实验的数据源来自加州大学计算机与信息院，是用于合成控制图时间序列聚类分析的一组数据。数据集中一共包含600组数据，每一组数据都有60个分量，也就是数据是60维的。数据一共可以分成6个聚类，分别是：

1-100 Normal （正常） 101-200 Cyclic （循环）

201-300 Increasing trend （增加趋势） 301-400 Decreasing trend （减少趋势） 401-500 Upward shift （上升变化） 501-600 Downward shift （下降变化）

2. 数据预处理

由于本数据集的数据维数较多，所以本实验采用了结构体来存储60维的数据，并使用指针来进行对数据的操作，以提高速度。在数据预处理过程中，首先将数据从data文件中读出，后依次存入结构体数组dataset[600]中。 3. k-means聚类算法

k-means 算法接受参数 k ；然后将事先输入的

n个数据对

象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对

kmeans算法 数据源为synthetic_control.data

象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。 （1）算法思路：

首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然 后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。 （2）算法步骤：

step.1---初始化距离K个聚类的质心（随机产生） step.2---计算所有数据样本与每个质心的欧氏距离，将数据样本加入与其欧氏距离最短的那个质心的簇中（记录其数据样本的编号）

kmeans算法 数据源为synthetic_control.data

step.3---计算现在每个簇的质心，进行更新，判断新质心是否与原质心相等，若相等，则迭代结束，若不相等，回到step2继续迭代。

4. 数据挖掘实现的源代码

//111060850.cpp KMeans聚类算法 //

#include "stdafx.h" #include<iostream> #include<math.h> #include<stdlib.h> #include<string> #include<fstream> #include<time.h>

using namespace std;

const int N=36000; //数据个数 const int D=60; //数据维度

struct DataSet{ //用来存储数据的结构体 double arg[D]; };

const int K=6; //集合个数

int *CenterIndex; //质心索引集合

//struct DataSet *Center; //质心集合 //struct DataSet *CenterCopy[];

DataSet Center[K]; //保存现在的质心

DataSet CenterCopy[K]; //保存上一次迭代中的质心 //double *DataSet;

int Cluster[6][N/D]; //保存每个簇包含的数据的索引值 int *Top; ifstream fin; char ch;

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

kmeans聚类算法采用的是给定类的个数K,将N个元素(对象)分配到K个类中去 使得类内对象之间的相似性最大,而类之间的相似性最小 */ //数据存储在结构体中

//函数声明部分

void InitData(struct DataSet* dataset);

//对数据集进行初始化，从文件中将其读取出后转化为double型依次存入结构

kmeans算法 数据源为synthetic_control.data

体中

void InitCenter(struct DataSet* dataset); //初始化质心

void CreateRandomArray(int n,int k,int *centerIndex); //随机产生一组索引值，用于初始化质心

void CopyCenter(struct DataSet* dataset); //复制保存上一次迭代的质心

void UpdateCluster(struct DataSet* dataset); //更新簇

void UpdateCenter(struct DataSet* dataset); //更新质心

int GetIndex(struct DataSet* dataset,struct DataSet* centerIndex); //本程序的核心，计算每一数据元素属于哪一个聚类，并返回其索引值 void AddtoCluster(int index,int value); //根据索引值将数据元素的索引加入到簇之中 void print(struct DataSet* dataset);

bool IsEqual(struct DataSet* value1,struct DataSet* value2); //判断现有质心和上一次迭代的质心是否相等 double DoubletoString(const char* str); //string转化为double型的函数

double Euclidean(struct DataSet* value1,struct DataSet* value2); //计算欧几里得距离函数

int main(int argc, char* argv[]) {

int Flag=1;

double ttime=0,start=0,end=0; start=clock();

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

/* for(int i=0;i<N/D;i++) {for(int j=0;j<D;j++)

cout<<dataset[i].arg[j]<<" "; cout<<endl; }*/

while(Flag) {

UpdateCluster(dataset); UpdateCenter(dataset);

if(IsEqual(Center,CenterCopy)) {

Flag=0; }

kmeans算法 数据源为synthetic_control.data

else {

CopyCenter(dataset); } }

end=clock();

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

return 0; }

void InitData(struct DataSet* dataset) {

int i=0,j=0;

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

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

//从文件中读入数据，存入fDataSet数组中，此数组为string类型 //然后通过转化成double型存入DataSet数组之中。 cout<<"开始从文件读入数据"<<endl; fin.open("synthetic_control.data"); for(i=0;i<N/D;i++) for(j=0;j<D;j++) {

while(fin.peek()!='\n'&&fin.peek()!=' ') //从文件中取出数字（字符串形式），略过空格和换行 { fin>>ch;

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<<"数据已读入"<<endl; InitCenter(dataset); UpdateCluster(dataset); }

kmeans算法 数据源为synthetic_control.data

void InitCenter(struct DataSet* dataset) {

int i=0;

//产生随即的K个<N的不同的序列

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

for(int j=0;j<D;j++)

Center[i].arg[j] = dataset[CenterIndex[i]].arg[j]; //cout<<Center[i]<<" "<<endl; }

CopyCenter(dataset); }

void CreateRandomArray(int n,int k,int *centerIndex) {

int i=0,j=0;

for(i=0;i<K;i++) {

int a=rand()%n; for(j=0;j<i;j++) {

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

if(j>=i) {

centerIndex[i]=a; } else {

i--; } } }

void CopyCenter(struct DataSet* dataset) {

int i=0;

for(i=0;i<K;i++)

kmeans算法 数据源为synthetic_control.data

{

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

void UpdateCluster(struct DataSet* dataset) {

int i=0; int tindex;

for(;i<K;i++) {

Top[i]=0; }

for(i=0;i<N/D;i++) {

tindex=GetIndex(&dataset[i],Center); //tindex是指dataset[i]属于第tindex个簇

AddtoCluster(tindex,i); //把dataset[i]加入到所属的簇当中 } }

int GetIndex(struct DataSet* value,struct DataSet* center) {

int i=0;

int index=i;

// double min=fabs(value-center[i]); double min=Euclidean(value,&center[i]); for(i=0;i<K;i++) {

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

index=i;

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

return index; }

kmeans算法 数据源为synthetic_control.data

void AddtoCluster(int index,int value) {

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

double DoubletoString(const char* str) {

double temp = 0.0,wt = 10.0; bool flag = true; int i;

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

if(flag&&*(str+i)==46) //若遇到小数点则置标志位为false，则后面读入的

flag = false; //char转化为小数形式

else if(flag) //整数部分 temp = (int)(*(str+i)-48)+temp*10; else{

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

return temp; }

double Euclidean(struct DataSet* value1,struct DataSet* value2) {

double temp=0,sum=0; for(int i=0;i<D;i++) sum = (value1->arg[i]-value2->arg[i])*(value1->arg[i]-value2->arg[i]); temp = sqrt(sum); return temp; }