通用kmeans算法c++_OOP实现与python可视化输出数据_注释版

东方耀

通用kmeans算法c++_OOP实现与python可视化输出数据_注释版

1. #include <iostream>
   
2. #include <fstream>
   
3. #include "zennze/kmeans_oop.hpp"
   
4. 
   
5. using namespace std;
   
6. using std::cin;
   
7. using std::cout;
   
8. using std::initializer_list;
   
9. using std::runtime_error;
   
10. 
    
11. 
    
12. // 通用kmeans算法c++_OOP实现与python可视化输出数据_注释版
    
13. 
    
14. class NDimenPoint : public VirtualPoint
    
15. {
    
16. private:
    
17.     int dimension;  // 多维点类的维度
    
18.     vector<double> xs;   // 一个点的数据
    
19. 
    
20. public:
    
21.     // 构造一个点 只要维度
    
22.     NDimenPoint(const int d) : dimension(d) { xs.resize(d); }
    
23.     // 构造一个点 维度与点数据
    
24.     NDimenPoint(const int d, vector<double> l) : dimension(d), xs(l){}
    
25.     // 构造一个新点  用另外一个点
    
26.     NDimenPoint(const NDimenPoint &p) : dimension(p.dimension), xs(p.xs) {}
    
27.     ~NDimenPoint(){};
    
28.     bool operator==(const VirtualPoint &p) override
    
29.     {
    
30.         // 类型转换：父类 转 子类
    
31.         auto pp = static_cast<const NDimenPoint &>(p);
    
32.         if (dimension != pp.dimension)
    
33.             return false;
    
34.         for (size_t i = 0; i < xs.size(); i++)
    
35.             if (xs[i] != pp.xs[i])
    
36.                 return false;
    
37.         return true;
    
38.     }
    
39.     bool operator!=(const VirtualPoint &p) override
    
40.     {
    
41.         auto pp = static_cast<const NDimenPoint &>(p);
    
42.         if (dimension != pp.dimension)
    
43.             return true;
    
44.         for (size_t i = 0; i < xs.size(); i++)
    
45.             if (xs[i] != pp.xs[i])
    
46.                 return true;
    
47.         return false;
    
48.     }
    
49.     void add(const NDimenPoint &p)
    
50.     {
    
51.         // 定义 点的 加法
    
52.         if (p.dimension != dimension)
    
53.             throw runtime_error("dimension mismatch");
    
54.         for (size_t i = 0; i < xs.size(); i++)
    
55.             xs[i] += p.xs[i];
    
56.     }
    
57.     NDimenPoint operator/(const int n)
    
58.     {
    
59.         // 定义 点除以一个n的操作
    
60.         if (n == 0)
    
61.             throw std::runtime_error("divisor zero error!");
    
62.         NDimenPoint res(dimension);
    
63.         for (size_t i = 0; i < dimension; i++)
    
64.         {
    
65.             res.xs[i] = xs[i] / n;
    
66.         }
    
67.         return res;
    
68.     }
    
69.     double disTo(const NDimenPoint &p)
    
70.     {
    
71.         // 定义 两点之间的欧式距离 这样支持了多维数据了
    
72.         double tmp = 0;
    
73.         for (size_t i = 0; i < dimension; i++)
    
74.             tmp += pow(xs[i] - p.xs[i], 2);
    
75.         return sqrt(tmp);
    
76.     }
    
77.     string toString() override
    
78.     {
    
79.         stringstream ss;
    
80.         ss << "[";
    
81.         for (size_t i = 0; i < dimension; i++)
    
82.         {
    
83.             if (i > 0)
    
84.                 ss << ", ";
    
85.             ss << xs[i];
    
86.         }
    
87.         ss << "]";
    
88.         return ss.str();
    
89.     }
    
90. 
    
91. 
    
92.     static double calcDisToCluster(const VirtualPoint &p, const Cluster &c)
    
93.     {
    
94.         // 静态方法： 点 到 簇质心的距离
    
95.         auto pp = static_cast<const NDimenPoint &>(p);
    
96.         auto cp = static_cast<const NDimenPoint &>(*(c.getCentroid()));
    
97.         // 本质还是： 点到点 之间的距离
    
98.         return pp.disTo(cp);
    
99.     }
    
100.     static sharedVPoint avgPoints(const vector<sharedVPoint> &points)
     
101.     {
     
102.         // 计算一堆点集合的质心
     
103.         if (points.size() <= 0)
     
104.             return nullptr;
     
105.         NDimenPoint resPoint(static_cast<const NDimenPoint &>(*points[0]).dimension);
     
106.         for (auto &&p : points)
     
107.             resPoint.add(static_cast<const NDimenPoint &>(*p));
     
108.         // 求和 再 除以n  均值
     
109.         resPoint = resPoint / points.size();
     
110.         // cerr << "DEBUG\t" << resPoint.toString() << ", POINTS.SIZE " << points.size() << endl;
     
111.         return make_shared<NDimenPoint>(resPoint);
     
112.     };
     
113. };
     
114. 
     
115. 
     
116. 
     
117. 
     
118. vector<NDimenPoint> geneData(int num, const int dimension, double maxVal = 1000)
     
119. {
     
120.     std::default_random_engine generator(time(NULL));
     
121.     std::uniform_real_distribution<double> distribution(0, maxVal);
     
122.     vector<NDimenPoint> points;
     
123.     for (size_t i = 0; i < num; i++)
     
124.     {
     
125.         vector<double> tmpVec;
     
126.         for (size_t j = 0; j < dimension; j++)
     
127.             tmpVec.push_back(distribution(generator));
     
128.         points.push_back(NDimenPoint(dimension, tmpVec));
     
129.     }
     
130.     return points;
     
131. }
     
132. 
     
133. 
     
134. void output(const vector<Cluster> &clusters, const int dimension)
     
135. {
     
136.     cout << "{"
     
137.          << ""dimension":" << dimension << "," << endl
     
138.          << ""clusters":[";
     
139.     for (int i = 0; i < clusters.size(); i++)
     
140.     {
     
141.         if (i > 0)
     
142.             cout << ", ";
     
143.         std::cout << clusters[i].toString() << std::endl;
     
144.     }
     
145.     cout << "]}" << endl;
     
146. }
     
147. 
     
148. 
     
149. void output_json(const vector<Cluster> &clusters, const int dimension)
     
150. {
     
151.     std::string file_path = "./kmeans_visualization_py.json";
     
152.     std::ofstream write_out_f;
     
153.     write_out_f.open(file_path);
     
154. 
     
155. 
     
156.     write_out_f << "{"
     
157.          << ""dimension":" << dimension << "," << endl
     
158.          << ""clusters":[";
     
159.     for (int i = 0; i < clusters.size(); i++)
     
160.     {
     
161.         if (i > 0)
     
162.             write_out_f << ", ";
     
163.         write_out_f << clusters[i].toString() << std::endl;
     
164.     }
     
165.     write_out_f << "]}" << endl;
     
166. 
     
167.     write_out_f.close();
     
168. }
     
169. 
     
170. 
     
171. void kmeans_work()
     
172. {
     
173.     const int maxRound = 1000;
     
174.     const int pointCnt = 150;      // 数据集的点数
     
175.     int dimension = 1;             // 点的维度
     
176.     int k = 0;
     
177.     cerr << "dimension, k: ";
     
178.     cin >> dimension >> k;
     
179. 
     
180.     vector<sharedVPoint> points;   // 点集的 共享指针
     
181.     for (auto &&p : geneData(pointCnt, dimension))
     
182.         points.push_back(make_shared<NDimenPoint>(p));
     
183.    
     
184.     auto clusters = KmeansAlg::run(points, k, NDimenPoint::calcDisToCluster, NDimenPoint::avgPoints, maxRound);
     
185.    
     
186.     output_json(clusters, dimension);
     
187.     output(clusters, dimension);
     
188. }
     
189. 
     
190. int main()
     
191. {
     
192.     std::cout << "kmeans算法实现！" << endl;
     
193. 
     
194.     kmeans_work();
     
195. 
     
196.     return 0;
     
197. }
     

复制代码

1. #include <algorithm>
   
2. #include <cmath>
   
3. #include <ctime>
   
4. #include <exception>
   
5. #include <iostream>
   
6. #include <memory>
   
7. #include <random>
   
8. #include <sstream>
   
9. #include <string>
   
10. #include <vector>
    
11. using std::cerr;
    
12. using std::endl;
    
13. using std::make_shared;
    
14. using std::pow;
    
15. using std::shared_ptr;
    
16. using std::sqrt;
    
17. using std::string;
    
18. using std::stringstream;
    
19. using std::to_string;
    
20. using std::vector;
    
21. 
    
22. /**
    
23. * kmeans - 点作为数据，cluster是点的聚簇
    
24. * BEGIN
    
25. *      选出来 k 个点作为中心点生成聚簇
    
26. *      循环
    
27. *           计算点与聚簇的距离
    
28. *           每个点加入到距离最近的聚簇中
    
29. *           更新聚簇中心点
    
30. *           聚簇中心点未变？退出
    
31. *      输出聚簇
    
32. * END
    
33. *
    
34. * 数据结构
    
35. * 点 - ==() toString()
    
36. * 聚簇 - 计算中心点()
    
37. * calcDis(point cluster)
    
38. * kmeans() -
    
39. * 为了设计出更为通用的结构，选择采用OOP面向对象设计，结构比较复杂，尤其是距离计算，求质心这两个函数
    
40. * VirtualPoint - 虚拟点类(抽象类)，无数据成员，定义了 == != 两个纯虚函数
    
41. Cluster - 聚簇类，数据成员: VirtualPoint的集合 和 中心点(VirtualPoint类型)  
    
42.           函数成员: 设置质心 更新质心 清空点...
    
43. KmeansAlg - 算法框架，run方法实现了聚类算法，提供必要参数(点之间距离计算，求平均点方法)，无需重写算法即可运行
    
44. 
    
45. ------------------
    
46. 
    
47. NDimenPoint - 多维点类，继承VirtualPoint，用来处理多维数据
    
48. 
    
49. * 两个通用类 - 虚拟点与聚簇，实际使用的时候，继承VirtualPoint类
    
50. */
    
51. 
    
52. class VirtualPoint
    
53. {
    
54. private:
    
55. public:
    
56.     VirtualPoint() {}
    
57.     virtual ~VirtualPoint() {}
    
58.     // 纯虚函数
    
59.     virtual bool operator==(const VirtualPoint &p) = 0;
    
60.     virtual bool operator!=(const VirtualPoint &p) = 0;
    
61.     virtual string toString() = 0;
    
62. };
    
63. 
    
64. // 为何用智能指针 因为 簇里 不停的清空点集与add点，所以为了提高效率 直接操作指针
    
65. typedef shared_ptr<VirtualPoint> sharedVPoint;
    
66. // 求平均点的方法也可能是任意的，因此需要作为参数传递给算法(函数指针)
    
67. typedef sharedVPoint avgPointFunc(const vector<sharedVPoint> &);
    
68. 
    
69. 
    
70. class Cluster
    
71. {
    
72.     // 簇类：管理 质心与 该簇所有的元素
    
73. private:
    
74.     vector<sharedVPoint> points;   // 频繁操作点 用指针提高效率
    
75.     sharedVPoint centroid;   // centroid质心 的点
    
76.     avgPointFunc *avgPoints;  // 求质心的函数指针
    
77. 
    
78. public:
    
79.     Cluster(avgPointFunc avg) { avgPoints = avg; }
    
80.     ~Cluster() {}
    
81.     Cluster &setCentroid(sharedVPoint p)
    
82.     {
    
83.         centroid = p;
    
84.         // 把质心 放进一堆点里 这是为何？ 对结果没有影响  影响输出了
    
85.         points.push_back(p);
    
86.         return *this;
    
87.     }
    
88.     bool updateCentroid()
    
89.     {
    
90.         sharedVPoint tmpPoint = avgPoints(points);
    
91.         // 哪种情况 计算出来为 nullptr ?  如果points.size()==0吗？
    
92.         if (tmpPoint == nullptr)
    
93.             return false;
    
94.         bool changed;
    
95.         // 质心是否改变  true为改变了
    
96.         if (tmpPoint != nullptr && centroid != nullptr)
    
97.             changed = (*tmpPoint) != (*centroid);   // 计算出来的与原来的一样 才为false
    
98.         else
    
99.             changed = true;
    
100.         centroid = tmpPoint;  // 计算出来的质心 更新一下
     
101.         return changed;
     
102.     }
     
103.     void clear() { points.clear(); }
     
104.     void addPoint(sharedVPoint p)
     
105.     {
     
106.         points.push_back(p);
     
107.     }
     
108.     string toString() const
     
109.     {
     
110.         stringstream ss;
     
111.         if (centroid == nullptr || points.size() == 0){
     
112.             // setCentroid()不把质心加入到点集 会影响这里
     
113.             return "{}";
     
114.         }
     
115.             
     
116.         // 打印质心 与 该簇的所有点
     
117.         ss << "{"centroid": " << centroid->toString() << ","points": [";
     
118.         for (int i = 0; i < points.size(); i++)
     
119.         {
     
120.             if (i > 0)
     
121.                 ss << ", ";
     
122.             ss << points[i]->toString();
     
123.         }
     
124.         ss << "]}";
     
125. 
     
126.         return ss.str();
     
127.     }
     
128.     // 得到该簇的质心
     
129.     sharedVPoint getCentroid() const { return centroid; }
     
130.     // 得到该簇的所有的元素
     
131.     const vector<sharedVPoint> &getPoints() { return points; }
     
132. };
     
133. 
     
134. // 计算 VirtualPoint 与 Cluster的质心 之间的距离
     
135. // 距离的计算方法 可能是任意的(不仅仅欧式距离)，因此需要作为参数传递给算法(函数指针)
     
136. typedef double calcFunc(const VirtualPoint &, const Cluster &);
     
137. 
     
138. class KmeansAlg
     
139. {
     
140. public:
     
141.     KmeansAlg() {}
     
142.     ~KmeansAlg() {}
     
143.     // 生成 k 个 位于 [0, n) 中的不同的随机数, n < 100000000
     
144.     static vector<int> randDiffNumbers(int n, int k)
     
145.     {
     
146.         // 选择随机的k个初始质心
     
147.         const int maxn = 100000000;
     
148.         vector<int> res;
     
149.         if (n <= 0 || n >= maxn)
     
150.             throw std::runtime_error("n is less than zero or greater than maxn(100,000,000)");
     
151.         for (int i = 0; i < n; i++)
     
152.             res.push_back(i);
     
153.         random_shuffle(res.begin(), res.end());
     
154.         res.resize(k);
     
155.         return res;
     
156.     }
     
157.     static vector<Cluster> run(vector<sharedVPoint> data, int k, calcFunc calcDis, avgPointFunc avgPoints, const int maxRound = 1000)
     
158.     {
     
159.         if (k <= 1)
     
160.             throw std::runtime_error("k is less than 1");
     
161.         vector<Cluster> clusters;
     
162.         
     
163.         for (auto &&i : randDiffNumbers(data.size(), k)){
     
164.             // 从data里随机选择k个 作为初始的 质心
     
165.             // Cluster(avgPoints)这是构造了一个 簇
     
166.             // clusters.size() == k
     
167.             // && 是右值引用   & 是左值引用
     
168.             clusters.push_back(Cluster(avgPoints).setCentroid(data[i]));
     
169.         }
     
170.             
     
171.         for (int round = 0; round < maxRound; round++)
     
172.         {
     
173.             // 每次迭代就需要把簇的点集清空 因为都要重新计算
     
174.             for (auto &&c : clusters)
     
175.                 c.clear();
     
176.             for (size_t i = 0; i < data.size(); i++)
     
177.             {
     
178.                 // 遍历计算所有的数据点，将其就近分配到对应的簇
     
179.                 double minDis = calcDis(*(data[i]), clusters[0]);
     
180.                 int minIndex_cluster = 0;  // 离哪个簇质心距离最小的簇的索引
     
181.                 for (size_t j = 1; j < clusters.size(); j++)
     
182.                 {
     
183.                     // j为从1开始 因为前面已经算过了
     
184.                     double tmpDis = calcDis(*(data[i]), clusters[j]);
     
185.                     if (tmpDis < minDis)
     
186.                         minDis = tmpDis, minIndex_cluster = j;
     
187.                 }
     
188.                 // 以上的目的是：看当前的点 离哪个簇的质心 最近
     
189.                 // 现在就知道你这个数据点 属于哪个簇了
     
190.                 clusters[minIndex_cluster].addPoint(data[i]);
     
191.             }
     
192.             
     
193. 
     
194.             bool changed = false;
     
195.             for (auto &&c : clusters){
     
196.                 // 每个簇更新各自的簇质心 看是否有改变
     
197.                 changed = changed || c.updateCentroid();
     
198.             }
     
199. 
     
200.             std::cout << "第" << round << "轮迭代：" <<"簇质心是否有改变=" << changed << std::endl;
     
201. 
     
202.             // 簇质心没有改变了 就可以退出迭代了
     
203.             if (!changed)
     
204.                 break;
     
205. 
     
206.         }
     
207.         return clusters;
     
208.     }
     
209. };
     

复制代码

1. # -*- coding: utf-8 -*-
   
2. __author__ = u'东方耀 微信：dfy_88888'
   
3. __date__ = '2022/3/16 下午5:21'
   
4. __product__ = 'PyCharm'
   
5. __filename__ = '14_kmeans聚类结果的可视化_for_c++'
   
6. 
   
7. # 运行kmeans算法
   
8. # 将结果(JSON化)输出到文件中
   
9. # 使用Python读取文件内容
   
10. # 使用pyplot可视化
    
11. 
    
12. from mpl_toolkits.mplot3d import Axes3D
    
13. import matplotlib.pyplot as plt
    
14. import json
    
15. import random
    
16. 
    
17. colors = [
    
18.     "#ff0000", "#00ff00", "#0000ff", "#404040", "#ff00ff", "#00ffff", "#C0ff00", "#ffC000", "#ff00C0", "#000070",
    
19.     "#007000", "#700000",
    
20. ]
    
21. 
    
22. 
    
23. def paint(ax, xs, ys, color, zs=None, marker='.', s=30):
    
24.     if zs != None:
    
25.         # print("这是打印三维的")
    
26.         ax.scatter(xs=xs, ys=ys, zs=zs, zdir='z', c=color, marker=marker, s=s)
    
27.     else:
    
28.         ax.scatter(x=xs, y=ys, c=color, marker=marker, s=s)
    
29. 
    
30. 
    
31. def readData():
    
32.     random.shuffle(colors)
    
33.     output_json_c_file = "/home/jiang/jjj_eigen_works/my_use_eigen_demos/build/kmeans_visualization_py.json"
    
34.     data = json.load(open(output_json_c_file, mode="r", encoding="utf-8"))
    
35.     dimension = data["dimension"]
    
36.     clusters = []
    
37.     clusterCnt = 0
    
38.     for tmpRawCluster in data["clusters"]:
    
39.         tmpCluster = {"centroid": None, "xss": [],
    
40.                       "color": colors[clusterCnt % 140]}
    
41.         if "centroid" in tmpRawCluster:
    
42.             tmpCluster["centroid"] = tmpRawCluster["centroid"]
    
43.         for i in range(0, dimension):
    
44.             tmpCluster["xss"].append([])
    
45.         if "points" in tmpRawCluster:
    
46.             for tmpRawPoint in tmpRawCluster["points"]:
    
47.                 for j in range(0, len(tmpRawPoint)):
    
48.                     tmpCluster["xss"][j].append(tmpRawPoint[j])
    
49.         clusters.append(tmpCluster)
    
50.         clusterCnt += 1
    
51.     return {"dimension": dimension, "clusters": clusters}
    
52. 
    
53. 
    
54. def work():
    
55.     data = readData()
    
56.     print("读入的数据：维度=%d, 类别k=%d" % (int(data["dimension"]), len(data["clusters"])))
    
57.     fig = plt.figure()
    
58.     if data["dimension"] == 2:
    
59.         ax = fig.add_subplot(111)
    
60.         for cluster in data["clusters"]:
    
61.             if cluster["centroid"]:
    
62.                 paint(ax, cluster["xss"][0],
    
63.                       cluster["xss"][1], cluster["color"], marker='o')
    
64.                 # 画质心用大点
    
65.                 paint(ax, [cluster["centroid"][0]], [
    
66.                     cluster["centroid"][1]], "#000000", marker='^', s=150)
    
67.     elif data["dimension"] == 3:
    
68.         ax = fig.add_subplot(111, projection='3d')
    
69.         for cluster in data["clusters"]:
    
70.             paint(ax, cluster["xss"][0], cluster["xss"]
    
71.             [1], cluster["color"], cluster["xss"][2], marker='o')
    
72.             # 画质心用大点
    
73.             paint(ax, cluster["centroid"][0], cluster["centroid"]
    
74.             [1], "#000000", cluster["centroid"][2], marker='^', s=150)
    
75.     plt.show()
    
76.     pass
    
77. 
    
78. 
    
79. if __name__ == "__main__":
    
80.     work()
    

复制代码

Dummy

请问怎样才有198的阅读权限？