数据挖掘中采用VC编程的Kmean算法示例

// KMean.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <stdlib.h> #include <assert.h> #include <string.h> #include <time.h> #include <stdio.h> #define MAX_ITEM_SUM 100000 char* infile; // 输入文件，从命令行输入 int k; // k个集合，从命令行输入 int itemSum; // 输入文件中包含的数字个数 int * items; // 从文件中的读取的数字数组，经过KMSort()排序后，形成由小到大排列的数组 int *mids; // 中值集合，实际存放的是中值在items中的索引值，根据k和itemSum 产生，每次计算生成新 // 的集合后重新选择中值 int *midsBak; // 中值备份集合，重新生成中值集合和备份集合比较，如果一样，则停止计算 int * kSet; // itemSum个元素的数组，每个元素表示items中同序号的元素所属集合，元素取值0到k-1， // 对应该集合的中值在mids中的序号 /* 从输入文件读出数据，数据只能是数值型，存放在items中，并返回数据个数 */ int KMReadItem( ) { FILE* pfile; int i = 0; int j; pfile = fopen(infile, "r"); assert(pfile);//断言，判断值是否为真 while(!feof(pfile) && i<MAX_ITEM_SUM) { if(1 == fscanf(pfile,"%d", items+i)) i++; } assert(i<MAX_ITEM_SUM); return i; } /*allocate mem for mids, midsbak, kSet */ void KMInit( ) { mids = (int*)malloc(k*sizeof(int));//中值集合 midsBak = (int*)malloc(k*sizeof(int));//中值备份集合 kSet = (int*)malloc(itemSum*sizeof(int*));//所有的数字 }//动态分配存储空间 /* 释放 */ void KMFree() { free (mids); free(midsBak); free(kSet); } /*交换位置*/ inline void swap(int& a, int&b) { int t = a; a = b, b = t; } /* 数据排序 */ void KMSort(int * items, int itemSum) { int i,j; for(i = 1; i<itemSum; i++) { for(j = i-1; j>=0; j--) { if(items[j+1]<items[j]) swap(items[j+1],items[j]); else break; } } } int Rand(int seed) { srand((unsigned)time( NULL )); return rand()%seed; } /* 根据k和itemSum产生mids初值 */ void KMInitSeeds() { int i,j; for (i = 0; i<k; i++) { RandAgain: midsBak[i] = mids[i] = Rand(itemSum);//(2*i+1)*itemSum/(2*k)+k/2; for(j = 0; j<i;j++) { if(mids[i] == mids[j]) goto RandAgain; } } KMSort(midsBak,k); KMSort(mids,k); } /* 返回和item最接近的中值序号 */ int KMNearlest( int item) { int i; unsigned int t = -1; // int s; if(item<=items[mids[0]])return 0; if(item>=items[mids[k-1]])return k-1; for(i = 1; i<k; i++) { if((item<items[mids[i]])) { if((item-items[mids[i-1]])>(items[mids[i]]-item)) { return i; } else return i-1; } } assert(0); return 0; } /* 找出并返回第i个集合的中值 */ int KMmid(int i ) { int sum = 0; int j; int lastone; for (j = 0; j<itemSum; j++) { if(kSet[j] == i) { sum ++; lastone = j; } } return lastone - sum/2; } /* 根据中值产生最小值集合，然后在求出新的中值，如果新的中值和中值备份数据不一致，则继续产生新的集合，否则，结束 */ void KMRun() { int i; int flag = 1; while(flag){ for(i = 0; i<itemSum; i++) { kSet[i] = KMNearlest(items[i]); } for(i = 0; i<k; i++) { mids[i] = KMmid(i); } flag = 0; for(i = 0; i<k; i++) { if(mids[i] != midsBak[i]) { midsBak[i] = mids[i]; flag = 1; } } } } /* 输出计算结果 */ void KMOut() { int i,j=0,c; FILE* pfile; pfile = fopen("result.txt","w"); for(i = 0; i<k; i++) { fprintf(pfile, "\ngroup %d:", i); c = 0; while(kSet[j] == i) { if(c++%20 == 0) fprintf(pfile,"\n");//换行输出 fprintf(pfile, " %d", items[j++]); } } fclose(pfile); } /* 算法主程序 */ void KMean() { itemSum = KMReadItem();//读数据项 KMInit();//变量分配空间 KMSort(items,itemSum);//数据项排序 KMInitSeeds();//初始化种子点 KMRun();//聚类 KMOut(); KMFree(); } /* 主程序 */ int main(int argc, char* argv[]) { if(argc<3) { printf("usage: kmean k infile"); exit(0); } k = atoi(argv[1]); infile = (char*)malloc(strlen(argv[2])+1); strcpy(infile,argv[2]); items = (int*)malloc(MAX_ITEM_SUM*sizeof(int)); KMean( ); free(infile); free(items); return 1; }