草庐IT

KMeans算法与GMM混合高斯聚类

LeonYi 2023-07-10 原文

一、K-Means

K-Means是GMM的特例（硬聚类，基于原型的聚类）。假设多元高斯分布的协方差为0，方差相同。
 
K-Means算法思想
对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
N个d维样本，时间复杂度 O(kLNd)
  1. 初始K个类（簇心）
  2. E步：对每个样本，计算到K个类的欧式距离，并分配类标签 O(kNd)
  3. M步：基于类内的样本，以样本均值更新类（均值最小化，类到类内样本的误差） O(Nd)
  4. 重复2-3步，直到聚类结果不变化或收敛
迭代次数为L
 
收敛性证明：
 
聚类处理：
特征归一化，缺失值，异常值
 
K-Means的主要优点有：
　　1）基于原型的聚类，实现简单收敛速度快。
　　2）聚类效果较优。
　　3）算法的可解释度比较强。
　　4）主要需要调参的参数仅仅是簇数k。
K-Means的主要缺点有：
　　1）K值的选取不好把握
　　2）对于不是凸的数据集比较难收敛
　　3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
　　4） 采用迭代方法，得到的结果只是局部最优（本身是个NP-hard问题，组合优化，多项式系数）
　　5） 对噪音和异常点比较的敏感。
  
# 基于Cursor生成的代码
import numpy as np

def k_means(X, k, max_iters=100):
    # randomly initialize centroids
    centroids = X[np.random.choice(range(len(X)), k, replace=False)]
    
    for i in range(max_iters):
        # calculate distances between each point and each centroid
        distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))
        
        # assign each point to the closest centroid
        labels = np.argmin(distances, axis=0)
        
        # update centroids to be the mean of the points assigned to them
        for j in range(k):
            centroids[j] = X[labels == j].mean(axis=0)
    
    return centroids, labels

d = 3
k = 3
X = np.random.rand(100, 3)
centroids, labels = k_means(X, k, max_iters=100)

import matplotlib.pyplot as plt

fig = plt.figure(figsize=(10, 7))
ax = fig.add_subplot(111, projection='3d')

ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=labels, cmap='viridis')
ax.scatter(centroids[:, 0], centroids[:, 1], centroids[:, 2], marker='*', s=300, c='r')

ax.set_xlabel('X Label')
ax.set_ylabel('Y Label')
ax.set_zlabel('Z Label')

plt.show()

二、GMM

⾼斯分布的线性组合可以给出相当复杂的概率密度形式。
通过使⽤⾜够多的⾼斯分布，并且调节它们的均值和⽅差以及线性组合的系数，⼏乎所有的连续概率密度都能够以任意的精度近似。
对3个高斯分布的概率密度函数进行加权。考虑K个⾼斯概率密度的叠加，形式为：
混合⾼斯（mixture of Gaussians），每⼀个⾼斯概率密度N (x | µk, Σk)被称为混合分布的⼀个成分（component），并且有⾃⼰的均值µk和协⽅差Σk。
具有3个成分的混合⾼斯分布的轮廓线。参数πk被称为混合系数。GMM
 
可把πk = p(k)看成选择第k个成分的先验概率， 把 密度N (x | µk, Σk) = p(x | k)看成以k为条件的x的概率。
⾼斯混合分布的形式由参数π, µ和Σ控制，其中令π ≡ {π1, . . . , πK}, µ ≡
{µ1, . . . , µK}且Σ ≡ {Σ1, . . . , Σk}。⼀种确定这些参数值的⽅法是使⽤最⼤似然法。根据公式），对数似然函数为：
因为对数中存在⼀个求和式，导致参数的最⼤似然解不再有⼀个封闭形式的解析解：
  • ⼀种最⼤化这个似然函数的⽅法是使⽤迭代数值优化⽅法。
  • 另⼀种是使⽤EM期望最⼤化算法(对包含隐变量的似然进行迭代优化)。
 
样本x为观测数据，混合系数为隐变量，高斯分布的参数。
当成分为多元高斯分布时（d维），相当于从混合多元高斯分布中生成了样本，通过EM算法迭代地学习模型参数（均值和方差以及混合系数）。
  1. 期望：根据参数，更新样本关于类的响应度（隶属度，相当于分别和K个类计算距离并归一化）。确定响应度，就可以确定EM算法的Q函数（完全数据的对数似然关于 分布的期望），原始似然的下界。
  2. 最大化：根据响应度，计算均值、方差。
EM算法收敛后，直接求每个样本关于成分的响应度即可得到聚类结果（可软，可硬argmax）
 
当多元高斯分布的方差相同时，且每个样本只能指定给一个类时（one-hot响应度，argmax），GMM退化成K-means算法。
import numpy as np
from sklearn import datasets
import matplotlib.pyplot as plt
from sklearn.mixture import GaussianMixture
from sklearn.cluster import KMeans

# 创建数据，并可视化
X, y = datasets.make_blobs(n_samples=1500,
                             cluster_std=[1.0, 2.5, 0.5],
                             random_state=170)
plt.figure(figsize=(12,4))
plt.rcParams['font.family'] = 'STKaiti'
plt.rcParams['font.size'] = 20
plt.subplot(1,3,1)
plt.scatter(X[:,0],X[:,1],c = y)
plt.title('原始数据',pad = 20)
Kmeans聚类
kmeans = KMeans(3)
kmeans.fit(X)
y_ = kmeans.predict(X)
plt.subplot(1,3,2)
plt.scatter(X[:,0],X[:,1],c = y_)
plt.title('KMeans聚类效果',pad = 20)
GMM高斯混合模型聚类
gmm = GaussianMixture(n_components=3)
y_ = gmm.fit_predict(X)
plt.subplot(1,3,3)
plt.scatter(X[:,0],X[:,1],c = y_)
plt.title('GMM聚类效果',pad = 20)
 
plt.figtext(x = 0.51,y = 1.1,s = 'KMeans VS GMM',ha = 'center',fontsize = 30)
plt.savefig('./GMM高斯混合模型.png',dpi = 200)
优点：
  • 可以完成大部分形状的聚类
  • 大数据集时，对噪声数据不敏感
  • 对于距离或密度聚类，更适合高维特征
缺点：
  • 计算复杂高，速度较慢
  • 难以对圆形数据聚类
  • 需要在测试前知道类别的个数（成分个数，超参数）
  • 初始化参数会对聚类结果产生影响
参考
1.https://www.jianshu.com/p/2c42c567e893
2. PRML
KMeansGMMspansectioncolor人工智能

有关KMeans算法与GMM混合高斯聚类的更多相关文章

  1. ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2

    我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. ruby - 如何测试正在使用 RSpec 和 Mocha 调用的混合类方法？ - 2

    我有一个模块:moduleMyModuledefdo_something#...endend由类使用如下:classMyCommandextendMyModuledefself.execute#...do_somethingendend如何验证MyCommand.execute调用了do_something？我已经尝试使用mocha进行部分模拟，但是当未调用do_something时它不会失败:it"callsdo_something"doMyCommand.stubs(:do_something)MyCommand.executeend 最佳答案

  4. ruby-on-rails - 为什么 DataMapper 使用混合与继承？ - 2

    所以我只是对此感到好奇:DataMapper为其模型使用混合classPostincludeDataMapper::Resource虽然active-record使用继承classPost有谁知道为什么DataMapper选择这样做(或者为什么AR选择不这样做)？ 最佳答案 它允许您从另一个不是DM类的类继承。它还允许动态地将DM功能添加到类中。这是我正在处理的模块中的类方法:defdatamapper_classklass=self.dupklass.send(:include,DataMapper::Resource)klass

  5. ruby-on-rails - 将 Ruby 代码和文字标记与 Haml 混合 - 2

    如何用HAML编写这个ERB:#OR我可以:=some_ruby_code+":"#and=some_ruby_code%br但我不想在这里连接，我想将它写成内联:(=some_ruby_code):#and(=some_ruby_code)%br 最佳答案 =some_ruby_code+":"-#and=some_ruby_code+""编辑1:我不确定您在寻找什么。你想要其中之一吗？==#{some_ruby_code}:-#and==#{some_ruby_code}或==#{some_ruby_code}:-#and=so

  6. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  7. ruby - 在 Ruby 中实现 Luhn 算法 - 2

    我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s

  8. Ruby 斐波那契算法 - 2

    下面是我写的一个计算斐波那契数列中的值的方法:deffib(n)ifn==0return0endifn==1return1endifn>=2returnfib(n-1)+(fib(n-2))endend它工作到n=14，但在那之后我收到一条消息说程序响应时间太长(我正在使用repl.it)。有人知道为什么会这样吗？ 最佳答案 Naivefibonacci进行了大量的重复计算-在fib(14)fib(4)中计算了很多次。您可以将内存添加到您的算法中以使其更快:deffib(n,memo={})ifn==0||n==1returnnen

  9. ruby-on-rails - Rails add_index 算法 : :concurrently still causes database lock up during migration - 2

    为了防止在迁移到生产站点期间出现数据库事务错误，我们遵循了https://github.com/LendingHome/zero_downtime_migrations中列出的建议。(具体由https://robots.thoughtbot.com/how-to-create-postgres-indexes-concurrently-in概述)，但在特别大的表上创建索引期间，即使是索引创建的“并发”方法也会锁定表并导致该表上的任何ActiveRecord创建或更新导致各自的事务失败有PG::InFailedSqlTransaction异常。下面是我们运行Rails4.2(使用Acti

  10. ruby - 趋势算法 - 2

    我正在开发一个类似微论坛的项目，其中一个特殊用户发布一条快速(接近推文大小)的主题消息，订阅者可以用他们自己的类似大小的消息来响应。直截了当，没有任何形式的“挖掘”或投票，只是每个主题消息的响应按时间顺序排列。但预计会有很高的流量。我们想根据它们引起的响应嗡嗡声来标记主题消息，使用0到10的等级。在谷歌上搜索了一段时间的趋势算法和开源社区应用示例，到目前为止已经收集到两个有趣的引用资料，但我还没有完全理解它们:Understandingalgorithmsformeasuringtrends，关于使用基线趋势算法比较维基百科页面浏览量的讨论，在SO上。TheBritneySpearsP

随机推荐