K-平均聚类算法(k -means Clustering)(k-

作者: 原上的小木屋 | 来源:发表于2020-06-12 00:13 被阅读0次

第六章数据聚类算法——基于K-Means聚类算法
算法笔记（4）-K-Means聚类算法及python代码实现
机器学习(十五) K-means 算法
K-平均聚类算法(k -means Clustering)(k-
基于Spark的机器学习实践 (九) - 聚类算法
机器学习A-Z～K平均聚类算法
【机器学习实战】第10章 K-Means（K-均值）聚类算法
sklearn调包侠之K-Means
《机器学习实战》笔记（十）：Ch10 - 利用k-均值聚类算法对
【机器学习】无监督学习 K-means(K-均值聚类算法）

主要思想

k-平均聚类算法在类别数已知时使用。在质心不断明确的过程中完成特征量的分类任务。

具体步骤

为每个数据随机分配类；
计算每个类的重心；
计算每个数据与重心之间的距离，将该数据分到重心距离最近的那一类；
重复步骤2和步骤3直到没有数据的类别再改变为止。

以减色化和直方图作为特征量来执行以下的算法

对图像进行减色化处理，然后计算直方图，将其用作特征量；
对每张图像随机分配类别0或类别1（在这里，类别数为2，以np.random.seed(1)作为随机种子生成器。当np.random.random小于th时，分配类别0；当np.random.random大于等于th时，分配类别1，在这里th=0.5）；
分别计算类别0和类别1的特征量的质心（质心存储在gs = np.zeros((Class, 12), dtype=np.float32)中）；
对于每个图像，计算特征量与质心之间的距离（在此取欧氏距离），并将图像指定为质心更接近的类别。
重复步骤3和步骤4直到没有数据的类别再改变为止。

import cv2
import numpy as np
import matplotlib.pyplot as plt
from glob import glob#导入三个关于图像处理主要的库，opencv、numpy、matplotlib以及关于路径操作的glob库
# Dicrease color对图像减色处理
def dic_color(img):
    img //= 63
    img = img * 64 + 32
    return img
# Database
def get_DB():
    # get training image path
    train = glob("123//test//*")#准备测试数据集
    train.sort()
    # prepare database
    db = np.zeros((len(train), 13), dtype=np.int32)
    pdb = []
    # each train
    for i, path in enumerate(train):#对于每一个图像
        # read image
        img = dic_color(cv2.imread(path))#先对其进行减色化处理
        # histogram绘制直方图
        for j in range(4):每一个通道给4个占位用来存放32、96、160、224的像素点
            db[i, j] = len(np.where(img[..., 0] == (64 * j + 32))[0])#对像素点进行计数
            db[i, j + 4] = len(np.where(img[..., 1] == (64 * j + 32))[0])#对像素点进行计数
            db[i, j + 8] = len(np.where(img[..., 2] == (64 * j + 32))[0])#对像素点进行计数，这一步骤完成，db与KNN中的db一样，每一个图片就成为了一个1行13列的特征向量
        # get class
        if 'akahara' in path:
            cls = 0
        elif 'madara' in path:
            cls = 1
        # store class label
        db[i, -1] = cls#对db的第13位上的索引打上标签
        # add image path
        pdb.append(path)
    return db, pdb#返回图像集的特征向量和路径
# k-Means step1#k-Means第一步
def k_means_step1(db, pdb, Class=2):#划分的类为两类，将参数输入
    # copy database
    feats = db.copy()#db备份
    # initiate random seed
    np.random.seed(1)#np.random.seed()函数可以保证生成的随机数具有可预测性。
    # assign random class
    for i in range(len(feats)):#先随机把图片的标签打乱，让其自动产生聚类
        if np.random.random() < 0.5:
            feats[i, -1] = 0
        else:
            feats[i, -1] = 1
    # prepare gravity
    gs = np.zeros((Class, 12), dtype=np.float32)#准备一个2行12列的数组
    # get gravity
    for i in range(Class):#对于每一个类别
        gs[i] = np.mean(feats[np.where(feats[..., -1] == i)[0], :12], axis=0)#对打第一类标签的图片的特征向量取均值，这就是所谓的每个类的质心
    print("assigned label")
    print(feats)
    print("Grabity")
    print(gs)#将每个类的质心打印出来
db, pdb = get_DB()
k_means_step1(db, pdb)

如代码中分析的那样，上述代码只是计算了每个类别的质心在哪里，只算是完成了K-means的第一个步骤，接下来我们进行后续步骤

import cv2
import numpy as np
import matplotlib.pyplot as plt
from glob import glob
# Dicrease color#引入四个包
def dic_color(img):#减色
    img //= 63
    img = img * 64 + 32
    return img
# Database
def get_DB():
    # get training image path#准备图像数据
    train = glob("123//test//*")
    train.sort()
    # prepare database
    db = np.zeros((len(train), 13), dtype=np.int32)
    pdb = []
    # each train
    for i, path in enumerate(train):
        # read image
        img = dic_color(cv2.imread(path))
        # histogram
        for j in range(4):
            db[i, j] = len(np.where(img[..., 0] == (64 * j + 32))[0])
            db[i, j+4] = len(np.where(img[..., 1] == (64 * j + 32))[0])
            db[i, j+8] = len(np.where(img[..., 2] == (64 * j + 32))[0])
        # get class
        if 'akahara' in path:
            cls = 0
        elif 'madara' in path:
            cls = 1
        # store class label
        db[i, -1] = cls
        # add image path
        pdb.append(path)
    return db, pdb#返回图像特征向量和路径
# k-Means step2#k-means第二步
def k_means_step2(db, pdb, Class=2):
    # copy database
    feats = db.copy()
    # initiate random seed
    np.random.seed(1)
    # assign random class
    for i in range(len(feats)):
        if np.random.random() < 0.5:
            feats[i, -1] = 0
        else:
            feats[i, -1] = 1#到这里还和上面的代码类似，先把标签打乱
    while True:
        # prepare greavity
        gs = np.zeros((Class, 12), dtype=np.float32)
        change_count = 0
        # compute gravity#计算每个类别的质心
        for i in range(Class):
            gs[i] = np.mean(feats[np.where(feats[..., -1] == i)[0], :12], axis=0)
        # re-labeling
        for i in range(len(feats)):#对于每个图像，计算他们与两个质心的距离
            # get distance each nearest graviry
            dis = np.sqrt(np.sum(np.square(np.abs(gs - feats[i, :12])), axis=1))
            # get new label
            pred = np.argmin(dis, axis=0)#得到最小的距离索引标签
            # if label is difference from old label
            if int(feats[i, -1]) != pred:#如果标签和最小距离的标签不一致
                change_count += 1#同时交换次数加1，循环结束时判断交换次数看有没有增加，没有增加说明聚类趋于稳定，终止循环
                feats[i, -1] = pred#就把标签换掉
        if change_count < 1:#如果循环次数没增加即终止循环
            break
    for i in range(db.shape[0]):
        print(pdb[i], " Pred:", feats[i, -1])#输出预测结果
db, pdb = get_DB()
k_means_step2(db, pdb)

使用K-means进行图像减色

在之前的代码中，我们涉及到了减色处理，但都是固定减多少颜色。这里，我们使用k−平均聚类算法用于动态确定要减少的颜色。
算法如下

从图像中随机选取K个RGB分量（这我们称作类别）。
将图像中的像素分别分到颜色距离最短的那个类别的索引中去，色彩距离按照下面的方法计算： $dis=\sqrt{(R−R′)^2+(G−G′)^2+(B−B′)^2}$
计算各个索引下像素的颜色的平均值，这个平均值成为新的类别；
如果原来的类别和新的类别完全一样的话，算法结束。如果不一样的话，重复步骤2和步骤3；
将原图像的各个像素分配到色彩距离最小的那个类别中去。

import cv2
import numpy as np
import matplotlib.pyplot as plt
from glob import glob#照例导入四个包
# K-means step1#k-means第一步
def k_means_step1(img, Class=10):#将图像和聚类划分的类别数作为参数传入
    #  get shape获取图像尺寸
    H, W, C = img.shape
    # initiate random seed
    np.random.seed(0)
    # reshape重塑图像矩阵，将其拉成1列，共计H*W行，每一行代表一个像素点的BGR值
    img = np.reshape(img, (H * W, -1))
    # select one index randomly随机选取class个索引，对于我们的代码来说，就是随机选取10个值
    i = np.random.choice(np.arange(H * W), Class, replace=False)
    Cs = img[i].copy()
    print(Cs)
    clss = np.zeros((H * W), dtype=int)#构造一个与图像尺寸一样大的clss数组，拍平，一行H*W列的数组
    # each pixel#对于每一个像素
    for i in range(H * W):
        # get distance from base pixel#分别计算像素与10个基类之间的距离
        dis = np.sqrt(np.sum((Cs - img[i]) ** 2, axis=1))
        # get argmin distance#选取最小的距离将基类的索引做标记
        clss[i] = np.argmin(dis)
    # show
    out = np.reshape(clss, (H, W)) * 50#将clss作为像素值绘制出来
    out = out.astype(np.uint8)
    return out#返回图像
# read image
img = cv2.imread("123.jpg").astype(np.float32)
# K-means step2
out = k_means_step1(img)
cv2.imwrite("out.jpg", out)
cv2.imshow("result", out)
cv2.waitKey(0)

上述代码仅仅迭代了一次，聚类还没达到稳定，我们增加一些代码，使聚类趋于稳定

import cv2
import numpy as np
import matplotlib.pyplot as plt
from glob import glob#依旧引入四个包
def k_means(img, Class=5):
    # get shape获取图像的尺寸
    H, W, C = img.shape
    # initiate random seed
    np.random.seed(0)
    # reshape image
    img = np.reshape(img, (H * W, -1))
    # get index randomly
    i = np.random.choice(np.arange(H * W), Class, replace=False)
    Cs = img[i].copy()#直至这一步，一切代码还和上面相同
    while True:
        # prepare pixel class label#对于准备的每一个标签
        clss = np.zeros((H * W), dtype=int)
        # each pixel#对于每一个元素
        for i in range(H * W):
            # get distance from index pixel
            dis = np.sqrt(np.sum((Cs - img[i]) ** 2, axis=1))#计算与不同标签像素点的距离
            # get argmin distance
            clss[i] = np.argmin(dis)#获取最小标签索引
        # selected pixel values选定像素值
        Cs_tmp = np.zeros((Class, 3))#创建临时数组，用来存放class个质点的值
        # each class label#对于每一个标签
        for i in range(Class):
            Cs_tmp[i] = np.mean(img[clss == i], axis=0)#计算每个类的均值，将其放入Cs_tmp这个临时数组中，待质点值不再发生变化，聚类结束
        # if not any change
        if (Cs == Cs_tmp).all():
            break
        else:
            Cs = Cs_tmp.copy()
    # prepare out image
    out = np.zeros((H * W, 3), dtype=np.float32)#创建输出图像
    # assign selected pixel values
    for i in range(Class):#对于每一个类
        out[clss == i] = Cs[i]#在输出图像中对属于同一类的像素进行赋值
    print(Cs)
    out = np.clip(out, 0, 255)#将像素值在0-255之外截断
    # reshape out image
    out = np.reshape(out, (H, W, 3))#输出图像
    out = out.astype(np.uint8)
    return out
# read image
img = cv2.imread("123.jpg").astype(np.float32)
# K-means
out = k_means(img)
cv2.imwrite("out.jpg", out)
cv2.imshow("result", out)
cv2.waitKey(0)

第六章数据聚类算法——基于K-Means聚类算法
6.2 基于K-Means聚类算法 K平均算法是一种无监督的机器学校算法。K-平均聚类与K-邻近之间没有任何关系。...
算法笔记（4）-K-Means聚类算法及python代码实现
K-Means算法也被称为K-平均或K-均值算法，是一种广泛使用的聚类算法。K-Means算法是基于相似性的无监督...
机器学习(十五) K-means 算法
1 简介 K-means称为K-平均算法，简单来讲K-平均聚类算法的目的就是：把 n个点（可以是样本的一次观察或...
K-平均聚类算法(k -means Clustering)(k-
主要思想 k-平均聚类算法在类别数已知时使用。在质心不断明确的过程中完成特征量的分类任务。具体步骤为每个数据随...
基于Spark的机器学习实践 (九) - 聚类算法
1 k-平均算法(k-means clustering)概述 1.1 回顾无监督学习 ◆ 分类、回归都属于监督学习...
机器学习A-Z～K平均聚类算法
本文来讲讲K平均聚类算法(K-Means Clustering),K Means算法是所有聚类算法中最经典的一种，...
【机器学习实战】第10章 K-Means（K-均值）聚类算法
第 10 章 K-Means（K-均值）聚类算法 K-Means 算法聚类是一种无监督的学习, 它将相似的对象归...
sklearn调包侠之K-Means
K-Means算法 k-均值算法（K-Means算法）是一种典型的无监督机器学习算法，用来解决聚类问题。算法流程...
《机器学习实战》笔记（十）：Ch10 - 利用k-均值聚类算法对
第10章 K-均值聚类算法(代码) K-均值算法的优缺点K-均值是发现给定数据集的 K 个簇的聚类算法, 之所以称...
【机器学习】无监督学习 K-means(K-均值聚类算法）
任务利用K-均值聚类算法对未标注数据分组对聚类得到的簇进行后处理二分K-均值聚类算法思想聚类算法几乎可以...