求助：K-means聚类算法！

Question

已有二位矢量组，现在需要用k-均值聚类方法将其分类，使用VC怎么实现呢？

Answer 1

找本模式识别看看，好象有算法流程的，比ISODATA简单

Answer 2

前一阵刚写过一个，呵呵// kMeans.h: interface for the kMeans class.
//
//////////////////////////////////////////////////////////////////////#if !defined(AFX_KMEANS_H__967B7DA0_1B78_448B_95B0_C0F8B9A125DB__INCLUDED_)
#define AFX_KMEANS_H__967B7DA0_1B78_448B_95B0_C0F8B9A125DB__INCLUDED_#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000#include <afxtempl.h>
#include "Clustering.h"
class kMeans:public CClustering
{
public:
BOOL Cluster(vector<POINT> sample); //K均值聚类
kMeans();
virtual ~kMeans();protected:
double GetPolicy(); //准则函数
void Initial(int nK); //初始聚类中心
BOOL SetNewCenter(); //求新聚类中心向量值
void AssignSample(); //分配样本到各聚类中心
void ShowResult(CArray<POINT,POINT>* data,CDC* pDC); //显示一部分算法结果private:
vector<CLUSTER_CENTER> m_center; //样本子集
vector<POINT> m_sample; //全部样本集
};#endif // !defined(AFX_KMEANS_H__967B7DA0_1B78_448B_95B0_C0F8B9A125DB__INCLUDED_)// kMeans.cpp: implementation of the kMeans class.
//
//////////////////////////////////////////////////////////////////////#include "stdafx.h"
#include "Cluster.h"
#include "kMeans.h"#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////kMeans::kMeans()
{}kMeans::~kMeans()
{}BOOL kMeans::Cluster(vector<POINT> sample)
{
const int ITERATOR_TIMES=20; //迭代次数上限
int nTimes=0,nType=1,i; //nTimes实际迭代次数，nType最佳决策时的K值
double fMinWeight=-1; //求最佳决策用 for(i=0;i<sample.size();i++) //保存样本到成员变量
{
m_sample.push_back(sample[i]);
} for(i=0;i<m_sample.size()-1;i++) //尝试不同的K值k:[2,样本数-1]
{
Initial(i+1); //初始聚类中心
do
{
AssignSample(); //分配样本到聚类中心
if(SetNewCenter()) //各聚类中心新向量值，并判断循环结束与否
break;
}while(nTimes++<ITERATOR_TIMES);

double fWeight=GetPolicy()*(i+1)*(i+1); //得到该聚类的评价
CString str;
str.Format("\n分成%d类时，准则函数值为：%f",i+1,fWeight);
AfxMessageBox(str);
TRACE("\n分成%d类时，准则函数值为：%f",i+1,fWeight);
if(fMinWeight==-1)
fMinWeight=fWeight;
if(fWeight<fMinWeight)
{
fMinWeight=fWeight; //求最佳决策
nType=i+1;
}
nTimes=0;
}

TRACE("\n求得在决策函数下最优分类为k=%d",nType);
Initial(nType); //初始聚类中心
//Initial(2); //初始聚类中心 do
{
AssignSample();
if(SetNewCenter()) //各聚类中心新向量值
break;
}while(nTimes++<ITERATOR_TIMES);
return true;
}void kMeans::ShowResult(CArray<POINT,POINT>* data,CDC *pDC)
{
TRACE("\n集合元素为:");
for(int i=0;i<data->GetSize();i++)
TRACE("(%d,%d) , ",(*data)[i].x,(*data)[i].y);}void kMeans::AssignSample()
{
int nType=0; //样本属于哪个聚类中心
double fMinDistance=-1; for(int n=0;n<m_center.size();n++) //重新分配前先清空样本子集
{
m_center[n].S.clear();
} for(int i=0;i<m_sample.size();i++)
{
fMinDistance=-1,nType=0;
for(int j=0;j<m_center.size();j++)
{
double fDistance=GetDistance(m_sample[i],m_center[j].point);
if(fMinDistance==-1)
fMinDistance=fDistance;
if(fDistance<fMinDistance)
{
fMinDistance=fDistance; //求最小距离
nType=j;
}
}
m_center[nType].S.push_back(m_sample[i]); //分配
}
for(int q=0;q<m_center.size();q++)
{
TRACE("\n样本子集S%d中有样本:",q+1);
for(int m=0;m<m_center[q].S.size();m++)
{
TRACE("(%d,%d) ",m_center[q].S[m].x,m_center[q].S[m].y);
}
}
}BOOL kMeans::SetNewCenter()
{
BOOL bOver=true; //算法是否结束，当新聚类中心向量全部等于原向量时
fPOINT old;
for(int i=0;i<m_center.size();i++)
{
old.x=m_center[i].point.x; //保存原向量
old.y=m_center[i].point.y;
m_center[i].point.x=0;
m_center[i].point.y=0;
for(int j=0;j<m_center[i].S.size();j++)
{
m_center[i].point.x+=m_center[i].S[j].x;
m_center[i].point.y+=m_center[i].S[j].y;
}
m_center[i].point.x/=m_center[i].S.size();
m_center[i].point.y/=m_center[i].S.size(); //新聚类中心坐标
if((old.x!=m_center[i].point.x)||(old.y!=m_center[i].point.y))
bOver=false; //有不相等的向量就不结束算法
TRACE("\n新聚类中心坐标Z%d为:(%.2f,%.2f)",i+1,m_center[i].point.x,m_center[i].point.y);
}
return bOver;
}void kMeans::Initial(int nK)
{
m_center.clear();
CLUSTER_CENTER initial;
if(nK>m_sample.size())
return;
for(int i=0;i<nK;i++)
{
initial.point.x=m_sample[i].x;
initial.point.y=m_sample[i].y;
m_center.push_back(initial); //初始值
TRACE("\n初始聚类中心坐标Z%d为:(%.2f,%.2f)",i+1,m_center[i].point.x,m_center[i].point.y);
}
}double kMeans::GetPolicy() //决策函数：这里取距离平方和
{
double fAverageDistance=0;
for(int i=0;i<m_center.size();i++)
{
m_center[i].D=0;
for(int j=0;j<m_center[i].S.size();j++)
{
m_center[i].D+=GetDistance(m_center[i].S[j],m_center[i].point)*GetDistance(m_center[i].S[j],m_center[i].point);
}
fAverageDistance+=m_center[i].D; //距离平方和 }
//fAverageDistance/=m_sample.size();
return fAverageDistance;
}
父类
// Clustering.h: interface for the CClustering class.
// 聚类基类
//  提供距离计算，通用数据结构等
//////////////////////////////////////////////////////////////////////#if !defined(AFX_CLUSTERING_H__D5BA79F7_9013_47D5_9BF3_B4DF83DED61B__INCLUDED_)
#define AFX_CLUSTERING_H__D5BA79F7_9013_47D5_9BF3_B4DF83DED61B__INCLUDED_#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <vector>
using namespace std;typedef struct{
double x;
double y;
}fPOINT;typedef struct{
fPOINT point; //中心坐标
vector<POINT> S; //聚类中心样品集
double D; //样品集到聚类中心的平均距离
fPOINT thiggma; //样本距离标准差
}CLUSTER_CENTER; //样本子集数据结构class CClustering  
{
public:
CClustering();
virtual ~CClustering();
//private:
// vector<CLUSTER_CENTER> m_center; //聚类中心
// vector<POINT> m_sample; //样本集protected:
double GetDistance(POINT x, fPOINT center);
};#endif // !defined(AFX_CLUSTERING_H__D5BA79F7_9013_47D5_9BF3_B4DF83DED61B__INCLUDED_)// Clustering.cpp: implementation of the CClustering class.
//
//////////////////////////////////////////////////////////////////////#include "stdafx.h"
#include "Cluster.h"
#include "Clustering.h"#include <math.h>#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////CClustering::CClustering()
{}CClustering::~CClustering()
{}double CClustering::GetDistance(POINT x, fPOINT center)
{
double fResult=0;
fResult=pow((pow((x.x-center.x),2)+pow((x.y-center.y),2)),0.5);//|x-center|
return fResult;
}

Answer 3

一直没人回复，我本来不报什么希望！没想到还是有高手！谢谢foxmail！