Monday, July 4, 2022

Lance-Williams algorithm

 В агломеративной иерархической кластеризации вы начинаете с того, что рассматриваете каждую точку как отдельный кластер. Затем вы объединяете кластеры, чтобы получить кластеры большего размера, пока не получите один кластер, содержащий все точки.

Как вы объединяете кластеры? В начале, когда все кластеры имеют только по одной точке, это тривиально: вы хотите, чтобы расстояние между точками в одном кластере было небольшим (это называется сцеплением), а расстояние между точками в разных кластерах было больше (это называется разделением); поэтому вы объединяете точки, которые находятся ближе всего друг к другу. 

================================

Есть несколько эвристик, которые мы могли бы использовать:

1.Single Linkage или MIN: в этом случае расстояние между двумя кластерами является минимальным из расстояний между любыми двумя точками, каждая из которых взята из одного из кластеров. Это обрабатывает неэллиптические формы, но чувствительно к шуму и выбросам.

2.Полная связь или МАКС: это похоже на первое, но вместо этого мы рассматриваем максимальное расстояние. Это менее чувствительно к шуму и выбросам, но предпочитает шаровидные формы. 

3.Среднее по группе: здесь вы берете среднее расстояние между всеми возможными парами точек, по одной точке из каждого кластера.

4.Метод Ward: в методе Ward вы объединяете кластеры, которые приводят к минимальной дисперсии внутри кластера. 

Другой способ сформулировать это так: вы объединяете кластеры, которые приводят к минимальному увеличению квадрата ошибки.

Алгоритм принадлежит к семейству Ланса-Вильямса, если расстояние d_{(ij)k} может быть рекурсивно вычислено как




При этом мы имеем матрицу







===================================

Выбираем метрику расстояния для измерения расстояния между двумя группами. 

1) Используя метод Ward , в этом методе  вы объединяете кластеры, которые приводят к минимальной дисперсии внутри кластера. Смотри аргументацию (4)

2) На каждой итерации мы объединяем два кластера с наименьшей средней связью в один. Повторяем последний шаг, пока у нас не будет один большой кластер, содержащий все точки данных.

(.env) boris@boris-All-Series:~/AgglomerClustering$ cat CreditCard.py

import pandas as pd

import numpy as np

import matplotlib.pyplot as plt

from sklearn.decomposition import PCA

from sklearn.cluster import AgglomerativeClustering

from sklearn.preprocessing import StandardScaler, normalize

from sklearn.metrics import silhouette_score

import scipy.cluster.hierarchy as shc


X = pd.read_csv('CC_GENERAL.csv')

# Dropping the CUST_ID column from the data

X = X.drop('CUST_ID', axis = 1)

# Handling the missing values

X.fillna(method ='ffill', inplace = True)

# Scaling the data so that all the features become comparable

scaler = StandardScaler()

X_scaled = scaler.fit_transform(X)

# Normalizing the data so that the data approximately

# follows a Gaussian distribution

X_normalized = normalize(X_scaled)

# Converting the numpy array into a pandas DataFrame

X_normalized = pd.DataFrame(X_normalized)

pca = PCA(n_components = 2)

X_principal = pca.fit_transform(X_normalized)

X_principal = pd.DataFrame(X_principal)

X_principal.columns = ['P1', 'P2']

plt.figure(figsize =(8, 8))

plt.title('Visualising the data')

Dendrogram = shc.dendrogram((shc.linkage(X_principal, method ='ward')))

plt.show()






























Изменения последних строк кода

plt.figure(figsize =(8, 8))
plt.title('Visualising the data')
Dendrogram = shc.dendrogram((shc.linkage(X_principal, method ='ward')))

ac5 = AgglomerativeClustering(n_clusters = 5)
 
plt.figure(figsize =(6, 6))
plt.scatter(X_principal['P1'], X_principal['P2'],
            c = ac5.fit_predict(X_principal), cmap ='rainbow')
plt.show()















Использование метода средней связи, где расстояние между двумя кластерами — это среднее расстояние между точками данных в одном кластере и точками данных в другом.
На каждой итерации мы объединяем два кластера с наименьшей средней связью в один.
Повторяйте вышеуказанный шаг, пока у нас не будет один большой кластер, содержащий все точки данных. Плюсы:
Нет необходимости указывать количество кластеров. У вас есть возможность выбрать самые красивые кластеры.Этот алгоритм не чувствителен к выбору метрики расстояния.

No comments:

Post a Comment