Глава 7. КЛАСТЕРИЗАЦИЯ
7.1. Метрика расстояния (Евклидово)
\[ d(\mathbf{u}, \mathbf{v}) = \sqrt{\sum_{i=1}^{n} (u_i - v_i)^2} \]Объяснение: Евклидово расстояние измеряет прямолинейное расстояние между двумя точками в n-мерном пространстве. Широко используется в кластеризации и методах ближайших соседей.
Пример: Для \(\mathbf{u} = [1, 2]\) и \(\mathbf{v} = [3, 4]\), \(d(\mathbf{u}, \mathbf{v}) = \sqrt{(3 - 1)^2 + (4 - 2)^2} = \sqrt{2^2 + 2^2} = \sqrt{4 + 4} = \sqrt{8} \approx 2.828\).
Реализация:
import numpy as np
def euclidean_distance(u, v):
"""Вычисляет евклидово расстояние между векторами u и v."""
return np.sqrt(np.sum((np.array(u) - np.array(v))**2))
u_vec = [1, 2]
v_vec = [3, 4]
dist = euclidean_distance(u_vec, v_vec)
print(f"Euclidean distance: {dist}")
7.2. Манхэттенское расстояние (Расстояние городских кварталов)
\[ d(\mathbf{u}, \mathbf{v}) = \sum_{i=1}^{n} |u_i - v_i| \]Объяснение: Манхэттенское расстояние измеряет сумму абсолютных разностей между соответствующими компонентами, напоминая расстояния по сетке городских кварталов.
Пример: Для \(\mathbf{u} = [1, 2]\) и \(\mathbf{v} = [3, 4]\), \(d(\mathbf{u}, \mathbf{v}) = |3 - 1| + |4 - 2| = 2 + 2 = 4\).
Реализация:
import numpy as np
def manhattan_distance(u, v):
"""Вычисляет манхэттенское расстояние между векторами u и v."""
return np.sum(np.abs(np.array(u) - np.array(v)))
u_vec = [1, 2]
v_vec = [3, 4]
dist = manhattan_distance(u_vec, v_vec)
print(f"Manhattan distance: {dist}")
7.3. Косинусное сходство
\[ \text{Cosine Similarity}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\| \|\mathbf{v}\|} \]Объяснение: Косинусное сходство измеряет косинус угла между двумя векторами, отражая сходство ориентации, а не магнитуды. Значение 1 означает одинаковое направление, -1 - противоположное, 0 - ортогональность.
Пример: Для \(\mathbf{u} = [1, 0]\) и \(\mathbf{v} = [0, 1]\), сходство равно 0. (\(\mathbf{u} \cdot \mathbf{v} = 0\))
Реализация:
import numpy as np
def cosine_similarity(u, v):
"""Вычисляет косинусное сходство между двумя векторами."""
u = np.array(u)
v = np.array(v)
dot_product = np.dot(u, v)
norm_u = np.linalg.norm(u)
norm_v = np.linalg.norm(v)
if norm_u == 0 or norm_v == 0:
return 0.0
return dot_product / (norm_u * norm_v)
u_vec = [1, 0]
v_vec = [0, 1]
sim = cosine_similarity(u_vec, v_vec)
print(f"Cosine Similarity: {sim}")
7.4. Сходство Жаккара (для бинарных данных)
\[ \text{Jaccard Similarity}(A, B) = \frac{|A \cap B|}{|A \cup B|} \] (где A и B - множества или бинарные векторы, \(|\cdot|\) - мощность множества или количество ненулевых элементов/единиц)Объяснение: Сходство Жаккара сравнивает пересечение и объединение бинарных данных (или множеств), часто используется для сходства текстов и множеств.
Пример: Для \(\mathbf{u} = [1, 1, 0]\) и \(\mathbf{v} = [1, 0, 1]\). Пересечение (AND): \([1, 0, 0]\), размер = 1. Объединение (OR): \([1, 1, 1]\), размер = 3. Сходство = 1 / 3.
Реализация:
import numpy as np
def jaccard_similarity_binary(u, v):
"""Вычисляет сходство Жаккара для бинарных векторов u и v."""
u = np.asarray(u, dtype=bool)
v = np.asarray(v, dtype=bool)
intersection = np.sum(np.logical_and(u, v))
union = np.sum(np.logical_or(u, v))
if union == 0:
return 1.0 # Если оба вектора нулевые
return intersection / union
u_bin = [1, 1, 0]
v_bin = [1, 0, 1]
sim = jaccard_similarity_binary(u_bin, v_bin)
print(f"Jaccard Similarity: {sim}")
7.5. Целевая функция k-Means
\[ J = \sum_{i=1}^{k} \sum_{\mathbf{x}_j \in C_i} \|\mathbf{x}_j - \boldsymbol{\mu}_i\|^2 \] (где k - число кластеров, \(C_i\) - множество точек в i-м кластере, \(\boldsymbol{\mu}_i\) - центроид i-го кластера)Объяснение: Целевая функция k-Means минимизирует сумму квадратов расстояний между точками данных и центроидами их назначенных кластеров (внутрикластерная сумма квадратов).
Пример: Для точек \([1, 2], [3, 4]\) в кластере \(C_1\) с центроидом \(\boldsymbol{\mu}_1 = [2, 3]\), вычислить вклад в J. Вклад \( = \|[1, 2] - [2, 3]\|^2 + \|[3, 4] - [2, 3]\|^2 = \|[-1, -1]\|^2 + \|[1, 1]\|^2 = ((-1)^2+(-1)^2) + (1^2+1^2) = (1+1) + (1+1) = 2 + 2 = 4\).
Реализация (вычисление значения функции):
import numpy as np
# X - данные (n_samples, n_features)
# centroids - координаты центроидов (k, n_features)
# labels - метки кластеров для каждой точки X (n_samples,)
def k_means_objective(X, centroids, labels):
"""Вычисляет целевую функцию k-Means (инерцию)."""
total_inertia = 0
for i in range(len(centroids)):
cluster_points = X[labels == i]
if len(cluster_points) > 0:
centroid = centroids[i]
# Сумма квадратов расстояний до центроида для точек этого кластера
inertia_i = np.sum(np.linalg.norm(cluster_points - centroid, axis=1)**2)
total_inertia += inertia_i
return total_inertia
# Альтернатива, если использовать labels для индексации centroids:
# return np.sum(np.linalg.norm(X - centroids[labels], axis=1)**2) # Как в OCR
# Пример
X_data = np.array([[1, 2], [3, 4], [8, 8], [9, 10]])
centroids_km = np.array([[2, 3], [8.5, 9]])
labels_km = np.array([0, 0, 1, 1]) # Пример меток
inertia = k_means_objective(X_data, centroids_km, labels_km)
print(f"k-Means Objective (Inertia): {inertia}") # 4.0 (от кластера 0) + 0.5 + 0.5 (от кл. 1) = 5.0
7.6. Правило обновления центроидов (k-Means)
\[ \boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\mathbf{x}_j \in C_i} \mathbf{x}_j \] (Новый центроид i-го кластера - это среднее всех точек, отнесенных к этому кластеру)Объяснение: Центроид каждого кластера обновляется как среднее арифметическое (центр масс) точек, назначенных этому кластеру на предыдущем шаге.
Пример: Для кластера \(C_1 = \{[1, 2], [3, 4]\}\), вычислить новый центроид \(\boldsymbol{\mu}_1\). \(\boldsymbol{\mu}_1 = \frac{1}{2} ([1, 2] + [3, 4]) = \frac{1}{2} [4, 6] = [2, 3]\).
Реализация:
import numpy as np
# X - данные (n_samples, n_features)
# labels - метки кластеров для каждой точки X (n_samples,)
# k - количество кластеров
def update_centroids(X, labels, k):
"""Обновляет центроиды в k-Means."""
new_centroids = np.zeros((k, X.shape[1]))
for i in range(k):
cluster_points = X[labels == i]
if len(cluster_points) > 0:
new_centroids[i] = np.mean(cluster_points, axis=0)
else:
# Обработка пустого кластера (например, оставить старый центроид или переинициализировать)
# Здесь для простоты оставим нулевым, но это плохая практика
print(f"Warning: Cluster {i} is empty.")
# Можно переназначить самую далекую точку или случайную
return new_centroids
# Пример
X_data = np.array([[1, 2], [3, 4], [1.5, 2.5]])
labels_km = np.array([0, 0, 0])
k_clusters = 1 # В данном случае 1 кластер
new_cents = update_centroids(X_data, labels_km, k_clusters)
print(f"Updated centroids: {new_cents}") # [[ (1+3+1.5)/3, (2+4+2.5)/3 ]] = [[1.833, 2.833]]
7.7. Метод локтя (Elbow Method) для оптимального k
\[ J(k) = \sum_{i=1}^{k} \sum_{\mathbf{x}_j \in C_i} \|\mathbf{x}_j - \boldsymbol{\mu}_i\|^2 \] (Анализируется график зависимости \(J(k)\) (внутрикластерной суммы квадратов) от числа кластеров k)Объяснение: Метод локтя находит оптимальное количество кластеров k, определяя "локоть" (точку резкого замедления убывания) на графике зависимости целевой функции k-Means \(J(k)\) от k.
Реализация (вычисление J(k) для разных k):
import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
# X - данные (n_samples, n_features)
# max_k - максимальное количество кластеров для проверки
def elbow_method_inertia(X, max_k):
"""Вычисляет инерцию для разного числа кластеров k."""
inertias = []
k_values = range(1, max_k + 1)
for k in k_values:
# n_init=10 для уменьшения влияния случайной инициализации
kmeans = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
inertias.append(kmeans.inertia_) # inertia_ - это J(k)
return k_values, inertias
# Пример данных
# X_data = np.random.rand(100, 2) * 10
# max_clusters = 10
# k_vals, inertia_vals = elbow_method_inertia(X_data, max_clusters)
# Визуализация (опционально)
# plt.figure(figsize=(6, 4))
# plt.plot(k_vals, inertia_vals, marker='o')
# plt.title('Метод локтя для k-Means')
# plt.xlabel('Количество кластеров (k)')
# plt.ylabel('Инерция (J(k))')
# plt.grid(True)
# plt.show()
7.8. Целевая функция k-Medoids
\[ J = \sum_{i=1}^{k} \sum_{\mathbf{x}_j \in C_i} d(\mathbf{x}_j, \mathbf{m}_i) \] (где \(\mathbf{m}_i\) - медоид i-го кластера (реальная точка из данных), \(d\) - функция расстояния)Объяснение: k-Medoids минимизирует сумму расстояний между точками данных и медоидами их кластеров. Медоиды - это точки из самого набора данных, что делает метод более робастным к выбросам, чем k-Means.
Пример: Заменить центроиды медоидами для робастной кластеризации.
Реализация (вычисление значения функции):
import numpy as np
# X - данные (n_samples, n_features)
# medoid_indices - индексы медоидов в X (k,)
# labels - метки кластеров для X (n_samples,)
# distance_func - функция расстояния (e.g., euclidean_distance)
def k_medoids_objective(X, medoid_indices, labels, distance_func):
"""Вычисляет целевую функцию k-Medoids."""
total_distance = 0
medoids = X[medoid_indices] # Получаем координаты медоидов
k = len(medoids)
for i in range(k):
cluster_points = X[labels == i]
if len(cluster_points) > 0:
medoid = medoids[i]
# Сумма расстояний до медоида
# Используем distance_func
distances_i = [distance_func(point, medoid) for point in cluster_points]
total_distance += np.sum(distances_i)
# Альтернатива с linalg.norm, если distance_func - евклидово:
# total_distance += np.sum(np.linalg.norm(cluster_points - medoid, axis=1))
return total_distance
# Пример
# X_data = np.array([[1, 2], [3, 4], [1, 3], [8, 8], [9, 10]])
# med_idx = np.array([0, 3]) # Точки [1,2] и [8,8] - медоиды
# labels_med = np.array([0, 0, 0, 1, 1]) # Пример меток
# obj_val = k_medoids_objective(X_data, med_idx, labels_med, euclidean_distance)
# print(f"k-Medoids Objective: {obj_val}")
# Кластер 0: d([1,2],[1,2])=0, d([3,4],[1,2])=sqrt(8), d([1,3],[1,2])=1. Сумма=0+2.828+1=3.828
# Кластер 1: d([8,8],[8,8])=0, d([9,10],[8,8])=sqrt(1+4)=sqrt(5)=2.236. Сумма=0+2.236=2.236
# Итого: 3.828 + 2.236 = 6.064
7.9. Целевая функция Fuzzy c-Means (Нечеткая c-средних)
\[ J_m = \sum_{i=1}^{c} \sum_{j=1}^{n} u_{ij}^m \|\mathbf{x}_j - \mathbf{v}_i\|^2 \] (где c - число кластеров, n - число точек, \(u_{ij}\) - степень принадлежности j-й точки i-му кластеру (\(\sum_i u_{ij} = 1\)), \(m > 1\) - параметр расплывчатости (fuzzifier), \(\mathbf{v}_i\) - центр i-го кластера)Объяснение: Fuzzy c-means присваивает каждой точке данных значения принадлежности \(u_{ij}\) к каждому кластеру, допуская мягкую (нечеткую) кластеризацию.
Реализация (вычисление значения функции):
import numpy as np
# X - данные (n_samples, n_features)
# centroids - центры кластеров (c, n_features)
# memberships - матрица принадлежностей (n_samples, c)
# m - параметр расплывчатости
def fuzzy_c_means_objective(X, centroids, memberships, m):
"""Вычисляет целевую функцию Fuzzy c-Means."""
n_samples = X.shape[0]
n_clusters = centroids.shape[0]
objective = 0
# Вычисляем квадраты расстояний от каждой точки до каждого центроида
dist_sq = np.zeros((n_samples, n_clusters))
for i in range(n_clusters):
dist_sq[:, i] = np.linalg.norm(X - centroids[i], axis=1)**2
# Вычисляем взвешенную сумму
objective = np.sum((memberships**m) * dist_sq)
return objective
# Пример (требуются memberships из алгоритма Fuzzy c-Means)
# X_data = np.array([[1, 1], [1, 2], [5, 5], [6, 5]])
# centroids_fcm = np.array([[1, 1.5], [5.5, 5]])
# memberships_fcm = np.array([[0.9, 0.1], [0.8, 0.2], [0.1, 0.9], [0.2, 0.8]]) # Пример принадлежностей
# m_fuzzifier = 2
# obj_val = fuzzy_c_means_objective(X_data, centroids_fcm, memberships_fcm, m_fuzzifier)
# print(f"Fuzzy c-Means Objective: {obj_val}")
7.10. Коэффициент силуэта (Silhouette Score)
\[ S_i = \frac{b_i - a_i}{\max(a_i, b_i)} \] (где \(a_i\) - среднее расстояние от точки i до других точек в ее кластере, \(b_i\) - минимальное среднее расстояние от точки i до точек в другом кластере) Общий Silhouette Score - среднее \(S_i\) по всем точкам.Объяснение: Коэффициент силуэта оценивает качество кластеризации, сравнивая внутрикластерные расстояния с межкластерными. Значения близки к 1 указывают на хорошую кластеризацию, близки к -1 - на плохую, близки к 0 - на перекрывающиеся кластеры.
Реализация (используя scikit-learn):
import numpy as np
from sklearn.metrics import silhouette_score
from sklearn.cluster import KMeans
# Пример данных
# X_data = np.array([[1, 2], [1, 4], [1, 0],
# [4, 2], [4, 4], [4, 0]])
# Пример кластеризации
# kmeans = KMeans(n_clusters=2, random_state=0, n_init=10).fit(X_data)
# labels_sil = kmeans.labels_
# Вычисление коэффициента силуэта
# score = silhouette_score(X_data, labels_sil)
# print(f"Silhouette Score: {score}")
7.11. Дендрограмма иерархической кластеризации
\[ d(C_1, C_2) = \min_{\mathbf{x} \in C_1, \mathbf{y} \in C_2} \|\mathbf{x} - \mathbf{y}\| \quad (\text{Single linkage}) \] (или другие методы связи: complete, average, Ward)Объяснение: Дендрограмма визуально представляет процесс иерархической кластеризации, показывая порядок слияния кластеров и расстояния, на которых происходят слияния.
Реализация (построение дендрограммы):
import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt
# Пример данных
# X_data = np.array([[1, 2], [2, 2], [1, 4], [4, 4], [5, 4]])
# Выполняем иерархическую кластеризацию (метод Ward)
# Z = linkage(X_data, method='ward')
# Строим дендрограмму
# plt.figure(figsize=(8, 4))
# plt.title('Иерархическая кластеризация (Дендрограмма)')
# plt.xlabel('Индекс образца')
# plt.ylabel('Расстояние (Ward)')
# dendrogram(Z)
# plt.show()
7.12. Связь Уорда (Ward's Linkage)
\[ d(C_i, C_j) = \sqrt{\frac{|C_i||C_j|}{|C_i| + |C_j|}} \|\boldsymbol{\mu}_i - \boldsymbol{\mu}_j\| \] (или чаще используется приращение суммы квадратов \(ESS\)) \[ \Delta ESS = \frac{|C_i||C_j|}{|C_i| + |C_j|} \|\boldsymbol{\mu}_i - \boldsymbol{\mu}_j\|^2 \] (Минимизируется прирост внутрикластерной дисперсии при слиянии)Объяснение: Метод связи Уорда минимизирует увеличение общей внутрикластерной дисперсии при слиянии кластеров, что приводит к формированию компактных, сферических кластеров.
Реализация (используя scipy.cluster.hierarchy.linkage):
from scipy.cluster.hierarchy import linkage
import numpy as np
# Пример данных
# X_data = np.array([[1, 2], [2, 2], [1, 4], [4, 4], [5, 4]])
# Вычисляем матрицу связей методом Ward
# Z_ward = linkage(X_data, method='ward')
# print("Ward Linkage Matrix Z:\n", Z_ward)
7.13. Одиночная связь (Single Linkage) против Полной связи (Complete Linkage)
\[ d_{\text{single}}(C_i, C_j) = \min_{\mathbf{x} \in C_i, \mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y}) \] \[ d_{\text{complete}}(C_i, C_j) = \max_{\mathbf{x} \in C_i, \mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y}) \]Объяснение: Одиночная связь (метод ближайшего соседа) объединяет кластеры на основе минимального расстояния между точками из разных кластеров (склонна к "цепному эффекту"). Полная связь (метод дальнего соседа) использует максимальное расстояние (формирует более компактные кластеры).
Реализация (используя scipy):
from scipy.cluster.hierarchy import linkage
import numpy as np
# Пример данных
# X_data = np.array([[1, 2], [2, 2], [1, 4], [4, 4], [5, 4]])
# Вычисляем матрицы связей
# Z_single = linkage(X_data, method='single')
# Z_complete = linkage(X_data, method='complete')
# print("Single Linkage Matrix Z:\n", Z_single)
# print("\nComplete Linkage Matrix Z:\n", Z_complete)
7.14. Средняя связь (Average Linkage)
\[ d_{\text{average}}(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{\mathbf{x} \in C_i} \sum_{\mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y}) \]Объяснение: Средняя связь вычисляет среднее расстояние между всеми парами точек из двух разных кластеров, балансируя крайности одиночной и полной связи.
Реализация (используя scipy):
from scipy.cluster.hierarchy import linkage
import numpy as np
# Пример данных
# X_data = np.array([[1, 2], [2, 2], [1, 4], [4, 4], [5, 4]])
# Вычисляем матрицу связей
# Z_average = linkage(X_data, method='average')
# print("Average Linkage Matrix Z:\n", Z_average)
7.15. Критерий минимального остовного дерева (MST)
\[ \text{Вес MST} = \sum_{(u, v) \in E_{\text{MST}}} w(u, v) \] (где \(w(u, v)\) - вес ребра (расстояние) между точками u и v, \(E_{\text{MST}}\) - множество ребер минимального остовного дерева)Объяснение: Минимальное остовное дерево (MST) соединяет все точки с минимальным суммарным весом ребер. Используется в некоторых алгоритмах кластеризации (например, для нахождения начальных кластеров или анализа связности) для обнаружения плотных областей.
Реализация (используя scipy.sparse.csgraph):
import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.sparse.csgraph import minimum_spanning_tree
# Пример данных
# X_data = np.array([[1, 2], [2, 2], [1, 4], [4, 4], [5, 4]])
# Вычисляем матрицу попарных расстояний
# distance_matrix = squareform(pdist(X_data, metric='euclidean'))
# Находим MST. Результат - разреженная матрица CSR.
# mst = minimum_spanning_tree(distance_matrix)
# Суммарный вес MST
# mst_weight = mst.sum()
# print(f"Total weight of MST: {mst_weight}")
# print("\nMST (CSR matrix):\n", mst.toarray()) # Показать матрицу смежности MST
7.16. Условие основной точки DBSCAN
\[ |N_{\epsilon}(\mathbf{x})| \ge \text{MinPts} \] (где \(N_{\epsilon}(\mathbf{x}) = \{\mathbf{y} \in D \mid d(\mathbf{x}, \mathbf{y}) \le \epsilon\}\) - \(\epsilon\)-окрестность точки \(\mathbf{x}\), MinPts - минимальное число точек)Объяснение: Основная точка (core point) в DBSCAN должна иметь по крайней мере MinPts соседей (включая саму себя) в пределах расстояния \(\epsilon\).
Реализация (проверка условия):
import numpy as np
# neighbors - список или массив индексов или координат соседей точки x в epsilon-окрестности
# MinPts - параметр DBSCAN
def check_core_point(neighbors, MinPts):
"""Проверяет, является ли точка основной."""
# Убедимся, что считаем и саму точку (если она не включена в neighbors)
# Стандартно |Neighbors(x)| в DBSCAN включает саму точку x.
return len(neighbors) >= MinPts
# Пример
# neighbors_of_x = [...] # Список соседей, полученный из данных
# is_core = check_core_point(neighbors_of_x, MinPts=4)
7.17. Условие плотностной связности DBSCAN
Точка \(\mathbf{p}\) достижима по плотности (density-reachable) от точки \(\mathbf{q}\), если существует цепочка точек \(\mathbf{p}_1, \dots, \mathbf{p}_n\) такая, что \(\mathbf{p}_1 = \mathbf{q}\), \(\mathbf{p}_n = \mathbf{p}\), и каждая \(\mathbf{p}_{i+1}\) находится в \(\epsilon\)-окрестности основной точки \(\mathbf{p}_i\). Две точки \(\mathbf{p}\) и \(\mathbf{q}\) связаны по плотности (density-connected), если существует основная точка \(\mathbf{o}\), из которой достижимы и \(\mathbf{p}\), и \(\mathbf{q}\).Объяснение: DBSCAN формирует кластеры, соединяя точки, которые достижимы по плотности друг от друга через цепочки соседей основных точек.
Реализация (использование scikit-learn):
import numpy as np
from sklearn.cluster import DBSCAN
# X - данные (n_samples, n_features)
# epsilon - радиус окрестности (eps)
# min_samples - параметр MinPts
# X_data = np.array([[1, 2], [2, 2], [2, 3], [8, 7], [8, 8], [25, 80]])
# epsilon = 3.0
# min_pts = 2
# dbscan = DBSCAN(eps=epsilon, min_samples=min_pts).fit(X_data)
# labels = dbscan.labels_ # Метки кластеров (-1 для шума)
# print(f"DBSCAN Labels: {labels}")
7.18. Метрика связности (Cohesion)
\[ \text{Cohesion}(C_i) = \sum_{\mathbf{x}_j \in C_i} \|\mathbf{x}_j - \boldsymbol{\mu}_i\|^2 \] (Внутрикластерная сумма квадратов для кластера \(C_i\). Общая связность - сумма по всем кластерам, т.е. \(J\) из k-Means.)Объяснение: Связность измеряет компактность кластеров. Меньшие значения указывают на более плотные, тесные кластеры.
Реализация (для одного кластера):
import numpy as np
# cluster_points - точки, принадлежащие кластеру
# centroid - центроид этого кластера
def calculate_cohesion(cluster_points, centroid):
"""Вычисляет связность (инерцию) одного кластера."""
if len(cluster_points) == 0:
return 0.0
return np.sum(np.linalg.norm(cluster_points - centroid, axis=1)**2)
# Пример (для кластера 0 из примера 7.5)
# cluster0_points = np.array([[1, 2], [3, 4]])
# centroid0 = np.array([2, 3])
# cohesion0 = calculate_cohesion(cluster0_points, centroid0)
# print(f"Cohesion of cluster 0: {cohesion0}") # 4.0
7.19. Метрика разделения (Separation)
\[ \text{Separation} = \sum_{i=1}^{k} \sum_{j=i+1}^{k} d(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)^2 \quad (\text{пример}) \] (Или другие метрики, измеряющие расстояние/различие между кластерами, например, минимальное расстояние между точками разных кластеров)Объяснение: Разделение измеряет расстояние или различие между кластерами. Большие значения указывают на хорошо разделенные кластеры.
Реализация (сумма квадратов расстояний между центроидами):
import numpy as np
# centroids - координаты центроидов (k, n_features)
def calculate_separation_centroids(centroids):
"""Вычисляет сумму квадратов расстояний между центроидами."""
k = len(centroids)
separation = 0
for i in range(k):
for j in range(i + 1, k):
separation += np.linalg.norm(centroids[i] - centroids[j])**2
return separation
# Пример из 7.5
# centroids_km = np.array([[2, 3], [8.5, 9]])
# sep = calculate_separation_centroids(centroids_km)
# print(f"Separation (sum of sq dist between centroids): {sep}")
# ||[2,3]-[8.5,9]||^2 = ||[-6.5, -6]||^2 = (-6.5)^2 + (-6)^2 = 42.25 + 36 = 78.25
7.20. Мягкая принадлежность к кластеру (Soft Clustering Membership)
\[ u_{ij} = \frac{\|\mathbf{x}_j - \mathbf{v}_i\|^{-2/(m-1)}}{\sum_{k=1}^{c} \|\mathbf{x}_j - \mathbf{v}_k\|^{-2/(m-1)}} \] (Формула для обновления принадлежностей в Fuzzy c-Means)Объяснение: Мягкая кластеризация присваивает значения принадлежности \(u_{ij}\) каждой точке к каждому кластеру, указывая степень принадлежности.
Реализация (вычисление принадлежностей для одной точки):
import numpy as np
# point - точка данных (n_features,)
# centroids - центры кластеров (c, n_features)
# m - параметр расплывчатости
def calculate_fuzzy_memberships(point, centroids, m):
"""Вычисляет степени принадлежности точки к кластерам."""
c = len(centroids)
distances = np.linalg.norm(centroids - point, axis=1)
# Обработка случая, когда точка совпадает с центроидом
if np.any(distances == 0):
memberships = np.zeros(c)
memberships[distances == 0] = 1.0
return memberships
# Вычисляем степени -2/(m-1)
exponent = -2.0 / (m - 1)
dist_pow = distances**exponent
# Нормализуем
memberships = dist_pow / np.sum(dist_pow)
return memberships
# Пример
# point_x = np.array([1, 2])
# centroids_fcm = np.array([[1, 1.5], [5.5, 5]])
# m_fuzzifier = 2
# mem = calculate_fuzzy_memberships(point_x, centroids_fcm, m_fuzzifier)
# print(f"Memberships for point {point_x}: {mem}")
# dist = [||[1,2]-[1,1.5]||, ||[1,2]-[5.5,5]||] = [||[0, 0.5]||, ||[-4.5, -3]||] = [0.5, sqrt(20.25+9)=sqrt(29.25)~5.408]
# exp = -2/(2-1) = -2
# dist_pow = [0.5^-2, 5.408^-2] = [4, 1/29.25 ~ 0.034]
# sum_dist_pow = 4 + 0.034 = 4.034
# mem = [4/4.034, 0.034/4.034] ~ [0.991, 0.009] - Сходно с примером 7.9
7.21. Энтропия для оценки кластеризации
\[ H = -\sum_{i=1}^{k} \sum_{j=1}^{l} p_{ij} \log p_{ij} \] (где \(k\) - число кластеров, \(l\) - число истинных классов (если известны), \(p_{ij} = |C_i \cap L_j| / n\) - вероятность того, что случайно выбранный объект принадлежит кластеру \(C_i\) и истинному классу \(L_j\))Объяснение: Энтропия измеряет неопределенность или "чистоту" кластеров по отношению к известным истинным меткам. Меньшие значения указывают на более чистые кластеры (большинство объектов в кластере принадлежат одному истинному классу).
Реализация (используя contingency matrix):
import numpy as np
from sklearn.metrics.cluster import contingency_matrix
import math
# labels_true - истинные метки классов
# labels_pred - метки, присвоенные алгоритмом кластеризации
def clustering_entropy(labels_true, labels_pred):
"""Вычисляет энтропию кластеризации."""
# Матрица сопряженности: строки - истинные классы, столбцы - предсказанные кластеры
cont_matrix = contingency_matrix(labels_true, labels_pred)
n = np.sum(cont_matrix)
# Вычисляем совместные вероятности p_ij
p_ij = cont_matrix / n
# Вычисляем энтропию, игнорируя нулевые вероятности
entropy = -np.sum(p_ij[p_ij > 0] * np.log2(p_ij[p_ij > 0])) # Используем log2 для битов
return entropy
# Пример
# true_labels = np.array([0, 0, 1, 1, 2, 2])
# pred_labels = np.array([0, 0, 0, 1, 1, 1]) # Кластер 0 содержит {0,0,1}, Кластер 1 содержит {1,2,2}
# entropy_val = clustering_entropy(true_labels, pred_labels)
# print(f"Clustering Entropy: {entropy_val}")
7.22. Взаимная информация (Mutual Information) для кластеризации
\[ I(U, V) = \sum_{i=1}^{|U|} \sum_{j=1}^{|V|} P(i, j) \log \frac{P(i, j)}{P(i)P(j)} \] (где U - разбиение по истинным меткам, V - разбиение по кластерам, P(i, j) - вероятность объекта принадлежать классу i и кластеру j, P(i), P(j) - маргинальные вероятности)Объяснение: Взаимная информация измеряет общую информацию (уменьшение неопределенности) между истинными метками и предсказанными кластерами.
Реализация (используя scikit-learn):
from sklearn.metrics import mutual_info_score
import numpy as np
# true_labels = np.array([0, 0, 1, 1, 2, 2])
# pred_labels = np.array([0, 0, 0, 1, 1, 1])
# mi = mutual_info_score(true_labels, pred_labels)
# print(f"Mutual Information: {mi}")
7.23. F-мера (F-Measure) для кластеризации
\[ F = \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} \] (Precision и Recall вычисляются для пар точек: принадлежат ли они одному классу/кластеру)Объяснение: F-мера оценивает производительность кластеризации, балансируя точность (precision) и полноту (recall) на основе пар точек.
Реализация (используя scikit-learn f1_score с усреднением):
Примечание: Прямое использование `f1_score` для кластеризации требует интерпретации кластеров как предсказанных классов. Это не всегда прямолинейно. Чаще используются метрики, основанные на парах (ARI, NMI). Если F-меру применяют, то обычно вычисляют Precision/Recall/F1 для каждого истинного класса относительно предсказанных кластеров и усредняют.
from sklearn.metrics import f1_score
import numpy as np
# true_labels = np.array([0, 0, 1, 1, 2, 2])
# pred_labels = np.array([0, 0, 0, 1, 1, 1])
# Вычисление F1-меры с усреднением (например, 'weighted')
# Это предполагает соответствие меток кластеров истинным меткам, что не всегда так.
# f_measure = f1_score(true_labels, pred_labels, average='weighted')
# print(f"F1 Score (weighted average): {f_measure}")
# Для более строгой оценки кластеризации лучше использовать ARI, NMI.
7.24. Скорректированный индекс Рэнда (ARI - Adjusted Rand Index)
\[ \text{ARI} = \frac{\text{RI} - \text{Expected RI}}{\max(\text{RI}) - \text{Expected RI}} \] (где RI - Индекс Рэнда, Expected RI - ожидаемое значение RI при случайном присвоении меток)Объяснение: ARI корректирует Индекс Рэнда на случайность, измеряя сходство кластеризации с истинными метками. Значения близки к 1 означают идеальное совпадение, 0 - случайное.
Реализация (используя scikit-learn):
from sklearn.metrics import adjusted_rand_score
import numpy as np
# true_labels = np.array([0, 0, 1, 1, 2, 2])
# pred_labels = np.array([0, 0, 0, 1, 1, 1])
# ari = adjusted_rand_score(true_labels, pred_labels)
# print(f"Adjusted Rand Index (ARI): {ari}")
7.25. Нормализованная взаимная информация (NMI - Normalized Mutual Information)
\[ \text{NMI}(U, V) = \frac{I(U, V)}{\sqrt{H(U)H(V)}} \quad (\text{или } \frac{2 I(U, V)}{H(U) + H(V)}) \] (где I(U, V) - взаимная информация, H(U), H(V) - энтропии разбиений U и V)Объяснение: NMI нормализует взаимную информацию для сравнения решений кластеризации разных размеров или с разным количеством кластеров. Значения от 0 до 1.
Реализация (используя scikit-learn):
from sklearn.metrics import normalized_mutual_info_score
import numpy as np
# true_labels = np.array([0, 0, 1, 1, 2, 2])
# pred_labels = np.array([0, 0, 0, 1, 1, 1])
# nmi = normalized_mutual_info_score(true_labels, pred_labels)
# print(f"Normalized Mutual Information (NMI): {nmi}")