机器学习（Python+sklearn+TensorFlow 2.0）-第2版 微课视频版 课件 02-聚类

机器学习第二章聚类

人们在面对大量未知事物时，往往会采取分而治之的策略，即先将事物按照相似性分成多个组，然后按组对事物进行处理。机器学习里的聚类（Clustering）就是用来完成对事物进行分组的任务。Cluster常翻译为簇或簇类，聚类算法是对代表事物的实例的集合进行分簇的算法。聚类属于无监督学习。先讨论较容易理解的K均值聚类算法，并通过一个有趣的示例展示其应用方法，然后介绍聚类算法的任务、评价和分类等知识，随后讨论较为复杂的DBSCAN、OPTICS和AGNES等算法。第二章聚类21K均值聚类算法及应用示例2聚类算法基础3DBSCAN及其派生算法4AGNES算法第二章聚类3

2.1.1K均值聚类算法及实现4

2.1.1K均值聚类算法及实现5

2.1.1K均值聚类算法及实现6算法流程2.1.1K均值聚类算法及实现7实例2.1.1K均值聚类算法及实现第1次迭代第2次迭代8示例核心代码2.1.1K均值聚类算法及实现9Sklearn中的调用在sklearn的cluster包中提供了两种实现k-means算法的方法，分别是KMeans类和k_means函数。2.1.1K均值聚类算法及实现10背景目前，手机上采用的身份认证方式多为密码口令、指纹识别、人脸识别以及手势识别等。这些方式在识别时需要用户的主动配合，多次验证操作会降低用户的使用体验。而且，它们属于一次性的认证方式，不能对用户身份进行持续的实时识别监控。有没有什么办法来克服这些缺点呢？每个人的运动特点是不一样的，是否可以用来进行持续的身份识别呢？2.1.2在手机机主身份识别中的应用示例11加速度幅度值特征2.1.2在手机机主身份识别中的应用实例

12步态向量

经过滑窗处理后，当采样频率为10Hz时，走路的每步周期长度大约有10至12个数据采样值，即每步数据用一个长度为10、11或12的向量表示。2.1.2在手机机主身份识别中的应用实例13聚类分析将长度为10、11、12的三类步态向量分开，每类用k-means算法进行聚类分析，可发现同一人的步态向量确实在多维空间中聚集在一起，而不同人的步态向量在空间中聚集的簇会有一定的间距。三个簇中心两两之间的欧氏距离分别为：18.5，11.6，7.7。所有簇成员与簇中心的欧氏距离的平均值和方差分别是(3.78，6.81)，(5.47，2.34)，(4.79，1.48)。2.1.2在手机机主身份识别中的应用实例14聚类分析代码2.1.2在手机机主身份识别中的应用实例15手机机主身份识别应用方案-学习过程2.1.2在手机机主身份识别中的应用实例获取加速度分量值求幅度值周期划分按周期分类剔除孤立点确定簇心和边界半径

滑窗计算中心点计算每个点与中心点的欧氏距离及均值剔除距离大于均值M倍的点重复上述过程，直至距离小于均值的点数与总点数之比位于区间（0.5-K，0.5+K）内16因速度快慢差异，每步周期的抽样点数会不同，在学习和识别时要按类分别处理。出现比较多的每周期抽样点数为9，10，11三类。手机机主身份识别应用方案-识别过程2.1.2在手机机主身份识别中的应用实例17求幅度值周期划分周期序列抽象为点计算各点与簇心的距离并与边界半径作比较根据正常点所占比例判断是否为机主>S？YESNO是机主不是机主RC手机锁屏发送紧急短信后台监测手机状态+应用实例的实现，是一次成功的探索。该探索先是对不同人的步态数据具有不同特点的“猜想”，然后采用k-means算法对该“猜想”进行了“验证”，最后再依据“验证”过的结论进行具体实现。

探索在机器学习的学习和应用中具有重要意义，尤其是在将要学习的特征工程和神经网络等内容中。探索精神是指人们对所想知道的事物、对象的锲而不舍的追求。它使人们由求知的欲望发展到学习知识、掌握知识、运用知识的实践活动。探索是创新的重要途径。2.1.2在手机机主身份识别中的应用实例18

2.1.3进一步讨论19

2.1.3进一步讨论20

2.1.3进一步讨论21局部最优与全局最优在条件（样本集、分簇数等）明确以后，k-means算法的任务就成了使SSE最小的优化计算。在最优化问题中，常常会出现所谓的局部最优解。2.1.3进一步讨论22局部最优解是在小范围内的最优解。全局最优解是在问题域内的最优解。在k-means算法中，如果初始点选取的不好，就会陷入局部最优解，而无法得到全局最优解，这是因为SSE是所谓的非凸函数。局部最优与全局最优sklearn.cluster包中的KMeans函数提供了尽量取得全局最优值的常规方法，如使初始簇中心尽量分散开、多次运行取最优值等等。还可以在算法运行完毕后，对簇结构进行调整来尽量降低SSE值，基本思路是尝试拆分SSE值最大的簇，合并两个小簇。拆分的方法是对SSE值最大的簇再次运行将k值设为2的k-means算法，得到两个小簇。合并的方法，可以将间距最小的两个簇合并，也可以合并两个使得SSE增加最小的簇。2.1.3进一步讨论23k值的确定

横坐标是k值，纵坐标为SSE值。SSE值在k小于4时下降显著，而在大于4时，下降缓慢，认为在分簇数为4时，簇结构已经相对稳定，于是确定k值为4。2.1.3进一步讨论24

2.1.3进一步讨论25二分k-means算法二分k-means（bisectingk-means）算法试图克服k-means算法收敛于局部最优值的缺陷，它的基本思想是“分裂”。首先将所有点看成一个簇，然后将该簇一分为二，之后选择其中一个簇继续分裂。选择哪一个簇进行分裂，取决于对其进行的分裂是否可以最大程度降低SSE值。2.1.4改进算法26

2.1.4改进算法27

2.1.4改进算法28MiniBatchk-means算法MiniBatchk-means算法通过略微牺牲优化质量来取得显著减少计算时间的效果。它的基本思想是用随机抽取的代表样本来进行优化计算，而不是在全部样本上进行计算。具体来讲，先从样本集中随机抽取出小部分训练样本，根据簇中心进行簇分配，然后再在簇内进行簇中心计算，重复以上过程直到簇中心稳定或者达到指定迭代次数，最后再根据簇中心将所有样本点进行分配。MiniBatchKMeans类的参数大部分与KMeans类的参数相同，不同的重要参数有：batch_size指定采样集的大小，默认是100，可根据数据集数量或者噪声点情况增加。实际效果需要反复试验。2.1.4改进算法291K均值聚类算法及应用实例2聚类算法基础3DBSCAN及其派生算法4AGNES算法第二章聚类30

2.2.1聚类任务31

2.2.1聚类任务32

2.2.2样本点常用距离度量33

2.2.2样本点常用距离度量34

2.2.2样本点常用距离度量35

2.2.2样本点常用距离度量36

2.2.3聚类算法评价指标37

2.2.3聚类算法评价指标38

2.2.3聚类算法评价指标39

2.2.3聚类算法评价指标40

2.2.3聚类算法评价指标41

2.2.3聚类算法评价指标42

2.2.3聚类算法评价指标43

2.2.3聚类算法评价指标441.划分聚类划分聚类是基于距离的，它的基本思想是使簇内的点距离尽量近、簇间的点距离尽量远。由于损失函数的非凸性，除了采用穷举法，算法难以保证每次都得到全局最优解。而在数据量很大时，采用穷举法不现实，因此，此类算法大都采用所谓的贪心策略，即在每一轮迭代中寻求当前最优解，并基于此轮最优解进行下一轮迭代，如此通过多轮迭代来提高求解质量。2.2.4聚类算法分类452.密度聚类密度聚类是基于所谓的密度（Density）进行分簇。这里的密度是指某样本点给定邻域内的其它样本点的数量。密度聚类的思想是当邻域的密度达到指定阈值时，就将邻域内的样本点合并到本簇内，如果本簇内所有样本点的邻域密度都达不到指定阈值，则本簇划分完毕，进行下一个簇的划分。2.2.4聚类算法分类463.层次聚类层次（Hierarchical）聚类方法强调的是聚类执行的过程，分为自底向上的凝聚方法和自顶向下的分裂方法两种。凝聚方法是先将每一个样本点当成一个簇，然后根据距离和密度等度量准则进行逐步合并。分裂方法是先将所有样本点放在一个簇内，然后再逐步分解，如二分k-means算法。2.2.4聚类算法分类47

2.2.4聚类算法分类485.模型聚类模型（Model）聚类假定每个簇符合一个分布模型，通过找到这个分布模型，就可以对样本点进行分簇。模型聚类主要包括基于统计和基于神经网络两大类方法，前者以高斯混合模型（GaussianMixtureModels，GMM）为代表，后者以自组织映射网络（Self

Organizing

Map，SOM）为代表。2.2.4聚类算法分类491K均值聚类算法及应用实例2聚类算法基础3DBSCAN及其派生算法4AGNES算法第二章聚类50

2.3.1相关概念及算法流程51

2.3.1相关概念及算法流程52

2.3.1相关概念及算法流程53

2.3.1相关概念及算法流程54

2.3.1相关概念及算法流程55应用示例2.3.1相关概念及算法流程56

57

58

2.3.3OPTICS算法59

2.3.3OPTICS算法60

2.3.3OPTICS算法61计算可达距离流程OPTICS算法的核心思想是将每个点离最近聚集密集区的可达距离都计算出来，然后据此进行分簇。2.3.3OPTICS算法62

2.3.3OPTICS算法63可达距离形成两个凹陷，分别对应两个簇。如果以图中的虚线距离为标准来划分，则虚线以上的点为噪声点，它们离聚集区过远，而虚线以下的点聚集在两个区域，分别对应两个簇。sklearn中的OPTICS类其中，max_eps参数即为邻域半径ϵ，min_samples参数为核心点最小邻域点数MinPts，eps参数即为分簇的距离标准（上图中虚线代表的距离）。2.3.3OPTICS算法64示例2.3.3OPTICS算法65示例2.3.3OPTICS算法661K均值聚类算法及应用实例2聚类算法基础3DBSCAN及其派生算法4AGNES算法第二章聚类67

2.4.1簇之间的距离度量682.4.2算法流程692.4