Я пытаюсь реализовать иерархическую кластеризацию в R: hclust(); для этого требуется матрица расстояний, созданная dist(), но у моего набора данных есть около миллиона строк, и даже экземпляры EC2 исчерпывают ОЗУ. Есть ли обходной путь?hclust() в R на больших наборах данных
Одним из возможных решений для этого является выборка данных, кластер меньшего образца, затем обработка кластеризованного образца в качестве учебных данных для k ближайших соседей и «классификация» остальной части данных. Вот краткий пример с строками 1.1M. Я использую образец из 5000 пунктов. Исходные данные не хорошо разделены, но только с 1/220 данных образец отделяется. Поскольку ваш вопрос относится к hclust, я использовал это. Но вы можете использовать другие алгоритмы кластеризации, такие как dbscan или средний сдвиг.
## Generate data
set.seed(2017)
x = c(rnorm(250000, 0,0.9), rnorm(350000, 4,1), rnorm(500000, -5,1.1))
y = c(rnorm(250000, 0,0.9), rnorm(350000, 5.5,1), rnorm(500000, 5,1.1))
XY = data.frame(x,y)
Sample5K = sample(length(x), 5000) ## Downsample
## Cluster the sample
DM5K = dist(XY[Sample5K,])
HC5K = hclust(DM5K, method="single")
Groups = cutree(HC5K, 8)
Groups[Groups>4] = 4
plot(XY[Sample5K,], pch=20, col=rainbow(4, alpha=c(0.2,0.2,0.2,1))[Groups])
Теперь просто присвоить все остальные точки до ближайшего кластера.
Core = which(Groups<4)
library(class)
knnClust = knn(XY[Sample5K[Core], ], XY, Groups[Core])
plot(XY, pch=20, col=rainbow(3, alpha=0.1)[knnClust])
Несколько быстрых заметок.
Это кластеры данных, они не выполняют иерархическую кластеризацию. Обычная кластеризация просто делит вещи на определенное количество групп, иерархическая кластеризация делает «семейное дерево» для всех данных, присваивая каждой отдельной точке данных определенное место в дереве. – Barker
@ Баркер - да. Согласен. Это не иерархическая кластеризация на полных данных. – G5W
Конечные результаты не являются иерархической кластеризацией вообще (или, в лучшем случае, это иерархия из 3), вы выкинули все отношения между группами, когда вы разрезали дерево, и просто использовали верхние 3 кластера для вашего классификатора. Вы можете получить своего рода полу иерархию, если бы вы сохранили все ваши 5000 групп из «hclust» и назначили остальную часть данных каждому из 5000 филиалов. Затем вы могли бы создать реальную иерархию (хотя и с некоторыми потенциальными ошибками), если затем вы запустили 'hclust' на каждой из групп, а затем подключили их обратно к дереву. – Barker
Наилучший подход здесь, вероятно, состоит в том, чтобы сделать подмножества ваших данных, которые наиболее близки друг к другу (возможно, с использованием другого алгоритма кластеризации, такого как KNN), а затем сделать иерархические кластеры этих подмножеств, а затем, наконец, назначить каждый кластер местоположение в иерархии. [This post] (http://stackoverflow.com/questions/9156961/hierarchical-clustering-of-1-million-objects) обсуждает эту основную идею. Реализация в сообщении находится в [tag: python], но большинство из них просто обсуждают идеи, а не код. – Barker
Кроме того, посмотрите на пакет ['Rclusterpp'] (https://cran.r-project.org/web/packages/Rclusterpp/vignettes/Rclusterpp.pdf) для более эффективного иерархического алгоритма кластеризации. – Barker
Возможный дубликат [Матрица большого расстояния в кластеризации] (http://stackoverflow.com/questions/34281593/large-distance-matrix-in-clustering) – Barker