任意维度代码的实现
基础理论
在基于anchor的目标检测算法中，anchor一般都是通过人工设计的。例如，在SSD、Faster-RCNN中，设计了9个不同大小和宽高比的anchor。然而，通过人工设计的anchor存在一个弊端，就是并不能保证它们一定能很好的适合数据集，如果anchor的尺寸和目标的尺寸差异较大，则会影响模型的检测效果。
在论文YOLOv2中提到了这个问题，作者建议使用K-means聚类来代替人工设计，通过对训练集的bounding box进行聚类，自动生成一组更加适合数据集的anchor，可以使网络的检测效果更好。
“The network can learn to adjust the boxes appropriately but if we pick better priors for the network to start with we can make it easier for the network to learn to predict good detections. Instead of choosing priors by hand, we run k-means clustering on the training set bounding boxes to automatically find good priors.”
Standard K-means
首先简单复习一下标准的K-means算法，K-means是一种简单且常用的无监督学习算法，它旨在将数据集划分成K个簇，使得相同簇之内的数据相似性高，不同簇之间的数据相似性低。
算法步骤：
初始化K个簇中心;使用相似性度量（一般是欧氏距离），将每个样本分配给与其距离最近的簇中心；计算每个簇中所有样本的均值，更新簇中心；重复2、3步，直到均簇中心不再变化，或者达到了最大迭代次数。
Anchor K-means
接下来介绍如何对bounding box进行K-means。
度量选择
通常，bounding box由左上角顶点和右下角顶点表示，即 (x1,y1,x2,y2) 。在对box做聚类时，我们只需要box的宽和高作为特征，并且由于数据集中图片的大小可能不同，还需要先使用图片的宽和高对box的宽和高做归一化，即
w
=
w
b
o
x
w
i
m
g
,
h
=
h
b
o
x
h
i
m
g
w=\frac{w_{box}}{w_{img}}, h=\frac{h_{box}}{h_{img}}
w=wimgwbox,h=himghbox
如果直接使用标准K-means中的欧氏距离作为度量，则会有个问题，就是在聚类结果中，大box簇会比小box簇产生更大的误差（squared error）。由于我们只关心anchor与box的IOU，不关心的box的大小，因此，使用IOU作为度量更加合适。
假设有
a
n
c
h
o
r
=
(
w
a
,
h
a
)
，
b
o
x
=
(
w
b
,
h
b
)
anchor=(w_{a},h_{a})，box=(w_{b},h_{b})
anchor=(wa,ha)，box=(wb,hb) ，则
I
O
U
(
b
o
x
,
a
n
c
h
o
r
)
=
i
n
t
e
r
s
e
c
t
i
o
n
(
b
o
x
,
a
n
c
h
o
r
)
u
n
i
o
n
(
b
o
x
,
a
n
c
h
o
r
)
−
i
n
t
e
r
s
e
c
t
i
o
n
(
b
o
x
,
a
n
c
h
o
r
)
IOU(box,anchor)=\frac{intersection(box,anchor)}{union(box,anchor)-intersection(box,anchor)}
IOU(box,anchor)=union(box,anchor)−intersection(box,anchor)intersection(box,anchor)
=
m
i
n
(
w
a
,
w
b
)
⋅
m
i
n
(
h
a
,
h
b
)
w
a
h
a
+
w
b
h
b
−
m
i
n
(
w
a
,
w
b
)
⋅
m
i
n
(
h
a
,
h
b
)
=\frac{min(w_{a},w_{b})\cdot min(h_{a},h_{b})}{w_{a}h_{a}+w_{b}h_{b}-min(w_{a},w_{b})\cdot min(h_{a},h_{b})}
=waha+wbhb−min(wa,wb)⋅min(ha,hb)min(wa,wb)⋅min(ha,hb)
需要说明的一点是，这里计算IOU时，不用管box的位置，我们假设所有box的左上顶点都在原点，如下图所示：
)
显然，IOU的取值在0到1之间，如果两个box越相似，则它们的IOU值越大。由于在习惯上，我们希望两个box越相似则它们的距离应该越近，所以最终的度量公式为：
d
(
b
o
x
,
a
n
c
h
o
r
)
=
1
−
I
O
U
(
b
o
x
,
a
n
c
h
o
r
)
d(box,anchor)=1-IOU(box,anchor)
d(box,anchor)=1−IOU(box,anchor)
由上式可知，当box与anchor完全重叠，即IOU=1时，它们之间的距离为0。
一个简单的实现
我们都知道yolov3对训练数据使用了k-means聚类的算法来获得anchor boxes大小，但是具体其计算过程是怎样的呢？下面我们来详细的分析其具体计算过程：
第一步：首先我们要知道我们需要聚类的是bounding box，所以我们无需考虑其所属类别，第一步我们需要将所有的bounding box坐标提取出来，也许一张图有一个矩形框，也许有多个，但是我们需要无区别的将所有图片的所有矩形框提取出来，放在一起。
第二步：数据处理获得所有训练数据bounding boxes的宽高数据。给的训练数据往往是其bounding box的4个坐标，但是我们后续需要聚类分析的是bounding box的宽高大小，所以我们需要将坐标数据转换为框的宽高大小，计算方法很简单：长=右下角横坐标-左上角横坐标、宽=右下角纵坐标-左上角纵坐标。
第三步：初始化k个anchor box，通过在所有的bounding boxes中随机选取k个值作为k个anchor boxes的初始值。
第四步：计算每个bounding box与每个anchor box的iou值。传统的聚类方法是使用欧氏距离来衡量差异，也就是说如果我们运用传统的k-means聚类算法，可以直接聚类bounding box的宽和高，产生k个宽、高组合的anchor boxes，但是作者发现此方法在box尺寸比较大的时候，其误差也更大，所以作者引入了iou值，可以避免这个问题。iou值计算方法：这里参考下图和计算代码：
min_w_matrix = np.minimum(cluster_w_matrix, box_w_matrix) #cluster_w_matrix, box_w_matrix分别代表anchor box和bounding box宽大小
min_h_matrix = np.minimum(cluster_h_matrix, box_h_matrix) #cluster_h_matrix, box_h_matrix分别代表anchor box和bounding box高大小
inter_area = np.multiply(min_w_matrix, min_h_matrix) #inter_area表示重叠面积
IOU = inter_area / (box_area + cluster_area - inter_area)#box_area表示bounding box面积 ;cluster_area表示anchor box面积
由于iou值往往越大越好，所以作者定义了一个距离d参数，用来表示其误差：
d=1-IOU
第五步：分类操作。经过前一步的计算可以的到每一个bounding box对于每个anchor box的误差d（n,k），我们通过比较每个bounding box其对于每个anchor box的误差大小{d(i,1)，d(i,2)，…,d(i,k)},选取最小误差的那个anchor box，将这个bounding box分类给它，对于每个bounding box都做这个操作，最后记录下来每个anchor box有哪些bounding box属于它。
第六步：anchor box更新。经过上一步，我们就知道每一个anchor box都有哪些bounding box属于它，然后对于每个anchor box中的那些bounding box，我们再求这些bounding box的宽高中值大小（这里参照github上作者qqwweee那个yolov3项目，也许也有使用平均值进行更新），将其作为该anchor box新的尺寸。
第七步：重复操作第四步到第六步，直到在第五步中发现对于全部bounding box其所属的anchor box类与之前所属的anchor box类完全一样。（这里表示所有bounding box的分类已经不再更新）
第八步：计算anchor boxes精确度。至第七步，其实已经通过k-means算法计算出anchor box。但是细心的同学可能已经发现，k-means.py还给出其精确度大小，其计算方法如下：使用最后得到的anchor boxes与每个bounding box计算其IOU值，对于每个bounding box选取其最高的那个IOU值（代表其属于某一个anchor box类），然后求所有bounding box该IOU值的平均值也即最后的精确度值。
应网友要求附上代码（代码来源）：
import numpy as np
import xml.etree.ElementTree as ET
import glob
import random
def cas_iou(box,cluster):
x = np.minimum(cluster[:,0],box[0])
y = np.minimum(cluster[:,1],box[1])
intersection = x * y
area1 = box[0] * box[1]
area2 = cluster[:,0] * cluster[:,1]
iou = intersection / (area1 + area2 -intersection)
return iou
def avg_iou(box,cluster):
return np.mean([np.max(cas_iou(box[i],cluster)) for i in range(box.shape[0])])
def kmeans(box,k):
# 取出一共有多少框
row = box.shape[0]
# 每个框各个点的位置
distance = np.empty((row,k))
# 最后的聚类位置
last_clu = np.zeros((row,))
np.random.seed()
# 随机选5个当聚类中心
cluster = box[np.random.choice(row,k,replace = False)]
# cluster = random.sample(row, k)
while True:
# 计算每一行距离五个点的iou情况。
for i in range(row):
distance[i] = 1 - cas_iou(box[i],cluster)
# 取出最小点
near = np.argmin(distance,axis=1)
if (last_clu == near).all():
break
# 求每一个类的中位点
for j in range(k):
cluster[j] = np.median(
box[near == j],axis=0)
last_clu = near
return cluster
def load_data(path):
data = []
# 对于每一个xml都寻找box
for xml_file in glob.glob('{}/*xml'.format(path)):
tree = ET.parse(xml_file)
height = int(tree.findtext('./size/height'))
width = int(tree.findtext('./size/width'))
# 对于每一个目标都获得它的宽高
for obj in tree.iter('object'):
xmin = int(float(obj.findtext('bndbox/xmin'))) / width
ymin = int(float(obj.findtext('bndbox/ymin'))) / height
xmax = int(float(obj.findtext('bndbox/xmax'))) / width
ymax = int(float(obj.findtext('bndbox/ymax'))) / height
xmin = np.float64(xmin)
ymin = np.float64(ymin)
xmax = np.float64(xmax)
ymax = np.float64(ymax)
# 得到宽高
data.append([xmax-xmin,ymax-ymin])
return np.array(data)
if __name__ == '__main__':
# 运行该程序会计算'./VOCdevkit/VOC2007/Annotations'的xml
# 会生成yolo_anchors.txt
SIZE = 416
anchors_num = 6
# 载入数据集，可以使用VOC的xml
path = r'./VOCdevkit/VOC2007/Annotations'
# 载入所有的xml
# 存储格式为转化为比例后的width,height
data = load_data(path)
# 使用k聚类算法
out = kmeans(data,anchors_num)
out = out[np.argsort(out[:,0])]
print('acc:{:.2f}%'.format(avg_iou(data,out) * 100))
print(out*SIZE)
data = out*SIZE
f = open("yolo_anchors.txt", 'w')
row = np.shape(data)[0]
for i in range(row):
if i == 0:
x_y = "%d,%d" % (data[i][0], data[i][1])
else:
x_y = ", %d,%d" % (data[i][0], data[i][1])
f.write(x_y)
f.close()
详尽k-means聚类anchors
今天补下之前没有细讲的聚类anchors相关知识，所使用的代码参考的是yolov3 spp以及yolov5中生成anchors的方法。
K-means理论简介
k-means是非常经典且有效的聚类方法，通过计算样本之间的距离（相似程度）将较近的样本聚为同一类别（簇）。使用k-means时主要关注两个问题（个人认为）：1.如何表示样本与样本之间的距离（核心问题），这个一般需要根据具体场景去设计，不同的方法聚类效果也不同，最常见的就是欧式距离。2.分为几类，这个也是需要根据应用场景取选择的，也是一个超参数。
k-means算法主要流程如下：
1 手动设定簇的个数k，假设k=2。2 在所有样本中随机选取k个样本作为簇的初始中心，如下图（random clusters）中两个黄色的小星星代表随机初始化的两个簇中心。3 计算每个样本离每个簇中心的距离（这里以欧式距离为例），然后将样本划分到离它最近的簇中。如下图（step 0）用不同的颜色区分不同的簇。4 更新簇的中心，计算每个簇中所有样本的均值（方法不唯一）作为新的簇中心。如下图（step 1）所示，两个黄色的小星星已经移动到对应簇的中心。5 重复第3步到第4步直到簇中心不在变化或者簇中心变化很小满足给定终止条件。如下图（step2）所示，最终聚类结果。
生成以上聚类过程图片的代码： plot_kmeans.py
K-means在anchors中的应用
在之前讲faster rcnn理论时，使用的anchors都是作者通过经验手工设计的， 但为什么这么设计作者并未提及。那这里为什么要聚类anchors？yolov2论文中有这么一段话The network can learn to adjust the boxes appropriately but if we pick better priors for the network to start with we can make it easier for the network to learn to predict good detections.简单的说如果我们一开始就选择了合适的anchors，那么网络就更容易去学习得到好的检测器。那什么才算好的anchors呢？作者通过计算Avg IOU即所有目标bboxes与anchors最大IOU的均值作为指标，Avg IOU越大代表得到的anchors越好。 上面已经简单介绍了k-means算法的过程，下面在说下yolov2中是怎么利用k-means算法进行聚类得到anchors的。这里主要关注的是如何定义样本之间的距离。论文中有这么一句话，If we use standard k-means with Euclidean distance larger boxes generate more error than smaller boxes.简单的说就是直接使用欧式距离来计算效果不是很好。那么用什么表示距离呢，论文中使用1-IOU(bboxes, anchors)表示距离，如果bbox与对应的簇中心（anchor）IOU越大，则距离越近（1-IOU(bboxes, anchors)越小）。如下图所示采用Cluster SSE(Sum of Square Error) 误差平方和（欧式距离）和采用Cluster IOU相比，Cluster IOU对应的Avg IOU更大，当然你想使用Cluster SSE也是可以的。并且在anchors个数相同的情况下Cluster IOU得到的Avg IOU比Faster RCNN中手工设计（Anchor Boxes）的Avg IOU更高。
下面是我参考几个开源项目自己改的代码。使用k-means算法，1-IOU(bboxes, anchors)作为样本之间的距离进行聚类。代码很简单，简要介绍下：
1 在所有的bboxes中随机挑选k个作为簇的中心。2 计算每个bboxes离每个簇的距离1-IOU(bboxes, anchors)3 计算每个bboxes距离最近的簇中心，并分配到离它最近的簇中4 根据每个簇中的bboxes重新计算簇中心，这里默认使用的是计算中值，自己也可以改成其他方法5 重复3到4直到每个簇中元素不在发生变化
yolo_kmeans.py
import numpy as np
def wh_iou(wh1, wh2):
# Returns the nxm IoU matrix. wh1 is nx2, wh2 is mx2
wh1 = wh1[:, None] # [N,1,2]
wh2 = wh2[None] # [1,M,2]
inter = np.minimum(wh1, wh2).prod(2) # [N,M]
return inter / (wh1.prod(2) + wh2.prod(2) - inter) # iou = inter / (area1 + area2 - inter)
def k_means(boxes, k, dist=np.median):
"""
yolo k-means methods
refer: https://github.com/qqwweee/keras-yolo3/blob/master/kmeans.py
Args:
boxes: 需要聚类的bboxes
k: 簇数(聚成几类)
dist: 更新簇坐标的方法(默认使用中位数，比均值效果略好)
"""
box_number = boxes.shape[0]
last_nearest = np.zeros((box_number,))
# 在所有的bboxes中随机挑选k个作为簇的中心。
clusters = boxes[np.random.choice(box_number, k, replace=False)]
while True:
# 计算每个bboxes离每个簇的距离 1-IOU(bboxes, anchors)
distances = 1 - wh_iou(boxes, clusters)
# 计算每个bboxes距离最近的簇中心
current_nearest = np.argmin(distances, axis=1)
# 每个簇中元素不在发生变化说明以及聚类完毕
if (last_nearest == current_nearest).all():
break # clusters won't change
for cluster in range(k):
# 根据每个簇中的bboxes重新计算簇中心
clusters[cluster] = dist(boxes[current_nearest == cluster], axis=0)
last_nearest = current_nearest
return clusters
代码链接： https://github.com/WZMIAOMIAO/deep-learning-for-image-processing/blob/master/others_project/kmeans_anchors/yolo_kmeans.py
yolov5中聚类anchors代码讲解
如果你是直接使用yolov5的训练脚本，那么它会自动去计算下默认的anchors与你数据集中所有目标的best possible recall，如果小于0.98就会根据你自己数据集的目标去重新聚类生成anchors，反之使用默认的anchors。
下面代码是我根据yolov5中聚类anchors的代码简单修改得到的。基本流程不变，主要改动了三点：1.对代码做了些简化。2.把使用pytorch的地方都改成了numpy（感觉这样会更通用点，但numpy效率确实没有pytorch高）。3.作者默认使用的k-means方法是scipy包提供的，使用的是欧式距离。我自己改成了基于1-IOU(bboxes, anchors)距离的方法。当然我只是注释掉了作者原来的方法，如果想用自己把注释取消掉就行了。但在我使用测试过程中，还是基于1-IOU(bboxes, anchors)距离的方法会略好点。
完整代码链接： https://github.com/WZMIAOMIAO/deep-learning-for-image-processing/tree/master/others_project/kmeans_anchors
其实在yolov5生成anchors中不仅仅使用了k-means聚类，还使用了Genetic Algorithm遗传算法，在k-means聚类的结果上进行mutation变异。接下来简单介绍下代码流程：
读取训练集中每张图片的wh以及所有bboxes的wh（这里是我自己写的脚本读取的PASCAL VOC数据）将每张图片中wh的最大值等比例缩放到指定大小img_size，由于读取的bboxes是相对坐标所以不需要改动将bboxes从相对坐标改成绝对坐标（乘以缩放后的wh）筛选bboxes，保留wh都大于等于两个像素的bboxes使用k-means聚类得到n个anchors使用遗传算法随机对anchors的wh进行变异，如果变异后效果变得更好（使用anchor_fitness方法计算得到的fitness（适应度）进行评估）就将变异后的结果赋值给anchors，如果变异后效果变差就跳过，默认变异1000次。将最终变异得到的anchors按照面积进行排序并返回
main.py
import random
import numpy as np
from tqdm import tqdm
from scipy.cluster.vq import kmeans
from read_voc import VOCDataSet
from yolo_kmeans import k_means, wh_iou
def anchor_fitness(k: np.ndarray, wh: np.ndarray, thr: float): # mutation fitness
r = wh[:, None] / k[None]
x = np.minimum(r, 1. / r).min(2) # ratio metric
# x = wh_iou(wh, k) # iou metric
best = x.max(1)
f = (best * (best > thr).astype(np.float32)).mean() # fitness
bpr = (best > thr).astype(np.float32).mean() # best possible recall
return f, bpr
def main(img_size=512, n=9, thr=0.25, gen=1000):
# 从数据集中读取所有图片的wh以及对应bboxes的wh
dataset = VOCDataSet(voc_root="/data", year="2012", txt_name="train.txt")
im_wh, boxes_wh = dataset.get_info()
# 最大边缩放到img_size
im_wh = np.array(im_wh, dtype=np.float32)
shapes = img_size * im_wh / im_wh.max(1, keepdims=True)
wh0 = np.concatenate([l * s for s, l in zip(shapes, boxes_wh)]) # wh
# Filter 过滤掉小目标
i = (wh0 < 3.0).any(1).sum()
if i:
print(f'WARNING: Extremely small objects found. {i} of {len(wh0)} labels are < 3 pixels in size.')
wh = wh0[(wh0 >= 2.0).any(1)] # 只保留wh都大于等于2个像素的box
# Kmeans calculation
# print(f'Running kmeans for {n} anchors on {len(wh)} points...')
# s = wh.std(0) # sigmas for whitening
# k, dist = kmeans(wh / s, n, iter=30) # points, mean distance
# assert len(k) == n, print(f'ERROR: scipy.cluster.vq.kmeans requested {n} points but returned only {len(k)}')
# k *= s
k = k_means(wh, n)
# 按面积排序
k = k[np.argsort(k.prod(1))] # sort small to large
f, bpr = anchor_fitness(k, wh, thr)
print("kmeans: " + " ".join([f"[{int(i[0])}, {int(i[1])}]" for i in k]))
print(f"fitness: {f:.5f}, best possible recall: {bpr:.5f}")
# Evolve
# 遗传算法(在kmeans的结果基础上变异mutation)
npr = np.random
f, sh, mp, s = anchor_fitness(k, wh, thr)[0], k.shape, 0.9, 0.1 # fitness, generations, mutation prob, sigma
pbar = tqdm(range(gen), desc=f'Evolving anchors with Genetic Algorithm:') # progress bar
for _ in pbar:
v = np.ones(sh)
while (v == 1).all(): # mutate until a change occurs (prevent duplicates)
v = ((npr.random(sh) < mp) * random.random() * npr.randn(*sh) * s + 1).clip(0.3, 3.0)
kg = (k.copy() * v).clip(min=2.0)
fg, bpr = anchor_fitness(kg, wh, thr)
if fg > f:
f, k = fg, kg.copy()
pbar.desc = f'Evolving anchors with Genetic Algorithm: fitness = {f:.4f}'
# 按面积排序
k = k[np.argsort(k.prod(1))] # sort small to large
print("genetic: " + " ".join([f"[{int(i[0])}, {int(i[1])}]" for i in k]))
print(f"fitness: {f:.5f}, best possible recall: {bpr:.5f}")
if __name__ == "__main__":
main()
运行结果如下，注意由于随机性每次结果都会有些差异，如果要能够复现，需要固定numpy以及random包的随机数种子。
read data info.: 100%|██████████| 5717/5717 [00:00<00:00, 6549.98it/s]
kmeans: [12, 18] [27, 31] [33, 69] [75, 48] [65, 118] [125, 137] [164, 268] [299, 166] [382, 337]
fitness: 0.73256, best possible recall: 0.99956
Evolving anchors with Genetic Algorithm: fitness = 0.7358: 100%|██████████| 1000/1000 [00:05<00:00, 182.22it/s]
genetic: [13, 23] [34, 31] [30, 75] [79, 66] [69, 143] [142, 134] [169, 270] [331, 177] [391, 338]
fitness: 0.73582, best possible recall: 0.99930
聚类anchors需要注意的坑
有时使用自己聚类得到的anchors的效果反而变差了，此时你可以从以下几方面进行检查：
注意输入网络时训练的图片尺寸。这是个很重要的点，因为一般训练/验证时输入网络的图片尺寸是固定的，比如说640x640，那么图片在输入网络前一般会将最大边长缩放到640，同时图片中的bboxes也会进行缩放。所以在聚类anchors时需要使用相同的方式提前去缩放bboxes，否则聚类出来的anchors并不匹配。比如你的图片都是1280x1280大小的，假设bboxes都是100x100大小的，如果不去缩放bboxes，那么聚类得到的anchors差不多是在100x100附近。而实际训练网络时bboxes都已经缩放到50x50大小了，此时理想的anchors应该是50x50左右而不是100x100了。如果使用预训练权重，不要冻结太多的权重。现在训练自己数据集时一般都是使用别人在coco等大型数据上预训练好的权重。而这些权重是基于coco等数据集上聚类得到的结果，并不是针对自己数据集聚类得到的。所以网络为了要适应新的anchors需要调整很多权重，如果你冻结了很多层（假设只去微调最后的预测器，其他权重全部冻结），那么得到的结果很大几率还没有之前的anchors好。当可训练的权重越来越多，一般使用自己数据集聚类得到的anchors会更好一点（前提是自己聚类的anchors是合理的）。
更多Kmeans和Kmeans++算法精讲
目录
前言
一、聚类
1.1 概念
1.2 一般过程
1.3 分类
二、Kmeans算法
2.1原理
2.2算法步骤
2.3k值确定
2.3.1先验法
2.3.2手肘法
2.4代码实现
2.5优缺点
三、Kmeans++算法
3.1原理
3.2算法步骤
3.3代码实现
3.4优缺点
一、聚类
1.1 概念
聚类(Clustering) 是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也就是说，聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。
聚类和分类
**聚类(Clustering)：**是指把相似的数据划分到一起，具体划分的时候并不关心这一类的标签，目标就是把相似的数据聚合到一起，聚类是一种无监督学习(Unsupervised Learning)方法。**分类(Classification)：**是把不同的数据划分开，其过程是通过训练数据集获得一个分类器，再通过分类器去预测未知数据，分类是一种监督学习(Supervised Learning)方法。
1.2 一般过程
**①数据准备：**包括特征标准化和降维；**②特征选择：**从最初的特征中选择最有效的特征,并将其存储于向量中；**③特征提取：**通过对所选择的特征进行转换形成新的突出特征；**④聚类(或分组)：**首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量，而后执行聚类或分组；**⑤聚类结果评估：**是指对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。
1.3 分类
二、Kmeans算法
2.1原理
Kmeans 算法是一种常用的聚类算法，它是基于划分方法聚类的。它的原理是将数据划分为k个簇，每个簇由距离中心最近的数据点组成，基于计算样本与中心点的距离归纳各簇类下的所属样本，迭代实现样本与其归属的簇类中心的距离为最小的目标。
简单来说，Kmeans 算法就是通过不断地调整簇的中心点，并将数据点指派到距离它最近的中心点所在的簇，来逐步将数据划分成若干个簇。
常见目标函数：
2.2算法步骤
算法执行步骤如下：
选取K个点做为初始聚集的簇心（也可选择非样本点）;分别计算每个样本点到 K个簇核心的距离（这里的距离一般取欧氏距离或余弦距离），找到离该点最近的簇核心，将它归属到对应的簇；所有点都归属到簇之后， M个点就分为了 K个簇。之后重新计算每个簇的重心（平均距离中心），将其定为新的“簇核心”；反复迭代 2 - 3 步骤，直到达到某个中止条件。
【注意】常用的中止条件有迭代次数、最小平方误差MSE、簇中心点变化率
2.3k值确定
Kmeans划分k个簇，不同k值的情况对最终结果的影响至关重要，不同的k值会带来不同的结果，如下图所示：
一般情况下，我们确定k值常用两种方法：先验法、手肘法
2.3.1先验法
先验法比较简单，就是凭借着业务知识确定k的取值。比如对于iris花数据集，我们大概知道有三种类别，可以按照k=3做聚类验证。从下图可看出，对比聚类预测与实际的iris种类是比较一致的。
2.3.2手肘法
可以知道k值越大，划分的簇群越多，对应的各个点到簇中心的距离的平方的和（类内距离，WSS）越低，我们通过确定WSS随着K的增加而减少的曲线拐点，作为K的取值。
2.4代码实现
Kmeans具体代码如下：
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
def assignment(df, center, colmap):
# 计算所有样本分别对K个类别中心点的距离
for i in center.keys():
df["distance_from_{}".format(i)] = np.sqrt((df["x"] - center[i][0]) ** 2 + (df["y"] - center[i][1]) ** 2)
distance_from_centroid_id = ['distance_from_{}'.format(i) for i in center.keys()]
df["closest"] = df.loc[:, distance_from_centroid_id].idxmin(axis=1) # "closest"列表示每个样本点离哪个类别的中心点距离最近
print(df["closest"])
df["closest"] = df["closest"].map(lambda x: int(x.lstrip('distance_from_')))
df["color"] = df['closest'].map(lambda x: colmap[x])
return df
def update(df, centroids):
# 更新K个类别的中心点
for i in centroids.keys():
# 每个类别的中心点为 属于该类别的点的x、y坐标的平均值
centroids[i][0] = np.mean(df[df['closest'] == i]['x'])
centroids[i][1] = np.mean(df[df['closest'] == i]['y'])
return centroids
def main():
df = pd.DataFrame({
'x': [12, 20, 28, 18, 10, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72, 23],
'y': [39, 36, 30, 52, 54, 20, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24, 77]
})
k = 3
# 一开始随机指定 K个类的中心点
center = {
i: [np.random.randint(0, 80), np.random.randint(0, 80)]
for i in range(k)
}
colmap = {0: "r", 1: "g", 2: "b"}
df = assignment(df, center, colmap)
for i in range(10): # 迭代10次
closest_center = df['closest'].copy(deep=True)
center = update(df, center) # 更新K个类的中心点
df = assignment(df, center, colmap) # 类别中心点更新后，重新计算所有样本点到K个类别中心点的距离
if closest_center.equals(df['closest']): # 若各个样本点对应的聚类类别不再变化，则结束聚类
break
plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='b')
for j in center.keys():
plt.scatter(*center[j], color=colmap[j], linewidths=6)
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()
if __name__ == '__main__':
main()
实现效果：
2.5优缺点
优点：
理解容易，聚类效果不错处理大数据集的时候，该算法可以保证较好的伸缩性和高效率当簇近似高斯分布的时候，效果非常不错
缺点：
K值是用户给定的，在进行数据处理前，K值是未知的，给定合适的 k 值，需要先验知识，凭空估计很困难，或者可能导致效果很差对初始簇中心点是敏感的不适合发现非凸形状的簇或者大小差别较大的簇特殊值(离群值或称为异常值)对模型的影响比较大
三、Kmeans++算法
3.1原理
原始Kmeans算法最开始随机选取数据集中k个点作为聚类中心，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。**Kmeans++算法主要对对K-Means初始值选取的方法的优化。**也就是说，Kmeans++算法与Kmeans算法最本质的区别是在k个聚类中心的初始化过程。
3.2算法步骤
其实通过上面的介绍，我们知道了 Kmeans++算法和Kmeans算法就是选择一开始的k个聚类中心点的方法有差别而已。其初始点的选择过程如下：
从数据点中随机选择一个中心。对于每个数据点x，计算D(x)，即x与已经选择的最接近中心之间的距离。使用加权概率分布随机选择一个新的数据点作为新的中心，其中选择点 x 的概率与D(x)^2成正比。重复步骤2和3，直到选择了K个中心。
其余训练过程与KMeans一致。
3.3代码实现
Kmeans++具体代码如下：
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import random
def select_center(first_center, df, k, colmap):
center = {}
center[0] = first_center
for i in range(1, k):
df = assignment(df, center, colmap)
sum_closest_d = df.loc[:, 'cd'].sum() # cd = 最近中心点的距离。把所有样本点对应最近中心点的距离都加在一起
df["p"] = df.loc[:, 'cd'] / sum_closest_d
sum_p = df["p"].cumsum()
# 下面是轮盘法取新的聚类中心点
next_center = random.random()
for index, j in enumerate(sum_p):
if j > next_center:
break
center[i] = list(df.iloc[index].values)[0:2]
return center
def assignment(df, center, colmap):
# 计算所有样本分别对K个类别中心点的距离
for i in center.keys():
df["distance_from_{}".format(i)] = np.sqrt((df["x"] - center[i][0]) ** 2 + (df["y"] - center[i][1]) ** 2)
distance_from_centroid_id = ['distance_from_{}'.format(i) for i in center.keys()]
df["closest"] = df.loc[:, distance_from_centroid_id].idxmin(axis=1) # "closest"列表示每个样本点离哪个类别的中心点距离最近
df["cd"] = df.loc[:, distance_from_centroid_id].min(axis=1)
df["closest"] = df["closest"].map(lambda x: int(x.lstrip('distance_from_')))
df["color"] = df['closest'].map(lambda x: colmap[x])
return df
def update(df, centroids):
# 更新K个类别的中心点
for i in centroids.keys():
# 每个类别的中心点为 属于该类别的点的x、y坐标的平均值
centroids[i][0] = np.mean(df[df['closest'] == i]['x'])
centroids[i][1] = np.mean(df[df['closest'] == i]['y'])
return centroids
def main():
df = pd.DataFrame({
'x': [12, 20, 28, 18, 10, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72, 23],
'y': [39, 36, 30, 52, 54, 20, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24, 77]
})
k = 3
colomap = {0: "r", 1: "g", 2: "b"}
first_center_index = random.randint(0, len(df) - 1)
first_center = [df['x'][first_center_index], df['y'][first_center_index]]
center = select_center(first_center, df, k, colomap)
df = assignment(df, center, colomap)
for i in range(10): # 迭代10次
closest_center = df['closest'].copy(deep=True)
center = update(df, center) # 更新K个类的中心点
df = assignment(df, center, colomap) # 类别中心点更新后，重新计算所有样本点到K个类别中心点的距离
if closest_center.equals(df['closest']): # 若各个样本点对应的聚类类别不再变化，则结束聚类
break
plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='b')
for j in center.keys():
plt.scatter(*center[j], color=colomap[j], linewidths=6)
plt.xlim(0, 80)
plt.ylim(0, 80)
plt.show()
if __name__ == '__main__':
main()
实现效果：
3.4优缺点
优点：
避免了Kmeans随机选取k个聚类中心导致可能聚类中心选择的不好，最终对结果会产生很大的影响的问题在目标检测应用中，Kmeans++通过改变初始聚类中心的生成方式，增大初始锚框之间差距，使锚框更适应整体据分布，得到了匹配度更好的多尺度锚框，进而提升了模型的检测性能。
缺点：
由于聚类中心点选择过程中的内在有序性，在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)。
相关链接
您阅读本篇文章共花了：
发表评论