import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from scipy.spatial.distance import squareform
import matplotlib.font_manager as fm

# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans']
plt.rcParams['axes.unicode_minus'] = False

# 11种语言的距离矩阵
D = np.array([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [7, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0],
    [6, 4, 5, 5, 0, 0, 0, 0, 0, 0, 0],
    [6, 6, 6, 9, 7, 0, 0, 0, 0, 0, 0],
    [6, 6, 5, 9, 7, 2, 0, 0, 0, 0, 0],
    [6, 6, 5, 9, 7, 1, 1, 0, 0, 0, 0],
    [7, 7, 6, 10, 8, 5, 3, 4, 0, 0, 0],
    [9, 8, 8, 8, 9, 10, 10, 10, 10, 0, 0],
    [9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 0]
])

# 语言名称
languages = ['E', 'N', 'Da', 'Du', 'G', 'Fr', 'S', 'I', 'P', 'H', 'Fi']
language_names = ['英语', '挪威语', '丹麦语', '荷兰语', '德语', '法语', '西班牙语', '意大利语', '波兰语', '匈牙利语', '芬兰语']

# 确保距离矩阵是对称的
D_symmetric = np.maximum(D, D.T)

print("距离矩阵：")
print(D_symmetric)
print("\n语言代码对应：")
for i, (code, name) in enumerate(zip(languages, language_names)):
    print(f"{i}: {code} - {name}")

# 将距离矩阵转换为压缩形式（用于scipy）
distance_vector = squareform(D_symmetric)

def plot_dendrogram(linkage_matrix, method_name, languages):
    """绘制树状图"""
    plt.figure(figsize=(12, 8))
    dendrogram(linkage_matrix, labels=languages, leaf_rotation=45)
    plt.title(f'{method_name}聚类树状图')
    plt.xlabel('语言')
    plt.ylabel('距离')
    plt.tight_layout()
    plt.show()

def print_clustering_steps(linkage_matrix, method_name, languages):
    """打印聚类过程"""
    print(f"\n{method_name}聚类过程：")
    n = len(languages)
    clusters = {i: [languages[i]] for i in range(n)}
    
    for i, (idx1, idx2, dist, count) in enumerate(linkage_matrix):
        idx1, idx2 = int(idx1), int(idx2)
        new_idx = n + i
        
        if idx1 < n:
            cluster1 = clusters[idx1]
        else:
            cluster1 = clusters[idx1]
            
        if idx2 < n:
            cluster2 = clusters[idx2]
        else:
            cluster2 = clusters[idx2]
            
        new_cluster = cluster1 + cluster2
        clusters[new_idx] = new_cluster
        
        print(f"步骤 {i+1}: 合并 {cluster1} 和 {cluster2}, 距离 = {dist:.2f}")

# (1) 最短距离法 (Single Linkage)
print("=" * 50)
print("(1) 最短距离法 (Single Linkage)")
print("=" * 50)
linkage_single = linkage(distance_vector, method='single')
print_clustering_steps(linkage_single, "最短距离法", languages)
plot_dendrogram(linkage_single, "最短距离法", languages)

# (2) 最长距离法 (Complete Linkage)
print("\n" + "=" * 50)
print("(2) 最长距离法 (Complete Linkage)")
print("=" * 50)
linkage_complete = linkage(distance_vector, method='complete')
print_clustering_steps(linkage_complete, "最长距离法", languages)
plot_dendrogram(linkage_complete, "最长距离法", languages)

# (3) 类平均距离法 (Average Linkage)
print("\n" + "=" * 50)
print("(3) 类平均距离法 (Average Linkage)")
print("=" * 50)
linkage_average = linkage(distance_vector, method='average')
print_clustering_steps(linkage_average, "类平均距离法", languages)
plot_dendrogram(linkage_average, "类平均距离法", languages)

# (4) 重心距离法 (Centroid Linkage)
print("\n" + "=" * 50)
print("(4) 重心距离法 (Centroid Linkage)")
print("=" * 50)
linkage_centroid = linkage(distance_vector, method='centroid')
print_clustering_steps(linkage_centroid, "重心距离法", languages)
plot_dendrogram(linkage_centroid, "重心距离法", languages)

# 比较不同方法的结果
print("\n" + "=" * 60)
print("聚类结果比较")
print("=" * 60)

def get_clusters_at_distance(linkage_matrix, threshold, languages):
    """获取指定距离阈值下的聚类结果"""
    cluster_labels = fcluster(linkage_matrix, threshold, criterion='distance')
    clusters = {}
    for i, label in enumerate(cluster_labels):
        if label not in clusters:
            clusters[label] = []
        clusters[label].append(languages[i])
    return clusters

# 在距离阈值为5时比较各方法的聚类结果
threshold = 5
print(f"\n在距离阈值 {threshold} 时的聚类结果：")

methods = [
    ('最短距离法', linkage_single),
    ('最长距离法', linkage_complete),
    ('类平均距离法', linkage_average),
    ('重心距离法', linkage_centroid)
]

for method_name, linkage_matrix in methods:
    clusters = get_clusters_at_distance(linkage_matrix, threshold, languages)
    print(f"\n{method_name}:")
    for cluster_id, members in clusters.items():
        print(f"  簇 {cluster_id}: {members}")

# 分析语言相似性
print("\n" + "=" * 60)
print("语言相似性分析")
print("=" * 60)

print("\n最相似的语言对（距离最小）：")
min_dist = float('inf')
min_pairs = []
for i in range(len(D_symmetric)):
    for j in range(i+1, len(D_symmetric)):
        if D_symmetric[i][j] < min_dist and D_symmetric[i][j] > 0:
            min_dist = D_symmetric[i][j]
            min_pairs = [(i, j)]
        elif D_symmetric[i][j] == min_dist:
            min_pairs.append((i, j))

for i, j in min_pairs:
    print(f"{languages[i]}({language_names[i]}) - {languages[j]}({language_names[j]}): 距离 = {min_dist}")

print("\n最不相似的语言对（距离最大）：")
max_dist = 0
max_pairs = []
for i in range(len(D_symmetric)):
    for j in range(i+1, len(D_symmetric)):
        if D_symmetric[i][j] > max_dist:
            max_dist = D_symmetric[i][j]
            max_pairs = [(i, j)]
        elif D_symmetric[i][j] == max_dist:
            max_pairs.append((i, j))

for i, j in max_pairs:
    print(f"{languages[i]}({language_names[i]}) - {languages[j]}({language_names[j]}): 距离 = {max_dist}")