目录
1.概念介绍2.具体计算步骤3.Python实现
参考资料：https://blog.csdn.net/weixin_46713695/article/details/126385691?spm=1001.2014.3001.5502
1.概念介绍
最近在做一个序列聚类的项目，评价聚类优劣的时候，用到了 DBI 指数，根据自己的理解，梳理了网上看到的资料，以求步骤清晰公式易懂，给大家带来方便。
戴维森堡丁指数（Davies-Bouldin index，DBI） ，又称为分类适确性指标，是由 大卫L·戴维斯 和 唐纳德·Bouldin 提出的一种评估聚类算法优劣的指标。
综合考虑了类内样本相似度以及类间样本差异度 ，其值越小表征聚类有效性越高 ，假设我们有
m
m
m 个序列，将这些序列通过算法聚为
n
n
n 类，使用 DBI 聚类效果评价方法。具体定义如下：
D
B
I
=
1
N
∑
i
=
1
N
max
j
≠
i
S
i
‾
+
S
j
‾
∥
w
i
−
w
j
∥
2
DBI=\frac{1}{N}\sum^N_{i=1}\displaystyle \max_{j\neq i}\frac{\overline{S_i}+\overline{S_j}}{\left\| w_i-w_j\right\|_2}
DBI=N1i=1∑Nj=imax∥wi−wj∥2Si+Sj
式中：
D
B
I
DBI
DBI 表示 DBI 指标值；
S
i
‾
\overline{S_i}
Si 为第
i
i
i 类样本到其类中心的平均欧氏距离；
∥
w
i
−
w
j
∥
2
\left\| w_i-w_j\right\|_2
∥wi−wj∥2为第
i
i
i 和第
j
j
j 类的类中心欧氏距离。
2.具体计算步骤
1）计算
S
i
S_i
Si
DBI 计算公式中首先定义了
S
i
S_i
Si 变量，
S
i
S_i
Si 计算的是类内数据到簇质心的平均距离，代表了簇类
i
i
i 中各时间序列的分散程度，计算公式为：
S
i
=
(
1
T
i
∑
j
=
1
T
i
∣
X
j
−
A
i
∣
p
)
1
/
p
S_i=\left({\frac{1}{T_i}}\sum^{T_i}_{j=1}\left |X_j-A_i\right|^p\right)^{1/p}
Si=(Ti1j=1∑Ti∣Xj−Ai∣p)1/p 其中
X
j
X_j
Xj 代表簇类
i
i
i 中第
j
j
j 个数据点，也就是一个时间序列，
A
i
A_i
Ai 是簇类
i
i
i 的质心，
T
i
T_i
Ti 是簇类
i
i
i 中数据的个数。
p
p
p 取 1 表示：各点到中心的距离的均值，
p
p
p 取 2 时表示：各点到中心距离的标准差，它们都可以用来衡量分散程度。
p
p
p 在通常情况下取 2，这样就可以计算独立的数据点和质心的欧式距离（euclidean metric），当然在考察流型和高维数据的时候，欧氏距离也许不是最佳的距离计算方式，但也是比较典型的了。 2）计算
M
i
j
M_{ij}
Mij 分子之和计算完后，需计算分母
M
i
j
M_{ij}
Mij，DBI 定义了一个距离值
M
i
j
M_{ij}
Mij：表示第
i
i
i 类与第
j
j
j 类的距离，计算公式为：
M
i
j
=
∥
A
i
−
A
j
∥
p
=
(
∑
k
=
1
N
∣
a
k
i
−
a
k
j
∣
p
)
1
/
p
M_{ij}=\left\| A_i-A_j\right\|_p=\left(\sum^{N}_{k=1}\left |a_{ki}-a_{kj}\right|^p\right)^{1/p}
Mij=∥Ai−Aj∥p=(k=1∑N∣aki−akj∣p)1/p
a
k
i
a_{ki}
aki 表示第
i
i
i 类的质心点的第
K
K
K 个值，
M
i
j
M_{ij}
Mij 则就是第
i
i
i 类与第
j
j
j 类质心的距离（两个点的距离）。 3）计算
R
i
j
R_{ij}
Rij 计算了分子与分母后，DBI 定义了一个衡量相似度的值
R
i
j
R_{ij}
Rij，计算公式为：
R
i
j
=
S
i
+
S
j
M
i
j
R_{ij}=\frac{S_i+S_j}{M_{ij}}
Rij=MijSi+Sj 衡量第
i
i
i 类与第
j
j
j 类的相似度。 4）计算DBI 有了以上公式的基础，我们做一个基于簇类数
n
n
n 的
n
2
n^2
n2 的嵌套循环，对每一个簇类
i
i
i 计算最大值的
R
i
j
R_{ij}
Rij，记为
D
i
D_i
Di，即：
D
i
=
max
j
≠
i
R
i
,
j
D_i=\displaystyle \max_{j\neq i}R_{i,j}
Di=j=imaxRi,j 也即簇类
i
i
i 与其他类的最大相似度值，也就是取出最差结果。然后对所有类的最大相似度取均值就得到了 DBI 指数，计算公式为：
D
B
I
=
D
‾
=
1
N
∑
i
=
1
N
D
i
DBI=\overline{D}=\frac{1}{N}\sum^N_{i=1}D_i
DBI=D=N1i=1∑NDi 分类个数的不同可以导致不同的值，DBI 值越小，分类效果越好（说明分散程度越低）。
图例： 左图表示不同簇类数目下数据点的分类情况，右图表示在不同的簇类数目下(q=1)，DBI 值的变化。
总的来说，这个 DBI 就是计算类内距离之和与类间距离之比，来优化 k 值的选择，避免 K-means 算法中由于只计算目标函数Wn而导致局部最优的情况。
3.Python实现
Python 3 实现如下：
# -*- coding: utf-8 -*-
class evalution:
@classmethod
def vector_distance(cls, v1, v2):
"""
this function calculates de euclidean distance between two vectors.
params:
v1: vector v1
v2: vector v2
"""
sum = 0
for i in range(len(v1)):
sum += (v1[i] - v2[i]) ** 2
return sum ** 0.5
@classmethod
def compute_si(cls, i, x, clusters, nc):
"""
Average distance from within-class data to cluster centroids
params:
clusters: 某一聚类中心点，例如 clusters[j]，具体内容取决于 j 的值。
x: 分类结果中，某一类数据集合。
i: label_的索引, 若为 1，则 x[1]表示 label 为 clusters[j] 的数据的集合
nc: nc is number of clusters
"""
norm_c = nc
s = 0
for t in x[i]: # 遍历标签为 i 的数据
s += cls.vector_distance(t, clusters) # 遍历每个点 t 与质心clusters的距离，然后累加
return s / norm_c
@classmethod
def compute_rij(cls, i, j, x, clusters, nc):
"""
先计算 Mij，再计算 Rij
params:
clusters: cluster centroids
i, j: 两个聚类结果的索引
nc: nc is number of clusters
"""
m_ij = cls.vector_distance(clusters[i], clusters[j]) # 计算质心 i 和 j 的距离 Mij (分母)
r_ij = (cls.compute_si(i, x, clusters[i], nc) + cls.compute_si(j, x, clusters[j], nc)) / m_ij # 衡量 i 和 j 的相似度
return r_ij
@classmethod
def compute_di(cls, i, x, clusters, nc):
"""
Calculates the max similarity between cluster i and other clusters
params:
i: 聚类结果中某一label_
x: 聚类结果数据，x[1]表示label为1的数据的集合
clusters: cluster centroids(聚类中心)
nc: nc is number of clusters
return:
max(list_r): max similarity between cluster i and other clusters
"""
list_r = []
for j in range(nc):
if i != j:
temp = cls.compute_rij(i, j, x, clusters, nc)
list_r.append(temp)
return max(list_r)
@classmethod
def compute_db_index(cls, x, clusters, nc):
"""
params:
x:
clusters:
nc: nc is number of clusters
"""
sigma_r = 0.0
for i in range(nc):
sigma_r = sigma_r + cls.compute_di(i, x, clusters, nc)
db_index = float(sigma_r) / float(nc)
return db_index
if __name__ == '__main__':
db_index = evalution.compute_db_index(x, clusters, nc)
参考资料 [1] Davies-Bouldin指数（DBI） 2020.11 [2] Python实现DBI(davies_bouldin_score)评价指标 2020.3 [3] 聚类算法评价指标——Davies-Bouldin指数(Dbi) 2018.5 [4] 聚类算法内部度量-si,ch,dbi 2022.2
精彩内容
您阅读本篇文章共花了：
发表评论