层次聚类AGNES与DIANA

1. AGNES

AGNES是一种采用自底向上合并策略的聚类算法，其思想为：初始将所有样本看成一个簇，然后在每一轮过程中将距离最近的两个簇合并为一个簇，簇的个数不断减少到人为指定的聚类簇数K，终止算法。该算法关键在于如何度量两个簇的距离，集合间的距离计算有如下方式：
$$\begin{array}{rl}最小距离：dist(C_i,C_j)& =mi{n}_{[x\in C_i,z\in C_j]}||x-z|{|}_2\\ 最大距离：dist(C_i,C_j)& =ma{x}_{[x\in C_i,z\in C_j]}||x-z|{|}_2\\ 平均距离：dist(C_i,C_j)& =\frac{1}{|C_i||C_j|}\sum _{x\in C_i}\sum _{z\in C_j}||x-z|{|}_2\end{array}$$
采用最小距离的AGNES称为 “单连接算法” ，单连接趋向于发现有局部邻近性的簇。采用最大距离的AGNES称为 “全连接算法”，全连接趋向于发现有全局邻近性的簇。但是，单连接和全连接对离群点敏感，因为离群点始终为单个簇无法参与合并。采用平均距离的AGNES称为 “均连接算法” ，它可以克服离群点问题。

AGNES算法流程如下：

1. 输入: 数据集D和聚类簇数k
2. 初始化m个簇为m个样本
3. for i =1,2,…,m do
4. \enspace\enspace for j = 1,2,…,m do
5. \enspace\enspace\enspace\enspace $D_{ij}=dist(C_i,C_j)$
6. \enspace\enspace\enspace\enspace $D_{ji}=D_{ij}$
7. \enspace\enspace end for
8. end for
9. 设置当前簇个数：q = m
10. while q > k do
11. \enspace\enspace 从距离矩阵D中找到最近的两个簇$C_i$和$C_j$
12. \enspace\enspace 合并 $C_i=C_i\cup C_j$
13. \enspace\enspace 删除$C_j$并对簇重新编号
14. \enspace\enspace 删除距离矩阵D的第i行和第j列
15. \enspace\enspace for j=1,2,3…,q -1 do
16. \enspace\enspace\enspace\enspace 计算新的$D_{ij}=dist(C_i,C_j)$
17. \enspace\enspace\enspace\enspace 计算新的$D_{ji}=D_{ij}$
18. \enspace\enspace end for
19. \enspace\enspace 簇个数减少 q = q -1
20. end while
21. 输出: { C 1 , C 2 , . . . , C k } \{C_1,C_2,...,C_k\} {C1​,C2​,...,Ck​}

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