利用Python如何实现K-means聚类算法

目录
  • 前言
  • 算法原理
  • 目标函数
  • 算法流程
  • Python实现
  • 总结

前言

K-Means 是一种非常简单的聚类算法(聚类算法都属于无监督学习)。给定固定数量的聚类和输入数据集,该算法试图将数据划分为聚类,使得聚类内部具有较高的相似性,聚类与聚类之间具有较低的相似性。

算法原理

1. 初始化聚类中心,或者在输入数据范围内随机选择,或者使用一些现有的训练样本(推荐)

2. 直到收敛

  • 将每个数据点分配到最近的聚类。点与聚类中心之间的距离是通过欧几里德距离测量得到的。
  • 通过将聚类中心的当前估计值设置为属于该聚类的所有实例的平均值,来更新它们的当前估计值。

目标函数

聚类算法的目标函数试图找到聚类中心,以便数据将划分到相应的聚类中,并使得数据与其最接近的聚类中心之间的距离尽可能小。

给定一组数据X1,...,Xn和一个正数k,找到k个聚类中心C1,...,Ck并最小化目标函数:

其中是质心,计算表达式为

上图a表达了初始的数据集,假设k=2。在图b中,我们随机选择了两个k类所对应的类别质心,即图中的红色质心和蓝色质心,然后分别求样本中所有点到这两个质心的距离,并标记每个样本的类别为和该样本距离最小的质心的类别,如图c所示,经过计算样本和红色质心和蓝色质心的距离,我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心,如图4所示,新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程,即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。当然在实际K-Mean算法中,我们一般会多次运行图c和图d,才能达到最终的比较优的类别。

算法流程

注意点:

  1. 对于K-Means算法,首先要注意的是k值的选择,一般来说,我们会根据对数据的先验经验选择一个合适的k值,如果没有什么先验知识,则可以通过交叉验证选择一个合适的k值
  2. 在确定了k的个数后,我们需要选择k个初始化的质心,就像上图b中的随机质心。由于我们是启发式方法,k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响,因此需要选择合适的k个质心,最好这些质心不能太近。

流程:

输入是样本集D={x1,x2,...xm},聚类的簇树k,最大迭代次数N

输出是簇划分C={C1,C2,...Ck}

    1) 从数据集D中随机选择k个样本作为初始的k个质心向量: {μ1,μ2,...,μk}

    2)对于n=1,2,...,N

      a) 将簇划分C初始化为Ct=∅  t=1,2...k

      b) 对于i=1,2...m,计算样本xi和各个质心向量μj(j=1,2,...k)的距离:,将xixi标记最小的为所对应的类别。此时更新

      c) 对于j=1,2,...,k,对Cj中所有的样本点重新计算新的质心

      e) 如果所有的k个质心向量都没有发生变化,则转到步骤3)

    3) 输出簇划分C={C1,C2,...Ck}

Python实现

import numpy as np
import matplotlib.pyplot as plt
import random
from sklearn.datasets import make_blobs
np.random.seed(123)
from sklearn.cluster import KMeans
class Kmeans:
    def __init__(self,data,k):
        self.data=data
        self.k = k
    def cluster_data_Bysklearn(self):
        kmeans_model = KMeans(self.k,random_state=1)
        labels = kmeans_model.fit(self.data).labels_
        print(labels)
        return labels

    def kmeans(self):
        # 获取4个随机数
        rarray = np.random.random(size=self.k)
        # 乘以数据集大小——>数据集中随机的4个点
        rarray = np.floor(rarray * len(self.data))
        # 转为int
        rarray = rarray.astype(int)
        print('数据集中随机索引', rarray)
        # 随机取数据集中的4个点作为初始中心点
        center = data[rarray]
        # 测试比较偏、比较集中的点,效果依然完美,测试需要删除以上代码
        # center = np.array([[4.6,-2.5],[4.4,-1.7],[4.3,-0.7],[4.8,-1.1]])
        # 1行80列的0数组,标记每个样本所属的类(k[i])
        cls = np.zeros([len(self.data)], np.int)
        print('初始center=\n', center)
        run = True
        time = 0
        n = len(self.data)
        while run:
            time = time + 1
            for i in range(n):
                # 求差
                tmp = data[i] - center
                # 求平方
                tmp = np.square(tmp)
                # axis=1表示按行求和
                tmp = np.sum(tmp, axis=1)
                # 取最小(最近)的给该点“染色”(标记每个样本所属的类(k[i]))
                cls[i] = np.argmin(tmp)
            # 如果没有修改各分类中心点,就结束循环
            run = False
            # 计算更新每个类的中心点
            for i in range(self.k):
                # 找到属于该类的所有样本
                club = data[cls == i]
                # axis=0表示按列求平均值,计算出新的中心点
                newcenter = np.mean(club, axis=0)
                # 如果新旧center的差距很小,看做他们相等,否则更新之。run置true,再来一次循环
                ss = np.abs(center[i] - newcenter)
                if np.sum(ss, axis=0) > 1e-4:
                    center[i] = newcenter
                    run = True
            print('new center=\n', center)
        print('程序结束,迭代次数:', time)
        # 按类打印图表,因为每打印一次,颜色都不一样,所以可区分出来
        # for i in range(self.k):
        #     club = data[cls == i]
        #     self.showtable(club)
        # 打印最后的中心点
        self.showtable(center)
        #打印聚类标签
        print(cls)

    def showtable(self,data):
        x = data.T[0]
        y = data.T[1]
        plt.scatter(x, y)
        plt.show()

if __name__ == '__main__':
    data = np.random.rand(10,2)
    K = 4
    model = Kmeans(data,K)

    model.kmeans()
    model.cluster_data_Bysklearn()

结果:

自写得出的    [0 2 0 0 0 2 3 2 1 2]
调用模型的出的[0 2 0 1 0 2 3 2 3 0]

jupyter notebook实现

import numpy as np
import matplotlib.pyplot as plt
import random
from sklearn.datasets import make_blobs

%matplotlib inline
X, y = make_blobs(centers=6, n_samples=1000)
print(f'Shape of dataset: {X.shape}')

fig = plt.figure(figsize=(8,6))
plt.scatter(X[:,0], X[:,1], c=y)
plt.title("Dataset with 6 clusters")
plt.xlabel("First feature")
plt.ylabel("Second feature")
plt.show()

class KMeans():
    def __init__(self, n_clusters=6):
        self.k = n_clusters

    def fit(self, data):
        """
        Fits the k-means model to the given dataset
        """
        n_samples, _ = data.shape
        # initialize cluster centers
        self.centers = np.array(random.sample(list(data), self.k))
        self.initial_centers = np.copy(self.centers)

        # We will keep track of whether the assignment of data points
        # to the clusters has changed. If it stops changing, we are
        # done fitting the model
        old_assigns = None
        n_iters = 0

        while True:
            new_assigns = [self.classify(datapoint) for datapoint in data]

            if new_assigns == old_assigns:
                print(f"Training finished after {n_iters} iterations!")
                return

            old_assigns = new_assigns
            n_iters += 1

            # recalculate centers
            for id_ in range(self.k):
                points_idx = np.where(np.array(new_assigns) == id_)
                datapoints = data[points_idx]
                self.centers[id_] = datapoints.mean(axis=0)

    def l2_distance(self, datapoint):
        dists = np.sqrt(np.sum((self.centers - datapoint)**2, axis=1))
        return dists

    def classify(self, datapoint):
        """
        Given a datapoint, compute the cluster closest to the
        datapoint. Return the cluster ID of that cluster.
        """
        dists = self.l2_distance(datapoint)
        return np.argmin(dists)

    def plot_clusters(self, data):
        plt.figure(figsize=(12,10))
        plt.title("Initial centers in black, final centers in red")
        plt.scatter(data[:, 0], data[:, 1], marker='.', c='y')
        plt.scatter(self.centers[:, 0], self.centers[:,1], c='r')
        plt.scatter(self.initial_centers[:, 0], self.initial_centers[:,1], c='k')
        plt.show()
X = np.random.randn(10,100)
kmeans = KMeans(n_clusters=6)
kmeans.fit(X)
for data in X:
    print(kmeans.classify(data))

总结

K-Means的主要优点:

1)原理简单,容易实现

2)可解释度较强

K-Means的主要缺点:

1)K值很难确定

2)局部最优

3)对噪音和异常点敏感

4)需样本存在均值(限定数据种类)

5)聚类效果依赖于聚类中心的初始化

6)对于非凸数据集或类别规模差异太大的数据效果不好

到此这篇关于利用Python如何实现K-means聚类算法的文章就介绍到这了,更多相关Python实现K-means聚类算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-08-15

Python用K-means聚类算法进行客户分群的实现

一.背景 1.项目描述 你拥有一个超市(Supermarket Mall).通过会员卡,你用有一些关于你的客户的基本数据,如客户ID,年龄,性别,年收入和消费分数. 消费分数是根据客户行为和购买数据等定义的参数分配给客户的. 问题陈述:你拥有这个商场.想要了解怎么样的顾客可以很容易地聚集在一起(目标顾客),以便可以给营销团队以灵感并相应地计划策略. 2.数据描述 字段名 描述 CustomerID 客户编号 Gender 性别 Age 年龄 Annual Income (k$) 年收入,单位为千

python基于K-means聚类算法的图像分割

1 K-means算法 实际上,无论是从算法思想,还是具体实现上,K-means算法是一种很简单的算法.它属于无监督分类,通过按照一定的方式度量样本之间的相似度,通过迭代更新聚类中心,当聚类中心不再移动或移动差值小于阈值时,则就样本分为不同的类别. 1.1 算法思路 随机选取聚类中心 根据当前聚类中心,利用选定的度量方式,分类所有样本点 计算当前每一类的样本点的均值,作为下一次迭代的聚类中心 计算下一次迭代的聚类中心与当前聚类中心的差距 如4中的差距小于给定迭代阈值时,迭代结束.反之,至2继续下

Python机器学习之K-Means聚类实现详解

本文为大家分享了Python机器学习之K-Means聚类的实现代码,供大家参考,具体内容如下 1.K-Means聚类原理 K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大.其基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类.通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果.各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开. 算法大致流程为:(1)随机选取k个点作为种子点(这k个点不一定属于数据集)

python中实现k-means聚类算法详解

算法优缺点: 优点:容易实现 缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢 使用数据类型:数值型数据 算法思想 k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的,相近的就会放到同一个类别中去. 1.首先我们需要选择一个k值,也就是我们希望把数据分成多少类,这里k值的选择对结果的影响很大,Ng的课说的选择方法有两种一种是elbow method,简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好.另一种则是根据具体的需求确定,比如说进行衬衫尺寸的聚

python实现k-means聚类算法

k-means聚类算法 k-means是发现给定数据集的k个簇的算法,也就是将数据集聚合为k类的算法. 算法过程如下: 1)从N个文档随机选取K个文档作为质心 2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心的类,我们一般取欧几里得距离 3)重新计算已经得到的各个类的质心 4)迭代步骤(2).(3)直至新的质心与原质心相等或迭代次数大于指定阈值,算法结束 算法实现 随机初始化k个质心,用dict保存质心的值以及被聚类到该簇中的所有data. def initCent(dataSe

python实现鸢尾花三种聚类算法(K-means,AGNES,DBScan)

一.分散性聚类(kmeans) 算法流程: 1.选择聚类的个数k. 2.任意产生k个聚类,然后确定聚类中心,或者直接生成k个中心. 3.对每个点确定其聚类中心点. 4.再计算其聚类新中心. 5.重复以上步骤直到满足收敛要求.(通常就是确定的中心点不再改变. 优点: 1.是解决聚类问题的一种经典算法,简单.快速 2.对处理大数据集,该算法保持可伸缩性和高效率 3.当结果簇是密集的,它的效果较好 缺点 1.在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用 2.必须事先给出k(要生成的簇的数

在Python中使用K-Means聚类和PCA主成分分析进行图像压缩

在Python中使用K-Means聚类和PCA主成分分析进行图像压缩 各位读者好,在这片文章中我们尝试使用sklearn库比较k-means聚类算法和主成分分析(PCA)在图像压缩上的实现和结果. 压缩图像的效果通过占用的减少比例以及和原始图像的差异大小来评估. 图像压缩的目的是在保持与原始图像的相似性的同时,使图像占用的空间尽可能地减小,这由图像的差异百分比表示. 图像压缩需要几个Python库,如下所示: # image processing from PIL import Image fr

k-means 聚类算法与Python实现代码

k-means 聚类算法思想先随机选择k个聚类中心,把集合里的元素与最近的聚类中心聚为一类,得到一次聚类,再把每一个类的均值作为新的聚类中心重新聚类,迭代n次得到最终结果分步解析 一.初始化聚类中心 首先随机选择集合里的一个元素作为第一个聚类中心放入容器,选择距离第一个聚类中心最远的一个元素作为第二个聚类中心放入容器,第三.四...N个同理,为了优化可以选择距离开方做为评判标准 二.迭代聚类 依次把集合里的元素与距离最近的聚类中心分为一类,放到对应该聚类中心的新的容器,一次聚类完成后求出新容器里

K-means聚类算法介绍与利用python实现的代码示例

聚类 今天说K-means聚类算法,但是必须要先理解聚类和分类的区别,很多业务人员在日常分析时候不是很严谨,混为一谈,其实二者有本质的区别. 分类其实是从特定的数据中挖掘模式,作出判断的过程.比如Gmail邮箱里有垃圾邮件分类器,一开始的时候可能什么都不过滤,在日常使用过程中,我人工对于每一封邮件点选"垃圾"或"不是垃圾",过一段时间,Gmail就体现出一定的智能,能够自动过滤掉一些垃圾邮件了.这是因为在点选的过程中,其实是给每一条邮件打了一个"标签&qu

Python机器学习算法之k均值聚类(k-means)

一开始的目的是学习十大挖掘算法(机器学习算法),并用编码实现一遍,但越往后学习,越往后实现编码,越发现自己的编码水平低下,学习能力低.这一个k-means算法用Python实现竟用了三天时间,可见编码水平之低,而且在编码的过程中看了别人的编码,才发现自己对numpy认识和运用的不足,在自己的代码中有很多可以优化的地方,比如求均值的地方可以用mean直接对数组求均值,再比如去最小值的下标,我用的是argsort排序再取列表第一个,但是有argmin可以直接用啊.下面的代码中这些可以优化的并没有改,

K均值聚类算法的Java版实现代码示例

1.简介 K均值聚类算法是先随机选取K个对象作为初始的聚类中心.然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心.聚类中心以及分配给它们的对象就代表一个聚类.一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算.这个过程将不断重复直到满足某个终止条件.终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小. 2.什么是聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织

python机器学习实战之K均值聚类

本文实例为大家分享了python K均值聚类的具体代码,供大家参考,具体内容如下 #-*- coding:utf-8 -*- #!/usr/bin/python ''''' k Means K均值聚类 ''' # 测试 # K均值聚类 import kMeans as KM KM.kMeansTest() # 二分K均值聚类 import kMeans as KM KM.biKMeansTest() # 地理位置 二分K均值聚类 import kMeans as KM KM.clusterClu

Python机器学习算法库scikit-learn学习之决策树实现方法详解

本文实例讲述了Python机器学习算法库scikit-learn学习之决策树实现方法.分享给大家供大家参考,具体如下: 决策树 决策树(DTs)是一种用于分类和回归的非参数监督学习方法.目标是创建一个模型,通过从数据特性中推导出简单的决策规则来预测目标变量的值. 例如,在下面的例子中,决策树通过一组if-then-else决策规则从数据中学习到近似正弦曲线的情况.树越深,决策规则越复杂,模型也越合适. 决策树的一些优势是: 便于说明和理解,树可以可视化表达: 需要很少的数据准备.其他技术通常需要

python实现k均值算法示例(k均值聚类算法)

简单实现平面的点K均值分析,使用欧几里得距离,并用pylab展示. 复制代码 代码如下: import pylab as pl #calc Euclid squiredef calc_e_squire(a, b):    return (a[0]- b[0]) ** 2 + (a[1] - b[1]) **2 #init the 20 pointa = [2,4,3,6,7,8,2,3,5,6,12,10,15,16,11,10,19,17,16,13]b = [5,6,1,4,2,4,3,1,

python机器学习案例教程——K最近邻算法的实现

K最近邻属于一种分类算法,他的解释最容易,近朱者赤,近墨者黑,我们想看一个人是什么样的,看他的朋友是什么样的就可以了.当然其他还牵着到,看哪方面和朋友比较接近(对象特征),怎样才算是跟朋友亲近,一起吃饭还是一起逛街算是亲近(距离函数),根据朋友的优秀不优秀如何评判目标任务优秀不优秀(分类算法),是否不同优秀程度的朋友和不同的接近程度要考虑一下(距离权重),看几个朋友合适(k值),能否以分数的形式表示优秀度(概率分布). K最近邻概念: 它的工作原理是:存在一个样本数据集合,也称作为训练样本集,并

Python机器学习logistic回归代码解析

本文主要研究的是Python机器学习logistic回归的相关内容,同时介绍了一些机器学习中的概念,具体如下. Logistic回归的主要目的:寻找一个非线性函数sigmod最佳的拟合参数 拟合.插值和逼近是数值分析的三大工具 回归:对一直公式的位置参数进行估计 拟合:把平面上的一些系列点,用一条光滑曲线连接起来 logistic主要思想:根据现有数据对分类边界线建立回归公式.以此进行分类 sigmoid函数:在神经网络中它是所谓的激励函数.当输入大于0时,输出趋向于1,输入小于0时,输出趋向0

Python聚类算法之基本K均值实例详解

本文实例讲述了Python聚类算法之基本K均值运算技巧.分享给大家供大家参考,具体如下: 基本K均值 :选择 K 个初始质心,其中 K 是用户指定的参数,即所期望的簇的个数.每次循环中,每个点被指派到最近的质心,指派到同一个质心的点集构成一个.然后,根据指派到簇的点,更新每个簇的质心.重复指派和更新操作,直到质心不发生明显的变化. # scoding=utf-8 import pylab as pl points = [[int(eachpoint.split("#")[0]), in

Python机器学习k-近邻算法(K Nearest Neighbor)实例详解

本文实例讲述了Python机器学习k-近邻算法.分享给大家供大家参考,具体如下: 工作原理 存在一份训练样本集,并且每个样本都有属于自己的标签,即我们知道每个样本集中所属于的类别.输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后提取样本集中与之最相近的k个样本.观察并统计这k个样本的标签,选择数量最大的标签作为这个新数据的标签. 用以下这幅图可以很好的解释kNN算法: 不同形状的点,为不同标签的点.其中绿色点为未知标签的数据点.现在要对绿色点进行预测.由图不难得出

k均值算法c++语言实现代码

复制代码 代码如下: //k-mean.h #ifndef KMEAN_HEAD #define KMEAN_HEAD #include <vector> #include <map> //空间点的定义 class Node {     public:        double pos_x;        double pos_y;        double pos_z;      Node()      {          pos_x = 0.0;          pos