K

2023-05-06 01:08| 来源: 网络整理| 查看: 265

K-means（k-均值，也记为kmeans）是聚类算法中的一种，由于其原理简单，可解释强，实现方便，收敛速度快，在数据挖掘、聚类分析、数据聚类、模式识别、金融风控、数据科学、智能营销和数据运营等领域有着广泛的应用。

本文尝试梳理K-means聚类算法的基础知识体系，首先引出K-means的基础概念，介绍聚类算法的分类和基于划分的聚类算法；接着介绍K-means原理、K-means算法、K-means特征工程（类别特征、大数值特征）、K-means评估（SSE、轮廓系数），重点阐述了如何确定K值，如何选取初始中心点，如何处理空簇；然后介绍K-means的Python实现，K-means的Sklearn实现和用户聚类分群等聚类具体应用；最后对K-means进行总结，指出K-means的优缺点，K-means的改进办及聚类和分类的区别。具体目录如下：

1. K-means基础1.1. 聚类1.2. 聚类分类1.3. 基于划分的聚类算法1.3.1. 相似度1.3.2. 距离

2. K-means原理2.1. K-means原理2.2. K-means算法2.2.1. K-means如何确定 K 值？2.2.2. K-means如何选取初始中心点？2.2.3. K-means如何处理空簇？2.3. K- means特征工程2.4. K- means评估2.4.1. SSE2.4.2. 轮廓系数

3. K-means应用3.1. K-means的Python实现3.2. K-means的Sklearn实现3.3. 用户聚类分群

4. K-means总结4.1. K-means的优缺点4.2. K-means的改进4.3. 聚类和分类的区别

直接上PPT

K-means（K-均值）算法的原理、Python实现和应用

1. K-means基础

K-means基础的目录

1.1. 聚类

什么是聚类？

通俗说，聚类是将一堆数据划分成到不同的组中。

什么是聚类？

1.2. 聚类分类

都有哪些聚类算法呢？

依据算法原理，聚类算法可以分为基于划分的聚类算法（比如 K-means）、基于密度的聚类算法（比如DBSCAN）、基于层次的聚类算法（比如HC）和基于模型的聚类算法（比如HMM）。

都有哪些聚类算法呢？

在聚类算法中，常用的是 K-means 和 DBSCAN，但本文聚焦 K-means 。

HMM即隐马尔可夫模型（HiddenMarkovModel）在语音识别、机器翻译、中文分词、命名实体识别、词性标注、基因识别等领域有广泛的使用。HMM原理可参考：

刘启林：HMM隐马尔可夫模型的例子、原理、计算和应用

1.3. 基于划分的聚类算法

根据样本特征的相似度或距离远近，将其划分成若干个类。

基于划分的聚类算法

1.3.1. 相似度

什么是相似度？即两个对象的相似程度。

什么是相似度？

1.3.2. 距离

什么是距离？即两点的距离。

什么是距离？

2. K-means原理

K-means原理的目录

1967年，J. MacQueen 在论文《 Some methods for classification and analysis of multivariate observations》中把这种方法正式命名为 K-means。

1967年，J. MacQueen 在论文《 Some methods for classification and analysis of multivariate observations》中把这种方法正式命名为 K-means。

K-means，其中K是指类的数量，means是指均值。

2.1. K-means原理

K-means是基于样本集合划分的聚类算法，是一种无监督学习。

K-means原理

K-means是怎么判断类别的，又是怎么判断相似的？

通过K-means算法原理，可知K-means的本质是物以类聚。

2.2. K-means算法

K-means聚类算法的主要步骤：

第一步：初始化聚类中心；第二步：给聚类中心分配样本；第三步：移动聚类中心；第四步：停止移动。

注意：K-means算法采用的是迭代的方法，得到局部最优解

K-means算法

2.2.1. K-means如何确定 K 值？

K-means 常常根据 SSE 和轮廓系数确定 K 值。

K-means如何确定 K 值？

2.2.2. K-means如何选取初始中心点？

K-means选择不同的初始中心，会得到不同的聚类结果。

K-means 常使用 K-means++ 方法确定初始中心点。

K-means如何选取初始中心点？

2.2.3. K-means如何处理空簇？

聚类中心没有被分配到样本，常常将其删除。

K-means如何处理空簇？

2.3. K- means特征工程

类别特征、大数值特征都不适用于 K-means 聚类。

K- means特征工程

2.4. K- means评估

什么样的 K-means 聚类才是好的 K-means 聚类？

实际应用中，查查把 SSE（Sum of Squared Errors，误差平方和）与轮廓系数（Silhouette Coefficient）结合使用，评估聚类模型的效果。

什么样的 K-means 聚类才是好的 K-means 聚类？

2.4.1. SSE

SSE越小，聚类效果越好。

SSE越小，聚类效果越好

2.4.2. 轮廓系数

轮廓系数越大，聚类效果越好。

轮廓系数越大，聚类效果越好

3. K-means应用

K-means应用的目录

3.1. K-means的Python实现

K-means的Python实现

K-means算法Python实现代码如下：

# -*- coding:utf-8 -*- import numpy as np from matplotlib import pyplot class K_Means(object): # k是分组数；tolerance‘中心点误差’；max_iter是迭代次数 def __init__(self, k=2, tolerance=0.0001, max_iter=300): self.k_ = k self.tolerance_ = tolerance self.max_iter_ = max_iter def fit(self, data): self.centers_ = {} for i in range(self.k_): self.centers_[i] = data[i] for i in range(self.max_iter_): self.clf_ = {} for i in range(self.k_): self.clf_[i] = [] # print("质点:",self.centers_) for feature in data: # distances = [np.linalg.norm(feature-self.centers[center]) for center in self.centers] distances = [] for center in self.centers_: # 欧拉距离 # np.sqrt(np.sum((features-self.centers_[center])**2)) distances.append(np.linalg.norm(feature - self.centers_[center])) classification = distances.index(min(distances)) self.clf_[classification].append(feature) # print("分组情况:",self.clf_) prev_centers = dict(self.centers_) for c in self.clf_: self.centers_[c] = np.average(self.clf_[c], axis=0) # '中心点'是否在误差范围 optimized = True for center in self.centers_: org_centers = prev_centers[center] cur_centers = self.centers_[center] if np.sum((cur_centers - org_centers) / org_centers * 100.0) > self.tolerance_: optimized = False if optimized: break def predict(self, p_data): distances = [np.linalg.norm(p_data - self.centers_[center]) for center in self.centers_] index = distances.index(min(distances)) return index if __name__ == '__main__': x = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]]) k_means = K_Means(k=2) k_means.fit(x) print(k_means.centers_) for center in k_means.centers_: pyplot.scatter(k_means.centers_[center][0], k_means.centers_[center][1], marker='*', s=150) for cat in k_means.clf_: for point in k_means.clf_[cat]: pyplot.scatter(point[0], point[1], c=('r' if cat == 0 else 'b')) predict = [[2, 1], [6, 9]] for feature in predict: cat = k_means.predict(predict) pyplot.scatter(feature[0], feature[1], c=('r' if cat == 0 else 'b'), marker='x') pyplot.show()

执行结果如下：

{0: array([1.16666667, 1.46666667]), 1: array([7.33333333, 9. ])}

K-means的Python实现备注：*是两组数据的”中心点”；x是预测点分组。

3.2. K-means的Sklearn实现

K-means的Sklearn实现

K-means算法Sklearn实现代码如下：

# 把上面数据点分为两组（非监督学习） clf = KMeans(n_clusters=2) clf.fit(x) # 分组 centers = clf.cluster_centers_ # 两组数据点的中心点 labels = clf.labels_ # 每个数据点所属分组 print(centers) print(labels) for i in range(len(labels)): pyplot.scatter(x[i][0], x[i][1], c=('r' if labels[i] == 0 else 'b')) pyplot.scatter(centers[:,0],centers[:,1],marker='*', s=100) # 预测 predict = [[2,1], [6,9]] label = clf.predict(predict) for i in range(len(label)): pyplot.scatter(predict[i][0], predict[i][1], c=('r' if label[i] == 0 else 'b'), marker='x') pyplot.show()

执行结果如下：

[[7.33333333 9. ][1.16666667 1.46666667]]

[1 1 0 0 1 0]

K-means的Sklearn实现备注：*是两组数据的”中心点”；x是预测点分组。

3.3. 用户聚类分群

数据集：titanic.xls（泰坦尼克号遇难者与幸存者名单）

titanic.xls的数据集获取地址：

titanic.xls

任务：基于除survived字段外的数据，使用k-means对用户进行分组（生/死）

用户聚类分群

聚类的用户分群常用在早期，尝试进行用户探索。实际落地常常结合用户标签，或者用户画像进行用户分群。

刘启林：用户画像的基础、原理、方法论（模型）和应用

用户聚类分群的python代码如下：

# -*- coding:utf-8 -*- import numpy as np from sklearn.cluster import KMeans from sklearn import preprocessing import pandas as pd # 加载数据 df = pd.read_excel('titanic.xls') df.drop(['body', 'name', 'ticket'], 1, inplace=True) df.fillna(0, inplace=True) # 把NaN替换为0 # 把字符串映射为数字，例如{female:1, male:0} df_map = {} cols = df.columns.values for col in cols: if df[col].dtype != np.int64 and df[col].dtype != np.float64: temp = {} x = 0 for ele in set(df[col].values.tolist()): if ele not in temp: temp[ele] = x x += 1 df_map[df[col].name] = temp df[col] = list(map(lambda val: temp[val], df[col])) # 将每一列特征标准化为标准正太分布 x = np.array(df.drop(['survived'], 1).astype(float)) x = preprocessing.scale(x) clf = KMeans(n_clusters=2) clf.fit(x) # 计算分组准确率 y = np.array(df['survived']) correct = 0 for i in range(len(x)): predict_data = np.array(x[i].astype(float)) predict_data = predict_data.reshape(-1, len(predict_data)) predict = clf.predict(predict_data) if predict[0] == y[i]: correct += 1 print(correct * 1.0 / len(x))

执行结果：

第一次执行：0.6974789915966386第二次执行：0.3017570664629488

注意：结果出现很大波动，原因是它随机分配组(生:0,死:1）(生:1,死:0）。

4. K-means总结

K-means总结的目录

4.1. K-means的优缺点

K-means算法的优点、缺点是什么？

K-means算法的优点如下：

原理简单，实现方便，收敛速度快；聚类效果较优；模型的可解释性较强；调参只需要调类数k 。

K-means算法的缺点如下：

k的选取不好把握对初始聚类中心敏感对于不是凸的数据集比较难以收敛如果数据的类型不平衡，则聚类效果不佳采用的是迭代的方法，得到局部最优解对于噪音和异常点比较敏感

这里特别说明K-means缺点的第3点：对于不是凸的数据集比较难以收敛。

什么是凸集 (convex set)？

凸集 (convex set)

欧几里得空间的一个子集，其中任意两点之间的连线仍完全落在该子集内。例如，下面的两个图形都是凸集：

凸集

所以，凸的数据集，即数据集的样本呈现凸集分布。

相反，下面的两个图形都不是凸集：

不是凸集

所以，不是凸的数据集，即是数据集的样本呈现的不是凸集分布。

4.2. K-means的改进

针对K-means缺点，K-means有许多改进算法，具体如下表所示：

K-means的改进

4.3. 聚类和分类的区别

聚类和分类的区别是什么呢？

最大区别是：聚类是无监督的；分类是有监督学习。

其中机器学习的分类按输出类别（标签）不同，可以分为二分类（Binary Classification）、多分类（Multi-Class Classification）、多标签分类（Multi-Label Classification）。

刘启林：二分类、多分类、多标签分类的基础、原理、算法和工具

聚类和分类的区别

聚类的参考文献：

聚类的参考文献

总结：

因为 K-means 算法的原理简单，可解释强，实现方便，收敛速度快，在聚类算法中使用最广。

个人认为 K-means 是机器学习中三大基础算法之一（另外两个是决策树和逻辑回归），属于必须掌握的机器学习算法。

决策树的原理可参考：

刘启林：决策树（ID3、C4.5、CART）的原理、Python实现、Sklearn可视化和应用

逻辑回归的原理可参考：

刘启林：LR逻辑回归模型的原理、公式推导、Python实现和应用

结束语：

由于个人的经历、能力和水平是有限的，我的可能是片面的，也可能是错的，这里抛砖引玉。

能力和水平有限，我的可能是错的

理论本身是务虚的，需要实践、实践、再实践。个人觉得更系统、更全面的聚类理论知识可以参考张宪超的书《数据聚类》。

你的反馈，正的负的都是有价值的，有助于我加速迭代升级——更深入、更全面。

你可能会有更好的理论、实践案列，欢迎在评论区留言，咱们一起讨论。

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章