k均值聚类算法（k-means clustering algorithm）_k均值聚类方法

k-means算法又名k均值聚类算法。其算法思想大致为：先从样本集中随机选取 k 个样本作为类别中心，并计算所有样本与这 k 个类别中心的距离，对于每一个样本，将其划分到与其距离最近的类别中心所在的类别中，对于新的类别计算各个类别的新的类别中心。
  根据以上描述，我们大致可以猜测到实现k-means算法的主要三点：
  （1）类别个数 k 的选择
  （2）各个样本点到类别中心的距离
  （3）根据新划分的类别，更新类别中心

代码实现
首先定义类别中心：

struct KMeansClassCenter
{
	vector <int> classcenter;//类别中心，因为是1个像元，故不采用float或double
	vector <int> pixCode;//记录该类别的像元号
};
1
2
3
4
5

再定义每个点的象元值的属性

struct KMeansPixData
{
	vector <int> pixs;  //像元值
	KMeansClassCenter classcenter;//类别中心
	double class_distance;//距离
	int classNum;//类别号
};
1
2
3
4
5
6
7

进行聚类划分

bool kmeans(KMeansPixData *pixdata, int nBandCount, int nImgSizeX, int nImgSizeY, int m_maxClassNum, int m_maxIteratNum, int * outputpafScan)
{
	KMeansClassCenter *classCenter;

	pixdata = new KMeansPixData[nImgSizeX * nImgSizeY];
	
	for (int i = 0; i < m_maxClassNum; ++i)//给类别中心赋初始值
	{
		int classnum = (i + 0.5) * nImgSizeX * nImgSizeY / m_maxClassNum;
		classCenter[i].classcenter = pixdata[classnum].pixs;
	}

	for (int IteratNum = 0; IteratNum < m_maxIteratNum; ++IteratNum)//迭代
	{
		for(int pixcount = 0; pixcount < nImgSizeX * nImgSizeY; ++pixcount)//遍历像元
		{
			for (int classnum = 0; classnum < m_maxClassNum; ++classnum)//计算与每个类别中心的距离
			{
				float perclassdistance = 0;
				for (int bandcount = 0; bandcount < nBandCount; ++bandcount)
				{
					perclassdistance += (pixdata[pixcount].pixs[bandcount] - classCenter[classnum].classcenter[bandcount])
						* (pixdata[pixcount].pixs[bandcount] - classCenter[classnum].classcenter[bandcount]);
				}
				perclassdistance = sqrt(perclassdistance);
				if (classnum == 0)
					pixdata[pixcount].class_distance = sqrt((float)nImgSizeX * nImgSizeX + nImgSizeY * nImgSizeY);
				
				if (pixdata[pixcount].class_distance > perclassdistance)
				{
					pixdata[pixcount].class_distance = perclassdistance;
					pixdata[pixcount].classNum = classnum;
				}
				classCenter[pixdata[pixcount].classNum].pixCode.push_back(pixcount);//记录每个类别包括的像元号
			}
		}

		for (int classnum = 0; classnum < m_maxClassNum; ++classnum)//计算类别中心
		{
			for(int bandcount = 0; bandcount < nBandCount; ++bandcount)
			{
				int sum = 0;
				int maxsize = classCenter[classnum].pixCode.size();
				for (int classSize = 0; classSize < maxsize; ++classSize)//该类别像元个数
					sum += pixdata[classCenter[classnum].pixCode[classSize]].pixs[bandcount];
				if (maxsize == 0) continue;
				sum /= maxsize;
				classCenter[classnum].classcenter[bandcount] = (int)sum;
			}
		}
	}

	for(int bandcount = 0; bandcount < nBandCount; ++bandcount)
	{
		for(int pixcount = 0; pixcount < nImgSizeX * nImgSizeY; ++pixcount)		
			outputpafScan[pixcount] = pixdata[pixcount].classNum;
	}

	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

原始图像：

k-means聚类的结果：

欢迎大家批评指正。