算法简介:
k-means聚类算法是一种无监督学习的算法。
无监督学习(unsupervised learning):输入数据没有被标记,也没有确定的结果。样本数据类别未知,需要根据样本间的相似性对样本集进行分类(聚类,clustering)试图使类内差距最小化,类间差距最大化。通俗点将就是实际应用中,不少情况下无法预先知道样本的标签,也就是说没有训练样本对应的类别,因而只能从原先没有样本标签的样本集开始学习分类器设计。
监督学习(supervised learning):从给定的训练数据集中学习出一个函数(模型参数),当新的数据到来时,可以根据这个函数预测结果。监督学习的训练集要求包括输入输出,也可以说是特征和目标。训练集中的目标是由人标注的。监督学习就是最常见的分类(注意和聚类区分)问题,通过已有的训练样本(即已知数据及其对应的输出)去训练得到一个最优模型(这个模型属于某个函数的集合,最优表示某个评价准则下是最佳的),再利用这个模型将所有的输入映射为相应的输出,对输出进行简单的判断从而实现分类的目的。也就具有了对未知数据分类的能力。监督学习的目标往往是让计算机去学习我们已经创建好的分类系统(模型)。
算法思想:
k-means算法的思想比较简单,假设我们要把数据分成K个类,大概可以分为以下几个步骤:
- 随机选取k个点,作为聚类中心;
- 计算每个点分别到k个聚类中心的聚类,然后将该点分到最近的聚类中心,这样就行成了k个簇;
- 再重新计算每个簇的质心(均值);
- 重复以上2~4步,直到质心的位置不再发生变化或者达到设定的迭代次数。
算法流程图解
下面我们通过一个具体的例子来理解这个算法(我这里用到了Andrew Ng的机器学习教程中的图):
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:63f41039-6a6e-4de6-a010-2771f096a77d
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1be2ffa3-7a2b-42bf-8fbe-e173e5c76674
我们人眼当然可以很快的分辨出来,可以在两个聚类间找到一条合理的分界线,那么用k-means算法来解决这个问题会是怎样的呢?
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:96d407bf-db68-43ef-ae25-45e3f388250f
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:19f55d46-b78c-4d3a-bee2-e2d7ce93cb0d
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5a23c0ee-d68a-40ab-948a-247e0a22a960
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:154d72a8-b4fd-4fa1-935d-23a3ea871ac1
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3be8f98e-333d-4359-a53f-7a7acf9ca0ff
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c2221ad8-06ea-479f-b4c7-faa4ad716e95
红X和蓝X都向中间靠拢了一点。我们可以看到,聚类中心发生改变后,其他点离两个聚类中心的距离也跟随着发生了变化。然后我们重复第二步,根据每个点到两个聚类中心的距离远近来进行重新分类,离红X近的归为红类,离蓝X近的归为蓝类。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ff3f9dd7-39af-4d84-a853-809085dc24e2
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c2275cb7-857a-4589-b2d3-4c34b9b29e5c
这样我们就利用k-means算法把这个数据很好的分为两类啦。
我们可以看到,在整个过程中,我们都没有去监督算法,告诉他具体是分错了还是对了,只是在开始的时候告诉他要把这个数据分成多少类,然后后面的操作都是由他自己完成,完全没有人为的让他进行分类的学习,也没有帮助他纠正错误,所以k-means算法也是一种无监督学习方法。
相信看到这里你对k-means算法的原理也有了一个大概的了解啦。下面我们再来看看这个算法的代码实现吧。
用python实现k-means算法:
import numpy as np
import matplotlib.pyplot as plt
两点距离
def distance(e1, e2):
return np.sqrt((e1[0]-e2[0])**2+(e1[1]-e2[1])**2)
集合中心
def means(arr):
return np.array([np.mean([e[0] for e in arr]), np.mean([e[1] for e in arr])])
arr中距离a最远的元素,用于初始化聚类中心
def farthest(k_arr, arr):
f = [0, 0]
max_d = 0
for e in arr:
d = 0
for i in range(k_arr.__len__()):
d = d + np.sqrt(distance(k_arr[i], e))
if d > max_d:
max_d = d
f = e
return f
arr中距离a最近的元素,用于聚类
def closest(a, arr):
c = arr[1]
min_d = distance(a, arr[1])
arr = arr[1:]
for e in arr:
d = distance(a, e)
if d < min_d:
min_d = d
c = e
return c
if __name__=="__main__":
## 生成二维随机坐标,手上有数据集的朋友注意,理解arr改起来就很容易了
## arr是一个数组,每个元素都是一个二元组,代表着一个坐标
## arr形如:[ (x1, y1), (x2, y2), (x3, y3) ... ]
arr = np.random.randint(100, size=(100, 1, 2))[:, 0, :]
## 初始化聚类中心和聚类容器
m = 5
r = np.random.randint(arr.__len__() - 1)
k_arr = np.array([arr[r]])
cla_arr = [[]]
for i in range(m-1):
k = farthest(k_arr, arr)
k_arr = np.concatenate([k_arr, np.array([k])])
cla_arr.append([])
## 迭代聚类
n = 20
cla_temp = cla_arr
for i in range(n): # 迭代n次
for e in arr: # 把集合里每一个元素聚到最近的类
ki = 0 # 假定距离第一个中心最近
min_d = distance(e, k_arr[ki])
for j in range(1, k_arr.__len__()):
if distance(e, k_arr[j]) < min_d: # 找到更近的聚类中心
min_d = distance(e, k_arr[j])
ki = j
cla_temp[ki].append(e)
# 迭代更新聚类中心
for k in range(k_arr.__len__()):
if n - 1 == i:
break
k_arr[k] = means(cla_temp[k])
cla_temp[k] = []
## 可视化展示
col = ['HotPink', 'Aqua', 'Chartreuse', 'yellow', 'LightSalmon']
for i in range(m):
plt.scatter(k_arr[i][0], k_arr[i][1], linewidth=10, color=col[i])
plt.scatter([e[0] for e in cla_temp[i]], [e[1] for e in cla_temp[i]], color=col[i])
plt.show()
算法结果:
Original: https://blog.csdn.net/weixin_40933858/article/details/113817500
Author: 好好学习知识就是力量
Title: k-means聚类算法
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/561270/
转载文章受原作者版权保护。转载请注明原作者出处!