1. AGNES

AGNES是一种采用自底向上合并策略的聚类算法，其

思想

为：

初始将所有样本看成一个簇，然后在每一轮过程中将距离最近的两个簇合并为一个簇，簇的个数不断减少到人为指定的聚类簇数K，终止算法

。该算法关键在于如何度量两个簇的距离，集合间的距离计算有如下方式：

小

距

离

：

(

)

[

∈

]

∣

−

∣

最

大

距

离

：

(

)

[

∈

]

∣

−

∣

平

均

距

离

：

(

)

∣

∑

∈

∑

∈

∣

−

∣

\begin{aligned} 最小距离：dist(C_i,C_j) &= min_{[x\in C_i,z\in C_j]}||x-z||_2 \\ 最大距离：dist(C_i,C_j) &= max_{[x\in C_i,z\in C_j]}||x-z||_2 \\ 平均距离：dist(C_i,C_j)&=\cfrac{1}{|C_i||C_j|}\sum_{x\in C_i}\sum_{z\in C_j}||x-z||_2 \end{aligned}

$最小距离： d i s t (C_{i}, C_{j}) 最大距离： d i s t (C_{i}, C_{j}) 平均距离： d i s t (C_{i}, C_{j}) = m i n_{[x \in C_{i}, z \in C_{j}]} ∣ ∣ x - z ∣ ∣_{2} = m a x_{[x \in C_{i}, z \in C_{j}]} ∣ ∣ x - z ∣ ∣_{2} = \frac{1}{∣ C _{i} ∣ ∣ C _{j} ∣} x \in C_{i} \sum z \in C_{j} \sum ∣ ∣ x - z ∣ ∣_{2}$

采用最小距离的AGNES称为

“单连接算法”

，单连接趋向于发现有局部邻近性的簇。采用最大距离的AGNES称为

“全连接算法”

，全连接趋向于发现有全局邻近性的簇。但是，单

连接和全连接对离群点敏感

，因为离群点始终为单个簇无法参与合并。采用平均距离的AGNES称为

“均连接算法”

，它可以克服离群点问题。

AGNES算法流程如下

：

输入:

数据集D和聚类簇数k
初始化m个簇为m个样本
for i =1,2,…,m do
$\enspace\enspace$
for j = 1,2,…,m do
$\enspace\enspace\enspace\enspace$
$D_{ij} = dist(C_i,C_j) D i j = d i s t ( C i , C j )$
$\enspace\enspace\enspace\enspace$
$D_{ji} = D_{ij} D j i = D i j $
$\enspace\enspace$
end for
end for
设置当前簇个数：q = m
while q > k do
$\enspace\enspace$
从距离矩阵D中找到最近的两个簇
$C_i C i 和 C j C_j C j $
$\enspace\enspace$
合并
$C_i = C_i \cup C_j C i = C i ∪ C j $
$\enspace\enspace$
删除
$C_j C j 并对簇重新编号$
$\enspace\enspace$
删除距离矩阵D的第i行和第j列
$\enspace\enspace$
for j=1,2,3…,q -1 do
$\enspace\enspace\enspace\enspace$
计算新的
$D_{ij} = dist(C_i,C_j) D i j = d i s t ( C i , C j )$
$\enspace\enspace\enspace\enspace$
计算新的
$D_{ji} = D_{ij} D j i = D i j $
$\enspace\enspace$
end for
$\enspace\enspace$
簇个数减少 q = q -1
end while
输出:

$\{C_1,C_2,…,C_k\} { C 1 , C 2 , . . . , C k }$

pyhon实现如下：

#集合间的平均距离
def dist(X,Z):
    n1 = X.shape[0]
    n2 = Z.shape[0]
    total = 0.0
    for x in X:
        for z in Z:
            total +=math.sqrt((x-z) @ (x-z).T)
    return  total / (n1 * n2)
            
#从距离矩阵中找出最小值对应的下标
def minInD(D):
    m = D.shape[0]
    i_index = 0
    j_index = 0
    min_val = float('inf')
    for i in range(0,m):
        for j in range(0,m):
            if i == j:continue
            if D[i,j] <min_val:
                min_val = D[i,j]
                i_index = i
                j_index = j
    return [i_index,j_index]
def agnes(data,k):
    m,n = data.shape
    #初始化m个簇
    cls = []
    for i in range(0,m):
        cls.append(np.array([data[i]]))
    #初始化距离矩阵D
    D = np.zeros((m,m))
    for i in range(0,m):
        for j in range(0,m):
            D[i,j] = dist(cls[i],cls[j])
            D[j,i] = D[i,j]
    q = m#当前簇的个数
    while q > k:
        #找到距离最近的两个簇
        l,r =minInD(D)
        #合并两个簇
        cls[l] = np.concatenate((cls[l],cls[r]),axis=0)
        #删除原来的簇
        cls = np.delete(cls,r,axis = 0)
        #删除r行，r列
        D = np.delete(D,r,axis = 0)
        D = np.delete(D,r,axis = 1)
        #更新距离矩阵D
        for j in range(0,q-1):
            D[l,j] = dist(cls[l],cls[j])
            D[j,l] = D[l,j]
        q = q - 1
    return cls

2. DIANA

DIANA是一种采用自顶向下分裂策略的聚类算法。它的

思想是

：初始将整个样本视为一个簇，然后进行分裂，再找到直径最大的簇，再进行分裂；分裂的方式是先找到簇中平均相异度最大的样本作为新簇的起始点，然后在旧簇中不断寻找：到新簇的平均距离小于到旧簇的平均距离的样本划分给新簇。直到分裂的簇个数达到人为指定的k值，算法终止。有一些概念：

平均相异度（平均距离）：点与一个集合所有样本的距离之和再除以样本个数。
簇的直径：簇中任意两点距离的最大值。

DIANA算法流程如下：

输入：

数据集D和聚类簇数k
初始化所有样本为单个簇
当前簇数 q = 1
while q < k do
$\enspace\enspace$
找出直径最大的簇C
$\enspace\enspace$
找出C中平均相异度最大的样本X
$\enspace\enspace$
初始化新簇cls_new = {X}
$\enspace\enspace$
初始化旧簇cls_old = C – X
$\enspace\enspace$
REPEAT
$\enspace\enspace\enspace\enspace$
for i=1,2,…,len(cls_old) do
$\enspace\enspace\enspace\enspace\enspace\enspace$
计算样本cls_old[i]与cls_new的平均距离L
$\enspace\enspace\enspace\enspace\enspace\enspace$
计算样本cls_old[i]与cls_old -cls_old[i]的平均距离R
$\enspace\enspace\enspace\enspace\enspace\enspace$
if L < R then
$\enspace\enspace\enspace\enspace\enspace\enspace\enspace$
将样本添加到新集合中cls_new = cls_new
$\cap ∩ cls_old[i]$
$\enspace\enspace\enspace\enspace\enspace\enspace\enspace$
变更cls_old =cls_old – cls_old[i]
$\enspace\enspace\enspace\enspace\enspace\enspace\enspace$
发生更新就退出 break for
$\enspace\enspace\enspace\enspace\enspace\enspace$
end if
$\enspace\enspace\enspace\enspace$
end for
$\enspace\enspace$
UNTIL cls_old和cls_new不再变化
$\enspace\enspace$
一分为二：删除C，添加cls_old和cls_new
$\enspace\enspace$
q = q +1
end while
输出：

所有簇

python 实现如下：

#寻找直径最大的簇
def diameterMax(cls):
    #计算簇的直径
    def diameter(each):
        max_d = 0
        for x in each:
            for y in each:
                if (x == y).all() :continue
                d = math.sqrt((x-y)@(x-y).T)
                if d > max_d:
                    max_d = d
        return max_d
    index = -1
    maxs = 0
    for i in range(0,len(cls)):
        dia = diameter(cls[i])
        if dia > maxs:
            maxs = dia
            index = i

    return [cls[index],index]

#计算某个样本与集合的平均相异度
def distinct(x,C):
    totals = 0.0
    for c in C:
        totals +=  math.sqrt((x-c) @ (x-c).T)
    return totals / C.shape[0]

def diana(data,k):
    m,n = data.shape
    #初始化所有样本为一个簇
    cls = [data]
    #记录当前簇的个数
    q = 1
    #分裂到指定簇数结束
    while q < k:
        #找到直径最大的簇及其位置
        C,index =  diameterMax(cls)
        #找到平均相异度最大的点作为新的簇一个样本
        max_val = 0
        j = -1
        for i in range(0,C.shape[0]):
            diff = distinct(C[i],np.delete(C,i,axis=0))
            if max_val < diff:
                j = i
                max_val  = diff
       #初始化分裂后的两个集合
        cls_new = C[j].reshape((1,n))
        cls_old = np.delete(C,j,axis = 0)
        #new和old集合不再变动结束
        while True:
            count  = 0 #标记集合是否更新过 
            for i in range(0,cls_old.shape[0]):
                l =  distinct(cls_old[i],cls_new)
                r =  distinct(cls_old[i],np.delete(cls_old,i,axis=0))
                #若old集合的样本到new的最短距离比到自身的最短距离还要小
                if l < r:
                    count += 1
                    #更新old和new
                    cls_new = np.concatenate((cls_new,[cls_old[i]]),axis=0)
                    cls_old = np.delete(cls_old,i,axis=0)
                    break
                    
            if count == 0:break
        #一分为二
        cls.pop(index)
        cls.append(cls_new)
        cls.append(cls_old)
        q += 1
    return cls

原文链接：https://blog.csdn.net/ZHT2016iot/article/details/119214043

1. AGNES

2. DIANA

你可能也喜欢