K-means聚类算法
简介
k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
核心思想
通过迭代寻找k个类簇的一种划分方案，使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。
k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
k-means算法的基础是最小误差平方和准则,
其代价函数是：
μc(i)表示第i个聚类的均值。
各类簇内的样本越相似，其与该类均值间的误差平方越小，对所有类所得到的误差平方求和，即可验证分为k类时，各聚类是否是最优的。
上式的代价函数无法用解析的方法最小化，只能有迭代的方法。
算法步骤
先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：
1)没有（或最小数目）对象被重新分配给不同的聚类。
2)没有（或最小数目）聚类中心再发生变化。
3)误差平方和局部最小。
伪代码
选择k个点作为初始质心。
重复将每个点指派到最近的质心，形成k个簇 重新计算每个簇的质心 until 质心不发生变化
对{1, 2, 3, 11, 12, 13, 21, 22, 23}这9个样本值聚类
算法代码实现
1 #include<iostream>
2 #include<cmath>
3 #include<vector>
4 #include<ctime>
5 using namespace std;
6 typedef unsigned int uint;
7
8 struct Cluster
9 {
10 vector<double> centroid;
11 vector<uint> samples;
12 };
13 double cal_distance(vector<double> a, vector<double> b)
14 {
15 uint da = a.size();
16 uint db = b.size();
17 if (da != db) cerr << "Dimensions of two vectors must be same!!\n";
18 double val = 0.0;
19 for (uint i = 0; i < da; i++)
20 {
21 val += pow((a[i] - b[i]), 2);
22 }
23 return pow(val, 0.5);
24 }
25 vector<Cluster> k_means(vector<vector<double> > trainX, uint k, uint maxepoches)
26 {
27 const uint row_num = trainX.size();
28 const uint col_num = trainX[0].size();
29
30 /*初始化聚类中心*/
31 vector<Cluster> clusters(k);
32 uint seed = (uint)time(NULL); 33 for (uint i = 0; i < k; i++)
34 {
35 srand(seed);
36 int c = rand() % row_num;
37 clusters[i].centroid = trainX[c];
38 seed = rand();
39 }
40
41 /*多次迭代直至收敛，本次试验迭代100次*/
42 for (uint it = 0; it < maxepoches; it++)
43 {
44 /*每一次重新计算样本点所属类别之前，清空原来样本点信息*/
45 for (uint i = 0; i < k; i++)
46 {
47 clusters[i].samples.clear();
48 }
49 /*求出每个样本点距应该属于哪一个聚类*/
50 for (uint j = 0; j < row_num; j++)
51 {
52 /*都初始化属于第0个聚类*/
53 uint c = 0;
54 double min_distance = cal_distance(trainX[j],clusters[c].centroid);
55 for (uint i = 1; i < k; i++)
56 {
57 double distance = cal_distance(trainX[j], clusters[i].centroid);
58 if (distance < min_distance)
59 {
60 min_distance = distance;
61 c = i;
62 }
63 }
64 clusters[c].samples.push_back(j);
65 }
66
67 /*更新聚类中心*/
68 for (uint i = 0; i < k; i++)
69 {
70 vector<double> val(col_num, 0.0);
71 for (uint j = 0; j < clusters[i].samples.size(); j++)
72 {
73 uint sample = clusters[i].samples[j];
74 for (uint d = 0; d < col_num; d++)
75 {
76 val[d] += trainX[sample][d];
77 if (j == clusters[i].samples.size() - 1)
78 clusters[i].centroid[d] = val[d] / clusters[i].samples.size();
79 }
80 }
81 }
82 }
83 return clusters;
84 }
85
86 int main()
87 {
88 vector<vector<double> > trainX(9,vector<double>(1,0));
89 //对9个数据{1 2 3 11 12 13 21 22 23}聚类
90 double data = 1.0;
91 for (uint i = 0; i < 9; i++)
92 {
93 trainX[i][0] = data;
94 if ((i+1) % 3 == 0) data += 8;
95 else data++;
96 }
97
98 /*k-means聚类*/
99 vector<Cluster> clusters_out = k_means(trainX, 3, 100);
100
101 /*输出分类结果*/
102 for (uint i = 0; i < clusters_out.size(); i++)
103 {
104 cout << "Cluster " << i << " :" << endl;
105
106 /*子类中心*/
107 cout << "\t" << "Centroid: " << "\n\t\t[ ";
108 for (uint j = 0; j < clusters_out[i].centroid.size(); j++)
109 {
110 cout << clusters_out[i].centroid[j] << " ";
111 }
112 cout << "]" << endl;
113
114 /*子类样本点*/
115 cout << "\t" << "Samples:\n";
116 for (uint k = 0; k < clusters_out[i].samples.size(); k++)
117 {
118 uint c = clusters_out[i].samples[k];
119 cout << "\t\t[ ";
120 for (uint m = 0; m < trainX[0].size(); m++)
121 {
122 cout << trainX[c][m] << " ";
123 }
124 cout << "]\n";
125 }
126 }
127 return 0;
128 }
运行结果
优缺点
优点
1）原理比较简单，实现也是很容易，收敛速度快。
2）聚类效果较优。
3）算法的可解释度比较强。
4）主要需要调参的参数仅仅是簇数k。
缺点
1）采用迭代方法，得到的结果只是局部最优。
2）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
总结
这个算法的大概意思就是“物以类聚，人以群分”，依靠距离去聚集，然后选出质心，反复迭代，直到距离变化不大，直到到达目标，算法就终止了，还是比较容易理解的。
参考资料：
https://www.cnblogs.com/90zeng/p/k_means.html
https://blog.csdn.net/weixin_41105443/article/details/84725043