kmeans聚类手动实现-python版

Word count: 2k   |   Reading time≈ 9 min

聚类算法

是在没有给定划分类别的情况下，根据数据的相似度进行分组的一种方法，分组的原则是组内距离最小化而组间距离最大化。

K-means算法是典型的基于距离的非层次聚类算法，在最小化误差函数的基础上将数据划分为预定的K类别，采用距离作为相似性的评级指标，即认为两个对象的距离越近，其相似度越大。

kmeans流程

算法过程：

  1. 从N个样本数据中随机选取K个对象作为初始的聚类质心。
  2. 分别计算每个样本到各个聚类中心的距离，将对象分配到距离最近的聚类中。
  3. 所有对象分配完成之后，重新计算K个聚类的质心。
  4. 与前一次的K个聚类中心比较，如果发生变化，重复过程2，否则转过程5.
  5. 当质心不再发生变化时，停止聚类过程，并输出聚类结果。

数据集介绍

使用sklearn自带的鸢尾花数据集

from sklearn.datasets import load_iris
data = load_iris()

即可导入数据。

数据集中的特征包括：

print("鸢尾花数据集的返回值：\n", iris)
# 返回值是一个继承自字典的Bench
print("鸢尾花的特征值:\n", iris["data"])
print("鸢尾花的目标值：\n", iris.target)
print("鸢尾花特征的名字：\n", iris.feature_names)
print("鸢尾花目标值的名字：\n", iris.target_names)
print("鸢尾花的描述：\n", iris.DESCR)

我们这里只使用目标是和特征值，这个特征值经过print是一个四维向量。
鸢尾花的target只包括三种花，所以k=3时候理论上最佳。编写代码的时候将target一并写入数组进行组合，这样在聚类完成后进行验证分类的错误率来衡量算法好坏。

代码简介

代码除了调用数据集和划分数据集使用到了sklearn的库函数之外，其余全部使用python自带的list结构或set结构和numpy相关函数实现。

主函数

第一次随机选取核心，就取数据集的前k个分别作为中心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def main(x,y,k,max_iter,interrupte_distance = 0):
	#x是数据集，y是标签，k是聚类数目,终止距离和最大迭代数目.
	#第一步初始化ak
	a=[]
	a_check = []#用于之后检查准确率
	for i in range(k):
		a.append([x.pop(0)])
		a_check.append([y.pop(0)])
	#初始化完了，来一遍第一次
	for i in range(len(x)):
		dist = []
		for num in range(k):
			dist.append(calc_distance(a[num][0],x[i]))
		min_index = indexofMin(dist)
		a[min_index].append(x[i])
		a_check[min_index].append(y[i])
	check_print(a,a_check)
	#c初始化完成，a是一个k*特征数，的矩阵，a_check是检查矩阵。
	for i in range(max_iter):
		print('\n------------')
		print('第'+str(i+1)+'次循环')
		main_loop(a,a_check,interrupte_distance)

主循环

先检查终止条件是否满足。

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

def main_loop(a,a_check,interrupte_distance=0):
	#a的一重下表是k，a_check跟着最后算准确率.第二下标是数据集。
	k = len(a)
	ll = len(a[0][0])#特征的数量

	## a的第一个是上次的质心
	#计算质心
	a_array = np.array(a)
	heart_calc = []
	flag_interrupt = 0
	for i in range(k):
		heart_calc.append([])

	#print(len())
	#print(a[2])
	#exit(0)
	for i in range(k):
		#对a[i]求均值了
		for j in range(ll):
			#print(a[i][:][j][1])
			#print(i,j)
			#heart_calc[i].append(np.mean(a[i][:][j]))
			heart_calc[i].append(middle_mean(a,i,j))
		if calc_distance(heart_calc[i],a[i][0])>interrupte_distance:
			flag_interrupt = 1
	if flag_interrupt == 0:
		#满足距离要求
		return 0

	#聚类中心算完,并且不满足距离要求,开始迭代

	for i in range(k):
		for j in range(len(a[i])):
			tmp = a[i].pop(0)
			tmp_lab = a_check[i].pop(0)
			tmp_index = find_heart_index(heart_calc,tmp)
			a[tmp_index].append(tmp)
			a_check[tmp_index].append(tmp_lab)
	print('中心点坐标：')
	print(heart_calc)
	check_print(a,a_check)		
	return a,a_check

实验结果

当k=3时候，输出：

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

初始化错误率：0.35
初始化方差：0.2637878757089331


------------
第1次循环
中心点坐标：
[[5.173076923076924, 3.661538461538462, 1.4653846153846157, 0.27692307692307694], [6.528333333333333, 2.986666666666667, 5.255000000000001, 1.8366666666666667], [5.161764705882353, 2.8058823529411767, 2.85, 0.776470588235294]]
错误率：0.20833333333333334
方差：0.12704004558840606


------------
第2次循环
中心点坐标：
[[4.9975000000000005, 3.47, 1.4625, 0.2475], [6.495238095238095, 2.9777777777777783, 5.204761904761905, 1.8126984126984127], [5.447058823529411, 2.5529411764705885, 3.7588235294117647, 1.1588235294117646]]
错误率：0.15
方差：0.126100321239607


------------
第3次循环
中心点坐标：
[[4.9975000000000005, 3.47, 1.4625, 0.2475], [6.583928571428572, 3.001785714285714, 5.310714285714285, 1.8678571428571427], [5.545833333333333, 2.620833333333333, 3.9333333333333336, 1.2208333333333334]]
错误率：0.125
方差：0.12874688121486713


------------
第4次循环
中心点坐标：
[[4.9975000000000005, 3.47, 1.4625, 0.2475], [6.609433962264151, 3.020754716981132, 5.350943396226417, 1.8962264150943395], [5.61111111111111, 2.625925925925926, 4.007407407407407, 1.237037037037037]]
错误率：0.10833333333333334
方差：0.13044657523262912


------------
第5次循环
中心点坐标：
[[4.9975000000000005, 3.47, 1.4625, 0.2475], [6.631372549019607, 3.0156862745098034, 5.3803921568627455, 1.911764705882353], [5.641379310344826, 2.662068965517242, 4.048275862068966, 1.2551724137931033]]
错误率：0.10833333333333334
方差：0.13267293238109287

实验结论

整体来看，由于kmeans主要使用的是距离来分类，导致算法迅速收敛，一般两三个循环就可以收敛到最终结果了，即使一开始的中心点是随机选取的。

从实验结果可以看出，k=3和k=4时候差距不大，如果在增加k，效果就会变得不佳。由于k=4比三多一类，所以每一类内部的样本个数会变少，所以方差会略低与k=3。

完整代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import numpy as np

def indexofMin(arr):
	minindex = 0
	currentindex = 1
	while currentindex < len(arr):
		if arr[currentindex] < arr[minindex]:
			minindex = currentindex
		currentindex += 1
	return minindex
def get_var(a):
	#狗屁需求还要弄什么密度,用方差来反映离散程度吧
	l = len(a)
	ans = []
	for i in range(l):
		ans.append(np.array(a[i]).var(axis=0))
	return ans
def calc_distance(list_a,list_b):
	l = len(list_a)
	#约束是最小均方误差MSE
	ans = 0
	for i in range(l):
		ans += pow(list_a[i] - list_b[i],2)
	return np.sqrt(ans)

def main(x,y,k,max_iter,interrupte_distance = 0):
	#x是数据集，y是标签，k是聚类数目,终止距离和最大迭代数目.
	#第一步初始化ak
	a=[]
	a_check = []#用于之后检查准确率
	for i in range(k):
		a.append([x.pop(0)])
		a_check.append([y.pop(0)])
	#初始化完了，来一遍第一次
	for i in range(len(x)):
		dist = []
		for num in range(k):
			dist.append(calc_distance(a[num][0],x[i]))
		min_index = indexofMin(dist)
		a[min_index].append(x[i])
		a_check[min_index].append(y[i])
	check_print(a,a_check)
	#c初始化完成，a是一个k*特征数，的矩阵，a_check是检查矩阵。
	for i in range(max_iter):
		print('\n------------')
		print('第'+str(i+1)+'次循环')
		main_loop(a,a_check,interrupte_distance)

def middle_mean(l,i,j):
	#妈的heart_calc[i].append(np.mean(a[i][:][j]))用不了，why doesnt np work?
	tmp =[]
	for ii in range(len(l[i])):
		tmp.append(l[i][ii][j])
	return np.mean(tmp)

def main_loop(a,a_check,interrupte_distance=0):
	#a的一重下表是k，a_check跟着最后算准确率.第二下标是数据集。
	k = len(a)
	ll = len(a[0][0])#特征的数量

	## a的第一个是上次的质心
	#计算质心
	a_array = np.array(a)
	heart_calc = []
	flag_interrupt = 0
	for i in range(k):
		heart_calc.append([])

	#print(len())
	#print(a[2])
	#exit(0)
	for i in range(k):
		#对a[i]求均值了
		for j in range(ll):
			#print(a[i][:][j][1])
			#print(i,j)
			#heart_calc[i].append(np.mean(a[i][:][j]))
			heart_calc[i].append(middle_mean(a,i,j))
		if calc_distance(heart_calc[i],a[i][0])>interrupte_distance:
			flag_interrupt = 1
	if flag_interrupt == 0:
		#满足距离要求
		return 0

	#聚类中心算完,并且不满足距离要求,开始迭代

	for i in range(k):
		for j in range(len(a[i])):
			tmp = a[i].pop(0)
			tmp_lab = a_check[i].pop(0)
			tmp_index = find_heart_index(heart_calc,tmp)
			a[tmp_index].append(tmp)
			a_check[tmp_index].append(tmp_lab)
	print('中心点坐标：')
	print(heart_calc)
	check_print(a,a_check)		
	return a,a_check
def check_print(a,a_check):
	sum_num = 0
	wrong_num = 0
	for i in range(len(a_check)):
		tmp = max(a_check[i],key = a_check.count)
		for j in a_check[i]:
			sum_num+=1
			if j != tmp:
				wrong_num += 1
	#print(a_check)
	print("错误率："+str(wrong_num/sum_num))
	print("方差："+str(np.mean(get_var(a))))
	print()
def find_heart_index(heart,undef):
	#heart是各个中心节点,undef是待确定的特征
	k = len(heart)
	#print(heart)
	min_index = 0
	min_dis = 100000
	for i in range(k):
		tmp_dis = calc_distance(undef,heart[i])
		#print(tmp_dis)
		if(tmp_dis<min_dis):
			min_index = i
			min_dis = tmp_dis
	#print('min')
	#print(min_index)
	return min_index


if __name__ == '__main__':
	data = load_iris()

	#print(data.keys())
	x_train, x_test, y_train, y_test = train_test_split(data.data, data.target,test_size=0.2, random_state=222)


	#print("测试集的目标值：\n", y_train)
	main(x_train.tolist(),y_train.tolist(),4,5)
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2015-2024 galaxy
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信