кластерный анализ текста

[gamm]

из личного опыта. Нужно сначала сделать квантизацию векторов (заменить выборку относительно небольшим числом эталонов - мы обычно использовали 1-3 тысячи), а потом кластеризовать эти эталоны. Для построения эталонов мы использовали Кохоненовский SOM с сеткой 30х30 и более, или нейронный газ (строили не в R), в качестве эталонов брали средние, посчитанные по построенным классам. Эти методы хороши тем, что не нужно считать матрицу расстояний, поэтому работают и на миллионах точек.

Можно для LVQ попробовать и алгоритм Isodata, либо найти иерархический кластеризатор, который работает на больших данных.

[sergsh]

15770 объектов при Иерархической классификации требуют матрицу расстояний ВСЕХ со ВСЕМИ, а это примерно (15770*15770)/2, то есть массив размером 124 346 450
Поэтому в лоб иерархическая классификация для набора 15770 объектов не очень применима.

Я бы сделал для начала простую частотную классификацию для оценки наличия кластеров в данных.
То есть собрал бы 2D частоты встречаемости данных попарно из 3 факторов, и посмотрел - есть ли вообще там неоднородности
Это кстати можно делать на слабой машинке ...

[sergsh]

Можно для LVQ попробовать и алгоритм Isodata, либо найти иерархический кластеризатор, который работает на больших данных.

Gamm, а может быть такой - Иерархический, но для больших данных ?
Вы знаете такой ?
Что то типа отбора и объединения малых расстояний уже на этапе расчета матрицы расстояний ?

Как можно избежать матрицы расстояний всех со всеми ?

[sergsh]

Можно для LVQ попробовать и алгоритм Isodata, либо найти иерархический кластеризатор, который работает на больших данных.

Gamm, а может быть такой - Иерархический, но для больших данных ?
Вы знаете такой ?
Что то типа отбора и объединения малых расстояний уже на этапе расчета матрицы расстояний ?
Получаем в результате редкую матрицу расстояний и ее специально храним как разряженную ?

Как можно избежать матрицы расстояний всех со всеми ?

[gamm]

15770 объектов при Иерархической классификации требуют матрицу расстояний ВСЕХ со ВСЕМИ

можно и напрямую, например

Спойлер

you don't want to use the entire matrix to calculate the distance. You
will want to select the environmental columns and you may want to
standardize them to prevent one of them having more influence than
others.

Second, if you want to cluster such a huge data set using hierarchical
clustering, you need a lot of memory, at least 32GB but preferably
64GB. If you don't have that much, you cannot use hierarchical
clustering.

Third, if you do have enough memory, use package flashClust or
fastcluster (I am the maintainer of flashClust.)
For flashClust, you can install it using
install.packages("flashClust") and load it using library(flashClust).
The standard R implementation of hclust is unnecessarily slow (order
n^3). flashClust provides a replacement (function hclust) that is
approximately n^2. I have clustered data sets of 30000 variables in a
minute or two, so 55000 shouldn't take more than 4-5 minutes, again
assuming your computer has enough memory. тыц

наверняка есть и методы без вычисления матрицы, основанные на индексации пространства (k-d деревья и пр. => (O(n*log(n)))), но но сразу не нашел. Но сам подобное писал

[edvardoss]

Как можно избежать матрицы расстояний всех со всеми ?

учитывая срочность задачи написал алгоритм (вне R) который упорядочивает весь массив объектов в спектр аналогично разложению белого света на его оттенки, упорядоченные по своей схожести и плавно перетекающие друг в друга. ( Упорядочивание происходит по конкатенации предварительно рассчитанных индексов на основе веса токена по 10б.шкале и порядковому индексу токена). После пары итераций по ручной коррекции весов некоторых токенов алгоритм выдал очень и очень пристойный результат. Время отработки для 15770 объектов- 4 минуты. Фишка в том что расстояния я считаю не до упорядочивания а уже после: прохожу отдельной процедурой для расчета расстояний между текущим и предыдущим объектом в спектре по алгоритму Жаккара, итого количество расчетов=количество объектов-1 (это еще 3 минуты). После этого в спектре появляется метрика контрастов между объектами : в кластерах контраст визуально мал, в переходах между кластерами-велик. Как-то так...
Скорее всего изобрел велосипед и попутно открыл америку, тогда буду рад увидеть как данный метод называется:)
Тем не менее не хочется отходить от классических подходов unsupervized learning , отсюда вопрос:

Нужно сначала сделать квантизацию векторов (заменить выборку относительно небольшим числом эталонов - мы обычно использовали 1-3 тысячи), а потом кластеризовать эти эталоны. Для построения эталонов мы использовали Кохоненовский SOM с сеткой 30х30 и более

gamm, можно примерчик на R по отбору эталонов?

[gamm]

1. похоже на ординцию сообществ в Turboveg, название алгоритма не помню. Вроде twinspan. Кстати, неоднократно предложенный вам SOM покажет те же контрасты на 2D плоскости, если сделать побольше классов.

2. Можно k-means с большим числом классов, можно fuzzy c-means, isodata, тот же SOM. Как функции зовут, не помню, там несколько вариантов есть.

[ Сообщение с мобильного устройства ]