Python工程应用-数据分析基础与实践课件-第11章

第一章概论西华大学机器学习第十一章K均值聚类XXX学校XXX2022目录Contents模型介绍居民家庭消费调查物流公司最佳配送路径问题

知识引入3

有这样一个问题，在“双十一”期间，物流公司要给M城市的100个客户配送货物。客户分布在M市的各个地方，假设公司只有5辆货车，请问如何配送才能让客户能尽快收到包裹？

这个问题可以用本章介绍的聚类方法，将待配送的客户聚为5类，使得每个类别内部的客户距离相对较近，这样就可以为每个类别分配一辆配送车即可。

本章知识图谱4模型介绍一1模型介绍6

前面章节介绍的机器学习方法，都是监督学习的方法，也就是说，给定的训练样本都是事先标注好类别的，知道训练样本本身属于哪一类的。但在实际生活中，要获得大量的有标注的样本，本身就是比较困难的，因为样本的标注成本非常高。尽管现在有了一些诸如众包法等方式可以发动广大读者一起来进行数据标注，但仍然需要很高的成本。因此，我们需要针对没有标注的数据进行处理，而这样的问题就叫做无监督学习。聚类，就是一种非常典型的无监督学习方法，而本章介绍的K均值聚类，就是最简单的聚类算法。1.1模型概述7

顾名思义，聚类，就是指物以类聚，把具有相似特征的样本聚集在一起，形成一类。K均值(K-means)是一种聚类算法，是发现给定数据集的k个簇的算法。簇个数k是由用户给定的，每个簇通过其质心(centroid)，即簇中所有点的中心来描述。初始化质心每个点找距离最近的质心分配点到对应的簇更新质心1.1模型概述8K均值聚类属于无监督学习，无须准备训练集原理简单，实现起来较为容易结果可解释性较好，但在算法开始预测之前，需要手动设置k值，即估计数据大概的类别个数，不合理的k值会使结果缺乏解释性；可能收敛到局部最小值，在大规模数据集上收敛较慢；对于异常点、离群点敏感。1.2基本的K均值聚类算法9算法伪代码：选择k个点作为初始质心(通常随机)repeat对每个质心计算距离，将每个点指派到最近的质心，形成k个簇重新计算每个簇的质心until质心不发生变化1.2基本的K均值聚类算法10

可以使用误差的平方和(SumoftheSquaredError,SSE)作为度量聚类质量的目标函数。我们计算每个数据点的误差，即它到最近质心的欧氏距离，然后计算误差的平方和。SSE形式地定义如下：

其中，dist是欧氏空间中两个对象之间的标准欧氏距离。若数据集为：

1.2基本的K均值聚类算法11

SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。1.3K均值聚类算法的代码实现121.loadDataSet()完成的功能是加载数据集。创建空矩阵返回矩阵存入矩阵读取文件处理数据2.distEclud()主要负责计算两个向量的欧氏距离(也可以采用其他距离来衡量

计算方法为各个对应特征值差的平方和开方。1.3K均值聚类算法的代码实现133.randCent()负责为给定的数据集创建一个包含k个随机质心的集合。创建k行n列0矩阵随机获得质心存储质心1.3K均值聚类算法的代码实现144.

实现k均值聚类算法初始化聚类矩阵创建初始质心取第i个数据计算该数据与第j个质心的欧氏距离获取cent个质心所有数据计算平均值，得到最终质心结果与存储的质心比对更新最近距离，最近质心m行2列矩阵(m为样本数据个数)k行n列矩阵（k为质心数，n为特征数量）循环k次循环m次存储i行数据最新质心与距离存储k个质心循环k次1.3K均值聚类算法的代码实现155.验证效果1.4二分k-均值算法16算法伪代码：初始化簇表，使之包含由所有的点组成的簇。repeat从簇表中取出一个簇(选取对其划分能最大程度降低SSE值的簇)。{对选定的簇进行多次二分“试验”} fori=1to试验次数do

使用基本k均值，二分选定的簇。 endfor从二分试验中选择具有最小总SSE的两个簇。将这两个簇添加到簇表中。until簇表中包含k个簇。案例：居民家庭消费调查二2.1案例介绍18案例数据：

现有1999年全国31个省份城镇居民家庭平均每月消费性支出的主要类型数据，分别是食品、衣着、家庭设备用品及服务、医疗保健、交通和通讯、娱乐教育文化服务、居住以及杂项商品和服务。案例目标：

请尝试利用已有数据，对31个省份进行聚类。2.2案例实现19Sklearn库中的cluster模块中提供了KMeans类，该类可以实现K-均值聚类，其构造函数如下：sklearn.cluster.KMeans(n_clusters=8,init=’k-means++’,n_init=10,max_iter=300,tol=0.0001,precompute_distances=’auto’,verbose=0,random_state=None,copy_x=True,n_jobs=None,algorithm=’auto’)主要参数含义：n_clusters：可选，默.认为8。要形成的簇的数目，即类的数量。n_init：默认为10，用不同种子运行k-均值算法的次数。max_iter：默认300，单次运行的k-均值算法的最大迭代次数。返回KMeans对象的属性包括：cluster_centers_:数组类型，各个簇中心的坐标。labels_:每个数据点的标签。inertia_:浮点型，数据样本到它们最接近的聚类中心的距离平方和。n_iter_:运行的迭代次数。2.2案例实现20

案例实现过程

导入数据集初始化聚类器训练聚类器输出聚类结果聚成2类时(n_clusters=2)输出如下：聚成3类时(n_clusters=3)输出如下：物流公司最佳配送路径问题三3.1案例介绍22案例数据：

“双十一”期间，物流公司要给M城市的100个客户配送货物。假设公司只有5辆货车，客户的地理坐标在testSet.txt文件中。案例目标：

使用k-means算法，将文件内的地址数据聚成5类。由于每类的客户地址相近，可以分配给同一辆货车。3.2案例实现23初始化聚类矩阵创建初始质心取第i个数据计算该数据与第j个质心的欧氏距离获取cent个质心所有数据计算平均值，得到最终质心结果与存储的质心比对更新最近距离，最近质心m行2列矩阵(m为样本数据个数)k行n列矩阵（k为质心数，n为特征数量）循环k次循环m次存储i行数据最新质心与距离存储k个质心循环k次注：此案例选取样本中的前k个点作为初始聚类中心3.1案例实现24程序运行结果：想一想：在物流公司最佳配送路径问题的案例中：1、可否使用余弦距离？该怎么修改？2、随机选的种子，选哪个有区别吗？3、你认为K值怎么确定？

思考题251.现有20只球队的比赛信息，包括2019国际排名，2018世界杯排名，2015亚洲杯排名。请聚类分析各球队状况。

思考题262.下面的代码可以生成半环形的数据集，尝试补充完整下列对其用K-Means进行聚类的代码。你发现了什么问题吗？#环形数据importmatplotlib.pyplotaspltfromsklearn.clusterimportKMeansfromsklearn.datasetsimportmake_moons#生成环形数据集X,Y=make_moons(n_samples=200,noise=0.05,random_state=0)#=============以下需要补全=====================#=============以上需要补全=====================

#绘制聚类结果图plt.scatter(X[:,0],X[:,1],c=Y_