机器学习中的KMeans算法实现_AutoLISP版本

伊江痕

算法流程如下：

输入:
    X: 数据集
    K: 簇的数量
    max_iterations: 最大迭代次数
    tolerance: 簇中心变化的容忍度

过程:
1. 初始化:
    从X中随机选择K个数据点作为初始簇中心centroids
2. 迭代直到达到最大迭代次数或簇中心变化小于tolerance:
    a. 对于X中的每个点x_i，找到距离最近的簇中心c_j，并将x_i分配给相应的簇S_j
    b. 对于每个簇S_j，更新簇中心c_j为S_j中所有点的平均值
    c. 计算簇中心的变化量，如果所有簇中心的变化量都小于tolerance，则结束迭代

输出:
    簇分配结果
    簇中心


代码如下：

1. ;在CAD中随机绘制一些半径相同的圆，这些圆最好能肉眼可见的一簇一簇的（效果会好点），当然这些簇之间也不用完全的分离开，可以相互有些交错的那种（真实的数据集肯定不是那么的泾渭分明的），然后运行本代码，框选所有圆即可。
   
2. ;这里的k代表你想把这些圆分成多少簇。
   
3. (defun kmeans(k / max_i)
   
4.   (setq x (ssget))
   
5.   ;最大迭代次数
   
6.   (setq max_i 20)
   
7.   (setq lx (sslength x))
   
8.   ;centroids用来放属于不同簇的圆
   
9.   (setq centroids nil)
   
10.   ;centroids_core_p用来放簇中心的点坐标
    
11.   (setq centroids_core_p nil)
    
12.   ;从X中随机选择K个数据点作为初始簇中心centroids
    
13.   (repeat k
    
14.     (setq ent (ssname x (randrange 0 (- lx 1))))
    
15.     (setq cen (list ent))
    
16.     (setq centroids (append centroids (list cen)))
    
17.     (setq ent_p (cdr (assoc 10 (entget ent))))
    
18.     (setq centroids_core_p (append centroids_core_p (list ent_p)))
    
19.     )
    
20.   (setq ii 0)
    
21.   (repeat max_i
    
22.     (princ (strcat "第" (itoa ii) "次迭代"))
    
23.     (setq i 0)
    
24.     (repeat lx
    
25.       ;获取选择集中的一个圆圈
    
26.       (setq ci (ssname x i))
    
27.       (setq cip (cdr (assoc 10 (entget ci))))
    
28.       ;分别和centroids_core_p的圆心计算距离，看哪个距离最小就属于哪个簇
    
29.       (setq min_dist nil)
    
30.       (setq min_index 0)
    
31.       (setq j 0)
    
32.       (repeat k
    
33.         (setq centroidp (nth j centroids_core_p))
    
34.         (setq dist (distance cip centroidp))
    
35.         (if (/= dist 0)
    
36.           (if (or (< dist min_dist) (= min_dist nil))
    
37.             (progn
    
38.               (setq min_dist dist)
    
39.               (setq min_index j)
    
40.               )
    
41. 
    
42.             )
    
43.          
    
44.           )
    
45.         (setq j (+ j 1))
    
46.         )
    
47.       ;更新centroids
    
48.       (setq centroids
    
49.              (subst
    
50.                (append (nth min_index centroids) (list ci))
    
51.                (nth min_index centroids)
    
52.                centroids
    
53.                )
    
54.              )
    
55.       ;更新centroids_core_p
    
56.       (setq centroids_min_index (nth min_index centroids))
    
57.       (setq center_min_index
    
58.              (mapcar
    
59.                '(lambda (c)(cdr (assoc 10 (entget c))))
    
60.                centroids_min_index
    
61.                )
    
62.              )
    
63.       (setq x_lst (mapcar '(lambda (l)(car l)) center_min_index))
    
64.       (setq x_total (apply '+ x_lst))
    
65.       (setq x_average (/ x_total (length x_lst)))
    
66.       (setq y_lst (mapcar '(lambda (l)(cadr l)) center_min_index))
    
67.       (setq y_total (apply '+ y_lst))
    
68.       (setq y_average (/ y_total (length y_lst)))
    
69.       (setq z_lst (mapcar '(lambda (l)(caddr l)) center_min_index))
    
70.       (setq z_total (apply '+ z_lst))
    
71.       (setq z_average (/ z_total (length z_lst)))
    
72.       (setq newp (list x_average y_average z_average))
    
73.       (setq centroids_core_p
    
74.              (subst
    
75.                newp
    
76.                (nth min_index centroids_core_p)
    
77.                centroids_core_p
    
78.                )
    
79.              )
    
80. 
    
81.       (setq i (+ i 1))
    
82.       )
    
83.     (setq ii (+ ii 1))
    
84.     )
    
85.   ;给不同簇中的圆上不同色
    
86.   (setq index 0)
    
87.   (repeat k
    
88.     (setq centroids_index (nth index centroids))
    
89.     (setq l (length centroids_index))
    
90.     (setq i 0)
    
91.     (repeat l
    
92.       (setq e (nth i centroids_index))
    
93.       (setq e_data (entget e))
    
94.       (if (= (assoc 62 e_data) nil)
    
95.         (setq e_data (cons (cons 62 (+ index 1)) e_data))
    
96.         (setq e_data
    
97.              (subst
    
98.                (cons 62 (+ index 1))
    
99.                (assoc 62 e_data)
    
100.                e_data
     
101.                )
     
102.              )
     
103.         )
     
104.       
     
105.       (entmod e_data)
     
106.       (setq i (+ i 1))
     
107.       )
     
108.     (setq index (+ index 1))
     
109.     )
     
110.   
     
111.   )
     
112. (defun rand ( / a c m )
     
113.     (setq m   4294967296.0
     
114.           a   1664525.0
     
115.           c   1013904223.0
     
116.           $xn (rem (+ c (* a (cond ($xn) ((getvar 'date))))) m)
     
117.     )
     
118.     (/ $xn m)
     
119. )
     
120. (defun randrange ( a b )
     
121.     (+ (min a b) (fix (* (rand) (1+ (abs (- a b))))))
     
122. )

;在CAD中随机绘制一些半径相同的圆，这些圆最好能肉眼可见的一簇一簇的（效果会好点），当然这些簇之间也不用完全的分离开，可以相互有些交错的那种（真实的数据集肯定不是那么的泾渭分明的），然后运行本代码，框选所有圆即可。<br /> ;这里的k代表你想把这些圆分成多少簇。<br /> (defun kmeans(k / max_i)<br />   (setq x (ssget))<br />   ;最大迭代次数<br />   (setq max_i 20)<br />   (setq lx (sslength x))<br />   ;centroids用来放属于不同簇的圆<br />   (setq centroids nil)<br />   ;centroids_core_p用来放簇中心的点坐标<br />   (setq centroids_core_p nil)<br />   ;从X中随机选择K个数据点作为初始簇中心centroids<br />   (repeat k<br />     (setq ent (ssname x (randrange 0 (- lx 1))))<br />     (setq cen (list ent))<br />     (setq centroids (append centroids (list cen)))<br />     (setq ent_p (cdr (assoc 10 (entget ent))))<br />     (setq centroids_core_p (append centroids_core_p (list ent_p)))<br />     )<br />   (setq ii 0)<br />   (repeat max_i<br />     (princ (strcat "第" (itoa ii) "次迭代")) <br />     (setq i 0)<br />     (repeat lx<br />       ;获取选择集中的一个圆圈<br />       (setq ci (ssname x i))<br />       (setq cip (cdr (assoc 10 (entget ci))))<br />       ;分别和centroids_core_p的圆心计算距离，看哪个距离最小就属于哪个簇<br />       (setq min_dist nil)<br />       (setq min_index 0)<br />       (setq j 0)<br />       (repeat k<br />         (setq centroidp (nth j centroids_core_p))<br />         (setq dist (distance cip centroidp))<br />         (if (/= dist 0)<br />           (if (or (< dist min_dist) (= min_dist nil))<br />             (progn<br />               (setq min_dist dist)<br />               (setq min_index j)<br />               )<br /> <br />             )<br />          <br />           )<br />         (setq j (+ j 1))<br />         )<br />       ;更新centroids<br />       (setq centroids<br />              (subst<br />                (append (nth min_index centroids) (list ci))<br />                (nth min_index centroids)<br />                centroids<br />                )<br />              )<br />       ;更新centroids_core_p<br />       (setq centroids_min_index (nth min_index centroids))<br />       (setq center_min_index<br />              (mapcar<br />                '(lambda (c)(cdr (assoc 10 (entget c))))<br />                centroids_min_index<br />                )<br />              )<br />       (setq x_lst (mapcar '(lambda (l)(car l)) center_min_index))<br />       (setq x_total (apply '+ x_lst))<br />       (setq x_average (/ x_total (length x_lst)))<br />       (setq y_lst (mapcar '(lambda (l)(cadr l)) center_min_index))<br />       (setq y_total (apply '+ y_lst))<br />       (setq y_average (/ y_total (length y_lst)))<br />       (setq z_lst (mapcar '(lambda (l)(caddr l)) center_min_index))<br />       (setq z_total (apply '+ z_lst))<br />       (setq z_average (/ z_total (length z_lst)))<br />       (setq newp (list x_average y_average z_average))<br />       (setq centroids_core_p<br />              (subst<br />                newp<br />                (nth min_index centroids_core_p)<br />                centroids_core_p<br />                )<br />              )<br /> <br />       (setq i (+ i 1))<br />       )<br />     (setq ii (+ ii 1))<br />     )<br />   ;给不同簇中的圆上不同色<br />   (setq index 0)<br />   (repeat k<br />     (setq centroids_index (nth index centroids))<br />     (setq l (length centroids_index))<br />     (setq i 0)<br />     (repeat l<br />       (setq e (nth i centroids_index))<br />       (setq e_data (entget e))<br />       (if (= (assoc 62 e_data) nil)<br />         (setq e_data (cons (cons 62 (+ index 1)) e_data))<br />         (setq e_data<br />              (subst<br />                (cons 62 (+ index 1))<br />                (assoc 62 e_data)<br />                e_data<br />                )<br />              )<br />         )<br />       <br />       (entmod e_data)<br />       (setq i (+ i 1))<br />       )<br />     (setq index (+ index 1))<br />     )<br />   <br />   )<br /> (defun rand ( / a c m )<br />     (setq m   4294967296.0<br />           a   1664525.0<br />           c   1013904223.0<br />           $xn (rem (+ c (* a (cond ($xn) ((getvar 'date))))) m)<br />     )<br />     (/ $xn m)<br /> )<br /> (defun randrange ( a b )<br />     (+ (min a b) (fix (* (rand) (1+ (abs (- a b))))))<br /> )

枫叶棋语

伊神牛鼻plus

超超超人1670

膜拜一下

ssyfeng

我K=4，max_i=50，(kmeans 4)，好像结果有些问题，是否迭代次数不够多的原因，结果如下：

伊江痕

ssyfeng 发表于 2024-3-1 10:03
我K=4，max_i=50，(kmeans 4)，好像结果有些问题，是否迭代次数不够多的原因，结果如下：

出现这种情况很正常，大多都是迭代次数不够。你也可以把簇之间的距离弄得靠拢一点，重合一点，增加点难度。

伊江痕

ssyfeng 发表于 2024-3-1 10:03
我K=4，max_i=50，(kmeans 4)，好像结果有些问题，是否迭代次数不够多的原因，结果如下：

还有可能是，初始随机选取簇中心的时候，两个簇中心选到一块去了，就会这样。

ssyfeng

伊江痕 发表于 2024-3-1 10:27
还有可能是，初始随机选取簇中心的时候，两个簇中心选到一块去了，就会这样。

应该还有优化空间

伊江痕

ssyfeng 发表于 2024-3-1 10:34
应该还有优化空间

是的，这只是按照基础的算法流程撸下来的

你有种再说一遍

写个c#的看看

伊江痕

你有种再说一遍 发表于 2024-3-1 18:45
写个c#的看看

我想看你写