阅读 425

图像聚类 K-means算法实现

0、图像聚类

0.1 什么是图像聚类?

聚类是一种运用广泛的探索性数据分析技术,直观上讲,聚类是将对象进行分组的一项任务,使相似的对象归为一类,不相似的对象归为不同类中。

当聚类对象是图像的时候,就是所谓的图像聚类。

更为详细的介绍,可参考文后的参考资料[1]。

图像聚类就是在给出的图像集合中,根据图像的内容,在无先验知识的情况下,将图像按照相似度进行分类。使得分类后的图像类内相似度高,类间相似度低。中国有句俗话叫做“物以类聚,人以群分”,大概就是这个意思吧。

0.2 聚类算法的分类

前面讲到聚类是将相似度高的对象聚到一类中,如何来衡量对象之间的相似度是个关键问题。

按照聚类的尺度,聚类方法可以被分为以下三种:

  • 基于距离的聚类算法: 使用各种各样的距离来衡量数据对象之间的相似度
  • 基于密度的聚类算法: 依据合适的密度函数来进行分类
  • 基于互连性的聚类算法: 通常基于图或超图模型,将高度连通的对象聚为一类。

下面的部分主要介绍K-means聚类方法。

1、K-means聚类算法

K-means算法是一种基于距离的聚类算法,也叫做K均值K平均,也经常被称为劳埃德(Lloyd)算法。是通过迭代的方式将数据集中的各个点划分到距离它最近的簇内,距离指的是数据点到簇中心的距离。

1.1 K-means基本原理

K-means算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本划分为K个簇。将簇内的数据尽量紧密的连在一起,而让簇间的距离尽量的大。

Kmeans步骤

  1. 随机初始化k个簇中心坐标
  2. 计算数据集内所有对象到k个簇中心的距离,并将数据点划分到最近的簇
  3. 对每一个簇,重新计算该簇的质心,为当前簇内节点的坐标平均值
  4. 重复第2,3步直到收敛

终止条件有:

  • 不再有重新的分配
  • 达到最大迭代次数
  • 所有类中心移动小于某个值

K-means问题

  1. 贪心算法: 经常陷入局部最优解

    • 类中心个数K的选取
    • 初始点选取
  2. 对噪声或离群点比较敏感

    无法区分出哪些是噪声或者离群点,只能给每个数据点都判断出一个类别来,这样会导致样本质心偏移,导致误判或者聚类紧密程度降低。

  3. 样本点形状对聚类的影响

    K-means算法对于凸性数据具有良好的效果,能够根据聚类来将数据分为球状类的簇,但对于非凸形状的数据点就无能为力了,比如环形数据等等。如下图左边是K-means方法的聚类效果。

1.2 K-means中的参数

1. K值

聚类中心的个数K需要事先给定。K值的选取直接影响最终的聚类效果。

选取方法:

  1. elbow method通过绘制K和损失函数的关系图,选择拐点处的K值。即使用多个值进行尝试,取聚类指标最优或提升的转折点。
  2. 经验选取。根据人工经验先定几个K,多次随机初始化中心选经验上最合适的。

通常是根据经验选取,因为实际操作中拐点不明显,且效率太低,实际中不允许这样做。

elbow method也叫做“手肘法”,是利用误差平方和(SSE)的变化趋势来作为选取K值的指标。

SSE = \Sigma_{i=1}^{k} \Sigma_{p\in C_i}|p-m_i|^2

其中,C_i是第i个簇,pC_i中的样本点,m_iC_i的质心,SSE是所有样本的聚类误差,表示聚类效果的好坏。

如下图所示,当K取值为2~7时,对应的聚类结果,当K=5时的效果最好。

2. 初始聚类中心(质心)

K-means选择的初始点不同获得的最终分类结果也可能不同。在实际使用中,我们并不知道待聚类的数据集中哪些是我们关注的label,人工事先指定质心是不现实的。

一般初始质心的选择方法是:

  • 随机选择
  • Kmeans++方式
    • 第一个类中心->随机选取
    • D(x)为数据点x距最近的聚类中心的距离
    • 选取下一个聚类中心,选取的概率正比于D(x)^2
    • 以此类推,到第K个。

3. 距离度量

距离是K-means中衡量簇内样本点相似度的指标。

K-means中比较常用的距离度量方法是:

  • 欧几里得距离
  • 余弦相似度
  • 曼哈顿距离

2、K-means实现之sklearn

Python中的sklearn库中提供了K-means聚类的实现方法,我们可以直接调用。

对于图像聚类来讲,我们需要提取表示图像内容的特征x_ix_id维的特征向量。具有N个图像,其特征向量表示为X=(x_1, x_2, x_3,....x_n),维度为(n, d)

示例:

from sklearn.cluster import KMeans
import numpy as np

# X表示一组图像的特征向量
X = np.array([[1, 2], [1, 4], [1, 0],
           [4, 2], [4, 4], [4, 0]])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
kmeans.labels_
# array([0, 0, 0, 1, 1, 1], dtype=int32)
kmeans.predict([[0, 0], [4, 4]])
# array([0, 1], dtype=int32)
kmeans.cluster_centers_
# array([[ 1.,  2.],
#        [ 4.,  2.]])
复制代码

2.1 KMeans类

class 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=1, algorithm='auto')
复制代码

参数:

参数 含义
n_clsuters int, 可选,默认值为8。聚类中心的个数,即聚类的类数
init {‘k-means++’, 'random'或一个ndarray},初始化质心的方法,默认是'k-means++'‘random’随机从训练数据中选初始质心,如果传递一个ndarray,应该行如(n_clusters, n_features)并给出初始质心
n_init int,默认10,用不同质心初始化运行算法的次数,最终解是在inertia意义下选出的最优结果
max_iter int,默认300,执行一次K-means算法的最大迭代次数
tol float型,默认0.0001
precompute_distances {auto, True, False}预先计算距离值(更快,但占用更多内存),对一组数据只运行较少次聚类结果时,不需要预选计算。
verbose int型,默认0,是否打印中间过程,0是不打印
random_state int型,RandomState的实例或None,可选,默认None。如果是intrandom_state是随机数生成器使用的种子,如果是RandomState实例,random_state是随机数生成器,如果是None,随机数生成器是由np.randomRandomState实例
n_jobs int型,使用的计算力的数量,通过计算并行运行的每个n_init来实现。如果是-1,则所有CPU全部使用,如果指定为1,则不使用并行代码,方便调试。该值小于-1,则使用 (n_cpus + 1 + n_jobs) . 对于n_jobs = -2, 使用n_cpus-1.
algorithm 可选值'auto', 'full','elkan'。'full'是传统的K-means算法,'elkan'是elkan K-means算法,默认值‘auto’会根据数据值是否稀疏,来决定如何选择'full'和'elkan'。一般,数据稠密选‘elkan’,否则就是'full'。

主要属性:

属性 含义
cluster_centers_ 向量[n_clsuters, n_features],每个簇中心的坐标
Labels_ 每个数据的分类标签,从0开始
inertia_ float型,每个数据点到其簇的质心的距离之和,用来评估簇的个数是否合适

2.2 KMeans类方法

1. fit()

对Kmeans确定类别以后的数据集进行聚类.

定义:

def fit(self, X, y=None)
    random_state = check_random_state(self.random_state)
    X = self._check_fit_data(X)

    self.cluster_centers_, self.labels_, self.inertia_, self.n_iter_ = \
        k_means(
            X, n_clusters=self.n_clusters, init=self.init,
            n_init=self.n_init, max_iter=self.max_iter, verbose=self.verbose,
            precompute_distances=self.precompute_distances,
            tol=self.tol, random_state=random_state, copy_x=self.copy_x,
            n_jobs=self.n_jobs, algorithm=self.algorithm,
            return_n_iter=True)
    return self
复制代码

内部调用k_means函数进行聚类,返回self

调用k_means()函数,会返回self.cluster_centers_,self.labels_, self.inertia_, self.n_iter_

  • self.cluster_centers_:聚类中心,shape为 (k, n_features)
  • self.labels_int,聚类索引值,shape为(n_samples,)
  • self.inertia_:聚类失真值(训练集中所有观测到的距离的平方之和)
  • self.n_iter_:最佳结果对应的迭代次数,只有当 return_n_iter 设为True时返回。

2. predict()

根据聚类结果,确定所属类别

def predict(self, X)
复制代码
  • X:{array, sparse matrix},shape是[n_samples, n_features] 返回值:
  • labelsarray, shape是[n_samples,]。每个样例属于聚类的类别索引。

3. fit_predict

def fit_predict(self, X, y=None)
    return self.fit(X).labels_
复制代码

返回值:

  • labelsarray, shape是[n_samples,]。每个样例属于聚类的类别索引值。

计算聚类中,并预测每个sample的聚类索引。

等效于,调用fit(X)方法之后,调用predict(X)函数。

注意:在此函数中,返回的是self.fit(X).labels_属性。

4. transform

def transform(self, X)
复制代码

将X转化为聚类-距离空间

返回值:

  • X_newarray, shape是[n_samples, k]

5. fit_transform

def fit_transform(self, X, y=None)
复制代码

进行聚类运算,并将X转化到距离空间。

等效于,调用fit(X)方法之后,调用transform(X)函数,但是更为有效。

重要,sklearn中的Kmeans方法无法指定距离度量方法,默认使用欧式距离

K-means默认使用的是欧式距离,这是算法设计之初的度量基础。原因是涉及平均值的计算。

来自: 聚类分析 - sklearn的kmeans使用的是哪种距离度量? - IT屋-程序员软件开发技术分享社区

3、K-means实现之scipy

scipy库中也实现了K-means算法。

中心索引或聚类索引也被称为 “code” ,code到中心的映射表被称为 “code book”.

3.1 kmeans函数

使用kmeans函数进行聚类,需要两步来实现

  1. 使用kmeans函数生成codebook和失真值
  2. 使用vq函数将codebook分配到每个观察数据上,并得到每个观测数据到它最近中心点的距离。

示例:

import scipy
from scipy.cluster.vq import kmeans, vq, whiten
import numpy as np

#生成待聚类的数据点,这里生成了20个点,每个点4维:
points=scipy.randn(20,4) 

data=whiten(points) # 将原始数据做归一化处理
#返回聚类中心的映射表和损失
codebook, variance = kmeans(data, 4) 
# 使用vq函数根据聚类中心对所有数据进行分类,vq的输出所有数据的label和距离
code, distance = vq(data, codebook)

# 结果
>>> codebook # (4,4)
array([[-1.227829  , -0.41256122, -0.1342359 , -0.98257834],
       [ 1.01190005, -0.34999089, -0.13180372,  0.06394479],
       [ 0.01156929, -0.39212056,  1.86893218, -0.34921357],
       [ 0.21946277,  1.36809613,  0.87196001,  0.9213216 ]])
>>>variance
1.221658211170926

>>> code
array([2, 0, 0, 2, 0, 2, 1, 3, 1, 1, 3, 0, 1, 0, 1, 1, 3, 2, 3, 2],
      dtype=int32)
>>>distance
array([1.32927696, 0.99594691, 1.38351644, 1.22323281, 1.12605626,
       2.04444249, 0.55554746, 2.06947197, 1.44928466, 1.09481098,
       1.60957745, 1.07210177, 1.3848659 , 0.6393925 , 0.69392457,
       1.06200234, 1.09091552, 0.87726365, 0.76938663, 1.96214695])
复制代码

kmeans函数定义:

def kmeans(obs, k_or_guess, iter=20, thresh=1e-5, check_finite=True)
复制代码

参数:

  • obsndarrayMxN数组,每行表示一个观测矢量。特征必须进过whiten函数处理
  • k_or_guessint或者ndarray,产生的中心点的个数,每个中心点分配一个code,这也是质心在生成的code_book矩阵中的行索引,通过从观测矩阵中随机选择观测值来选择初始k中心。也可以通过传入一个kxN的数组来指定初始k中心点。
  • iterint,可选值。运行k均值算法的次数,返回具有最低失真的code book,如果为k_or_guess参数的数组指定了初始质心,则将忽略此参数,此参数不代表k均值算法的迭代次数
  • threshfloat,可选值。如果自上次k均值迭代以来失真的变化小于或等于阈值,则终止k均值算法。
  • check_finitebool,可选值,默认值:True。是否检查输入矩阵仅包含有限数。禁用可能会提高性能,但是如果输入中确实包含无穷大或NaN,则可能会导致问题(崩溃,终止)。

返回:

  • codebookndarray,由k个质心组成的维度(k,N)的数组
  • distortionfloat型,观测值与生成的中心点之间的平均欧式距离(非平方)。请注意,在K-means算法中失真的标准定义是平方距离总和。

注意: 1. `kmeans`函数中,`iter`参数用来指定运行K均值算法的次数,而不是迭代次数。算法终止条件只能通过`thresh`参数来指定。 2. 距离度量使用的是平均欧式距离(非平方)

vq函数定义:

def vq(obs, code_book, check_finite=True)
复制代码

code book中的每一个code分配给观察值。在MXN的数组中的每个观察矢量与code book中的质心进行比较,并为其分配最接近质心的code.

obs中的特征应该具有单位方差,可以通过将他们传递给whiten函数来实现。code book可以使用K-means算法或其他编码算法来创建。

参数:

  • obsMxN数组,每一行代表一个观测值。特征必须经过whiten函数处理。
  • code_bookndarray。通常使用k-means算法生成,每一行表示一个不同的code,列表示code的特征值。
  • check_finitebool,可选值,默认是True。是否检查输入数组中仅包含有限值。禁用可能会提高性能,但如果输入内容确实包含无穷大或NaN,则可能会导致问题(崩溃,终止)。

返回值:

  • code: ndarray,长度为M的数组,用于保存每个观察数据的code book
  • dist: ndarray``,(M,)每个观察数据到它最近code的失真值。

3.2 kmeans2函数

该函数也是用来实现K-means算法。该算法尝试最小化观测值和质心之间的欧几里得距离,包括几种初始化方法。

scipy.cluster.vq.kmeans2(data, k, iter=10, thresh=1e-05, minit='random', missing='warn', check_finite=True)
复制代码

参数:

  • data:ndarray(M,N)的数组,包含M个具有N维的观测数据。
  • k:int or ndarray,聚类个数。如果minit参数是matrix,或者如果给定一个ndarray,它被解释为初始聚类,以代替使用。
  • iter:int,可选值,k-means算法运行的迭代次数,注意,与kmeans函数的iter参数的含义不同。
  • thresh:float,可选值,没有使用
  • minit:str,可选值,初始化方法。可选择random, points,++matrix
    • random:从高斯生成k个质心,均值和方差根据数据估算出
    • points:从数据中随机选择k个观测值(行)作为初始中心
    • ++:根据kmeans++方法选择k个观测值
    • matrix:将k参数解释为初始质心的(k,M)数组
  • missing:str,可选值,用于解决空聚类的方法,可用方法有warnraise
    • warn:给出警告并继续
    • raise:引发ClusterError并终止算法
  • check_finite:bool,可选值,是否检查输入矩阵仅包含有限数,默认True

返回值:

  • centroid:ndarray:一个(k,N)的数组,表示k-means方法最后一次迭代的中心点
  • label:ndarray,每个观测值的代码或索引值。label [i]是第i个观测值最接近的质心的代码或索引

示例

import scipy
from scipy.cluster.vq import kmeans2, whiten
import numpy as np

#生成待聚类的数据点,这里生成了20个点,每个点4维:
points=scipy.randn(20,4) 

data=whiten(points) # 将原始数据做归一化处理
centroid, label = kmeans2(data, 5)

# 结果
>>> centroid
array([[ 0.52132816,  0.97577703, -0.30863464, -1.30546523],
       [-0.27344139, -0.81129939, -0.59560322,  0.47788319],
       [ 1.99658961, -0.10701021,  1.09921144,  0.51397034],
       [-0.37598454,  1.72180727, -0.18127439,  0.58114466],
       [ 0.25895367, -0.01881385,  1.25681737,  0.03119893]])
>>> label
array([1, 0, 3, 0, 1, 1, 2, 4, 0, 1, 1, 0, 4, 4, 0, 3, 1, 4, 3, 2],
      dtype=int32)
复制代码

4、参考资料

[1]各类聚类(clustering)算法初探 - 郑瀚Andrew.Hann - 博客园

[2]特征提取方法:聚类之Kmeans - Jack_Kuo的博客 - CSDN博客

[3]sklearn.cluster.KMeans — scikit-learn 0.17 文档

[4]K-means clustering and vector quantization (scipy.cluster.vq) — SciPy v1.3.1 Reference Guide

关注下面的标签,发现更多相似文章
评论