目录
参考资料：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}D B I =N 1 i =1 ∑N j =i max ∥w i −w j ∥2 S i +S j
式中：D B I DBI D B I 表示 DBI 指标值；S i ‾ \overline{S_i}S i 为第 i i i 类样本到其类中心的平均欧氏距离； ∥ w i − w j ∥ 2 \left\| w_i-w_j\right\|_2 ∥w i −w j ∥2 为第 i i i 和第 j j j 类的类中心欧氏距离。
2.具体计算步骤
- 1）计算S i S_i S i
- DBI 计算公式中首先定义了S i S_i S i 变量，S i S_i S i 计算的是类内数据到簇质心的平均距离，代表了簇类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}S i =(T i 1 j =1 ∑T i ∣X j −A i ∣p )1/p
其中X j X_j X j 代表簇类i i i 中第j j j 个数据点，也就是一个时间序列，A i A_i A i 是簇类i i i 的质心，T i T_i T i 是簇类i i i 中数据的个数。 - p p p 取 1 表示：各点到中心的距离的均值，p p p 取 2 时表示：各点到中心距离的标准差，它们都可以用来衡量分散程度。
- p p p 在通常情况下取 2，这样就可以计算独立的数据点和质心的欧式距离（euclidean metric），当然在考察流型和高维数据的时候，欧氏距离也许不是最佳的距离计算方式，但也是比较典型的了。
- 2）计算M i j M_{ij}M ij
分子之和计算完后，需计算分母 M i j M_{ij}M ij ，DBI 定义了一个距离值 M i j M_{ij}M ij ：表示第 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}M ij =∥A i −A j ∥p =(k =1 ∑N ∣a ki −a kj ∣p )1/p
a k i a_{ki}a ki 表示第 i i i 类的质心点的第 K K K 个值，M i j M_{ij}M ij 则就是第 i i i 类与第 j j j 类质心的距离（两个点的距离）。 - 3）计算R i j R_{ij}R ij
计算了分子与分母后，DBI 定义了一个衡量相似度的值 R i j R_{ij}R ij ，计算公式为：
R i j = S i + S j M i j R_{ij}=\frac{S_i+S_j}{M_{ij}}R ij =M ij S i +S j
衡量第 i i i 类与第 j j j 类的相似度。 - 4）计算DBI
有了以上公式的基础，我们做一个基于簇类数 n n n 的 n 2 n^2 n 2 的嵌套循环，对每一个簇类 i i i 计算最大值的R i j R_{ij}R ij ，记为D i D_i D i ，即：
D i = max j ≠ i R i , j D_i=\displaystyle \max_{j\neq i}R_{i,j}D i =j =i max R i ,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 D B I =D =N 1 i =1 ∑N D i
分类个数的不同可以导致不同的值，DBI 值越小，分类效果越好（说明分散程度越低）。
图例：
左图表示不同簇类数目下数据点的分类情况， 右图表示在不同的簇类数目下(q=1)，DBI 值的变化。
总的来说，这个 DBI 就是计算类内距离之和与类间距离之比，来优化 k 值的选择，避免 K-means 算法中由于只计算目标函数Wn而导致局部最优的情况。
; 3.Python实现
- Python 3 实现如下：
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]:
s += cls.vector_distance(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])
r_ij = (cls.compute_si(i, x, clusters[i], nc) + cls.compute_si(j, x, clusters[j], nc)) / m_ij
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
Original: https://blog.csdn.net/weixin_46713695/article/details/126303649
Author: 赵孝正
Title: 聚类算法评价指标之DBI指数及Python实现
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/617382/
转载文章受原作者版权保护。转载请注明原作者出处！