lab2.py

import math

# ============================================================
# Матрица косинусного подобия
# ============================================================
# Здесь задаём входные данные. Если хотите подставить свою матрицу —
# просто поменяйте labels_init и raw_sim, главное чтобы метки совпадали.

labels_init = ['U1', 'U2', 'U3', 'U4', 'U5']

# Задаём только верхний треугольник — матрица симметричная,
# поэтому повторяться не нужно
raw_sim = {
    ('U1', 'U2'): 0.95,
    ('U1', 'U3'): 0.90,
    ('U1', 'U4'): 0.85,
    ('U1', 'U5'): 0.80,
    ('U2', 'U3'): 0.75,
    ('U2', 'U4'): 0.70,
    ('U2', 'U5'): 0.65,
    ('U3', 'U4'): 0.60,
    ('U3', 'U5'): 0.80,
    ('U4', 'U5'): 0.70,
}

# Порог: если подобие двух кластеров ниже R, объединять их уже не будем
R = 0.85

# ============================================================
# Вспомогательные функции
# ============================================================

def build_matrix(labels, raw):
    """Разворачиваем половинчатый словарь в полную матрицу подобий."""
    sim = {}
    for i in labels:
        for j in labels:
            if i == j:
                sim[(i, j)] = 1.0
            elif (i, j) in raw:
                sim[(i, j)] = raw[(i, j)]
            elif (j, i) in raw:
                sim[(i, j)] = raw[(j, i)]
            else:
                sim[(i, j)] = 0.0
    return sim

def print_matrix(labels, sim, title):
    """Красиво печатаем матрицу подобия в консоль."""
    col_w = 12
    lbl_w = 16

    print(f"\n  {title}")
    header = " " * lbl_w + "".join(f"{l:>{col_w}}" for l in labels)
    print("  " + header)
    print("  " + "-" * len(header))
    for i in labels:
        row = f"{i:<{lbl_w}}"
        for j in labels:
            # Нижний треугольник не дублируем — ставим прочерк
            if labels.index(i) > labels.index(j):
                row += f"{'—':>{col_w}}"
            else:
                row += f"{sim[(i,j)]:>{col_w}.6f}"
        print("  " + row)

def find_max_pair(labels, sim):
    """
    Ищем пару кластеров с наибольшим подобием — именно их будем объединять следующими.
    Возвращает (i, j, значение).
    """
    best_val = -1.0
    best_i, best_j = None, None
    for idx_i, i in enumerate(labels):
        for idx_j, j in enumerate(labels):
            if idx_j <= idx_i:
                continue
            v = sim[(i, j)]
            if v > best_val:
                best_val = v
                best_i, best_j = i, j
    return best_i, best_j, best_val

def merge_clusters(labels, sim, ci, cj):
    """
    Объединяем два кластера ci и cj в один.
    Подобие нового кластера к любому другому считаем по правилу максимума:
    чем ближе хотя бы один из участников — тем ближе весь кластер.
    """
    new_label = f"{ci}, {cj}"
    new_labels = [new_label] + [l for l in labels if l != ci and l != cj]

    new_sim = {}
    for i in new_labels:
        for j in new_labels:
            if i == j:
                new_sim[(i, j)] = 1.0
            elif i == new_label and j == new_label:
                new_sim[(i, j)] = 1.0
            elif i == new_label:
                v = max(sim[(ci, j)], sim[(cj, j)])
                new_sim[(i, j)] = v
                new_sim[(j, i)] = v
            elif j == new_label:
                v = max(sim[(i, ci)], sim[(i, cj)])
                new_sim[(i, j)] = v
                new_sim[(j, i)] = v
            else:
                new_sim[(i, j)] = sim[(i, j)]
                new_sim[(j, i)] = sim[(j, i)]

    return new_labels, new_sim

# ============================================================
# Основной алгоритм
# ============================================================

print("=" * 65)
print("  ИЕРАРХИЧЕСКАЯ АГЛОМЕРАТИВНАЯ КЛАСТЕРИЗАЦИЯ")
print(f"  Порог объединения R = {R}")
print("=" * 65)

# Начинаем с каждого объекта в своём кластере
labels = list(labels_init)
sim = build_matrix(labels, raw_sim)

print_matrix(labels, sim, "Начальная матрица косинусного подобия")

iteration = 0

while True:
    ci, cj, val = find_max_pair(labels, sim)

    # Если даже самая близкая пара не дотягивает до порога — останавливаемся
    if val < R:
        print(f"\n{'=' * 65}")
        print(f"  Максимальное подобие {val:.6f} < R = {R}")
        print(f"  Дальнейшее объединение невозможно. Алгоритм завершён.")
        break

    iteration += 1
    print(f"\n{'=' * 65}")
    print(f"  Итерация {iteration}")
    print(f"  Найдено максимальное подобие: cos({ci}, {cj}) = {val:.6f} >= R = {R}")
    print(f"  Объединяем кластеры: [{ci}] + [{cj}] → [{ci}, {cj}]")
    print(f"  Правило пересчёта: sim(новый, X) = MAX(sim({ci}, X), sim({cj}, X))")

    # Сохраняем старую матрицу, чтобы корректно показать исходные значения при пересчёте
    prev_sim = dict(sim)
    labels, sim = merge_clusters(labels, sim, ci, cj)

    merged = f"{ci}, {cj}"
    others = [l for l in labels if l != merged]
    if others:
        print(f"\n  Пересчёт подобий для нового кластера [{merged}]:")
        for o in others:
            new_v = sim[(merged, o)]
            v_ci = prev_sim.get((ci, o), prev_sim.get((o, ci), 0.0))
            v_cj = prev_sim.get((cj, o), prev_sim.get((o, cj), 0.0))
            print(f"    sim([{merged}], [{o}]) = MAX(sim([{ci}], [{o}]), sim([{cj}], [{o}]))")
            print(f"                           = MAX({v_ci:.6f}, {v_cj:.6f}) = {new_v:.6f}")

    print_matrix(labels, sim, f"Матрица после итерации {iteration}")

print(f"\n{'=' * 65}")
print(f"  ИТОГОВЫЕ КЛАСТЕРЫ:")
for i, l in enumerate(labels, 1):
    members = l.replace(" ", "").split(",")
    print(f"  Кластер {i}: {{ {', '.join(members)} }}")
print("=" * 65)