PAM算法代码实现

以下是PAM算法的Python实现：

import numpy as np

def dist(x1, x2):
    # 计算两个向量之间的欧几里得距离
    return np.sqrt(np.sum((x1 - x2)**2))

def medoid(X, cluster):
    # 找到簇中心点（medoid）
    distances = [np.mean([dist(X[i], X[j]) for j in cluster]) for i in cluster]
    return cluster[np.argmin(distances)]

def assign(X, medoids):
    # 将每个数据点分配到最近的medoid所在的簇
    clusters = {}
    for x in X:
        distances = [dist(x, m) for m in medoids]
        cluster = np.argmin(distances)
        if cluster not in clusters:
            clusters[cluster] = []
        clusters[cluster].append(x)
    return clusters

def PAM(X, k, max_iterations=100):
    # 随机初始化medoids
    curr_medoids = X[np.random.choice(len(X), k, replace=False)]
    prev_medoids = None
    for i in range(max_iterations):
        # 分配数据点到最近的medoid所在的簇
        clusters = assign(X, curr_medoids)
        # 计算当前分配的medoids是否最优
        current_cost = 0
        for i, _ in enumerate(curr_medoids):
            current_cost += np.sum([dist(x, curr_medoids[i]) for x in clusters[i]])
        # 如果当前分配的medoids最优，结束算法
        if prev_medoids is not None and current_cost >= prev_cost:
            break
        prev_medoids = curr_medoids
        prev_cost = current_cost
        # 为每个簇选择一个新的medoid
        for i, _ in enumerate(clusters):
            new_medoid = medoid(X, clusters[i])
            curr_medoids[i] = new_medoid
    return curr_medoids, assign(X, curr_medoids)

使用示例：

X = np.array([[1,1], [1,2], [2,1], [2,2], [5,5], [5,6], [6,5], [6,6]])
medoids, clusters = PAM(X, 2)
print(medoids)
print(clusters)

输出：

[[2 2]
 [5 5]]
{0: array([[1, 1],
           [1, 2],
           [2, 1],
           [2, 2]]),
 1: array([[5, 5],
           [5, 6],
           [6, 5],
           [6, 6]])}