Машинное обучение — python (sklearn/scipy) реализует иерархическую кластеризацию, предварительно вычисленную пользовательскую матрицу расстояний

алгоритм

  • Пожалуйста, обратите внимание на источник оригинального текста при перепечатке, спасибо:blog.CSDN.net/Pentium cm/Ах…

Машинное обучение — python (sklearn/scipy) реализует иерархическую кластеризацию, предварительно вычисленную пользовательскую матрицу расстояний

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

Этот блог содержит контент:sklearn / scipyДва способа реализации иерархической кластеризации и в sklearnprecomputedПараметры для реализации пользовательской матрицы расстояний

1. реализация scipy

(1) Описание функции

В основном две функции: связь, fcluster

1. linkage

def linkage(y, method='single', metric='euclidean', optimal_ordering=False):

Объяснение функции функции: выполнить иерархическую/агрегированную кластеризацию.

  1. Параметры:

    • y: Вход y может быть одномерной сжатой матрицей расстояний (вектор расстояния) или двумерным массивом векторов наблюдения (матрица координатных точек).
    • метод: метод относится к методу расчета расстояния между классами.Существуют следующие методы: одиночный, полный, средний, взвешенный, центроидный, подопечный
      • одиночный: ближайший сосед, ближайшее расстояние между классами используется в качестве интервала между классами Найдите расстояние пары ближайших точек от кластера u и кластера v как расстояние кластера u и кластера v:在这里插入图片描述 在这里插入图片描述
      • завершено: самый дальний сосед, расстояние класса - это самое дальнее расстояние между классами Найдите расстояние пары самых дальних точек от кластеров u и v как расстояние кластеров u и v:在这里插入图片描述在这里插入图片描述
      • среднее: среднее расстояние, среднее расстояние между всеми парами между классами Например, есть несколько точек i в кластере u и несколько точек j в кластере v, расстояние между кластером u и кластером v равно:在这里插入图片描述 在这里插入图片描述
      • взвешенный: выполнение цепочки взвешенных/WPGMA на сжатой матрице расстояний Если кластер u состоит из кластера s и кластера t, то расстояние от кластера u до кластера v равно:在这里插入图片描述 在这里插入图片描述
      • centroid: расстояние до центра тяжести, расстояние между классом и центром тяжести в классе используется как расстояние класса在这里插入图片描述
      • ward: свести к минимуму дисперсию объединяемых кластеров.

  2. Возвраты (возвраты):

    • Z (ndarray): Иерархическая кластеризация кодируется как матрица связей.

      Z состоит из четырех столбцов.Первое поле и второе поле - номера кластеров.Перед начальным расстоянием каждое начальное значение идентифицируется от 0 до n-1, и здесь генерируется каждый новый кластер.На основе пара новых кластеров добавляется для идентификации.Третье поле представляет собой расстояние между первыми двумя кластерами, а четвертое поле представляет количество элементов, содержащихся во вновь созданном кластере.

  3. Использованная литература:docs.lastfriend.org/doc/lastfriend/day…


2. fcluster

def fcluster(Z, t, criterion='inconsistent', depth=2, R=None, monocrit=None):

Описание функции: формирует плоские кластеры из иерархических кластеров, определяемых заданной матрицей ссылок.

  1. Параметры:
    • Z: z — полученная Linkage матрица, в которую записывается иерархическая информация;
    • t: порог кластера
    • Критерийstr: критерий формирования плоских кластеров
      • непоследовательный:
      • расстояние: используйте расстояние между кластерами в качестве критерия разделения
  2. Возвраты (возвраты): fcluster(ndarray): Массив длины n. T[i] — количество плоских кластеров, которым принадлежит исходное наблюдение i.
  3. Подробная ссылка:docs.lastfriend.org/doc/lastfriend/day…

(2) Пример содержит полный алгоритм

Например, выполните агломеративную иерархическую кластеризацию по следующим 5 точкам.

x y
точка 0 1 2
пункт 1 2 3
пункт 2 -3 3
пункт 3 -2 -1
пункт 4 5 -1
Положение по осям:在这里插入图片描述Дерево кластеризации результата иерархической кластеризации:在这里插入图片描述
Полный алгоритм выглядит следующим образом:
```python
#!/usr/bin/env python
# encoding: utf-8
'''
@Author : pentiumCM
@Email : 842679178@qq.com
@Software: PyCharm
@File : sci_cluster.py
@Time : 2020/4/15 22:21
@desc: scipy реализует иерархическую кластеризацию
'''

import numpy as np from scipy.cluster.hierarchy import dendrogram, linkage, fcluster

from matplotlib import pyplot as plt

data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])

рисовать точки

plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red') n = np.arange(data.shape[0]) for i, txt in enumerate(n): plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2])) plt.show()

1. Иерархическая кластеризация

Метод сцепления используется для вычисления расстояния d(s,t) между двумя кластерами s и t.

Иерархическая кластеризация кодируется как матрица связей.

Z = связь (данные, «среднее») print("Процесс кластеризации: ", Z)

Формирует плоские кластеры из иерархических кластеров, определяемых заданной матрицей связей.

расстояние: критерий деления расстояния на расстояние

f = fcluster(Z, 4, 'расстояние') print("Результат планарной кластеризации: ", f)

fig = plt.figure(figsize=(5, 3))

Результаты иерархической кластеризации представлены в виде дендрограммы

dn = dendrogram(Z) plt.show()

算法运行结果：
```python
聚类过程： [[0.         1.         1.41421356 2.        ]
 [2.         3.         4.12310563 2.        ]
 [5.         6.         4.75565014 4.        ]
 [4.         7.         6.48606798 5.        ]]
平面聚类结果： [1 1 2 3 4]

Основная информация для кластеризации содержится в Z = linkage(data, 'average'). Z состоит из четырех столбцов.Первое поле и второе поле - номера кластеров.Перед начальным расстоянием каждое начальное значение идентифицируется от 0 до n-1, и здесь генерируется каждый новый кластер.На основе пара новых кластеров добавляется для идентификации.Третье поле представляет собой расстояние между первыми двумя кластерами, а четвертое поле представляет количество элементов, содержащихся во вновь созданном кластере.


Иерархическая кластеризация может сгруппировать все случаи одновременно.Когда результаты дерева кластеризации сгенерированы, вы можете нарисовать горизонтальную линию на дереве кластеризации (например, в приведенном выше алгоритме горизонтальная линия основана на расстоянии между кластерами ) Выберите результаты, сгруппированные по категориям. Если пользователей нужно разделить на две категории:在这里插入图片描述Необходимо только провести горизонтальную линию, как показано на рисунке выше, сверху вниз, чтобы оценить результаты двух групп.Можно видеть, что есть два типа результатов: один равен 4, а другой равен 0, 1, 2 и 3. Если вам нужно выполнить кластеризацию по трем категориям, вам нужно всего лишь перевести горизонтальную линию вниз, чтобы узнать результаты кластеризации по трем категориям.


Во-вторых, реализация sklearn

(1) Описание функции

Иерархическая кластеризация в библиотеке sklearn находится в AgglomerativeClustering sklearn.cluster:

def __init__(self, n_clusters=2, affinity="euclidean",
             memory=None,
             connectivity=None, compute_full_tree='auto',
             linkage='ward', distance_threshold=None):

Параметр конструктора класса AgglomerativeClustering имеет количество кластеровn_clusters, способ подключенияlinkage, параметры метрик соединенияaffinityТри важных параметра:

  • n_clusters: пользователь указывает, сколько категорий будет кластеризовано.

  • linkage: Выберите стратегию расчета расстояния между кластерами, в том числе: подопечный, полный, средний, одиночный

    • ward: свести к минимуму дисперсию объединяемых кластеров.
    • полное: полное расстояние/максимальное расстояние, используя максимальное расстояние между всеми наблюдениями в обеих группах.
    • single: минимальное расстояние, использующее минимальное расстояние между всеми наблюдениями в двух группах.
    • среднее: Среднее расстояние, используя среднее значение расстояний для каждого наблюдения двух групп.

  • affinity: метод расчета расстояния между кластерами. Может быть «евклидовым», «l1», «l2», «манхэттенским», «косинусным» или «предварительно вычисленным».

    • Если связь «направленная», принимается только «евклидово расстояние».

    • Если «предварительно вычислено», в качестве входных данных для метода подбора требуется матрица расстояний.

      距离矩阵Метод генерации: Предполагая, что у пользователя есть n точек наблюдения, сначала создайте список расстояний между этими n точками по очереди, то есть список расстояний с длиной n * (n-1)/2, а затем передайте scipy.spatial .distance Функция Squareform библиотеки dist может построить матрицу расстояний. Преимущество этого метода заключается в том, что пользователи могут использовать свой собственный определенный метод для расчета расстояния между любыми двумя точками наблюдения, а затем выполнять кластеризацию. Алгоритм кластеризации, основанный на пользовательской матрице расстояний, также будет приведен позже.

Использованная литература:исходная документация


(2) Полный алгоритм

#!/usr/bin/env python
# encoding: utf-8
'''
@Author  : pentiumCM
@Email   : 842679178@qq.com
@Software: PyCharm
@File    : sklearn_hierarchical_cluster.py
@Time    : 2020/4/23 15:00
@desc	 : sklearn的层次聚类
'''

import numpy as np
from matplotlib import pyplot as plt

from sklearn.cluster import AgglomerativeClustering

data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])

# 画点
plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red')
n = np.arange(data.shape[0])
for i, txt in enumerate(n):
    plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2]))
plt.show()

# 训练模型
ac = AgglomerativeClustering(n_clusters=3, affinity='euclidean', linkage='average')
clustering = ac.fit(data)

print("每个数据所属的簇编号", clustering.labels_)
print("每个簇的成员", clustering.children_)

Результат работы алгоритма:

每个数据所属的簇编号 [2 2 0 0 1]
每个簇的成员 [[0 1]
 			[2 3]
 			[5 6]
 			[4 7]]

С помощью дерева кластеризации, сгенерированного scipy, давайте разберемся с результатами кластеризации:

在这里插入图片描述clustering.labels_: указывает, к какому кластеру принадлежат данные.   [2 2 0 0 1]: указывает, что данные 0 и 1 разделены на кластер, 2 и 3 разделены на кластер и 4 разделены на кластер. clustering.children_: указывает, какие элементы находятся в каждом кластере. [[0 1] [2 3] [5 6] [4 7]]: сначала инициализируйте данные как кластеры 0 ~ n-1, затем объедините кластеры 0 и 1 в кластер 5 и объедините кластеры 2 и 3 в кластер 6. , Кластеры 5 и 6 объединяются в кластер 7, и, наконец, объединяются кластеры 4 и 7.


Дополнительные алгоритмы на основе предварительно вычисленных матриц расстояний

Полный алгоритм выглядит следующим образом:

#!/usr/bin/env python
# encoding: utf-8
'''
@Author  : pentiumCM
@Email   : 842679178@qq.com
@Software: PyCharm
@File    : sklearn_hierarchical_cluster.py
@Time    : 2020/4/23 15:00
@desc	 : sklearn的层次聚类
'''

import numpy as np
from matplotlib import pyplot as plt

from sklearn.cluster import AgglomerativeClustering

from sklearn.metrics.pairwise import euclidean_distances
import scipy.spatial.distance as dist
from scipy.cluster.hierarchy import dendrogram, linkage

data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])

# 画点
plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red')
n = np.arange(data.shape[0])
for i, txt in enumerate(n):
    plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2]))
plt.show()

# 聚类方式一
# 训练模型
ac = AgglomerativeClustering(n_clusters=3, affinity='euclidean', linkage='average')
clustering = ac.fit(data)

print("每个数据所属的簇编号：", clustering.labels_)
print("每个簇的成员：", clustering.children_)

# 聚类的方式二
# 自定义距离矩阵
num = data.shape[0]
dist_matrix = np.mat(np.zeros((num, num)))
for i in range(num):
    for j in range(i, num):
        distence = euclidean_distances(data[i:i + 1], data[j:j + 1])
        dist_matrix[i:i + 1, j:j + 1] = distence
        dist_matrix[j:j + 1, i:i + 1] = dist_matrix[i:i + 1, j:j + 1]

# 基于自定义的聚类矩阵进行聚类
model = AgglomerativeClustering(n_clusters=3, affinity='precomputed', linkage='average')
clustering2 = model.fit(dist_matrix)

print("自定义距离矩阵聚类方式：")
print("每个数据所属的簇编号：", clustering2.labels_)
print("每个簇的成员：", clustering2.children_)

# 调整距离矩阵的形状
dist_matrix = dist.squareform(dist_matrix)

# linkage方法用于计算两个聚类簇s和t之间的距离d(s,t)
# 层次聚类编码为一个linkage矩阵。
Z = linkage(dist_matrix, 'average')
print("聚类过程：", Z)

# 将层级聚类结果以树状图表示出来
fig = plt.figure(figsize=(5, 3))
dn = dendrogram(Z)
plt.show()

Результат работы алгоритма:

每个数据所属的簇编号： [2 2 0 0 1]
每个簇的成员： [[0 1]
			  [2 3]
			  [5 6]
			  [4 7]]
自定义距离矩阵聚类方式：
每个数据所属的簇编号： [2 2 0 0 1]
每个簇的成员： [[0 1]
			  [2 3]
			  [5 6]
			  [4 7]]
聚类过程： [[0.         1.         1.41421356 2.        ]
		  [2.         3.         4.12310563 2.        ]
		  [5.         6.         4.75565014 4.        ]
		  [4.         7.         6.48606798 5.        ]]

Приведенный выше алгоритм включает в себя два метода кластеризации sklearn.Второй метод — это метод предварительного расчета: алгоритм предварительно вычисляет матрицу расстояний dist_matrix между каждой точкой данных в начале периода, а затем при кластеризации affinity='precomputed' .


Напротив, для простого для понимания способа иерархической кластеризации вы можете использовать scipy.


использованная литература

Категории