Python机器学习编程与实践 课件 5 K-means聚类算法

机器学习算法

——K-means聚类算法聚类(Clustering)起源于分类学，可以看成是研究分类问题的一种方法。聚类并不等于分类，二者的主要区别在于，聚类所面对的目标类别是未知的。聚类没有分类的准确率高，但可以发现新知识、新规律，是了解未知世界的重要手段。聚类的典型应用包括：（1）为市场分析人员发现不同的客户群，刻画不同客户群的特征。（2）应用于房屋价格数据集，可以发现房屋的地段、面积、建筑年份等对房价的影响；（3）帮助人们发现基因相近的动植物，辅助划分生物种群；（4）用于web文档内容的发现。……聚类(Clustering)是指将不同的对象划分成由多个对象组成的多个类的过程。由聚类产生的数据分组，同一组内的对象具有相似性，不同组的对象具有相异性。聚类待划分的类别未知，即训练数据没有标签。聚类属于非监督学习。5.1.1聚类

簇(cluster)是由距离邻近的对象组合而成的集合。聚类的最终目标是获得紧凑、独立的簇集合。一般采用相似度作为聚类的依据，两个对象的距离越近，其相似度就越大。按照簇的定义和聚类的方式，聚类大致分为以下几种：K-Means为代表的簇中心聚类、基于连通性的层次聚类、以EM算法为代表的概率分布聚类、以DBSCAN为代表的基于网格密度的聚类，以及高斯混合聚类等。6.1.2K-Means聚类K-Means聚类算法也称为K均值聚类算法，是典型的聚类算法。对于给定的数据集和需要划分的类数k，算法根据距离函数进行迭代处理，动态地把数据划分成k个簇（即类别），直到收敛为止。簇中心(clustercenter)也称为聚类中心。K-Means聚类的优点是算法简单、运算速度快，即便数据集很大计算起来也便捷。不足之处是如果数据集较大，容易获得局部最优的分类结果。而且所产生的类的大小相近，对噪声数据也比较敏感。K-means算法的实现过程：首先选取k个数据点作为初始的簇中心。即聚类中心。初始的聚类中心被称为种子。然后逐个计算各数据点到各聚类中心的距离，把数据点分配到离它最近的簇。一次迭代之后，所有的数据点都会分配给某个簇。再根据分配结果计算出新的聚类中心，并重新计算各数据点到各种子点的距离。根据距离重新进行分配。不断重复计算和重复分配，直到分配不再发生变化或满足终止条件。聚类的运算流程随机选择k个数据点->起始簇中心While数据点的分配结果发生改变:for数据集中的每个数据点p:for循环访问每个簇中心c:computer_distance(p,c)

将数据点p分配到最近的簇for每一个簇:

簇中心更新为簇内数据点的均值聚类是一个反复迭代的过程，理想的终止条件是簇的分配和各簇中心不再改变。还可以设置循环次数、变化误差作为终止条件。K-means算法的类别划分依赖于样本之间的距离，距离的度量手段很多，常用的欧式距离和曼哈顿距离。5.1.3聚类算法的性能评估1.常见的聚类评价方法大致3类：外部有效性评价、内部有效性评价和相对评价法。外部评价反映聚类结果的整体效果，常用的指标有F-measure指数，Rand指数和Jaccard系数等。内部评价是利用数据集的内部特征来评价，包括Dunn（邓恩）指数、轮廓系数等指标。相对评价法选定某个评价指标，然后为聚类算法设置不同的参数进行测试。根据测试结果选取最优的算法参数和聚类模式等，例如改进的Dunn指数等。/hpuexplorer/article/details/115699428K–means目标函数聚类算法的理想目标是类内距离最小，类间距离最大。假设数据集X包含n个数据点，需要划分到k个类。聚类中心用集合U表示。聚类后所有数据点到各自聚类中心的差的平方和为聚类平方和，用J表示。聚类的目标就是使J值最小化，如果在某次迭代后J值没有发生变化，则说明簇的分配不再发生变化，算法已经收敛。6.2.1使用SKlearn实现K-Means聚类Scikit-learn的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。要形成的簇的数目，即类的数量。init:：有三个可选值‘k-means++’,’random’,或者传递一个ndarray向量。这三个参数是指定类的收敛方法默认值k-means++。初始的聚类中心对聚类结果影响很大，了解这三种初始化方法：（1）k-means++。用k-means++优化算法选定初始聚类中心，可以加速迭代收敛过程；（2）random随机从训练数据中选取初始聚类中心。（3）如果传递的是一个ndarray，格式，应该是（n_cluster,n_features）形式的，并给出初始的簇中心。n_init：默认为10，用不同种子运行k-均值算法的次数。max_iter：默认300，单次运行的k-均值算法的最大迭代次数。返回KMeans对象的属性包括：cluster_centers_：数组类型，各个簇中心的坐标。labels_：每个数据点的标签。inertia_：浮点型，数据样本到它们最接近的聚类中心的距离平方和。n_iter_：运行的迭代次数。6.2.1使用SKlearn实现K-Means聚类K-means模块的常用方法fit(X,[Y]),参数为X，Y为可选参数，进行K-means聚类计算。predict(X),预测X中每个样本的所属（最近的）簇。fit_predict(X,[Y]),是一个综合函数。算簇中心，并预测每个样本的所属簇。【例】使用sklearn.cluster.KMeans进行k-均值聚类。六个数据点，依次是[1,2],[1,2],[1,4],[1,0],[4,2],[4,4]和[4,0]]，聚类结果：【例】对鸢尾花数据进行聚类。思考：1.算法的性能怎么样？为什么？2.每次运行的结果是否相同，为什么？鸢尾花数据集是150朵花的测量记录。包括花瓣长度、宽度、花萼的长度、宽度以及花的类别。聚类过程中不需要类别标签，所以要想对鸢尾花数据集进行聚类，需要忽略花的类别标签。与真实相比，聚类结果看起来几乎全部都是判断错误。同学们可以思考一下真实情况是怎么样的？原因是：由于聚类没有标签，所以聚类结果中的012与真值的012含义完全不同。聚类结果的012仅仅是编号。与它是哪种类型的花没有关系。山鸢尾（0类花）位于编号1的簇内。杂色鸢尾（1类花）位于编号2的簇内。结果中可以看到，有个别数据被误判成零。维吉尼亚鸢尾（2类花），大部分位于0编号的簇内，有个别数据被误判成2。鸢尾花的标签虽然没有用作依据，但对于算法性能的评价还是非常重要的。【例】K-Means算法文本聚类算法实例先使用Jieba模块的lcut函数将七个句子划分成31个单词。再用TFIDF词频矩阵表明每个句子对31个单词的词频统计结果。最后使用K-Means聚类对矩阵的数据进行聚类并预测，得到各句的聚类结果。……6.2.2Python实现K-Means聚类

【例6.4】物流配送问题。问题描述：“双十一”期间，物流公司要给M城市的50个客户配送货物。假设公司只有5辆货车，客户的地理坐标在testSet.txt文件中，如何配送效率最高？问题分析：可以使用K-Means算法，将文件内的地址数据聚成5类。由于每类的客户地址相近，可以分配给同一辆货车。客户按地理位置被聚类成五类。这样物流公司的五辆车分别分管其中的一片区域，就可以达到更高的配送效率，客户就能更快的拿到自己盼望的快递了。6.3.1K-Means算法的不足

1.K值的选定比较难。2.初始聚类中心的选择对聚类结果有较大影响。3.K-Means算法的时间开销比较大。4.K-Means算法的功能具有局限性。Make_moons数据集聚类【例6.5】对半环形数据集进行k-均值