Кластеризация - это группировка объектов вместе, чтобы объекты, принадлежащие к одной группе (кластеру), были более похожи друг на друга, чем объекты в других группах (кластерах). В этом вводном руководстве по кластерному анализу мы рассмотрим несколько алгоритмов на Python, чтобы вы могли получить базовое представление об основах кластеризации на реальном наборе данных.
Набор данных
Для задачи кластеризации мы будем использовать знаменитый набор данных Zachary’s Karate Club. История, лежащая в основе набора данных, довольно проста: существовал клуб карате, в котором был администратор «Джон А» и инструктор «Мистер. Привет »(оба псевдонима). Затем между ними возник конфликт, в результате которого ученики (Узлы) разделились на две группы. Один последовал за Джоном, а другой - за мистером Хай.
Начало работы с кластеризацией в Python
Но достаточно вступительной речи, давайте перейдем к основной причине, по которой вы здесь, - к самому коду. Прежде всего, вам необходимо установить библиотеки scikit-learn и networkx для выполнения этого руководства. Если вы не знаете, как это сделать, ссылки выше должны вам помочь. Кроме того, не стесняйтесь следовать, скачивая исходный код этого руководства на Github.
Обычно наборы данных, которые мы хотим исследовать, доступны в текстовой форме (JSON, Excel, простой текстовый файл и т. Д.), Но в нашем случае networkx предоставляет их нам. Кроме того, чтобы сравнить наши алгоритмы, нам нужна правда о членах (кто за кем следил), которая, к сожалению, не предоставляется. Но с помощью этих двух строк кода вы сможете загрузить данные и сохранить правду (с этого момента мы будем называть это истинным фактом):
# Load and Store both data and groundtruth of Zachary's Karate Club G = nx.karate_club_graph()groundTruth = [0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,0, 0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1]
Последний шаг предварительной обработки данных - преобразование графа в матрицу (желательный ввод для наших алгоритмов). Это тоже довольно просто:
def graphToEdgeMatrix(G):
# Initialize Edge Matrix
edgeMat = [[0 for x in range(len(G))] for y in range(len(G))]
# For loop to set 0 or 1 ( diagonal elements are set to 1)
for node in G:
tempNeighList = G.neighbors(node)
for neighbor in tempNeighList:
edgeMat[node][neighbor] = 1
edgeMat[node][node] = 1 return edgeMatПрежде чем мы перейдем к методам кластеризации, я хотел бы, чтобы вы визуализировали наши данные. Итак, давайте скомпилируем для этого простую функцию:
def drawCommunities(G, partition, pos):
# G is graph in networkx form
# Partition is a dict containing info on clusters
# Pos is base on networkx spring layout (nx.spring_layout(G))
# For separating communities colors
dictList = defaultdict(list)
nodelist = []
for node, com in partition.items():
dictList[com].append(node)
# Get size of Communities
size = len(set(partition.values()))
# For loop to assign communities colors
for i in range(size):
amplifier = i % 3
multi = (i / 3) * 0.3
red = green = blue = 0
if amplifier == 0:
red = 0.1 + multi
elif amplifier == 1:
green = 0.1 + multi
else:
blue = 0.1 + multi
# Draw Nodes
nx.draw_networkx_nodes(G, pos,
nodelist=dictList[i],
node_color=[0.0 + red, 0.0 +
green, 0.0 + blue],
node_size=500,
alpha=0.8)
# Draw edges and final plot
plt.title("Zachary's Karate Club")
nx.draw_networkx_edges(G, pos, alpha=0.5)Что делает эта функция, так это просто извлекает количество кластеров, которые есть в нашем результате, и затем назначает другой цвет каждому из них (до 10 в течение заданного времени нормально) перед их построением.
Алгоритмы кластеризации
Некоторые алгоритмы кластеризации довольно хорошо сгруппируют ваши данные, а другие в конечном итоге этого не сделают. Это одна из основных причин, почему кластеризация является такой сложной проблемой. Но не волнуйтесь, мы не дадим вам утонуть в океане выбора. Мы рассмотрим несколько алгоритмов, которые, как известно, работают очень хорошо.
Кластеризация K-средних
Многие считают K-means золотым стандартом кластеризации из-за его простоты и производительности, и это первый метод, который мы попробуем. Когда вы вообще не знаете, какой алгоритм использовать, обычно первым выбором будет K-средство. Имейте в виду, что K-средства могут иногда неэффективно работать из-за своей концепции: сферические кластеры, которые можно отделить таким образом, чтобы среднее значение сходилось к центру кластера. Чтобы просто построить и обучить модель K-средних, используйте следующие строки:
kmeans = cluster.KMeans(n_clusters=kClusters, n_init=200)
kmeans.fit(edgeMat)
# Transform our data to list form and store them in results list
results.append(list(kmeans.labels_))Агломеративная кластеризация
Основная идея агломеративной кластеризации заключается в том, что каждый узел начинается в своем собственном кластере и рекурсивно сливается с парой кластеров, что минимально увеличивает заданное расстояние связи. Основное преимущество агломеративной кластеризации (и иерархической кластеризации в целом) заключается в том, что вам не нужно указывать количество кластеров. Конечно, за это приходится платить: производительность. Но в реализации scikit вы можете указать количество кластеров, чтобы повысить производительность алгоритма. Для создания и обучения агломеративной модели используйте следующий код:
agglomerative = cluster.AgglomerativeClustering(
n_clusters=kClusters, linkage="ward")
agglomerative.fit(edgeMat)
# Transform our data to list form and store them in results list
results.append(list(agglomerative.labels_))Spectral
Метод спектральной кластеризации применяет кластеризацию к проекции нормализованного лапласиана. Когда дело доходит до кластеризации изображений, спектральная кластеризация работает достаточно хорошо. Посмотрите следующие несколько строк Python, чтобы увидеть всю магию:
spectral = cluster.SpectralClustering(n_clusters=kClusters, affinity="precomputed", n_init= 200)
spectral.fit(edgeMat)
# Transform our data to list form and store them in results list
results.append(list(spectral.labels_))Распространение сродства
Ну, это немного другое. В отличие от предыдущих алгоритмов, вы можете видеть, что AF не требует определения количества кластеров перед запуском алгоритма. AF очень хорошо справляется с несколькими проблемами компьютерного зрения и биологии, такими как кластеризация изображений человеческих лиц и идентификация регулируемых транскриптов:
affinity = cluster.affinity_propagation(S=edgeMat, max_iter=200, damping=0.6)
# Transform our data to list form and store them in results list
results.append(list(affinity[1]))Метрики и графики
Что ж, пора выбрать, какой алгоритм больше подходит для наших данных. Простая визуализация результата может работать с небольшими наборами данных, но представьте себе граф с тысячей или даже десятью тысячами узлов. Для человеческого глаза это было бы немного хаотично. Итак, позвольте мне показать, как рассчитать скорректированную оценку ранда (ARS) и нормализованную взаимную информацию (NMI):
# Append the results into lists
for x in results:
nmiResults.append(normalized_mutual_info_score(groundTruth, x))
arsResults.append(adjusted_rand_score(groundTruth, x))Если вы не знакомы с этими показателями, вот краткое объяснение:
Нормализованная взаимная информация (NMI)
Взаимная информация двух случайных величин является мерой взаимной зависимости между двумя переменными. Нормализованная взаимная информация - это нормализация оценки взаимной информации (MI) для масштабирования результатов от 0 (отсутствие взаимной информации) до 1 (идеальная корреляция). Другими словами, 0 означает несходство, а 1 - полное совпадение.
Скорректированная оценка Rand (ARS)
Скорректированная оценка Rand, с другой стороны, вычисляет меру сходства между двумя кластерами, рассматривая все пары выборок и подсчитывая пары, которые назначены в одном или разных кластерах в прогнозируемом и истинном кластерах. Если это немного странно, имейте в виду, что на данный момент 0 - это наименьшее сходство, а 1 - самое высокое.
Итак, чтобы получить комбинацию этих показателей (NMI и ARS), мы просто вычисляем среднее значение их суммы. И помните, чем выше цифра, тем лучше результат.
Ниже я построил оценку результатов, чтобы мы могли лучше понять наши результаты. Мы могли бы построить их разными способами, как точки, как прямую линию, но я думаю, что столбчатая диаграмма - лучший выбор для нашего случая. Для этого просто используйте следующий код:
# Code for plotting results
# Average of NMI and ARS
y = [sum(x) / 2 for x in zip(nmiResults, arsResults)]
xlabels = ['Spectral', 'Agglomerative', 'Kmeans', 'Affinity Propagation']
fig = plt.figure()
ax = fig.add_subplot(111)
# Set parameters for plotting
ind = np.arange(len(y))
width = 0.35
# Create barchart and set the axis limits and titles
ax.bar(ind, y, width,color='blue', error_kw=dict(elinewidth=2, ecolor='red'))
ax.set_xlim(-width, len(ind)+width)
ax.set_ylim(0,2)
ax.set_ylabel('Average Score (NMI, ARS)')
ax.set_title('Score Evaluation')
# Add the xlabels to the chart
ax.set_xticks(ind + width / 2)
xtickNames = ax.set_xticklabels(xlabels)
plt.setp(xtickNames, fontsize=12)
# Add the actual value on top of each chart
for i, v in enumerate(y):
ax.text( i, v, str(round(v, 2)), color='blue', fontweight='bold')
# Show the final plot
plt.show()
Как вы можете видеть на приведенной выше диаграмме, K-среднее и агломеративная кластеризация дают наилучшие результаты для нашего набора данных (наилучший возможный результат). Это, конечно, не означает, что Spectral и AF являются низкоэффективными алгоритмами, просто они не соответствуют нашим данным.
Ну вот и все!
Спасибо, что присоединились ко мне в этом вступлении о кластеризации. Надеюсь, вы нашли ценность в том, чтобы увидеть, как мы можем легко управлять общедоступным набором данных и применять несколько различных алгоритмов кластеризации в Python. Дайте мне знать, если у вас есть какие-либо вопросы в комментариях ниже, и не стесняйтесь прикреплять проект кластеризации, с которым вы экспериментировали!
Первоначально опубликовано здесь: http://www.learndatasci.com/k-means-clustering-algorithms-python-intro/
