kmean.cpp

数据挖掘中的聚类算法简单实例

// 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>

#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;
}