赞
踩
本代码算法用例为鸢尾花数据集合;
IOSDATA算法实现步骤,在很多资料和论坛中都有详细的介绍,这里就不对算法步骤进行陈述了。
就我代码中,我对下面几个控制参数的理解:
初始聚类数:初始类聚中心,跟聚类聚中心划分簇。
期望得到的聚类数:这个数并不是最终得到的类聚数目,可以理解为我们人为的预估可能得到的类聚数,最后的结果不一定与这个数相等。
最大迭代次数:控制程序的迭代次数,根据样本数量大小设置,本代码中的最大迭代次数设置为10,但迭代到4步左右就已经类聚完成了。
其他的一些控制参数看注解或一些资料便知道其作用,这里就不做多余介绍。
建议先将K-MEAN聚类算法看懂,再看IOSDATA聚类算法,程序理解就容易多。K-MEAN算法的代码和实现步骤在我之前的博客中也有。
c语言代码如下:
(代码并不是很完美,当类聚得到的数目过少(本例为<3时)时会出现错误,本代码仅供学习参考)
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include "vector"
using namespace std;
#define alpha 0.5 //分裂比
#define dimNum 3 //维数为3
#define cNum 8 //初始类数
#define expectNum 4 //预期成类数
#define minNum 3 //小于此数则不能成类
#define splitVar 1.2 //大于此数分裂
#define connectVar 0.3 //小于此数合并
#define connectNum 2 //每次迭代允许合并的最大数
#define iterNum 10 //迭代次数为10
typedef vector<double> doubleVector;
typedef vector<doubleVector> clusterVector;
void ISODATA(vector<doubleVector> srcInf); //开始引擎
vector<doubleVector> getInf(); //获取文件数据
int getClusterNum(vector<doubleVector> mCenter, doubleVector srcInf); //归类
double getEUCdis(doubleVector t1, doubleVector t2); //计算欧式距离
doubleVector get_wMean(clusterVector cluster); //计算均值向量
doubleVector averageDist(doubleVector mCenter, clusterVector cluster); //计算Wi中所有样本距其相应聚类中心的平均距离
doubleVector allAvgDist(vector<doubleVector> avgDis); //计算所以样本距其相应的聚类中心的平均值
doubleVector getDeviation(doubleVector mCenter, clusterVector cluster); //计算没一聚类的标准偏差
double getMaxDev(doubleVector Dev); //获取最大标准偏差
doubleVector clusterSplit(doubleVector wMean, double sigma); //进行分裂
doubleVector eachCenterDist(doubleVector t1, doubleVector t2, int i, int j); //计算聚类中心两两间的距离
vector<doubleVector> distSort(vector<doubleVector> eachDist); //按距离进行排序
vector<doubleVector> Union(vector<doubleVector> mCenter, vector<doubleVector> sortDist); //进行合并
void Output(vector<clusterVector> cluster); //结果输出
//主函数
void main()
{
vector<doubleVector> srcInf;
srcInf = getInf();
ISODATA(srcInf);
}
//迭代开始引擎
void ISODATA(vector<doubleVector> srcInf)
{
int c;
int i, j;
int iter=1;
int lable;
vector<doubleVector> mCenter;
vector<clusterVector> cluster;
vector<doubleVector> wMean; //均值向量
vector<doubleVector> avgDist;
doubleVector all_AvgDis;
vector<doubleVector> devVal; //标准偏差值
vector<doubleVector> eachDist; //两两聚类中心距离
vector<doubleVector> eachDistSort; //两两聚类中心距离
doubleVector devMax; //最大偏差值
double sigma;
start:
printf("聚类开始:\n");
//初始化类聚中心
step1:
srand(time(NULL));
int chooseNum;
if(mCenter.empty()==NULL)
mCenter.clear();
mCenter.resize(cNum);
for(i=0; i<cNum; i++)
{
chooseNum = rand()%(int)(srcInf.size()/cNum)+i*(srcInf.size()/cNum);
for(j=0; j<dimNum; j++)
mCenter[i].push_back(srcInf[chooseNum][j]);
}
//根据距离归类
step2:
if(cluster.empty()==NULL)
cluster.clear();
cluster.resize(2*cNum);
for(i=0; i<srcInf.size(); i++)
{
lable = getClusterNum(mCenter, srcInf[i]);
cluster[lable].push_back(srcInf[i]);
}
//舍弃过小的类
step3:
for(i=0; i<cluster.size(); )
{
if(cluster[i].size()<minNum)
{
cluster.erase(cluster.begin()+i);
if(i<mCenter.size())
mCenter.erase(mCenter.begin()+i);
}
else
i++;
}
c = mCenter.size();
//更新均值向量
step4:
if(wMean.empty()==NULL)
wMean.clear();
for(i=0; i<cluster.size(); i++)
wMean.push_back(get_wMean(cluster[i]));
//获取各平均距离
step5:
if(avgDist.empty()==NULL)
avgDist.clear();
for(i=0; i<cluster.size(); i++) //计算Wi中所有样本距其相应聚类中心的平均距离
avgDist.push_back(averageDist(mCenter[i], cluster[i]));
all_AvgDis = allAvgDist(avgDist); //计算所以样本距其相应的聚类中心的平均值
//判断分裂、合并及迭代的运算步骤
step7:
if(iter==iterNum) //步骤(1)
{
// connectNum = 0;
goto step11;
}
if(c<=expectNum/2)//步骤(2)
goto step8;
if(iter%2==0 || c>=2*expectNum)//步骤(3)
goto step11;
//计算标准偏差
step8:
if(devVal.empty()==NULL)
devVal.clear();
for(i=0; i<mCenter.size(); i++) //计算标准偏差
devVal.push_back(getDeviation(mCenter[i], cluster[i]));
//计算标准偏差中偏差最大值
step9:
if(devMax.empty()==NULL)
devMax.clear();
for(i=0; i<devVal.size(); i++) //计算标准偏差中偏差最大值
devMax.push_back(getMaxDev(devVal[i]));
//进行分裂
step10:
for(i=0; i<devMax.size(); i++)
{
if((devMax[i]>splitVar && cluster[i].size()>2*minNum) || c<=expectNum/2)
{
sigma = alpha*devMax[i];
mCenter.push_back(clusterSplit(wMean[i], sigma));
mCenter.push_back(clusterSplit(wMean[i], -sigma));
mCenter.erase(mCenter.begin()+i);
}
}
c = mCenter.size();
//计算两两聚类间的距离
step11:
if(eachDist.empty()==NULL)
eachDist.clear();
for(i=0; i<mCenter.size()-1; i++)
for(j=i+1; j<mCenter.size(); j++)
{
eachDist.push_back(eachCenterDist(mCenter[i], mCenter[j], i, j));
}
//对距离进行排序
step12:
eachDistSort = distSort(eachDist);
//进行合并
step13:
mCenter = Union(mCenter, eachDistSort);
c = mCenter.size();
step14:
if(iter==iterNum)
{
printf("类聚结果为:\n");
Output(cluster);
system("pause");
return;
}
else
{
iter++;
goto step2;
}
}
//获取文件数据
vector<doubleVector> getInf()
{
int i=1;
vector<doubleVector> dst;
doubleVector temp;
double num;
FILE *fp;
fp = fopen("Inf.txt", "r");
if(fp == NULL)
printf("Open file error!\n");
//读取文件的数据
while(fscanf(fp, "%lf", &num)!=EOF)
{
temp.push_back(num);
if(i%3==0)
{
dst.push_back(temp);
temp.clear();
}
i++;
}
fclose(fp);
return dst;
}
//计算欧式距离
double getEUCdis(doubleVector t1, doubleVector t2)
{
double distance=0;
int i;
for(i=0; i<dimNum; i++)
distance += (t1[i]-t2[i])*(t1[i]-t2[i]);
return sqrtf(distance);
}
//根据初始中心进行归类
int getClusterNum(vector<doubleVector> mCenter, doubleVector srcInf)
{
double Dis;
double minDis = getEUCdis(mCenter[0], srcInf);
int i, lable=0;
for(i=1; i<mCenter.size(); i++)
{
Dis = getEUCdis(mCenter[i], srcInf);
if(Dis<minDis)
{
minDis = Dis;
lable = i;
}
}
return lable;
}
//计算均值向量
doubleVector get_wMean(clusterVector cluster)
{
doubleVector wMean;
double temp[dimNum];
int i, j;
for(i=0; i<dimNum; i++)
temp[i] = 0;
for(i=0; i<cluster.size(); i++)
for(j=0; j<dimNum; j++)
temp[j] += cluster[i][j];
for(i=0; i<dimNum; i++)
temp[i] = temp[i]/cluster.size();
wMean.clear();
for(i=0; i<dimNum; i++)
wMean.push_back(temp[i]);
return wMean;
}
//计算类聚中心m[i]的平均距离
doubleVector averageDist(doubleVector mCenter, clusterVector cluster)
{
int i, j;
doubleVector avgDist;
double temp[dimNum]={0};
for(i=0; i<cluster.size(); i++)
for(j=0; j<dimNum; j++)
temp[j] += cluster[i][j];
for(i=0; i<dimNum; i++)
temp[i] /= cluster.size();
avgDist.clear();
for(i=0; i<dimNum; i++)
avgDist.push_back(temp[i]);
return avgDist;
}
//计算所以样本距其相应的聚类中心的平均值
doubleVector allAvgDist(vector<doubleVector> avgDis)
{
int i, j;
doubleVector allAvg;
double temp[dimNum]={0};
for(i=0; i<avgDis.size(); i++)
for(j=0; j<dimNum; j++)
temp[j] += (i+1)*avgDis[i][j];
for(i=0; i<dimNum; i++)
temp[i] /= avgDis.size();
allAvg.clear();
for(i=0; i<dimNum; i++)
allAvg.push_back(temp[i]);
return allAvg;
}
//计算每一个聚类的标准偏差
doubleVector getDeviation(doubleVector mCenter, clusterVector cluster)
{
doubleVector dst;
int i, j;
double temp[dimNum]={0};
for(i=0; i<cluster.size(); i++)
for(j=0; j<dimNum; j++)
temp[j] += (cluster[i][j]-mCenter[j])*(cluster[i][j]-mCenter[j]);
dst.clear();
for(i=0; i<dimNum; i++)
{
temp[i] /= cluster.size();
temp[i] = sqrtf(temp[i]);
dst.push_back(temp[i]);
}
return dst;
}
//获取最大标准偏差
double getMaxDev(doubleVector Dev)
{
int i;
double max = Dev[0];
for(i=1; i<dimNum; i++)
if(max<Dev[i])
max = Dev[i];
return max;
}
//进行分裂
doubleVector clusterSplit(doubleVector wMean, double sigma)
{
int i;
doubleVector newMean;
double temp;
newMean.clear();
for(i=0; i<dimNum; i++)
{
temp = wMean[i]+sigma;
newMean.push_back(temp);
}
return newMean;
}
//计算聚类中心两两间的距离
doubleVector eachCenterDist(doubleVector t1, doubleVector t2, int x, int y)
{
int i;
doubleVector dist;
dist.clear();
for(i=0; i<dimNum; i++)
dist.push_back(fabs(t1[i]-t2[i]));
dist.push_back(x);
dist.push_back(y);
return dist;
}
//按距离进行排序
vector<doubleVector> distSort(vector<doubleVector> eachDist)
{
int i, j, l;
vector<doubleVector> dst;
doubleVector maxEachDist;
double temp;
doubleVector tempVet;
double min;
dst = eachDist;
//寻找每组中最大的距离
maxEachDist.clear();
for(i=0; i<eachDist.size(); i++)
maxEachDist.push_back(getMaxDev(eachDist[i]));
//排序
for(i=0; i<maxEachDist.size(); i++)
{
l=i;
min = maxEachDist[i];
for(j=i+1; j<maxEachDist.size(); j++)
if(min>maxEachDist[j])
{
min = maxEachDist[j];
l = j;
}
temp = maxEachDist[i];
maxEachDist[i] = maxEachDist[l];
maxEachDist[l] = temp;
tempVet = dst[i];
dst[i] = dst[l];
dst[l] = tempVet;
}
return dst;
}
//进行合并
vector<doubleVector> Union(vector<doubleVector> mCenter, vector<doubleVector> sortDist)
{
int i[connectNum], j[connectNum];
int m, n, delNum=0;
vector<doubleVector> newCenter;
vector<int> del;
doubleVector temp;
newCenter = mCenter;
//可联合数量
for(m=0; m<connectNum; m++)
for(n=0; n<dimNum; n++)
if(sortDist[m][n]<connectVar)
{
delNum++;
break;
}
//进行联合
for(m=0; m<delNum; m++)
{
i[m] = sortDist[m][dimNum];
j[m] = sortDist[m][dimNum+1];
for(n=0; n<dimNum; n++)
temp.push_back((i[m]*mCenter[i[m]][n]+j[m]*mCenter[j[m]][n])/(i[m]+j[m]));
newCenter.push_back(temp);
}
//避免重复删除
for(m=0; m<delNum; m++)
del.push_back(i[m]);
for(n=0; n<delNum; n++)
{
if(del[n]==j[n])
continue;
else
del.push_back(j[n]);
}
for(m=0; m<del.size(); m++)
newCenter[del[m]].clear();
for(m=0; m<newCenter.size(); )
{
if(newCenter[m].empty())
newCenter.erase(newCenter.begin()+m);
else
m++;
}
return newCenter;
}
//结果输出
void Output(vector<clusterVector> cluster)
{
int i, j, k;
for(i=0; i<cluster.size(); i++)
{
printf("\n类聚%d :\n", i+1);
for(j=0; j<cluster[i].size(); j++)
printf("%lf %lf %lf\n", cluster[i][j][0], cluster[i][j][1], cluster[i][j][2]);
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。